遊んでみる。
遊びなのでキーは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暗号の原理を知る
関連記事
RSAで遊ぼう
RSA-129を解こう!
サマーウォーズのあの暗号を解こう!
サマーウォーズのあの暗号を解こう!(その2)
サマーウォーズのあの暗号を解こう!(その3)
サマーウォーズのあの暗号を解こう!(その4)
サマーウォーズのあの暗号を解こう!(その5)
RSA暗号と中国の剰余定理と冪剰余計算の高速化