密码学期末复习（PPT）

1. 概述

1.1 引言

  1. 1949年，香农的《保密系统通信理论》将密码学推向基于信息论的学科，近代密码学诞生。

    1976年，Diffie和Hellman提出公钥密码学的思想，开启了现代密码学。

  2. 我国密码分级：核心密码（核心机密）、普通密码（高于商用）、商用密码（非机密）、个人密码（个人隐私）。前三种密码都由国家密码管理局统一管理。

1.2 网络安全概念

  1. 信息安全三要素（CIA）：

    • 机密性
      • 数据保密性：隐私或者秘密数据不向非授权者泄露、也不被他们使用
      • 隐私性：个人能够控制和确定自身相关的哪些信息可以被收集、保存、公开及向谁公开
    • 完整性
      • 数据完整性：信息和程序只能以特定的方式进行改变
      • 系统完整性：系统以一种正常的方式执行预定的功能，免于被非法的操控
    • 可用性

    除此之外，还需要一些安全概念：

    • 真实性：一个实体是真实、可被验证的，或者信息和信息的来源是正确的。
    • 可追溯性：实体的行为可以追溯到唯一的该实体。

  2. 安全泄露事件的影响：

    执行使命的能力 资产损失 经济损失 对个人的伤害
    低 能力一定程度降低，效果稍有降低 较少 很小 很小
    中 能力显著降级，能完成主要功能，但效果明显降低 显著 显著 显著，但是不威胁生命安全
    高 能力严重降级，不能完成一项或多项功能 大部分 大部分 严重，包括威胁生命安全

  3. OSI安全框架：安全方面：攻击、机制和服务

    • 安全攻击：任何危及信息系统安全的行为。
    • 安全机制：用来检测、阻止攻击或从攻击状态恢复到正常状态的过程。
    • 安全服务：利用一种或多种安全机制进行反攻击。

  4. 安全攻击

    • 安全漏洞是信息系统产生安全问题的内因，也叫缺陷、隐患、脆弱性。

    • 安全威胁是信息系统产生安全问题的外因，也叫攻击。

    • 安全威胁分为：

      • 自然威胁：各种自然灾害、设备老化等
      • 人为威胁：对信息及信息系统的人为攻击，通过找弱点，到达破坏、欺骗等效果

    • 攻击方式有两种：主动攻击和被动攻击。

    • 被动攻击：窃听，不影响正常的通信，不对信息进行任何修改，以获取信息为目的。

      被动攻击分为：信息内容的泄露、流量分析。

    • 主动攻击：对数据流进行篡改，或者产生假的信息。

      主动攻击包括：

      • 拒绝服务：对系统可用性进行攻击。
      • 消息修改：修改消息内容、延迟传输、修改消息顺序等。破坏完整性。
      • 伪装：假装成其他实体。对真实性进行攻击。
      • 重放：将截获的信息再次发送。

  5. 安全服务：对系统资源进行特殊保护的处理或者通信服务。

    1. 数据保密性：防止消息内容泄露，被窃听。防止被动攻击
    2. 认证：保证通信的真实性。包括单向通信和双向通信
    3. 数据完整性：保证所接受的信息是未经修改或重放的，还能用于对一定程度损坏的数据的恢复。
    4. 不可否认性：接收者能证明消息的真实来源，发送者能证实接收者已经接受了消息
    5. 访问控制：检查用户是否对某一资源有访问权。实现方式是认证

  6. 安全机制

    • 大多数机制的共同点：密码技术
    • 特定的安全机制：加密、数字签名、访问控制、数据完整性、认证交换、流量填充、路由控制、公证
    • 普遍的安全机制：可信功能、安全标签、事件检测、安全审计追踪、安全恢复
    • 安全服务与机制间的联系（表格）

  7. 网络安全模型：两个基本成分和一个可选成分：

    1. 消息的安全变换
    2. 通信双方共享的秘密信息
    3. 有时需要一个可信第三方

3. 传统加密技术

3.1 密码学发展史

  1. 三个阶段：
    1. -1949：古典密码
    2. 1949-1975：计算机使得基于复杂计算的密码成为可能。数据的安全性基于密钥而不是算法的保密。
    3. 1976-：公钥密码、对称密码进一步发展

