RSA 暗号は大きな数の素因数分解が困難であることを利用したアルゴリズムです。
このため、秘密鍵には 2 つの大きな素数が含まれています。以前、これを確かめるためにわざと鍵長を短く (32bit) にして、その動作を観察したことがありましたが、ふと思い立って普段使っている鍵にどれくらい大きな素数が使われているのか調べてみました。僕自身、自分の鍵の素数を確認してみるというのは初めての経験です。
† openssl の標準のコマンドでは10進表示はできない
あらかじめ断っておきますが、このエントリで使われている秘密鍵はサンプルとして生成したものです。
自分が実際に使っている鍵に含まれているこれらの値を公開してはいけません。
OpenSSL では openssl rsa -text -noout を使うと、秘密鍵の情報を表示させることができるのですが、鍵長が一定以上になると値が 16 進数で表示されるので、素数の値を直感的に理解することが難しくなります。具体的には以下のような感じになります。
このうち、秘密鍵にあたる素数は prime1, prime2 です(ただし、実際の計算に使われる秘密鍵にあたる値は publicExponent^(-1) mod ( prime1 - 1 ) * ( prime2 - 1 ) を計算して得られる privateExponent の方です)。
$ ssh-keygen ssh-keygen -t rsa -b 4096 -f ./id_rsa
$ openssl rsa -text -noout < id_rsa
Private-Key: (4096 bit)
modulus:
00:d9:75:60:e5:03:be:f0:42:7b:b0:7e:8e:dc:76:
92:8c:da:6c:85:64:e6:42:67:a2:c5:b7:4f:7e:f3:
1e:4e:52:cd:1f:6d:81:5a:f6:a6:1e:a5:9e:b5:37:
af:6b:98:5f:13:1f:cf:ae:f0:69:9b:a2:15:ce:bc:
f9:55:62:b8:d2:c2:4a:f7:6a:96:14:3f:10:da:b6:
38:2a:a9:95:19:d3:b8:42:56:a8:19:bc:fc:80:25:
70:25:2a:67:08:ba:c3:26:eb:ef:a9:d4:cd:99:3c:
51:ba:56:a6:b9:a2:e0:2f:f5:af:5c:62:2d:83:97:
cf:fe:d0:36:55:52:fc:f7:ff:5d:19:d7:f5:c2:c1:
93:06:52:fb:4b:a4:21:fb:25:f2:b1:9f:df:09:66:
8f:bc:4a:3a:f1:97:6f:fa:ca:a2:67:95:4f:d4:a8:
c4:84:6a:af:8e:ee:1d:01:7d:1c:2e:69:ed:c8:ac:
d4:d7:8d:d4:95:86:51:42:6b:b3:d4:0e:86:3a:62:
bd:d4:cf:a0:c0:03:4d:35:e8:3a:c3:f6:2e:fa:29:
b5:ea:46:83:5a:06:b5:36:84:b6:90:4a:06:2a:30:
1f:aa:a9:e2:ae:e8:27:25:c8:49:2b:3f:73:bd:19:
8f:c7:52:32:47:91:61:cf:2b:ca:cc:39:56:32:5b:
a8:2e:96:d6:4f:dc:cb:97:0e:0f:e7:0e:a2:d1:19:
9f:c0:91:9f:e0:19:eb:a5:57:c3:58:ac:dd:d1:05:
6e:ce:61:52:20:d7:7f:62:09:07:5f:4e:95:f3:51:
04:c2:f3:cc:5e:60:7b:8a:a6:c3:51:87:9a:1f:da:
0a:f9:81:22:e3:00:c8:22:3e:53:ea:17:35:77:63:
fb:34:3f:a8:5f:75:ae:d5:1b:3f:8f:7f:89:3f:4d:
f4:40:15:56:9b:7b:db:95:73:77:85:80:7e:ec:f8:
57:e7:08:d2:c9:51:54:40:b0:04:e9:ee:7c:b4:6d:
06:61:31:3a:78:bd:2d:b9:98:b1:ea:5a:ec:4d:fb:
99:3c:28:0e:c7:c9:e4:c9:31:9b:8d:43:45:88:f8:
92:da:c1:70:84:f7:54:9b:99:07:80:3d:f4:69:82:
eb:0b:d5:a6:74:ff:bf:d8:82:24:b5:07:b5:ac:43:
db:10:04:fd:99:93:58:ba:28:d6:57:ec:ad:69:07:
87:d9:c9:67:d6:fe:32:d5:3b:65:b1:59:75:36:2e:
a2:d0:8d:91:2c:75:4b:f0:67:69:d4:68:d0:70:91:
da:f7:d0:c0:f1:e8:5a:ac:09:63:4c:7b:b0:30:fa:
32:4b:f9:ff:15:f2:a2:c7:4b:e0:1a:a1:0b:fd:ea:
ae:dd:11
publicExponent: 65537 (0x10001)
privateExponent:
24:25:bc:db:94:c9:d2:8a:5a:a1:36:08:6d:61:50:
6f:15:87:e0:8c:ab:31:f2:a4:3e:15:80:a3:6b:aa:
67:fe:9f:96:4f:cf:a6:dd:45:33:e6:f8:00:cb:a6:
df:4d:ce:d0:11:03:a6:e2:d3:cb:49:20:32:e3:7a:
d6:d4:b8:40:60:87:b1:a5:08:19:89:7a:35:c1:00:
89:26:f3:5f:fd:af:ad:67:56:3e:21:0a:20:0b:19:
1f:34:73:38:22:43:7a:5e:d1:d1:fb:4b:c9:e3:1a:
fa:cc:98:9e:57:12:c9:26:1f:e6:4d:73:9f:62:46:
f2:e6:8d:81:95:6f:f3:91:81:5a:60:69:bb:dc:0d:
a2:89:7c:b8:50:2a:4d:e3:3a:fa:87:c6:bd:7b:4c:
fd:51:a1:86:b3:53:ab:ee:af:1c:64:d7:86:54:1f:
86:9b:6d:5f:66:f9:6f:5b:ea:a9:54:76:70:5b:3a:
6e:32:67:5a:0b:9f:ca:58:b8:e5:d1:1c:42:ec:52:
fd:e3:1d:a7:8d:64:f2:47:0e:2d:b0:e8:92:31:08:
ca:4e:ba:5a:e6:ae:8c:c7:76:c9:79:64:98:f2:b2:
f0:dd:98:8e:d6:8c:5b:5d:75:bc:38:a9:f6:8f:1f:
35:54:d6:82:cb:09:e5:34:34:5b:ca:54:27:be:d0:
af:cf:4e:36:be:e5:51:27:9b:a5:95:e2:eb:ce:06:
2d:f9:2d:15:59:bb:bd:72:c0:a7:1c:8b:fd:6f:ca:
9f:fa:e4:1d:cb:a2:f4:3e:c5:96:51:d7:bf:48:bc:
31:66:cf:90:ad:73:49:7e:60:c8:eb:9e:4b:3b:52:
81:e7:f3:20:8d:9f:6c:fe:82:20:6e:0c:cc:5e:8a:
90:15:cf:a9:49:50:d2:86:97:19:7b:bb:38:20:39:
89:9a:a3:58:a7:1c:79:01:88:d6:b7:97:ee:b6:87:
0b:57:fe:4d:f2:2c:39:f8:84:a0:f3:75:c9:43:ed:
46:91:15:70:c1:a3:41:74:b3:9f:ab:16:64:a7:bd:
cd:fe:42:53:34:d3:20:49:cc:6a:f5:94:a1:6a:1d:
ce:98:c7:3c:ef:dd:90:ec:33:42:b0:62:9f:6b:7c:
a7:6a:31:14:f2:1e:eb:8f:ec:27:30:af:ee:bb:7a:
c6:c8:75:01:10:4b:d5:67:e6:15:5f:49:12:7e:15:
15:a4:74:ea:c0:ab:46:3f:0c:55:07:8e:c4:9e:f5:
1e:e9:8c:93:39:e8:10:54:e8:9c:3b:cc:a9:40:63:
b6:5a:a3:99:a4:22:5e:87:57:3c:34:f9:3c:20:f3:
da:c5:c4:1d:62:28:5c:67:99:9f:f9:37:d6:a1:50:
8e:21
prime1:
00:fb:45:a9:e2:f1:31:90:62:f7:ca:b8:8f:cb:4f:
94:73:21:7b:2b:a9:15:8c:a1:a6:4e:07:ad:45:17:
d6:04:91:cd:c0:56:6f:ac:22:4c:ee:06:29:e0:0b:
4a:51:9d:1a:8f:ca:42:37:f1:e9:77:e3:9d:36:7d:
8b:f5:4c:f8:28:89:16:a3:7c:21:9c:d5:6f:ad:f3:
83:91:6f:f1:c9:66:8b:40:76:5e:78:1f:15:b6:ee:
1d:2c:20:e1:dd:de:9d:cf:ae:73:a6:46:51:bf:dc:
25:35:3c:3f:c7:03:9f:1e:7e:8b:a8:17:47:86:71:
5c:ea:7b:a1:15:10:67:9d:83:46:3e:89:68:dc:7d:
b4:0d:2c:89:f6:c3:b0:ea:69:72:7f:a3:30:88:b1:
e2:ef:4b:04:cc:d1:e9:07:a1:22:b4:d9:52:1f:24:
83:c9:5b:0c:86:c1:c7:17:fe:08:64:5e:47:cf:86:
a3:d1:37:7a:98:67:62:04:47:ec:fa:1a:9e:ef:cc:
2f:5e:25:f7:36:c4:17:55:dc:32:21:b4:98:d2:ff:
8b:92:50:e9:4d:d8:46:56:63:84:5d:19:8e:31:31:
45:02:14:84:33:f8:e8:0d:39:f6:49:88:69:10:a9:
85:d7:ec:2b:b2:3a:85:17:7d:56:d3:a6:08:46:c2:
24:45
prime2:
00:dd:8c:d7:1c:35:1a:21:7e:30:b2:ad:a2:6d:e5:
7c:74:55:ba:72:d1:14:75:4f:6d:e9:a4:ca:b1:d0:
d7:9d:a7:5a:31:6a:16:d7:0c:26:15:38:c4:36:91:
5d:de:2d:c5:e1:fd:1d:b8:20:fd:bd:dc:3a:e1:a4:
b5:d1:a6:a0:0d:7e:f2:d6:99:34:ce:18:e9:69:a2:
c5:1d:b4:da:af:a9:e8:64:d4:2f:f9:b8:bf:3e:e8:
f4:54:dc:59:d2:e1:c0:a6:cc:06:53:e2:73:7f:08:
9d:3c:c7:52:ae:97:f8:a3:8e:e3:2f:29:64:36:77:
71:71:ef:d1:85:86:01:c1:89:6e:e4:5c:e2:a0:9f:
ca:8f:26:72:db:dc:f7:d3:d8:5d:ec:c4:71:60:27:
12:a4:a7:ed:81:5a:06:83:33:ba:2d:79:a8:18:57:
67:f9:ab:ea:7d:21:a7:39:bf:dc:e2:b7:3c:54:e6:
40:9b:14:ce:b9:37:cd:44:db:2e:e6:03:af:46:c9:
d1:94:52:1b:6d:fe:7c:fb:fd:1c:6e:0a:4d:cb:d4:
32:a2:e7:fb:30:35:cf:14:0e:b2:d3:9f:d4:95:17:
23:e0:88:b4:05:38:03:f4:e1:dc:e3:66:37:3f:36:
70:76:ca:82:b5:34:43:e5:c1:c2:2f:40:d5:9b:7b:
f0:5d
exponent1:
7f:8a:27:a6:22:88:e6:e1:e5:26:87:b1:ad:1f:d2:
98:f1:a8:a4:4b:a9:bd:7d:1b:7d:c5:d5:c4:19:4a:
2f:7d:96:73:07:2c:9d:b1:b7:5c:a5:d2:41:7f:59:
94:bd:6a:8b:0b:bd:ba:c9:d6:98:5c:f7:22:7e:6d:
38:f0:7d:91:8d:ab:e9:05:8b:c6:20:6c:14:5e:63:
2c:c2:26:76:f4:ce:bf:c4:95:44:e1:7a:53:24:df:
b7:d3:64:f2:0a:1a:0e:1d:5d:64:4b:93:19:10:73:
ee:66:8b:74:c7:b8:cf:70:aa:10:82:e8:72:2c:3e:
5e:62:ac:2b:95:ed:11:fd:5c:fd:47:1f:eb:b2:fe:
5e:25:7a:4d:bf:9c:a0:0f:2f:e7:eb:7c:2a:16:28:
bb:0f:57:fb:62:9c:a6:9b:ba:93:13:2f:e4:d0:d2:
f7:b4:78:52:3a:2f:85:55:13:0b:66:f3:8a:39:ac:
12:f8:d7:08:5e:89:58:e4:ed:3b:31:a1:f4:d3:ae:
43:5a:7f:f5:d3:68:88:d3:40:ba:ed:01:19:30:4e:
b6:d0:cc:eb:0f:58:fc:66:7c:fc:08:89:ad:1c:76:
0b:8d:40:61:64:f8:dc:25:cc:86:1c:70:3f:dd:dc:
2a:f2:1c:67:d5:de:52:42:f3:7c:70:6d:09:05:68:
05
exponent2:
0c:dd:c7:08:4e:55:2c:28:c5:ef:3a:82:3a:5b:9f:
74:aa:1d:df:d9:20:95:07:7d:dc:99:c3:63:bc:3b:
29:5e:b4:b0:35:f7:09:9a:1d:04:12:7d:e2:a5:62:
8c:2a:a0:59:55:77:ca:5f:b0:1c:bc:93:76:d3:37:
f3:ea:f7:54:91:50:cd:01:ac:bd:63:58:fa:d7:87:
17:08:8f:c2:af:dd:5d:2d:ad:73:95:35:16:14:35:
4c:50:57:af:15:89:38:a6:94:9f:7e:81:32:99:6f:
78:3e:23:21:1c:96:45:f9:60:5c:36:cd:29:14:9a:
b4:01:37:6b:c7:b2:86:68:d2:d5:d4:47:1d:08:ea:
9c:91:a1:0d:ff:b1:2c:ce:5d:f6:08:1a:85:78:ff:
6e:2c:8a:70:7e:a7:ee:2a:ac:df:43:37:6d:e2:75:
99:5c:50:8b:df:ce:74:5e:1e:17:d4:88:5e:6d:d8:
c6:a8:d8:b0:8c:fb:10:ca:a1:d8:9d:d2:2a:0c:42:
6d:98:af:1b:1e:32:67:f7:f5:14:b6:e8:79:b3:e3:
14:ee:df:f9:96:c6:65:e5:cc:a0:d9:a1:60:df:2d:
28:37:08:2d:5d:69:6d:69:48:88:b4:40:f5:1c:d6:
3f:2f:d7:93:6a:6b:9f:06:37:9e:c2:e7:24:d6:77:
c9
coefficient:
00:e4:37:77:5e:05:2f:ba:4a:a9:f2:c7:5a:88:93:
2d:47:e7:92:7f:bf:18:16:71:4e:5e:a6:39:9c:fb:
06:72:fc:44:3d:7e:42:a1:f6:1c:de:ed:c1:9b:0f:
9e:40:f8:84:34:d6:22:e1:8e:ad:76:d4:52:ae:0d:
6a:37:a7:0c:a1:be:eb:83:be:b8:ea:79:67:8b:d3:
e8:59:6b:ab:e2:06:2f:1c:a2:2a:71:63:1e:1a:a1:
26:12:46:d4:f6:3a:26:85:38:bc:ea:09:da:bf:a6:
22:05:f2:d2:8f:f0:e0:7f:c4:03:52:8a:5b:cb:c0:
65:e2:9c:7b:3f:f0:88:c5:74:0c:f4:28:9e:07:7f:
fa:b7:2f:3c:d1:4a:4f:39:91:9a:d1:19:15:e3:6b:
47:82:f4:c9:ee:36:4e:a0:0f:79:84:de:6c:ac:35:
05:db:13:a7:1d:a9:34:34:df:30:5b:2e:b7:13:c5:
24:80:d1:e1:54:bb:fc:2e:07:cb:6c:89:76:b5:55:
4c:38:94:c3:d8:8c:94:7d:ca:80:b9:27:17:26:43:
d1:7d:e3:02:51:eb:e7:f3:b2:41:9e:0b:f9:08:19:
d2:b6:2c:aa:49:db:a1:e0:e4:57:34:75:d6:b9:5a:
90:ac:a4:e9:36:95:82:73:41:1c:93:a1:41:65:7f:
74:51
[ssh の RSA キーファイルから素数を取り出してみた の続きを読む]