[IT-Security-1] 非對稱式密碼學 Asymmetric Cryptography

Asymmetric Cryptography 

Notes from RWTH Aachen University course 
“IT security 1” Wintersemester 2019/20
professor: Meyer, Ulrike Michaela

RSA

• Asymmetric加密機制
• 變數長度通常小於key
• 但加密結果與key長度相同
• 較少用在長訊息的加密
• 運用：
• 加密對稱key
• 加密authentication challenges
• digital signature
• public key:
• 選擇兩個質數 $p,q$
• 計算 $n$$=$$pq$
• 在 $\phi($$n$$)$ 中選擇 $e$
• public key: $(n,e)$
• private key:
• 計算 $d$，其中 $e$$d$$=1\ mod$$\ \phi(n)$
• private key: $d$

Euler’s Theorem

• $\text{for any }a\in\mathbb{Z}_n^*$
  $a^{\phi(n)}=1\ \text{mod}\ n$
• idea: 循環群，$\phi(n)$是元素個數
• 一般化：
  $\text{for any }a\in$$\mathbb{Z}_n$$\text{ in case }n=pq$
  $a^{\phi(n)+1}=a\ \text{mod}\ n$
  $a$ 不必與 $n$ 互值

RSA的安全性

• 分解 $n=pq\ \Leftrightarrow$ 計算 $\phi(n) \Leftrightarrow$ 計算 $d$
• 目前還不知道有沒有方法：如果不知道 $d$ 仍能破解RSA加解密
• 建議用2048 bit，即p,q為1024 bit

PKCS (Public Key Cryptography Standard)

• 定義兩個RSA的encoding方法：
• RSAES-PKCS1-v1_5
• RSAES-OAEP

OAEP = Optimal Asymmetric Encryption Padding

RSAES = RSA Encryption Scheme

• 兩者定義如何pad訊息為更長的訊息

為什麼需要PKCS?

• 確認明文是合法的、可辨識的
• 避免被竄改密文

為什麼需要OAEP?

• 使得密文具有隨機性(有random seed)

RSA後門

