rsa暗号

rsa暗号

idoushiki.hatenablog.com
以前に、シーザー暗号化するプログラムについての記事を書いた。今回は、さらに強力な「RSA暗号」について書いてみた。

暗号文＝平文^e mod n

RSA暗号は平文、鍵、暗号文どれも数で、暗号文はe乗した平文を割ったあまりである。

eとnが公開鍵になる。

復号化の式はこのようになる

平文＝暗号文^d mod n

プライベート鍵はdとnになる

鍵のペアの作り方

１　 nを求める

２ rを求める

３ eを求める

４ 　dを求める

nを求める

素数を2つ用意する

この素数をp,qとする

pとqを掛け合わせて、これをnとする

n=p*q

rを求める

rは、(p-1)と(q-1)の最小公倍数

eを求める

eは1よりも大きくて、rよりも小さい数とする。
eとrの最大公約数が１になるようにする。

dを求める

dは、１より大きくてrより小さい数とする。

e*d mod r = 1 になるようにする

rubyでrsa暗号化するプログラムと復号化するプログラムを組んでみた

暗号化

復号化

このプログラムでは、素数のpとqの数値は17,19に固定しておいて、eとdは乱数でランダムな値を生成するようにしている。

暗号化する平文の数値を大きくしていくと、正常に復号化できない。
たぶん暗号化、復号化するときに平文の数を何乗もするから数が大きくなりすぎるんだな。