密码学相关基础知识

一、基本知识

1.术语

• 明文：没有经过加密，任何人都能看得懂的文字

• 密文：经过加密后的文字

• 密钥：明文与密文转换的参数

2.保密原则

是现代密码学和古典密码学的重要区别

• 现代密码原则：密码系统的安全性不依赖于算法的保密而依赖于密钥的安全

• 古典密码原则：密码系统的安全性依赖于算法的保密和密钥的安全

3.安全性

绝对安全(无条件安全)：

指的是攻击者在拥有无限的计算资源的条件下也无法被攻破的秘密体制，对于一个加密算法，如果明文空间的每种概率分布，其中的每个明文和每个密文都满足，不论特定密文是否出现，特定明文出现概率都相同(即：P(M=m|C=c) = P(M=m))

计算安全：

攻击在有限计算资源的条件下很难攻破密码体制，将攻击者的攻击视作一个算法，要求算法的时间复杂度O(n^c)足够大，无法遍历密钥(n为密钥的二进制位数，c为常数)

4.安全目标

破坏性从上到下依次降低

• 攻击者不能获得密钥

• 攻击者不能获得全部明文

• 攻击者不能获得明文的任何部分

• 攻击者不能获得明文的任何函数

5.加密原则

• 扩散(diffusion)：明文及密钥的影响尽可能散布到多密文中(置换)

• 混淆(confusion)：使明文和密文间的统计相关性最小化(代换)

6.数学基础

包括数论、概率论、近世代数、代数几何、计算复杂性

二、密码编码

1.古典密码

(1)置换密码

明文中的字符保持不变，通过改变字符顺序进行加密

• 栅栏密码：加密：将明文分成k组，取每组的第i个字符连成密文段i，再将密文段全部相连形成密文解密：将密文分成k组，取每组的第i个字符连成明文段i，再将明文段全部相连形成明文密钥：k

(2)代换密码

明文中的字符顺序保持不变，通过将字符替换成其他字符进行加密

单表代换:

加法密码:

(也叫移位密码特例为凯撒密码)

加密：E(x)=(x+k)%m

解密：D(x)=(x-k)%m

密钥：k

乘法密码:

加密：E(x)=(kx)%m

解密：D(x)=(k^-1x)%m

密钥：k

仿射密码:

加密：E(x)=(a*x+b)%m

解密：D(x)=(x-b)/a%m

密钥：(a，b)

棋盘密码:

编制密码表：绘制5*5的方格，将i和j放入同一个格子，给每一个格子一个坐标(x，y)

加密：将明文依次替换为坐标对

解密：将密文在密码表中找到坐标对应的值

多表代换:

• 维吉尼亚密码:加密：E(x)=(x[i]+k[i%n])%m解密：D(x)=(x[i]-k[i%n])%m密钥：k[n]

多字符代换

普莱费尔密码:

编制密码表：

1.绘制5*5方格

2.选取密钥(任意字符组合)

3.将密钥依次填入方格(重复的字符只保留第一次出现的位置，字符I和L视作同一个字符)

4.其余字符按顺序填入方格

5.整理明文，每两个字符组成一对，两相同字符相连时在中间插入X

加密：

1.明文对在同一行时，密文为其右侧的字符

2.明文对在同一列时，密文为其下方的字符

3.明文对在不同行列时，密文为明文对所在正方形的另外两个角点上的字符

解密：

1.密文对在同一行时，明文为其右侧的字符

2.密文对在同一列时，明文为其上方的字符

1. 密文对在不同行列时，明文为密文对所在正方形的另外两个角点上的字符

一次一密介绍

每次加密都使用全新的密钥，每个密钥仅使用一次，是理论上绝对安全的加密方式

2.现代密码

(1)对称密码(单钥密码)

优点：加密快，密钥短，历史悠久

缺点：密钥管理困难，不能进行身份认证和数字签名

序列密码(流密码)：

给定种子通过算法生成密钥流，再将明文位或字符分别与密钥流进行模加法运算

基础：有限状态自动机，二元序列伪随机，线性反馈移位寄存器，m序列

A5-1：

应用：蜂窝电话手机到基站间的通信加密，用户sim卡中有不发生改变的基本密钥K1，在产生会话时基站生成64位随机密钥k，并使用k1加密，发送给用户，用户使用k1解密后得到随机密钥k，随机密钥仅一次通话内有效。

RC4：

算法：

1.初始置换

(1)线性填充256位长的s表s[i]=i

(2)循环使用种子填充256位长的k表k[i]=seed[i%n]

(3)用k表对s表进行初始置换,j=(j+s[i]+k[i])%256(j初始为0)，交换s[i]和s[j]的位置

2.密钥流生成

(1)i，j初始为零

(2)循环加密每一位，i=(i+1)%256,j=(j+s[j])%256，交换s[i]和s[j]，t=(s[i]+s[j])%256

(3)s[t]就是这一位的位密钥，与该位进行异或得到位密文

(2)分组密码(块密码)

将明文划分为若干组(一般64位一组)，再将各分组加密

基础：SP网络，Feistel结构、SPN结构

DES：

衍生：3DES

算法：

1.输入64位的明文数据

2.初始置换IP

3.在轮函数F中进行16轮迭代变换

4.逆置换IP^-1

5.得到64位密文数据

轮函数：

