10.第十讲 公钥加密算法 (续)

第十讲公钥加密算法(续)
•公钥密码(续)
•RSA \ElGamalalgorithms

1. 公钥加密
•公钥加密算法: 用于加密任何消息
•常能用于签名和密钥交换
•eg. RSA,ElGamal
•基于不同有限域的指数运算(galois整数
域、elliptic curves etc)

•其它问题的公钥体制(Error Correcting
Codes)

•大多数都被攻破

2. RSA (Rivest,Shamir,Adleman)
•使用最广泛的公钥加密算法
•Rivest,Shamir&Adleman(RSA) in 1977
•R LRivest, AShamir, LAdleman, "On
Digital Signatures and Public Key
Cryptosystems", Communications of the
ACM,vol21 no 2, pp120-126, Feb 1978
•

3. RSA Setup
•每个用户生成自己的公钥\私钥对:
•选择两个随机大素数(~100 digit), p, q
•计算模数N=p.q
•选择一个随机加密密钥匙e: egcd(e,ø(N))=1

•解下列同余方程,求解密密钥d:
•e.d=1 mod ø(N)and 0<=d<=N
•公开加密密钥: K={e,N}
•保存其解密似钥:
•K
-1
={d,p,q}

4。RSA 参数选择
•需要选择足够大的素数p, q
•通常选择小的加密指数e,且与ø(N)互素
•e对所有用户可以是相同的
•最初建议使用e=3
•现在3太小
•常使用e=2
16
-1 = 65535

•解密指数比较大

5. RSA Usage
•要加密消息M，发送者要得到接收者的
公钥K={e,N}

•计算: C=M
e
mod N, where 0<=M

•为解密C，接收者使用私钥
•K
-1
={d,p,q}

•计算: M=Cdmod N
6. RSA理论•RSA 基于Fermat's Theorem: •if N =pqwhere 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 是特殊选择的•iee.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= M1mod N•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，计算：
688
79
(mod 3337)=1570

5.收到密文1570后，用私钥d＝1019进行解密：
15701019（mod 3337)=688

9。RSA 安全性
•RSA 安全性基于计算ø(N)的困难性•要求分解模N10. RSA的实现问题•需要计算模300 digits (or 1024+ bits) 的乘
法
•计算机不能直接处理这么大的数
•（计算速度很慢）

•需要考虑其它技术，加速RSA的实现

11. RSA –的快速实现
•加密很快，指数小
•解密比较慢，指数较大
•利用中国剩余定理CRT，
•CRT 对RSA解密算法生成两个解密方程（利用M =C
d
mod R）

•即: M
1
= M mod p = (C mod p)

d mod (p-1)

•M2= M mod q = (C mod q)
d mod (q-1)
•解方程M = M1mod p
•M = M2mod q
•具有唯一解（利用CRT）：
•:M = [((M2+q -M1)u mod q] p + M
1

•其中p.u mod q = 1

12。El Gamal公钥加密方案
•Diffie-Hellmankey distribution scheme 的变形
•能够用于安全交换密钥
•published in 1985 byElGamal:
•T.ElGamal, "A Public Key Cryptosystem and a
Signature Scheme Based on Discrete Logarithms",
IEEE Trans. Information Theory,volIT-31(4),
pp469-472, July 1985.

•安全性是基于离散对数
•缺点：增加了消息长度（2倍）
13 密钥建立
•密钥生成：
•选取一个大素数p及本原元a
•接收者Bob有一个密秘钥x
B

•计算yB=axBmod p

•

14. ElGamal加密
•为加密M
•发送者选择随机数k, 0<=k<=p-1
•计算消息密钥K:
•K =y
B
k
mod p

•计算密文对: C = {C1,C2}
•C1=akmod p
•C2= K.M mod p
•发送到接收者
•k需要永久保密

15. ElGamal解密
•首先计算message key K
•K = C1xBmod p =ak.xBmod p
•计算明文:
•M = C2.K-1mod p

16. ElGamalExample
•选择p=97及本原根a=5
•recipient Bob 选择秘密钥x
B=58& 计算并发布公钥yB
=558=44

mod 97

•Alice 要加密M=3to Bob
•首先得到Bob的公开密钥yB=44
•选择随机k=36计算:
K=4436=75 mod 97

•计算密文对:
•C1= 536= 50 mod 97
•C2= 75.3 mod 97 = 31 mod 97
•发送{50,31}to Bob
•Bob 恢复message key K=5058=75 mod 97
•Bob 计算K-1= 22 mod 97
•Bob 恢复明文M = 31.22 = 3 mod 97

17。公钥密码现状
•已知的安全算法是有限域上指数运算
素数域GF(p)上的整数运算
•多项式运算GF(2^n)
•椭圆曲线上的运算(elliptic curves) (harder to
compute so use smaller sizes)

•基于其它困难问题的体制

18. 公钥密码方案的实际应用
•实现速度
•通常用于交换对称算法的加密密钥
•数字签名算法（下节内容）
19 小结
•RSA 算法
•ElGamal算法
•实现问题

Exercises
1.Illustrate the operation of RSA, given the
following parameters:

System modulus n=119 (7x17)
encryption exp e=11
Determine the decryption exponent d, and
hence details the public and private keys
for this user. Then show how a message
M=20would be encrypted anddecrpyted.

•END!