适合考前过知识点的精简版复习资料。

1. cryptography

security attack (e.g. Interruption, Interception, Modification, Fabrication 分别对应 availability 可获得性, Confidentiality 保密性, Integrity 完整性, Authentication 认证性)

来自外部的攻击：passive threats（数据保密） / active threats（消息认证）

来自内部的攻击：发送方否认 / 接收方否认（数字签名）

open / closed design model

simple encryption method: shift, affine, substitution, vigenere, vernam (one-time-pad)

A cryptosystem has (at least) : Plaintext / Secret Key / Ciphertext / Encryption Algorithm / Decryption Algorithm

加密算法分类

  • operation type (binary/integer arithemetic)
  • # of keys (对称/非对称)
  • how plaintext is processed (block cipher/stream cipher)

Key Distribution Center (KDC)

  • 干什么？和用户之间的联系？
  • master key / temporary session key

2. symmetric encrption

与非对称加密对比，两者的优缺点 + 使用时需要注意的地方

Generic Example of Block Encryption (P变换和S变换 for one loop)

Feistel Cipher Structure (many loops)

DES

注意每个数字 (input和output都是64位, key 一共是56位 {减去8位奇偶校验位的结果}, 但每轮生成48位的 subkey, 总共有16轮, block size 为 1byte)

每一轮加密解密过程如下：

其中F变换为：expansion(32 bit -> 48 bit 和 subkey 保持一致, 不是直接加0, 有一定的策略) -> Rn 异或 Kn -> S-Box Substitution (32 bit 每6位产生4位的值) -> P-box Permutation (32 bit 使得下一轮顺序颠倒, 增强安全性)

涉及到的matrix: E(expansion) / S(compression) / P(permuation for each loop) / IP(initial pemutation) / IP-1(inverse initial pemutation)

整个框架：

上图包含了 subkey generation 的过程，涉及到的matrix: permutation choice 1 (7*8的选择)/ permutation choice 2 (4*8的选择)

暴力破解平均只需要 2^55，对于现代算力来说太弱了，并且字母 ascii 码只有7位，使得其变得更加脆弱 -> 新的解决方案 3DES -> 后来发现还是不太好 (Meet-in-the-middle ATTACK, slow, block size is too short)，于是产生了 AES

DES Variants

AES Rijndael

流程：（1）字节代换（AES的S盒）（2）行位移（3）列混淆（4）轮密钥加

下图来自于 博客, 侵删。具体操作步骤可结合该博客和我的前一篇博文。【列混淆 以前看懂过，现在又搞不明白了，暂且搁置】

优点：硬件软件的实现都有提升（Atomic operations / small tables in ROM / barrel-shifting registers / fast table lookup routine / Considerable parallelism）

Modes of Operation 可参考维基百科

ECB / CBC / OFB / CFB / CTR / MAC 记忆每种操作的公式以及优缺点

3. hash

性质：Takes on input of any size / Produces fixed-length output / Easy to compute (efficient) / One-Way-ness Weak Collision-Resistance / Strong Collision-Resistance

Merkle-Damgard construction

$$ h_i = f(M_i, h_{i-1}) h_0=IV $$

Compression function f(): fixed-size output

Birthday Paradox

CHF from a Block Cipher：Hi = E ( Mi, Hi-1 ), H0= 0 Davies-Meyer CHF：Hi = Hi-1 ⊕ E ( Mi, Hi-1 ), H0= 0

-》Final ciphertext Hp is the hash output

Hash Func Examples：MD5 (defunct 失灵的) / SHA-1(weak) / SHA-256(SHA-2 family 仍在使用) / SHA-3

Message Authentication：哈希函数除了能保证消息的完整性，还能应用于消息认证

消息认证3种方法：摘自引用2

1.基于消息加密的认证

认证是通过双方都知道的密钥，来解密接收到的接收到的消息。如果解密后的结果是一堆乱码，则说明消息不合法，不是对方发送的。

2.基于消息认证码(MAC)的认证

一般来说发送方发送 M + E(K, H(M)) 给接收方，存在的问题是可能存在哈希碰撞被hacker发现可以伪造 (forgery) 数据，可以考虑 H(K || M)

