现代密码学

古典密码体制的计算：¶

字母对照表¶

仿射变换¶

加密变换*E*_k(*m)=a+b*m mod q 解密变换 *D_k(c)=(c-a)**b*^-1 mod q

密钥短语密码¶

选择一个英文短语作为密钥字或称密钥短语，如HAPPY NEW YEAR，去掉重复的字母得到HAPYNEWR。将它依次写在明文字母表的下面，而后再将字母表中未在短语中出现过的字母依次写在这个短语后面，就可以构造一个代换表，如下所示：

维吉尼亚密码（多表代换）¶

设密钥k=(k[0], k[1],,…,k[d-1])属于Zqd,

代换序列: p=(p[0], p[1],…,p[d-1]), p(x)=x+k[i] mod q. 明文序列: m=(m[0], m[1],…)

密文序列: c=(m[0]+k[0])(m[1]+k[1])…(m[d-1]+k[d-1])

(m[d]+k[0])(m[d+1]+k[1])……

设*q*=26, d=6, k=CIPHER=(2,8,15,7,4,17) 明文: m=this cryptosystem is not secure 密文: c=VPXZGI AXIVWP UBTTMJ PWIZIT WZT

Hill加密（多字母代换）¶

基于矩阵的线性变换:

Z26为模26的同余类集合, K是一个L*L矩阵,在Z26上可逆,即存在K^-1使得: KK^-1 = I (在Z26上)

注：明文与密文都是L维的向量 m=（m1, m2 …, mL); c=(c1,c2,…,cL); 加密：c=mK mod 26; 解密：m=cK^-1 mod 26;

换位密钥（综合案例）¶

明文：m= the simplest possible transposition ciphers 分成长度为5的组：

加密变换：将各组内字符按位置标号（0~4）实施下述置换（permutation) (Ek为正变换，Dk为逆变换)

密钥：c=STIEH EMSLP STSOP EITLB SRPNA TOIIS IOPCN SHXRE

流密码¶

游程分布计算¶

设*a*= (a[0], a[1],…,a[i],…)是一个周期为*N*的二元序列，在一个周期内连续出现的最多的符号“0”（或1）的串，称为0（或1）的一个游程。在一个游程中，0（或1）的个数称为该游程的长度。

在序列 k={*k*i}=001110100000111100…中, 有长为1的0游程一个; 长为4的0游程一个; 长为5的0游程一个; 长为1的1游程一个; 长为3的1游程一个; 长为4的1游程一个

注意有周期，即{*k*i}= 001110100000111100 001110100000111100 …

序列自相关计算¶

设*a*=(a*0,*a*1,…,*a[N-1])和*b*=(b*0,*b*1,…,*b[N-1])是两个周期为*N*的二元周期序列，其相关函数定义为

其中i+t是模N运算

特别地，如果*a*=b，则*R*a*,a(t)被称为自相关函数，其中当t =0，*R*a,a(0)被称为同相自相关函数，而当*t*不等于0， R*a,a(t)被称为异相自相关函数。

反馈移位寄存器（输出为a1）¶

设有限域GF(2)上的3级FSR的反馈函数为: f(*x*1, *x*2, *x*3)=*x*1异或*x*2异或*x*3 初始状态为*s*0=(1,0,1). 求FSR序列.

解: 反馈移位寄存器序列: a =1011…; 周期*q*=4.

线性反馈移位寄存器¶

已知如图所示的3级LFSR. 特征多项式为： f(x)=1+x²+x³ 即为 a[0]+a[2]+a[3]=0

LFSR序列*a*=(a[0], a[1],…,a[n-1],…) 满足递推关系式: a[n]=a[n-2]+a[n-3]. 如果设初始状态为: (0,0,1) 即*a*[0]=0, a[1]=0, a[2]=1,输出序列为: 0010111, 周期为7.

分组密码¶

DES算法¶

DES算法流程¶

分组大小: 2*w*=64 密钥大小: |K|=56 子密钥: |K[i]|=48 轮数: h=16

对明文作置换*IP*后开始第1次迭代第16次迭代后，交换左、右32bit数据，再作逆置换*IP*^-1，即得密文

IP变换¶

