一、古典密码
单表代换密码
1、置换密码
（1）列置换
（2）周期置换
2、代换密码
①加法密码：
用明文字母在字母表中后面第k个字母来代替
凯撒密码——历史上第一个密码技术
③密钥词组代替密码
多表代换密码
①Vernam密码
明文、密文、密钥都表示为二进制位
用密钥控制生成矩阵，然后每两个字母为单位进行代换
③Hill密码（乘积密码）
建立在矩阵相乘的基础上
二、背包密码
背包问题：超递增背包
如递增序列为1 4 6 13 27 52
首先背包质量与最大元素比较，若背包质量大，则该元素在背包中，用背包质量减去该元素质量，然后再比较下一个，以此类推，如果背包质量小，则直接比较下一个，一次类推
例子：
如背包总重量为70，重量序列为｛1，4，6，13，27，52｝
最大质量52小于70，因此52在此背包中
下一个重量27大于70-52=18，因此27不在背包中
继续以此类推，直到总重量减少到0或者无法继续减少，则表示已经找到
此处对应的明文是110101
从密钥构造公钥
选择一个超递增序列为密钥｛2，3，6，13，27，52｝
对每一个值乘以一个数n，对m求余
作为模的数应大于序列中所有数的和
此处设m=107, n与m互素， 取n=29
则背包问题序列为：
2*29 mod 107 = 58
3*29 mod 107 = 87
6*29 mod 107 = 67
······
最终得到的公钥序列为：｛58，87，67，56，34，10｝
要对一个二进制消息进行教秘，先将其分成长度和背包序列相同的块，1表示在包内，0则表示不在
如消息：011001 100101 000101
公钥：｛58，87，67，56，34，10｝
则
011001：87+67+10=164
100101：58+56+10=124
000101：56+10=66
密文为164，124，66
解密
先计算n^-1（乘法逆元）满足n*n^-1 mod m = 1
将密文的每一个值与n^-1相乘模m，然后用私钥来求解
继续用上个例子
m=107, n=29, 私钥｛2，3，6，13，27，52｝密文为164，124，66
计算出n^-1=48
则密文要与48相乘模107
164*48 mod 107=61=3+6+52 对应011001
124*48 mod 107=67=2+13+52 对应100101
66*48 mod 107=65 = 13+52 对应000101
RSA
需要懂得三部分知识：
互质关系：两个正整数只有1为公因子，没有其他公因子，不是质数的两个数也可以构成互质关系
欧拉公式：φ(n)为比n小但与n互素的正整数个数，称为n的欧拉函数。对任一素数p, 有φ(n)＝p-1，而对于两个不同的素数p和q，则对n=pq，可以证明φ(n)＝φ(pq)=(p-1)(q-1)=φ(p)*φ(q)
模反元素：求模反元素（逆元），可以用辗转相除法，上面已经有过说明
RSA算法如下：
选择两个素数p和q，n= p*q， φ(n)=(p-1)*(q-1),选择整数e,使gcd(φ(n), e)=1, 1<e<φ(n), 计算逆元d= e^-1 mod φ(n)， 得到公钥KU={e, n}， 私钥= {d, n}。
加密：明文M, 密文：C=m^e mod n
解密：密文C， 明文：M=C^d mod n
如A要发送信息9726给B
首先由B生成密钥，假设选择了两个素数p=101和q=113， 计算的n=p*q=101*103=11413， φ(n) =(q-1)*(p-1)=11200， e与 φ(n)没有公因子，选择e为3533， 算得d=e^-1 =3533^-1 mod 11200 = 6597
得到公钥=｛3533， 11413｝， 私钥=｛6597， 11413｝
A得到公钥将明文加密9726^3533 mod 11413 = 5761，此为密文
当B收到密文时，就用私钥进行解密
5761^6597 mod 11413 = 9726得到信息