3.2 对称密码模型

  1. 密钥为，密钥可能值的范围为密钥空间。加解密函数为：

  2. 对于加解密过程，明文加密后再解密得到的内容必须和原来明文相同。

  3. 密码学：研究信息的保密和复原保密信息以获取其真实内容的学科称为密码学。它包括密码编码学和密码分析学。

    • 密码编码学：研究对信息进行编码实现隐蔽信息的一门学科。
    • 密码分析学：不知道任何加密细节的条件下解密消息的技术，即“破译”。

  4. 对称密码：

    • 又称传统密码、常规密码、私钥密码、单钥密码
    • 发送方和接收方共享一个共同的密钥。

  5. 对称密码安全的两个必备条件：

    1. 加密算法必须足够强
    2. 发送者和接收者在某种安全的形式下获得密钥并且保证密钥的安全

  6. Kerckhoff原则：系统的保密性不依赖于对加密体制或算法的保密，而依赖于对密钥的保密。

  7. 密码编码学的三个特征：

    1. 明文转换为密文的运算类型：代替（元素映射到另一个元素）、置换（元素的重新排列）。要求运算是可逆的。
    2. 所用的密钥数：单钥密码（基于计算安全性，即破译的计算量下限）、双钥密码（基于可证明安全性，即依赖数学难题）
    3. 处理明文的方法：分组密码、序列密码（流密码）

  8. 密码分析学：

    • 目标：得到密钥
    • 攻击方法：密码分析（利用算法的性质、明文的特性、明密文对）、穷举攻击
    • 基于密码分析的攻击：
      1. 唯密文攻击
      2. 已知明文攻击：已知多个明文-密文对
      3. 选择明文攻击：由破译者选择的明文信息及其密文
      4. 选择密文攻击：由破译者选择的密文信息及其明文
      5. 选择文本攻击：选择明文+密文攻击

  9. 无条件安全：算法产生的密文不能给出唯一决定明文的足够信息，此时敌手获得多少密文用多长时间都不能解密密文。仅当密钥至少和明文一样长时，才能达到无条件安全。即只有一次一密方案是无条件安全的。

  10. 计算上安全：破译密文的代价超过被加密信息的价值或破译密文所花的时间超过信息的有用期。计算上安全弱于无条件安全。

  11. 穷举攻击：敌手想找出一个私钥，采用穷举攻击。若k是均匀随机分布的，则敌手需要平均尝试：

3.3 代替技术

  1. 凯撒密码
    • 字母表位移k位
    • 共有26种可能的密钥，25种有效
    • 加密：
    • 解密：
  2. 采样密码（乘法密码）
    • 明文字母表每隔k位取出一个
    • 要求密钥k与26互素，有 个 可用密钥
    • 加密：
    • 解密：
  3. 仿射代替密码
    • 加法和乘法结合
    • q=26时，共26*12-1 = 311 个可用密码（减去的是不变的变换）
    • 加密：
    • 解密：
  4. 单表代替密码：
    • 随机映射
    • 密钥数目：
    • 缺陷：密文字母带有明文的统计特性，明文中一个元素仅影响密文中一个元素
    • 语言的统计特性：
      • 单字母：极大概率：e，大概率字母：tao，较大概率：inshr
      • 多字母
      • 单词特性
    • 单表代替密码之所以容易被攻击，是因为每个密文字母都是用同一个代替密表加密而成的，相同的密文字母对应着相同的明文字母。实际上只是改变字母的名称。
  5. Playfair密码
    • 多字母代替密码，5*5矩阵，先填充单词，再填充剩下的。I=J
    • 加密：明文两个字母一组，如果两个字母相同则在中间插入一个填充字母。同行：循环向右，同列：循环向下，对角线：另一对角线，按加密两字母的行排序
    • 优点：安全性优于单表代替密码，使用频率分析困难
  6. Hill密码
    • 多字母代替密码，利用矩阵
    • 加密：
    • 解密：
    • 优点：完全隐藏了单字母的频率特性，可以抵抗唯密文攻击
    • 容易被已知明文攻击破解

3.4 多表代替技术

  1. 多表代替：对每位明文采用不同的单表代替。当明文和密钥一样长时成为一次一密密码。
  2. 维吉尼亚密码：明文，密钥，密文
    • 26*26表格，行和列均为a-z，表内为每行以a.b.c...z开头的凯撒密码
    • 加密：
    • 解密：
  3. 博福特密码：
    • 加密：
    • 解密：
  4. 弗纳姆Vernam密码：
    • 与密钥诸位异或
  5. 一次一密：
    • 在Vernam密码中，如果采用的密钥不重复就是一次一密体制
    • 在理论上不可被破解，但是在实际上不可行
  6. 多表代替密码的破译：
    • 对于周期多表代替密码，可以转换成多组单表代替密码进行破译。

3.5 其他技术

  1. 置换技术
  2. 轮转机
  3. 隐写术

4. 分组密码和数据加密标准

4.1 Feistel密码

  1. 分组密码：明文分组加密，得到等长的密文分组。解密算法是加密算法的逆运算。

  2. 可逆变换：每个明文分组唯一对应一个密文分组。映射的总数是 。称为理想分组密码。

  3. 混淆：是密文和加密密钥之间关系变得复杂，以阻止攻击者发现密钥。

  4. 扩散：每个密文字母尽可能受多个明文数字的影响，使得明文的统计特性消散在密文中。

  5. 乘积密码：在单个加密机制中依次使用两个或两个以上不同类型的基本密码，所得结果的密码强度将强于每个单个密码的强度。

  6. Feistel密码是一种特殊的SP网络，交替使用代替和置换，增强密码的扩散和混淆性能。

  7. Feistel密码的结构：加密和解密完全相同

  8. 在Feistal密码结构中，中间经过若干轮上述基本结构，加密和解密的最后都要添加一步交换L和R

  9. F函数不必可逆。

  10. Feistel密码的解密过程与加密过程实质相同，无需区分实现加密和解密算法，只是密钥使用顺序不同。

  11. Feistel密码的设计：

    • 分组越大，安全性越高，但是计算越慢
    • 密钥越长，安全性越高，但是计算越慢
    • 循环越多，安全性越高
    • 子密钥产生算法和轮函数设计越复杂，安全性越高

  12. DES、SM4为分组密码

