现代密码学第讲：公钥密码学2(必修).pdfVIP

《现代密码学》第七章 公钥密码（二） 1 上节内容回顾 公钥密码体制的提出及分类 公钥密码体制的基本概念 单向陷门函数的概念 设计公钥加密算法--背包密码体制 本节主要内容 RSA算法及其分析 ElGmal算法 椭圆曲线密码体制 其它公钥密码算法 3 RSA算法 RSA算法是1978年由R.Rivest, A.Shamir 和L.Adleman提出的一种用数论构造的、也 是迄今为止理论上最为成熟完善的公钥密码 体制，该体制已得到广泛的应用。 它既可用于加密、又可用于数字签字。 RSA算法的安全性基于数论中大整数分 解的困难性。 R L Rivest, A Shamir, L Adleman, On Digital Signatures and Public Key Cryptosystems, Communications of the ACM, vol 21 no 2, pp120-126, Feb 1978 4 RSA算法 1. 密钥的产生 ① 选两个安全的大素数p和q 。 ② 计算n=p ×q，φ(n)=(p-1)(q-1),其中φ(n)是n 的欧拉函数值。 ③ 选一整数e，满足1e φ(n)，且 gcd( φ(n),e)=1。 ④ 计算d，满足d·e≡1 mod φ(n),即d是e在模φ(n) 下的乘法逆元，因e与φ(n)互素，由模运算可知， 它的乘法逆元一定存在。 ⑤ 以{e,n}为公开钥,{d,n}为秘密钥。 5 RSA算法 2. 加密 加密时首先将明文比特串分组，使得每个分 组对应的十进制数小于n，即分组长度小于 log2n。然后对每个明文分组m，作加密运算： c≡me mod n 6 RSA算法 3. 解密 对密文分组的解密运算为：m≡cd mod n 证明RSA算法中解密过程的正确性. 证明： m与n互素，由加密过程知c≡me mod n，所以 cd mod n≡med mod n≡mk φ(n)+1 mod n 则由Euler定理得 mφ(n) ≡1 mod n,mk φ(n) ≡1 mod n,mk φ(n)+1 ≡m mod n 即cd mod n≡m。 7 RSA算法 例： 选p=7，q=17. 求得n=p ×q=119，φ(n)=(p-1)(q-1)=96. 取e=5，满足1e φ(n)，且gcd( φ(n),e)=1， 计算满足d·e=1 mod 96且小于96的d. 因为77 ×5=385=4 ×96+1，所以d为77， 因此公开钥为{5，119}，秘密钥为{77，119}. 设明文m=19，则加密过程为 c≡195 mod 119≡2476099 mod 119≡66; 解密过程为 m ≡ 6677mod 119≡19. 8 RSA算法的安全性 整数分解问题：已知n是两个大素数的乘积，求 n的素分解 RSA的安全性 是基于分解大整数困难的假定 如果RSA的模数n被成功地分解为p ×q，则获 得φ