密碼學概論–陳榮傑

NCTU CS
回主頁

Syllabus

Course

Ch0

3 related research areas in CS and EE

  1. Information Theory
  2. Coding Theory
  3. Cryptography

Why encode data?

  1. efficiency (ex. Hoffman Code)
  2. error detection / correction (ex. binary [5,3]-code -> codewords)
  3. secrecy / authentitation (ex. DES)
  • Cryptology (保密學)
    • Cryptography
    • Cryptanalysis
  • Cryptography (密碼學)
    • study and allpicaty of secure
  • Cryptanalysis (破密學)

two types of Cryptosystems

  • symmetric-key (ency-key = dency-key)
    • block cipher (塊狀加密)
      key 針對 分塊的 text 分別加密
      e.g. AES, DES
    • stream cipher (串流加密)
      key 以某方法(ex. 除質數，找小數)產生無窮字串，利用字串直接對整串 text 加密
      e.g. RC4
  • asymmetric-key (public key != private key)
    • ciphertext (密文)
      \(c = m^e \mod n\)
    • plaintext (明文)
      \(m = c^d \mod n\)
      \(d = e^{-1} mod \phi(n)\)
      \(\phi(n) = (p-1)(q-1)\)

A public-key cryptosystem is usually based on a hard math problem!
3 hard math problems

  1. Factorigation \(n = p * q\)
  2. Discrete log \(g^x\)
  3. Closest vector of a lattice (最接近格子點)
    給 n 個 vector 代表座標軸及其單位座標，給 P(a,b)，求最接近的格子點 ex.
    \[ base= \begin{bmatrix} 3 & 0\\ 0 & 2 \end{bmatrix} \]
    and
    \[P = (100,210)\]
    Find closest point \(Q\) (lattice)

Ch1 Classical Cryptography

Introduction: Simple Cryptosystems

A cryptosystem is a five-tuple (P,C,K,E,D) satisfies

  • P: finite set of possible plaintexts (明文)
  • C finite set of possible ciphertexts (密文)
  • K: keyspace, finite set of possible keys
  • for each K, ther is an encryption (加密) rule \(e_k\) and corresponding decryption (解密) rule \(d_k\)

a and b are integers, m is a positive integer
congruece: \(a \equiv b \mod m\) if m divides \(b - a\)

\(Z_m = set of \{0, 1, ..., m-1\}\)

  • with 2 operations + and *
  • \(10 + 20 = 4 \ in \ Z_{26} (10+20\mod26=4)\)
  • \(10*20 = 18 \ in \ Z_{26} (10*20\mod26=18)\)

Shift Cipher (平移)

  • \(P = C = K = Z_{26}\)
  • \(K,x,y \in Z_{26}\)
  • \(e_k(x) = (x + K) \mod 26\)
  • \(d_k(y) = (y - K) \mod 26\)

Suppose \(K=11\)

  • Plaintext: student
  • Ciphertext: DEFOPZE

Subsititution (取代)

\(e_{\pi}(x) function\)

Affine Cipher

模函式
affine function
\(f(x) = (ax + b) \mod m\)
(\(\gcd(a,m) = 1\))

  • \(\phi(m)\): 小於 m 中與 m 互質的個數
  • \(\phi(m) = p^e - p^{e-1}\)
  • \(\phi(mn) = \phi(m)\phi(n)\)
  • e.g. \(e_K(x) = (7x+3)\mod26\)

Vigenere Cipher

eg. \(key = (2,8,15,7)\)
加一個固定的質(序列)，加完後重頭加

Hill Cipher

key=可逆矩陣
\(e_k(x)=xk\)
\(c_k(y)=yk^{-1}\)

Permutation Cipher

字串中的相對位置改變

第一個跑到第三個
第二個跑到第五個
…

Cryptanalysis (密碼破密)

Kerckhoffs' principle
你一定要告訴我你怎們加密，你一定要告歲我 key

Attech module

  • ciphertext only attack (最難的，僅知已加密文字（即密文）的情況下進行攻擊)
  • known plaintext attack (攻擊者掌握了 "某段" 明文 x 和對應密文 y)
  • chosen plaintext attack (指定的明文要他加密，我再回推 => 可以指定任意明文)
  • chosen ciphertext attack (給密文，請他給相對的明文)

