跳至主要內容

现代密码学

12a2024/10/7大约 58 分钟密码学

现代密码学

  • 现代密码学结合了信息论、数学和计算机科学，相比古典密码学经历了两次重要革命
    • 机械密码出现：第一次世界大战和第二次世界大战期间，密码学的重要性被全面提升。例如，德国的“恩尼格玛机（Enigma）”采用了复杂的电气转子系统实现了可变替换的加密方法。然而，盟军依靠计算技术的突破（如图灵团队的“炸弹机”）破解了恩尼格玛机，这直接推动了密码学向更强大的数学模型和计算手段的方向发展
    • 计算机和信息论出现：二战后，随着电子计算机的发明以及信息论的兴起，密码学进入了科学化的阶段，香农在1949年提出了完美安全性的概念：如果密钥长度至少等于明文长度且完全随机，密文将无法被破解。这一理论尽管强大，但由于密钥管理上的实际困难，只能在特定场景（如一次性密码本）中应用。因此，现代密码学需要在安全性和实用性之间找到平衡

对称加密算法

对称加密介绍

  • 现代对称加密密码学基于计算复杂性理论和混淆扩散理论
    • 计算困难问题的引入：计算复杂性理论为现代密码学提供了坚实的数学支撑。密码学的一个重要目标是设计在有效计算资源范围内难以破解的系统，这直接涉及到计算问题的复杂性分类。 这些问题的共同特征是已知解决方法的计算成本非常高，但验证其解却相对简单。密码学的许多方案基于以下假设：
      • 大整数分解问题(RSA 加密的基础)
      • 离散对数问题(ElGamal、椭圆曲线加密的基础)
      • NP完全问题(如哈密顿回路问题，广泛应用于零知识证明)
    • 香农的混淆与扩散香农的混淆与扩散理论进一步明确了加密算法的设计原则：
      • 混淆Confusion：通过复杂的代换操作，隐藏明文和密钥与密文之间的直接关系。
      • 扩散Diffusion：通过置换和轮转操作，使明文的一个微小变化能影响密文的多个位置
  • 对称加密算法是指加密和解密使用相同的密钥完成，一般分为以下两类
    • 分组密码：一般是通过将明文信息分为n段等长的数字序列，然后对每组使用相同的密钥生成对应的n段等长密文输出
    • 流密码：一般通过单一密钥生成多个循环的bit状态，使用bit状态一次对一个bit加密，生成一个bit结果，之后跳转下一个bit状态，直到明文全部bit都加密完成

分组密码算法

  • 分组密码：将内容分段加密，然后生成对应的每段密文
  • 出于对成本的考虑，分组密码不可能都使用一次一密的方式对每个组使用不同的密钥加密，一般都是使用单一密钥完成所有组加密的。在这种情况下，会存在重复内容加密结果相同的情况，根据重复的密文位置和重复内容可能给破解提供更多有效模式信息，降低破解难度，因此，分组密码的相邻块之间一般会进行混淆，一般有以下方案(包括不处理方案)

    • 电子密码本ECB：不对内容进行额外处理，算法简单

      • 加密解密可以并行实现
      • 相同明文得到相同密文，不能隐藏模式信息
      • 对某一块的直接攻击是可能的，块内容可能被删除替换重排
      • 如果传递中出现某块损坏，只会影响一块信息

    • 密码分组链接方式CBC：使用上一块密文异或当前明文(如果是第一块异或之前约定好的初始块iv)，对异或结果进行加密，解密时将解密结果异或前一块密文内容(如果是第一块异或iv)，得到原始明文

      • 没有已知的并行加密方法，但解密可以并行实现
      • 相同明文得到不同的密文，安全性好于ECB，是大多数系统标准的加密方法(ssl、ipSec)
      • 如果对一块内容攻击修改或发生传递损坏，会影响两块信息(当前块和之后一块)
      • 块内容不容易被删除替换重排
      CBC加解密流程图
      CBC加解密
      CBC加解密

    • 密码反馈方式CFB：修改加密方法，对前一块密文加密(第一块对初始块iv加密)，得到的加密结果异或当前明文得到本块密文，解密时也是执行加密操作，然后通过异或还原明文

      • 没有已知的并行方法，无论是加密还是解密
      • 将分组密码转换为类流密码的方式，密钥状态不断变换，通过和密钥状态异或完成本块加密
      • 隐藏了明文的模式信息，要求加解密的初始块相同且唯一
      • 对一块内容攻击修改或发生传递损坏，会影响多个块
      CFB方式加解密流程图

      CFB加密CFB解密

    • 输出反馈方式OFB：和CFB类似，修改加密方法，对iv不断加密(取加密结果一部分)，得到的新加密结果不仅异或当前明文得到本块密文，而且作为下一块要加密的内容，解密也是对iv不停加密，然后对每块通过异或还原明文

      • 没有已知的并行方法，无论是加密还是解密
      • 隐藏了明文模式信息
      • 对某一块的直接攻击是可能的，块内容可能被删除替换重排
      • 如果传递中出现某块损坏，只会影响一块信息
      OFB方式加解密流程图
      OFB加解密
      OFB加解密

