公開鍵の秘密 -追補- ― 2007/02/09 01:26
つまりは，秘密鍵から公開鍵を生成できないというのは，僕の単なる思い込みなのであった。
... とひとつ前に書いているが，厳密に言うと思い込みではない。
暗号化／復号化のために使う鍵のペアは，次のように導きだす。
まず，大きな素数をふたつ用意する。p と q とする。p と q を掛けて n を導く。n = p*q である。つぎに p と q からそれぞれ 1 を引いた数を求める。(p - 1) と (q - 1)である。この二つをかける。(p - 1)*(q - 1)。3よりも大きな数字で，この (p - 1)*(q - 1) と 1以外の公約数を持たない(つまり，たがいに素である)数を求める。これが e となる。つぎが複雑だ。「ある数に e をかけ(p - 1)*(q - 1)で割ると，あまりが 1になる」数を探す。その数が d となる。
暗号化と復号化に使うペアは，(d, n)と(e, n)だ。n を導きだした p と q は登場しない。n は十分大きな数字なので n から p と q を求めることはむずかしく，e と d はそれぞれ p と q から直接的に導きだされるから，p と q を知らなければ，e から d を導くことは難しく，また d から e を導くこともきわめて難しい。
つまり，厳密な意味では秘密鍵(d, n)から公開鍵(e, n)を求めることは計算上非常に難しく，逆もまたしかり，である。
秘密鍵から公開鍵を生成できるというのは，秘密鍵を納めた秘密鍵ファイル(OpenSSH では id_rsa)に厳密な意味での秘密鍵(d, n)以外に，計算の元となった p と q，そして (p - 1) と (q - 1)，くわえて e (公開鍵の片割れ) までもが記録されているからに過ぎない。