3.2 数据加密标准(DES)

  1. DES（Data Encryption Standard）使用56比特的密钥加密64位的明文，得到64位的密文。

  2. 算法的实现过程：

    1. 初始置换IP：

    2. 16轮迭代运算：，子密钥长48位

      迭代运算过程包含4步： --32bit--> 扩展置换E --48bit--> 与子密钥异或 --48bit--> S盒代替 --32bit--> 置换运算P --32bit-->

    3. 逆置换IP-1：

  3. S盒：唯一的非线性变换，决定了算法的安全强度，起到混淆的作用。DES中的S盒接受6bit，第一位和最后一位组成选择行，中间4位选择列，输出4比特

  4. 子密钥的产生：

    密钥扩展算法要求子密钥的统计独立性和灵敏性，从一些子密钥中获得其他子密钥在计算上是困难的。

  5. 雪崩效应：明文或密钥的一点小的变动都引起密文的较大变化。P置换的目的是提供雪崩效应。

  6. 弱密钥：初始密钥产生的16个子密钥相同。

    半弱密钥：存在不相等的，使得。DES一共有6对半弱密钥。

  7. 差分密码攻击：通过比较两个已知明文差异的明密文对，在使用相同子密钥的情况下搜索密文中的已知差异。

  8. 线性密码分析：基于找到DES中进行变换的线性近似，可以在有2^47个已知明文的情况下破译DES密钥，但实践中仍不可行。

  9. 分组密码的整体结构：Feistel结构和SP网络

  10. SP网络结构：每一轮中，轮输入首先被一个由子密钥控制的可逆函数S（混淆）作用，然后再对所得结果用置换（或可逆线性变换）P（扩散）作用。SP网络结构可以更快的扩散，但加解密通常不相似。

3.3 多重加密与三重DES算法

  1. 闭合的加密算法：对于任意密钥，都存在，使得： 对于闭合的加密算法，多次加密并不能增强安全性。但是DES不是一个闭合的加密算法，所以二重DES和三重DES有一定的价值。

  2. 二重DES的强度不等于56*2=112bit密钥的密码强度，会受到中途相遇攻击：

    中途相遇攻击：

    • 加密：
    • 已知一对。对所有可能的种对进行加密，得到z，存储为一个字典。对所有可能的种对进行解密，得到z，此时可以查找上述字典，配对x和y，一旦找到则确定两个密钥。
    • 两重DES的密文有种，密钥有种，因此有种密钥能产生给定的密文。
    • 攻击法最大的实验次数是次，即算法难度为。
    • 如果再用一对进行对密钥的验证，则错误率降为。

  3. 三重DES：

    • 加密：
    • 解密：

3.4 DES的差分密码分析

  1. 通过分析特定明文差分对相对应密文差分影响来获得尽可能大的密钥。

6. 高级加密标准

6.1 代换-置换网络(SPN)

  1. 乘积密码体制：先用一种密码进行加密，对加密结果使用另一种方法进行加密。如果第二种加密方式是自己，则为二重成绩，记为。n重成绩记为。
  2. 如果，则称密码是幂等的。幂等密码体制和自己做乘积，不能提高算法安全性。古典密码大部分都是幂等的。
  3. 迭代密码：如果密码不是幂等的，则多次迭代有可能提高安全性。一种构造简单的非幂等密码体制的方法是对两个不同的密码体制做乘积，并且保证两个密码体制是不能交换的。
  4. 在代换(S)-置换(P)网络中：加密：，解密：
  5. 对于任意的线性变换，都有：

