二、

欧几里得算法、扩展欧几里得算法求模逆：算到余数为+1后把1放到一边，每次替换较小的“因数”（不是系数）

替换密码－
移位密码：m+k mod 26，容易受唯密文攻击
乘法密码：加密c=km mod 26，解密m=k^-1*c mod 26；k要和26互素，只有11种
仿射密码：生成(k1,k2)属于(0,26)×[0,26)。对每一个明文字母，加密：c=k1m+k2 mod 26，解密（就是把m移到一边）：m=k1^-1*(c-k2) mod 26
实际可以把明文写成1×n的一列，前面乘以k1，加上也写成（每个相同的）一列k2。
密钥空间：26*φ(26)=26*12=312。

弱点：明文和密文一一对应，可以根据语言的统计学特性破解。

Hill密码：(c1,c2)=(m1,m2)*{{k1,k2}, {k3,k4}}，解密用密钥乘以逆矩阵。
不能抵抗已知明文攻击：如果是n*n的密钥方阵，需要n个明文-密文对用线代知识解方程就可以解出所有的k。

三、数据加密标准(DES)

加解密过程：64位明文输入，初始置换；56位初始密钥迭代16次产生16个子密钥；两者迭代16次，初始逆置换，输出；解密算法完全相同，只是子密钥反过来使用

四种工作模式：
电子密码本ECB (electronic codebookmode)，简单可并行，相同明文产生相同密文
密码分组链接CBC (cipher blockchaining)：加密无法并行，解密可以。相同明文产生不同密文
密码反馈CFB (cipher feedback)：流密码
输出反馈OFB (output feedback)：流密码，安全性较CFB差

四、RSA加解密

欧拉函数：p为素数
1. phi(p)==p-1
2. phi(p^k)==p^(k-1)*(p-1)
3. 若(m1,m2)==1，则phi(m1m2)==phi(m1)*phi(m2)
4. phi(pq)==phi(p)phi(q)==(p-1)(q-1)

生成RSA密钥：
随机选择大素数p,q，保密。计算pq=n，公开。计算phi(n)，保密。随机选择1<e<phi(n)，公开。计算ed==1 mod phi(n)中的d（扩展欧几里得算法），保密。
加密：消息分组为[0,n-1]的整数m，计算c = m^e mod n，用模幂运算。
解密：m = c^d mod n
安全性：基于大整数的因子分解的困难性。

五、

散列函数：将任意长度的消息M映射成一个固定长度散列值h的函数
散列函数的安全性：强力攻击生日攻击。对两个文件各做m/2处微小变化，分别产生2^(m/2)个m位的hash值，有超过0.5的概率有两者的hash一样

消息鉴别：信源（发送者）识别、验证信息完整性、消息发送的时间。
与密钥相关的单向散列函数通常称为MAC（消息鉴别码）：它利用密钥来生成一个固定长度的短数据块，并将该数据块附加在消息之后。
应用：保护数据交换不受第三方侵犯，但无法保证双方自生欺骗。

区别：消息认证码和散列函数都属于认证函数。但是散列函数用于认证时，通常和数字签名结合使用。

RSA数字签名：与加密一样，只是用的是d签名（加密），e验证；会有存在性伪造，可以对消息Hash后的值签名。

ElGamal签名：
随机生成大素数p，随机生成g和x属于(0,p-1)，计算y=g^x mod p；x为私钥，y为公钥。
签名：对于消息m，随机生成k属于(0,p-1)且k与p-1互素。计算r=g^k mod p，s=(m-xr)k^-1 mod p-1；(r,s)是m的签名
验证：y^r*r^s==g^m mod p

安全性分析基于求离散对数问题的困难性；有存在性伪造。
要注意的问题：1. k不能暴露，否则可根据s求出x。2. 不能使用同一个k对两个不同的消息签名，否则两者的r一样，s可以解方程组算出来。

六、DH密钥交换协议

随机生成大素数p，随机选择1<g<p，公开。
用户Ali随机生成0<A<p-2，用户Bob随机生成B（称为秘密s1和s2）。
分别计算g^A mod p和g^B mod p（称为消息m1和m2），互相发送（当然实际连接时是等Ali算完s1和m1，发请求到了Bob，Bob才开始算s2和m2）。
Ali再计算m2^A mod p，Bob的是m1^B mod p，两者相等都是g^AB mod p（称为K）。
m是公钥，s是私钥。即使公开m1和m2，K仍无法求出。
计算出K后对要加密的数据异或一下就加密了，再异或一下就解密了，因为两者的K相同；也可以使用AES，则K就是AES的密钥。
安全性分析：基于求离散对数问题的困难性；存在中间人攻击。

中间人攻击：Ali把g^A mod p发给W，W生成A'，计算g^A' mod p发给Bob。A和W的密钥就是g^B'^A，B和W的类似。
中间人攻击的防御：利用数字签名可以解决中间人攻击的缺陷。抵御中间人攻击最有效的方法是加入第三方的公证机构，即引入PKI体系中的CA认证中心，提供对公钥的认证。

七、认证和证书

口令机制：最广泛研究和使用，长度为5~8的字符串。
弱点：外部泄露，口令猜测，线路窃听，重放
单向函数：对付线路窃听，消息为id和hash(p)。数据库只存q=hash(p)
对付重放：消息为id、随机数nrv，和g(nrv, q)。其中g两者都知道
一次性口令：防止重放，两边都有一个随机序列产生器dsv。消息为id和g(time, dsv, hash(p, dsv))
询问-应答：与第二种类似，只是用server先发送的nrv，消息就只有id和g(nrv, q)

单向/双向认证：挑战-响应方式。两种方式：共享秘密、公钥体制

安全的主要威胁：假冒、截取、篡改、否认。
PKI是生成、管理、存储、分发和吊销基于公钥密码学的公钥证书所需要的硬件、软件、人员等的综合
数字证书将一个人或其他实体的身份和公开密钥绑定，含有CA的签名；只要信任CA，就能信任他获得的证书
签名私钥绝对不能够作备份和存档，丢失后只需重新生成新的密钥对。验证公钥需要存档