Skip to content

Latest commit

 

History

History
155 lines (99 loc) · 3.98 KB

Cryptography.md

File metadata and controls

155 lines (99 loc) · 3.98 KB
Raw

Cryptography

Ch1 古典密码

凯撒密码

$$ e_k(x)=(x + 3) mod 26\\ d_k(x)=(x - 3) mod 26 $$

Playfair

(From wikipedia)

  1. 选取一个英文字作密鑰。除去重覆出现的字母。将密鑰的字母逐个逐个加入5×5的矩阵内，剩下的空间将未加入的英文字母依a-z的顺序加入。（将Q去除，或将I和J视作同一字。）
  2. 将要加密的讯息分成两个一组。若组内的字母相同，将X（或Q）插入两字母之间，重新分组（例如 HELLO 将分成 HE LX LO）。若剩下一个字，也加入X字。
  3. 在每组中，找出两个字母在矩阵中的地方。
  • 若两个字母不在同一直行或同一橫列，在矩阵中找出另外两个字母，使这四个字母成为一个长方形的四个角。
  • 若两个字母在同一橫列，取这两个字母右方的字母（若字母在最右方则取最左方的字母）。
  • 若两个字母在同一直行，取这两个字母下方的字母（若字母在最下方则取最上方的字母）。

Hill密码

$$ y=Kx $$

K求逆 $$ \left(\begin{array}{cc}a & b \ c & d\end{array}\right)^{-1}=(a d-b c)^{-1}\left(\begin{array}{cc}d & -b \ -c & a\end{array}\right) $$

维吉尼亚密码

$$ e_k(x_1, x_2, ..., x_m)=(x_1 + k_1, x_2 + k_2, ...,x_m + k_m)\\ d_k(y_1, y_2, ..., y_m)=(y_1 - k_1, y_2 - k_2, ...,y_m - k_m) $$

重合指数 $$ I_{c}(x)=\frac{\sum_{i=0}^{25}\left(\begin{array}{c}f_{i} \ 2\end{array}\right)}{\left(\begin{array}{l}n \ 2\end{array}\right)} \approx \frac{\sum_{i=0}^{25} f_{i}\left(f_{i}-1\right)}{n(n-1)} $$ f为频数，n为字符串长度

英语为0.065，随机为0.038

Ch2 编码与信息论

熵

$$ H(x)=-\Sigma_{x\in X}Pr[x]log_2(Pr[x]) $$

Huffman编码

Ch3 分组密码

AES

DES

CBC & EBC

明文分组在加密之前一定会与前面一个密文分组进行xor运算。因此即使明文分组1和明文分组2的值是相等的，密文分组1和2的值也不一定是相等的。这样一来，ecb模式的缺陷在cbc模式里面就不存在了。

cbc加密过程：

  1. 将要CBC加密的数据分为N个块,每个块为16字节
  2. 随机找一个IV(初始向量),大小为每个块的大小(16字节),用于与第一个块进行异或运算
  3. 将异或运算的结果进行选定的加密方式进行加密
  4. 将得到的第一块密文与第二块明文进行异或运算
  5. 将异或运算的结果进行选定的加密方式进行加密
  6. 将得到的第二块密文与第三块明文进行异或运算
  7. 将异或运算的结果进行选定的加密方式进行加密
  8. 最后得到三块加密获得的密文

​

Ch4 Hash函数

Hash函数属性

  1. 有效性
  2. 抗原像攻击
  3. 抗第二原像攻击
  4. 无碰撞性

Hash函数应用

  • 完整性鉴别
  • 数字签名
  • 口令认证
  • 消息认证码（MAC）
  • 身份认证
  • 数据库保护
  • 零知识证明

生日攻击

消息认证码

分类

  • 基于分组算法
    • 串行的：CBC-MAC，XCBC，OMAC，CMAC
    • 并行的：PMAC，XOR-MAC
    • 认证加密的：OCB，CCM
  • 直接设计的MAC：MAA
  • 基于杂凑算法
  • 基于Universal Hashing

Ch5 公钥密码

RSA

举个栗子

$p=47, q=71$

$n=p*q=3337,\phi(n)=(p-1)(q-1)=3220$

随机选取正整数$d=1019,s.t.0<d<3220 \and gcd(d,3220)=1$

计算$e=d^{-1}mod\phi(n)=79$

则公钥$e=79,n=3220$, 私钥$d=1019$

对消息M=668加密，$C=M^{e}mod n= 668^{79}mod3337=1570$

解密：$M=C^{d}mod n = 1570^{1019}mod 3337=668$

ElGamal

  • 私钥a；
  • 公开部分：大素数$p$，生成元$\alpha$，公钥$\beta=\alpha^\alpha$

签名方法：设$m\in Z$是待签名的消息，秘密随机选取一个整数k，$1\leq k \leq p-2$，而且$(k,p-1)=1$ 计算

$r=\alpha^k(mod p )$

$s=k^{-1}(\alpha-ra)(mod p-1)$

$(m,r,s)$为对消息m的数字签名。

验证方法：对方收到的消息m的数字签名（m,r,s）之后，使用签名者的公钥进行验证，

$(\beta^r)(r^s)=\alpha^m(mod p)$

如果上式成立，那么接受签名，如果不成立则拒绝签名。