古典密码体制的计算：

字母对照表

image-20210516231951185

仿射变换

加密变换E_k(m)=a+bm mod q 解密变换 D_k(c)=(c-a)b^-1 mod q

密钥短语密码

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

image-20210516225756011

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

设密钥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

img

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的组：

m= thesi | mples | tposs | iblet | ransp | ositi | oncip | hersx

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

image-20210516232300060

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

流密码

image-20210517102812683

游程分布计算

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

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

注意有周期，即{ki}= 001110100000111100 001110100000111100 …

序列自相关计算

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

image-20210517112507287

其中i+t是模N运算

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

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

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

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

image-20210517113753799image-20210517120042178

线性反馈移位寄存器

已知如图所示的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算法流程

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

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

image-20210517124455834

IP变换

将64位明文打乱重新排列. 设x=x1x2…x64，则IP(x)=x58x50x42…x23x15x7

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

初始置换IP的逆置换 将64位密文位置还原. 设y=y1y2…y64，则IP-1(y)=y40y8y48…y17y57y25

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

23453124312

轮函数F

image-20210517170542193img

扩展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)

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

imgimage-20210517171932281

子密钥生成算法

image-20210517172335799

置换变换：PC-1

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

123

循环左移LSi

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

imgimgimg

置换选择 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=(m1,m2,m3,m4)，其中每个子块长度为16。将密文M分为4个子块: M=(M1,M2,M3,M4), 其中每个子块长度为16。将密钥z分为6个子块：z=(z1,z2,z3,z4,z5,z6)，其中每个子块长度为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], w0[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(aij)=bij.

image-20210517234451746行位移和列混合image-20210517234715584image-20210517234942412 轮密钥加image-20210517235039021

解密算法

字母代换

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

image-20210517235236692

行位移和列混合

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

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

image-20210517235537276

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

初始变换——密钥加

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

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

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

第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的乘法生成元。

测试方法:令q1,q2,…, qn是p-1的素因子，对于所有的q1,q2,…, qn, 计算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的离散对数，求离散对数为一个困难问题

中国剩余定理

image-20210518231736846二次剩余image-20210519000305911

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)，ed = 1 mod φ(n*).

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

私钥: SK=(p, q , d).

加密算法

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

解密算法

密文c: 0<=c<n，明文 m=D_SK(c)=c^d (mod n)

Rabin 公钥密码体制

密钥生成算法

选择两个大的素数p和q，要求p和q都是4的倍数加3。

计算n=p*q。Bob的公钥是n，对外公布。 Bob的私钥是（p，q），自己私藏。

加密算法

将明文通过一个可逆映射为一个小于n且与n互素的正整数m,即 0<m<n 且 gcd (m,n)=1。

Alice用Bob的公钥n，计算： c=m²(mod n)。c为密文。

解密算法

Bob 收到密文c后，用自己的私钥（p，q）计算

image-20210519002629696

背包公钥密码体制

密钥生成算法

取n个具有超递增性的物品重量：a1，a2，a3，…，an。

取正整数M，U，满足

(1) M>a1+a2+a3+…+an；(2) M>U；(3) U*a1>M；

M与U互素，因此可以用辗转相除法计算出U关于(modM)的逆元U^-1。

计算：b1=U*a1(mod M)，b2=Ua2(mod M) ，b3=Ua3(mod M) ，…，bn=Uan(mod M) 。(不具有超递增性)

此时

a1=U^-1b1(mod M)，a2=U^-1b2(mod M)，a3=U^-1b3(mod M)， …，an=U^-1bn(mod M) 。

{b1，b2，b3，…，bn}是公钥。

{a1，a2，a3，…，an} ， M，U都是私钥。

加密算法

设明文m为正整数，其二进制展开式为m=(m1,m2,m3…mn)₂。使用公钥{b1，b2，b3，…，bn}计算密文c ：c=m1*b1+m2b2+m3b3+…+mnbn。密文c是一个正整数。

解密算法

使用私钥{a1，a2，a3，…，an} ， M，U，计算变换课文C：

C=U^-1c(modM)

=U^-1(m1b1+m2b2+m3b3+…+mnbn )(modM)

=m1a1+m2a2+m3a3+…+mnan(modM)

=m1a1+m2a2+m3a3+…+mnan。

Elgamal 公钥密码体制