流密码算法

  • 流密码：主流思想是根据密钥通过密钥流发生器zi=f(k,σi)z_i=f(k,\sigma_i)生成密钥状态bit流z=z1z2z3...z=z_1z_2z_3...，然后根据当前密钥bit完成每bit内容的加密

    • 其中σi\sigma_i是加密器中的记忆元件(存储器)在时刻ii的状态，ff是由密钥kk和σi\sigma_i产生的函数
    • 明文x=x1x2x3...x=x_1x_2x_3...的加密内容y=y1y2y3...=Ez1(x1)Ez2(x2)Ez2(x2)...y=y_1y_2y_3...=E_{z_1}(x_1)E_{z_2}(x_2)E_{z_2}(x_2)...
    • 二元加法流密码是目前最为常用的流密码体制，其加密变换可表示为yi=zi⊕xiy_i=z_i\oplus x_i，这里的二元是指生成结果只有0和1两种

  • 流密码可以分为同步流密码和自同步流密码两种，如果σi\sigma_i独立于明文字符的叫做同步流密码，否则叫做自同步流密码

    • 同步流密码：由于密钥流发生器和加密内容无关，密钥状态生成和加密可以看做两部分
    • 自同步流密码：是一种有记忆变换的密码。每一个密钥与已产生的固定数量的密文位有关，密钥由已生成的密文决定。在密文传输过程中，如果一个密文位发生变化，那么该位的变化会影响到后续密文位的正确解密。所以，自同步流密码有错误传递现象

      由于自同步流密码的状态难以分析，大部分理论内容都是对同步流密码的

  • 二元加法同步流密码是当前最为常用的流密码机制，通过一个滚动密钥生成器完成每位bit密钥状态的生成，通过异或完成每位明文的加密

    滚动密码生成器
    滚动密码生成器

  • 滚动密钥生成器：参考了一次一密的设计思路，通过密钥生成器代替创建一次一bit密钥，滚动密钥生成器的设计和优化思路是创建具有极大的周期、良好的统计特性、抗线性分析、抗统计分析的密钥流伪随机序列

  • 有限状态自动机：是具有离散输入和输出(输入集和输出集均有限)的一种数学模型

    • 主要由3部分构成
      • 有限状态集合
      • 有限输入和有限输出字符集
      • 状态转移函数：即根据当前状态和输入字符，决定跳转到的下一个状态
    • 有限状态自动机可用有向图表示，称为转移图
      • 转移图的顶点对应于自动机的状态
      • 转移图的有向边对应自动机的状态转移，即在对应输入值的情况下，状态将转移到另一个状态

  • 简单的同步流密码密钥生成器可以看作是一台以密钥k为输入的有限状态自动机，同时为了能够创建具有极大的周期、良好的统计特性、抗线性分析、抗统计分析的密钥流，并且要便于通过低配置硬件容易实现，必须采用非线性函数

    • 非线性转移的有限自动机理论还不太线性理论成熟，可以通过将非线性转移函数分解成线性驱动部分和非线性组合部分，当做两部分来实现
    • 线性驱动部分控制生成器的状态转移，为非线性组合部分提供统计性能好的序列
    • 非线性组合部分用这些序列生成满足要求的密钥流序列

  • 线性反馈移位寄存器：线性驱动部分可以通过线性反馈移位寄存器LFSR实现，有线性反馈和移位两个特点。很明显，构成线性反馈移位寄存器的多个一般寄存器序列a1a2a3...an−1ana_1a_2a_3...a_{n-1}a_n，每轮都执行移位操作和线性反馈操作f(a1,a2,...,an)f(a_1,a_2,...,a_n)，不断往复得到输出序列，初始状态可以由用户决定

    线性反馈移位寄存器结构图
    线性反馈移位寄存器结构图

    • 移位：寄存器中的内容将不断右移，右移出最低位寄存器的bit是本轮输出

    • 线性反馈：通过当前寄存器中的内容经过线性反馈结构得到的新bit将填入移位后空出的最高位寄存器，一般线性反馈结构是通过与和异或完成的，还可以添加常数开关，比如an+t=cnat⊕cn−1at+1⊕...⊕c1an+t−1a_{n+t}=c_{n}a_{t}\oplus c_{n-1}a_{t+1}\oplus...\oplus c_{1}a_{n+t-1}，其中的cic_i取0和1代表硬件开关控制寄存器是否参与反馈，tt为非负数表示生成轮数。通过这些开关控制，不是所有的寄存器aia_i都参与状态转移，添加了更多的变化

      带开关的线性反馈移位寄存器
      带开关的线性反馈移位寄存器

    • 线性反馈移位寄存器输出序列的性质完全由其反馈函数决定

      • nn级线性反馈移位寄存器最多有2的n次方个不同的状态
      • 若其初始状态为0，则其状态恒为0
      • 若其初始状态非0，则其后边的状态也不会为0
      • 因此n级线性反馈移位寄存器的状态周期小于等于2n−12^{n}-1

  • 线性反馈移位寄存器计算得到的输出密钥流序列需要有好的随机性，做到即使截获其中一段，也无法推测后面是什么。由于状态有限，而相同的状态状态转移结果是相同的，生成的密钥流是有周期的，要完全做到随机性是困难的，只能保证在截取到比周期长度短的序列时，不会发现规律，也就是伪随机序列

    • 对二元序列GF(2)GF(2)上的无限伪随机序列a=(a1,a2,...,an,...)a=(a_1,a_2,...,a_n,...)，是有最小周期p(a)p(a)的

      GF域的计算

      GF(2i)GF(2^i)是伽罗瓦域(有限域)的概念，在其中的运算都没有进位，应该转换为多项式xi+xi−1+...+x2+x+1x^{i}+x^{i-1}+...+x^{2}+x+1的形式做乘法和加法

      • 其中的GF(2)GF(2)指的是对应的多项式前面的系数只能为0或1，多项式中的加法运算是异或加法，相当于对2取模，当然在这里的输入aia_i也只能为0或1，最终输出结果也只有0或1

    • 将最小周期内的随机序列首尾相连，并把其中形如011...110011...110或100..001100..001即连续的1或0序列称为1的游程和0的游程，并把游程中的1或0的个数作为称为游程的长度

    • 序列的自相关函数R(t)=∑k=1T(−1)ak(−1)ak−1,0≤t≤T−1R(t)= {\textstyle \sum_{k=1}^{T}}(-1)^{a_k} (-1)^{a_{k-1}},0\le t\le T-1，当T=0T=0时，R(t)=TR(t)=T，当TT不为0时，函数称为异自相关函数

    • Golomb对伪随机序列提出了3个公设，满足3个公设就是伪随机序列 1. 在序列的一个周期内，0和1的个数相差至多为1(说明周期内中0与1出现的概率基本上相同) 2. 在序列的一个周期内，长为i的游程占游程总数的1/2i(i=1,2,...)，且在等长的游程中0的游程个数和1的游程个数相等(说明0与1在序列中每一个位置上出现的概率相同) 3. 异自相关函数是一个常数。这就意味着通过对序列与其平移后的序列作比较，不能给出其他任何信息

    • 为了能够作为密钥流，生成的伪序列还应该满足周期大，计算容易，难以根据周期内一块区域内容确定整个周期序列的三个条件

  • n级线性反馈移位寄存器an+t=cnat⊕cn−1at+1⊕...⊕c1an+t−1a_{n+t}=c_{n}a_{t}\oplus c_{n-1}a_{t+1}\oplus...\oplus c_{1}a_{n+t-1}生成的最小周期为mm的序列可以被证明满足3个公设，被广泛使用，如果不添加非线性部分，可以根据一段密钥流(密钥流可以通过明文和密文异或得到)，计算线性反馈操作f(a1,a2,...,an)f(a_1,a_2,...,a_n)中的cic_{i}，比如已知5级线性反馈移位寄存器的一段密钥流为110100100001011，计算方法如下

    • 如果希望破解关系，需要的密钥流长度应该至少为2n，比如根据5个aia_i的多项式方程组对应的矩阵表达式，上述5级线性反馈移位寄存器应该满足

      对应矩阵
      对应矩阵

    • 然后通过矩阵求逆可以求得cic_i的值，需要注意的是矩阵中只有0和1二元，因此在通过和E矩阵同时行变换求逆的过程中，可以直接使用异或加法

  • 非线性组合子系统用非线性组合函数F来实现，这部分会使用多个线性反馈移位寄存器LFSR的结果进行组合选择，得到最终的真实密钥流，还可以通过触发器完成

    • Geffe序列生成器：由3个LFSR组成，其中LFSR2作为控制生成器使用

      Geffe序列生成器
      Geffe序列生成器

    • J-K触发器：它的两个输入端分别用J和K表示，其输出不仅依赖本次输入，还依赖前一次的输出

      J-K触发器序列生成器
      J-K触发器序列生成器

    • 钟控制序列生成器：最基本的模型是用一个LFSR控制另外一个LFSR的移位时钟脉冲

      钟控制序列生成器
      钟控制序列生成器

第4章 流密码.ppt

DES

算法原理

  • DES是1977年由美国国家标准局颁布的数据加密标准，但由于算法本身存在缺陷，在1998年12月以后，DES就不再作为联邦加密标准

  • DES算法是一种分组加密算法，符合当时标准局的要求

    • 完全使用了处理器的基本运算，比如移位，加法等，可以快速完成
    • 加密和解密可共用同一套硬件结构，降低费用
    • 算法可被证明有效，且最终的加密和算法无关，和密钥有关

  • DES算法使用64位bit的密钥，对明文片段分组处理，每组处理64位bit的明文，主要流程可以分为以下部分

    • 内容块分割
    • 子秘钥生成
    • 每组加密置换

  • 内容块分割：直接将需要加密的字符串每64bit划分为一组，不足64位的内容补0，保证所有的加密组内容都是64位

  • 子密钥生成：算法使用64bit的密钥，但并非每一位都是用于存储密钥，秘钥中有奇偶校验位，有效密钥位数为56位，并通过16轮循环移位和置换选择操作获得真正的16轮48位密钥

    • 置换选择PC-164->56：去除8位奇偶校验(8、16、24、32、40、48、56、64)，同时对内容打乱，得到56bit的数据，置换如下

      置换表PC-1
      // DES置换下标从1开始
int PC1[56] = {
57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18,
10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36,
63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22,
14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4
};
      • 分割密钥数据：将密钥分割成左右两部分，每部分28bit
      • 对两部分数据分别循环左移：通过每轮循环左移，生成16个56bit秘钥(左右两边各28bit)，每轮左移位数根据密钥表确定
      移位表
      // 第i个值对应第i轮移位位数
int MOVE_TABLE[16] = {1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1};
      • 压缩置换PC-256->48：每轮得到的秘钥最后要进行重新打乱和压缩，将密钥结果变成48bit，压缩置换根据压缩置换表得到
      压缩置换PC-2
      // DES置换下标从1开始
int COMP_48_TABLE[48] = {
    14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10,
    23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2,
    41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48,
    44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32
};

  • 对每组64bit进行加密置换：通过对每组使用16轮密钥加密的方式，加密64bit信息，输出64bit密文结果

    • 输入数据开始时进行初始置换IP：通过初始置换打乱数据内容，64bit信息全部保留，只是更换位置

      初始置换表IP
      // 置换下标从1开始
int IP_TABLE[64] = {
    58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4,
    62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8,
    57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3,
    61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7
};

    • 分割数据块：将置换结果分割成左右两部分，每部分32bit

    • 执行16轮函数变换：每轮对右边32bit数据进行处理，之后交换左右部分，重复16轮，每轮处理过程如下

      • 对右边的32bit执行扩展置换32->48：通过扩展表在8行4列的32bit矩阵左右两边增加2列数据
      扩展置换
      // 置换索引从1开始
// 32 | 01 02 03 04 | 05
// 04 | 05 06 07 08 | 09
// 08 | 09 10 11 12 | 13
// 12 | 13 14 15 16 | 17
// 16 | 17 18 19 20 | 21
// 20 | 21 22 23 24 | 25
// 24 | 25 26 27 28 | 29
// 28 | 29 30 31 32 | 01
int EXPAND_TABLE[48] = {
    32, 1, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9,
    8, 9, 10, 11, 12, 13, 12, 13, 14, 15, 16, 17,
    16, 17, 18, 19, 20, 21, 20, 21, 22, 23, 24, 25,
    24, 25, 26, 27, 28, 29, 28, 29, 30, 31, 32, 1
};
      • 对此轮秘钥和扩展置换结果进行异或操作：48bit的数据和48bit秘钥按位执行异或
      • 对上一步结果执行S盒置换48->32：设计了8个S盒将48bit压缩成32bit，每个S盒都是4行16列的元素列表，8个S盒分别处理8段6bit数据，将6bit的第一个和最后一个bit位合在一起作为行索引的二进制形式b1b6b_1b_6，将剩下4bit作为列索引的二进制形式b2b3b4b5b_2b_3b_4b_5，将索引到的对应元素作为对应段的输出结果，对应元素不超过4bit，因此一共输出32bit
      S盒置换
      // 置换是通过二进制索引完成的，比如：100100作为第一段，那么就对应S1中第2行第2列即为15
