密码学期末复习（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位的输入数据，消除输入数据的规律性。循环左移的值与迭代的部步数和轮数都有关。加法是模相加。

    5. 输出：第L个分组处理后就是x的散列值。

  4. 安全性：MD5杂凑码中输出的每一比特是所有输入比特的函数，因此获得了很好的扩散效果。

  5. 从穷举搜索的角度，第二类生日攻击需要进行次运算，因此认为MD5容易受到第二类生日攻击。

11.3.2 SHA-1

  1. 迭代型哈希函数

  2. 输入：长度小于的消息。分组大小：512比特。输出：160比特。

  3. 算法步骤：

    1. 填充，与MD5相同

    2. 附加消息长度：用64位表示长度，并以大端存储的方式附加在后面

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

    4. 以512位分组为单位处理消息：压缩函数：

      共四轮处理，每轮20次迭代。

      分组中前16个字直接使用，后面使用计算，输入分组的16个字扩展成80个字以供压缩函数使用。基本逻辑函数执行位运算，每轮不同。加法是模相加。

    5. 输出

  4. 安全性：SHA1抗穷举攻击的能力比MD5强，并且抗密码分析的能力不弱。

11.3.3 SM3

  1. 迭代型哈希结构
  2. 分组长度：512位。输出长度：256位。
  3. 算法步骤：
    1. 填充：填充到512位的倍数，方法与MD5一样。
    2. 消息扩展：对每个分组产生132个消息字，每个消息字长32位。
    3. 迭代压缩：使用消息字进行迭代。
    4. 输出

11.4 海绵结构：SHA-3

  1. SHA-3 第三代安全散列算法，之前名为Keccak算法。
  2. 海绵函数允许输入长度和输出长度可变。
  3. 海绵结构包括两个阶段：吸水阶段和挤压阶段。
  4. 算法流程：
    1. 填充：消息n位，被分为k个长r的分组
    2. 对长度b=r+c的状态变量s进行操作，初值设为0，在迭代中更新。默认下c=1024, r=576
    3. 吸水阶段：填充c个零，将输入从r位扩展到b位；扩展后与s进行运算，作为迭代函数f的输入，输入结果为s的新值
    4. 挤压阶段：每轮迭代中s的前r位保留作为输出分组Zi
    5. 输出：输出数据块的个数j由需要输出的位数l决定：

11.5 基于分组密码的Hash函数

  1. CBC和CFB工作模式的特点：一个明文块的改变，在加密时会引起相应的密文块及其后的所有密文块改变。因此可利用分组密码的CBC和CFB工作模式构造Hash函数。
  2. 构造方式：
    1. 链接变量作为密钥：上一轮的输出作为下一轮的密钥
    2. 基于密码分组链接(CBC)工作模式：上一轮的输出与下一组消息异或，然后被加密
    3. 基于密码反馈(CFB)工作模式：上一轮的输出在下一轮中被加密，解密结果与这组消息进行异或
  3. 基于分组密码CBC和CFB工作模式的Hash函数中的密钥k：
    • 若k保密，则是带密钥的Hash函数，常用于产生MAC，用于保证消息的完整性。
    • 若k公开，则此类Hash函数是不安全的，甚至不是弱无碰撞。

11.6 基于离散对数的Hash函数

Chaum-Heijst-Pfitzmann Hash函数：

  1. 基于离散对数问题，可以证明是安全的

  2. p是一个大素数，是一个素数，a和b是Zp的两个本原元。定义hash函数为：

  3. Chaum-Heijst-Pfitzmann Hash函数是强抗碰撞的。

    证明：用反证法。若Hash函数h有一对碰撞，则可证明离散对数能被有效计算。

12. 消息认证码

12.1 对消息认证的要求

验证的内容包括：

  1. 所收到的消息确实来自真正的发送方
  2. 消息没有被修改
  3. 也可以验证消息的顺序和及时性

12.2 消息认证函数

  1. 认证符的产生有三类：
    1. 哈希函数：消息映射为定长的哈希值，以哈希值作为认证符
    2. 消息加密：对整个消息加密后的密文作为认证符
    3. 消息认证码：是消息和密钥的函数，产生定长的值
  2. 利用对称密码进行认证：
    • 发送端：将明文消息M作为某个函数F的输入，产生帧校验序列（FCS），M和FCS连接到一起后进行加密
    • 接收端：解密，重新利用F函数计算M的FCS，如果计算得到和收到的FCS相等，则认为消息是真实的
  3. 公钥加密：先签名再加密：提供保密性和认证性
  4. 消息认证码MAC：是指消息被一密钥控制的公开函数作用后产生的、用作认证符的、固定长度的数值。。
  5. MAC是实现有效、安全可靠数字签字和认证的重要工具，是安全认证协议中的重要模块。
  6. MAC算法不要求可逆性，想是带有密钥的Hash函数。但是也不是加密函数，因为MAC算法不要求可逆性，与加密函数相比，MAC函数更不容易被攻破。

