はじめに

最近暗号化の仕組みに興味を持ち、『暗号技術入門第3版』を読みました。そして、RSAをPythonで作って遊んでみました。
そのあと実際に使われているOpenSSLを触っていた時に感じた疑問について書きます。

なお、本記事で登場する { E, D, N, p, q, L } とは、前の記事で使ったものと同様です。

記号	意味
p	素数1
q	素数2
N	p * q
L	lcm((p-1), (q-1))
E	公開鍵
D	秘密鍵

RSAをPythonで作ってみた
https://qiita.com/rby39/items/6829bcdce7ebb42c25f7

素朴な疑問

実際に使われているOpenSSLでRSA(512bit)の秘密鍵と公開鍵を作ってみました。

$ openssl genrsa -out private.txt 512
$ openssl rsa -in private.txt -out public.txt -pubout

なお、OpenSSLでは鍵はPEMという方式で作成されます。
PEMはA-Z a-z 0-9 +\ (Padding = )で表現するbase64を使うため、1文字 6bit です。

秘密鍵 ( 2556bit？ )

公開鍵 ( 756bit？ )

-----BEGIN PUBLIC KEY-----
MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAMDK5Nqe9n13ht/ppIjvLecOMknJyyAF
GtyYowzEe41FYVBNEhvqYrG0G0tJvdI3SIaNzAuaPktRb93+tDFh0iMCAwEAAQ==
-----END PUBLIC KEY-----

全然サイズが違うんです。
本を読み終えた私には意味が分かりませんでした。

秘密鍵は 512bitのN + 512bitのDで合計1024bitくらいなのでは。
公開鍵も 512bitのN + 512bitのEで秘密鍵と同じくらいのサイズのはず。
そもそも公開鍵の3倍以上って、秘密鍵大きすぎ！
うわっ.... 私の公開鍵少なすぎ...？

これがOpenSSLを触ってみての私の疑問でした。
そして、少し調べてみると秘密鍵を整えて表示することができるコマンドを見つけました。
これで解決するだろうと実行してみると...

秘密鍵

$ openssl rsa -text -noout -in public.txt
RSA Private-Key: (512 bit, 2 primes)
modulus:  # N のことかな
    00:c0:ca:e4:da:9e:f6:7d:77:86:df:e9:a4:88:ef:
    2d:e7:0e:32:49:c9:cb:20:05:1a:dc:98:a3:0c:c4:
    7b:8d:45:61:50:4d:12:1b:ea:62:b1:b4:1b:4b:49:
    bd:d2:37:48:86:8d:cc:0b:9a:3e:4b:51:6f:dd:fe:
    b4:31:61:d2:23
publicExponent: 65537 (0x10001)  # なにこれ短い
privateExponent:  # 秘密鍵 E っぽい
    11:74:cd:8f:f6:00:bf:8f:89:08:d1:30:f2:ad:25:
    6c:dc:5e:35:4c:2e:36:32:00:22:a5:37:6e:3a:84:
    2d:60:48:5f:79:01:a8:b4:ca:31:8b:cb:05:e3:2c:
    a1:c9:2a:ca:f5:cf:04:1e:de:f5:5c:0d:73:b6:48:
    55:44:a1:71
prime1:  # これは p
    00:f7:31:6f:59:c2:58:d4:b4:33:62:1b:07:73:79:
    3d:9c:bb:01:af:c6:d8:9f:72:9f:af:52:94:44:c8:
    75:9f:df
prime2:  # これは q
    00:c7:a9:4a:36:f0:48:dd:b3:63:04:86:e0:c4:d3:
    c3:8c:09:a5:0c:0c:ef:bc:2c:2c:10:cc:23:98:69:
    d4:86:3d
exponent1:  # え... L とか？
    00:d2:ec:62:b8:33:66:3a:f1:1c:5b:1c:f7:29:a8:
    0d:53:9c:1a:5f:53:8b:e9:da:13:b9:b4:fc:01:09:
    0f:9c:ff