循环群`

设(G,*)是一个有限群, |G|= n, e是G的单位元. 如果存在 a属于G，使得a, a2,…, an=e互不相同,即 G={a, a2,…,an}, 则称a是G的一个本原元（生成元）. (G,*)称为循环群。

有限域

设p是一个素数, Zp= {0,1,2,…, p-1}. 在Zp 中, 加法与乘法按 mod (p) 进行, 则Zp称为一个有限域。

GF(p)的本原元

设Zp= {1,2,…, p-1}, a属于Zp*, 如果a, a²,…, a^p-1 =1互不相同,即 Zp*={a, a2,…,ap-1}, 则称a是Zp的一个本原元. (Zp*, )是一个循环群。

密钥生成算法

厄格玛尔(ElGamal)密码体制

密钥产生: 选择素数p，整数g, x满足 0<g, x<p, 计算 y=g^x mod p.

公钥: (p, g, y)

私钥: x

加密算法

设明文为m (0<m<p), 随机选取k(0<k<p), 计算 c1=g^k mod p, c2=y^km mod p.

密文: c=(c1, c2)

解密算法

设密文为c=(c1, c2), 则明文为 m=c2*(c1^x)^-1 mod p.

image-20210519005352194

椭圆曲线加解密运算

密钥选取

确定公开参数(p, a, b, n, g)

选择一个素数p, 确定有限域GF(p) 选择a, b属于GF(p), 确定椭圆曲线E

选择E的一个循环子群H, 使得| H |=n是一个大素数 选择H的一个本原元g.

确定私钥: x 用户随机选取x属于{0,1,2,…,n-1}

确定公钥: y= x*g.

有限域上的椭圆曲线

椭圆曲线群计算

设p>=3是素数, Fp= {0,1,…, p-1}是有限域, a, b属于p, △=4a³+27b²不等于0 mod (p), 同余方程 y²=x³+ax+b

image-20210519154815918image-20210519154649100

加解密算法

加密算法 设明文为m, 将m映射到循环群H上的点. 随机选取k属于{0,1,…,n-1} 计算:c1=kg=(x1, y1) 计算:c2 =m+ky=(x2, y2) 密文: c=(c1, c2)

解密算法 设密文为c=(c1, c2), 则明文为 m=c2-xc1.

加解密例子

image-20210519155122577

Hash函数

lHash函数的分类

单向Hash函数（one-way）给定一个Hash值y，如果寻找一个消息x，使得y=h (x)是计算上不可行的，则称h是单向Hash函数.

弱抗碰撞Hash函数（weakly collision-free） 任给一个消息x，如果寻找另一个不同的消息x’，使得h(x) =h(x’)是计算上不可行的，则称h是弱抗碰撞Hash函数.

强抗碰撞Hash函数 （strongly collision-free） 如果寻找两个不同的消息x和x’，使得h(x)=h(x’)是计算上不可行的，则称h是强抗碰撞Hash函数.

数字签名

RSA签名

密钥生成算法

选取两个大素数p，q，计算 n=pq，去φ(n)=( p -1) ( q -1)。 任选整数e，满足： 0< e <φ(n)，且gcd(e ,φ(n))=1。

用扩展Euclidean算法求e模j(n)的逆d，即 e*d=1 mod φ(n)。 签名者的公钥: { n，e}，私钥:{ p，q，d}。

签名算法 设消息为x，则x的RSA签名为 y=x^d mod n 验证算法当接收方收到签名(x,y)后，验证x=y^e mod n

Elgamal 数字签名

密钥生成算法 选取一个大素数p，g属于Zp*是一个本原元，p和g是系统公开参数。 任选整数x，满足：1≤x≤p-2。计算 y=g^x mod p. 签名者的公钥为y，私钥为x。

签名算法

image-20210519014700894验证算法image-20210519014748009

美国数字签名标准

密钥生成算法签名及验证算法

image-20210519155650723

俄罗斯数字签名标准

密钥生成函数签名算法及验证算法

image-20210519155531829

FS签名

选取两个大素数p、q，令n=p*q。n是公开参数，p和q是管理中心CA掌握的密钥。设h是一个公开的Hash函数，k是一个固定的正整数。

管理中心CA为用户A产生k个公开密钥： y_i (i =1,2,…,k) 是模n的平方剩余

再为用户A产生k个私钥（保密）

签名算法image-20210519015617777

验证算法image-20210519015734096