非对称密钥密码体系

对称密钥密码体系存在的问题：能实现加密，但不能完成密钥分配和数字签名

公钥密码体制

每个用户都有一对选定的密钥（公钥k₁；私钥k₂），公开的密钥后可以像电话号码一样进行注册公布。

主要特点：

• 加密和解密能力分开
• 公钥加密私钥解密：多个用户加密的消息只能由一个用户（用私钥）解读（用于公共网络中实现保密通信）
• 私钥加密公钥解密：只能由一个用户加密消息而使多个用户可以解读（可用于认证条统中对消息进行数字签字——抗抵赖）。
• 无需事先分配密钥

公钥密码应满足的要求

• 接收B产生密钥对在计算上是容易的
• 发送方A用收方的公开钥对消息m加密以产生密文c在计算上是容易的。
• 收方B用自己的秘密钥对密文c解密在计算上是容易的。
• 敌手由密文c和B的公开密钥恢复明文在计算上是不可行的。
• 敌手由密文c和B的公开密钥恢复秘密密钥在计算上是不可行的
• 加解密次序可换，即E_PKB[D_SKB(m)]=D_SKB[E_PKB(m)]，不是对任何算法都做此要求。

以上要求本质就是找出合适的单向陷门函数

陷门单向函数

• 单向函数是求逆困难的函数，而单向陷门函数(Trapdoor one-way function)，是在不知陷门信息下求逆困难的函数，当知道陷门信息后，求逆是易于实现的。
• 陷门单句函数是一族可逆函数fk，满足
  1.Y=f_k(X)易于计算（当k和X已知）
  2.X=f_k^-1(Y)易于计算（当k和Y已知）
  3.X=f_k^-1(Y)计算上不可行（Y已知但k未知）

RSA算法

• MIT三位年青教学家R.L.Rivest，A.Shamir和LAdleman等[1978，1979]发现了一种用数论构造双钥的方法，称作MIT体制，后来被广泛称之为RSA体制。
• 它既可用于加密、又可用于数字签字。
• RSA算法的安全性基于数论中大整数分解的困难性。

算法描述——密钥产生

1. 独立地选取两大素数p和q(各100~200位十进制数字)
2. 计算n=p×q，其欧拉函数值φ(n)=(p-1)(q-1)
3. 随机选一整数e，1≤e<φ(n)，gcd(φ(n),e)=1
4. 在模φ(n)下，计算e的有逆元d=e^-1 mod φ(n)
5. 以n，e为公钥。秘密钥为d（p, q不再需要，可以销毁。）
6. 加密：将明文分组，各组对应的十进制数小于n
   c = m^e mod n
7. 解密： m = c^d mod n

• 例题：
  设 p = 7, q = 17
  可求得 n = p×q = 119, φ(n)=(p-1)(q-1) = 96
  取 e = 5, 满足 1≤e<φ(n)，gcd(φ(n),e)=1
  确定满足d·e = 1 mod 96 且小于96的d，因为 77×5 = 385 = 4×96 + 1, 所以 d为77
  公开密钥为 {5,119} 秘密钥为 {77}
  设明文 m=19，由加密过程得到的密文为 c ≡ 19⁵ mod 119 ≡ 2476099 mod 119 ≡ 66
  解密为 66⁷⁷ mod 119 ≡ 19
• 加密文本：
  p=47, q=61,φ(n)=2760时，d=167
  n=2867 e=1223
  用RSA算法加密与解密的过程：
  例：明文=“RSA ALGORITHM”
  明文用数字表示 空白=00，A=01, B=02,…, Z=26 (两位十进制数表示)
  181901 00 0112 0715 1809 2008 1300
  利用加密变换公式C=m^emod r,
  即C = 18 19 12 23 mod 2867
  =27562756 2001 0542 0669 2347 0408 1815

应用

公钥体制加密

公钥体制加、解密 m=D(c）= D_SKB(E_PKB(m))
安全保障：

• 从公开钥PK_B和密文c要推出明文m或解密钥SK_B在计算上是不可行的；
• 由于任一用户都可用用户B的公开钥PK_B向他发送机密消息，因而密文c不具有认证性。

公钥密码认证体制

• 用户A以自己的秘密钥SK_A对消息m进行A的专用变换D_SKA，A计算密文：c=D_SKA(m)送给用户B，B验证c： m=E _PKA(c）=E _PKA(D _SKA(m))
• 安全性
  由于SK_A是保密的，其他人都不可能伪造密文c，可用A的公开钥解密时得到有意义的消息m。因此可以验证消息m来自A而不是其他人，而实现了对A所发消息的认证。

RSA一般应用过程

• 可以同时实现数字签名和消息认证

公钥保密和认证体制

为了同时提供认证功能和保密性，可使用双重加、解密
加密c=E_PKB[E_SKA[m]]
解密m=D_PKA[D_SKB[c]]

小结

RSA密码算法

cs