现代公开钥匙系统

4-1-1 公开钥匙系统架构

         (Public-key Cryptosystem)

·         1976 年 Diffie-Hellman 暗门函数观念

o        E：加密算法、D：解密算法、P：明文

1.    D(E(P)) = P

2.    由 E 很难推演出 D

3.    E 不会被选定明文攻击法破解

·         1978 年 Rivest 、Shamir 与 Adleman (RSA) 提出公开钥匙架构

o        每一使用者都有两把钥匙，一把加密，另一把则解密。

o        两把钥匙：

§         公开钥匙 (Public Key)

§         私有钥匙 (Private Key)

o        通讯双方至少持有对方的一把钥匙。

o        相对应的加密或解密算法。 

·         运作程序：

o        加密程序：C = E_KR(M)

o        解密程序：M = D_KU(C) = D_KU(E_KR(M)) = M

4-2 公钥系统之应用

·   加密/解密功能

·   数字签章功能

·   钥匙交换

·         Alice 与 Bob 运作

o        Alice：{K_Ua, K_Ra}

o        Bob ：{K_Ub, K_Rb}

·         隐密性加密：

·         数位签章：

·         数字签章附加隐密性：

4-3 公钥系统之算法

·         『数论』(Number Theory) 推导出来

·   RSA 算法 (本章介绍)

·   椭圆曲线密码学 (Elliptic Curve Cryptographic, ECC) (本书未介绍)

·   Diffie-Hellman 算法 (本章介绍)

·   数字签章标准 (Digital Signature Standard, DSS) (第七章介绍)

·   ElGamal 算法 (本书未介绍)

4-4 数论与密码学

·   质数与互质数

·   同余算术

o      同余加法

o      同余乘法

o      同余指数

·   相关定理

o      Fermat 定理

o      Euler's Totient 函数

o      Euler 定理

4-4-1 质数与互质数

• (A) 质数 (Prime)：只能被 1 或自己整除的数。
• • 1 ~ 100 之间的质数：

2, 3, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

• • 任意数 a > 1，可被分解成多个质数的乘积：

 a = p₁^αp1× p₂^αp2 × p₃^αp3× p₄^αp4…× p_i^αpi =

• • 譬如：

3600 = 2⁴ × 3² × 5²，则 α₂ =4、α₃ =2、α₅ =2。

• (B) 互质：gcd(a, b) 表示 a 和 b 的最大公因素。
• • 如果 gcd(a, b) =1， 表示 a 与 b 互质。
  • 譬如：gcd(18, 300) = 6，计算如下：

300 =  2² × 3¹ × 5²；

18 =  2¹ × 3² × 5⁰，则

gcd(300, 18) = 2¹ × 3¹ × 5⁰ = 6

4-5 同余算术 (Modular Arithmetic)

·   取余数的运算

·   modulo 2 (二进制运算)、modulo 8、modulo 16

·   譬如：

 16 mod 10 ≡ 6

4-5-1 同余加法 (Modular Addition)

·    6+7≡3 或 13≡ 3 mod 10

·   0 ~ 9 之间的同余加法 (Modulo 10)

+	0	1	2	3	4	5	6	7	8	9
0	0	1	2	3	4	5	6	7	8	9
1	1	2	3	4	5	6	7	8	9	0
2	2	3	4	5	6	7	8	9	0	1
3	3	4	5	6	7	8	9	0	1	2
4	4	5	6	7	8	9	0	1	2	3
5	5	6	7	8	9	0	1	2	3	4
6	6	7	8	9	0	1	2	3	4	5
7	7	8	9	0	1	2	3	4	5	6
8	8	9	0	1	2	3	4	5	6	7
9	9	0	1	2	3	4	5	6	7	8

• 反向暗门
• •  K_E + K_D = 10

加密钥匙 (KE)：	1	2	3	4	5	6	7	8	9
解密钥匙 (KD)：	9	8	7	6	5	4	3	2	1

