现代密码学复习

您所在的位置：网站首页 › python程序随机生成一个100以内的正整数 › 现代密码学复习

现代密码学复习

2023-03-11 05:14| 来源: 网络整理| 查看: 265

密码学总结

第一章——只因础模型与概念

1.1 密码学五元组（结合皮卷）

1.2 Dolev-Yao威胁模型

1.3 攻击类型

1.4 柯克霍夫原则（Kerckhoffs's principle）

1.5 对称、非对称加密

1.6 密码的目标

1.7 保密通信模型

第二章——古典密码

2.1 仿射密码

2.2 Hill密码

例题0 ——解同余方程组

例题1——仿射密码

例题2——希尔密码

第三章——DES算法

IP置换

E扩展

S盒压缩

P盒置换

秘钥生成

分组加密

扩散与混淆

3DES

第四章——高级加密标准

4.1 x乘法

4.2 AES算法

第五章——RSA与公钥加密

通信开销对比

加密过程

证明

例题

第六章——离散对数与数字签名

6.1 离散对数问题

6.2 中间人攻击

6.3 Diffie- Hellman 密钥交换算法

6.4 Merkle's Puzzles秘钥交换协议

6.5 离散对数问题与生日攻击

6.6 ElGamal数字签名的实现过程

第七章——秘钥管理技术

秘钥分配中心(KDC)

第八章——几个重要的密码学话题

8.1 Shamir 门限方案

第九章——密码学新技术

9.1 椭圆曲线加密(ECC)

9.2 密钥更新

第一章——只因础模型与概念 1.1 密码学五元组（结合皮卷）

明文、密文、加密、解密、秘钥

明文：皮纸裹紧在密码棒上的信息

密文：单纯的皮纸

密钥：密码棒(Scytale)

加密：将空白的皮纸卷在密码棒上，再写信息

解密：将含有信息的皮纸裹紧在密码棒上

1.2 Dolev-Yao威胁模型

他能获得经过网络的任何信息

他是网络的一个合法使用者，所以可以跟任何用户对话

他可以成为任何主题发出信息的接收者

他能冒充任何人，给任何人发消息

1.3 攻击类型

唯密文攻击：只有密文，攻击者尽可能多的恢复明文，最好能获取密钥。

已知明文攻击：除了有截获的密文外，还有一些已知的“明文—密文对”来破译密码

选择明文攻击：密码分析者不仅可得到一些“明文—密文对”，还可以选择被加密的明文，并获得相应的密文

自适应选择明文攻击：不仅可得到一些“明文—密文对”，还可以选择被加密的明文，并获得相应的密文

选择密文攻击：可以选择一些密文，并得到相应的明文

1.4 柯克霍夫原则（Kerckhoffs's principle）

密码学上的柯克霍夫原则（Kerckhoffs's principle）：即使密码系统的任何细节已为人悉知，只要密匙未泄漏，它也应是安全的。所以现代密码学（基于柯克霍夫原则）的安全性，是密钥而非算法的安全性。

1.5 对称、非对称加密

1.5.1 对称加密（DES、AES）

传统密码算法，加密密钥能从解密密钥推出来，反之也成立。

对称加密算法可以分为两类，序列算法和分组算法。

序列算法：一次对明文中的一个bit或Byte运算

分组算法：对明文中的一组bit进行运算（经典分组长度为64位）

1.5.2 非对称加密（RSA）

公开密钥算法，加密的密钥不同于解密的密钥，而且解密密钥不能根据加密密钥计算出来。

1.5.3 对称加密的优缺点（不同）

优点：方便记忆；计算量小，速度快，适合对海量数据进行加密

缺点：

密钥传输不安全，密钥易泄露

用户增加导致密钥数量激增，管理困难

无不可抵赖性，不能进行数字签名

1.6 密码的目标

密码协议在安全系统中，其关键目的是安全（而不是算法不可破译），借助这些安全的密码算法，达到：