6.2 高级加密标准(AES)

  1. Rijndael是一个迭代型分组密码，其分组长度和密钥长度都可变，可以为128比特、192比特、256比特。Rijndael使用非线性结构的S-boxes，能抵抗所有已知的攻击。Rijndael中轮函数由3层不同的可逆均匀变换组成，分别为线性混合层、非线性层、密钥加层。

    在第一轮之前使用一个初始密钥加层，目的是：使加解密相似、对安全性无意义、有利于差分分析。

  2. AES是一个迭代型分组密码，其分组长度固定为128 比特，密钥长度则可以是128，192或256比特

  3. AES流程：

  4. 128、192、256比特分别为：16、24、32字节，4、6、8字（），迭代轮数分别为10、12、14（）

  5. 分组是以字节为单位的4*4方阵.按列排序：

    1
    2
    3
    4
    a0	a4	a8	a12
    a1	a5	a9	a13
    a2	a6	a10	a14
    a3	a7	a11	a15

  6. 字节代替：S盒，非线性变换，输入8位，高4位为行值，低四位为列值，输出8位

  7. 行移位：第0行不动，第1.2.3行循环左移1.2.3位。经过行移位后，1列中4个元素被分布到不同的列中。

  8. 列混淆：矩阵乘法，运算范围是：。 列混淆的逆变换：

    列变换也可以通过多项式计算来定义：把状态矩阵的列视为多项式， 其中要求与模数多项式互素，这样才存在逆多项式进行逆运算。

    列混淆的原理：矩阵系数是码字间最大距离的编码（MDS码），这使得有良好的混淆性。经过几轮的列混淆和行移位后，所有的输出位与所有的输入位都有关。

  9. 密钥轮加：与密钥进行逐比特异或。

  10. 密钥扩展：共生成字，前4字用于和明文异或，后面每4字用于每轮的密钥轮加中。

    扩展过程中，如果下标不是4的倍数，则；如果是4的倍数，则将向左循环移动一个字节，并进行字节代换，与轮常数Rcon异或。

    使用轮常数消除对称性；密码密钥的差异扩散到轮密钥中的能力，即密钥的每个位能影响到轮密钥的许多位；已知部分密码密钥或部分轮密钥比特, 不能计算出许多其它轮密钥比特；足够的非线性性, 防止只从密码密钥的差分就能完全决定所有的轮密钥差分。

  11. AES的加密和解密的轮结构顺序不同，但是逆向行移位与逆向字节代替、轮密钥加和逆向列混淆可以交换。

    行移位改变顺序，字节代替改变内容，互不影响；可以将轮密钥做逆向列变换后，则可以先逆向列混淆，在与变换后的轮密钥异或。

  12. AES的安全性：可以抵抗差分攻击和线性密码攻击，目前还不存在快于穷举攻击的攻击方式。

  13. 评价：运算均在2^8有限域上，除了查表操作外均为简单的异或和移位操作。每一轮密钥扩展中都有非线性变换，增强了密码的抗攻击能力。

7. 分组加密的工作模式

7.1 电话本模式 ECB

  1. 明文分组，每组都使用相同的密钥加密。同一明文组总产生同样的密文组。
  2. 如果最后一组不足64位，则需要填充。
  3. 适合短消息加密，应用长消息时容易受到攻击。

7.2 密文分组链接模式 CBC

  1. 加密算法的输入是当前明文分组和前一次密文分组的异或，每个密文块依赖于前面的所有明文块。
  2. 需要使用初始化向量，IV应像密钥一样被保护。需要填充。
  3. 加密时无法并行处理。解密时，从两个邻接的密文块即可得到一个明文块，因此解密过程可以被并行化。
  4. 如果传输时发生错误，则恢复的明文中只有这个块和下一块的内容发生改变。
  5. 解密时，密文中1位的变化只会改变这个块和下一块的内容改变。
  6. 加密过程为：

7.3 密文反馈模式 CFB

  1. 利用CFB（cipher feedback）模式或OFB模式可将分组对称密码转换为流密码。

  2. 不需要对消息填充，而且运行是实时的。

  3. 需要初始向量。

  4. 加密过程不能并行化，解密过程可以。

  5. 对信道错误较敏感，错误传播：1个比特密文传输错误会传播约64/j个分组。

  6. 加密过程：

    、

7.4 输出反馈模式 OFB

  1. 与CFB的区别是加密算法的输出反馈到下一轮。

  2. 优点：传输过程中的比特错误不会被传播；缺点：比CFB模式更易受到对消息流的篡改攻击。

  3. 加密过程：

7.5 计数器模式 CTR

  1. CTR将块密码变为流密码。它通过递增一个加密计数器以产生连续的密钥流，其中，计数器可以是任意保证不产生长时间重复输出的函数，使用一个普通的计数器是最简单和最常见的做法。

  2. 不需要填充

  3. 可并行加密，可预处理（明文不参与密钥生成），加密数据块随机访问（只需要加计数器）

  4. 加密过程：

8. 伪随机数的产生和流密码

8.1 伪随机数的产生原则

  1. 随机数序列需要满足两个特征：随机性和不可预测性
  2. 随机性：
    • 分布均匀性：0和1均匀分布
    • 独立性：任何子序列不能由其他子序列推导出
    • 序列是否满足分布均匀性可以检测得出，但是是否满足独立性无法检测。有一些算法可以检测出不满足独立性。
  3. 不可预测性：
    • 序列以后的数是不可预测的。
    • 真随机数列是不可预测的，因为各个位之间互相独立。
    • 伪随机数序列要注意不可预测性。
  4. 真随机数：物理噪声、高质量随机数编辑成书、真随机数发生器（TRNG）
  5. 伪随机数：使用算法生成随机数，由伪随机数发生器（PRNGs）产生
    • 伪随机数发生器（PRNG）：生产不限长度的位流，通常作为对称流密码的输入。
    • 伪随机函数（PRF）：用于产生固定长度的伪随机数串。如对称加密的时变值。PRF的输出常为种子加一些上下文相关的特定值。
  6. 对PRNG的要求：
    • 通用要求：输出保密性：不知道种子的敌手不能知道伪随机串。
    • 特定要求：随机性、不可预测性、种子的特性
      • 随机性：尽管生成的位流是确定的，但是要显示是随机的。
      • 不可预测性：前向不可预测性、后向不可预测性
      • 种子的特性：安全、不可预测
  7. PRNG的设计
    • 特意设计的PRNG算法
    • 基于现存密码的算法，如对称分组密码、非对称密码、Hash函数等

8.2 伪随机数发生器