先将64位数据分成左右两部分(L,R)，每轮计算时，记录R成为下一轮的L，同时让R经过扩展表(E盒)、代换表(S盒)、置换表(P盒)的变换再与L进行异或成为下一轮的R

密钥生成算法：

1.初始置换(PC-1)：根据置换表去除校验位并对剩余字符进行置换

2.轮迭代：将初始置换得到的56位字符分左右两部分(C,D)，C，D分别向左循环移动移位得到下一轮的(C,D)，并将本轮(C,D)输入置换表PC-2得到本轮的密钥K(48位)

AES：

衍生：AES-128、AES-192、AES-256

算法：

1.白化(轮密钥加)

2.进行轮迭代(128迭代10轮、192迭代12轮、256迭代14轮)[字节代换、行移位、列混淆、轮密钥加]

3.最后一轮迭代[字节代换、行移位、轮密钥加]

设计原理：

AES将一个字节视作一个系数为各位的七次多项式，而它可以通过在二元域上模一个不可约的八次多项式m(x)得到，选取m(x)为下x8 +x4 + x3+x+1并定义加法为两字节逐位异或，乘法为多项式在模m(x)下相乘的结果。同理，也可以将一个字视作一个系数为各位的三次多项式，m(x)为x4+1。

SM4：

国密算法

(3)非对称密码(双钥密码)

优点：密钥管理简单，能够进行身份认证和数字签名

缺点：运算慢，密钥长，发展较短

RSA:

算法：

1.密钥生成

取不相等的两大素数p，q，令N=p*q，N的lambda函数为lcm(p-1，q-1)，在1到lambdaN之间任取一与lambdaN互素的整数e，再求e在模lambda N下的逆元d，(e,N)为公钥(d,N)为私钥

2.加密算法

密文c=E(m)=m^e(modN)

3.解密算法

明文m=D©=c^d(modN)

另：计算ab(modN)的方法是二元法，先将b写成二进制形式，然后分离每一位(最高位为1号其他位依次编号)。令c[0]=1，c[i]=c[i-1]2*m(b[i]-1)

ElGamal:

算法：

1.密钥生成

取一大素数p，求其生成元g，找一随机数做私钥x，通过g^x%p求公钥y

2.加密算法

密文有两部分，先选一个随机数k，求出c1=gk%p，c2=m*yk%p，密文为(c1，c2)

3.解密算法

直接计算m=c2*(c1x)-1即为明文

另：该算法是不确定性的，同一个密文使用不同的随机数k加密得到的密文不同(同一个密文最多有p-1个明文)，所以k必须保密且仅使用一次，如果使用相同k被攻击者得到，则可通过y^k%p得到私钥

ECC：

算法：

三、数字签名与密钥管理

1.数字签名

RSA：

签名算法：

与加密算法一致，但是使用私钥进行加密

验证算法：

与解密算法一致，但是使用公钥进行解密

ElGamal：

签名算法：

1.任选一个与大素数p的欧拉函数f互素的整数k

2.计算s1=gkmodp，s2=(m-x*s1)*k-1modf

3.(s1,s2)为签名

验证算法：

签名真实的等价条件为ys1*s1s2=gm(mod p)

2.密钥管理

(1)密钥生成

(2)密钥分发

四、密码分析

1.敌手模型

敌手一般假定在发送方与接收方之间，能够截获密文并企图恢复明文

2.攻击场景

攻击性从上到下依次提高

唯密文攻击: 攻击者只能得到若干条同一密钥加密的密文

已知明文攻击: 攻击者能拿到若干同一密钥加密的明密文对

选择明文攻击: 攻击者可以选择一些明文并得到对应的密文

选择密文攻击: 攻击者可以选择一些密文并得到对应的明文

3.攻击方式

(1)穷举攻击

暴力穷举: 穷举全部密钥

字典攻击: 用所有可能的密钥组成一个字典进行穷举

(2)频率分析

利用明文已知的统计规律进行破译

单字符:

最常出现依次为E、T、A、O、I、N、S、H、R、D、L(有效攻击单字符替换和置换密码)

双字符：

最常出现依次为TH、HE、IN、ER、AN、RE、DE、ON、ES、ST、EN、AT、TO、NT、HA、ND(有效攻击多字符替换和置换密码)

三字符：

最常出现依次为THE、ING、AND、HER、ERE、ENT、THA、NTH、WAS、ETH、FOR、DTH(有效攻击多字符替换和置换密码)

(3)长度测试法

两个相同的明文段加密成相同的密文段，则者两个明文段之间的距离大概率是密钥长度的整数倍。当有多个相同段时，密钥长度大概率为段间距的最大公因数的因数。再利用重合指数法就可以验证密钥长度

(4)重合指数法

当猜对密钥时，计算的概率值约为0.065，否则约为0.038

(5)社会工程学

通过对知道算法的人的渗透获得算法

(6)逆向工程学

对含有加密算法的程序进行逆向工程获取其算法

(7)彩虹表攻击

预先计算常见的加密值形成数据库，破解时查表得到明文

(8)确定性分析

利用已知两和数学关系进行破译

(9)差分密码分析

通过分析两个明文差值对密文的影响推断密钥，利用拉格朗日公式的思想，推断加密算法的等价变换破译密码

(10)线性密码分析

寻找给定密码的算法的近似表达破译密码

(11)差分线性分析

将差分密码分析和线性密码分析组合破译

(12)密钥相攻击

根据有某种关系的明密文对进行分析攻击