机密性：信道上信息的明文不被截获（先加密后传输）

完整性：可以检测数据是否被有意无意地修改过

认证性：身份认证，确认信息确实是XX发出的，而不是冒名顶替的

抗抵赖性：对于一个正在进行的行为，参与的主体不可否认（即不能虚假的否认他发出过XX信息）

1.7 保密通信模型

如图，秘密信道（安全信道）可以将秘钥k提前传给Bob，这里我们不论他们是怎样传输的。

Alice用秘钥k和加密机，加密明文m产生密文c，密文c在公开信道（不安全信道）传给解密机，解密机通过刚刚安全信道传来的k，将解密的m传给Bob。其实整个过程中，只有密文c传输的信道是不安全的，如果不能完全理解，还可以看看网上的图。

对应的攻击和得出

唯密文攻击：只知道密文，推出明文或密钥

已知明文攻击：知道部分的明文和密文对，推出密钥和加密算法。

在这里插入图片描述

选择明文攻击：知道明文就知道密文，目标为推出密钥。在这里插入图片描述

自适应选择明文攻击：在选择明文攻击中，密码分析者还可以选择一大块被加密的明文。而在自适应选择明文攻击中，可以选择较小的明文块，然后再基于第一块的结果选择另一个明文块，以此类推。所以其实和选择明文攻击区别不大。

选择密文攻击：知道密文就知道明文，目标为推出密钥。

在这里插入图片描述

第二章——古典密码 2.1 仿射密码

该密码运用了乘法逆元和模运算，a~z 对应于 0~25，将明文的每个字符转为对应的数字

加密函数： $\small D(x) = (a*x+b) \mod 26$ ，这里a,b变量就是密钥，注意 a必须和26互素

通过加密函数得到密文的数字，在查表，组合在一起就构成了密文。

解密过程与加密类似

解密函数： $\small E(x) = a^{-1}(x-b) \mod 26$ ，这里 $\small a^{-1}$ 是a关于26的乘法逆元。

注：仿射密码不能抵抗唯密文攻击（也就是什么都不能抵抗），具体原因比较复杂。我们可以根据大数据字母统计类型，判断他的移位b，之后同余列方程求解a（好像是这样）

2.2 Hill密码

希尔密码和仿射密码一样，是域上的线性运算。和仿射密码不同的是，这里的线性运算是矩阵乘法，因此他是多表替换的古典密码。

Step0 选取秘钥K

这一步是事先做的，随便选一个秘钥K： $\small \begin{pmatrix} 1 & 2 \\ 0 & 1 \\ \end{pmatrix}$

二阶矩阵求逆：

$\small \begin{pmatrix} a & b \\ c & d \\ \end{pmatrix}^{-1} \equiv (ad-bc)^{-1} \begin{pmatrix} d & -b \\ -c & a \\ \end{pmatrix} \mod 26$

$\small K^{-1} = \begin{pmatrix} 1 & -2 \\ 0 & 1 \\ \end{pmatrix}$

Step1 译码

先将明文串对应英文字母编码表进行数字转化 dloguszijluswogany--> 4 12 15 7 21 19 26 9 10 12 21 19 23 15 7 1 14 25，然后两两一组写成矩阵形式：

$\small \begin{pmatrix} 4 & 15 & 21 & 26 & 10 & 21 & 23 & 7 & 14\\ 12 & 7 & 19 & 9 & 12 & 19 & 15 & 1 & 25\\ \end{pmatrix}$

Step2 加密

$\small K*\begin{pmatrix} 4 & 15 & 21 & 26 & 10 & 21 & 23 & 7 & 14\\ 12 & 7 & 19 & 9 & 12 & 19 & 15 & 1 & 25\\ \end{pmatrix} = \begin{pmatrix} 1 & 2 \\ 0 & 1 \\ \end{pmatrix} \begin{pmatrix} 4 & 15 & 21 & 26 & 10 & 21 & 23 & 7 & 14\\ 12 & 7 & 19 & 9 & 12 & 19 & 15 & 1 & 25\\ \end{pmatrix}$

