跳转至

对称密码

一、基础知识

（一）异或

运算规则：同为0，异为1

0⊕0=0 1⊕1=0
0⊕1=1 1⊕0=1

（二）常见三种运算符

  1. ^ ，异或计算
  2. | ，有1则1，全0才0 （析取）
  3. & ，有0则0，全1才1（合取）

（三）奇偶校验

奇偶校验是一种校验代码传输正确性的方法。根据被传输的一组二进制代码的数位中“1”的个数是奇数或偶数来进行校验。

采用奇数的称为奇校验，反之，称为偶校验。采用何种校验是事先规定好的。通常专门设置一个奇偶校验位，用它使这组代码中“1”的个数为奇数或偶数。

用奇校验，则当接收端收到这组代码时，校验“1”的个数是否为奇数，从而确定传输代码的正确性。

（四）有限域

有限域是包括有限个元素、能进行加减乘除运算的集合

  • 单位元：任何元素与单位元做运算，得到的都是该元素，单位元是唯一的。
  • 逆元：A与B做运算，得到的结果是单位元，则A和B互为该运算下的逆元
  • 封闭性：运算元素和结果都在域中有对应元素
  • 结合律
  • 交换律
  • 分配律
  • 无零因子

用处：将四则运算精简为二则运算加和乘

群环域

有限域GF(p)

p一定为素数，运算是模p的运算，域中有p个元素，p为素数保证每个元素都有加法和乘法逆元

例：GF(p)，其中 p = 7

  • 加：(a\oplus b)(mod\ 7)=(a+b)(mod\ 7)
  • 减：(a\ominus b)(mod\ 7)=(a+(-b))(mod\ 7)，-b为 b 的加法逆元
  • 乘：(a\otimes b)(mod\ 7)=(a\times b)(mod\ 7)
  • 除：(a\oslash b)(mod\ 7)=(a/ b)(mod\ 7)=(a\times(b^{-1}))(mod\ 7)，b^{-1}是 b 的乘法逆元

​ 在这里，已知5\otimes 3=1，所以6\oslash5=6\otimes3=4，除法运算要求在有限域GF(7)​内，满足封闭性

符合二进制的域GF(2^m)

GF(2)：只有0和1元素，01相加减都需要模2，符合异或运算

扩展域： 如果有限域的阶不是素数，则在这个有限域内加法和乘法操作就不能模p，$ m>1 $ 的域称为扩展域。扩展域的元素可以用多项式表示，且扩展域内的计算也可以通过多项式运算得到。

扩展域GF(2^m)： 在AES中包含256个元素的有限域可以用GF(2^8)。该域的每一个元素都可以用一个字节表示。

每个元素 $ A\in GF(2^8) $ 都可以表示为：$ A(x)=b_7x^7+……+b_1x+b_0, b_i\in GF(2)={0,1} $

简单举例：$ 1=1,2=x,3=1+x,4=x2,5=1+x2,6=x+x^2,…… $

运算

加法： 异或

例：57+66=01010111+01100110=00110001=31，这里的57、66和31均为16进制

乘法： 先乘再加，最后模，这里的模多项式采用m(x)=x^8+x^4+x^3+x+1 $$ 57\times 66=01010111\times 01100110\ =(x6+x4+x^2+x+1)\times (x6+x5+x^2+x)\ =x{12}+x+x8+x7+x6+x+x9+x7+x6+x5\ +x8+x6+x4+x3+x2+x7+x5+x3+x^2+x\ =x{12}+x+x{10}+x9+x7+x6+x4+x(mod x8+x4+x3+x+1)\ =x7+x5+x4+x3+x+1 $$ x乘法运算： 定义为x·b(x)=b_7x^8+b_6x^7......+b_1x^2+b_0x(mod\ m(x))，在这里 x 相当于16进制的 02 $$ b_7=1,x·AE=02·10101110=01011100\oplus 00011011=01000111=47\ b_7=0,x·57=02·01010111=10101110=AE $$

二、分组密码

定义：将明文消息分割成固定长度的数据块，并使用相同的密钥和算法对每个数据块进行加密

例：加密FOUR_AND_FOUR利用分组密码可以先加密FOUR，再加密_AND_ ，最后加密FOUR，即一次加密明文中一个字符块

