4。RSA参数选择 需要选择足够大的素数p,q ■通常选择小的加密指数e,且与o(N)互素 e对所有用户可以是相同的 最初建议使用e=3 ■现在3太小 常使用e=216-1=65535 解密指数比较大
4。RSA 参数选择 ◼ 需要选择足够大的素数 p, q ◼ 通常选择小的加密指数e,且与ø(N) 互素 ◼ e 对所有用户可以是相同的 ◼ 最初建议使用e=3 ◼ 现在3太小 ◼ 常使用 e=2 16-1 = 65535 ◼ 解密指数比较大
5. RSA Usage ■要加密消息M,发送者要得到接收者的 公钥K={e,N} ■计算:C=Me,modN, Where0<=M<N 为解密C,接收者使用私钥 K-d, p, gl 计算:M= Cd mod n
5. RSA Usage ◼ 要加密消息 M， 发送者要得到接收者的 公钥Kr={er ,Nr } ◼ 计算: C=Me r mod Nr , where 0<=M<N ◼ 为解密 C， 接收者使用私钥 ◼ K-1 r={d,p,q} ◼ 计算: M=Cd mod Nr
6.RSA理论 RSA基于 Fermat' s Theorem if N= pq where p, g are primes, then Xo(N)=1 mod N for all x not divisible by p or g, ie gcd(X, 0(N))=1 where o(=(p-1(q-1) ■但在RSA中,e&d是特殊选择的 ie e d=1 mod o(N)ed=1+RO(N) hence have M=Cd= med= m1+RO(N) M. MO(ND)R=M1 (1)R=M mod N
6. RSA理论 ◼ RSA 基于Fermat's Theorem: ◼ if N = pq where p, q are primes, then: Xø(N) = 1 mod N ◼ for all x not divisible by p or q, ie gcd(x,ø(N))=1 ◼ where ø(N)=(p-1)(q-1) ◼ 但在 RSA 中，e & d 是特殊选择的 ◼ ie e.d=1 mod ø(N) 或e.d=1+Rø(N) ◼ hence have: M = Cd = Me.d = M1+Rø(N) = M1 .(Mø(N)) R = M1 .(1)R = M1 mod N ◼
8。RSA举例 1.选素数p=47和q=71,得n=3337 q(n)=46×70=3220 2.选择e=79,求得私钥d=e1≡1019mod 3220)。 3.公开n=3337和e=79 4.现要发送明文688,计算 6887(mod3337)=1570 5收到密文1570后,用私钥d=1019进行解密: 15701019(mod3337)=688
8。RSA举例 例子： 1. 选素数p=47和q＝71，得n=3337, (n)=46×70＝3220； 2. 选择e=79，求得私钥d=e -1 1019(mod 3220）。 3. 公开n=3337和e=79. 4. 现要发送明文688，计算： 68879(mod 3337)=1570 5.收到密文1570后，用私钥d＝1019进行解密： 15701019（mod 3337)=688