5第4章公钥密码体制086.ppt

网络工程08级 主要内容 公钥密码体制的产生 数论基础 公钥密码体制的基本原理 RSA公钥密码体制 其它公钥密码算法 素数(prime number)和数的互素 定义：如果整数p(p1)只能被1或者它本身整除，而不能被其他整数整除，则其为素数(质数) ，否则为合数。 素数定理： 在各种应用中，我们需要大的素数,如100位的素数 素数是构成整数的因子，每一个整数都是由一个或几个素数的不同次幂相乘得来的。 算术基本定理： 任何一个不等于0的正整数a都可以写成唯一的表达式 a＝P1α1P2α2…Ptαt， 这里P1P2P3…Pt是素数，其中αi0  数论导引 素数和数的互素 除数(因子)的概念：设z为所有全体整数构成的集合，若 b≠0且 使得a=mb , 此时称b整除a.记为b∣a,还称b为a的除数(因子). 注:若a=mb+r且0rb,此时b不整除a,记为b┼a定义：若a?x mod n =1，则称a与x对于模n互为逆元。 用扩展Euclid算法求乘法逆元 若a和n互素，则a在模n下有逆元。 最大公约数 a和b的最大公约数是能够同时整除a和b的最大正整数，记为gcd(a,b)。 如果gcd(a,b)=1，则说a和b是互素的。 定理： 设a和b是两个整数(至少一个非0)， d=gcd(a,b)，则存在整数x和y，使得ax+by=d 特殊地，如果a和b互素，则有整数x和y，使得ax+by=1 同余 设整数a，b，n(n ≠0)，如果a-b是n的整数倍，则a≡b(mod n)，即a同余于b模n。也可理解为a/n的余数等于b/n的余数。 (mod n)运算将所有的整数(无论小于n还是大于n)，都映射到{0,1,…,n-1}组成的集合。 模算术的性质 有整数a，b，c，n(n ≠0)： 如果a≡b(mod n)， b≡c(mod n) 那么a≡c(mod n) 如果a≡b(mod n)， c≡d(mod n) 那么a+c≡b+d， a-c≡b-d， ac≡bd (mod n) 模算术的性质 对于某个固定模m的同余式可以象普通的等式那样相加相减和相乘 （可交换的、可结合的、可分配的）而且，简化运算每个中间结果的模n运算，其作用与先进行全部运算，然后再简化模n运算是一样的。 (1)[a(mod m)±b(mod m)] mod m =(a±b)(mod m) (2)[a(mod m)?b(mod m)] mod m =a ? b(mod m) (3)[(a ?b)(mod m)]+[(a?c)(mod m)] mod m =(a ? (b+c))(mod m) 例1 152 mod 12 =(3*3) mod 12=9 例2 通过同余式演算证明560－1是56的倍数，223－1是47的倍数。 解： 注意53=125≡13(mod56) 于是有56≡169≡1(mod56) 对同余式的两边同时升到10次幂，即有56∣560-1。 注意26=64≡-30(mod47), 于是 223=(26)3·25=(26 · 26)26 · 25 ≡900· (-30) ·(32) mod(47) ≡(7)(-30) ·(32) (mod47) ≡(-30) ·(224) (mod47) ≡(-30) ·(36) (mod47) ≡(-1080) (mod47) ≡1(mod47) 于是有 47∣223-1 求117 (mod13)，21234 mod 789 112 =121 ≡4 (mod13)， 114 ≡ 42 ≡3 (mod13)， 117 ≡ 11?4 ? 3 ≡ 2 (mod13) 除法 设整数a，b，c，n(n ≠0)，且gcd(a,n)=1。 如果ab≡ac (mod n)，那么b≡c (mod n) 证明：∵ gcd(a,n)=1，∴有x和y，使ax+ny=1 两边同乘以(b-c): (b-c)(ax+ny)=b-c 即:(ab-ac)x+n(b-c)y=b-c ……① ∵ ab≡ac (mod n), 即ab=ac+k1n,∴ab-ac 是n的倍数 同时，n(b-c)y显然也是n的倍数 所以，:(ab-ac)x+n(b-c)y也是n的倍数，假设是k2倍 则①式变为：b-c= k2n 即b≡c (mod n) 欧几里得算法 欧几里得（Euclid）算法是数论中的一个基本技术，是求两个正整数的最大公因子的简化过程。而推广的Eucl