[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