• 製造RSA的key
• Naïve RSA backdoor
• 固定prime $p$，選擇隨機 $q$，計算出公開 $n$
• 此backdoor可以用 $p$ 找到 $d$，為什麼?
• 計算 $q=p^{-1}n$
• 計算 $d$， $e$ 在 $\phi(n)$ 中的inverse
• 被external攻擊：
• 取得兩個public key $(n,e),(n',e')$即可攻擊
• 因為 $p$ 固定，則 $gcd(n,n')=p$
• 則可用上列的方式取得 $d,d'$
• Better RSA backdoor
• 製造商擁有key pair
  public key: $(E,N)$
  private key: $D$
• 隨機選取 $p,q$
• 計算 $e=p^E\text{ mod }N$
  檢查是否可逆，某則重新選取 $p$
• 被external攻擊：
• 若知道 $(e,n)$
• 則計算 $e^D\text{ mod }N=p$，用此計算 $d$
• 因為 $e=p^E\text{ mod }N$
• $e^D=p^{ED}\text{ mod }N=p^{\phi(N)+1}\text{ mod }N=p\text{ mod }N$
• 需要製造商的private key才有辦法攻擊
• Naïve RSA signature
• 跟Naïve RSA生成key方式相同
• 易受 existential forgery 攻擊
• 攻擊者隨機選擇 $s$$\in\mathbb{Z}_n$，宣稱是Alice對 $m$ 生成的signature：$m$$:=$$s$$^e\text{ mod }n$
• 因為 $m$$^d=$$s$$^{ed}\text{ mod }n=$$s$$\text{ mod }n$
• 很容易生成pair $(m,s)$ 使得 $s$ 是 $m$ 的合法簽章
• 但是很難對有意義的 $m$ 生成 $s$

existential forgery 是針對 digital signature 或 MAC 攻擊的詞

• RSA是 multiplicative homomorphic(乘法同態)

加密後再相乘等於相乘後再加密

• $s:=s_1s_2=m_1^dm_2^d=(m_1m_2)^d\text{ mod }n$
• $s$ 仍是 $m_1m_2$ 的合法簽章
• 安全的RSA signature
• 簽章前先用已知的hash function
• $s=h(m)^d\text{ mod }n$
• 解決
• existential forgery
  因為pre-image resistant，難找到 $s^e=h(m)$
• multiplicative homomorphic
  因為pre-image resistant，難找到$h(m)=h(m_1)h(m_2)$
• 對DSS, ECDSA簽章機制仍適用
• 簽章的訊息若過長，hash之後能縮短
• PKCS
• RSA的兩個encoding scheme
• RSASSA-PSS
• RSASSA-PKCS1-v1_5
• 用digital signature的好處：
• MAC無法為 public 提供authenticity
• Non-repudiation 簽章人無法否認自己傳送過這個訊息
• RSA攻擊的結果：
• Total break: 取得私鑰
• Universal forgery: 偽造所有訊息簽章
• Selective forgery: 偽造選擇的訊息簽章
• Existential forgery: 偽造沒有意義的訊息的簽章

DSS (Digital Signature Standard)

• 用DSA(Digital Sianature Algorithm)
• 建立在離散對數問題(discrete logarithm problem)的困難度
• 給定 $Y,p,g: Y=g^x\text{ mod }p$，難以找到 $x$
• Key generation
  $p$: 1024 bit
  $q$: 160 bit
  $q$$|($$p$$-1)$
• 隨機選擇 $x$$\in\mathbb{Z}_p^*$ 使得$x$$^{\frac{p-1}{q}}\text{ mod }p\neq 1$
  設 $g$$:=$$x$$^{\frac{p-1}{q}}\text{ mod }p$
• 隨機選擇 $a$ $\in\{1...,$ $q$ $-1\}$
  計算 $A$$=$$g$$^a$$\text{ mod }$$p$
• public key:
  $($$p$$,$ $q$$,$ $g$$,$ $A$$)$
• private key:
  $a$

支援的bitlength:
1024/160
2048/224
2048/256
3072/256

• Signature generation
• 隨機選擇 $k$ $\in\{1...,$ $q$ $-1\}$
  計算
  $r$ $=($$g$$^k$$\text{ mod }$$p$$)\text{ mod }$$q$
  $s$ $=($$k$$^{-1}(h(m)+$$a$$r$$))\text{ where }$$k^{-1}$$\text{ is the inverse of }$$k$$\text{ mod }$$q$
• signature on $m$ is the pair $($$r$$,$ $s$$)$

指數160 bit較有效率
$k$ 對每個訊息需不同

為何需要不同的 $k$

• $s_1=(k^{-1}(h(m_1)+ar))\text{ mod }q$
  $s_2=(k^{-1}(h(m_2)+ar))\text{ mod }q$
• $s_1-s_2$$=k^{-1}(h(m_1)-h(m_2))\text{ mod }q$
  可得 $k$
• 則private key $a$ 可被算出來

• Signature verification
• 當收到 $m,s,r$
• 檢查 $s, r\in{1,...,q-1}$
• 計算
  $u_1=h(m)s^{-1}\text{ mod }q$
  $u_2=rs^{-1}\text{ mod }$
• 計算 $v=(g^{u_1}A^{u_2}\text{ mod }p)\text{ mod }q$
  若 $r=v$ 則接受此signature

Diffie-Hellman Key Exchange

• 用在雙方需使用同一把對稱私鑰時
• 建立在離散對數問題的困難度
• 方法：
• 雙方得到質數 $p$ 及generator $g\in\mathbb{Z}_p^*$
• Alice計算 $h_A=g^a\text{ mod }p$，Bob計算 $h_B=g^b\text{ mod }p$
• Alice傳 $h_A$ 給Bob，Bob傳 $h_B$ 給Alice
• Alice計算 $h_B^a$，Bob計算 $h_A^b$

• Man-in-the-Middle Attack
• 攻擊者在中間替換 $h_A,h_B$

Basics Reading
Kaufmann et al., Network Security Chapter 6 and 7

PKCS#1, v.2.1

DSS specification: FIPS 186-2