NIST美國國家標準與科技機構發起的Public Key公開金鑰加解密系統競賽，RSA (Rivest–Shamir–Adleman)加密演算法由三位密碼學家共同研究出來在1973年發表，最終獲選最早為公開金鑰系統標準之一，雖然後來英國Government Communications Headquarters(GCHQ)國家通訊總部說他們的英國密碼學家早在1970年就已經研究出Non-Secret Encryption這種非對稱式加解密系統，但不管怎麼說，RSA在當時算是非常突破性的成果。
首先選擇兩個隨機的大質數p p p q q q
那怎樣的質數才算大？
參考整數複雜度量測 之後討論都使用多少bit長度為單位，以及p p p q q q n n n n = p q n = pq n = pq φ ( n ) = ( p − 1 ) ( q − 1 ) \varphi(n) = (p-1)(q-1) φ ( n ) = ( p − 1 ) ( q − 1 ) l e n ( p − 1 ⋅ q − 1 ) len(p-1 \cdot q-1) l e n ( p − 1 ⋅ q − 1 )
φ ( n ) \varphi(n) φ ( n ) Euler’s Totient Function尤拉函數 ，目的是為了找所有與n n n p p p q q q p p p p p p q q q q q q n n n
接著隨機挑選一個e ∈ Z n e \in Z_{n} e ∈ Z n e ⊥ φ ( n ) e\perp\varphi(n) e ⊥ φ ( n ) e e e d d d
d = e − 1 m o d φ ( n ) d = e^{-1} \>\> mod \>\> \varphi(n) d = e − 1 m o d φ ( n ) d d d e e e p k = ( e , n ) pk = (e, n) p k = ( e , n ) s k = ( d , n ) sk = (d, n) s k = ( d , n )
選一個想要加密的明文Message m ∈ Z n m \in Z_{n} m ∈ Z n
c = E ( p k , m ) = m e m o d n c = E(pk, m) = m^{e} \>\> mod \>\> n c = E ( p k , m ) = m e m o d n
接收者收到傳輸者加密過後的密文 Ciphertext c ∈ Z n c \in Z_{n} c ∈ Z n
m = D ( s k , c ) = c d m o d n m = D(sk, c) = c^{d} \>\> mod \>\> n m = D ( s k , c ) = c d m o d n
私鑰是由公鑰所計算得來的d = e − 1 m o d φ ( n ) d = e^{-1} \>\> mod \>\> \varphi(n) d = e − 1 m o d φ ( n ) e d = k φ ( n ) + 1 ed = k\varphi(n)+1 e d = k φ ( n ) + 1
a p − 1 ≡ 1 ( m o d p ) a^{p-1} \equiv 1 \>\> (mod \>\> p) a p − 1 ≡ 1 ( m o d p ) a ∈ Z p a \in Z_{p} a ∈ Z p p p p
以及中國餘式定理Chinese Remainder Theorem:
如果x = a ( m o d p ) x = a \>\> (mod\>\> p) x = a ( m o d p ) x = a ( m o d q ) x = a \>\>(mod\>\> q) x = a ( m o d q ) x = a ( m o d p q ) x = a \>\>(mod\>\> pq) x = a ( m o d pq ) p q pq pq
所以需要證明的是m = c d ( m o d n ) = ( m e m o d n ) d m o d n = m e d m o d n m = c^{d} \>\> (mod \>\> n) = (m^{e} \>\> mod \>\> n)^{d} \>\> mod \>\> n = m^{ed} \>\> mod \>\> n m = c d ( m o d n ) = ( m e m o d n ) d m o d n = m e d m o d n
如前面中國餘式定理所述m = c d ( m o d n ) m = c^{d} \>\>(mod\>\> n) m = c d ( m o d n ) m = c d ( m o d p ) m = c^{d} \>\>(mod\>\> p) m = c d ( m o d p ) m = c d ( m o d q ) m = c^{d} \>\>(mod\>\> q) m = c d ( m o d q ) c d = m e d ( m o d p ) c^{d} = m^{ed} \>\>(mod \>\> p) c d = m e d ( m o d p ) e d = 1 ( m o d φ ( n ) ) ed = 1 \>\>(mod \>\> \varphi(n)) e d = 1 ( m o d φ ( n )) e d = 1 ( m o d ( p − 1 ) ( q − 1 ) ) ed = 1 \>\>(mod \>\>(p-1)(q-1)) e d = 1 ( m o d ( p − 1 ) ( q − 1 ))
可以將e d = 1 ( m o d ( p − 1 ) ( q − 1 ) ) ed = 1 \>\>(mod \>\>(p-1)(q-1)) e d = 1 ( m o d ( p − 1 ) ( q − 1 )) e d = k ( p − 1 ) ( q − 1 ) + 1 ed = k(p-1)(q-1) + 1 e d = k ( p − 1 ) ( q − 1 ) + 1 k k k
m e d = m k ( p − 1 ) ( q − 1 ) + 1 ( m o d p ) = m ⋅ m k ( p − 1 ) ( q − 1 ) ( m o d p ) = m ⋅ ( m ( p − 1 ) ) k ( q − 1 ) ( m o d p ) ( F e r m a t ′ s L i t t l e T h e o r e m ) = m ⋅ ( 1 ) k ( q − 1 ) ( m o d p ) = m ( m o d p ) m^{ed}\\ = m^{k(p-1)(q-1)+1} \>\>(mod\>\> p)\\ = m \cdot m^{k(p-1)(q-1)} \>\>(mod \>\>p)\\ = m \cdot (m^{(p-1)})^{k(q-1)} \>\>(mod\>\> p) \>\> \>\> (Fermat's\>\> Little \>\>Theorem)\\ = m \cdot (1)^{k(q-1)} \>\>(mod \>\>p)\\ = m \>\>(mod\>\> p) m e d = m k ( p − 1 ) ( q − 1 ) + 1 ( m o d p ) = m ⋅ m k ( p − 1 ) ( q − 1 ) ( m o d p ) = m ⋅ ( m ( p − 1 ) ) k ( q − 1 ) ( m o d p ) ( F er ma t ′ s L i ttl e T h eor e m ) = m ⋅ ( 1 ) k ( q − 1 ) ( m o d p ) = m ( m o d p )
同理在m o d q mod \>\> q m o d q
m e d = m k ( p − 1 ) ( q − 1 ) + 1 ( m o d q ) = m ⋅ m k ( p − 1 ) ( q − 1 ) ( m o d q ) = m ⋅ ( m ( q − 1 ) ) k ( p − 1 ) ( m o d q ) ( F e r m a t ′ s L i t t l e T h e o r e m ) = m ⋅ ( 1 ) k ( p − 1 ) ( m o d p ) = m ( m o d q ) m^{ed}\\ = m^{k(p-1)(q-1)+1} \>\>(mod\>\> q)\\ = m \cdot m^{k(p-1)(q-1)} \>\>(mod \>\>q)\\ = m \cdot (m^{(q-1)})^{k(p-1)} \>\>(mod\>\> q) \>\> \>\> (Fermat's\>\> Little\>\> Theorem)\\ = m \cdot (1)^{k(p-1)} \>\>(mod \>\>p)\\ = m \>\>(mod\>\> q) m e d = m k ( p − 1 ) ( q − 1 ) + 1 ( m o d q ) = m ⋅ m k ( p − 1 ) ( q − 1 ) ( m o d q ) = m ⋅ ( m ( q − 1 ) ) k ( p − 1 ) ( m o d q ) ( F er ma t ′ s L i ttl e T h eor e m ) = m ⋅ ( 1 ) k ( p − 1 ) ( m o d p ) = m ( m o d q )
得證m e d = m ( m o d p ) m^{ed} = m \>\>(mod \>\>p) m e d = m ( m o d p ) m e d = m ( m o d q ) m^{ed} = m \>\>(mod\>\> q) m e d = m ( m o d q ) m e d = m ( m o d n ) = c ′ m^{ed} = m \>\>(mod \>\>n) = c' m e d = m ( m o d n ) = c ′
非對稱式加密系統的安全性都倚靠數學難題，而計算這些金鑰大多使用軟體像是openssl等，當然也有像是特殊的加解密硬體機器可以使用，一台也不便宜，所以幾乎都是企業才會去採購，故網路上的伺服器幾乎都是使用軟體的方法在計算，但在網路上每秒有多少組金鑰對正在產生，而軟體的計算速度也不能太慢，故可以使用一些小方法來提昇效率。
像是使用特殊的e e e e e e
舉例3 = 11(b), 17 = 10001(b), 65537 = 10000000000000001(b)使用 Square and Multiply 演算法 計算c = m e m o d n c = m^{e} \>\> mod \>\> n c = m e m o d n
另外就是透過中國餘式定理與同構特性 的特性計算m = c d m o d n m = c^{d} \>\> mod \>\> n m = c d m o d n
首先設定s k = ( d 1 , d 2 , n , p , q ) sk = (d_{1}, d_{2}, n, p, q) s k = ( d 1 , d 2 , n , p , q ) d 1 = d m o d p − 1 , d 2 = d m o d q − 1 d_{1} = d \>\> mod \>\> p-1, d_{2} = d \>\> mod \>\> q-1 d 1 = d m o d p − 1 , d 2 = d m o d q − 1
接著預先計算q ‾ = q ( q − 1 m o d p ) m o d n \overline{q} = q(q^{-1} \>\> mod \>\> p)\>\> mod\>\> n q = q ( q − 1 m o d p ) m o d n p ‾ = p ( p − 1 m o d q ) m o d n \overline{p} = p(p^{-1} \>\> mod \>\> q)\>\> mod \>\> n p = p ( p − 1 m o d q ) m o d n
就可以計算m 1 = ( c m o d p ) d 1 m o d p m 2 = ( c m o d q ) d 2 m o d q m = ( m 1 q ‾ + m 2 p ‾ ) m o d n m_{1} = (c \>\> mod \>\> p)^{d_{1}}\>\> mod \>\> p \\ m_{2} = (c \>\> mod \>\> q)^{d_{2}} \>\> mod \>\> q \\ m = (m_{1}\overline{q} + m_{2} \overline{p}\>\>\>\>) \>\> mod \>\> n m 1 = ( c m o d p ) d 1 m o d p m 2 = ( c m o d q ) d 2 m o d q m = ( m 1 q + m 2 p ) m o d n
軟體的話可以利用平行運算分別計算m 1 m_{1} m 1 m 2 m_{2} m 2
是假設私鑰d d d d < n 1 / 4 d < n^{1/4} d < n 1/4 p − 1 , p + 1 , q − 1 , q + 1 p-1, p+1, q-1, q+1 p − 1 , p + 1 , q − 1 , q + 1 ∣ p − q ∣ |p - q| ∣ p − q ∣ p p p q q q ( n = 2048 b i t s ← p = 1024 b i t s , q = 1024 b i t s ) (n = 2048\>\> bits \gets p = 1024 \>\> bits, q = 1024 \>\> bits) ( n = 2048 bi t s ← p = 1024 bi t s , q = 1024 bi t s ) ( p − q ) 2 / 4 {(p-q)^{2}}/{4} ( p − q ) 2 / 4 ( p + q ) 2 / 4 {(p+q)^{2}}/{4} ( p + q ) 2 / 4 n n n n = ( p + q ) 2 / 4 − ( p − q ) 2 / 4 n = {(p+q)^{2}}/{4} - {(p-q)^{2}}/{4} n = ( p + q ) 2 / 4 − ( p − q ) 2 / 4 p + q / 2 {p+q}/{2} p + q / 2 ⌈ n ⌉ \lceil \sqrt{n} \rceil ⌈ n ⌉
首先我們計算z = ⌈ n ⌉ z = \lceil \sqrt{n} \rceil z = ⌈ n ⌉ y = z + i , i ≥ 0 y = z + i, i \geq 0 y = z + i , i ≥ 0 y y y y 2 − n y^{2} - n y 2 − n x 2 x^{2} x 2 x x x x = p − q / 2 x = {p-q}/{2} x = p − q / 2 x x x ( x − y ) ( x + y ) = p q (x-y)(x+y) = pq ( x − y ) ( x + y ) = pq
針對弱參數的對策就是p p p q q q
假設一組n = p q n = pq n = pq
( p k 1 , s k 1 ) = ( ( e 1 , n ) , ( d 1 , n ) ) ( p k 2 , s k 2 ) = ( ( e 2 , n ) , ( d 2 , n ) ) (pk_{1}, sk_{1}) = ((e_{1}, n), (d_{1}, n)) \\ (pk_{2},sk_{2}) = ((e_{2}, n), (d_{2}, n)) ( p k 1 , s k 1 ) = (( e 1 , n ) , ( d 1 , n )) ( p k 2 , s k 2 ) = (( e 2 , n ) , ( d 2 , n ))
可以使用其中一對的金鑰去搜尋另一對的金鑰，假設今天知道user1的金鑰要猜user2的私鑰:
( p k 1 , s k 1 , p k 2 ) → s k 2 ′ = ( d 2 ′ , n ) , d 2 ′ = e 2 − 1 m o d ( e 1 d 1 − 1 ) (pk_{1}, sk_{1}, pk_{2}) \to sk_{2}' = (d_{2}', n), d_{2}' = e_{2}^{-1} \>\> mod \>\> (e_{1}d_{1} -1) ( p k 1 , s k 1 , p k 2 ) → s k 2 ′ = ( d 2 ′ , n ) , d 2 ′ = e 2 − 1 m o d ( e 1 d 1 − 1 ) e 1 d 1 − 1 e_{1}d_{1}-1 e 1 d 1 − 1 k ⋅ φ ( n ) k \cdot \varphi(n) k ⋅ φ ( n )
以及假設一個M e s s a g e m Message \>\>m M ess a g e m c 1 = m e 1 m o d n c_{1} = m^{e_{1}} \>\> mod \>\> n c 1 = m e 1 m o d n c 2 = m e 2 m o d n c_{2} = m^{e_{2}} \>\> mod \>\> n c 2 = m e 2 m o d n s , t s, t s , t
c 1 s c 2 t m o d n = m s e 1 + t e 2 m o d n = m c_{1}^{s}c_{2}^{t} \>\> mod \>\> n = m^{se_{1}+te_{2}} \>\> mod \>\> n = m c 1 s c 2 t m o d n = m s e 1 + t e 2 m o d n = m
s e 1 + t e 2 = 1 se_{1}+te_{2} = 1 s e 1 + t e 2 = 1 e 1 ⊥ e 2 e_{1} \perp e_{2} e 1 ⊥ e 2
針對共同模數攻擊的對策是盡量不要使用同一個n n n
在早期許多伺服器使用e = 3 e = 3 e = 3 m m m e = 3 e=3 e = 3 c c c
c 1 = m 3 m o d n 1 c 2 = m 3 m o d n 2 c 3 = m 3 m o d n 3 c_{1} = m^{3} \>\> mod \>\> n_{1} \\ c_{2} = m^{3} \>\> mod \>\> n_{2} \\ c_{3} = m^{3} \>\> mod \>\> n_{3} c 1 = m 3 m o d n 1 c 2 = m 3 m o d n 2 c 3 = m 3 m o d n 3
前面提到使用中國餘式定理CRT可以計算共同的數，c = c 1 c 2 c 3 m o d n = m 3 m o d n 1 n 2 n 3 = m 3 c = c_{1}c_{2}c_{3} \>\> mod \>\> n = m^{3} \>\> mod \>\> n_{1}n_{2}n_{3} = m^{3} c = c 1 c 2 c 3 m o d n = m 3 m o d n 1 n 2 n 3 = m 3
而m = c 1 / 3 = ( m 3 ) 1 / 3 m = c^{1/3} = (m^{3})^{1/3} m = c 1/3 = ( m 3 ) 1/3 m m m e e e
這種攻擊方法需要倚靠Oracle讓攻擊者可以取得明文密文對，可以將oracle想成一張很大的表，系統提供一個Decryption Oracle O e , n O_{e, n} O e , n c c c m = c d m o d n m = c^{d} \>\> mod \>\> n m = c d m o d n
透過原本的c c c c ′ = c r e m o d n c' = cr^{e} \>\> mod \>\> n c ′ = c r e m o d n r ∈ R Z n ∗ r \in_{R} Z_{n}^{*} r ∈ R Z n ∗
詢問oracle O e , n ( c ′ ) → m ′ O_{e, n}(c') \to m' O e , n ( c ′ ) → m ′ m ′ = m ⋅ r m' = m \cdot r m ′ = m ⋅ r
最後計算m ′ r − 1 m o d n = m r r − 1 m o d n = m m'r^{-1} \>\> mod \>\> n = mrr^{-1} \>\> mod \>\> n = m m ′ r − 1 m o d n = m r r − 1 m o d n = m
透過mask掉原本的c c c c ′ c' c ′ r r r c c c m m m
Non-adaptive chosen ciphertext attakc(CCA1): 攻擊者把想要詢問的密文一次挑選出來，只能針對oracle詢問一次O e , n ( c i ) , 1 ≤ i ≤ s O_{e, n}(c_{i}), 1 \leq i \leq s O e , n ( c i ) , 1 ≤ i ≤ s
Adaptive chosen ciphertext attack(CCA2): 攻擊者在多項式時間內可以一次一次的詢問oracle，不限詢問次數O e , n ( c i ) , 1 ≤ i ≤ s O_{e, n}(c_{i}), 1 \leq i \leq s O e , n ( c i ) , 1 ≤ i ≤ s
如此可見CCA2的安全性等級是最高的，所以看paper在證明密碼系統的安全性時雖然作者會寫有CCA的安全性，但需要讀者再去檢查一下oracle的等級，看是達到CCA1還是CCA2的安全性
針對RSA選定密文攻擊方法是採用O A E P + OAEP^{+} O A E P +