·   (K_D + K_E) mod 10 ≡0 </P class=MsoNormal style=SPAN>

·   y + y^-1 mod n ≡0

4-5-2 同余乘法 (Modular Multiplication)

• 0 ~ 9 之间的同余乘法 (modulo 10)

×	0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	0	0	0	0	0	0
1	0	1	2	3	4	5	6	7	8	9
2	0	2	4	6	8	0	2	4	6	8
3	0	3	6	9	2	5	8	1	4	7
4	0	4	8	2	6	0	4	8	2	6
5	0	5	0	5	0	5	0	5	0	5
6	0	6	2	8	4	0	6	2	8	4
7	0	7	4	1	8	5	2	9	6	3
8	0	8	6	4	2	0	8	6	4	2
9	0	9	8	7	6	5	4	3	2	1

• 适合的反向暗门：{1, 3, 7, 9}
• 加密与解密关系：

加密钥匙 (KE)：	1	3	7	9
解密钥匙 (KD)：	1	7	3	9

• 范例：
• • 参数：K_E = 3, K_D = 7, P = 4
  • 加密：C = K_E * 4 = 3* 4 = 2
  • 解密：P = K_D * 2 = 7 *2 = 4
• K_E 与 K_D 互为反函数 (Y 与 Y^-1)
• • y × y^-1 mod n ≡ 1
  • 范例：
  • • 1 × 1 mod 10 ≡ 1

3 × 7 mod 10 ≡ 1

7 × 3 mod 10 ≡ 1

9 × 9 mod 10 ≡ 1

4-5-3 同余指数 (Modular Exponentation)

• 0 ~ 9 之间 mod 10 的运算结果

xy	0	1	2	3	4	5	6	7	8	9
0		0	0	0	0	0	0	0	0	0
1	1	1	1	1	1	1	1	1	1	1
2	1	2	4	8	6	2	4	8	6	2
3	1	3	9	7	1	3	9	7	1	3
4	1	4	6	4	6	4	6	4	6	4
5	1	5	5	5	5	5	5	5	5	5
6	1	6	6	6	6	6	6	6	6	6
7	1	7	9	3	1	7	9	3	1	7
8	1	8	4	2	6	8	4	2	6	8
9	1	9	1	9	1	9	1	9	1	9

• 较适合的反向暗门为  {1, 3, 7, 9}
• 范例：
• • P =8, K_E = 3, K_D = 7
  • 加密：密文 C = P^Ke = 8³ ≡ 2 mod 10；则密文为 2。
  • 解密：明文 P = C^Kd = 2⁷ ≡ 8 mod 10；则明文为 8。
• 加密与解密关系：

加密钥匙 (KE)：	1	3	7	9
解密钥匙 (KD)：	1	7	3	9

• 反向暗门关系为：
• • y × y^-1 mod n ≡ 1

4-6 数论相关定理

·   Fermat 定理

·   Euler's Totient 函数

·   Euler 定理

4-6-1 Femat 定理

·   定义：若 p 为质数，且 a 是无法让 p 整除的正整数，则：

o      a^p-1 ≡ 1 mod p

·   譬如： a = 7,  p=19  则  7^19-1 ≡ 1 mod 19

o      7² = 49 ≡ 11 mod 19

7⁴ = 7² × 7² ≡ 11 × 11 = 121 ≡ 7 mod 19

7⁸ = 7⁴ × 7⁴ ≡ 7 × 7 = 49 ≡ 11 mod 19

7¹⁶ = 7⁸ × 7⁸ ≡ 11 × 11 = 121 ≡ 7 mod 19

a^p-1 =7¹⁸ = 7¹⁶ × 7² ≡ 7 × 11 = 77 ≡ 1 mod 19 得证之。

·   Fermat 定理变形：

o      a (a^p-1 )≡ a( 1 mod p)

a^p ≡ a mod p

4-6-2 Euler's Totient 函数

