密码学基础笔记(二)

第三章 分组密码和数据加密标准（DES）

流密码与分组密码

分组密码：

所谓分组密码是将明文分成一组一组，在密钥的控制下，经过加密变换生成一组一组的密文。

​ Step 1：将明文消息序列m1, m2, …, mi, …划分成等长的消息组（m1, …, mn），（mn+1, …, m2n），…

​ Step 2：在密钥k=k1, k2, …, kn的控制下按固定的加密算法一组一组进行加密。

​ Step 3：最后输出一组一组密文（c1, c2, …, cl），（cl+1, cl+2, …, c2l）。

在相同密钥下，分组密码对每组明文所进行的变换是一样的，因此只需要研究对单独一组明文进行加密变换。

Feistel密码

Feistel建议使用乘积密码的概念来逼近理想分组密码。乘积密码是指依次使用两个或两个以上基本密码，所得结果的密码强度将强于所有单个密码的强度。

C=Enckn(...Enck2(Enck1(m))…)

Feistel密码：

  • 代替：每个明文元素或元素组被唯一地替换为相应的密文元素或元素组。

  • 置换：明文元素的序列被替换为该序列的一个置换。也就是说，序列里没有元素被添加，删除或替换，但序列里出现的顺序改变了。

  • 扩散：将明文的统计特性散布到密文中去，这可以通过让每个明文数字尽可能地影响多个密文数字。

  • 混淆：使密文和密钥之间的统计关系尽可能复杂，以使敌手无法得到密钥。

  • 分组长度: 分组越大则安全性越高，但加密速度就越慢。设计中最为普遍使用的是64比特。

  • 密钥长度：密钥越长则安全性越高，但加密速度就越慢。现在普遍认为64比特或更短的密钥长度是不安全的，通常使用128比特的密钥长度。

  • 迭代轮数：单轮结构远不足以保证安全性，但多轮结构可提供足够的安全性。典型地，轮数取为16。
  • 子密钥产生算法：该算法的复杂性越大，则密码分析的困难性就越大。
  • 轮函数F：轮函数的复杂性越大，密码分析的困难性也越大。
  • 快速软件加/解密：许多情况下，算法是被镶嵌在应用程序中，因而无法用硬件实现。此时算法的执行速度是考虑的关键。
  • 简化分析难度：如果算法能被无疑义地解释清楚，就可容易地分析算法抵抗攻击的能力，有助于设计高强度的算法。

数据加密标准（DES）

在2001年高级加密标准（AES）提出前，DES一直是使用最广泛的加密方案。

  • 分组长度为64比特，密钥长度为56比特。

  • DES在1975年3月17日首次被公布在联邦记录中，经过大量的公开讨论后，DES于1977年1月15日被正式批准并作为美国联邦信息处理标准。

  • 规定每隔5年由美国国家保密局作出评估，并重新批准它是否继续作为联邦加密标准。

DES加密算法概述：

  • DES的结构是典型的Feistel密码结构。
  • 明文分组长度为64bit。
  • 密文分组长度为64bit。
  • 初始密钥长度为64bit。（其中，第8、16、24、32、40、48、56、64为奇偶校验位，因此，实际的密钥长为56bit。）

DES加密过程：

  1. 初始置换IP：重排明文分组的64 bit数据。
  2. 具有相同功能的16轮迭代：每轮中都有置换和代换运算，第16轮变换的输出分为左右两半，并交换次序。
  3. 逆初始置换IP-1（IP的逆）：产生64 bit的密文。

子密钥Ki的生成：

  1. 初始密钥K为64 bit，首先置换选择PC1置换。
  2. 将置换后的56 bit分为各28 bit的左、右两半，分别记为C0和D0。在第i轮分别对Ci-1和Di-1进行循环左移，移位后的结果作为求下一轮子密钥的输入，同时也作为置换选择PC2的输入。
  3. 通过置换选择PC2产生的48 bit的Ki，即为i轮的子密钥，作为轮函数f (Ri-1, Ki)的输入。

S盒代换：

DES算法中除了S盒是非线性变换外，其余变换均为线性变换，S盒是经过精心设计和严格挑选的。