模26后结果即为加密信息

Step3 解密

$\small K^{-1}*\begin{pmatrix} 4 & 15 & 21 & 26 & 10 & 21 & 23 & 7 & 14\\ 12 & 7 & 19 & 9 & 12 & 19 & 15 & 1 & 25\\ \end{pmatrix} = \begin{pmatrix} 1 & -2 \\ 0 & 1 \\ \end{pmatrix} \begin{pmatrix} 4 & 15 & 21 & 26 & 10 & 21 & 23 & 7 & 14\\ 12 & 7 & 19 & 9 & 12 & 19 & 15 & 1 & 25\\ \end{pmatrix}$

模26后结果即为解密信息

注意译码、读取结果的顺序如下：

$\begin{pmatrix} 1 & 3 & 5 & ... \\ 2 & 4 & 6 & ... \\ \end{pmatrix}$

例题0 ——解同余方程组

$ax \equiv b\mod m$ 怎样求解

Step1 有没有解？有几个解？

解的个数为(a,m)，例如 $13x \equiv 1 \mod 25$ 只有一个解，而 $12x \equiv 1 \mod 26$ 有两个解（这里的一个解是0-m里的一个解，在实数范围内有无数个解）

Step2 a,b,m 同时除以 (a.m)

这一步可以很大程度上的化简运算，这样方程就只会有一个解，之后再把解扩大到 0~m 的范围。但有时候没必要，因为(a.m)有时为1

Step3 求化简后的 $ax \equiv 1\mod m$

欧几里得算法，如果m小应该直接试，解出来的x记作x_0

Step4 加入b

如果(a,m)=1，则 $x = x_0*b \mod m$

如果 $(a,m)1, x \equiv \frac{b}{(a,m)}*x_0+\frac{m}{(a,m)}*t,t = 0,1...,(a,m)-1$ ，注意a,b,m都是题目里最开始给出的值,，不是化简后的嗷！

例题1——仿射密码

明文E(4)，H(7)对应的密文F(5)，W(22)，求出仿射密码的秘钥

$f(x) = kx+b$ 代入可得方程