·   ψ(n) 是小于 n 但与 n 成为互质之正整数的数目，譬如ψ(10) = 4，则表示小于 10 且与 10 为互质的数字共计有 4 个。

• 30 以前数字的ψ(n)

n	ψ(n)	n	ψ(n)	n	ψ(n)
1	1	11	10	21	12
2	1	12	4	22	10
3	2	13	12	23	22
4	2	14	6	24	8
5	4	15	8	25	20
6	2	16	8	26	12
7	6	17	16	27	18
8	4	18	6	28	12
9	6	19	18	29	28
10	4	20	8	30	8

·   如果 p 为质数的话，则：ψ(p) = p-1

·   譬如：p=3，则ψ(3) = 3-1=2；p=19，则 ψ(19) = 18

·   假设有两个质数 p 与 q，而 n = pq，则：

o      ψ(n) =ψ(pq) =ψ(p) × ψ(q) = (p-1) × (q-1)

o      譬如，p=3、q=7、然而 n = 21，则：

ψ(21) =ψ(3) × ψ(7) = 2 × 6 = 12 = (3-1) × (7-1)

4-6-3 Euler 定理

·   定义：如果 a 与 n 互质（gcd(a, n) = 1）的话，则：

o      a^ψ(n) ≡ 1 mod n

·   意思表示：a 与 n 相互之间无法整除的话（互质），a^ψ(n) 除以 n，所得到的余数为 1。譬如，a = 3、n = 10，则ψ(n) =ψ(10) =4（由图 4-6 得知），推演如下：

o      a^ψ(n) = 3⁴ = 81 ≡ 1 mod 10 ≡ 1 mod n

·   Euler 定理的变形：

o      a × (a^ψ(n) )≡ a × (1 mod n)

o      a^ψ(n)+1 ≡ a mod n

4-7 RSA 算法推演

     (RSA Algorithm)

·   定义：

o      明文：M

o      密文：C

o      加密：C ≡ M^e mod n

o      解密：M ≡ C^d mod n ≡(M^e)^d mod n ≡ M^ed mod n

o      公开钥匙：K_U = {e, n}

o      私有钥匙：K_D = {d, n}

o      寻找出适合的 n、e  与  d

4-7-1 推论  M ≡ M^ed mod n

·   必须合乎下列条件：

1. 必须找出 e、d 与 n 的值，对所有 M < n，都能满足 M^ed ≡ M mod n。

2. 对任何 M < n 而言，计算 M^e 与 C^d 都必须非常容易。

3. 如果给定 e 与 n，要计算出 d 是非常困难的；反之亦然。

·   由 Euler 定理：

o      m^ψ(n)+1 ≡ m mod n 

o      ψ(n)=(p-1)(q-1) 其中 n = pq 则：

o      m^ψ(n)+1 = m^(p-1)(q-1)+1 ≡ m mod n

·   如ii-font-family: 果：m 与 n 互质的话（gcd(m, n) = 1）则：

o      gcd(m, n) =1 表示 m 与 n 之间无法整除

o      但 n = pq，如果 m/n = m/pq  不可以整除的话，则 m/p 与 m/q 是否可以或无法整除。

o      假设两个条件：

§         m = pc，其中 c 为任何整数。

§         gcd(m, p)≠1 与 gcd(m, q) =1。

·   其中 gcd(m, q) =1，表示 m 与 q 之间是互质的关系：

o      依照 Euler 定理：a^ψ(n) ≡ 1 mod n，则：

o      m^ψ(q) ≡ 1 mod q

o      利用同余运算规则：

[m^ψ(q)]^ψ(p) ≡ 1 mod q

m^ψ(p)×ψ(q) ≡ 1 mod q

m^(p-1)×(q-1) ≡ 1 mod q；又ψ(n) = (p-1)×(q-1) 则：

o      m^ψ(n) ≡ 1 mod q

o      m^ψ(n) = 1 + kq

o      如果等号双边各乘以 m，其中 m = cp 与 n = pq，则：

m^ψ(n)+1 = m + kcpq = m + kcn