12.3 MAC的安全性

  1. 攻击目的：

    • 伪造攻击：攻击者在没有密钥的情况下，伪造一个未经认证的对
    • 密钥恢复攻击：攻击者通过分析一系列消息、认证码对，找到控制密钥

  2. 伪造攻击

  3. 密钥恢复攻击：考虑敌手使用穷搜索攻击获取密钥

    • 密钥有种，MAC值有种，，敌手知道多对信息和其认证码
    • 第一轮：对于，穷举所有的密钥，由于密钥数多于MAC值的取值，因此有个密钥可能是正确的
    • 第二轮：对于，在上述密钥中遍历，找到也满足这个式子的密钥值，得到个密钥可能是正确的
    • 不断重复：，则平均需要a轮
    • 因此消息认证码的穷攻击比对使用相同长度密钥的加密算法的穷搜索攻击代价更大。

  4. 穷举攻击中，攻击者有通过攻击密钥空间和攻击MAC值两种办法

    • 攻击密钥空间：

      密钥长k位，对所有可能的密钥进行计算，至少有一个密钥会产生正确的MAC，代价为

      根据上述的密钥恢复攻击，可知存在一些不是正确密钥的密钥也会导致某个信息的认证码是相同的，因此需要不断重复，使用别的消息进行检查。可以证明，检查这些消息总的代价是：

    • 攻击MAC值：

      目的是对给定的消息产生其有效的MAC或者对给定的MAC产生其给定的消息

      与攻击具有单向性或抗弱碰撞能力的Hash码所需的代价相同，代价为

      这种攻击方式不能离线进行

  5. MAC的构造：

    1. 用hash函数构造MAC
    2. 用分组密码构造MAC
    3. 用伪随机算法构造MAC

12.4 基础Hash函数的MAC：HMAC

  1. HMAC能提供：

    1. 消息完整性认证
    2. 信源身份认证

  2. HMAC的设计目标：

    1. 可以不经修改直接使用现有的哈希函数
    2. 镶嵌的哈希函数可以方便的被替换
    3. 保持镶嵌的散列函数的最初性能，不因用于HMAC而使其性能降低
    4. 以简单的方式处理密钥
    5. 在对镶嵌的散列函数合理假设的基础上，易于分析HMAC用于认证时的密码强度 -> 是HMAC优于其他基于散列函数的MAC的一个主要方面，HMAC在其镶嵌的散列函数具有合理密码强度的假设下，可证明是安全的。

  3. 算法描述： L：M消息分组数，b：一个分组中的比特长度，n：哈希函数的输出长度

    1. K密钥长度左边填充0到b比特长，如果K的长度大于b，则先对K进行哈希后填充。得到K'
    2. K'与ipad异或，后面链接M的分组
    3. 哈希上面的所有分组
    4. K'与opad异或，将上一步的哈希链接在异或值后
    5. 进行hash，输出值为HMAC

  4. HMAC的有效实现：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    def sha1_hmac(key, message: bytes):
        # 将密钥和消息分别进行填充
        if len(key) > 64:
            key = sha1(key)
        key += b'\x00' * (64 - len(key))
        ipad = b'\x36' * 64
        opad = b'\x5c' * 64
        # 图中虚线的部分可以提前计算，用于作为散列函数的初值IV
        k_ipad = bytes([x ^ y for x, y in zip(key, ipad)])
        k_opad = bytes([x ^ y for x, y in zip(key, opad)])

        # 计算HMAC-SHA1值
        inner_hash = sha1(k_ipad + message)
        outer_hash = sha1(k_opad + inner_hash)

        return outer_hash

  5. HMAC的安全性

    1. HMAC的安全取决于镶嵌的哈希函数的安全性。
    2. 证明了对HMAC的攻击等价于对内嵌散列函数的下述两种攻击之一：
      1. 攻击者能够计算压缩函数的一个输出，即使IV是随机的和秘密的。
      2. 攻击者能够找出散列函数的碰撞，即使IV是随机的和秘密的。

13. 数字签名