将64位明文打乱重新排列. 设*x*=x*1*x*2…*x*64，则*IP(x)=*x*58*x*50*x*42…*x*23*x*15*x*7

加密结果：10011000 00000111 00110001 11111101 10010110 01100101 11000010 10001110

初始置换IP的逆置换将64位密文位置还原. 设*y*=y*1*y*2…*y*64，则*IP-1(y)=*y*40*y*8*y*48…*y*17*y*57*y*25

解密结果：11011111 00101011 11010000 00100101 10101000 10011100 01000011 01101001

23453 124312

轮函数F¶

扩展E变换（对R进行扩展变换）¶

S盒和置换P运算（S盒输出结果置换）¶

输入: b[1] b[2] b[3 ]b[4] b[5] b[6], 用10进制表示:

(i)10=b[1]b[6] (0<=i<=3), (j)10=b[2]b[3]b[4]b[5] (0<=j<=15)

对于*S*1，输入*b*=101011, 有*i*=11=3, j=0101=5, 输出: S*1(*b)= *S*1(3,5)=9=1001.

子密钥生成算法¶

置换变换：PC-1¶

64位密钥*K*的第8, 16, 24,…,64位共8位是奇偶校验位, 其余56位作为密钥用. 选择*K*的第57,49,…位共28位作为密钥段*C*0;选择*K*的第63,55,…位共28位作为密钥段*D*0.

123

循环左移LSi¶

将28位的密钥段作为*C*[i], D[i]循环左移1或2位,左移位数由下表确定.

置换选择 PC-2¶

从56位密钥段*C*[i]||*D[i]中选择48位作为子密钥*K[i].

DES解密算法¶

与DES加密结构相同子密钥使用次序相反: K[16], K[15], …, K[2], K[1] 输入：密文y; 输出：明文*x*

IDEA中主要运算¶

运算‘+’：两个长度为16的比特串*x*和*y*。 x‘+’*y*表示*x*和*y*做逐位模2加运算（逐比特异或）。

运算“+”：将长度为16的比特串*x*和*y*看作是“≥0，且<2¹⁶”的整数。x“+”*y*表示*x*和*y*做模2¹⁶加运算。

运算×：将长度为16的比特串*x*和*y*看作是“≥1，且<2¹⁶+1”的整数。

其中将全0串看作是2¹⁶。 x×*y*表示*x*和*y*做模2¹⁶+1乘运算。（注意： 2¹⁶+1 是素数）

轮函数¶

轮函数数据¶

轮函数为*M*=F(m, z), 其中*m*是明文，它是长度为64的比特串；*M*是密文，它是长度为64的比特串； *z*是密钥，它是长度为96的比特串。

将明文*m*分为4个子块：m=(m*1,*m*2,*m*3,*m*4)，其中每个子块长度为16。将密文*M*分为4个子块: *M=(M*1,*M*2,*M*3,*M*4), 其中每个子块长度为16。将密钥*z*分为6个子块：*z=(*z*1,*z*2,*z*3,*z*4,*z*5,*z*6)，其中每个子块长度为16。

三种运算‘+’、“+”、×分别为前面所述。

轮函数运算¶

轮函数算法描述如下：

（1）(m[1], m[2], m[3], m[4])(×,“+”,“+”,×) (z[1], z[2], z[3], z[4])=(a, b, c, d)。（群加密）

（2）(a‘+’c, b‘+’d)=(e, f)。（MA变换）

（3）((e×z[5])“+”f )×z[6]=u，u“+”(e×z[5])=v。（MA变换）

（4）(a, b, c, d)(‘+’,‘+’,‘+’,‘+’) (u, v, u, v)=(w[1], w[2], w[3], w[4])。（MA变换）

（5）(w[1], w[3], w[2], w*0[4])=(*M[1], M[2], M[3], M[4])。（块置换）

加密顺序¶

分组密码IDEA的完整加密算法是连续8次使用轮函数，不过第8轮与前7轮有所不同。前7轮是普通轮，轮函数的运算步骤如前所述为：

群加密→MA变换→块置换。

第8轮是特殊轮，轮函数的运算步骤为：

群加密→MA变换→群加密。

IDEA算法解密¶

加解密顺序不同，只不过密钥顺序发生改变：

