《东南大学信息安全课件》由会员分享，可在线阅读，更多相关《东南大学信息安全课件（28页珍藏版）》请在金锄头文库上搜索。
1、第二章 信息安全数学基础东南大学 网络空间安全学科胡爱群 教授2024/9/201主要内容素数、素数性质 、大素数生成方法；同余、中国剩余定理；群、环、域、有限域。2024/9/202素数定义：设整数n0, 1。如果除了 1和 n外，n没有其它因数 （因子），则n是素数（或质数、不可约数）。否则n叫合数。素数总是指正整数，通常写成 p.例子： 2，3，5，7都是素数，而4，6，10，15，21都是合数。2024/9/203互素的概念(a,b)=(b,a);如果 b|a, 则（a,b）=b;如果 pa，则（p,a）=1,即互素。a,b是整数，p是素数2024/9/204素数的判定和生成2024/
2、9/205练习：判断139为素数还是合数？2024/9/206同余的概念练习：39=4 mod(7); 61=5 mod(7).2024/9/207Euler函数定义： 设m是一个正整数，把0,1,m-1中与m互素的数的个数记作(m), (m)就叫做Euler函数。练习： 求(10)=？ (77)=?定理： 设m、n是两个互素的正整数，则(mn)=(m)(n).2024/9/208对于素数m ，(m)=?Euler函数的推论设p、q是不同的素数，则 （1）(pq)=pq-p-q+1.设n=pq, 则（2）如果知道n和(n)，就可求出p和q.练习：证明素数的性质（1）和（2）。可求解该二元方程组
3、得到p和q.2024/9/209Euler定理设m是大于1的整数，(m)是m的Euler函数。如果a是满足（a,m）=1的整数，则 练习：验证 210=1 mod(11)。解：m=11, a=2, (m)=10, (2,11)=1, 根据Euler定理，上式成立。 也可以这样做：210=1024=1023+1=93*11+1=1 mod(11)2024/9/2010Fermat定理练习：p=17, a=4, 417=4 mod (17)2024/9/2011大素数的生成逐个查找太费时间，可以利用Euler定理进行检验，称为Fermat素性检验。Euler定理：设n是大于1的整数，(n)是n的E
4、uler函数。如果a是满足（a,n）=1的整数，则 如果n是一个素数，则(n)=n-1, 有an-1=1 mod(n). 反过来说，如果有一个整数a, 且（a, n）=1, 使得an-11 mod(n), 那么n是一个合数，不是素数。例子：n=63. 假定a=2, 262=26022=(26)10 22=6410 221 mod(63)因此63不是素数。=1 mod(63)2024/9/2012素性检验给定奇数n3和安全参数t，随机选取整数b, 2bn-2;计算r=bn-1 (mod n);如果r1, 则n是合数；重复上述过程t次。注意：上述方法可以检验出来是合数，但若满足r=1的n未必是素数
5、。练习：n=561是合数，但依然满足r=1.提示：561=3.11.172024/9/2013中国剩余定理2024/9/20142024/9/2015求解韩信点兵问题：2024/9/2016利用中国剩余定理求解大的幂次数2024/9/2017Euclid除法及广义Euclid除法任意两个整数a、b(b0),则对于任意的整数c, 存在唯一的整数q、r，使得 a=qb+r，crb+c.例子： 121=248+25例子：设a=169, b=121, 求a和b的最大公因子，即（a,b）利用广义Euclid除法： 169=1121+48 121=2 48+25 48=1 25+23 25=1 23+2
6、23=11 2+1 2=2 1 因此 （169，121）=1. 2024/9/2018RSA算法中私钥的计算设有两个素数p=719, q=1283.n=p q=719 1283=922477(n)=(p) (q)=(p-1)(q-1)=920476随机选取整数e, 1e(n), 使得（e, (n)）=1.公钥是Kp=n,e, 私钥为d, 1d d=6574832024/9/2019群的概念定义：设G是一个具有结合法的非空集合，如果：（1）满足结合律： a,b,cG, 都有 (ab)c=a(bc);（2）G中存在单位元： e G, 对任意aG，都有 ae=ea=a;（3）G中的元素具有可逆元：
7、对任意aG， a-1 G, 使得aa-1=a-1a=e.G的结合法写作乘法时，G称为乘群；G的结合法写作加法时，G称为加群。2024/9/2020同态的概念设G、G是两个群，f是G到G的一个映射，如果对任意的a、bG，都有 f(ab)=f(a)f(b)则f叫做G到G的一个同态。如果f是一个加密过程，即 E(ab)=E(a)E(b), 称为乘同态。 E(a+b)=E(a)+E(b), 称为加同态。 2024/9/2021环的概念定义：设R具有两种结合法（通常表示为加法和乘法）的非空集合，如果下列条件成立：（1）R对于加法构成一个交换群；（2）（结合律） a,b,cR, 都有 (ab)c=a(bc
8、);（3）（分配律） a,b,cR, 都有a(b+c)=ab+ac;则R叫做环。2024/9/2022有限域的概念集合F=a，b，对F的元素定义了两种运算：“+”和“*”，并满足以下3个条件：（1）F的元素关于运算“+”构成交换群，设其单位元素为0；（2）F0的元素关于运算“*”构成交换群。即F中元素排除元素0后，关于“*”法构成交换群。（3）分配律成立，即对于任意元素a，b，cF，恒有a*(b+c)=(b+c)*a=a*b+a*c。p是素数时，F0，1，2，p-1，在mod p意义下，关于求和运算“+” 及乘积“*”，构成了域。F域的元素数目有限时称为有限域, 记为GF(p)。有限域元素的数
9、目称为有限域的阶。2024/9/2023GF(p)有限域中的运算p=52024/9/2024三大难解数学问题 1、大整数的因数分解问题给定两个大的素数p、q, 计算乘积p q=n很容易；给定大整数n，求n的素因数p、q，使得n=p q非常困难。 如：p=20000000000000002559, q=8000000000000001239是两个大素数，它们的乘积 n=1600000000000000229500000000000003170601但要分解这个数很困难。2024/9/20252、离散对数问题已知有限循环群G=gk|k=0,1,2,及其生成元g和阶n=|G|.给定整数a, 计算元素
10、ga=h很容易；给定元素h, 计算整数x, 0xn, 使得gx=h非常困难。例如：给定p=20000000000000002559, g=11,a=20030428, 可以计算出ga=1134889584997235257 (mod p)但要求整数x, 使得gx=1134889584997235257 (mod p) 非常困难。2024/9/20263、椭圆曲线离散对数问题已知有限域Fp上的椭圆曲线点群E(Fp)=(x,y)FpFp|y2=x3+ax+b, a,bFpUO点P=(x,y)的阶为一个大的素数。给定整数a, 计算点Q=aP=(xa, ya)很容易；给定点Q，计算整数x, 使得 xP=Q非常困难。2024/9/2027习题1. 利用素数判定定理，求所有不超过110的素数.2. 证明N=131为素数.3. 求m=91的Euler函数(91)=?4. 用Euler定理，验证 212=1 mod(11).5. 用中国剩余定理，求 x=2100000 mod(55).2024/9/2028
