[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 PaddingRSAES = 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\)
Kaufmann et al., Network Security Chapter 6 and 7
DSS specification: FIPS 186-2
留言
張貼留言