DES算法保密的关键在于S盒！

DES的解密过程：

  • DES的加密算法具有可逆性，解密64 bit密文消息分组使用与加密相同的算法，所不同的是子密钥顺序使用相反，依次为 K16, K15, …, K1。
  • 当64 bit密文作为明文输入时，解密过程的第1轮迭代使用子密钥K16，第2轮迭代使用子密钥K15，…，第16轮迭代使用子密钥K1，结果输出得到64 bit明文。

56位密钥的使用：

在DES成为标准时，采用的密钥是56 bit，其密钥量仅为256约为1017个，难以抵抗穷举搜索攻击。

问题主要集中在算法中的8个S盒上。DES密码体制的安全性依赖于非线性的S盒。S盒设计的详细准则一直没有公开，致使许多密码学家怀疑S盒设计中可能包含陷门。

双重DES ：

针对DES有效密钥长度偏短等安全性问题，人们利用实现DES的现有软硬件，寻求使用DES的多重加密方案以增加密码体制的强度。实用中一般广泛采用的有二重和三重DES等几种形式。

第四章 数学基础（略）

第五章 AES

AES应用实例：

  • 路由器
  • 安卓
  • SIM卡

总体结构：

AES是一个迭代型分组密码：

  • 分组长度：可以独立地指定为128比特、192比特、256比特。
  • 密钥长度：可以独立地指定为128比特、192比特、256比特。

状态、种子密钥和轮数：

类似于明密文分组，算法的中间结果也分组，称中间结果的分组为状态，所有的操作都在状态上进行。

  • 状态可以用以字节为元素的矩阵表示，该矩阵有4行，列数记为Nb，Nb等于分组长度除以32。
  • 种子密钥也用一个以字节为元素的矩阵表示，该矩阵有4行，列数记为Nk，Nk等于分组长度除以32。

迭代的轮数记为Nr，Nr与Nb和Nk有关，Nr与Nb和Nk的关系如下表：

详细结构

当Nk等于4时，整个算法由10轮组成。每轮由4个变换模块组成，分别是：

  1. 字节代换（ByteSub）
  2. 行移位（ShiftRow）
  3. 列混合（MixColumn）
  4. 轮密钥加（AddRoundKey）

最后一轮略有不同，没有列混合。

加密过程：

  1. 初始轮密钥加
  2. Nr-1轮迭代
  3. 最后一轮变换

字节代替变换（ByteSub）

字节代换是非线形变换，独立地对状态的每个字节进行。代换表（即S-盒）是可逆的，由以下两个变换的合成得到：

  1. 首先，将字节看作GF(28)上的元素，映射到自己的乘法逆元，00映射到自己。
  2. 其次，对字节做如下的（GF(2)上的，可逆的）仿射变换：

行移位变换（ShiftRow）

状态矩阵State中的每一行将以字节为单位，循环左移不同的位移量。

  • 第一行：保持不变
  • 第二行：循环左移一个字节
  • 第三行：循环左移两个字节
  • 第四行：循环左移三个字节

列混合变换（MixColumn）

将State乘以一个固定的矩阵A。

轮密钥加变换（AddRoundKey）

密钥加是将轮密钥Ki简单地与状态State进行逐比特异或。

AES的密钥扩展

密钥扩展指从种子密钥得到轮密钥的过程，其基本原则如下：

  • 轮密钥的比特数等于分组长度乘以轮数加1：128 bit × (10+1) = 1408 bit
  • 种子密钥被扩展成为扩展密钥（密钥扩展）。
  • 轮密钥从扩展密钥中取，其中第1轮轮密钥取扩展密钥的前Nb个字，第2轮轮密钥取接下来的Nb个字，如此下去（轮密钥选取）。

密钥扩展算法

将种子密钥扩展为扩展密钥的计算过程如下：

当种子密钥长度为128bit时，Nk＝4：

temp = SubByte(RotByte(W[i-1])) Å Rcon[i/Nk]

  • RotByte( )：循环左移一个字节，如W=(a0, a1, a2, a3)，则RotByte(W)=(a1, a2, a3, a0)。
  • SubByte( )：S盒的字节代换。
  • Rcon[i]：轮常数

