RSA暗号とは
大きな素数を素因数とする数の素因数分解が困難であることを根拠とした暗号技術の一つ。
シンプルだが、強力である。
公開鍵で暗号化し、秘密鍵で復号する。
RSA暗号を使ったやり取りの仕組み
【鍵の生成】
まず、データの受信者が公開鍵と秘密鍵を準備する。
具体的に作る鍵の種類と作り方は以下の通り。
① 非常に大きく、ランダムである任意の素数「p」
② 非常に大きく、ランダムである任意の素数「q」 ※ただし、p≠q
③ pとqの積「n」
④ (p-1)(q-1)と互いに素(=最大公約数が1となる)な任意の自然数「e」
⑤ edを(p-1)(q-1)で割った余りが1となるような任意の自然数「d」
「n」と「e」を公開鍵、「p」「q」「d」を秘密鍵となる。
【暗号化】
データの送信者は、受信者から受け取った公開鍵「n」「e」を使ってメッセージを暗号化する。
具体的には、
- メッセージを数値「α」に変換する ※ただし、α<n
- αのe乗をnで割った余りを求め、それを暗号文「y」とする
送信者は、暗号文「y」を受信者に送る。
【復号化】
受信者は送られてきた暗号文「y」を秘密鍵「d」を使って復号し、平文を取得する。
具体的には、
- yのd乗をしたものを「β」とする
- βをnで割った余りを求め、それを平文「Σ」とする
あとがき
nは公開されている。
んで、復号するにはdが必要。
さらに、dを得るにはpとqが必要。
p×qで算出されるnは公開されているが、nからpとqを逆算するにはとんでもねー手間がかかるため、やってらんねーてこと。