相当于：m 除以 n，而得到的商是 kc、余数是 m，因此，可改写成：

m^ψ(n)+1 ≡ m mod n

o      再利用：a^ψ(n) ≡ 1 mod n 推导出：

[m^ψ(n)]^k ≡ 1 mod n

m^kψ(n) ≡ 1 mod n

m^kψ(n)+1 = m^{k(p-1)(q-1)+1} ≡ m mod n

·   又 n = pq，且 p 与 q 皆为质数

                  M^kψ(n)+1 ≡ M mod n

给定：  

          ed = kψ(n) +1

则：   

           M^ed ≡ M mod n  ；得到推演结果

于是：

                  ed ≡ 1 mod ψ(n)

                   d ≡ e^-1 mod ψ(n)

4-8-1 推论结果归类 ·   RSA 算法相关参数 o       p 与 q 两质数：自行选择的私有值。 o      n=pq：计算而得的公开值。 o      选择 e，需满足 gcd(ψ(n), e)=1；1 < e <ψ(n)：自选公开值。（一般都固定值 3 或其它数值） o      d ≡ e-1 mod ψ(n)：计算出私有值。 o      公开钥匙：KU = {e, n} o      私有钥匙：KD = {d, n} 4-8-2 验证推演结果 ·   假设参数： 1. 选定两个质数，p = 7、q = 17。 2. 计算 n = pq = 7 × 17 = 119。 3.  计算ψ(n) = (p-1) × (q-1) = 6 × 16 = 96。 4.  选定 e，但必须满足 gcd(e, ψ(n)) =1，则选择 e =5，因与 96 互质。 5. 选定 d，但必须满足 de ≡1 mod 96，且 d < 96。本范例选择 d = 77，因为 77×5 = 385 ≡1 mod 96（385 除以 96，得到余数为 1）。 ·   经过上述推演得到： o      公开钥匙：KU = {e, n} = {5, 119} o      私有钥匙：KR = {d, n} = {77, 119} 验证结果：假设明文  M = 19  加密编码：C ≡ Me mod n ≡ 195 mod 119 ≡ 66 mod 119，则密文为 66。 演算过程如下： 192 = 361 ≡ 4 mod 119 194 ≡ 4 × 4 = 16 ≡ 16 mod 119 195 = 194 × 191 ≡16 × 19 = 304 ≡ 66 mod 119 解密编码：M ≡ Cd mod n ≡ 6677 mod 119 ≡ 19 mod 119，则明文为 19。 演算过程如下： 662 = 72 mod 119 664 = 72 × 72 = 5184 = 67 mod 119 668 = 67 × 67 = 4489 = 86 mod 119 6616 = 86 × 86 = 7396 = 18 mod 119 6632 = 18 × 18 = 324 = 86 mod 119 6664 = 86 × 86 = 7396 = 18 mod 119 6677 = 6664 × 668 × 664 × 66 = 6845256 = 19 mod 119

4-9-1 选择 p 与 q 条件

·   n = p * q

·   选择条件：

o      p 与 q 的长度不要相差太多，两者大小都应介于 10⁷⁵ 到 10¹⁰⁰ 之间。

o      (p-1) 与 (q-1) 都应该含有一个很大的质因子。

o      gcd(p-1, g-1) 的值，应该很小。

4-9-2 选择 e 与 d 的条件

·   {e, n} 为公开钥匙

·   {d, n} 为私有钥匙

·   选择因素： ed ≡ 1 modψ(n)

·   选择方式：

o      先选择 p 与 q，之后再选择 e，但选择 e 的条件是必须满足与 (p-1)(q-1) 的质数关系。

o      先选择 e，之后再选择 p 与 q，但选择条件是必须满足 e 与 (p-1)(q-1) 之间是质数的关系。

·   一般采用先选 e，并固定为 3。

4-10-1 攻击 RSA 算法的方法

·   暴力攻击法

·   数学攻击法：因子分解法