int S_BOX[8][4][16] = {
    //S1
    14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7,
    0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8,
    4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0,
    15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13,
    //S2
    15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10,
    3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5,
    0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15,
    13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9,
    //S3
    10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8,
    13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1,
    13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7,
    1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12,
    //S4
    7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15,
    13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9,
    10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4,
    3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14,
    //S5
    2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9,
    14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6,
    4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14,
    11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3,
    //S6
    12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11,
    10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8,
    9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6,
    4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13,
    //S7
    4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1,
    13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6,
    1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2,
    6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12,
    //S8
    13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7,
    1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2,
    7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8,
    2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11
};
      • 对上一步结果执行P盒置换：将32bit数据再打乱顺序，得到新的32bit数据
      P置换
      int P_TABLE[32] = {
    16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 10,
    2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25
};
      • 将右边32bit结果异或左部分32bit数据，并将本轮开始时右边32bit数据作为下一轮的左边数据

    其中1-4是通过Feistel结构实现的，也被称为F函数

    • 交换左右部分，相当于取消16轮变换中的最后一次左右交换

    • 执行末置换IP-1：根据末置换表再打乱64bit结果得到最终的密文

      末置换IP-1
      int IP1_TABLE[64] = {
    40, 8, 48, 16, 56, 24, 64, 32, 39, 7, 47, 15, 55, 23, 63, 31,
    38, 6, 46, 14, 54, 22, 62, 30, 37, 5, 45, 13, 53, 21, 61, 29,
    36, 4, 44, 12, 52, 20, 60, 28, 35, 3, 43, 11, 51, 19, 59, 27,
    34, 2, 42, 10, 50, 18, 58, 26, 33, 1, 41, 9, 49, 17, 57, 25
};
每组处理的流程图
DES核心流程图
DES核心流程图

解密过程

  • DES算法加密和解密可以使用相同的算法，唯一的区别在于加密和解密的密钥顺序是相反的，在加密中第i轮使用的是第ii个密钥，而在解密中第ii轮使用的是第15−i15-i个密钥(i∈[0,15]i\in[0, 15])

DES的问题和优化

  • DES算法在提出之后，有以下争论
    • S盒设计思路不明确，可能有未知算法后门
    • 密钥长度过短，穷举破译时间短
    • 存在弱密钥和半弱密钥
      • 弱密钥是指经过生成之后，每轮密钥都相同，并且经过两次相同秘钥加密之后，会得到明文，一共有4个弱密钥
      • 半弱密钥是指使用一个密钥加密的结果，可以通过另一个密钥解密，一共有12个半弱密钥
  • 到了上世纪90年代，硬件和破译算法发展到已经可以在短时间完成破解，因此在算法过渡阶段，对DES算法进行了新的优化，通过变形增加算法的破解难度
    • 双重DES：对一个数据进行两次DES加密，加密的密钥应该避开半弱密钥
      • 可能出现中间相遇攻击，也就是如果已知一个明文和对应的加密结果，可以对明文进行加密得到所有密钥的加密结果，并通过hash或其他快速索引方法存储下来
      • 之后对密文解密，将解密的结果和所有加密结果进行比较，有很大概率能够找到两个密钥
      • 攻击所需运算次数少于2倍秘钥可能数(合计为2∗2562*2^{56})，仅需要256∗642^{56}*64个存储单元共计101710^{17}字节
    • 三重DES：通过三次DES加/解密，增加破解难度，有四种模型
      • DES-EEE3：三个不同密钥，顺序使用三次加密算法
      • DES-EEE2：密钥1=密钥3，顺序使用三次加密算法
      • DES-EDE3：三个不同密钥，依次使用加密-解密-加密算法
      • DES-EDE2：密钥1=密钥3，依次使用加密-解密-加密算法

      使用三重DES时，可以增加破解难度，提高安全性，而且可以将三重DES方便地转化为单DES(通过加密-解密-加密相同密钥)，但会增加加密时间，开销更多

DES--g2.ppt

AES

  • AES是在1997年美国国家标准技术研究所发起的高级加密标准Advanced Encryption Standard活动中选中的算法，活动有以下要求
    • 比三重DES快
    • 至少与三重DES一样安全
    • 数据分组长度为128比特
    • 密钥长度为128/192/256比特
    • 免费且要求放弃开发者版权，非保密
  • SP网络加密结构：在加密的每一轮中，分别经过S层和P层，S和P分别被称为混乱层和扩散层，主要起混乱和扩散作用

    • 轮输入首先被一个由子密钥控制的可逆函数S作用

    • 然后再对所得结果用置换(或可逆线性变换)P作用

      SP网络结构
      SP网络结构

AES算法的基本结构

  • AES算法的轮变换中没有Feistel结构，轮变换是由三个不同的可逆一致变换组成，称之为层
    • 线性混合层：确保多轮之上的高度扩散
    • 非线性层：具有最优最差-情形非线性性的S-盒的并行应用
    • 密钥加层：轮密钥简单地异或到中间状态上
  • AES算法的基本过程

    • 字节代换：AES的字节代换其实就是一个简单的查表操作。AES定义了一个S盒和一个逆S盒分别由来加密和解密

      • 状态矩阵中的元素按照下面的方式映射为一个新的字节：把该字节的高4位作为行值，低4位作为列值，取出S盒或者逆S盒中对应的行的元素作为输出
      置换表和逆置换表
      // 置换表
unsigned char sBox[] =
{ /*  0    1    2    3    4    5    6    7    8    9    a    b    c    d    e    f */
    0x63,0x7c,0x77,0x7b,0xf2,0x6b,0x6f,0xc5,0x30,0x01,0x67,0x2b,0xfe,0xd7,0xab,0x76, /*0*/ 
    0xca,0x82,0xc9,0x7d,0xfa,0x59,0x47,0xf0,0xad,0xd4,0xa2,0xaf,0x9c,0xa4,0x72,0xc0, /*1*/
    0xb7,0xfd,0x93,0x26,0x36,0x3f,0xf7,0xcc,0x34,0xa5,0xe5,0xf1,0x71,0xd8,0x31,0x15, /*2*/
    0x04,0xc7,0x23,0xc3,0x18,0x96,0x05,0x9a,0x07,0x12,0x80,0xe2,0xeb,0x27,0xb2,0x75, /*3*/
    0x09,0x83,0x2c,0x1a,0x1b,0x6e,0x5a,0xa0,0x52,0x3b,0xd6,0xb3,0x29,0xe3,0x2f,0x84, /*4*/
    0x53,0xd1,0x00,0xed,0x20,0xfc,0xb1,0x5b,0x6a,0xcb,0xbe,0x39,0x4a,0x4c,0x58,0xcf, /*5*/
    0xd0,0xef,0xaa,0xfb,0x43,0x4d,0x33,0x85,0x45,0xf9,0x02,0x7f,0x50,0x3c,0x9f,0xa8, /*6*/ 
    0x51,0xa3,0x40,0x8f,0x92,0x9d,0x38,0xf5,0xbc,0xb6,0xda,0x21,0x10,0xff,0xf3,0xd2, /*7*/
    0xcd,0x0c,0x13,0xec,0x5f,0x97,0x44,0x17,0xc4,0xa7,0x7e,0x3d,0x64,0x5d,0x19,0x73, /*8*/
    0x60,0x81,0x4f,0xdc,0x22,0x2a,0x90,0x88,0x46,0xee,0xb8,0x14,0xde,0x5e,0x0b,0xdb, /*9*/
    0xe0,0x32,0x3a,0x0a,0x49,0x06,0x24,0x5c,0xc2,0xd3,0xac,0x62,0x91,0x95,0xe4,0x79, /*a*/
    0xe7,0xc8,0x37,0x6d,0x8d,0xd5,0x4e,0xa9,0x6c,0x56,0xf4,0xea,0x65,0x7a,0xae,0x08, /*b*/
    0xba,0x78,0x25,0x2e,0x1c,0xa6,0xb4,0xc6,0xe8,0xdd,0x74,0x1f,0x4b,0xbd,0x8b,0x8a, /*c*/
    0x70,0x3e,0xb5,0x66,0x48,0x03,0xf6,0x0e,0x61,0x35,0x57,0xb9,0x86,0xc1,0x1d,0x9e, /*d*/
    0xe1,0xf8,0x98,0x11,0x69,0xd9,0x8e,0x94,0x9b,0x1e,0x87,0xe9,0xce,0x55,0x28,0xdf, /*e*/
    0x8c,0xa1,0x89,0x0d,0xbf,0xe6,0x42,0x68,0x41,0x99,0x2d,0x0f,0xb0,0x54,0xbb,0x16  /*f*/
};

