はじめに
OpenSSHのコマンドで生成されるRSA鍵ペアについて、
なぜ秘密鍵id_rsaから公開鍵を作り出せるのか疑問に思いましたので調べてみました。
RSA鍵ペアの概要
大きな２つの素数を$p$,$q$とした場合、
N = pq \tag{1}
以下(2)を満たす変数を$L$とする。
L = lcm(p-1, q-1) \tag{2}
さらに、次の式(3)を満たす変数を$E$とする。
gcd(E, L) = 1 \tag{3}
最後に、式(4)を満たす変数を$D$とする。
ED≡1 (mod L) \tag{4}
※ lcm(x,y)はx,yの最小公倍数(Least Common Multiple)
※ gcd(x,y)はx,yの最大公約数(Greatest Common Divisor)
ここまでで求めた$(E, N)$のペアが公開鍵, $(D, N)$のペアが秘密鍵になります。
また、$E$,$D$を現実的な時間で求めるには最初の素数$p$,$q$を知っている必要があります。
OpenSSHでのRSA鍵ペア生成
OpenSSHのssh-keygenコマンドでRSA鍵ペアを作成すると
$ ssh-keygen
Generating public/private rsa key pair.
Enter file in which to save the key (/home/vagrant/.ssh/id_rsa):
Enter passphrase (empty for no passphrase): (Enter)
Enter same passphrase again: (Enter)
公開鍵id_rsa.pubと秘密鍵id_rsaが生成されます。
ssh-keygenの-yオプションはヘルプを見てみると
-y Read private key file and print public key.
と書かれており、秘密鍵を入力とし、公開鍵を出力することができます。
今回の疑問点
上記の式(4)で, $ED≡1$は$DE≡1$とも書けますので、
- なぜ秘密鍵から公開鍵が求められるのか？
- 秘密鍵Dから公開鍵Eを生成できるなら、逆に公開鍵から秘密鍵を作ることもできてしまうのでは？
という疑問が浮かびましたので、調べました。
id_rsaから公開鍵を生成できる理由
なぜ秘密鍵から公開鍵が求められるのか？
答え：ファイルid_rsaには最初に作られる素数p,qも含まれている。
これはopensslを利用すると確認することができます。
$ openssl rsa -text -noout < id_rsa
modulus:
00:dc:dc:dd:17:bb:10:3d:16:ee:cf:e7:bc:ec:e1:
...
publicExponent: 65537 (0x10001)
privateExponent:
0f:73:a0:40:2d:c5:28:10:f7:aa:31:f3:44:bb:4a:
...
prime1:
00:fe:d0:9b:2a:40:b4:7c:d1:29:05:ae:a2:46:06:
...
prime2:
00:dd:e3:d5:27:48:30:d0:3b:77:de:a8:70:a5:8f:
...
exponent1:
6e:94:e7:11:92:1d:01:a1:df:94:98:b1:d1:84:0b:
...
上記の[prime1], [prime2]が素数p,qになります。
秘密鍵Dから公開鍵Eを生成できるなら、逆に公開鍵から秘密鍵を作ることもできてしまうのでは？
答え：ファイルid_rsa.pubにはE,Nしか含まれていないので、秘密鍵を作ることはできない。