文章目录

• [XJTU计算机网络安全与管理]——第五讲公钥加密算法
• • 一、数论知识补充
  • • 素数
    • 素因子
    • 互质与最大公约数GCD
    • 费马小定理——记住
    • 欧拉函数——记住
    • 欧拉定理
    • 素性检验
    • 本原根
  • 二、公钥密码学
  • • 公钥密码与传统密钥比较
    • 公钥密码学的引入
    • • 私钥密码学
      • 背景
      • 公钥密码学
    • 公钥密码体制
    • 公钥密码算法的特征
    • 公钥密码学的应用
    • 公钥密码策略的安全性
    • 公钥密码算法基础
  • 三、RSA算法——重点
  • • RSA密钥的建立
    • RSA的使用
    • 举例
  • 四、Diffie-Hellman密钥交换
  • • 算法
    • 举例说明
  • 五、EIgamal 密码体制——基于离散对数
  • 六、椭圆曲线密码体制
  • 参考资料

[XJTU计算机网络安全与管理]——第五讲公钥加密算法

一、数论知识补充

素数

素数是除了1与自身无其他因子的数；它们无法被写为数字的乘积；1一般不再考虑之内

例如：2，3，5，7是素数，4，6，8，9不是

素数是数论研究的中心

200以内的素数有：2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199

素因子

N的分解就是将N写为其他数字的分解：n=a x b x c

分解一个数要比通过将因子相乘得到一个数要困难得多

素分解：因子都是素数

互质与最大公约数GCD

当两个数最大公约数是1时称两个数互素

相反的，我们可以通过比较它们的素因子的最小阶数得到

最大公约数可以用欧几里得算法得到

费马小定理——记住

a^p-1 mod p = 1 ，这里的p为素数且GCD(a,p)=1

3⁶ mod 7 = 1

在公钥加密与素性检验中很有用

欧拉函数——记住

对于模n的算术运算

其完全剩余集为：0…n-1

将完全剩余集中与n互素的元素的个数称为欧拉函数Euler Totient Function ø(n)——记住

例：n=10

完全剩余集为{0,1,2,3,4,5,6,7,8,9}

其中与n互素的为{1,3,7,9}

欧拉函数值为4

欧拉定理

费尔马定理的推广

若gcd(a,n)=1则对于任意的a，n有$a^{\Phi (n)}\mathrm{m}\mathrm{o}\mathrm{d}n=1$

举例

1、a=3;n=10; ø(10)=4;

因此3⁴= 81 = 1 mod 10

2、a=2;n=11; ø(11)=10;

1~10都和11互素，一个素数p的欧拉函数值为p-1，费马小定理是欧拉定理的特殊情况

因此2¹⁰= 1024 = 1 mod 11

素性检验

经常被用来寻找大素数

传统的方式是试除法：该方法通常用于较小的数字

实际应用中通常利用素数的统计学特征进行选择：

测试所有的素数都满足的特性

但有些合数也同样满足

素数大约是每ln n出现，由于可以忽略偶数所以实际上在n中平均下来看大约寻找一个素数需要的运算量是$0.5\ln n$

本原根

欧拉定理我们有：$a^{\Phi (n)}\mathrm{m}\mathrm{o}\mathrm{d}n=1$

考虑$a^m=1(\mathrm{m}\mathrm{o}\mathrm{d}n),\text{GCD}(a,n)=1$

M是一定存在的（因为可以$m=\Phi (n)$）

一旦阶数达到m则出现循环

若$m=\Phi (n)$那么a被称为本原根

若p为素数则连续不断的a的阶生成了模p的群。

二、公钥密码学

公钥密码与传统密钥比较

公钥密码学的引入

私钥密码学

传统的私钥加密使用单一的密钥

发送方与接收方共享密钥

若密钥泄露则通信会出现泄密

是对称的，当事双方地位均等。因此无法避免当接收方伪造消息并声称来源于发送方

背景

对称密钥编码所面临的难题：

密钥分配：通信密钥太多，管理和分发困难。

数字签名和认证。

密码体制上的突破

