Simple insights into the Mathematics of the RSA Algorithm

Simple insights into the Mathematics of the RSA (Rivest–Shamir–Adleman) Algorithm:

Public-key cryptography (asymmetric cryptography): 非對稱加密 以傳輸[對稱加密]之金鑰.

A) Mathematics:

A.1) 互質 (coprime):

(1) 任2個質數 (prime number)互質.

(2) 一質數 ∧ 另一非前者之倍數.

(3) 較大數為質數.

(4) 1與任何自然數互質.

(5) p ∈ Z 整數 ∧ p > 1, → p 與 p-1 互質.

(6) p為奇數 ∧ p > 1, → p 與 p-2 互質.

A.2) Euler’s totient function:

令質數 p, q,

令 n = p · q,

令 x ∈ N 自然數 ∧ 1 ≦ x ≦ n
∧ x 與 n 互質,

令 φ(n) = x 之個數,

∵ p, q 互質 → φ(n) = φ(p · q) = φ(p) · φ(q),
∵ p, q 為質數 → φ(p) = p – 1, φ(q) = q – 1

→ φ(n) = (p – 1)(q – 1)

A.3) Public-key:

令 公鑰為 (n, e) (ASN.1, Abstract Syntax Notation One),
使 1 < e < φ(n) ∧ e 與 φ(n) 互質
(實際應用常取 e = 65537).

A.4) Private-key:

令 私鑰為 (n, d) (ASN.1),
e · d ≡ 1 (mod φ(n))
→ e · d mod φ(n) = 1
(d 為 e 對 φ(n) 之模反元素)

A.5) Encryption:

令 明文m ∧ m < n,
令 密文c,
m^e ≡ c (mod n)
→ c = m^e mod n

A.6) Decryption:

c^d ≡ m (mod n)
→ m = c^d mod n

A.7) Security:

公開傳遞: e, n, c,
解密需要: d, n, c,
→ 需要求d,
∵ e · d mod φ(n) = 1,
→ d = (φ(n)·k + 1) / e, k ∈ N ∧ k ≧ 1
→ 需要求φ(n),
∵ φ(n) = φ(p · q) = (p – 1)(q – 1)
→ 需要質因素分解(prime factorization) n, 但實際應用中n至少1024位數(二進制), 難以分解之.

B) e.g. 令質數 p = 3, q = 5

B.1) 令 n = p · q = 15,

B.2) φ(n) = (p – 1)(q – 1) = 2 · 4 = 8

互質: [1], [2], 3, [4], 5, 6, [7], [8], 9, 10, [11], 12, [13], [14], 15

B.3) 令 公鑰e, 使 1 < e < φ(n) ∧ e 與 φ(n) 互質
→ 取 e = 7

B.4) 令 私鑰d,
e · d ≡ 1 (mod φ(n))
→ 7·d ≡ 1 (mod 8)
→ 7·d = 8·k + 1, k ∈ N ∧ k ≧ 1,

7·d = 9, 17, 25, 33, 41, [49], 57, 65, 73, 81, 89, 97, [105]…, [161], ……
d = 49 / 7 = 7 = e (bad)
d = 105 / 7 = 15 = n (bad)
d = 161 / 7 = 23

B.5) Encryption:

令 明文m ∧ m < n → m = 12,
令 密文c,
m^e ≡ c (mod n)
c = m^e mod n
= 12^7 mod 15
≡ 12· 12^2 · 12^2 · 12^2 mod 15
≡ 12·9·9·9 mod 15 (∵ 12^2 ≡ 9 (mod 15))
≡ 12 · 3^3 · 3^3 mod 15
≡ 12·12·12 mod 15 (3^3 ≡ 12)
≡ 24·24·3 mod 15
≡ 9·9·3 mod 15 (24 ≡ 9)
= 3

B.6) Decryption:

c^d ≡ m (mod n)
m = c^d mod n
= 3^23 mod 15
≡ 3 · 3 · 3 · 3^5^4 mod 15
≡ 3 · 3 · 3 · 3^4 mod 15 (∵ 3^5 ≡ 3 (mod 15))
≡ 27 · 27 · 3 mod 15
≡ 12 · 12 · 3 mod 15 (27 ≡ 12)
= 12

C) e.g. 令質數 p = 5, q = 11

C.1) 令 n = p · q = 55,

C.2) φ(n) = (p – 1)(q – 1) = 4 · 10 = 40

C.3) 令 公鑰e, 使 1 < e < φ(n) ∧ e 與 φ(n) 互質
→ 取 e = 33

C.4) 令 私鑰d,
e · d ≡ 1 (mod φ(n))
→ 33·d ≡ 1 (mod 40)
→ 33·d = 40·k + 1, k ∈ N ∧ k ≧ 1,

33·d 個位數為1,
d個位數為7, d = 17

C.5) Encryption:

令 明文m ∧ m < n → m = 50,
令 密文c,
m^e ≡ c (mod n)
c = m^e mod n
= 50^33 mod 55
≡ 50 · 50^32 mod 55
≡ 50 · 50^2^16 mod 55
≡ 50 · 25^16 mod 55 (∵ 50^2 ≡ 25 (mod 55))
≡ 50 · 625^8 mod 55
≡ 50 · 20^2^4 mod 55 (625 ≡ 20)
≡ 50 · 15^4 mod 55 (20^2 ≡ 15)
≡ 50 · 225^2 mod 55
≡ 50 · 5^2 mod 55 (225 ≡ 5)
= 40

C.6) Decryption:

c^d ≡ m (mod n)
m = c^d mod n
= 40^17 mod 55
≡ 40 · 40^2^8 mod 55
≡ 40 · 5^8 mod 55 (40^2 ≡ 5)
≡ 40 · 5^4^2 mod 55
≡ 40 · 20^2 mod 55 (5^4 ≡ 20)
≡ 40 · 15 mod 55 (20^2 ≡ 15)
= 50

Reference:

(1) 加密算法 – RSA算法一 https://read01.com/zh-tw/nEO0y.html
(2) 加密算法 – RSA算法二 https://read01.com/GmmRgO.html
(3) 銀行密碼系統安全嗎?質數(素數)到底有啥用?李永樂老師11分鐘講RSA加密演算法 https://www.youtube.com/watch?v=D_kMadCtKp8
(4) 同餘的基本概念 http://www.sec.ntnu.edu.tw/Monthly/92(256-265)/261-PDF/2003-261-03(21-27).pdf
(5) What is RSA OAEP & RSA PSS in simple terms https://security.stackexchange.com/questions/183179/what-is-rsa-oaep-rsa-pss-in-simple-terms