AES的解密过程

AES加密算法的每一步都可逆！

第6章 分组密码的工作模式

分组密码的工作模式：

为了能在各种应用场合使用DES，1980年，美国在FIPSPUS 81中标准化了DES算法的四种工作模式，后来对AES算法研发过程中，增加了新的工作模式，这些模式适用于任何分组密码算法。

五种常用的工作模式为:

1.电码本（Electronics Code Book，ECB）

2.密文分组链接（Cipher Block Chaining，CBC）

3.密文反馈（Cipher-FeedBack，CFB）

4.输出反馈（Output-FeedBack，OFB）

5.计数器（Counter，CTR）

为了方便描述，定义如下符号：

  • Ek：分组密码加密算法
  • M1, M2, …, Mn：明文消息中n个连续的分组
  • C1, C2, …, Cn：密文消息中n个连续的分组
  • IV：初始向量，是一个随机比特串
  • HSj(A)：A的j个最高有效位，例如HS8(0010101110100101)=00101011
  • LSj(A)：A中除了j个最高位外剩下的有效位，例如LS8(0010101110100101)=10100101
  • A||B：消息分组A和B的链接

电码本模式

电码本模式是分组密码的一个直接应用：它一次对一个明文分组Mi直接加密，每次的加密密钥k都相同。

当密钥k取定时，对明文的每一个分组Mi，都有一个惟一的密文分组Ci与之对应。ECB模式的加密过程为：

Ci=Ek(Mi)，i=1，2，…，n

  • ECB模式的优点：当改变一个明文分组值的时候，仅仅会引起相应的密文分组取值发生变化，而其他密文分组不受影响。

  • ECB模式的缺点：相同的明文分组会产生相同的密文分组，易暴露明文的固有格式。因此ECB不适用于长消息，建议在大多数情况下不要使用ECB模式进行加密操作。

密文分组链接模式

密码分组链接模式是用于普通数据加密的一种分组密码工作模式。CBC解决了ECB的安全缺陷，可以让重复的明文分组产生不同的密文分组。

C0=IV,
Ci=Ek(MiÅCi-1)，

i=1,2, …, n

  • CBC模式的优点：CBC模式输出的是随机化的密文分组，CBC模式适用于较长的明文消息进行加密。

  • CBC模式的缺点：当信道噪音等干扰带来密文传输错误时，密文中一位的错误将影响当前分组及下一分组的解密。

密文反馈模式

设传送的每个单元（如一个字符）是j比特长，通常取j=8。以IV作为初始的b比特随机输入分组，存放于移位寄存器中。

I1= IV Ii=LSj(Ii-1)||Ci-1 (i=2,3,…,n)

O1=Ek(I1) Oi=Ek(Ii) (i=2,3,…,n)

C1=M1ÅHSj(O1) Ci=MiÅHSj(Oi) (i=2,3,…,n)

  • CFB模式的优点：随机化密文。

  • CFB模式的缺点：当信道噪音等干扰带来密文传输错误时，密文中一位的错误将影响当前分组及下一分组的解密。

输出反馈模式

输出反馈模式在结构上类似于CFB模式，两种模式的不同之处在于：

  • OFB：将加密算法的输出反馈到移位寄存器

  • CFB：将密文单元反馈到移位寄存器

计数器模式

计数器模式要求计数器的长度与分组长度相同，它将计数器从初始值开始计数所得到的值作为分组加密算法的输入，经过加密算法变换后的结果与明文分组异或，得到密文分组。

Ci=MiÅE(Ctri)，i=1,2, …, n

  • CRT模式的优点：
    • 可以处理任意长度的数据，而且加密-解密过程仅涉及加密运算，不涉及解密运算，因此不用实现解密算法。
    • 能并行处理，即能同时对多个分组的加密-解密进行处理，而不必等到前面分组处理完才开始，而且可以提前进行预处理，这也可以极大地提高处理效率。
    • 可以随机地对任意一个密文分组进行解密，对该密文分组的处理与其他密文无关。