8.2.1 线性同余发生器

  1. 参数：m模，a乘数，c增量，X0初始值或种子

  2. 迭代算法：

  3. 评价线性同余发生器的性能：

    • 迭代函数应该是全周期的，级重复0 - m-1之间的所有书
    • 产生的序列应该看上去是随机的
    • 能有效地利用32位运算器方便的实现

  4. 在计算机中，为了满足上述指标并便于运算，m一般取，c=0，a是m的一个本原根（如7^5）

  5. 线性同余算法只在初值X0的选取具有随机性，算法本身无随机性，以后的数被确定性的产生了。

  6. 如果敌手知道算法的参数，只要知道当前的一个数，就知道了后续的所有数。

    敌手知道数列中的极少一部分，就可以确定出算法的参数。

  7. 可以利用内部系统时钟修正随机数数列：产生几个数后用时钟值作为种子；或者将当前时钟值加到每个随机数上。

8.2.2 BBS发生器

  1. 参数：两个大素数，，一个随机数s与n互素

  2. 算法：

    1
    2
    3
    4
    X[0] = s ** 2 % n
    for i in range(length):
        X[i] = X[i-1] ** 2 % n
        B[i] = X[i] % 2

  3. BBS的安全性基于大整数分解的困难性，是密码安全伪随机数比特产生器

  4. 密码安全伪随机数比特产生器：以伪随机比特产生器的输出序列的前k个比特作为输入，不存在多项式时间算法，能以大于1/2的概率预测第k+1个比特。

8.3 使用分组密码的伪随机数发生器

  1. 使用分组密码CTR模式和OFB模式：

  2. ANSI X9.17：使用3个三重DES加密，输出一个64比特的伪随机数和一个64比特的新种子

8.4 流密码

  1. 伪随机数发生器的输出称为密钥流，密钥流和明文流的每一个字节进行按位异或运算，得到一个密文字节。密码系统的安全性取决于密钥流的性能。

  2. 流密码类似于一次一密，但是一次一密使用的是真正的随机数流。

  3. 一次一密密码：密钥流是完全随机序列，且密钥不重用。一次一密在唯密文攻击条件下是理论保密的，这是唯一一个能被证明是无条件安全的密码。

  4. 流密码可以分为：同步流密码和自同步流密码

  5. 同步流密码：密钥流生成器独立于明文字符。

    • 对于明文而言，加密过程是无记忆的；解密过程要求密钥流和加密密钥流完全同步。
    • 通信双方有相同的种子序列和初始状态，就可以产生相同的密钥。

  6. 自同步流密码：密钥流生成器与明文字符有关。

    • 是有记忆的：时刻的密文与时刻的明文和时刻之前个明文符号有关。

    • 有自同步能力。

    • 明文每个字符扩散在密文多个字符中，强化了抗统计分析的能力。

8.5 线性反馈移位寄存器 LFSR

  1. 密钥发生器的组成：驱动部分（提供统计特性好的序列）和非线性组合部分（变换成密码学特性好的序列）

  2. 反馈移位寄存器是序列密码设计中常用乱源。目的是以种子密钥为序列的初态，按照确定的递推关系，产生一个周期长、线性复杂度高、统计特性好的初始乱源，然后利用密码变换，最终产生抗破译能力强的乱数序列。

  3. 一个反馈寄存器由两部分组成：移位寄存器和反馈函数。如果反馈函数、是n个变量的线性函数，则称为线性反馈移位寄存器(LFSR)。输出的序列称为线性反馈移位寄存器序列，记为LFSR序列。

  4. 把多项式f(x)称为LFSR的特征多项式

  5. 例题：

  1. 反馈移位寄存器的功能完全由其反馈逻辑函数决定。

  2. 移位寄存器的序列存在周期。能达到最长周期的序列称为m序列。

  3. 表示方法：

8.6 流密码RC4算法

  1. RC4分为密钥调度算法（KSA）和伪随机数生成算法（PRGA）

​ KSA使用密钥生成原始S表。

​ PRGA使用S表产生流密钥序列。

  1. 加密单位是字节。密钥长度1-256字节任意。

  2. 密钥调度算法：

    RC4使用了一个2^8字节大小的非线性数据表(简称S表)，对S表进行非线性变换，得到密钥流。

    1
    2
    3
    4
    5
    S = [i for i in range(256)]
    T = [k[i % len(k)] for i in range(256)]
    for i in range(256):
        j = j + S[i] + T[i] % 256
        S[i], S[j] = S[j], S[i]

  3. 伪随机数生成算法：

    1
    2
    3
    4
    5
    6
    7
    i, j = 0, 0
    while True:
        i = i + 1 % 256
        j = j + S[i] % 256
        S[i], S[j] = S[j], S[i]
        t = S[j] + S[i] % 256
        k = S[t]

  4. 通过设计合适的伪随机数发生器，当密钥长度相当时，流密码可提供和分组密码一样的安全性。

  5. 对于流密码，如果用流密码对两个明文加密且使用相同密钥，则密码分析就会相当容易：如果对两个密文流进行异或，那么得出的结果就是两个原始明文的异或。

9. 公钥密码与 RSA

