4RSA公钥算法 RSA公钥算法是由 Rivest shamir和 Adleman在1978年提出 来的(见 Communitions of the acm. vol2lNo.2.Feb.1978 PP20-126)该算法的数学基础是初等数论中的 Euler(欧拉)定 理,并建立在大整数因子的困难性之上。 欧拉定理 表述1:将Zn表示为Zn其中n=p0:p为素数且相异 若Z=gZn(g,m=1易见Z为p(m阶的乘法群且有 g 9(=l(mod n) o(n=(p-1)(g-7 表述2:若整数g和n互素,则 go(n=l(mod n) 其中φ()为比n小,但与n互素的正整数个数,称为n的欧 拉函数
4 RSA公钥算法 RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出 来的 见Communitions of the ACM. Vol.21.No.2. Feb. 1978, PP.120-126)该算法的数学基础是初等数论中的Euler 欧拉)定 理 并建立在大整数因子的困难性之上 欧拉定理 表述1 将Z/(n 表示为 Zn 其中n=pq; p,q为素数且相异 若Z*n≡{g Zn|(g,n)=1} 易见Z*n为 ϕ (n)阶的乘法群 且有 g ϕ (n)≡1(mod n) 而 ϕ (n)=(p-1)(q-1). 表述2 若整数g和n互素 则 g ϕ (n)≡1(mod n) 其中ϕ (n)为比n小 但与n互素的正整数个数, 称为n的欧 拉函数
RSA密码体制描述如下 首先,明文空间P=密文空间C=Zn A密钥的生成 选择pq,pq为互异素数,计算np°q,g(n)=(p-1)q-1选择整 数e使(qp(n)e)=1,lep(n).计算d,使d=e(modg(n),公钥 Pk={en},私钥Sk={dpq} 注意,当0<M<m时Mp=(modn)自然有: MFp=M(modn,而ed=1(modp(n)易见(My≡M(mdn) B加密(用en 明文:M<n密文:C= M(mod n C解密(用d,pq) 密文:C明文:M=C(modn) 注:1’,加密和解密是一对逆运算。 2’,对于0<M<m时,若(Mn)≠1,则M为p或q的整数倍,假设M=cp,由(cpq=1有 Mo(q)= I(mod g M9(q)9(p)= l(mod g)
RSA密码体制描述如下 首先 明文空间P 密文空间C=Zn A.密钥的生成 选择p,q p,q为互异素数 计算n=p*q, ϕ (n)=(p-1)(q-1), 选择整 数e使(ϕ (n),e)=1,1<e<ϕ (n)),计算d,使d=e-1(mod ϕ (n))),公钥 Pk={e,n};私钥Sk={d,p,q} 注意 当0<M<n时,Mϕ (n) =1(mod n)自然有 MKϕ (n)+1≡M(mod n), 而ed ≡ 1 (mod ϕ (n)),易见(Me)d ≡ M(mod n) B.加密 (用e,n) 明文 M<n 密文 C=Me(mod n). C.解密 (用d,p,q) 密文 C 明文 M=Cd mod n) 注 1*, 加密和解密是一对逆运算 2*, 对于0<M<n时 若(M,n) 1 则M为p或q的整数倍 假设M=cp 由(cp,q)=1 有 Mϕ (q) ≡ 1(mod q) M ϕ (q) ϕ (p) ≡ 1(mod q)
有Mq=1+kq对其两边同乘M=cp有 有M+= M+kcpq=M+kcn于是 有M(q+= M(mod n) 例子:若Bob选择了p=101和q=11,那么,n11413 0(n)=100×112=1120211200=26×52×7,一个 正整数e能用作加密指数,当且仅当e不能被2,5,7所 整除(事实上,Bob不会分解φ(m,而是用辗转相除 法(欧式算法)来求得e,使(e,φ(n)=1)。假设Bob选 择了e=3533,那么用辗转相除法将求得: d=e-l=6597mod11200于是Bob的解密密钥d=6597 Bob在一个目录中公开n=11413和e=3533现假设Aice想发 送明文9726给Bob,她计算 972633(mod11413)=5761
有Mϕ (q) = 1+kq 对其两边同乘M=cp有 有Mϕ (q) 1=M+kcpq=M+kcn于是 有Mϕ (q) 1 ≡ M(mod n) 例子 若Bob选择了p=101和q 113 那么 n=11413, ϕ (n)=100 112 11200 然而11200 26 52 7 一个 正整数e能用作加密指数 当且仅当e不能被2 5 7所 整除 事实上 Bob不会分解 (n) 而是用辗转相除 法 欧式算法 来求得e 使 e, (n)=1) 假设Bob选 择了e=3533 那么用辗转相除法将求得 d=e -1 ≡ 6597(mod 11200), 于是Bob的解密密钥d=6597. Bob在一个目录中公开n=11413和e=3533, 现假设Alice想发 送明文9726给Bob 她计算 97263533(mod 11413)=5761
且在一个信道上发送密文5761。当Bob接收到密文5761时, 他用他的秘密解密指数(私钥)d=6597进行解密: 576167(mod11413)9726 注:RSA的安全性是基于加密函数e(xx(modn是一个 单向函数,所以对的人来说求逆计算不可行。而Bob能 解密的陷门是分解n=pq,知φ(n)=(p-l)q-1)。从而用欧 氏算法解出解密私钥d
且在一个信道上发送密文5761 当Bob接收到密文5761时 他用他的秘密解密指数 私钥 d 6597进行解密 57616597 mod 11413)=9726 注 RSA的安全性是基于加密函数ek(x)=xe(mod n)是一个 单向函数 所以对的人来说求逆计算不可行 而Bob能 解密的陷门是分解n=pq 知ϕ (n)=(p-1)(q-1) 从而用欧 氏算法解出解密私钥d
RSA密码体制的实现 实现的步骤如下:Bob为实现者 (1)Bob寻找出两个大素数p和q (2)Bob计算出n=p和(n)(p-1)(q-1) (3)Bob选择一个随机数e(0<e<g(m),满足(e,@(n)=1 (4Bob使用辗转相除法计算d=e-(modφ(n) (5Bob在目录中公开n和e作为她的公开钥。 密码分析者攻击RSA体制的关键点在于如何分解n。若分 解成功使npq,则可以算出中(n)=(p-1)q-1),然后由公 开的e,解出秘密的d
RSA密码体制的实现 实现的步骤如下 Bob为实现者 (1)Bob寻找出两个大素数p和q (2)Bob计算出n=pq和ϕ (n)=(p-1)(q-1). (3)Bob选择一个随机数e(0<e< ϕ (n)) 满足 e ϕ (n) 1 (4)Bob使用辗转相除法计算d=e-1(mod ϕ (n)) (5)Bob在目录中公开n和e作为她的公开钥 密码分析者攻击RSA体制的关键点在于如何分解n 若分 解成功使n=pq 则可以算出 (n) p-1)(q-1) 然后由公 开的e 解出秘密的d