RSA暗号について雑にまとめた
RSA とは?
暗号化の方式. 暗号化における鍵配送問題を解決する公開鍵暗号を実現した画期的な方法. 発明者3人の名前から RSA という名前になった.
必要な知識
だいたい wikipedia に載ってる.
- オイラーのΦ関数
ruby で書くとこんな感じ
def euler(n) coprimes = (1..n).select {|k| n.gcd(k) == 1 } coprimes.size end
RSA 暗号のしくみ
一方 がわからないと の復元は困難(らしい)
アリスがボブにメッセージ を安全に送りたいとき
ボブは を公開する.
アリスは に対して を計算してボブに送信する.
ここで第三者キャロルにアリスが送信した暗号文を盗み見られたとしても, がわからないキャロルには暗号文を解読できない.
暗号文を受け取った ボブは秘密鍵 を用いて を復元してメッセージを読む.
という感じで安全に送れる. 公開されてるなら だから も もわかって もわかるやん!
と言いたくなるけど, 巨大な素数の合成数の素因数分解しようと思ったらめちゃくちゃに時間がかかるのでまあ現実的には無理ということになっている.
思ったより長くなってしまった。見にくいけど腰が痛いのでぶん投げる。間違ってたら教えてください。