// 逆置换表
unsigned char invsBox[256] = 
{ /*  0    1    2    3    4    5    6    7    8    9    a    b    c    d    e    f  */ 
    0x52,0x09,0x6a,0xd5,0x30,0x36,0xa5,0x38,0xbf,0x40,0xa3,0x9e,0x81,0xf3,0xd7,0xfb, /*0*/
    0x7c,0xe3,0x39,0x82,0x9b,0x2f,0xff,0x87,0x34,0x8e,0x43,0x44,0xc4,0xde,0xe9,0xcb, /*1*/
    0x54,0x7b,0x94,0x32,0xa6,0xc2,0x23,0x3d,0xee,0x4c,0x95,0x0b,0x42,0xfa,0xc3,0x4e, /*2*/
    0x08,0x2e,0xa1,0x66,0x28,0xd9,0x24,0xb2,0x76,0x5b,0xa2,0x49,0x6d,0x8b,0xd1,0x25, /*3*/
    0x72,0xf8,0xf6,0x64,0x86,0x68,0x98,0x16,0xd4,0xa4,0x5c,0xcc,0x5d,0x65,0xb6,0x92, /*4*/
    0x6c,0x70,0x48,0x50,0xfd,0xed,0xb9,0xda,0x5e,0x15,0x46,0x57,0xa7,0x8d,0x9d,0x84, /*5*/
    0x90,0xd8,0xab,0x00,0x8c,0xbc,0xd3,0x0a,0xf7,0xe4,0x58,0x05,0xb8,0xb3,0x45,0x06, /*6*/
    0xd0,0x2c,0x1e,0x8f,0xca,0x3f,0x0f,0x02,0xc1,0xaf,0xbd,0x03,0x01,0x13,0x8a,0x6b, /*7*/
    0x3a,0x91,0x11,0x41,0x4f,0x67,0xdc,0xea,0x97,0xf2,0xcf,0xce,0xf0,0xb4,0xe6,0x73, /*8*/
    0x96,0xac,0x74,0x22,0xe7,0xad,0x35,0x85,0xe2,0xf9,0x37,0xe8,0x1c,0x75,0xdf,0x6e, /*9*/
    0x47,0xf1,0x1a,0x71,0x1d,0x29,0xc5,0x89,0x6f,0xb7,0x62,0x0e,0xaa,0x18,0xbe,0x1b, /*a*/
    0xfc,0x56,0x3e,0x4b,0xc6,0xd2,0x79,0x20,0x9a,0xdb,0xc0,0xfe,0x78,0xcd,0x5a,0xf4, /*b*/
    0x1f,0xdd,0xa8,0x33,0x88,0x07,0xc7,0x31,0xb1,0x12,0x10,0x59,0x27,0x80,0xec,0x5f, /*c*/
    0x60,0x51,0x7f,0xa9,0x19,0xb5,0x4a,0x0d,0x2d,0xe5,0x7a,0x9f,0x93,0xc9,0x9c,0xef, /*d*/
    0xa0,0xe0,0x3b,0x4d,0xae,0x2a,0xf5,0xb0,0xc8,0xeb,0xbb,0x3c,0x83,0x53,0x99,0x61, /*e*/
    0x17,0x2b,0x04,0x7e,0xba,0x77,0xd6,0x26,0xe1,0x69,0x14,0x63,0x55,0x21,0x0c,0x7d  /*f*/
};

    • 行移位操作：行移位是一个简单的左循环移位操作。当密钥长度为128比特时，状态矩阵的第0行左移0字节，第1行左移1字节，第2行左移2字节，第3行左移3字节

      • 行移位的逆变换是将状态矩阵中的每一行执行相反的移位操作
      行移位
      行移位

    • 列混合：列混合变换是通过矩阵相乘来实现的，经行移位后的状态矩阵与固定的矩阵相乘，得到混淆后的状态矩阵

      • 矩阵的乘法是定义在GF(28)GF(2^8)上的，使用相乘矩阵时要对每个元素进行对应多项式取余乘法操作，不产生进位，在之后还要取余保证每个元素最后小于模数
      • 使用的矩阵是固定的，在加密变换时左乘此矩阵
      列混合
      列混合
      • 使用的逆矩阵也是固定的，在解密变换时也是左乘此矩阵
      逆列混合
      逆列混合

    • 轮密钥加：将128位轮密钥Ki同状态矩阵中的数据进行逐位异或操作，轮密钥通过密钥扩展得来

      • 为了实现128bit的异或，将内容的每一列4B分别与对应列32bit密钥w[x]进行异或
      • 轮密钥加的逆运算同正向的轮密钥加运算完全一致
      轮密钥加
      轮密钥加
      算法流程图
      AES算法流程图
      AES算法流程图
  • 密钥扩展：通过密钥调度算法从密钥中产生，包括两个组成部分：密钥扩展和轮密钥选取

    • 所有轮密钥比特的总数等于轮数加1再乘分组长度(如128比特的分组长度和10轮迭代，共需要1408比特的密钥)

    • 将密码密钥扩展成一个扩展密钥

    • 轮密钥按下述方式从扩展密钥中选取：第一个轮密钥由开始Nb个字组成，第二个轮密钥由接下来的Nb个字组成，如此继续下去

      密钥扩展
      密钥扩展
  • AES首先将初始密钥输入到一个4*4的状态矩阵中，密钥是依次填满矩阵的每一列，由此得到第一轮的四块秘钥
  • 其中每块之后的秘钥通过以下方法生成，⊕\oplus为异或
    • 如果i不是4的倍数，那么第i列由如下等式确定：W[i]=W[i−4]⊕W[i−1]W[i]=W[i-4]\oplus W[i-1]
    • 如果i是4的倍数，那么第i列由如下等式确定：W[i]=W[i−4]⊕g(W[i−1])W[i]=W[i-4]\oplus g(W[i-1])，其中g函数也就是g变换
  • g变换

    • 字循环：执行一字节循环左移，[b0,b1,b2,b3][b0,b1,b2,b3]->[b1,b2,b3,b0][b1,b2,b3,b0]

    • 字节替换：使用S盒实行字节替换

    • 轮常数异或：前两步的结果第一个字节和轮常数RC[j]异或，也可以认为轮常数后面还有3个全0的字节，下面给出的表中的数值为16进制

      每轮对应的轮常数
      每轮对应的轮常数

IDEA-RC5RC6-AES-g3g21 - 副本.ppt

非对称加密

非对称加密介绍

  • 非对称密码又称为公钥密码和双钥密码
    • 在公钥密码体制以前的整个密码学史中，所有的密码算法都是基于代换和置换这两个基本工具
    • 而公钥密码算法的基本工具不再是代换和置换，而是数学函数，而且以非对称的形式使用两个密钥
  • 公钥密码算法的最大特点是采用两个密钥将加密和解密能力分开，公开密钥用于加密，私有密钥用于解密。算法有以下重要特性： 已知密码算法和加密密钥，求解密密钥在计算上是不可行的
  • 对于公钥密码，我们需要构造单向陷门函数，也就是满足下列条件的函数ff：
    • 给定xx，计算y=f(x)y=f(x)是容易的
    • 给定yy, 计算xx使y=f(x)y=f(x)是困难的
    • 存在δ\delta，已知δ\delta时,对给定的任何yy，若相应的xx存在，则计算xx使y=f(x)y=f(x)是容易的

RSA

数学基础

  • 同余：RSA中大量运用了模运算modmod，模运算是求解余数的操作，如果(a mod n)=(b mod n)，则称a和b是同余的a≡bmod  na\equiv b \mod n，同余有以下性质
    • a−b≡0mod  na-b\equiv 0 \mod n，则称n∣(a−b)n|(a-b)
    • 若n∣(a−b)n|(a-b)，则a≡bmod  na\equiv b \mod n
    • a≡bmod  na\equiv b\mod n，则b≡amod  nb\equiv a \mod n
    • a≡bmod  na\equiv b\mod n,b≡cmod  nb\equiv c\mod n，则a≡cmod  na\equiv c\mod n
  • 取余运算的逆元
    • 加法逆元：对每一xx，都有一yy，使得x+y≡0mod  nx+y\equiv 0\mod n,称yy为xx的负数，也称为加法逆元
    • 乘法逆元：对xx，若有yy，使得x∗y≡1mod  nx*y\equiv 1\mod n，则称yy为xx的倒数，也称为乘法逆元，不是所有数都有乘法逆元
  • 扩展欧几里得算法求乘法逆元：扩展欧几里得算法是用于求解已知ax+by=gcd(a,b)ax+by=gcd(a,b)，求xx,yy的问题，对于ax≡bmod  max\equiv b \mod m的乘法逆元问题，可以通过ax=k1m+r,b=k2m+rax=k_1m+r,b=k_2m+r转换变为ax+(k2−k1)m=bax+(k_2-k_1)m=b，扩展欧几里得算法见互素判断，此时的b需要等于1，a才是x的乘法逆元
  • 定理：设a∈Zn={0,1,...,n−1}a\in Z_n=\{0,1,...,n-1\}，gcd(a, n)=1，则a在ZnZ_n中有mod n的乘法逆元，gcd是求最大公约数算法
  • 费尔马定理：也称为费马小定理，如果p是一个质数，而整数a不是p的倍数，ap−1≡1mod  pa^{p-1}≡1 \mod p
  • 欧拉定理：若a和n互素gcd(a,n)=1gcd(a, n)=1，则有aφ(n)≡1mod  na^{\varphi(n)}≡1 \mod n，其中φ(n)\varphi(n)是欧拉函数，指的是[1,n−1][1,n-1]中的整数与nn互素的元素个数，当nn是素数时，结果就是n−1n-1
  • Diffie-Hellman算法，利用了幂函数和取模计算密钥
    • 选取一个大素数p，和大的整数g，1<g<p1<g<p，这两个数无需保密
    • 两方分别选取一个足够大的数，计算y=gx(mod  p)y=g^x(\mod p)，并将计算结果发送给对方，然后对得到的结果使用自己的x，再求k=yx(mod  p)k=y^x(\mod p)，这时，两方的密钥都相同，为k1=k2=gx1x2(mod  p)k_1=k_2=g^{x_1x_2}(\mod p)
    • 使用计算的密钥进行加密和解密，除非发送密钥和之后通信时的内容，完全被中间人截获，并更换了两方收到的y，密钥是安全的，这要求中间主机能够快速实时计算出加解密结果