13.1 数字签名的基本概念

  1. 数字签名主要用于对数字消息进行签名，以防消息的冒名伪造或篡改，也可用于通信双方的身份鉴别。

  2. 需要具有可验证性和不可伪造性。

  3. 数字签名的主要功能：

    1. 确认信息是由签名者发送的
    2. 确认消息自签名后到收到为止，未被修改过
    3. 签名者无法否认签名是由自己发送的

  4. 一个数字签名包含三部分：密钥生成、签名算法、验证算法

  5. 数字签名的安全性：

    四类攻击目标从前至后难度依次递减：

    四类攻击能力从前至后逐渐增强：

  6. 数字签名的解决方案：

  7. 数字签名方案的分类：

13.2 常见的数字签名方案

13.2.1 ElGamal签名

  1. 随机数k不能泄露且不能被重复使用，否则x有可能被算出
  2. 存在ElGamal数字签名的变形在某些假设下，能被证明在选择消息攻击下是安全的

13.2.2 Schnorr数字签名

Schnorr数字签名方案的安全性分析

  1. ElGamal系统中是中的本原元，而Schnorr中不是。因此ElGamal的安全性更高，因为 的阶更高。
  2. Schnorr系统的签名文较短，e的长度由函数h决定
  3. Schnorr首先提出可以提前计算，因此实现过程更快

13.2.3 ECDSA

13.2.4 SM2

椭圆曲线：

  1. 验证算法的特点：加入了较多的检错功能，防止信道干扰和对手的篡改。
  2. 目前尚没有发现求解椭圆曲线离散对数问题的亚指数算法。
  3. 软硬件实现规模小，容易实现160位的椭圆曲线密码的安全性，相当于1024位的 RSA密码。目前最大的应用是二代身份证。

14. 密钥的管理和分发

14.1 密钥管理

  1. 密钥管理原则：
    1. 攻击者无法窃取
    2. 即使窃取到了也无法使用（超过使用时间和范围限制）
    3. 密钥的分配和更新对用户透明
  2. 密钥产生：
    1. 长度应该足够
    2. 密钥生成算法要足够安全：密钥生成算法的安全性不应低于密码算法的安全性
    3. 避免使用弱密钥，应使用长密钥
  3. 密钥生成算法：
    1. 非线性密钥空间：算法生成的密钥的强度不一致
    2. 线性密钥空间：密钥强度一致
  4. 防止我方黑盒密码设备被敌方利用：
    • 密钥分为前后两部分，前一部分是密钥，后一部分是一个固定值用该密钥加密后得到的字符串
    • 设备执行时，先解密后面的字符串，若匹配则正常。若不匹配，使用另外一个弱算法。
    • 密钥128位，识别串64位，随机选取一个得到好密钥的概率是
  5. 密钥验证：确认来自正确的人；确认密钥没有传输错误（附带一个用该密钥加密的密文）
  6. 密钥更新：用旧密钥计算、用旧密钥协商，新密钥的安全性不会超过旧密钥。重新认证身份并分发密钥。旧密钥必须销毁。

14.2 基于对称加密的对称密钥分发

  1. 两个用户使用单钥密钥体制的时候，必须先共享一个密钥，还需要经常更新密钥。

  2. 密码系统的强度也依赖于密钥分配技术。

  3. 密钥分配的基本方法：

    1. 密钥由A选取并通过物理手段发送给B

    2. 密钥由第三方选取并通过物理手段发送给AB

    3. 如果AB事先已有一密钥，则其中一方选取新密钥后，用已有的密钥加密新密钥并发送给另一方。

      缺点：攻击者一旦获得一个密钥就可获取以后所有的密钥，同时用这种方法对所有用户分配初始密钥时，代价仍然很大。

    4. 如果AB与第三方分别有一保密信道，则第三方选取密钥后，分别在两个保密信道上发送给AB

  4. 第四种方法比较常用，其中的第三方通常是一个负责为用户分配密钥的密钥分配中心(KDC)。这时每一用户必须和密钥分配中心有一个共享密钥，称为主密钥。通过主密钥分配给一对用户的密钥称为会话密钥，通信完成后，会话密钥即被销毁。主密钥可通过物理手段发送。

  5. 密钥分配的具体过程：

    1. A向KDC发送 Request 和 N1（这次业务的唯一标识符，是一个随机数，防止重放和篡改）

    2. KDA返回一个由（A保存的主密钥的）加密的信息，保证只有A能解密。解密信息包括：，Request，N1，

    3. A得到会话密钥。并向B转发最后一项的内容。由于最后一项是由B的主密钥加密的，因此只有B可以解密。并且可以获取会话密钥和对话的另一方的ID

    4. B用会话密钥加密一个随机数N2发给A

    5. A以f(N2)返回作为对B的应答，f函数可以是对N2加一等操作。

      45两步可以让B相信第三步收到的消息不是一个重放。第三步已经完成了密钥分配，45两步还完成了认证的功能。

  6. 密钥的分层控制：

    • 网络中如果用户数目非常多且分布的地域非常广，则需要使用多个KDC的分层结构
    • 分层结构可减少主密钥的分布，还可将虚假KDC的危害限制到一个局部区域，但会降低信任度

  7. 分布式密钥控制：

    • 在上述方法中需要所有用户都信任KDC，还需要对KDC加以保护。如果密钥分配是无中心的，则可以不需要KDC，但是主密钥多达个。
    • 在整个网络的局部范围却非常有用

  8. 密钥的控制使用：

    • 主密钥：密钥加密密钥。会话密钥：数据加密密钥。
    • 如果主密钥泄露了，则相应的会话密钥也将泄露，因此主密钥的安全性应高于会话密钥的安全性。

  9. 会话密钥的有效期：

    • 会话密钥更换得越频繁，系统的安全性就越高。
    • 会话密钥更换得太频繁，又将延迟用户之间的交换。

