初等数论ppt第三章 简化剩余类、欧拉函数、RSA课件.ppt
第三章(2) 简化剩余类、欧拉函数及其应用、RSA,复习,剩余类及完全剩余系,3 简化剩余系与欧拉函数,4 欧拉定理.费马定理及应用,36,公钥密码体制,37,RSA算法概况,MIT三位年青数学家R.L.Rivest，A.Shamir和L.Adleman等1978, 1979发现了一种用数论构造双钥的方法，称作MIT体制，后来被广泛称之为RSA体制。它既可用于加密、又可用于数字签字。RSA算法的安全性基于数论中大整数分解的困难性。,38,算法描述密钥产生,独立地选取两大素数p和q(各100200位十进制数字)计算 n=pq，其欧拉函数值(n)=(p1)(q1) 随机选一整数e，1e(n)，gcd(n), e)=1在模(n)下，计算e的有逆元d=e -1 mod (n) 以n，e为公钥。秘密钥为d。(p, q不再需要，可以销毁。),加密将明文分组，各组对应的十进制数小于n c=me mod n解密 m=cd mod n,39,解密正确性证明,cd mod n med mod n m1 modj(n) mod n mkj(n)+1 mod ngcd(m,n) =1 mj(n)1 mod n欧拉定理 mkj(n)1 mod n mkj(n)+1m mod n,gcd(m,n) 1m是p的倍数或q的倍数，设m=cp，gcd(m,q)=1, mj(q)1 mod q， mkj(q)1 mod q， mkj(q) j(p)1 mod q mkj(n)1 mod q，,存在一整数r，使mkj(n)1rq两边同乘m=cp, mkj(n)+1m+rcpq=m+rcn,即mkj(n)+1m mod n,40,选p=7，q=17。求n=pq=119，(n)=(p-1)(q-1)=96。取e=5，满足1e(n)，且gcd(n),e)=1。确定满足de=1 mod 96且小于96的d，因为775=385=496+1，所以d为77公开钥为5，119，秘密钥为77。设明文m=19，则由加密过程得密文为c195 mod 1192476099 mod 11966解密为6677mod 11919,例题,41,用RSA算法加密与解密的过程：例：明文=“RSA ALGORITHM”(1) 明文用数字表示 空白=00， A=01, B=02, , Z=26 (两位十进制数表示)1819 0100 0112 0715 1809 2008 1300(2) 利用加密变换公式 C=me mod r, 即C = 18191223 mod 2867=2756,2756 2001 0542 0669 2347 0408 1815,=47, q=61, (n)=2760时，d=167,n=2867,e=1223,42,RSA算法实现,如何判定一个给定的大整数是素数？已知d如何计算e，使e * d1 mod(n)？如何计算C Me mod n或MCd mod n？,43,Miller-Rabin 素性检验算法,44,求模逆元的扩展欧几里德算法,45,求模幂的模重复平方计算法,求am，其中a，m是正整数： 将m表示为二进制形式bk bk-1b0，m=bk2k+bk-12k-1+b12+b0,46,RSA的快速实现,加密很快，指数小解密比较慢，指数较大利用中国剩余定理CRT，CRT 对RSA解密算法生成两个解密方程（利用M=Cd mod pq）即: M1 = M mod p = (C mod p)d mod (p-1) mod p M2 = M mod q = (C mod q)d mod (q-1) mod q 解方程 M = M1 mod p M = M2 mod q 具有唯一解（利用CRT ）,47,RSA的安全性,RSA的安全性是基于分解大整数的困难性假定如果分解n=pq，则立即获得(n)=(p1)(q1)，从而能够确定e的模(n)乘法逆d由n直接求(n)等价于分解nRSA-129历时8个月被于1996年4月被成功分解，RSA130于1996年4月被成功分解密钥长度应该介于1024bit到2048bit之间,48,49,RSA的安全性,|p-q|要大p-1,q-1都应有大的素因子。en且dn1/4,则d能被容易的确定。,作业6,P60 1,3P64 1,2,
