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とかいらない。

公開鍵暗号方式における暗号化とデジタル署名の双方向性に関する考察

公開鍵暗号方式において、暗号化は、公開鍵を用いて行われ、受信者は秘密鍵を用いて暗号化されたデータを復号する。

 

このとき公開鍵と秘密鍵はペアであり、データを暗号化して送信する者をA、データを受信して復号する者をBとすると、公開鍵はBが作成して公開した鍵であり、秘密鍵はBが作成して自分で保持している鍵である。

 

公開鍵を公開しないと暗号化することができないし、

秘密鍵を公開してしまうと誰でも復号化できてしまう。

 

公開鍵暗号方式では署名と検証ということも行われる。

 

署名と検証においては送信者が秘密鍵を用いて署名し、

受信者が公開鍵を用いて検証する。

 

この話を聞くと、

『要するに暗号化は公開鍵で暗号化して、署名は秘密鍵で暗号化するってことだね？』

と言いたくなってしまうのだが、そうではない。

 

とりあえず、「署名は秘密鍵で暗号化するということではない」と覚えておけば、

会話して笑われたり怒られたりすることはない。

 

が、そこで『じゃあいったい署名ってどんな処理なの？そしてそれを検証するってどういう処理なの？』

 

と考えてほしい。

 

というか、私はそれを考えて軽く調べてみたのだがよくわからないのである。

 

公開鍵暗号方式は、ある程度大きな数の素因数分解が困難であることを利用している。

ある程度大きな桁数の素数を掛けることは容易であるが、

結果からもとの二つの素数を求めることはコンピュータを使っても事実上不可能である。

 

 

d1をもとのデータ、d2を暗号化したデータ、k1を公開鍵、Eを暗号化する演算とすると、

d1 E k1 = d2

 

k2を秘密鍵、Dを復号する演算とすると

 

d2 D k2 = d1

 

となればよい。

 

 このとき、Eが単なる掛け算であったら、k1は公開されているので、

d1を求めるにはd2を k1で割ればよいことになってしまう。

 

だから、Eはk2を使わないと復号できないような演算でなければならない。

 

それはどういう方法だろうか？

 

 

RSA暗号のwikipediaを見る

鍵のペア（公開鍵と秘密鍵）を作成して公開鍵を公開する。

まず、適当な正整数 e を選択する。

また、大きな2つの素数の組み{p,q}を生成し、

それらの積 n=pq を求めて、

組み{e,n}を平文の暗号化に使用する鍵（公開鍵）とする。

2つの素数{p,q} は秘密に保管し、

暗号文の復号に使用する鍵（秘密鍵）d の生成にも使用する

d=e^-1 mod Φ

ここで

Φ=lcm(p-1,q-1)

※lcmは最小公倍数

暗号化（平文 m から暗号文 c を作成する）：

c=m^e mod n

復号（暗号文 c から元の平文 m を得る）：

m=c^d mod n

暗号化（e 乗）は公開鍵 {e,n} があれば容易に計算でき、

復号（d 乗）も容易に計算できる。

しかし、秘密鍵 d を知らずに解読（法 n の下で e 乗根を計算）するのは、

「n の素因数を知らないと難しい（大きい合成数の素因数分解も難しい）」

と考えられている。

つまり、「秘密鍵を用いずに暗号文から平文を得ることは難しい」と信じられている。

これがRSA暗号の安全性の根拠である。

 

鍵生成

 

k をセキュリティパラメータとする。

p,q（ただしp≠q）をk/2ビットの素数とし、

n=pqとする。

eをΦ(n)未満の正の整数で、

Φ(n)と互いに素な数とし、

dを、Φ(n)を法としたeの逆数 ( deΞ1 (mod Φ(n)) )とする。

ただしここでΦはオイラーのφ関数で、

この場合は

Φ(n)=(p-1)(q-1)

である。

dは、e,Φ(n)が既知の時には拡張されたユークリッドの互除法を使えば容易に求まる。

deをΦ(n)で割った整数商をxとした場合、

de+(-x)Φ(n)=1

が成り立ち、

かつ

eの取り方から

gcd(e,Φ(n)) = 1

であるのでこれを解けばよい、

dを秘密鍵とし

n, eを公開鍵とする

pとqが漏れるとdが計算で求まるため、pとqは安全に破棄すること

 

暗号化

 

aを平文空間Znの元とする。

b=a^e mod n を計算し、bを出力する。

 

復号化

bを暗号文とする。

a' = b^d mod n を計算し、a'を出力する。

 

ここでa'=aとなり、復号できる。

  

ちなみに公開鍵暗号方式は最初RSA暗号方式なしに考案されて、

それを実現するためにRSA暗号方式が考えられたらしい。

 

 

さて。

 

では署名と検証である。

 

だいたい、以下のように説明されている。

 

送信者がデータのハッシュ値を計算して秘密鍵で暗号化し添付（これが署名）

受信者が暗号化されたハッシュ値を公開鍵で復号

受信者が自分でデータのハッシュ値を計算して、復号したハッシュ値と等しいかどうかを確認

 

wikipediaに書いてある通り、暗号化も復号化もおこなっている演算はある数について

ある数の累乗を求めそれをある数で割った余りを計算している。

同じ計算を違うパラメータでおこなうことによって暗号化になり復号化になるのである。

デジタル署名においては先に秘密鍵による演算がなされてその結果に対して公開鍵による演算がなされる。

これを、『秘密鍵により暗号化し公開鍵により復号化する』と言ってはいけないのだ。

そう言うと怒る人がいる。

怒る理由は、私が調べて理解したところでは以下の2点である。

1. それはRSA暗号方式にしかあてはまらない

2. 署名で「暗号化」するのはデータではなくデータのハッシュである

以下はRSA暗号方式を使うこと前提にした話である。

私が調べて理解した知識によれば、「秘密鍵でも暗号化できる」。

ただし、デジタル署名で暗号化するのはデータそのものではなくデータのハッシュである。

秘密鍵で暗号化されたデータのハッシュを公開鍵で復号化し、

自分でデータのハッシュを計算してその結果を復号化したハッシュと比較する、

これが「署名の検証」である。

では、データのハッシュを公開鍵で暗号化して秘密鍵の保持者に送信したら「署名」になるか？

ならない。

なぜなら公開鍵は公開されているので誰でもそれを使ってハッシュを暗号化することはできるからだ。

では、ハッシュではなくデータそのものを秘密鍵で暗号化して公開鍵で復号化させたらどうか？

暗号化というのは、「鍵を生成した人」ではなく、「鍵を生成した人に暗号化したデータを送信する人」が行う。

では、逆の場合は？「鍵を生成した人」が、誰かに暗号化したデータを送りたいときにはどうすればいいのか？

その場合は、データを送りたい相手に鍵ペアを生成してもらうのか。

秘密鍵でハッシュを暗号化し復号できるなら、秘密鍵でデータそのものも暗号化できるはずだが、そういう話は聞かない。

それをしないひとつの理由として、秘密鍵は公開鍵より鍵長が長くて演算に時間がかかる、ということが説明されていたが、

時間がかかるからやらない、ということなら不可能ではないということだ。

（未完）