9.1 公钥密码原理

  1. 公钥，私钥

  2. 可提供的安全服务：

    • 保密性：任何人可以使用公钥加密，只有私钥持有者可以用私钥解密。
    • 不可否认性：只有私钥持有者可以使用私钥签名，任何人可以使用公钥认证。

  3. 公钥密码技术研究的基本工具不再像对称密码技术那样是代替和置换，而是数学函数。公钥密码体制的这种安全性理论基础只是基于复杂性理论的一种计算安全性。

  4. 公钥密码体制由6部分组成：明文密文、公钥私钥、加密解密算法。

  5. 公钥密码体制的主要特点是采用两个密钥将加密和解密能力分开。

  6. 使用公钥密码进行加密时，由于任何人都可以使用公钥进行加密，因此得到的密文不具有认证性，即无法确定是谁发的。因此要同时实现保密性和认证性，要采用双重加密：先用自己的私钥进行签名，再用对方公开的公钥加密后公开。

  7. 公钥密码应该满足的条件：

  8. 单向函数不能用于加密。丹恒单向陷门函数对于不知道陷门的人表现出单向函数的特性，可以用于加密。因此设计公钥密码体制变成了寻找单向陷门函数。公钥密码思想的首创者Diffie和Hellmen指出：计算复杂性中的NP完全问题可被用作设计公钥密码算法。

  9. 可提供单向函数的数学难题是：

    • 大整数分解问题：RSA
    • 有限域的离散对数问题：DH协议
    • 椭圆曲线上的离散对数问题：SM2

9.2 RSA公钥算法

  1. RSA是一种分组加密算法，明文和密文在0到n-1之间，n是一个正整数，公钥为(e,n)，私钥为(d,n)

  2. 算法的数学基础是初等数论中的Euler(欧拉)定理，并建立在大整数因子分解的困难性之上

  3. 其中包括三个算法：密钥生成算法、加密算法、解密算法

  4. 密钥生成算法：

    两个不同但是大小相近的大素数p和q，n=pq，整数e满足 ，计算d满足 。则 为公钥， 为私钥。

  5. 加密算法：

    将明文M分组，使得每组的内容十进制数小于n，即分组长度小于（小于比n小的2的最大次幂）（分组大小，满足），对每组明文做运算：

  6. 解密算法：

  7. 算法的正确性证明

  8. RSA的安全性是基于加密函数是一个陷门单向函数，陷门是分解，进而用欧式法则求出私钥d。

  9. 优点：第一个能同时用于加密和数字签名的算法，也易于理解和操作；符合计算机网络的环境；对于大量用户，可以将加密密钥用电话簿的方式印出。

  10. 缺点：产生密钥很麻烦；分组长度太大，运算代价很高，尤其是速度较慢。

9.3 RSA中的计算问题

  1. 快速模幂算法

平方和乘法将计算的模乘法数目缩小到至多，为c的二进制表示的比特数

如n以二进制表示有k比特，即，则有

因此计算可以在时间内完成。

为了提高加密速度，e可以取特定的小整数，如，或者3。但是RSA也是无法达到对称密钥的运行速度。具体应用中将RSA算法更多地用于密钥的安全传输过程，而在针对具体传输信息 的加密与解密中依靠对称密钥算法，这样便能够增进密码系统的运行速度。

  1. 解密的快速实现

  2. 密钥生成

    采用概率素数判定测试(如：Miller Rabin)找到可使用的p和q

9.4 RSA的安全性分析

  1. p和q大约是100位的十进制数，n长度不少于512比特

  2. 要很大，且pq的长度相同

  3. p和q最好位强素数：

    强素数需满足：p-1也有大的素数因子r，p+1也有大的素数因子，r-1仍有大的素数因子

9.4.1 因式分解攻击

  1. 有三种途径：分解n；能计算出；能直接确定d
  2. 转移到2048位的RSA、Diffie-Hellman或DSA密钥

9.4.2 参数选取不当造成的攻击

  1. 要很大
  2. 如果小，则也小，此时稍大于n，即稍大于
  3. 顺序检查大于的每一个数x，找到某个x使得可以被开方为y，则

9.4.3 选择密文攻击

  1. RSA算法有同态的特点：
  3. RSA最优非对称加密填充（RSA-OAEP）可抗击适应性选择密文攻击。

9.4.4 共模攻击

  1. 不同用户之间不要共享整数n

  2. 若一个用户有一个模数n，而拥有多组不同的e和d。若存在同一信息P分别用不同的公钥加密，若e1和e2恰好互质（存在），则可以得到P：

9.4.5 小指数攻击

9.4.6 解密密钥的安全

  1. 在私钥d被泄露的情况下，整数n也不再安全，重新选择e也无法保证安全性，必须重新选择n。
  2. 计算解密密钥d的难度并不小于对整数n进行素因子分解的难度。
  3. 如果获得一个 的非平凡平方根，则可以在多项式时间内完成对n的分解。

10. 其他密码体制