Diffie & Hellman,“New Direction in Cryptography”,1976。

首次公开提出了“公开密钥密码编码学”的概念。

这是一个与对称密码编码截然不同的方案。

提出公开密钥的理论时，其实用性并没有又得到证明：

当时还未发现满足公开密钥编码理论的算法；

直到1978 年，RSA 算法的提出。

公钥密码学

也许是3000年来密码学发展史中最巨大的进步

使用两个密钥-私钥与公钥

非对称，因此参与者地位不再相当

通过巧妙的利用数论观念实现

是私钥密码学的补充而不是取代

为解决两个关键性问题

1️⃣ 密钥分配（key distribution）-如何在不需要密钥分配中心KDC的前提下安全通信

2️⃣ 数字签名-如何验证消息来源于被声称的发送方

公开提出：Whitfield Diffie & Martin Hellman 1976

其实在60年代中期已在NSA中提出

公钥密码体制

公钥/双密钥/非对称密码学涉及两个密钥

公钥：可被所有人知道，可被用来加密消息与验证签名

私钥：仅被接受者所知，用来解密消息与创建签名。

拿私钥加密就是创建签名

公钥加的密，私钥解开；私钥加的密，公钥解开

该类算法被称为非对称因为：加密消息或验证签名的那一方无法解密消息或创建签名

其主要步骤如下：

1️⃣ 每一用户产生一对密钥，用来加密和解密消息。

2️⃣ 每一用户将其中一个密钥存于公开的寄存器或其他可访问的文件中，该密钥称为公钥，另一密钥是私有的。如图9.1(a)所示，每一用户可以拥有若干其他用户的公钥。

3️⃣ 若Bob要发消息给Alice,则Bob用Alice的公钥对消息加密。

4️⃣ Alice收到消息后，用其私钥对消息解密。由于只有Alice知道其自身的私钥，所以其他的接收者均不能解密出消息。

利用这种方法，通信各方均可访问公钥，而私钥是各通信方在本地产生的，所以不必进行分配。只要用户的私钥受到保护，保持秘密性，那么通信就是安全的。在任何时刻，系统可以改变其私钥，并公布相应的公钥以替代原来的公钥。

在这种方法中，发送方首先用其私钥对消息加密，得到数字签名，然后再用接收方的公钥加密，所得的密文只能被拥有相应私钥的接收方解密，这样可保证消息的保密性，但这种方法的缺点是，在每次通信中要执行四次复杂的公钥算法而不是两次。
$$\begin{gathered} Z=E(P{U}_b,E(P{R}_a,X)) \\ X=D(P{U}_a,D(P{R}_b,Z)) \\ 其中PR为私钥，PU为公钥 \end{gathered}$$

公钥密码算法的特征

公钥密码算法依赖于两个密钥，这里：

如果仅知道算法与加密密钥那么要获取解密密钥在计算上是不可行的

当知道相应的加/解密密钥时进行加解密运算在计算上是比较容易的

相关联的两个密钥都可以被用来加密消息而另一个则被用来解密

公钥密码学的应用

通常被用在三个范畴

1️⃣ 加密消息（提供安全性）

2️⃣ 数字签名（提供鉴别）

3️⃣ 密钥交换（会话密钥）

公钥密码策略的安全性

像私钥密码算法一样，采用暴力破解理论上是可行的。

密钥非常长（512bit）（目前2048~3072bit）

安全性依赖于足够大的加解密与密码分析之间的难度差异

需要非常大的数字

相比于私钥加密要慢

公钥密码算法基础

单向函数：对于一个函数$f(x)$，如果对于其定义域上的任意 x，$f(x)$都容易计算，同时，对于其值域中几乎所有的取值 y ，计算其逆函数$f^{-1}(y)$都是不可行的，则函数$f(x)$被称为单向函数

可以提供单向函数的三大数学难题

大整数分解问题（简称IFP）；

离散对数问题（简称DLP）；

椭圆曲线离散对数问题（简称ECDLP）。