$\left\{\begin{matrix} 4k+b \equiv 5 \mod 26 & 1. \\ 7k+b \equiv 22 \mod 26& 2. \\ \end{matrix}\right.$

①x7，②x4得

$\left\{\begin{matrix} 28k+7b \equiv 35 \equiv 9 \mod 26 & 1. \\ 28k+4b \equiv 88 \equiv 10 \mod 26& 2. \\ \end{matrix}\right.$

$3b \equiv -1 \mod 26 \equiv 51 , b \equiv 17 \mod 26$

将b代入①中，同理可得 $k \equiv 23 \mod 26$

秘钥为 $f(x) \equiv (23x+17) \mod 26$

例题2——希尔密码

FRIDAY(5,17,8,3,0,24) --> PQCFKO(15,16,2,5,10,20) ，求秘钥矩阵K

$|K| \equiv | 5 \times 3- 8 \times 17 | \mod 26 = 9 \mod 26$

$\begin{pmatrix} 5 & 17 \\ 8 & 3 \\ \end{pmatrix}^{-1} \equiv 9^{-1} \begin{pmatrix} 3 & -17 \\ -8 & 5 \\ \end{pmatrix} \equiv 3 \begin{pmatrix} 3 & -17 \\ -8 & 5 \\ \end{pmatrix}\equiv \begin{pmatrix} 9 & 1 \\ 2 & 15 \\ \end{pmatrix} \mod 26$

$\begin{pmatrix} 5 & 17 \\ 8 & 3 \\ \end{pmatrix} * K \equiv \begin{pmatrix} 15 & 16 \\ 2 & 5 \\ \end{pmatrix} \mod 26$

$\therefore K \equiv \begin{pmatrix} 5 & 17 \\ 8 & 3 \\ \end{pmatrix}^{-1}\begin{pmatrix} 15 & 16 \\ 2 & 5 \\ \end{pmatrix}\equiv \begin{pmatrix} 9 & 1 \\ 2 & 15 \\ \end{pmatrix} \begin{pmatrix} 15 & 16 \\ 2 & 5 \\ \end{pmatrix} \equiv \begin{pmatrix} 7 & 19 \\ 8 & 3 \\ \end{pmatrix} \mod 26$

第三章——DES算法

DES属于对称密码算法中的分组加密（块加密），和流密码相对应。DES算法将明文分为若干个64位块（不足补充），秘钥为56位（8位校验位）。DES算法流程图如下

接下来，进行DES算法关键步骤的逐步解析：

IP置换

IP置换和IP逆置换，还有后面提到的P置换逻辑都是一样的。例如下图IP置换矩阵的第一行 n 第一列为58，含义即为将第58个元素位置换为第一个。置换完后密文长度不变，仍为64位。

E扩展

64位字段可以分为前32位和后32位，前32位不变，后32位进行E扩展置48位，具体扩展方法如下：

例如图中原本的32位字段为，将32位字段分为8组，每组前后各加两个比特，组成新的 $6 \times 8 = 48$ 位字段。新加的两位分别是前一组字段的最后一位和后一组字段的第一位，见下所示。

1101 0001 0011 0100 原文本 011010 100010 100110 101001 E扩展文本 S盒压缩

S盒是精心设计的8个矩阵，是DES算法中混淆的关键部分，他的质量（随机性）很大程度影响DES的加密效果。

之后，我们要再将E扩展后的48位后半字段，通过S盒压缩为32位，具体压缩方法如下：

先将48位分为8组，每组6位。6位取出前两位和中间四位，拼成2进制数，再将2进制转化为十进制，即经过一系列操作，将6位数变为2个十进制数。将这两个十进制数当作横纵坐标，寻找S盒中对应的十进制数，再将这个十进制数用4位2进制表示。至此，我们将48位文本压缩为了32位。

(3，15) 在S盒中对应的元素为13（查表得），之后转换为二进制1011，所以通过S盒我们将111111压缩为了1011。

P盒置换

P盒压缩和IP置换思路大致相似，例如第一行第一列元素为16，即将第16位置换到第一位，剩余以此类推。

秘钥生成

秘钥生成思路流程图如下：

如图中的流程，首先需要进行一次PC-1的选择置换，即去掉密钥中的校验位（8,16，...，64）。去掉8位校验位还剩下56位密钥，将56位分为C_0 (前28位)和D_0 (后28位) ，根据下表进行密钥的循环左移（如图中密钥表的计算逻辑）。得到的C_i D_i 进行合并后，再进行一次PC-2的选择置换，将密钥流变为48位。

分组加密

到现在完成了一套DES算法加密，但还存在很严重的一个问题：上述算法每次只能加密固定的64bit数据，但如果给出的明文不是64bit怎么办呢？？

为了解决这个问题，提供了下面的两种方案（也就是模式）：

ECB模式

ECB模式∶Electronic CodeBook mode（电子密码本模式）

CBC模式

CBC模式∶Cipher Block Chaining mode（密码分组链接模式）

这两者最大的区别即是，在发生错误时，对整个的解密加密会产生多大的影响。由加解密的流程图可见，ECB模式一旦某组出现错误，只会影响自己；但CBC模式一旦某组出现错误，会影响自己本组和后面的所有组，因为后面的密文、明文都需要和前一组进行异或操作，因此这种模式的可靠性更高。

在解密过程中，假设有一个密文分组损坏了，只要密文分组的长度没有变化，则解密时最多只会有2个分组受到数据损坏的影响。

假设密文分组中有一些比特缺失了，那么会导致密文分组的长度发生变化，此后的分组发生错位，则缺失比特的位置之后的密文分组就全部无法解密了。

CFB模式

密码反馈模式（Cipher Feedback, CFB）：CFB模式不直接加密明文，而是将前一个密文使用密钥Key再加密后，与明文异或，得到密文。同样，第一个密文需要初始向量IV加密得到。

与CBC模式比较：在CBC模式中，明文分组和密文分组之间有XOR和密码算法两个步骤；而在CFB模式中，明文分组和密文分组之间只有XOR。

OFB模式

输出反馈模式（Output Feedback, OFB）：OFB模式并不是通过密码算法对明文直接进行加密的，而是通过将“明文分组”和“密码算法的输出”进行XOR来产生“密文分组”的。在这一点上OFB模式和CFB模式非常相似。

和CBC模式、CFB模式一样，OFB模式中也需要使用初始化向量(IV)。

CTR模式

计数器模式（Counter, CTR）：CTR模式是一种通过将逐次累加的计数器进行加密来生成密钥流的流密码。

计数器的生成方法：每次加密时都会生成一个不同的值来作为计数器的初始值。其中前8个字节为nonce，这个值在每次加密时必须都是不同的。后8个字节为分组序号，这个部分是会逐次累加的。

场景应用

首先，ECB模式是绝对不建议采用的，因为安全性太差。

其次，在有噪声的信道中，建议采用CTR模式。CTR模式使用了计数器对明文进行加密，加密后的密文与明文长度相同，可以防止填充攻击，同时也不需要向CBC模式一样进行初始化向量的传输，因此在噪声干扰较大的情况下具有更好的容错能力。

在没有噪声的信道中，除了ECB的任何模式都可以。CBC、CFB、OFB都提高了安全性。此外，CTR模式具有并行加密解密的优势，在性能方面表现较好。

在混合网络模型中，应采用CBC模式和CTR模式，由于它们具有前向安全性和随机性，能够提供良好的保密性和完整性保护。

扩散与混淆

扩散

所谓扩散就是让明文中的每一位影响密文中的许多位，或者说让密文中的每一位受明文中的许多位的影响。这样可以隐蔽明文的统计特性。

在DES算法中，扩散的代表步骤是P盒置换，将S盒输出的 32 位数据打乱重排，32 位->32 位；结果为一轮 f 函数输出。这样明文中的每一位就可以影响密文中的许多位，达到了扩散的目的。

混淆

所谓混淆就是将密文与密钥之间的统计关系变得尽可能复杂，使得攻击者即使获取了关于密文的一些统计特性，也无法推测密钥，使用复杂的非线性代替变换可以达到比较好的混淆效果，例如乘积与迭代。

在DES算法中，混淆的代表步骤是 S 盒替换，S 盒替换中使用了 8 个 S 盒，每个 6 位输入，4 位输出，起到混淆作用，48 位->32 位。这让明文密文之间的关系尽可能复杂，达到了混淆的目的。

3DES

由于DES算法密钥太短，尽管算法上安全，但容易被暴力破解。因此，为了加长密钥使用了 3DES 算法。对于 3DES，明文块通过加密算法进行加密；然后结果再次通过同一加密算法；第二次加密的结果第三次通过同一加密算法。

通常，第二阶段使用解密算法而不是加密算法。第二阶段的解密在 3DES 算法的加密上没有任何加密意义。它的唯一优点是允许 3DES 用户通过重复密钥来解密由旧的单个 DES 用户加密的数据。

第四章——高级加密标准 4.1 x乘法

使用x乘法计算 $f(x) \times g(x)$

$\\ f(x)=x^6+x^4+x+1 , g(x)=x^2+x+1 \\ f(x)=x^6+x^4+x+1=01010011 , g(x)=x^2+x+1=00000111 \\ a_1 = f(x)\times1=01010011 \\ a_2=f(x)\times x = 10100110 \\ a_3=f(x)\times x^2=(10100110 \times 00000010) \bigoplus 00011011 = 01001100 \bigoplus 00011011=01010111 \\ \therefore f(x)\times g(x) = a_1 \bigoplus a_2 \bigoplus a_3 = 10100010 = x^7+x^5+x$

注：当b_7=1 ，也就是最前面的数字为1，乘x后的结果需要异或 00011011，具体原因类似溢出（课本P72）

练习题：

$f(x)=x6+x3+x2+1, g(x)=x7+x4+x3+1$ ，求 $f(x) \times g(x)$

$\\ f(x)*x: (01001101)*(00000010)=(10011010) \\ f(x)*x^2: (01001101)*(00000100)=(00110100) \oplus (00011011)=(00101111) b_7=1 \\ f(x)*x^3: 00101111*00000010=01011110 \\ f(x)*x^4: 10111100 \\ f(x)*x^5: 01001101*00100000=01111000\oplus00011101=01100011 b_7=1 \\ f(x)*x^6: 01001101*01000000=10101010 \\ f(x)*x^7: 10001100\oplus00011011=10010111 \\ f(x)*g(x)=01001101\oplus01011110\oplus10111100\oplus10010111 =00111000$

4.2 AES算法

AES 属于分组加密算法明文长度固定为128位密钥长度可以是128、192、256位，算法流程图如下：

注：最后一轮没有列混合，下面的算法默认明文密文为16字节（128位）

初始变换

将明文矩阵和子秘钥矩阵进行异或，得到新的矩阵，这一步称为初始变换

字节代换

跟DES算法中几乎一模一样，例如得到新矩阵的第一行第一列元素为 19，我们将1看做行，9看做列，在S盒中查找元素（假设找到为d4），那么这个19就替换为d4，整个矩阵的16个元素依次类推。

S盒如下：

行移位

按照如下规则进行行移位：

第一行不变

第二行整体向左1个字节（一个块）

第三行整体向左2个字节（一个块）

第四行整体向左3个字节（一个块）

列混合

将得到的矩阵左乘一个固定的矩阵，得到的结果为列混合的结果。

注：列混合不是普通的进行矩阵乘法，而是基于有限域上，具体过程如下

乘法如4.1，加法即异或，注意a_7=1要异或00011011 ，这即为列混合算法（乘法加法如4.1）。

轮秘钥加

得到的矩阵，每一列和每一列对应的与一个给定的矩阵进行异或。这个给定的矩阵来自之前的子秘钥矩阵，通过秘钥扩展可以得到10个这样的“给定的矩阵”。

秘钥扩展

如图，我们设列从w_0开始计数，要求的列为w_i ，求法如下：

如果i不是4的倍数，那么第i列由如下等式确定： W[i]=W[i-4]⨁W[i-1]

如果i是4的倍数，那么第i列由如下等式确定： W[i]=W[i-4]⨁T(W[i-1])

函数T由3部分组成：字循环、字节代换和轮常量异或。

1.字循环：将1个字中的4个字节循环左（上）移1个字节。即将输⼊字[b0, b1, b2, b3]变换成 [b1,b2,b3,b0]，如下图

2.字节代换：对字循环的结果使⽤S盒进行字节代换，如上S盒cf应该被替换为8a，依次类推

3.轮常量异或：将前两步的结果同轮常量Rcon[j]进行异或，其中j表示轮数。

如上图轮常量表在右上角已经给出，蓝色一列表示W[i-4] ，橘黄色一列表示刚刚得到的结果，浅黄色表示第一轮的轮常量Rcon[1] ，这三者异或就能得到i为4倍数情况下的扩展W[i] 。

最终秘钥扩展的结果如下图（共10组）

总结

扩散与混淆

扩散

所谓扩散就是让明文中的每一位影响密文中的许多位，或者说让密文中的每一位受明文中的许多位的影响。这样可以隐蔽明文的统计特性。

在AES算法中，扩散的具体实现是行移位+列混淆，因为列混淆使用有限域上的矩阵乘法，让每一字节的输出密文受到多个字节影响。

混淆

在AES算法中，混淆是通过字节代换实现的，这样可以让明文、密文间的关系尽量复杂。

第五章——RSA与公钥加密通信开销对比

RSA算法基于因素分解，ElGamal算法基于离散对数问题。这里的比较基于安全性相同，同时满足80bit安全特性。

80bit安全特性含义是：非对称加密的秘钥取多长，可以达到对称加密算法 80bit 密钥的强。他只是一个人为规定的东西，不用在意为什么这样规定。

对于RSA算法，需要选取两个大素数 p、q ，要传输的内容为 $M^e \mod N \equiv C$ ，要求 $N=p\times q \geq 1024bit$

对于ElGamal公钥加密，需要选取一个大素数 p ，要传输的内容是 $c =(c_1,c_2)$ ，其中算法为了达到同样的安全级别 p 要取160bit。

尽管ElGamal公钥加密要传输两个密文，但大素数 p 远远小于RSA算法的大素数N，因此传输的内容比RSA算法更少。

因此，在安全等级相同的情况下，ElGamal公钥加密比RSA算法的通信开销更小。

加密过程

选择一对不相等的大质数，记作p、q

计算 $N = p \times q$

计算 $\phi(N) = (p-1)\times(q-1)$

选择一个与 $\phi(N)$ 互质的整数e

计算出e对于 $\phi(N)$ 的模反元素d

公钥 KU = (e,N) ，私钥KR = (d,N) 注意这括号不是最大公约数，而是表达形式，具体见例题！

如果两个正整数e和φ(n)互质，那么⼀定可以找到⼀个整数d，使得ed-1被φ(n)整除，或者说ed除以φ(n)所得余数为1。此时，d就叫做e的模反元素。

加密 $M^e \mod N \equiv C$

解密 $C^d \mod N \equiv M$

证明

你可能现在比较疑惑，为什么 $C^d \mod N \equiv M$ 就能得到明文，下面是证明：

先将C代入，即：( $M^e \mod N)^d \mod N \equiv M$

根据D-H部分的证明可得， $M^{ed} \mod N \equiv M$

代入 $ed-1 \equiv k\phi(N) ,M^{k\phi(N)+1}\equiv M^{k\phi(N)}M \equiv M \mod N$

下面的证明目标即为 $M^{k\phi(N)}\equiv1 \mod N$ ，根据欧拉定理，在 $(a,N)=1$ 的情况下， $a{^\phi(N)} \equiv 1\mod N$ 所以只要证明 $(M^k,N)=1$ ，即M、N互素即可。

N的构成是两个大素数p、q的乘积，所以明文M的k次幂是不可能跟两个大素数有关的，再加上本身p、q的值都非常大，即便M是长串明文，也可能通过分组的方式避免这种微乎其微的可能。

例题

取p=3、q=11;

$N=p \times q = 33$

$\phi(N) = (p-1)(q-1) = 20$

选择一个与 $\phi(N)$ 互素的数，我们选择e=3

找到一个d使得 $ed \equiv 1 \mod \phi(N)$ ，解得 $d \equiv 7 \mod 20$

公钥 $KU = (e,n) = (3,33)$ ，私钥 $KR = (d,n) = (7,33)$

假如明文M=20，加密即为 $20^3 \mod 33 = 14$ ，解密即为 $14^7 \mod 33 = 20$

第六章——离散对数与数字签名

DH算法属于公钥加密算法，他产生的主要原因是解决保密通信模型中没有绝对安全信道的问题。

6.1 离散对数问题

假设a, p均为素数，则有以下等式： ${a_1 \mod p, a_2 \mod p,..., a_{(p-1)} \mod p} ={1, 2,..., p-1}$ //{}表示集合

对于任意⼀个数x，若0

【本文地址】

公司简介

联系我们