10.1 Rabin密码体制

  1. Rabin密码体制已被证明对该体制的破译与分解大整数是等价的

  2. 不以一一对应的单向陷门函数为基础，对同一密文，可能有两个以上对应的明文

  3. 密钥生成算法：

    选择两个大素数pq满足，计算

    n为公钥，p,q为私钥

  4. 加密：

  5. 解密：求解 ，由CRT知该方程等价于解方程组： 由于 ，方程组的解容易得出，每个方程都由两个解。因此可以得到四个可能的解，即每一密文对应的明文不惟一。

    为了有效确定明文，可在m中加入某些双方商定的信息，如日期、发送者的ID等。

  6. 例题：

10.2 Diffie-Hellman密钥交换

  1. Diffie-Hellman算法可以用于密钥分配，但是不能用于加密或解密信息。

  2. 安全性依赖于有限域上计算离散对数非常困难。

  3. 算法流程：

    1. AB协商一个大素数p和本原根a，a和p公开
    2. A产生随机数x，计算，X发给B
    3. B产生随机数y，计算，Y发给A
    4. A计算
    5. B计算

  4. Diffie-Hellman密钥交换容易受到中间人攻击，原因是Diffie-Hellman密钥交换不认证对方。

  5. 改进的Diffie-Hellman密钥交换算法：

  6. 非交互双方密钥协商协议

    • 有一组用户，每个用户都产生一个长期密钥Xi，并计算公开的Yi
    • 全局g和a
    • 任何用户都可以访问该用户的公开值，计算密钥，用密钥对消息加密后发送给A
    • 优点：若该中心目录是可信的，则这种形式的通信既可保证保密性（只有i和j可以确定密钥，所有其他用户均不能读取该消息），又可保证某种程度的真实性（接收方i知道只有用户j能用该密钥产生消息）。

  7. 多方的Diffie-Hellman：

10.3 ElGamal密码体制

  1. 双钥密码体制，用于加密和签名

  2. 安全性基于求解离散对数问题的困难性。

  3. 密钥生成算法：

    1. 选取一个足够大的素数q，在上选取一个本原元a
    2. 随机选取一个整数 ，并计算
    3. 公钥为 ，私钥为

  4. 加密：

    1. 消息 。以分组密码序列的方式来发送信息，每个分组的信息大小不超过q。

    2. 选择任意整数

    3. 一次性密钥

    4. 得到密文对：

  5. 解密： 推导过程：

  6. 例题：

  7. 密文由明文和所选随机数来确定，因而是非确定性加密，或称为随机化加密。

  8. 如果信息必须分组然后以加密的密钥序列发送，那么每一个分块要有唯一的k。如果k用于多个分块。利用信息的分块M1，攻击者会计算出其他块。

    方法：两个C2和做比，K被约掉。

10.4 ECC

10.4.1 椭圆曲线密码简介

  1. 基于椭圆曲线数学的一种公钥密码的方法。
  2. 椭圆曲线上的公钥密码体制的优点：速度快、密钥短、存储空间和传输带宽占用较少，安全性高，灵活性好。
  3. 基于椭圆曲线离散对数问题的困难性。
  4. 国家标准与技术局和ANSI X9已经设定了最小密钥长度的要求，RSA和DSA是1024位，ECC是160位，相应的对称分组密码的密钥长度是80位。

10.4.2 实域R上的椭圆曲线

  1. 无穷远点：平行线交于无穷远点，则平面上所有直线都有唯一的交点

  2. 椭圆曲线为曲线 上的点，外加无穷远点

    其中参数ab满足 ，则椭圆曲线构成一个群，并定义加法运算

  3. 如果椭圆曲线上的三个点位于同一直线上，那么它们的和为无穷远点（零点）。

    其中O为加法的单位元。，则负元定义为：

  4. 点Q的倍点：做Q的切线，与椭圆曲线交于点S，

10.4.3 Zp上的椭圆曲线

  1. 定义： 曲线所有的解(x,y)，连同无穷远点定义为Zp上的一个椭圆曲线，记为

  2. 上的椭圆曲线点加公式： 其中：

10.4.4 GF(2^m)上的椭圆曲线

  1. 方程为：

  2. 使用生成元

10.4.5 椭圆曲线密码体制

  1. 椭圆曲线密码体制(ECC)，其依据是定义在椭圆曲线点群上的离散对数问题的难解性。

  2. ，且P的阶很大（，t很大）。取，则的求解是难处理的。

  3. 一般数域上的离散对数问题（以及大数分解问题）存在亚指数级时间复杂度求解算法，而ECDLP只有纯指数算法。

  4. 用椭圆曲线实现Diffie-Hellman密钥交换

  5. 用椭圆曲线实现ElGamal密码体制

  6. 例题：

  7. ECC技术要求：

    1. p越大越安全，但是会变慢，200bit左右即可
    2. G是基点，n是G的阶，n应该为质数
    3. h是椭圆曲线上所有点的个数m与n相除的商的整数部分，

  8. 优点;

    1. 安全性高
    2. 密钥量小
    3. 灵活性好
    4. 速度快
    5. 适合嵌入式设备

11. 密码学Hash函数