解密:

  1. 暴力找
    \[ y = ax + b \\ x = a^{-1}y - b \]
  2. 用經驗找常見的字母或字串先 try (做字典)
  3. find m
    • Index of coincidence of x (Friedman)
      • 先檢查 m=? (用 x 算出來大概接近 0.06)
      • 每 m 個抓出來，可算出 swift 了多少格
      • 找出 block shift 了多少
    • Kasaski
      • 找出類似字串的距離，m 可能等於其距離的公因數
    • 找 swift
  4. Hill Cipher
    • \(\phi(n)\) 1~n 間跟 n 互質的個數
      • \(\phi(p) = p-1\)
      • \(\phi(p^2) = p^2 - p\)
      • \(\phi(p^k) = p^k - p^{k=1}\)
      • \(\phi(pq) = (p-1)(q-1)\) \((\gcd(m,n) = 1)\)
      • \(\phi(26) = \phi(2) * \phi(13) = 12\)
    • \(3^{-1} = 9 (mod 26)\)
    • \(m \geq 2\) is an integer
    • \(P = C = (Z_{26})^m\)
    • k = {m*m invertible matrices over Z_26}
    • for a key K
      • \(e_k(x) = xK\)
      • \(d_k(y) = yK^{-1}\)
    • Hill Cipher is difficult to break with a ciphertext-only attack
    • known plaintext attack
      • 需有曾經看過的加密 (知道明文a與加密後的密文b)
      • 用反舉證的概念
      • \(a = b * k\)
        \[ \begin{bmatrix} \end{bmatrix} \]

DES

Keysize: 56
blocksize: 64

Feistel cipher:

  1. 分一半(32 + 32)
  2. 每一次 round 用原來的 key (56 bit) 產生 subkey (4 8bit)
  3. IP(\(IP(x) = L_0R_0\)): initial permutation
  4. 位置調動
    • \(L_{new} = R_{old}\)
    • \(R_{new} = L_{old} \oplus f(R_{old}\& key)\)
  5. function (bent functions)
    \[f: \{0,1\}^{32} * \{1,0\}\&{48} → \{0,1\}^{32}\]

2-DES
Meet in the middle attack 可解 DES

Asymmetric key (public key)

DES (Secret key)
RSA (public/private key)

  • function
    • authentication
    • confidentiatiality
  • Used
    • Asymmetric
    • Certificate
    • PKI (public key infrastructure)
    • Secret
    • Authentication 確實是某人送出的
    • Key exchange
    • Digital signature
    • encryption/decryption
  • Encryption
    • with public
    • with private key
  • term
    • plaintext: 明文
    • encryption algo: 加密 algo
    • cyphertext
    • decryption algo
  • msg -> your private en -> his public en -> his private de -> your public de -> msg

RSA

Select p, q (big prime, p != q)
n = p * q
\(\phi(n)=(p-1)(q-1)\)
select e s.t. \(gcd(\phi(n),e)=1, 1<e<\phi(n)\)
\(d==e^{-1}(mod\phi(n))\)
Public: {e,n}
Private: {d,n}

  • encryption
    • Plaintext M
    • Ciphertext: \(C = M^e \mod n\)
  • decryption
    • Ciphertext: C
    • Plaintext: \(M = C^d \mod n\)

群環體

Group

  • +, *
  • +, * 單位元素
  • +, * 反元素
  • 封閉性
  • 交換律, 結合律…

四元數 (Quarternion)

  • a + bi + cj + dk
  • \(-1 = i^2 = j^2 = k^2\)
  • 沒有交換性 (i * j = -j * i)
  • 八元數 (Octonion) // …數學家真的太無聊了吧 XD
  1. (G, *) is a group
    • \(Z_p^* = Z_p - 0 = \{1,2,3,...,p-1\}\)
    • * is closed
    • * is associative
    • \(\exists\) identity \(e \in G\)
    • \(\exists a^{-1} \in G\) for any \(a \in G\), s.t. \(a*a^{-1} = a^{-1}*a = e\)
    • if G is commutative, G is called a commutative group(abelian group)
  2. (G, +, *) is a ring
    • (G, +) is abelian group
    • * is closed
    • * is associative
    • 分配律: (a+b)*c = (a*c) + (b*c)
  3. (G, +, *) is a field
    • (G, +, *) is a ring
    • (G\{0}, *) is a abelian group, where 0 is 加法單位元素
    • finite / infinite
      Why \(Z_p\) is a field
  • because \(\forall{a} \in Z_p, \exists{a^{-1}}\)
  • how to find \(a^{-a}\) => 輾轉相除法