exponent2:  # もう知ってる係数がなくなりました ...
    21:ed:e9:d7:b6:33:9b:c1:3d:45:6a:aa:4d:a8:72:
    e5:9c:49:f8:e7:45:e2:23:5b:85:ab:3b:2d:4e:66:
    b8:3d
coefficient:  # なにこれ？
    00:df:fc:8f:10:ef:1b:2b:e6:11:60:f6:01:e7:d7:
    e4:43:d8:74:8e:4d:27:2c:6b:44:e5:86:25:96:14:
    9f:42:1a

公開鍵

$ openssl rsa -pubin -text -noout -in public.txt
RSA Public-Key: (512 bit)
Modulus:  # 秘密鍵でも登場した...やっぱり N だな
    00:c0:ca:e4:da:9e:f6:7d:77:86:df:e9:a4:88:ef:
    2d:e7:0e:32:49:c9:cb:20:05:1a:dc:98:a3:0c:c4:
    7b:8d:45:61:50:4d:12:1b:ea:62:b1:b4:1b:4b:49:
    bd:d2:37:48:86:8d:cc:0b:9a:3e:4b:51:6f:dd:fe:
    b4:31:61:d2:23
Exponent: 65537 (0x10001)  # もしや公開鍵 E のことでは...

うーん... わからん。

この疑問は以下の記事で分かりやすくまとめられていました。

「OpenSSLとPythonでRSA暗号の原理を知る」
http://inaz2.hatenablog.com/entry/2013/11/27/225953

解決

modulus           INTEGER,  -- n = p*q
publicExponent    INTEGER,  -- e = 65537 (=0x10001)
privateExponent   INTEGER,  -- d == e^(-1) mod (p-1)*(q-1)
prime1            INTEGER,  -- p
prime2            INTEGER,  -- q
exponent1         INTEGER,  -- d mod (p-1)
exponent2         INTEGER,  -- d mod (q-1)
coefficient       INTEGER,  -- q^(-1) mod p

参考元 : http://inaz2.hatenablog.com/entry/2013/11/27/225953

まず、この中で私が知っているのは以下のものだけでした。

このうち D = 65537 (=0x10001)で固定されているのは驚きましたが、考えてみると自然な値です。
先ず値を固定したとしても公開鍵ですので問題ありません。それどころか17bitの小さな数に確定することで相対的に秘密鍵のビット数を大きくとることができるため秘密鍵がより強力になるようです。

modules = N
prime1 = p
prime2 = q
publicExponent = E
privateExponent = D

そして、以下のものは複合処理で使う数学的な方法「中国の剰余定理」で効率的に計算をするための値でした。
計算に興味が無いこともないのですが、数学アレルギーが出そうなため断念しました。また気になったときに調べるかもしれません。

exponent1 INTEGER, -- d mod (p-1)
exponent2 INTEGER, -- d mod (q-1)
coefficient INTEGER, -- q^(-1) mod p

おわりに

結論、私が実装した "馬鹿正直" なアルゴリズムとは程遠い実装( 計算順序も違う )がされていて、~~速度や性能を上げるための工夫があるため、秘密鍵と公開鍵の形式が予想通りではなかっただけでした。OpenSSLすごそうです。~~

OpenSSLというよりも、RSAの規格( RFC )として決まっているようです。
また、このアルゴリズム自体は少なくとも1982年には発表されていたようです。

初めにあった疑問が解消されたため満足しました。

秘密鍵は 512bitのN + 512bitのDで合計1024bitくらいなのでは。 →　計算高速化に使う係数を含んでる

公開鍵も 512bitのN + 512bitのEで秘密鍵と同じくらいのサイズのはず。　→　Eは省略されている

そもそも公開鍵の3倍以上って、秘密鍵大きすぎ！　→　公開鍵より持つ値の個数が4倍も違うため当然

うわっ.... 私の公開鍵少なすぎ...？ →　同上

参考

「OpenSSLとPythonでRSA暗号の原理を知る」
http://inaz2.hatenablog.com/entry/2013/11/27/225953
RSA暗号運用でやってはいけないnのこと
https://www.slideshare.net/sonickun/rsa-n-ssmjp