（一）分组模式

分为ECB（电子密码本）、CBC（密码块链接）、CFB（密码反馈），OFB（输出反馈），前两种模式使用分组密码，后两种模式将分组密码当作流密码使用，另外常见还有CTR（计数器），是OFB的变种

  1. ECB

一般给定密钥后，相同的明文块会有相同的密文块，如果明文块反复出现，对应的密文块也会多次出现，会为破解密文提供线索

加密：

img

电子密码本仅适合加密短消息，明文重复少，破解几率低

解密：

img

  1. CBC

在块密码中增加反馈机制链接，即用每个块来修饰下一个块的加密

加密：

img

(1) 如图所示，第1步有两个输入：第1个明文块和一个随机文本块。随机文本块是初始化向量（IV），没有特殊含义，只是为了使每个消息独特。将第1个明文块和IV异或再用密钥加密，生成密文块1

(2) 将密文块1跟明文块2异或后再用密钥加密得出密文块2，依次类推

注：IV仅在第1个明文块中使用，但用相同的密钥加密

解密：

img

  1. CFB

数据加密单元更小（8位，即输入1个字符的大小）

工作原理：

(1) 和CBC一样使用64位IV，IV保存在移位寄存器里，用密钥加密IV得出加密的IV

(2) 将加密的IV最左边（即最高有效）的 j 位与明文的前 j 位进行异或，产生密文的第1部分，将密文C反馈给IV移位寄存器

(3) IV移位寄存器左移 j 位，即IV所在的位移寄存器内容左移 j 位，因此IV移位寄存器最右j位为不可探测数据，用密文C填充最右 j 位

(4) 重复以上步骤

加密过程：

img

解密(重新走一遍加密算法)：

img

  1. OFB

OFB与CFB非常相似，唯一的区别是，CFB将密文反馈到加密过程下一阶段，OFB将IV加密过程的输出反馈到加密过程下一阶段

img

可以和CFB加密过程对比着来看

OFB的优势在于，个别位的错误只会影响个别位，不会破坏整个消息；缺点在于攻击者可以同时篡改密文和信息的校验和，而我们无法检测这种篡改

注：校验和就是通过对数据进行特定算法处理，生成一个简短的固定长度的校验码，附加在数据尾部。这个校验码的生成基于数据的每一位进行异或运算。如果数据中某一位发生变化，那么在校验码中这一位也会发生变化，从而检测到错误

  1. CTR

CTR是OFB的变种，用序列号（即计数器）作为输入，在加密每个块后，再使用下一个计数器值填充寄存器。通常使用一个常数作为计数器初始值，并且每次迭代后递增。计数器块的大小等于明文块的大小。CTR模式可以多个文本块并行处理。

img

（二）填充方式

关于填充，一般情况下明文长度是不符合分块要求的，需要对此进行填充。

常见填充方式如下：

  1. ISO 10126： 规定应在最后一个块的末尾用随机字节进行填充，填充边界应由最后一个字节指定。

这种填充方式中，填充字符串的最后一个字节为填充字节的长度，其他为随机字节

例如：现在有3bytes，块大小为8bytes，需要填充5bytes，则最后一个为 05，其他全部为 00

原数据：66 6F 72

填充后的数据：66 6F 72 81 A3 00 23 05

  1. PKCS7： 假设需要填充n (n>0) 个字节才对齐，填充n个字节，每个字节都是n ；如果数据本身就已经对齐了，则填充一块长度为块大小的数据，每个字节都是块大小；PKCS7填充字节的范围在 1-255 之间 ，填充方式为上面的 填充数据为填充字节的长度，填充如下：
1
2
3
4
5
6
7
01
02 02
03 03 03
04 04 04 04
05 05 05 05 05
06 06 06 06 06 06
etc.

当且仅当N小于256时才有用。

原数据：66 6F 72

填充后的数据：66 6F 72 05 05 05 05 05

  1. PKCS5： 将数据填充到8的倍数，填充数据计算公式是，假如原数据长度为len，利用该方法填充后的长度是 len + (8 - (len % 8)), 填充的数据长度为 8 - (len % 8)，块大小固定为8字节，和PKCS7的区别在于，5的填充块大小为8bytes，而7的填充块大小可以在1-255bytes之间。

  2. ISO/IEC 7816-4： 第一个字节是值为 '80' （十六进制） 的强制字节，如果需要，后跟 0 到 N − 1 个设置为 '00' 的字节，直到到达块的末尾

例如：66 6F 72 80 00 00 00 00

  1. Zero padding： 所有需要填充的字节都用零填充。比如66 6F 72 00 00 00 00 00。它通常应用于二进制编码的字符串(以null 结尾的字符串)，因为null字符通常可以作为空格被剥离。

（三）DES

DES使用56位的密钥和64位的明文块进行加密，初始密钥实际上也是64位，但在开始之前，丢弃了密钥的每个第8位，得到56位密钥。丢弃之前可进行奇偶校验，以确保密钥不包含任何错误。

img

(1)初始置换

初始置换只发生一次，且只发生在第一轮之前，例如，初始置换指定要将原始明文块的第1位替换成原始明文块的第58位，第2位替换成第50位等。

完成初始置换后，生成的64位置换明文块被分为两半，各32位，左半块是左明文(L0)，右半块是右明文(R0)，对这两块执行16轮操作

img

(2)获取子密钥

在进入第一轮之前，还需要对密钥进行处理生成子密钥，每一轮将使用不同的子密钥参与运算。DES加密算法的密钥长度为56位，一般表示为64位(每个第8位用于奇偶校验)，将用户提供的64位初始密钥经过一系列的处理得到K1,K2,…,K16，分别作为1~16轮运算的16个子密钥。

  1. 将64位密钥去掉8个校验位，用密钥置换PC-1置换剩下的56位密钥。

PC-1置换表如下

图 3

  1. 将56位分成前28位C0和后28位D0。

  2. 根据轮数，这两部分分别循环左移1位或2位

图 4

  1. 移动后，将两部分合并成56位后通过压缩置换PC-2后得到48位子密钥。

PC-2置换表如下

图5

(3)轮函数f

轮函数F的作用是将输入的32比特数据和48比特子密钥进行加密输出32比特

扩展置换E：将数据的右半部分Ri从32位扩展为48位。位选择函数(也称E盒)。

img

异或：扩展后的48位输出E(Ri)与压缩后的48位密钥Ki作异或运算；

S盒替换：将异或得到的48位结果分成八个6位的块，每一块通过对应的一个S盒产生一个4位的输出。（8个不同s盒压缩处理）

\ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13

原始数据：1 0011 1，头尾：11，中间：0011，压缩后数据：0010

P盒置换：将S盒得到的输出再和P盒进行置换操作。

图6

  • 一轮下来”右侧“并没有被加密，需要不同的子密钥重复若干次，并在每两轮处理之间将左右数据对调
  • 3轮加密需要两次左右对调，对调只在两轮之间进行，最后一轮结束之后不需要对调
  • 解密只需要照相反顺序使用子密钥就可以

(4)逆置换

也叫最终置换，DES加密过程最后的逆置换IP−1，是初始置换的逆过程。经过16次迭代运算后，进行逆置换，即得到密文输出。逆置换正好是初始置的逆运算。例如，第1位经过初始置换后，处于第40位，而通过逆置换，又将第40位换回到第1位。置换表如下：

图7

（四）AES

1. 加密

img

轮密钥加： 明文矩阵P，子密钥矩阵K，轮密钥加的结果就是两个矩阵对应元素异或

字节替换： 将字节看作GF(2^8)上的元素，根据s盒做映射，然后对字节做如下的（GF(2)上可逆的）仿射变换

字节替换

行移位： 第一行不变，第二行左移1，第三行左移2，第四行左移3

列混淆： 在列混淆变换中，将状态矩阵的每个列都视为 GF(2^8) 上的多项式，再与一个固定的多项式 c(x) 进行模 x^4+1 乘法，否则列混合变换就不可逆了， c(x)=03x^3+01x^2+01x+02 ，这个式子与 x^4+1 互素，设 b(x)=c(x)\otimes a(x) ，有： $$ \begin{bmatrix} b_0 \ b_1 \ b_2 \ b_3 \end{bmatrix}=\begin{bmatrix} c_0 & c_3 & c_2 & c_1\ c_1 & c_0 & c_3 & c_2\ c_2 & c_1 & c_0 & c_3\ c_3 & c_2 & c_1 & c_0 \end{bmatrix}\begin{bmatrix} a_0\ a_1\ a_2\ a_3 \end{bmatrix} = \begin{bmatrix} 02 & 03 & 01 & 01\ 01 & 02 & 03 & 01\ 01 & 01 & 02 & 03\ 03 & 01 & 01 & 02 \end{bmatrix}\begin{bmatrix} a_0\ a_1\ a_2\ a_3 \end{bmatrix} $$

2. 密钥编排：

指从种子密钥中获得轮密钥的过程，由密钥扩展和轮密钥选取两部分组成，其基本原则如下：

  • 轮密钥的比特数等于分组长度乘以轮数加1
  • 种子密钥被扩展为扩展密钥
  • 轮密钥从扩展密钥中取，其中第1轮轮密钥取扩展密钥的前 N_b 个字，第2轮轮密钥取接下来的 N_b 个字，如此下去

1）密钥扩展(这部分可看5分钟搞定AES算法)

扩展密钥是以4字节字为元素的一维阵列，表示为 W[N_b*(N_r+1)] ，其中前 N_k 个字取为种子密钥，以后每个字按递归方式定义，扩展算法根据 N_k 范围不同而不同，只讲 N_k=4 的情况。

分为 w[i] 的 i能整除 4 和 i 不能整除 4

Rcon[i/N_k] 是轮常数，值与N_k无关，定义为Rcon[i]=(RC[i],00,00,00)，其中RC[i]是GF(2^8)中值为x^{i-1}的元素，因此RC[1]=01,RC[i]=x(02)·RC[i-1]=x^{i-1}

2）轮密钥选取

轮密钥i（即第 i 个轮密钥）由轮密钥缓冲字W[N_b*i]到W[N_b*(i+1)-1]给出

2. 解密

  • 交换逆向行移位和逆向字节代替并不影响结果
  • 交换轮密钥加和逆向列混淆并不影响结果，关键在于首先可以把异或看成域上的多项式加法，然后多项式中乘法对加法具有分配律

加解密全图

三、流密码

定义：流密码是加密和解密双方使用相同伪随机加密数据流作为密钥，明文数据每次与密钥数据流顺次对应加密，得到密文数据流。实践中数据通常是一个位（bit）并用异或（XOR）操作加密 可以理解成明⽂ ⊕ ‘密钥’，但是密钥是由⼀个伪随机数⽣成器⽣成的

PRG/PRNG伪随机数生成器

伪随机序列：如果一个序列能够和等长的随机序列不可区分的话，那么它就是伪随机序列，即可以以假乱真的序列

LCG线性同余生成器

LCG的原理是通过一个递归公式生成下一个随机数，包含一个乘法因子、一个加法常数和一个模数。 $$ X_{n+1}=AX_n+B(mod m)\ 其中乘法因子0<A<m，加法常数0≤B0\ A=13,B=17,m=22,X_n=8\ X_{n+1}=(13\times 8+17)mod 22 =121 mod 22=11 $$ python：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
import time
seed = int(time.time())
a=13
b=17
m=22
def generate_random(seed):
    while True:
        seed = (a * seed + b ) % m
        yield seed

random_generator=generate_random(seed)

for i in range(20):
    random_number = next(random_generator)
    print(random_number)

LFSR线性反馈移位寄存器

LFSR

示意图

python:

1
2
3
4
5
state = 0b1101
for i in range(16):
    print("{:04b}".format(state))
    newbit = (state^(state>>1))&1
    state = (state>>1)|(newbit<<3)

作业课后发压缩包，其wp在网上均可找到，希望大家理解后写出自己的wp

参考文献：ctfwiki、密码学中的数学基础1 群环域 、密码学中的数学基础2 伽罗华域（Galois Field）上的四则运算 、现代密码学｜AES数学基础｜GF（2^8）有限域上的运算问题、现代密码学｜AES加密算法、DES加密算法｜密码学｜信息安全、nssctf工坊等

评论