Finite Field

  • Example
    • Z5
    • \(2/4 = 2/4^{-1}=2\times 4 = 3\)
    • \((x+1)/(x^2+x+1) = (x+1)\times (x^2+x+1)^{-1}\)
    • e.g. \(Z_{2^2}, x^2+1=(x+1)^2\)
    • \(Z_4\) is not a field (4 is not prime) (乘法沒封閉性)
    • \(F_8\) is a field (but ring)

Fermat's and Euler's Theorems

Carmichael function
Fermat Theorems
\[a^{p-1}\equiv1\pmod p\]
pf:

Euler Theorems
\[a^{\phi(n)}\equiv1\pmod n (\phi(n): 與n互質的數)\]
e.g. \(747^100802 \bmod1000 =?\)

ϕ(1000)=ϕ(2^3 5^3)=ϕ(2^3)ϕ(5^3)=4*100=400

How to get ϕ

  1. if p is prime: \(\phi(p^n)=p^n-p^{n-1}\)
  2. if gcd(m,n) = 1: \(\phi(mn)=\phi(m)\phi(n)\)

CRT 中國餘數定理

\(x\equiv a_1\pmod{m_1}\)
\(x\equiv a_2\pmod{m_2}\)
…
\(x\equiv a_n\pmod{m_n}\)
if \(m_i\) 兩兩互質 =>
\(\exists!x\bmod M=m_1m_2...m_n\)
\[x=(\sum a_iM_i(M_i^{-1}\bmod m_i)) \pmod M\]
\[M_i=\frac{M}{m_i}\]
pf:
若 m 沒有互質, 將 m 質因數分解即可

RSA proof

M -> (e_A, n_A)
C = M^e \mod n
M = C^d \mod n

Why works
By Eulers
If gdc(a,n) = 1, htena=1 Imod n)
… 漏掉好多多多多多…

SHA-X

BirthDay paradox

n 個人中，有人同一天生日的機率是多少？
都在不同天生日：\(1\times(1-\frac{1}{365})\times(1-\frac{2}{365})\times...\)
有衝突的：\(1-[1\times(1-\frac{1}{365})\times(1-\frac{2}{365})\times...]=1-e^{\frac{-r^2}{2N}}\)

  • 生日攻擊法
    • 要幾次 hashes 可以得到 collision

SHA-1

  • Preimage(one-way property)
    • 給 h(x) 找一個 x 都很難(x 會有無限多個)
  • Second preimage(weak collision resistant)
    • 給定 x，找到 y != x, s.t. h(x) == h(y) 很難
  • Collision(strong collision resistant)
    • 隨便要找出 x, y 使得 h(x) == h(y)
  • 難度

訊息傳遞驗證

  1. 明文 M 及 Hash(M) 一起加密傳送
  2. M 及 加密後的 Hash(M) 一起傳送
  3. M 及 Hash(共有secart) 後再一起 Hash 後傳送
  4. M 及 Hash(secart) 一起 Hash 後，再加密傳送
  • 加密通常都對 hash 完的值做，以減少複雜度

數位簽章

Compression function

  • IV: 一開始給的，例如 前 n 個質數的 sqrt
  • \(CV_i = f(Y_{i-1},CV_{i-1})\)
  • 只要 f() 可以打亂即可，例如：一開始 f() 是用 DES
  • 執行：
    1. 原值 + padding + length => 1024bit 的倍數
      • padding: 100000…0
      • length: 原值的長度
    2. 進 function
    3. 得到 hash(msg)

Primality test

  • \(Z_n^*\):所有跟 n 互質的數的集合
  • \(\phi(n) = N(n) = \Pi(質因數次方-1)\)
  • 費馬小定理
  • 尤拉定理
  • order: (?)
    1. ord(n): \(n^o = 1 \mod k\) 中最小的 o
  • generator
  • 中國餘數定理
  • Square-and-Multipl

Quadratic Residue

a 是 quadratic residue modulo n，代表 \(a\in Z_n^*\) 而且 a 的開根號也是 \(Z_n^*\)

  • \(Z_n=Q_n U \overline{Q_n}\)
  • p > 2 is prime and \(α\) is a generator of \(Z_p^*\)
    • \(\alpha\) 的偶數次方會是 \(Q_p\)，\(\alpha\)的奇數次方會是 \(\overline{Q_p}\)
    • \(N(Q_p) = N(\bar{Q_p})=\frac1 2\)
    • 如果 \(a\in Q_p\)，則 \(x^2=a\) 會有兩個解(一正一負)
    • \(a^\frac{p-1}{2}=-1\mod p\)
  • 定義 Legendre symbol：\(\begin{pmatrix}\frac{a}{p}\end{pmatrix}\)
  • Euler's criterion:
    • \((\frac{a}{p})=a^{\frac{p-1}{2}}\mod p\)
    • e.g. \((\frac{3}{23})=\frac{23-1}{2}=1011_2\)
  • Jacobi symbol\((\frac{a}{n})\):
    • n > 2 is an odd integer, \(p_i\) is prime and \(n=p_1^{e_1}p_2^{e_2}...p_n^{e_n}\)
      …

