RSA公钥密码体制 2021/2/21 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 11 RSA公钥密码体制
RSA公钥算法 ■RSA公钥算法是由R. Rivest,A. Shamir和 L. Adleman在1977年提出来的 ■该算法的数学基础是初等数论中的欧拉 ( Euler)定理并建立在大整数因子分解的困 难性之上的 2021/22 计算机算法设计与分析 12
2021/2/21 计算机算法设计与分析 12 RSA公钥算法 ◼ RSA公钥算法是由R. Rivest, A. Shamir和 L. Adleman在1977年提出来的。 ◼ 该算法的数学基础是初等数论中的欧拉 (Euler)定理并建立在大整数因子分解的困 难性之上的
欧拉定理 ■若整数a和m互素,贝 ap(n)=1(mod n) 其中q(n)为比n小但与n互素的正整数个数 称为n的欧拉函数。 ■比如:q(10)=|{9,7,3,1} q(15)=1{14,13,11,8,7,4,2,1}=8。 ■计算o(n)很困难。但可以证明,若n=p*q (p、q均为素数),φ(n)=(p-1)*(q-1)。 2021/221 计算机算法设计与分析 13
2021/2/21 计算机算法设计与分析 13 欧拉定理 ◼ 若整数a和m互素，则 a (n) ≡ 1 (mod n) ◼ 其中(n)为比n小但与n互素的正整数个数, 称为n的欧拉函数。 ◼ 比如：(10) = |{9，7，3，1}| = 4， (15)=|{14, 13, 11, 8, 7, 4, 2, 1}| = 8。 ◼ 计算(n)很困难。但可以证明，若n = p*q (p、q均为素数)，(n)=(p – 1)*(q – 1)
用欧拉函数构造单向陷门函数 ■选取大整数n和一个与q(n)互质的整数e,将n和 e公开。若要对明文m加密,则令 c=me(mod n) ■显然,这是一个单向函数 若已知一个整数d满足e*d(modo(n)=1,则 cd=(me)d(mod n)=(med)(mod n) (mp(n)+)(mod n)=(*m o(n)(mod n)=m ■这里,整数d就是陷门 2021/221 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 14 用欧拉函数构造单向陷门函数 ◼ 选取大整数n和一个与(n)互质的整数e，将n和 e公开。 若要对明文m加密，则令 c = me (mod n)。 ◼ 显然，这是一个单向函数。 ◼ 若已知一个整数d满足e*d (mod (n)) = 1，则 c d = (me ) d (mod n) = (med) (mod n) = (m (n)+1) (mod n) = (m*m (n)) (mod n) = m。 ◼ 这里，整数d就是陷门
RSA密码体制描述 A.密钥的生成: 1、选择两个素数p、q,计算n=p*q和 q(n)=(p-1)*(q-1) ■2、选取整数b,使其满足gcd(b,(m)=1, 1<b<g(n), 3、计算a,满足a*b≡1modq(n) 4、将n和b作为加密秘钥公开,将p、q和 a作为解密秘钥保密 2021/22 计算机算法设计与分析 15
2021/2/21 计算机算法设计与分析 15 RSA密码体制描述 ◼ A. 密钥的生成： ◼ 1、选择两个素数p、q，计算n = p*q和 (n) = (p –1)*(q – 1)。 ◼ 2、选取整数b，使其满足gcd(b, (n)) = 1， 1 < b < (n)， ◼ 3、计算a，满足a*b ≡ 1 mod (n) 。 ◼ 4、将n和b作为加密秘钥公开，将p、q和 a作为解密秘钥保密