密码学备忘录-复习总纲

1. mode of operation

WorkflowAdvantagesLimitations
ECBElectronic Codebook电码本$C_i=E_k(M_i)$简单、主要用于少量分组的传输。没有明密文错误传播当明文分组重复时，密文也重复，易实现统计分析攻击
CBCCipher block chaining密文分组链接$C_i=E_k(M_i \bigoplus{C_{i-1}})$
$C_0=IV$		CBC没有明文错误传播，密文错误传播小需要初始化和保护IV（原因），前面的分组会对后面的产生影响
CFBCiphertext feedback密文反馈$C_i=M_i \bigoplus{E_k(C_{i-1}})$
$C_0=IV$		可作为随机数生成器在错误发生后，错误会在几个区块内传播（但不是无限期地传播）。
OFBOutput feedback输出反馈$O_i=E_k(O_{i-1})$
$C_i=M_i\bigoplus O_{i-1}$
$O_0=IV$		可作为随机数生成器，密文1bit错误只会导致对应的1bit出错接收者和发送者必须保持同步
CTRGalois/Counter计数器$O_i=E_k(i)$
$C_i=M_i\bigoplus O_{i-1}$		速度快对每一分组必须用不同的$K$和计数$i$
AES-XTS--$T$ is tweak, $H$ is a hash function
$C=H(T)\bigoplus{E(K,H(T)\bigoplus{M})}$		高效

2. Symmetric Algorithm

DESAES3DESRC4
BasicIn DES the data block is divided into two halves.In AES the entire data block is processed as a single matrix.EEE/EDERC4生成一个伪随机的比特流（一个密钥流）。这些比特流可以通过与明文比特异或来进行加密
PrincipleDES work on Feistel Cipher structure.AES works on Substitution and Permutation Principle.-PRNG
Plaintext明文按64位进行分组，以比特为单位Plaintext can be of 128,192, or 256，以字节为单位 bits-以字节为单位
Key size密钥长64位，有效密钥长度56（第8、16、24、32、40、48、56、64位是校验位， 使得每个密钥都有奇数个1密钥长度则可以是128，192或256比特EEE的有效密钥长度为168位（56x3），但由于中途相遇攻击，它的有效安全性仅为112位40–2048 bits
Rounds16 rounds10 rounds for 128-bit algo

12 rounds for 192-bit algo

14 rounds for 256-bit algo		-1
Rounds NamesExpansion Permutation, Xor, S-box, P-box, Xor and Swap.Subbytes, Shiftrows, Mix columns, Addroundkeys.-KSA(s-box)/Encryption(PRNG)
Security1. S盒提供了DES的核心安全性—如果没有S盒，密码会是线性的，很容易破解 2. S盒，P置换和E扩张各自满足了混淆扩散原则 3. Avalanche Effect 4. Timing Attacks && Cryptanalysis1. SubBytes提供了非线性代换保证安全性-RC4安全性主要取决于于初始密钥的保密性
SpeedDES is comparatively slower.AES is faster.慢中慢7 cycles per byte on original Pentium

2.1. DES

StepsChanges
Expansion Permutation$R_i$ is expanded by using the expansion permutation,32->48
Key mixing$R_i=R_i\bigoplus{Subkey_i}$48
S-box Substitution1.$R_i$is divided into eight 6-bit pieces before processing by the S-boxes 2.8个S-boxes中的每一个都根据一个非线性转换，以查找表的形式，将其6个输入位替换为4个输出位48->32
P-box Permutation根据映射规则表，把输入的每位映射到新的输出位32
XOR and Swap$R_{i+1}=L_i\bigoplus{R_{i}}$32
Key schedulePC1\PC2（permutation chosen）64->56->48

2.2. AES

Stepslength
SubBytes矩阵中各字节被固定的8位查找表中对应的特定字节所替换，输入的高4-bit对应的值作为行标，低4-bit对应的值作为列标，$S(b_{i,j})=S(a_{i,j})$128
ShiftRows矩阵中每一列的各个字节循环向左方位移，且位移量则随着列数递增而递增（第一行保持不变，第二行循环左移8比特，第三行循环左移16比特，第四行循环左移24比特）128
MixColumnslinear transformation 矩阵乘法128
AddRoundKey$b_{i,j}=K_{i,j}\bigoplus{a_{i,j}}$128
Key expansion若j%4=0,则w[j]=w[j-4]⊕g(w[j-1]),否则w[j]=w[j-4]⊕w[j-1]128

3. Assymetric Algorithm

DifficultyPre-sharePub KeyPri KeyEncryptDecrypt
RSAelies on the practical difficulty of factoring the product of two large prime numbers-{n,e}{n,d}$C=M^e\bmod{n}$$M=C^d\bmod{n}$
Diffie-Hellmanthe difficulty of a certain problem in G related to computing discrete logarithms(DLP).公共原根p/公共质数q in GF(p)-A,By=q^A mod p
传递$y_a$/$y_b$		k=$q^{AB}\bmod{p}$为会话密钥
ElGamalthe difficulty of a certain problem in G related to computing discrete logarithms(DLP).公共原根p/公共质数q in GF(p)p,q,$y_a$/$y_b$A,B$R=q^r$
$S=u*Y_b^r$
传递(R,S)		${S}/{R^B}={u*Y_b^r}/{q^{rB}}
=u=x$
ECC------
ECDH-finding the discrete logarithm of a random elliptic curve element with respect to a publicly known base point is infeasible
“elliptic curve discrete logarithm problem” (ECDLP),比一般的DLP难		椭圆的公共参数（Common parameters of the ellipse）公钥是点 H，H = dG.
$H_A$,$H_B$		私钥是一个范围在 {1,…,n−1} 中的随机整数 d，其中 n 是子群的阶
$d_A$,$d_B$		传递$H_A$,$H_B$$S=d_AH_B$
$=d_B(d_AG)$
$=d_BH_A$
EC ElGamal------

4. Key Exchange and Distribution

4.1. Exchange(Asymmetric)

  • dh
  • ecdh

4.2. Distribution(Quantum)

  • BB84
  • B92
  • E91

5. Hash

5.1. MAC vs HASH VS Digital signature

1
2
3
4
5
6
7
8
9
Cryptographic primitive | Hash |    MAC    | Digital
Security Goal           |      |           | signature
------------------------+------+-----------+-------------
Integrity               |  Yes |    Yes    |   Yes
Authentication          |  No  |    Yes    |   Yes
Non-repudiation         |  No  |    No     |   Yes
------------------------+------+-----------+-------------
Kind of keys            | none | symmetric | asymmetric
                        |      |    keys   |    keys

6. Math

6.1. group vs ring vs field