4-10-2 因子分解攻击法

·         有三种攻击法：

o        将 n 分解成两个质因子 p 与 q：如此便可以计算出ψ(n) = (p-1)(q-1)，并且一般 e 都采用某一固定值（如 e =3），接着可以计算出 d ≡ e^-1 mod ψ(n)。

o        由 n 计算出 ψ(n)：不必先算出 p 和 q，可以寻找出 d ≡ e^-1 mod ψ(n)。

o        直接找出 d：不必先计算出 ψ(n)。

4-11-1 Diffie-Hellman 钥匙交换的运作程序

·   n 与 g 为公开值

·   双方各选一个较大的数值 x 与 y

·   计算出『秘密钥匙』：g^xy mod n

4-7-2 验证 Diffie-Hellman 算法

·   Alice 选定：n = 47,  g =3,  x=8,  计算出：

o      g^x mod n = 3⁸ mod 47 = 28 mod 47

o      讯息 (1) = {47, 3, 28}

·   Bob 选定：y =10 ,  计算出：

o      g^y mod n = 3¹⁰ mod 47 = 17 mod 47

o      讯息 (2) = {17}

·   Alice 计算会议钥匙：

o      (g^x mod n)^y = g^xy mod n = 28¹⁰ mod 47 = 4 mod 47

·   Bob 计算会议钥匙：

o      (g^y mod n)^x = g^xy mod n = 17⁸ mod 47 = 4 mod 47

·   会议钥匙 k= 4

4-12-1 中间人攻击

       (Man-in-the-middle Attack)

·   Trudy 为中间人

4-12-2 防御中间人攻击

·   公开 Diffie-Hellman 参数

·   认证的 Diffie-Hellman 参数

4-13 公开钥匙密码标准

       (Public-key Cryptography Standard, PCKS)

·   RSA Data Security Inc.

·   网站：http://www.rsasecurity.com/rsalabs/pkcs/

·   PKCS #1：RSA 加密标准（RSA Cryptography Standard）

·   PKCS #3：Diffie-Hellman 钥匙交换标准（Diffie-Hellman Key-Agreement Standard）

·   PKCS #5：密码基础的加密标准（Password-Based Cryptography Standard）

·   PKCS #6：凭证延伸之语意标准（Extended-Certificate Syntax Standard）

·   PKCS #7：讯息加密之语意标准（Cryptographic Message Syntax Standard，RFC 2315）

·   PKCS #8：私有钥匙讯息之语意标准（Private-Key Information Syntax Standard）

·   PKCS #9：选择性属性格式（Selected Attribute Type）

·   PKCS #10：凭证索取之语意标准（Certification Request Syntax Standard）

·   PKCS #11：加密符记接口标准（Cryptographic Token Interface Standard）

·   PKCS #12：个人讯息交换标准（Personal Information Exchange Standard）

·   PKCS #13：椭圆曲线密码标准（Elliptic Curve Cryptographic Standard）

·   PKCS #15：密码符记讯息格式标准（Cryptographic Token Information Format Standard）

4-14 公开钥匙分配

·       公开声明 (Public Announcement)

·       公用目录 (Public Available Directory)

·       公开钥匙授权 (Public-key Authority)

·       公开钥匙凭证 (Public-key Certificate)

4-14-1 公开声明

·   直接将个人公开钥匙公布于：

o      网站

o      邮递清单

o      新闻论坛，、、、等等

4-14-2 公用目录

·   钥匙托管 (Key Escrow)

·   钥匙托管中心 (KEC)

4-14-3 公开钥匙授权

·   授权中心 (Authority Center)

·   实时索取钥匙

14-4-4 公开钥匙凭证

·   凭证 (Certificate)

·   凭证授权 (Certificate Authority, CA)

·   客户保存凭证

 

FONT-SIZE: 13.5pt; LINE-HEIGHT: 200%; LETTER-SPACING: 0.4pt; mso-ascii-font-family: SPAN style=SPAN lang=EN-US