RSA - 範例題

RSA 加密程式是目前最為廣泛,且不易破解的加密演算法,現在應用在 自然人憑證,會產生公開密碼(N,e) Public Key, 記得要公開喔,否則就無法通訊,而藏在晶片卡內的 d值,則為 Private Key

M-> C 很簡單 , C->M 很困難 (具有單向函數暗門特色)

整理:
1. N= p * q , {p.q are lage prime number}
2.(e,N) =1 ,N=(p-1)(q-1) {e,N 戶為質數}
3. d*e ≡ 1 mod N

----------------------------------------------------
ex: p=11,q=13, 所以N = pq=143
N=(p-1)(q-1) = 10 * 12 =120
令 e=13
de ≡ 1 mod N
13d ≡ 1 mod 120
所以 d ≡ 37 mod 120

{ 13 d ≡ 1 mod 120
13 x 1 ≡ 13 mod 120
13 x 9 ≡ 117 mod 120
13 x (-9) ≡ 3 mod 120
13 x (-36) ≡ 12 mod 120

13 x d ≡ 1 mod 120 (想辦法為 1 )
13 x (1-(-36)) ≡ 13-12 mod 120
得到 13 x 37 ≡ 1 mod 120
所以 d ≡ 37 mod 120
}


加密: 假設 M=2
C=M^e ≡ 2 ^ 13 mod 143
≡ 41 mod 143

解密:
M ≡ 41 ^37 mod 143
已知 41^2 ≡ -35 mod 143
41^4 ≡ (-35)^2 ≡ -62 mod 143
41^8 ≡ (-62)^2 ≡ -17 mod 143
41^16 ≡ (-17)^2 ≡ 3 mod 143
41^32 ≡ 9 mod 143

所以 41^37 ≡ 41^32 * 41^4 * 41
≡ 9 * (-62) * 41 mod 143
≡ -(-2) mod 143
≡ 2 mod 143 ... end