RSA基本原理

  • 算法采用了离散对数的困难问题，也就是建立在求大整数因子的困难性问题上
    • 对于一个由两个不同的素数相乘得到的大整数n，应该满足欧拉定理aφ(n)≡1mod  na^{\varphi(n)}≡1 \mod n，其中的欧拉函数φ(n)=(p−1)(q−1)\varphi(n)=(p-1)(q-1)，也就是在[1,pq][1, pq]之间有p个q的倍数和q个p的倍数不和n互素，pq被统计了两次，最后需要加1
    • 如果不告诉p和q的值，告诉n，寻找p和q使n=pq是困难的
  • 算法流程
    • 选大素数p和q，计算n=p×qn=p×q，φ(n)=(p−1)(q−1)\varphi(n)=(p-1)(q-1)
    • 随机选一在[1,φ(n))[1,\varphi(n))中的与φ(n)\varphi(n)互素的整数ee，也就是要求满足，求出对应逆元d=e−1(mod  φ(n))d=e^{-1}(\mod \varphi(n))
    • 取公钥为{e,n}\{e, n\}，私钥为dd
    • 加密是将明文M转换为一个个二进制长度小于nn的整数片段m，然后对每个明文分组m，做加密运算crypt=memod  ncrypt=m^e\mod n
    • 解密是对每个分组内容m=cryptdmod  nm=crypt^d\mod n
  • 细节问题：

    • 素性检验：通过概率素性检验判断大整数是否是素数，比如Miller-Rabin算法，见素性检测

    • 找到足够大的素数：一般是随机选取大的奇数，然后用素性检验判断是否是素数，重复这个过程

    • 大整数的指数运算：对于取模指数am=ymod  na^m=y\mod n可以使用快速指数运算，减少计算难度

      • 将m分解成二进制形式bkbk−1...b1b0b_kb_{k-1}...b_1b_0，则有am=(((((...abk)2abk−1)2...)2ab2)2ab1)2ab0a^m=(((((...a^{b_{k}})^2a^{b_{k-1}})^2...)^2a^{b_2})^2a^{b_1})^2a^{b_0}
      • 将计算拆解成从最低位开始的每次的乘法计算，并在每次乘法计算完成后对n取模，减少计算量
      long fast_exp(int a, int b, int m) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return ans % m;
}