11.1 密码学hash函数的应用

  1. 哈希函数用于将任意长的消息映射为较短的、固定长度的一个值。对于大的输入集合使用该函数，输出结果应该分布均匀且看起来随机。

  2. Hash函数首要目标是保证数据的完整性，对于任何一位或几位的改变都将极大可能改变其hash码。

  3. 散列函数是一种单向密码体制，即它从明文到密文是不可逆映射，并且找到两个不同的数据块对应相同的Hash值在计算上不可行。

  4. MD系列：1978年，Merkle和Damagad设计MD迭代结构。

    SHA系列：SHA1、SHA2都是迭代结构。Keccak被选为SHA-3，采用了创新的“海绵引擎”散列消息文本。

    国密：SM3，采用MD结构，输出值为256比特。

  5. 哈希函数在密码学中的应用：消息认证码、谁在前面、伪随机数发生器、一次性口令

    在区块链中的应用：快速验证、防止篡改、POW工作量证明

  6. 消息认证：

    • 是验证消息完整性的一种服务。确保受到的数据不变且发送方的身份有效。
    • 方法1：AB共享一个密钥，消息与其杂凑码链接后用单钥加密算法加密
    • 方法2：用单钥加密算法仅对杂凑码加密，这种方式用于不要求保密性的情况下，可减少处理负担
    • 方法3：AB共享一个秘密值S，A计算消息和秘密值链接在一起的杂凑值，并将此杂凑值附加到消息后发往B
    • 方法4：在上一种方式的基础上，在消息与杂凑值链接以后再增加单钥加密运算
    • 方法5：用公钥加密算法，将消息和用发送方的密钥签名消息的杂凑码连接在一起
    • 方法6：方法5之后再使用单钥加密算法加密。这种方式提供了保密性和数字签名

  7. 数字签名：

    • 使用用户的私钥加密消息的Hash值，其它任何知道该用户公钥的人通过数字签名验证消息的完整性。
    • 可以减少签名长度，提高签名速度；可以不泄露签名对应的信息。

11.2 安全性需求

  1. Hash函数安全性条件：伪随机性:映射分布均匀性和差分分布均匀性

    使输入中每一个比特的信息，尽量均匀地反映到输出的每一个比特上去

    输出中的每一个比特，都是输入中尽可能多比特的信息一起作用的结果

    01个数大致相等、雪崩效应、1个变化一半以上变化

  2. 杂凑函数的攻击：伪造消息，使其与原来消息的杂凑码相同

  3. 攻击方法：穷举攻击（原像攻击和第二原像攻击、碰撞攻击）、算法分析

  4. 评价hash算法抗密码分析能力的方法是：与穷举攻击所需的代价相比，理想的hash函数算法要求密码分析攻击所需代价大于或等于穷举攻击所需代价。

  5. 穷举攻击：不依赖于任何算法细节，仅与Hash值长度有关，包括

    1. 原像攻击和第二原像攻击：给定hash，找到这个杂凑值的消息。攻击规模是，平均尝试次
    2. 碰撞攻击：找到两个信息满足哈希值相等。两种常用的攻击方法：生日攻击法和中点交会攻击法。

  6. 第一类生日攻击：

    • 问题：H有n个可能的输出， 是一个特定的输出，对H取k个输入，至少有一个输入y使得时，k有多大？
    • y取k个随机值得到函数的k个输出中至少有一个等于H(x)的概率为：。若概率等于0.5，则。当输出长为m比特时，

  7. 第二类生日攻击：

    • 寻找函数H的具有相同输出的两个任意输入
    • 设哈希函数输出长度为m比特，H的k个随机输入中至少有两个产生相同输出的概率大于0.5，则：

11.3 迭代型哈希函数

  1. 输入消息M分为L个长度为b位的分组（），若不能正好分组，需要填充到b的整数倍位。f为压缩函数。

  2. Hash函数的一般结构为：

  1. 迭代技术（压缩函数f）：

  2. 由于函数的输入包含了长度，所以攻击者必须：找出具有相同的Hash值且长度相等的两条消息，或者长度不等但是加入消息长度后Hash相同的消息，增加了攻击的难度。

  3. Merkle和Damgard已经证明：如果压缩函数是无碰撞的，则上述方法得到的Hash函数也是无碰撞的。因此Hash函数的核心是设计无碰撞的压缩函数f，要求找出f的碰撞在计算上是不可行的。

11.3.1 MD5

  1. 迭代型散列函数

  2. 输入：任意长度。分组：512比特。输出：128比特。

  3. 算法步骤：

    1. 填充，填充的第一位是1，其余为0。填充到比512的倍数少64位（），原始已经满足长度要求的数据也需要填充。

    2. 附加消息长度：将原始消息长度用64位表示，先填充低32位，后填充高32位。长度超过64位的取低64位。经过1、2步预处理后，消息长度为512的倍数，分组：

    3. 初始化缓冲区：中间结果和最终结果都保存在128位的缓冲区里。缓冲区用4个32位寄存器表示。对4个缓冲区附初始值，并以小端格式存储。

    4. 以512位的分组为单位处理消息：迭代执行压缩函数：

      由四轮组成，每轮中对四个缓冲区进行16次迭代，每步迭代中使用当前512比特分组中的一个字（32比特）。

      每轮中使用当前分组的16个字的顺序不一样。每轮中使用的逻辑函数g执行的位运算也不同。常数表的作用是“随机化”32位的输入数据，消除输入数据的规律性。循环左移的值与迭代的部步数和轮数都有关。加法是模