单向陷门函数：对于一个单向函数$f(x)$，如果其逆函数$f^{-1}(y)$在已知某些辅助信息的情况下容易求解得出，则称该单向函数$f(x)$为单向陷门函数。

构造公钥密码系统的关键是如何在求解某个单向函数的逆函数的NP完全问题中设置合理的“陷门”

一些常用的公钥密码算法

基于因子分解问题的Rabin算法；

椭圆曲线公钥算法；

基于有限域中离散对数难题的ElGamal公钥密码算法

基于代数编码系统的McEliece公钥密码算法；

基于*“子集和”难题的Merkle-Hellman Knapsack**公钥密码算法；*

目前被认为安全的Knapsack型公钥密码算法Chor-Rivest

三、RSA算法——重点

Rivest, Shamir & Adleman of MIT in 1977

最为人所知与广泛采用的公钥策略

基于整数有限域中模p的指数运算

指数运算需要O((log n)³) （容易）

使用大整数（1024bits）

安全性来源于大整数的分解困难

分解需要$O(e^{\log n\log \log n})$（困难）

RSA密钥的建立

用户通过如下过程生成密钥对

1️⃣ 选择两个随机的大素数p，q

2️⃣ 计算它们的乘积（系统的模）$n=p\times q$

注意欧拉函数值$\Phi (n)=(p-1)(q-1)$

3️⃣ 随机选取加密密钥e

这里$1<e<\Phi (n)，\text{gcd}(e,\Phi (n))=1$

4️⃣ 解下面的等式获得解密密钥d

$e.d=1\mathrm{m}\mathrm{o}\mathrm{d}\Phi (n)and0\le d\le n$

5️⃣ 公开其公钥： P U = { e ， n } PU=\{e，n\} PU={e，n}；保留私钥： P R = { d ， n } PR=\{d，n\} PR={d，n}

RSA的使用

1️⃣ 加密一条消息M，发送方需要：

获取公钥PU={e,n}

计算C = M^e mod n, where 0≤M<n

2️⃣ 解密C，接收方需要

利用私钥PR={d,n}

计算M = C^d mod n

3️⃣ 必要的时候需要进行分块

举例

1️⃣ $p=17\&q=11$

2️⃣ $n=pq=17\times 11=187$

3️⃣ $\Phi (n)=(p–1)(q-1)=16\times 10=160$

4️⃣ $e:\text{gcd}(e,160)=1;e=7$

5️⃣ $d:d\cdot e=1\mathrm{m}\mathrm{o}\mathrm{d}160andd<160Valueisd=23since23\times 7=161=1\times 160+1$

6️⃣ P U = { 7 , 187 } PU=\{7,187\} PU={7,187}

7️⃣ P R = { 23 , 187 } PR=\{23,187\} PR={23,187}

加密解密过程如下：

选取M=88(88<187)

加密：$C=88^7\mathrm{m}\mathrm{o}\mathrm{d}187=11$

解密：$M=11^{23}\mathrm{m}\mathrm{o}\mathrm{d}187=88$

数学的破解有三种：

分解n，从而获得ø(n) 然后是 d

直接确定ø(n) ，然后是d

直接d

目前大家觉得1024-2048bit是安全的。

四、Diffie-Hellman密钥交换

第一个提出的公钥类策略

Diffie&Hellman

是一个使用的公开交换密钥的方法

在大量的商业应用中使用

该算法的有效性是建立在计算离散对数很困难的基础上

算法

共享的参数:

大素数 q或多项式

一个 mod q的本原根a：即a mod q，a² mod q，… ，a^q-1 mod q各不相同

在这种方法中，素数q和本原根α是两个公开的整数，假定用户A和B希望交换密钥，那么用户A选择一个随机整数$X_A<q$，并计算$Y_A={\alpha }^{X_A}\mathrm{m}\mathrm{o}\mathrm{d}q$，类似的，用户B也随机选择一个随机整数$X_B<q$，并计算$Y_B={\alpha }^{X_B}\mathrm{m}\mathrm{o}\mathrm{d}q$

