RSA暗号を実際に計算してみる

下記にRSA暗号の計算例が載っていたので、perlで実際に計算してみた。
https://milestone-of-se.nesuke.com/nw-basic/tls/rsa-summary/

# cat rsa.pl
use Math::BigInt;

#data
my $data = Math::BigInt->new("508");

print "data: ".$data."\n";

# encrypt
# koukaikagi 223, 1357

my $pubkey1 = 223;
my $pubkey2 = 1357;

my $crypt = ($data ** $pubkey1) % $pubkey2;

print "crypted data: ".$crypt."\n";


#decrypt

#himitukagi 103

my $privkey = 103;


$decrypt = ($crypt ** $privkey) % $pubkey2;

print "decrypted data: ".$decrypt."\n";

実行結果

# perl rsa.pl
data: 508
crypted data: 1319
decrypted data: 508

元のデータは 508
公開鍵となる数字は２つのペアで 223と1357である。
暗号化されたデータは、元のデータを223乗して、それを1357で割った余りとして作成し
この例ではその値は 1319である。
秘密鍵の値は103である。
復号は、1319を103乗して1357で割った余りとして求め、
その値は508であり、元のデータと一致する。

結果だけ見ると3～4桁の数字であるが、
計算途中で「508の223乗」というとんでもない計算があり、
280桁くらいになるので BigIntを使っている。

しかし実際の暗号化においては、508などという数値どころではない
文字列や画像、音声などを暗号化しているのだから
とてつもない量の計算がされている。
そのために暗号化専用のチップなどが使われたりしているのだ。

注目すべきは下記の記述である。
「メッセージ m を e 乗 (公開鍵で暗号化) したものに対しては d 乗 (秘密鍵で復号) することで元の m に戻りますし、
メッセージ m を d 乗 (秘密鍵で暗号化) したものに対しては e 乗 (公開鍵で復号) することで元の m に戻るのです。」

これがよく話題になる、「電子署名のことを秘密鍵で暗号化するというのは間違い」
のことである。
この人は、「別に署名を秘密鍵で暗号化するといってもいいじゃないか。」
という旨のことを言っている。
私もそう思う。

では、署名と検証もやってみよう。

# cat sign.pl
use Math::BigInt;

#data
my $data = Math::BigInt->new("508");

print "data: ".$data."\n";

# encrypt
# koukaikagi 223, 1357
#himitukagi 103

my $pubkey1 = 223;
my $pubkey2 = 1357;

my $privkey = 103;

my $sign = ($data ** $privkey) % $pubkey2;

print "signed data: ".$sign."\n";


#verify

$verified = ($sign ** $pubkey1) % $pubkey2;

print "verified data: ".$verified."\n";

さっきの暗号化の計算と同じことを、
暗号化時（署名時）に103乗し、復号時（検証時）に223乗、つまり逆にしている。
逆にしても、元の値に戻る。

# perl sign.pl
data: 508
signed data: 315
verified data: 508

当然、公開鍵と秘密鍵というのはどんな数字でもいいわけではなく、
上記のような計算が成り立つような数字を選ぶわけであるが、
「署名を秘密鍵で暗号化すると言ってはいけない」と怒ることはないんだなと、
ようやく安心できた。

python版

# cat rsa.py
data=508
pub1=223
pub2=1357
priv=103

print("data:"+str(data))

crypted=(data ** pub1) % pub2
print("crypted:"+str(crypted))

decrypted=(crypted ** priv) % pub2
print("decrypted:"+str(decrypted))

signed=(data ** priv) % pub2
print("signed:"+str(signed))

verified=(signed ** pub1) % pub2
print("verified:"+str(verified))

# python rsa.py
data:508
crypted:1319
decrypted:508
signed:315
verified:508

BigIntとかいらない。