RSAで遊ぼう

遊んでみる。
遊びなのでキーは32bitでよい。(30以下だとエラーになった。31以上でOK)

$ openssl genrsa 32 | tee private.key
Generating RSA private key, 32 bit long modulus
.+++++++++++++++++++++++++++
.+++++++++++++++++++++++++++
e is 65537 (0x10001)
-----BEGIN RSA PRIVATE KEY-----
MCsCAQACBQC/gCgdAgMBAAECBFTpNXECAwD12wIDAMdnAgJ5LQICcT8CAh4/
-----END RSA PRIVATE KEY-----
$ openssl rsa -text < private.key
Private-Key: (32 bit)
modulus: 3212847133 (0xbf80281d)
publicExponent: 65537 (0x10001)
privateExponent: 1424569713 (0x54e93571)
prime1: 62939 (0xf5db)
prime2: 51047 (0xc767)
exponent1: 31021 (0x792d)
exponent2: 28991 (0x713f)
coefficient: 7743 (0x1e3f)
writing RSA key
-----BEGIN RSA PRIVATE KEY-----
MCsCAQACBQC/gCgdAgMBAAECBFTpNXECAwD12wIDAMdnAgJ5LQICcT8CAh4/
-----END RSA PRIVATE KEY-----

「modulus」が2つの素数の積。N=pqのN。2つの公開鍵の片方。
「publicExpnent」が暗号化のときに使う指数。C=ME mod NのE。2つの公開鍵の片方。
「privateExponent」が復号のときに使う指数。M=CD mod NのD。秘密鍵。
「prime1」と「prime2」が2つの素数。N=pqのpとq。
「exponent1」、「exponent2」、「cofficient」は復号の時に中国の剰余定理というものが使われるそうで、その時に使われる係数だそう。exponent1=D mod (p-1)、exponent2=D mod (q-1)、coefficient=q-1 mod p(coefficient*q=1 mod p)。冪剰余の計算はコンピューターでは容易であるという説明がよくなされる。確かに暗号化の時のEは比較的小さい値(あと2進数で書くと1が少ない)であるため問題はないが、一方、復号の時のDは大きな値(上の例だと32ビットの鍵なのでそんなに大きな数字ではないが)になるので、アルゴリズムを工夫して高速化している、ということだそうだ。また2つの素数pとqがあればexponent1~cefficientを計算することは「容易」であるが、復号の度にいちいち計算し直すのは時間がかかるし、暗号の強度が損なわれるものでもないので、秘密鍵と一緒にファイルに埋め込んでしまえ、ということなのだろう。

「容易である(容易にできるとは言ってない)」みたいな感じ?

【参考URL】
RSA暗号ってどういうしくみなの...?(本文の記号の表記はこのサイトに従った)
ろば電子が詰まつてゐる
OpenSSLとPythonでRSA暗号の原理を知る

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください