密码学 总结

群 环 域

群 group

G是一个集合，在此集合上定义代数运算*，若满足下列公理，则称G为群。
1.封闭性 $a\in G,b\in G$=>$a\ast b\in G$
2.G中有恒等元素e，使得任何元素与e运算均为元素本身（如：单位矩阵、加法的0，乘法的1）
3.G的每个非0元素都有逆元素，使得元素*逆元素=e（如：加法中的负数，乘法中的倒数）
4.满足结合律

阿贝尔群（可交换群）：
1.满足群的四条公理
2.满足交换律（矩阵不满足）

例：(7,3)码在模2加法下构成群，(n,k)码又称群码
0000000 单位元
0011101
0100111
0111010
1001110
1010011
1101001
1110100
封闭性可验证。存在e。每个元素的逆都是他们本身。模2加法相当于异或，满足结合律。故此运算为群。
线性分组编码

环 Ring

R是一个集合，在其上定义两种代数运算+、*，若满足下列公理则称为环
1.+下构成群
2.*下满足封闭性
3. *下满足结合律
4. 分配律成立（包括左分配和右分配）
左分配：a(b+c)=ab+ac
右分配：(b+c)a=ba+ca
如：矩阵的乘对加满足分配律

e.g.
整数集合是环，加法和乘法构成整数环
实系数的多项式环

域 Field

在F集合上定义两种代数运算+和*，若满足下列公理，则F称为域
1.在加法下构成群
2.全体非0元素构成交换乘群（=加法和乘法都成群）
3.对加法和乘法分配律成立

域是有单位元素、非0元素有逆元素的交换环
e,g,以p=3为模的剩余类全体{0，1，2}构成域

有限域：域中元素数目是有限的； 记为： GF（q）q为域的阶，称为q元域；
无限域：域中元素的数目是无限的；
域的阶：域中元素的数目；

GF（2）为二元域，是最小的域
实际应用中，q的量级是$2^{1024}$，非常巨大

数域包括 复数域、实数域、有理数域

二元域上的多项式

系数取自GF(2),含有一个未定元x的多项式称为GF(2)上的多项式，用f(x)表示。
多项式的加法：同幂次的系数相加
多项式的乘法：正常展开
相加时使用模2加法，即异或，即不进位的加法
$x^2-x=x^2+(1{)}^{-1}x=x^2+x$

二元域上的既约多项式

f(x)是次数>0的多项式，若除了1和多项式本身以外，不能再被GF(2)上的其他多项式除尽，则称为f(x)是二元域上的既约多项式（不可约多项式）。
即，不能分解为两个多项式的乘积
e.g.m=4，f(x)=$x^4+x+1$ 等价于五元向量(1,0,0,1,1)

f(x)不能在GF(2)上分解，但可以在更大的范围域内分解
定义:如果有两个域F1，F2，如果$F_1\subset F_2$，则F2是F1的扩域。
在域F1上的一个不可约多项式，在其扩域F2上可能有根，如果f(x)在F2上有根$\alpha$，则在F2上f(x)有分解因子$(x-\alpha )$

e.g.$x^2+1$在R内不可分解，但在复数域上可以分解为(x+i)(x-i)

设P(x)是GF(2)上的m次既约多项式，GF(2)上所有次数小于m的多项式的全体，在模2加法、模P(x)乘法运算下构成一个$2^m$阶的有限域，称为GF($2^m$)，GF(2)是扩域GF($2^m$)的基域。扩域GF($2^m$)中有$2^m$个元素，每个元素形如：$a_{m-1}{x}^{m-1}+a_{m-2}{x}^{m-2}+...+a_{1}x+a_0$，可记为m维二元向量的形式($a_{m-1},a_{m-2},...,a_1,a_0$)

设P(x)是GF(2)上的一个m次既约多项式，如果构成的扩域GF($2^m$)中的全体非0多项式元素对模P(x)乘法构成乘法循环群，即，存在GF($2^m$)的一个非0元素$\alpha \in GF(2^m)$，它的各次幂${\alpha }^0,{\alpha }^1,...,{\alpha }^{2^m-2}$恰好构成扩域GF($2^m$)的全部非零元素，则称P(x)是GF(2)上的一个m次本原多项式。有：
1.$\alpha$是GF(2)的一个本原元
2.$\alpha$是GF(2)上的既约多项式P(x)在扩域GF($2^m$)中的一个根
3.GF(2)上的本原多项式P(x)在扩域GF($2^m$)中的任何一个根都是本原元

e.g.

$(0,1,\alpha ,{\alpha }^2,....,{\alpha }^{14})$构成域，称为GF（2）的4次扩域。域的阶为16，记为GF($2^4$)。也构成循环群。

求逆：扩展欧几里得算法

对称加密算法 AES

AES(Advanced Encryption Standard) 之 Rijndael算法

迭代分组密码，分组长度为128b，密码长度为128/192/256b，相应的轮数r为10/12/14

讨论密钥长度为128b，分组长度为128b的情况
128b的消息被分为16个字节，每字节8位，记为InputBlock=m0,m1,m2…m15
密钥分组如下：InputKey=k0,k1,k2…k15
内部数据结构表示为一个4x4的矩阵：
I n p u t B l o c k = [ m 0 m 4 m 8 m 12 m 1 m 5 m 9 m 13 m 2 m 6 m 10 m 14 m 3 m 7 m 11 m 15 ] InputBlock=

$$\begin{bmatrix} m0& m4& m8& m12\\ m1& m5& m9& m13\\ m2& m6& m10& m14\\ m3& m7& m11& m15 \end{bmatrix}$$ InputBlock= ​m0m1m2m3​m4m5m6m7​m8m9m10m11​m12m13m14m15​ ​

I n p u t K e y = [ k 0 k 4 k 8 k 12 k 1 k 5 k 9 k 13 k 2 k 6 k 10 k 14 k 3 k 7 k 11 k 15 ] InputKey=

$$\begin{bmatrix} k0& k4& k8& k12\\ k1& k5& k9& k13\\ k2& k6& k10& k14\\ k3& k7& k11& k15 \end{bmatrix}$$ InputKey= ​k0k1k2k3​k4k5k6k7​k8k9k10k11​k12k13k14k15​ ​

轮变换

Round(State,RoundKey)
State是轮消息矩阵，被看作输入和输出，RoundKey是轮密钥矩阵，由输入密钥通过密钥表导出，一轮的完成将导致State的元素改变状态。
每轮变换由四个不同的变换组成：

SubBytes(State)

模f(x)=$x^8+x^4+x^3+x+1$得到扩域GF($2^8$），有256个元素。
SubBytes函数为State的每个字节(x)提供非线性变换，任一非0的字节x$\in F_{2^8}$被下面的变换取代：$y=A{x}^{-1}+b$ 。求逆体现了变换的非线性，A是可逆的，所以此变换可逆。

e.g.

由于系数是0或1，因此可以将任何这样的多项式表示为比特串
加法是这些位串的XOR
乘法是移位&XOR
通过用不可约多项式的余数重复替换最高幂来实现模约简（也称为移位和XOR）

ShiftRows(State)

每行分别循环左移0，1，2，3位

MixColumns(State)

这个函数对State的每一列作用，迭代四次，下面仅仅描述对一列的作用：
令State的一列为： [ S 0 S 1 S 2 S 3 ]

$$\begin{bmatrix} S_0\\ S_1\\ S_2\\ S_3 \end{bmatrix}$$ ​S0​S1​S2​S3​​ ​,把这一列表示为三次多项式：$s(x)=s_3{x}^3+s_2{x}^2+s_{1}x+s_0$,因为s(x)的系数是字节，也就是说是$F_2^8$域中的元素，所以这个多项式是$F_2^8$上的。
列s(x)上的运算定义为将这个多项式乘以一个固定的3次多项式c(x)，然后模x4+1：
$d(x)=c(x)\times s(x)(mod{x}^4+1)$
$c(x)=c_3{x}^3+c_2{x}^2+c_{1}x+c_0$
其中，$x^i(mod{x}^4+1)=x^{imod4}$
Rijndeal给出：c3=“03”, c2=“01”, c1=“01”, c0=“02”
在乘积d(x)中，x2的系数是d2=c2s0+c1s1+c0s2+c3s3
上述乘法的系数可以写成以下矩阵乘法：
$F_8$上，c(x)与$x^4+1$是互素的，所以在$F_8(x)$中，逆$c(x{)}^{-1}(mod{x}^4+1)$是存在的。这等于说，上述矩阵变换是可逆的。

AddRoundKey(State, RoundKey)

这个函数是逐字节、逐比特地将RoundKey中的元素与State中的元素相加。这里的加，是F2中的加，也就是异或运算，是平凡可逆的。
不同轮的密钥比特是不同的。它们使用一个固定的“密钥表”导出密钥，每轮密钥不同，该“密钥表”是非秘密的。具体细节可参阅有关NIST的标准文件。

解密

非对称加密算法 RSA

非对称，指的是加密和解密的密钥不同，又称双钥密码技术、公钥密码技术。
当密钥足够长(现在常用1024bit以上)时，破解极其困难。

特点

公钥可以公布，私钥不可公布。
由私钥可以容易计算出公钥，反之困难。

陷门单向函数

若函数f:A->B可逆（单射+满射），且满足对$x\in A$，易于求解f(x)，但由f(x)求x极为困难，则称为 单向函数。
陷门单项函数：
$f_z:A_z->B_z,z\in Z$,Z是陷门信息集合。
1）在给定$z\in Z$下容易找到一对算法$E_z$和$D_z$，使得对所有$x\in A$，易于计算$f_z$及其逆，即：$f_z(x)=E_z(x),D_z(f_z(x))=x$。
2）只给定$E_z$和$D_z$时，对所有$x\in A$都很难从$y=f_z(x)$中计算出x

单向函数是求逆困难的函数，而陷门单项函数是在不知道陷门信息下求逆困难、在知道陷门信息下求逆容易的函数。

用于构造双钥密码的单向函数

1. 多项式求根
   有限域GF§上的多项式$y=f(x)=(x^n+a_{n-1}{x}^{n-1}+...+a_{1}x+a_0)modp$，当给定a,x,p后，很容易求出f(x)，但已知a,y,p，想求x非常困难，n,p很大时几乎无法求解。

2. 离散对数DL
   p是大素数，a是{0,1,2…,p-1}中与p互素的数。
   已知p,a,x,求f(x)=$a^{x}modp$很容易，但已知p,a,f(x)，求x（离散对数）很困难，计算时间是指数级

3. 大整数分解FAC
   已知大素数p,q,求n=pq只需一次乘法，但已知n求pq非常困难，已知算法有：
   试除法、二次筛、数域筛、椭圆曲线。
   给定n求pq的问题称为rsa问题。求n=pq分解的问题与以下几个问题等价：
   1）给定m,c,n，求d使得$c^d=mmodn$
   2)给定k,c,n，求m使得$m^k=cmodn$
   3)给定x,m，求是否存在y使得$x=y^{2}modm$（二次剩余问题）

4. 背包问题

5. 菲-赫尔曼问题 DHP
   给定素数p，可构造一乘群 Z p ∗ = { 1 , 2 , . . . p − 1 } Z^*_p=\{1,2,...p-1\} Zp∗​={1,2,...p−1}，令a为Z的生成元，若已知$a^a,a^b$，求$a^{ab}$

6. 二次剩余问题QR
   给定奇合数n和整数a，决定a是否为mod n的平方剩余

7. 模n的平方问题 SQROOT

RSA算法

安全性依赖于大整数分解的难度
$n=pq,\phi (n)=(p-1)(q-1)$为欧拉函数
公钥为e，满足$(e,\phi (n))=1$，私钥为d，$d=e^{-1}mod\phi (n)$
加密：m->c=$m^{e}modn$
解密：c->m=$c^{d}modn$

也就是找三个大素数p,q,e，求出$d=e^{-1}mod\phi (n)$，求逆的方法是扩展欧几里得算法。
公钥是n,e,密钥是d，公钥可公开，密钥不可公开，$\phi (n),p,q$都应该销毁。

用途

加密：A->用B的公钥加密->密文->用B的私钥解密->B，常用于交换对称加密算法的密钥，因为加密解密速度较慢。
数字签名：A->用A的私钥加密->签名->用A的公钥解密->B 得以验证