Just computing and appending H(m) to m is enough for integrity but not for authenticity -> 【？】有点无法理解，如果只有 H(m) 的话那不是任何人都能篡改吗，为什么还能提供完整性的证明？

如何提供 authenticity (消息的可靠性和真实性)：

Prefix: MAC=H(K || M) 基本上可行，但是 allows concatenation with arbitrary message H(K || M || M’)

Suffix: MAC=H(M || K) 会比前者可靠，但是 what if M’ is found such that H(M)=H(M’)

HMAC: MAC=H(K || H(K || M)) 被提出，应用在 IP security / TLS / IPSec 等领域

❓ 这部分需要后续跟进，对 integrity 和 authenticity 更精确的定义，以及为什么Prefix / Suffix / HMAC 的表现是这样？

3.基于哈希函数的认证

4. number theory

判断有限代数结构（Finite Algebraic Structures）

  1. Group (G,@): closure / associativity / identity / inverse
  2. Abelian 阿贝尔群/交换群: commutativity
  3. Cyclic: group generator G=<g>
  4. Order of a group: the size of set G |G| or #{G} or ord(G)
  5. Group (G,@) is finite if ord(G) is finite
  6. Rings (R, +, *)： (R, +) is an Abelian group (identity=0) & closure / associativity / identity=1 / distribution
  7. Monoid: associative / identity
  8. Fields (F, +, *): Commutative Ring + Inverse(*)
  9. Subgroup (G,@): H is a subset of G & (H, @) is a group

Some cases hard to understand:

  1. Integers mod(p) (where p is Prime) under Multiplication -> Nonzero integers mod p -> 这个集合包含所有模p等于1,2,…,(p-1)的数
  2. non-zero integers mod N = {1 …, x, … n-1} such that GCD(x, N)=1 -> 这个集合包含所有模n等于1,2,…,(n-1)的数，和前一个的区别在于这里 N 不一定是质数，任何数都可以

extended euclidian algorithm IRTQ法求逆

chinese remainder theorem(CRT) 可用于RSA的优化

5. asymmetric encryption

Encryption & Decryption / Digital signatures （Provides authentication (认证，是不是对方发的？), integrity (消息有没有被中间人恶意篡改？), and non-repudiation (不可抵赖的 😭 考试有填空只记得中文了)）

Key exchange: Diffie–Hellman key exchange

RSA：记忆流程 / 理解可以解密的原理 / 可行性的前提，为什么安全 / 复杂度分析，如何优化 Square-and-Multiply(快速幂) Speeding up RSA Decryption 利用中国剩余定理 / why 2 or more parties cannot share the same n / RSA Signature Scheme 很不安全

El Gamal：记忆流程 / 理解可以解密的原理 / 可行性的前提，为什么安全 / 优缺点 / El Gamal Signature 安全性，对存在性伪造的防范？看起来证明有点复杂 /

6. cryptographic protocol

Zero-knowledge proof 字面上的意思，不泄露秘密地证明自己 / 漆黑的洞穴

Fiat-Shamir Identification Scheme

通常会轮询个 20, 30, or log n 次，保证 Prover (Eve) 不能事先知道 query 是0还是1

还没了解怎么证明这个协议是 zero-knowledge 的？

7. authentication/identification

Secure Protocols：protocols / entities parties / rounds / messages 定义

Basis for Authentication：Something you know / Something you have / Something you are （好吧，考试又挂了，意思是差不多不知道给不给分）

具体场景 / 分析每种方式的优点和局限性

Authentication (Protocols)：Protocol ap1.0 - Protocol ap2.0 - Protocol ap3.0 - Protocol ap3.1 - Protocol ap4.0 - Protocol ap5.0

The Protocol (Nonces)：除了使用key外，还可以使用 sequence 和 time-stamps

8. Key Distribution

Conventional (Secret) key distribution / Public key distribution

Trusted Intermediaries

Key Distribution Center (KDC) 也叫 Trusted Third Part (TTP)

Reference

  1. UCI CS134 课件（mainly）
  2. 现代密码学复习要点总结（谷利泽）