椭圆曲线密码

  • 椭圆曲线是形如y2=ax3+bx+cy^2=ax^{3} + bx + c的曲线，如果希望构建椭圆曲线密码，首先要做的是构建曲线上的加法运算⊕\oplus，利用椭圆曲线上的两点构成的直线构建加法

    • 在椭圆曲线上取两点P和Q，连接PQ将和椭圆曲线E交于另一点R，计这种运算为P⊕Q=R′P\oplus Q=R'，另定义R的另一边的点即为R′=−RR'=-R

      椭圆曲线加法1
      椭圆曲线加法1

    • 也可以直接过P点做切线，与E交于另一点R，计这种运算为P⊕P=R′P\oplus P=R'

      椭圆曲线加法2
      椭圆曲线加法2

    • 还可以过两点做垂直x轴的直线，此时不与E交于第三个点，计这种运算为O⊕P=P\Omicron \oplus P=P，P′⊕P=OP'\oplus P=\Omicron

      椭圆曲线加法3
      椭圆曲线加法3

    实际情况下，椭圆曲线只选取GF(p)GF(p)上的有限域部分，也就是会对点的坐标对p取余

  • 椭圆曲线密码选择的困难问题是已知椭圆曲线上的一点xGxG是另一点GG的x倍点(G⊕(x−1)G=xGG\oplus (x-1)G=xG)，想知道x是困难的，将x作为密钥，xG作为公钥
    • 如果用户希望发送加密数据，应该发送点集{kG,M+kxG}\{kG,M+kxG\}，其中k是选取的随机数，M是原密文内容
    • 接收方通过(M+kxG)−x(kG)=M(M+kxG)-x(kG)=M计算得到原文，由于x难以知道，破解是困难的
    • 实际计算时需要对当前有限域范围取余
  • R点坐标可以通过直线和椭圆曲线E计算交点得到，比如椭圆曲线E为y2=ax3+bx+cy^2=ax^{3} + bx + c，三点坐标为P(x1,y1),Q(x2,y2),R(x3,y3)P(x_1,y_1),Q(x_2,y_2),R(x_3,y_3)
    • 计算直线斜率：不考虑无第三点P=−QP=-Q的情况，分为切线和非切线两种，切线通过对E两边求x导得到，非切线通过两点斜率公式得到

    λ={y2−y1x2−x1P≠Q3ax12+b2y1P=Q\lambda=\begin{cases}\frac{y_2-y_1}{x_2-x_1} P\not=Q\\\frac{3ax_1^2+b}{2y_1} P=Q\end{cases}

    • 对λ\lambda根据有限域范围p取模，如果λ\lambda不是整数，比如λ=mn\lambda=\frac{m}{n}，有mn=xmod  p\frac{m}{n}=x\mod p，即有nx=mmod  pnx=m\mod p，通过扩展欧几里得算法可以解得x的值
    • 带入得斜率方程(y−y1)=λ(x−x1)(y-y_1)=\lambda(x-x_1)或y=λx+by=\lambda x+b
    • 对于x3x_3通过将直线方程带入椭圆曲线E中，可以得到ax3−λ2x2+r=0ax^3-\lambda^2 x^2+r=0，其中的rr是其余项，由韦达定理，三次方程解和x1+x2+x3=−−λ2ax_1+x_2+x_3=-\frac{-\lambda^2}{a}，可求出x3x_3
    • 再根据直线方程求出y3y_3
    • 对坐标取模得到在有限域中的坐标

RSA==g61.ppt

数字签名

  • 若对相当长的文件通过签名认证，需要为长数据生成短的数字指纹，用来证实收到的消息来自可信的源点且未被篡改
    • 数字指纹不能轻易伪造，应该具有单向性，且抗碰撞
  • 数字签名函数一般有三类
    • 消息加密函数：用完整信息的密文作为对信息的鉴别
    • 消息鉴别码MAC：公开函数+密钥产生一个固定长度的值作为鉴别标识
    • 散列函数：是一个公开的函数，它将任意长的信息映射成一个固定长度的信息

散列函数

  • 散列函数H(M): 输入为任意长度的消息M; 输出为一个固定长度的散列值，称为消息摘要

    • H可以作用于一个任意长度的数据块
    • H产生一个固定长度的输出
    • 对任意给定的x，H(x)计算相对容易，无论是软件还是硬件实现
    • 对任意给定码h，找到x满足H(x)=h具有计算不可行性(单向性)
    • 对任意给定的数据块x，找到满足H(y)=H(x)的y≠xy\not=x具有计算不可行性，保证一个给定的消息的散列码不能找到与之相同的另外的消息(防止伪造，抗冲突)
    • 找到任意数据对(x,y)，满足H(x) = H(y)是计算不可行的(对已知的生日攻击方法的防御能力)

  • 生日攻击：一个教室中23个学生，至少有两人具有相同生日的概率不小于1/2，因此如果序列过短，很容易就会出现冲突

    • 可以看出，为了让哈希算法更安全，输出尽可能要长一点
    • 到目前为止，没有哪个哈希算法能够被证明为抗冲突的，但我们相信它们是抗冲突的
    • 生日攻击表明一个长度为n的消息摘要，只需要2n22^{\frac{n}{2}}次就可以找到冲突，即可输出个数的平方根
      生日攻击冲突所需寻找次数的证明

      可以写出有t个输出不冲突的概率为

      p=(1−12n)(1−22n)...(1−t−12n)=∏i=1t−1(1−i2n)p=(1-\frac{1}{2^n})(1-\frac{2}{2^n})...(1-\frac{t-1}{2^n})=\prod_{i=1}^{t-1}(1-\frac{i}{2^n})

      由于2n2^n一般很大，有

      p≈∏i=1t−1ei2n=e1+...+t−12n=e1+t−12n+1p\approx\prod_{i=1}^{t-1}e^{\frac{i}{2^n}}=e^\frac{1+...+t-1}{2^n}=e^\frac{1+t-1}{2^{n+1}}

      因此，如果设λ=1−p\lambda=1-p，则有

      2n+1ln⁡11−λ≈t(t−1)2^{n+1}\ln{\frac{1}{1-\lambda}}\approx t(t-1)

      由于t一般很大t≈t−1t\approx t-1

      t=2n+12ln⁡11−λt=2^{\frac{n+1}{2}}\sqrt{\ln{\frac{1}{1-\lambda}}}

      为了使λ>0.5\lambda>0.5，可以得到对应的tt

  • hash函数的通用结构：几乎被所有hash函数使用，具体做法

    • 把原始消息M分成一些固定长度的块Yi

    • 最后一块padding并使其包含消息M长度

    • 设定初始值CV0

    • 压缩函数f, CVi=f(CVi-1,Yi-1)

    • 最后一个CVi为hash值

      hash函数的通用结构
      hash函数的通用结构

SHA

  • SHA即安全哈希算法，已经经过了多次更新

  • 1993年SHA成为标准，生成128位结果，并在1995年改为SHA-1标准，SHA-1的特点是

    • 要求输入消息长度小于2642^{64}

    • 输入按512位的分组进行处理

    • SHA-1的摘要长度为160位

      SHA-1结构示意图
      SHA-1结构示意图

  • 补位：SHA1按照512bit间隔进行数据分批处理，且需要填充标志位和数据长度，因此消息必须进行补位

    • 原始数据末尾需要先追加一个字节填充(0x80)
    • 若此时数据长度不满足len%512=448len\%512=448, 填充(0x00)至满足条件
    • 每块中有448bit用于存储信息

  • 补长度：在末尾添加信息长度，一般是增加一块单独表示，因此要求信息长度小于2642^{64}

  • 初始化缓存：H(0), H(1), ..., H(4)区用以保存中间和最终散列函数的结果，大端存储时对应初始如下

    #define H0 0x67452301UL
#define H1 0xEFCDAB89UL
#define H2 0x98BADCFEUL
#define H3 0x10325476UL
#define H4 0xC3D2E1F0UL

// 设寄存器初始化如下，方便之后伪代码书写
ctx_.h0 = H0;
ctx_.h1 = H1;
ctx_.h2 = H2;
ctx_.h3 = H3;
ctx_.h4 = H4;

  • 消息摘要算法中的操作函数

    • S函数：循环左移操作符Sn(x)=(x<<n)∣(x>>32−n)S_n(x)=(x<<n)|(x>>32-n),x是一个字，也就是 32 bit大小的变量，n是一个整数且0<=n<=32

    • 非线性函数：使用第tt轮的数字进行计算

      /* const hash value for step */
#define K_00_19 0x5a827999UL  // step：00~19
#define K_20_39 0x6ed9eba1UL  // step：20~39
#define K_40_59 0x8f1bbcdcUL  // step：40~59
#define K_60_79 0xca62c1d6UL  // step：60~79
      非线性函数
      非线性函数

  • 消息摘要：计算需要两个160位的缓冲区，每个都由5个32位的字组成；还需要一个512位的数据缓冲区和一个双字临时缓冲区，经过80轮

    • 第一个5个字的缓冲区即为缓存当前轮结果寄存器A，B，C，D，E，初始值为当前的H0-H4，每轮更新

      A = ctx_.h0;
B = ctx_.h1;
C = ctx_.h2;
D = ctx_.h3;
E = ctx_.h4;

    • 第二个5个字的缓冲区即为存储最终结果H0, H1, H2, H3, H4

    • 512位作为16个双字的缓冲区W，存放当前块

    • 开始时，向缓冲区W0-W15填入当前块数据，之后16-79轮的缓冲区Wt数据由下面的方法生成

      Wt = S_1(W(t-3) ^ W(t-8) ^ W(t-14) ^ W(t-16))

    • 对所有轮都使用下方操作，其中T为临时缓冲区

      T = S_5(A) + F((B), (C), (D)) + (E) + W(t) + K(t);
E = D;
D = C;
C = S_30(B);
B = A;
A = T;
      消息摘要一次循环结构图
      消息摘要一次循环结构图

    • 修改缓冲区H，开启下一块的消息摘要

      ctx_.h0 = (ctx_.h0 + A) & 0xffffffffL;
ctx_.h1 = (ctx_.h1 + B) & 0xffffffffL;
ctx_.h2 = (ctx_.h2 + C) & 0xffffffffL;
ctx_.h3 = (ctx_.h3 + D) & 0xffffffffL;
ctx_.h4 = (ctx_.h4 + E) & 0xffffffffL;

  • 取出寄存器中的消息摘要结果：将处理好所有块之后的消息摘要H0, H1, H2, H3, H4以大端存储方式写入缓冲区

  • SHA-1在2005年证明只需要2692^{69}计算半天就可以找到冲突，比生日攻击2802^{80}低，已经被淘汰，现在使用的是SHA-2，有一系列算法，下方表格是SHA-1和一些SHA-2的算法的对比
类别SHA-1SHA-224SHA-256SHA-384SHA-512
消息摘要长度160224256384512
消息长度小于2642^{64}位小于2642^{64}位小于2642^{64}位小于21282^{128}位小于21282^{128}位
分组长度51251251210241024
计算字长度3232326464
计算步骤数8064648080

hash-gg9.ppt

量子通信

量子通信简介

  • 传统通信中存在被窃听的隐患，虽然可以通过算法缓解，但是存在破译的可能
  • 量子通信利用了物理学的基本原理，解决了这个问题，如果被窃听，信息测量后的微粒相比于测量之前，必然会产生变化
    • 测不准原理：微观世界中粒子位置是不可能被确定的,它总是以不同的概率存在于不同的地方，对未知状态系统的每一次测量都必将改变系统原来的状态
    • 量子不可克隆原理
    • 单个光子不可再分
  • 传统密码中加密的最佳方式是一次一密，但由于实现困难，密钥的更新和分配存在漏洞，商业化不可行
  • 量子通信中可以通过量子力学原理，解决一次一密中的密钥分发问题，这就是量子通信中的密钥分配协议即bb84协议，1984年提出，需要两条信道，一条量子信道，一条经典信道

    • 协议使用了两种编码方式，通过偏振光完成，发送方发送的数据会在这两个中随机选择一个进行编码

      编码方式
      编码方式

    • 同样的，在接收方也安排两种对应的测量基，由于接收不同情况的编码

      测量基
      测量基

      发送端使用的编码方式只有通过对应的测量基才能解密，不然无法获取信息

    • 协议过程

      • 发送方选定密钥S，逐位随机选取两种编码方式，然后通过量子信道发送S里0，1对应生成的量子态
      • 接收方通过量子信道收到发送方的信息后，随机使用测量基测量，正常情况下，测量错误的概率为50%(用错测量基)*50%(非0即1蒙错结果)=25%，当然也可能出现运输量子时发生损失，如果错误过多，说明可能被窃听
      • 接收方通过公共信道发送自己的选择
      • 发送方根据选择，告诉接收方哪些是对的，这些正确的串作为将要使用的密钥
      • 接收方再提供部分得到的正确位上的测量结果
      • 发送方确认测量结果的正确性，如果出错，回到开始或终止通信，否则发送确认信息，并剔除对应位置
      • 接收方收到确认信息后剔除发送的位置

量子通信.pptx

量子算法

  • 量子比特性质

    • 与经典比特有一个状态（0或1）不同，一个量子比特也有两种可能的状态，分别是∣0⟩\ket{0}与∣1⟩\ket{1}，后续也将∣0⟩\ket{0}与∣1⟩\ket{1}称为基态

    • 每个量子bit都是α∣0⟩+β∣1⟩\alpha\ket{0} + \beta\ket{1}，其中∣α∣2+∣β∣2=1|\alpha|^2+|\beta|^2=1，且α\alpha和β\beta都是复数

    • 对一个量子比特α∣0⟩+β∣1⟩\alpha\ket{0} + \beta\ket{1}加以测量，能以概率∣α∣2|\alpha|^2得到∣0⟩\ket{0}或以∣β∣2|\beta|^2概率得到∣1⟩\ket{1}

    • 量子比特可以通过列向量[αβ]\begin{bmatrix}\alpha\\\beta\end{bmatrix}表示，基向量∣0⟩\ket{0}可以表示为[10]\begin{bmatrix}1\\0\end{bmatrix}，∣1⟩\ket{1}可以表示为[01]\begin{bmatrix}0\\1\end{bmatrix}

    • 由于两个参数可以是复数且平方和为1，α\alpha和β\beta可以对应球坐标的θ\theta和γ\gamma，∣φ⟩=cos⁡θ2∣0⟩+eiγsin⁡θ2∣1⟩\ket{\varphi}=\cos{\frac{\theta}{2}}\ket{0}+e^{i\gamma}\sin{\frac{\theta}{2}}\ket{1}，也就是量子比特可以对应block圆上的点

      block圆
      block圆

  • 量子计算的优缺点，以特定的问题的计算函数f(x)f(x)举例说明，下方是对应的计算结构示意图，当前输入可以得到的结果∣φ⟩=∣0,f(0)⟩+∣1,f(1)⟩2\ket{\varphi}=\frac{\ket{0,f(0)}+\ket{1,f(1)}}{\sqrt{2}}，其中的逗号意思是多个比特的联合状态(这里是两个量子比特的联合状态)

    f(x)计算结构示意图
    f(x)计算结构示意图
    • 优点：量子计算能够并行，每个量子比特都包含了两个状态，就好像同时计算了所有的状态叠加，可以一次性评估所有可能的结果
    • 缺点：由于量子比特是两个状态的叠加态，不进行测量无法得到量子状态前面的系数，而进行测量后状态又被固定，也就是要设计量子算法，让测量结果趋向问题的解

  • 单比特量子门电路：对量子进行酉(you)变换，可以由2*2的矩阵UU给出，唯一的要求就是U+U=IU^+U=I，其中的U+U^+是UU共轭转置，II为单位阵

    共轭转置包括两个步骤，将矩阵的行和列互换；对矩阵中的每个元素取复共轭，即将复数的虚部取负

    • 常用的单比特量子门电路

      名称符号矩阵表示用途
      Hadamard门H12[111−1]\frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\1&-1\end{bmatrix}制备叠加态
      Pauli-X门X[0110]\begin{bmatrix}0&1\\1&0\end{bmatrix}将比特翻转(量子非门)
      Pauli-Y门Y[0−ii0]\begin{bmatrix}0&-i\\i&0\end{bmatrix}相位转移和比特翻转
      Pauli-Z门Z[100−i]\begin{bmatrix}1&0\\0&-i\end{bmatrix}转变相位
      相位门S[100i]\begin{bmatrix}1&0\\0&i\end{bmatrix}将1基态，在z轴方向上旋转一定角度,对0基态没有作用
      π8\frac{\pi}{8}门T[100eiπ4]\begin{bmatrix}1&0\\0&e^{\frac{i\pi}{4}}\end{bmatrix}-

    • 酉变换是唯一能够不改变矢量长度的变换

      证明思路
      证明思路

    • Hadamard门：对一个量子比特做H门操作，相对于让这个量子比特的向量表示左乘Hadamard门的矩阵形式

      • ∣0⟩\ket{0}：经过一个H门时，得到的是∣0⟩+∣1⟩2\frac{\ket{0}+\ket{1}}{\sqrt{2}}
      • ∣1⟩\ket{1}：经过一个H门时，得到的是∣0⟩−∣1⟩2\frac{\ket{0}-\ket{1}}{\sqrt{2}}
      • 如果对α∣0⟩+β∣1⟩\alpha\ket{0}+\beta\ket{1}使用了H门操作，会使∣0⟩\ket{0}项相互抵消，∣1⟩\ket{1}项被加强，经过H门后，得到的结果是(α∣0⟩+∣1⟩2+β∣0⟩−∣1⟩2)=α+β2∣0⟩+α−β2∣1⟩(\alpha\frac{\ket{0}+\ket{1}}{\sqrt{2}}+\beta\frac{\ket{0}-\ket{1}}{\sqrt{2}})=\frac{\alpha+\beta}{\sqrt{2}}\ket{0}+\frac{\alpha-\beta}{\sqrt{2}}\ket{1}

Grover量子搜索算法

  • 量子搜索算法的目的是在无序数据库或搜索空间中快速找到目标解，可能一个也可能多个，减少找到目标解所需的查询次数或计算复杂度
  • Grover量子算法：目的是在无序数据库中找到一个目标项，如果有多个满足条件的目标项，会随机找到一个

    • 初始化量子叠加态，使得搜索空间的所有项具有均匀概率幅

      • 初始时，使用N个全0的比特∣0⟩⊕n\ket{0}^{\oplus n}作为Hadamard门的输入
      • H(∣0⟩)=12[111−1][10]=12[11]H(\ket{0})=\frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\1&-1\end{bmatrix}\begin{bmatrix}1\\0\end{bmatrix}=\frac{1}{\sqrt{2}}\begin{bmatrix}1\\1\end{bmatrix}
      • 对每个比特施加Hadamard门，就可以生成一个叠加的均匀态

    • 通过一个标记函数对目标项的概率幅进行翻转，称为Oracle操作

      • 将需要的数据和其他的数据分开，方法是将需要的目标∣ω⟩\ket{\omega}变换相位，也就是增加负号

      Oω={∣x⟩ if x≠ω−∣x⟩ if x=ωO_\omega=\begin{cases}\ket{x}&\text{ if }x\not=\omega\\-\ket{x}&\text{ if }x=\omega\end{cases}

      • Oracle为Oω∣x⟩=(−1)f(x)∣x⟩O_\omega\ket{x}=(-1)^{f(x)}\ket{x}，其中的ff只有输入为需要的数据时才为1，剩下情况全是0，通过矩阵表示为

        O的矩阵表示
        O的矩阵表示

        一个例子

        也就是说，对应的矩阵是对特定状态进行了选择，如果状态使用的比特数为N，那么需要2N2^N大小的方阵，比如对于三量子比特序列，选择∣101⟩\ket{101}的选择矩阵UωU_\omega长这样

        三量子比特选择矩阵
        三量子比特选择矩阵

      • 所有的状态已经合在一起，对应的每个量子比特可以写成

      ∣φt⟩=1N∣x⟩+1N∑i=0i≠xN−1∣i⟩=∣β⟩+∣α⟩\ket{\varphi_t}=\frac{1}{\sqrt{N}}\ket{x}+\frac{1}{\sqrt{N}}\sum_{\substack{i=0\\i\not=x}}^{N-1}\ket{i}=\ket{\beta}+\ket{\alpha}

      ，其中∣β⟩\ket{\beta}是需要的数据

      • 将上面筛选取负的内容(量子比特序列)作为输入，即O(a∣α⟩+b∣β⟩)=a∣α⟩−b∣β⟩O(a\ket{\alpha}+b\ket{\beta})=a\ket{\alpha}-b\ket{\beta}，如果假设在所有的数据N中，有M个需要的数据，因此有a=N−MN,b=MNa=\sqrt{\frac{N-M}{N}},b=\sqrt{\frac{M}{N}}

    • 通过G算子增强目标项的概率幅，同时抑制其他项的概率幅

      • 设计G算子，G=(2∣ω⟩⟨ω∣−I)OG=(2\ket{\omega}\bra{\omega}-I)O，其中的OO就是上方的Oracle计算结果
      • G(∣φ⟩)=(2∣φ⟩⟨φ∣−I)(a∣α⟩−b∣β⟩)G({\ket{\varphi}})=(2\ket{\varphi}\bra{\varphi}-I)(a\ket{\alpha}-b\ket{\beta})

      G变换

      • 在以不需要的数据叠加态∣α⟩\ket{\alpha}为横轴，需要的数据叠加态∣β⟩\ket{\beta}为纵轴构建坐标系，设a=cos⁡θ2,b=sin⁡θ2a=\cos{\frac{\theta}{2}},b=\sin{\frac{\theta}{2}}，有∣φ⟩=cos⁡θ2∣α⟩+sin⁡θ2∣β⟩\ket{\varphi}=\cos{\frac{\theta}{2}}\ket{\alpha}+\sin{\frac{\theta}{2}}\ket{\beta}
      • 计算可以得到G(∣φ⟩)=(4cos⁡3θ2−3cos⁡θ2)∣α⟩+(3sin⁡θ2−4sin⁡3θ2)∣β⟩=cos⁡3θ2∣α⟩+sin⁡3θ2∣β⟩G(\ket{\varphi})=(4\cos^3{\frac{\theta}{2}}-3\cos{\frac{\theta}{2}})\ket{\alpha}+(3\sin{\frac{\theta}{2}}-4\sin^3{\frac{\theta}{2}})\ket{\beta}=\cos{\frac{3\theta}{2}}\ket{\alpha}+\sin{\frac{3\theta}{2}}\ket{\beta}
      • 最后一步是根据三倍角公式cos⁡2α=4cos⁡3α−3cos⁡α\cos{2\alpha}=4\cos^3{\alpha}-3\cos{\alpha}和sin⁡2α=3sin⁡α−4sin⁡3α\sin{2\alpha}=3\sin{\alpha}-4\sin^3{\alpha}得到结果
      • 可以用矩阵[cos⁡θ−sin⁡θsin⁡θcos⁡θ]\begin{bmatrix}\cos{\theta}&-\sin{\theta}\\\sin{\theta}&\cos{\theta}\end{bmatrix}表示变换，每次变换向∣β⟩\ket{\beta}旋转θ\theta
      对应的变换图
      对应的变换图
      • 因此Gk(cos⁡θ2∣α⟩+sin⁡θ2∣β⟩)=cos⁡(2k+1)θ2∣α⟩+sin⁡(2k+1)θ2∣β⟩G^k(\cos{\frac{\theta}{2}}\ket{\alpha}+\sin{\frac{\theta}{2}}\ket{\beta})=\cos{\frac{(2k+1)\theta}{2}}\ket{\alpha}+\sin{\frac{(2k+1)\theta}{2}}\ket{\beta}，G算子操作需要重复π4∗2n2M\frac{\pi}{4}*\frac{2^{\frac{n}{2}}}{M}次就能最接近需要的数据

      重复次数的计算

      ∣φ⟩=N−MN∣α⟩+MN∣β⟩\ket{\varphi}=\sqrt{\frac{N-M}{N}}\ket{\alpha}+\sqrt{\frac{M}{N}}\ket{\beta}，需要旋转的角度为π−θ2\frac{\pi-\theta}{2}，也就是在旋转arccos⁡MN\arccos{\sqrt{\frac{M}{N}}}之后会最接近∣β⟩\ket{\beta}

      • 这里隐含了角度小于π2\frac{\pi}{2}的条件
      • 每次角度增加θ\theta，因此需要的迭代次数为⌈arccos⁡MNθ⌉\lceil\frac{\arccos{\sqrt{\frac{M}{N}}}}{\theta}\rceil
      • 如果θ\theta很小，θ≈sin⁡θ≈2sin⁡θ2cos⁡θ2≈2MNN−MN≈2MN\theta\approx \sin{\theta}\approx 2\sin{\frac{\theta}{2}}\cos{\frac{\theta}{2}}\approx 2\sqrt{\frac{M}{N} \frac{N-M}{N}}\approx 2\sqrt{\frac{M}{N}}，结合θ<π2\theta < \frac{\pi}{2}，有π4∗2n2M\frac{\pi}{4}*\frac{2^{\frac{n}{2}}}{M}

    • 算法时间复杂度为o(MN)o(\sqrt{\frac{M}{N}})

deutsch算法

  • Deutsch算法是利用量子特性实现的最简单量子算法，这个算法要解决的问题是Deutsh问题

    • Deutsh问题：对于一个接受一位二进制数输入并输出一位二进制数的函数判断输出结果是常量(0或1)还是平衡的(各占一半)

    • 在经典算法里只能通过分别计算0和1对应的结果然后异或得到最终结果，当平衡时，异或为1

      def Judge(func: Callable[[int],bool]) -> bool:
    return (func(0) ^ func(1))

    • 但在量子位中，也就是有f(∣x⟩)=∣f(x)⟩f(\ket{x})=\ket{f(x)}，希望能够得到异或信息，因此需要对函数进行封装，并且应该是酉变换，可以使用Bf10∣x⟩∣y⟩=∣x⟩∣y⊕f(x)⟩B_{f^0_1}\ket{x}\ket{y}=\ket{x}\ket{y\oplus f(x)}对应的线路如下

      对函数的封装
      对函数的封装

  • 算法流程

    算法结构图
    算法结构图
    • 首先准备两个量子比特，两个量子比特分别初始化​∣0⟩∣1⟩\ket{0}\ket{1}，即有∣φ⟩=∣0⟩∣1⟩\ket{\varphi}=\ket{0}\ket{1}
    • 在每个量子比特上作用一个Hadamard门，此时状态叠加在一起，∣φ1⟩=∣0⟩+∣1⟩2∣0⟩−∣1⟩2\ket{\varphi_1}=\frac{\ket{0}+\ket{1}}{\sqrt{2}}\frac{\ket{0}-\ket{1}}{\sqrt{2}}
    • 通过BfB_f时，对这两个量子比特操作得到∣φ2⟩=∣0⟩+∣1⟩2(−1)f(x)∣0⟩−∣1⟩2\ket{\varphi_2}=\frac{\ket{0}+\ket{1}}{\sqrt{2}}(-1)^{f(x)}\frac{\ket{0}-\ket{1}}{\sqrt{2}}，xx为00和为11时，对应f(0)f(0)和f(1)f(1)，这个式子可以进一步化简，整体输出即

      ∣φ2⟩=∣0⟩+∣1⟩2(−1)f(x)∣0⟩−∣1⟩2=(−1)f(0)∣0⟩+(−1)f(1)∣1⟩2∣0⟩−∣1⟩2\begin{split}\ket{\varphi_2}&=\frac{\ket{0}+\ket{1}}{\sqrt{2}}(-1)^{f(x)}\frac{\ket{0}-\ket{1}}{\sqrt{2}}\\&=\frac{(-1)^{f(0)}\ket{0}+(-1)^{f(1)}\ket{1}}{\sqrt{2}}\frac{\ket{0}-\ket{1}}{\sqrt{2}}\end{split}

    • 在状态分离时，低位状态∣x⟩\ket{x}已经变成了(−1)f(0)∣0⟩+(−1)f(1)∣1⟩2\frac{(-1)^{f(0)}\ket{0}+(-1)^{f(1)}\ket{1}}{\sqrt{2}}，接下来再经过Hadamard门时，根据ff是否均衡，Hadamard门将得到不同的输出，进行测量即可
      • 当f(0)=f(1)f(0)=f(1)，(−1)f(0)∣0⟩+∣1⟩2(-1)^{f(0)}\frac{\ket{0}+\ket{1}}{\sqrt{2}}通过H门后将得到∣1⟩\ket{1}
      • 当f(0)≠f(1)f(0)\not=f(1)，(−1)f(0)∣0⟩−∣1⟩2(-1)^{f(0)}\frac{\ket{0}-\ket{1}}{\sqrt{2}}通过H门后将得到∣0⟩\ket{0}

      相位反冲

      线路最后的运行结果低位量子和高位量子并非是纠缠的，不论测量谁都不影响另一个量子；而且，最后只有低位量子包含我们需要的信息，高位量子则被丢弃

      • 此事的蹊跷之处在于，我们一开始引入黑箱量子门B时，状态不变的是低位量子，高位量子反而是应该发生改变的 像这种“本应改变的量子位(通常是受控位)没变、不应变的量子位(通常是控制位)反而发生改变”的现象称为相位反冲(Phase Kick-back)

量子算法简介1.pptx

区块链

简介

  • 区块链是分布式的块链式存储、不可篡改、安全可信的去中心化账本
    • 账本存储了整个网络中的交易信息，以块的形式存储，每隔一段时间就要使用新的块，所有人的资金都以数字形式存储在网络中，交易不仅要检查付款方的资金，还需要给出两方的电子凭证，确保交易是成立的
      • 区块的第一部分是区块头，它包含了标识和安全验证所需的元数据。这是整个区块的核心，比如包含上一块哈希值和时间戳，还有矿工计算的随机数
      • 区块的主体部分是交易数据，包含所有被矿工验证并打包进区块的交易记录
      • 区块的最后一行是该区块第一块和主体部分的哈希值，要求前一定位数全为0
    • 区块链中的矿工是维持网络的关键，负责验证交易、打包区块并添加到区块链中
      • 矿工计算能够让账本哈希值前一定位数为0的随机数，在计算完成后，将在下一个块第一行添加一个矿工奖励交易
      • 计算完成后将向所有网络中的节点广播，通过这种计算确保每个人账本的正确性
    • 账本的选择机制：当网络中存在多个账本分支(即分叉)时，系统如何决定哪个分支(或链条)被认可为主链。这一机制是区块链网络得以保持一致性的重要保障
      • 最长链原则：区块链通常选择**包含最多工作量(或累计权重)**的链条作为主链。比特币采用此原则
      • 累计工作量原则：选择累计工作量最高的链条，而不仅仅是区块数量最长的链条
      • 其他跟随权威节点决定的原则

      安全性保证

      如果一个节点希望蒙蔽另一个节点，他需要拥有比全网络一半矿工更大的算力(51%攻击)，才能保证被相信

  • 区块链中的拜占庭将军问题
    • 拜占庭将军问题：一群拜占庭将军围攻一座城市，必须通过商议一致决定是进攻还是撤退，如果不一致，可能会导致全军覆没
    • 对应的形式化定义：系统由nn个节点构成，其中的tt个节点是恶意节点(叛徒)，必须使所有的忠诚节点达成相同的决定，也就是需要少数服从多数决定
    • 解决办法
      • 口头消息算法：每个将军都会执行某个算法来把消息传送给其他将军，如果有三分之一是叛徒发布了相同的假消息，就无法判断两种消息的真伪，因此要求叛徒数量3t≤n−13t\leq n-1
      • 签名消息算法：将军之间传递消息必须附上签名，将进攻消息按顺序发送给每个将军，等每个人对消息做出评论(签名表示同意)，所有人都评论之后，再发送给每个人，让所有节点一致，要求叛徒数量t≤n−2t\leq n - 2

      使用签名的前提是：每个将军都知道其他将军的笔迹或印章，并且笔迹或印章无法被模仿，其他将军也容易进行认证；在一次通信中，各个将军是顺序签名的，如果所有的将军同时发消息，那么消息量会大大增加

两军问题

蓝军B驻扎在山谷之中，红军分两部分驻扎在山谷两旁A1，A2。A1和A2需要同时进攻才能击败蓝军。为了约定共同进攻的时间，A1派出通信兵将攻击时间传达给A2，但通信兵需要穿过山谷才能将攻击时间传达给A2

  • 问题思路

    • 而这个过程中，通信兵极有可能被蓝军截获从而导致A2不知道A1的进攻时间，于是A1不能确定进攻时间
    • 如果A2收到了进攻时间，为了和A1确定，A2在收到A1的信息之后也派出通信兵将自己受到的消息传给A1
    • 然而，A2的通信兵同样可能被拦截。于是A2也不确定A1是否知道自己的进攻时间
    • A1收到A2的消息，可以发出第三条消息，对A2做确认或者发现消息被篡改。但是，这又开始新的不确定过程。从而形成了无限循环，双方始终不能对进攻时间达成一致

  • 对比拜占庭将军问题

    • 这个问题虽然形式上拜占庭将军很像，但是本质上这两个问题是不同的。拜占庭将军问题描述的是可靠信道上的多主体共识问题，在满足一定条件的情况下，是可以达到一致性的
    • 而两军问题描述的是不可靠信道上的共识问题，也没有叛徒

  • 实际上，两军问题是第一个被证明是无解的计算机通信问题，在逻辑信道中由TCP协议降低风险，TCP三次握手通过加上序列号，确保对消息的确认，但是第三条消息能否被收到，发送方同样无法确认，也只是在成本和效率之间取得的折中

    两军问题
    两军问题
最近更新