14.3 基于非对称加密的对称密钥分发

  1. 公钥用于分配单钥密码体制的密钥非常合适。

  2. 简单分配流程：

    公钥缺少证书管理机构认证且非物理传输中容易受到中间人攻击。

  3. 具有保密性和认证性的密钥分配：

    1. 假定AB双方已完成公钥交换，则可按以下步骤建立共享会话密钥：

14.4 公钥分发

  1. 公开发布

  2. 公用目录表

  3. 公钥授权

    • 优点：每次密钥的获得由公钥管理机构查询并认证发送，用户不需要查表，提高了安全性
    • 缺点：公钥管理机构必须一直在线，由于每一用户要想和他人联系都需求助于管理机构，所以管理机构有可能成为系统的瓶颈。由管理机构维护的公钥目录表也易被敌手通过一定方式窜扰。

  4. 公钥证书

    • 用户通过公钥证书来互相交换自己的公钥而无须与公钥管理机构联系
    • 公钥证书由证书管理机构CA(certificate authority)为用户建立
    • A 将自己的公钥发给CA，CA返回A的公钥证书

  5. X.509认证服务

    1. 证书机构Y颁发给用户A的证书表示为：。

      V是版本号，SN是证书序号，AI是证书算法标识，CA是发行者，TA是有效期，A是用户信息，AP是A的公钥

    2. 任何可以访问CA的用户都可以得到一个证书，只有CA可以修改证书。由于证书用CA的私钥签名，不能伪造，因此可以放在一个公共目录中。

    3. 不共享同一CA的用户获得证书：

      两个CA之间已经交换了公开密钥，含有对方的证书。则A可以先读取，获取X2的公钥后，在读取，读取B的公钥。

      这个证书链可以表示为：

    4. 证书的撤销：每一个证书都具有一个有效期，有效期结束时证书将自动撤销。也可以在有效期结束前撤销。为了有效的管理证书的撤销，CA会维护一个证书撤销列表CRL。当用户获取一个证书时，应检查CA的CRL，判断该证书是否已被撤销。

14.5 公钥基础设施（PKI）

  1. 为管理公钥（生成、认证、存储、安装），须建立一套公钥基础设施（PKI，Public Key Infrastructure），PKI的基本组成元素是证书颁发机构（CA，Certificate Authority）。
  2. PKI主要完成的工作为：
    1. 为用户生成一对密钥（公开密钥，私有密钥），并通过一定的途径分发给用户。
    2. CA为用户签发数字证书，形成用户的公开密钥信息，并通过一定的途径分发给用户。
    3. 对用户证书的有效性进行验证。
    4. 对用户的数字证书进行管理。这些管理包括有效证书的公布、撤销证书的公布、证书归档等。
  3. PKI包含五个关键元素：
    1. 端实体：一个在公钥数字证书作用范围中被认证的实体。
    2. 签证机构CA：证书和证书撤销列表的发行人。
    3. 注册机构RA：可选元素，承担一些签证机构（CA）的管理任务。
    4. 证书撤销列表发布点：可选元素，CA可通过它来发布证书撤销列表（CRL）。
    5. 证书存取库：必备元素，提供存取数字证书和证书撤销列表的方法。
#密码学 #期末复习 #大二下
密码学期末复习（PPT）
https://harrison-1eo.github.io/2023/06/04/密码学期末复习/
作者
Harrison
发布于
2023年6月4日
更新于
2023年12月19日
许可协议