加密密钥(q[1],q[2],q[3],q[4],q[5],q[6])则对应的解密密钥为(q[1]^-1, -q[3], -q[2], q[4]^-1,q[5],q[6]) （加乘法逆运算）

IDEA 密钥生成算法¶

IDEA加密算法中所使用的密钥共有52个子块，即加密密钥长度为16×52=832（比特）。用户密钥实际上只有128 （比特），因此需要一个密钥扩展算法。密钥扩展算法如下。将128 比特的用户密钥分为8个子块，作为加密密钥的第一个“8个子块”；将128 比特密钥循环左移25位，再分为8个子块，作为加密密钥的第二个“8个子块”；

AES算法¶

AES流程¶

AES算法模多项式 m(x)=x⁸+x⁴+x³+x+1. 均为在GF(2⁸)上的运算11

初始变换——密钥加

第一轮：字节替换→行移位→列混合→密钥加第二轮：字节替换→行移位→列混合→密钥加

第三轮：字节替换→行移位→列混合→密钥加第四轮：字节替换→行移位→列混合→密钥加

………………………………………………………………

第Nr-1轮：字节替换→行移位→列混合→密钥加第Nr轮：字节替换→行移位

末尾变换——密钥加

字节代换¶

对状态的每个字节独立进行代换，是字节的非线性变换，也称为S盒变换。设 ByteSub(a*ij)=b*ij.

行位移和列混合轮密钥加

解密算法¶

字母代换¶

先做仿射的逆变换然后再求逆

行位移和列混合¶

行位移逆回即可列混合将状态矩阵每列的4个字节表示成一个3次多项式，再与多项式*d*(x)相乘.

d(x)=(0B)x³+(0D)x²+(09)x+(0E).

解密顺序（已对密钥进行变换）¶

初始变换——密钥加

第一轮：字节替换→行移位→列混合→密钥加第二轮：字节替换→行移位→列混合→密钥加

第三轮：字节替换→行移位→列混合→密钥加第四轮：字节替换→行移位→列混合→密钥加

………………………………………………………………

第Nr-1轮：字节替换→行移位→列混合→密钥加第Nr轮：字节替换→行移位

末尾变换——密钥加

公钥密码体制¶

补充数学¶

欧拉函数¶

(欧拉定理)对于任何互素的两个整数a和n，有 a^φ(n) ≡ 1 mod n 对任意的正整数k, 有 a^k*φ(n) +1≡ a mod n ，

欧拉函数*φ(n)*的几条性质：

(1) n为素数， φ(n)=n－1;(2)若p为素数，n为正整数，则φ(pⁿ)=(p-1)p*^n-1* (3) gcd(m, n) =1, φ(mn)= φ(m) ×φ(n)

如果*m*是使*a*^m ≡ 1 mod *n*成立的最小正整数，则称它是*a*对模*n*的指数，或者称为*a*关于模*n*的乘法阶，记为Ord_na。

若Ord_na=φ(n)，则称*a*是模*n*的本原根(primitive root)，也称模*n*的乘法生成元。

测试方法:令*q*1,q*2,…, *q*n是*p-1的素因子，对于所有的*q*1,q*2,…, *q*n, 计算*a^(p-1)/q (mod p) ，如果对某个素因子*q*，其结果为1，那么*a* 不是一个本原根。如果对所有素因子*q*，其结果都不为1 ，那么*a* 是一个本原根。

对于一个整数*b*和素数*n*的一个本原根*a*，可以找到唯一的指数*x*，使得*b* ≡ a^x mod n，其中0≤ x ≤n-1，指数*x*称为*b*的以*a*为基数的模*n*的离散对数，求离散对数为一个困难问题

中国剩余定理二次剩余

RSA算法¶

密钥生成算法¶

(1) 选取两个大素数 p, q

(2) 计算*n*= p*q, 取φ(n)=(p-1)*(q-1)

(3) 随机选取*e*: 1<e<φ(n)，与*φ*(n)互素

(4) 根据欧几里德算法计算*e*的逆 d=e^-1:

1<e<φ(n)，e*d = 1 mod φ(n).

(5) 公钥: PK=(n, e),

私钥: S*K=(p, *q , d).

加密算法¶

消息m: 0<=m<n，密文 c=E_PK(m)=m^e (mod n)