A和B保持其X是私有的，但是对另一方而言Y是公开访问的，即$X_A和X_B$是私有的，$Y_A和Y_B$是公开的。

用户A计算$K=(Y_B{)}^{X_A}\mathrm{m}\mathrm{o}\mathrm{d}q$并将其作为密钥；用户B计算$K=(Y_A{)}^{X_B}\mathrm{m}\mathrm{o}\mathrm{d}q$并将其作为密钥，这两种计算所得的结果相同。

至此双方完成了密钥的交换。通常这个秘密值被用于对称密码的密钥。现在考虑一个敌手能够观察到密钥交换的全过程并且期望得到这个秘密K。由于X_A和X_B是私有的，所以攻击者只能通过q，α，Y_A，Y_B来进行攻击，这样，他就必须求离散对数才能确定密钥。例如，要对用户B的密钥进行攻击，攻击者就必须先计算
$$X_B=d{\log }_{\alpha ,q}(Y_B)$$
然后他就可以像用户B那样计算出密钥K。
$$K=(Y_A{)}^{X_B}\mathrm{m}\mathrm{o}\mathrm{d}q$$
计算过程如下：

Diffie-Hellman密钥交换的安全性建立在下述事实之上：求关于素数的模素数幂运算相对容易，而计算离散对数却非常困难：对于大素数，求离散对数被认为是不可行的。

举例说明

Alice 和 Bob 希望交换密钥:

1️⃣ 共享 q=353 与 α=3

2️⃣ 选择密钥:

A 选择X^A=97, B 选择X^B=233

3️⃣ 计算公钥:

Y^A=3⁹⁷ mod 353 = 40 (Alice)

Y^B=3²³³ mod 353 = 248 (Bob)

4️⃣ 会话密钥:
$$\begin{gathered} K_{AB}=(Y_B{)}^{X_A}\mathrm{m}\mathrm{o}\mathrm{d}353=248^{97}\mathrm{m}\mathrm{o}\mathrm{d}353=160Alice计算得到 \\ {K}_{AB}=(Y_A{)}^{X_B}\mathrm{m}\mathrm{o}\mathrm{d}353=40^{233}\mathrm{m}\mathrm{o}\mathrm{d}353=160Bob计算得到 \end{gathered}$$

五、EIgamal 密码体制——基于离散对数

与Diffie-Hellman一样，ElGamal的系统用户也是共同选择一个素数q，α是q的素根。

🔑 用户A生成的密钥对如下：

1️⃣ 随机生成整数X_A使得1<X_A<q-1。

2️⃣ 计算$Y_A={\alpha }^{X_A}\mathrm{m}\mathrm{o}\mathrm{d}q$

3️⃣ A的私钥为$X_A$，公开密钥为 { q , α , Y A } \{q,\alpha,Y_A\} {q,α,YA​}。

🔑 其他任何用户B通过A的公开密钥可以加密信息：

1️⃣ 将信息表示为一个整数M,其中1≤M≤q-1,以分组密码序列的方式来发送信息，其
中每个分块的长度不小于整数q。

2️⃣ 选择任意整数k,使得1≤k≤q-1。

3️⃣ 计算一次密钥$K=(Y_A{)}^k\text{mod}q$。

4️⃣ 将M加密成明文对$(C_1,C_2)$,其中

$C_1={\alpha }^k\text{mod}q;C_2=KM\text{mod}q$

🔑 用户A恢复明文：

1️⃣ 通过计算$K=(C_1{)}^{X_A}\text{mod}q$恢复密钥。

2️⃣ 计算$M=(C_2{K}^{-1})\text{mod}q$。

可用下一个图进行说明：

若信息需要分组加密后发出则要求每个分组必须使用唯一的$k$，否则对手可用一个已知的分组M₁计算其他

六、椭圆曲线密码体制

优点：

密钥尺度较小；

参数选择较灵活；

具有由数学难题保证的安全性；

实现速度较快。

参考资料

[1] 西安交通大学计算机网络安全与管理2022年春PPT 田暄

[2] 密码编码学与网络安全（第七版），William Stallings著，王后珍等译