Prime numbers

  • 如何產生質數
    1. 隨機產生奇數，prime test
    2. 質數離散性：\(\Pi(x)~\frac{x}{\ln(x)}\) (\(\Pi\)：質數個數)
  • Solovay-Strassen primality test
    1. 原始方法：測 \([2,\sqrt n]\) 有沒有 n 的因數

Miller-Rabin

  • Fact
    • P: odd prime
    • p-1 = 2^sr, where r is odd
    • For all \(a\in N\) & \(gcd(a,p)=1\)
    • then \(a^r=1\mod n\)
    • or \(a^{2^j r}=-1\mod n\)

SHA3

  • 2006, NIST
  • 作法
    1. 將 msg 用 10* 的 padding 方式
  • padding
    • simple: \(10*0\)
    • multirate: \(10*1\)
      …

MAC

Message authentication code
有 key 的 hash

  • M H(M) => M' H(M') => 一般的 hash 無法認證

  • 專詞

    • Disclosure: 資料洩漏
    • Traffic analysis: 分析資料送出頻率
    • Masquerade: 資料認證 (防止第三者串改package)
    • Content modification: 內容竄改
    • Sequence modification: 順序竄改
    • Timing modification: Delay
    • Source repudiation: 寄件者拒絕承認(數位簽章)
    • Destination repudiation: 接收方確認收到

  • 認證作法

    • Hash function
    • Message encryption
    • Message authentication code(MAC)

  • MAC

    • Confidentiality: 機密信
    • Authentication: 確認信

    • 對稱式：加密 + 認證
    • 公鑰：加密
    • 私鑰：認證
    • 公私鑰：加密 + 認證

  • HMAC

    • Base on Hash
    • …

  • CMAC

    • 用 block cypher

數位簽章

  • 用私鑰對 hash(msg) 簽章 => S
  • 用公鑰確認 public_key(S) 產生的值是否與 hash(msg) 相同
  • 可是要如何確認某人的 pub_key 確實是他的？ => 第三方公證人
  • Attack:
    • (public)Key-only attack
      • 攻擊者只有 pub_key 卻可以產生 msg & Sign(msg)
    • known message attack
    • chosen message attack
      • C 把 msg 拿去請 A 簽章
    • Adaptive chosen message attack
  • Forgeries(M 和 簽章後的 M)
    • Existential forgery
    • Selective forgery

Secret Sharing Schemes

n 個人或以上才能開鎖

  • Secret Splitting
    • 將秘密分為 k 份，每人持一份
    • 用 mod 分
  • Threshold Schemes
    • 兩點決定一條線
    • 把秘密放在線上 (ex. 某個係數上)
    • e.g. 兩人各持有一點 (x,y)，key 就是 斜率
    • Vandermonde matrix
  • alternative approach
    • 利用 拉格朗日插值法 快速找到 threshold schemes
  • 階乘
    • 權限不同
    • e.g. 一個 A == 兩個 B
    • 多給幾把 key to 比較有權的人
    • or say 小於一定程度的 key count 就不能有權限
  • VSS (Verifiable Secret Sharing)
    • 參加者可以驗證
  • PVSS (publicly verifiable secret sharing)
    • 外面的人可以驗證
    • i.g. e-Vote, e-Cash

Blind Signature

第三者做簽章 (不是 sender)

  • i.g. 網路投票，不是選民簽章，而是選委會簽章
  • 簽章的人不知道她在幫誰簽章

  1. blinding: \(H(m)\times r^e\) (r 是 random value, e 是選委會的 public key)
  2. Singing: 選委會用自己的 private key 簽章 \((H(m)\times r^e)^d = H(m)^d\times r\)
  3. Unblinding: 選民把傳回來的值再除以 r => \(H(m)^d\) 也就是有簽章的 \(H(m)\)
  4. 最後投票，機器可以認出簽章

r 的用意是為了讓選委會不知道你投給誰

BitCoin

HW

Exam

作業跟考試有 8成 一樣，再加一兩題額外的題目

Select a repo