Cyber Security - RSA

RSA

• 非對稱式加密
• 由 Rivest、Shamir、Adleman三位教授發展出來
• 運算速度慢，通常用來加密 Session key (用來加密會議內容的 key)
• 將兩個質數 p 和 q（p != q）相乘得到 N 很簡單,但從 N 推回 p、q 不簡單，尤其當 N 很大的時候

製作 Public Key 與 Private Key:

1. 選擇 2 個超大相異質數 p, q 並計算 N = p * q
2. 計算 r = (p-1) × (q-1)
3. 選一整數 e 滿足 e < r 且 gcd(e, r) = 1
4. 尋一整數 d 滿足 ed ≡ 1 (mod r)
5. 銷毀 p 與 q，得 Public Key e 與 Private Key d

加密與解密:

1. Bob 要傳訊息給 Alice，訊息依據特定方法轉成整數 m (m < N)
2. Alice 將 Public Key (N, e) 交給 Bob
3. Bob 運算 c ≡ m^e (mod N) 得 c 並交給 Alice (加密)
4. Alice 運算 c^d ≡ m (mod N) 得 m，再依約定方法轉回原始內容 (解密)

RSA 中使用到了哪些觀念

• 模算數
• 最大公因數
• 線性同餘方程式
• 中國餘數定理
• 費馬小定理

RSA 快速複習

一些補充小帖

• p、q：任意選的兩個很大很大的質數
• N = p * q
• phi(N) = (p-1)(q-1)
  • 到 N 的質數個數
• pt： plain text 明文
• ct： ciper text 密文
• Encrypt：加密
• Decrypt：解密

RSA Example

1. Generate N and φ(n)
   • Choose p = 3 and q = 11
   • Compute N = p x q = 3 x 11 = 33
   • Compute φ(n) = (p - 1) x (q - 1) = 2 x 10 = 20
2. Generate e and d
   • Choose e such that 1 < e < φ(n) and e and φ(n) are coprime.
   • Compute a value for d such that (d x e) % φ(n) = 1.
   • e.g.
     • Public key is (e, n) => (7, 33)
     • Private key is (d, n) => (3, 33)
3. Encrypt / Decrypt
   • The encryption of pt = 2 is ct = 2^7 mod 33 = 29
   • The decryption of ct = 29 is pt = 29^3 mod 33 = 2

Reference

• NISRA Mask 學長的現代密碼學課程
• CHA 的 RSA 整理