第七章 伪随机数的产生和流密码

随机数的使用

大量密码算法或网络安全协议都需要随机数，如：

  • 密钥分发和认证
  • 会话密钥的产生
  • RSA等公钥密码算法
  • 对称密码的密钥

现实中的随机数：

  • 手机动态验证码
  • 动态验证码
  • 密码器

随机数的使用

这些应用对随机数序列产生提出了两个不同的要求：随机性和不可预测性。

  • 随机性
    • 分布均匀性：能通过均匀性检验、独立性检验、游程检验等基本的统计特性检验。
    • 独立性：序列中任何子序列不能由其他子序列推导出。
  • 不可预测性
    • 指即使给出产生序列的硬件和所有以前产生的序列的全部知识，也不可能预测下一个随机位是什么。因此，随机序列是非周期的。

伪随机数发生器

  • 物理方法：利用自然界的一些真的随机物理量，如放射性衰变、宇宙射线的触发时间等。
  • 计算机产生（数学方法）：由一个初始状态（称为“种子”）开始，通过一个确定的算法来生成。一旦给定算法和种子值，输出序列就是确定的了，因此有一定的周期性，规律性和重复性，不是真正的随机数，通常称之为伪随机数。产生伪随机数的算法或硬件一般称为伪随机数发生器。

BBS发生器

BBS（Blum-Blum-Shub）产生器是可证明安全的伪随机比特序列产生器。

首先选择两个大素数p和q，满足

p ≡ q ≡ 3 (mod 4)

令n = pq。再选一随机数s，使得s与n互素。

BBS产生器产生伪随机序列的算法如下：

​ X0 = s2 mod n

​ for i = 1 to ∞ do {

​ Xi = X2i-1 mod n;

​ R

i

= X

i

mod 2 }

流密码

流密码结构图：

RC4算法

RC4是MIT的Rivest开发的，是使用最为广泛的流密码算法之一。

  • RC4的大小由参数n确定。对于一个n位长的字（或0, 1 序列），有2n种不同的排列方式，对应2n个不同的元素（或状态），这些元素组成一个长为2n的数组S。
  • RC4每次随机选取数组S中的一个元素输出作为密钥k。

RC4包含了两个算法：

1.密钥调度算法（Key Scheduling Algorithm, KSA）：设置数组S的初始排序。

2.伪随机生成算法（Pseud Random Generation Algorithm, PRGA）：随机选取元素作为密钥k输出并修改数组S的原始排序，每产生一个密钥k，数组S就被重新排列一次。

KSA算法：

  • 常用的RC4的n=8，此时，RC4可以生成28=256个元素的数组S。KSA初始化S，取

S[i]=i (i=0, 1, …, 255)

  • 选择0到255之间的一个子序列作为密钥，填充到密钥数组K[i]=i(i=0, 1, …, 255)中。填充时，这个密钥不断地重复直到填满整个密钥数组。

  • 然后利用以下算法实现数组S的初始随机化排列。

​ j=0;

​ for i=0 to 255 do

​ j=j+S[i]+K[i] (mod 256);

​ swap (S[i], S[j]);

PRGA算法：

在KSA将数组S进行初始排序的基础上，PRGA从数组S中随机选取元素作为密钥流字节，同时修改S的排序，以便于下一次密钥流的选取。

选取过程取决于索引i和j，这两个索引都从0开始，选取时重复执行以下算法，直到产生与明文的长度相等的密钥流。

​ i=i+1 (mod 256);

​ j=j+S[i] (mod 256);

​ swap (S[i], S[j]);

​ t=S[i]+S[j] (mod 256);

​ k=S[t];

​ output k=S[t];

从算法中可以看出，索引i保证每个元素的改变，索引j保证元素改变的随机性。

RC4的优点是在软件容易实现且运行速度快。RC4广泛用于商业密码产品中，如用于属于IEEE
802.11无线LAN标准的WEP协议和更新的WiFi保护访问协议等。目前所用的初始密钥一般至少为128
位。

关于分析RC4的攻击方法有许多公开发表的文献。但是当密钥长度很大时，比如128位，没有那种攻击方法有效。