公開鍵の秘密 -追補- 2 ― 2007/02/09 13:52
さて、昨日までの勉強で秘密鍵ファイルには、秘密鍵のほかにも公開鍵や、それらを生成する材料となったふたつの素数までもが格納されているらしいことがわかった。
実際に OpenSSH の ssh-keygen のコードを見てみよう。下は OpenSSH 4.5-p1 に含まれる ssh-keygen.c からの抜粋だ。do_convert_private_ssh2_from_blob() という関数が実際に -y オプションを与えられたときに RSA の秘密鍵の処理を行っている部分のようだ。 訂正: この関数は、秘密鍵を SSH2 形式へ変更する -X オプションを指定したときに呼ばれる関数である。
この関数は、一連のデータのかたまり(鍵の元となる)とその長さを受け取り、Key 型へのポインタを返す。この関数は結構な長さがあるので該当部分だけ抜き出すと、次のようになる。
278 switch (key->type) { 279 case KEY_DSA: 280 buffer_get_bignum_bits(&b, key->dsa->p); 281 buffer_get_bignum_bits(&b, key->dsa->g); 282 buffer_get_bignum_bits(&b, key->dsa->q); 283 buffer_get_bignum_bits(&b, key->dsa->pub_key); 284 buffer_get_bignum_bits(&b, key->dsa->priv_key); 285 break; 286 case KEY_RSA: 287 e = buffer_get_char(&b); 288 debug("e %lx", e); 289 if (e < 30) { 290 e <<= 8; 291 e += buffer_get_char(&b); 292 debug("e %lx", e); 293 e <<= 8; 294 e += buffer_get_char(&b); 295 debug("e %lx", e); 296 } 297 if (!BN_set_word(key->rsa->e, e)) { 298 buffer_free(&b); 299 key_free(key); 300 return NULL; 301 } 302 buffer_get_bignum_bits(&b, key->rsa->d); 303 buffer_get_bignum_bits(&b, key->rsa->n); 304 buffer_get_bignum_bits(&b, key->rsa->iqmp); 305 buffer_get_bignum_bits(&b, key->rsa->q); 306 buffer_get_bignum_bits(&b, key->rsa->p); 307 rsa_generate_additional_parameters(key->rsa); 308 break; 309 }
key->type が KEY_RSA の場合には、はやり p, q, n, d, e を格納取り出している。
公開鍵の秘密 -追補- ― 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 (公開鍵の片割れ) までもが記録されているからに過ぎない。
公開鍵の秘密 -5- 完結編 ― 2007/02/09 00:19
完結編。
やはり,まずは標準にあたるべきである。
RFC 2313 - PKCS #1: RSA Encryption Version 1.5のセクション 7.2 にこうある。
7.2 Private-key syntax An RSA private key shall have ASN.1 type RSAPrivateKey: RSAPrivateKey ::= SEQUENCE { version Version, modulus INTEGER, -- n publicExponent INTEGER, -- e privateExponent INTEGER, -- d prime1 INTEGER, -- p prime2 INTEGER, -- q exponent1 INTEGER, -- d mod (p-1) exponent2 INTEGER, -- d mod (q-1) coefficient INTEGER -- (inverse of q) mod p } Version ::= INTEGER The fields of type RSAPrivateKey have the following meanings: o version is the version number, for compatibility with future revisions of this document. It shall be 0 for this version of the document. o modulus is the modulus n. o publicExponent is the public exponent e. o privateExponent is the private exponent d. o prime1 is the prime factor p of n. o prime2 is the prime factor q of n. o exponent1 is d mod (p-1). o exponent2 is d mod (q-1). o coefficient is the Chinese Remainder Theorem coefficient q-1 mod p.
つまり,秘密鍵には encryption exponent も decryption exponent も両方格納されている。ご丁寧に,直後の note には,
2. The presence of the public exponent e is intended to make it straightforward to derive a public key from the private key.
ここで public exponent といっているのは,encryption exponent と同義だ。つまりは,public exponent(公開指数,暗号化指数)がここにあるのは,秘密鍵から公開鍵を容易に生成できるようにするためであると明解に書かれている。
あー。すっきりした。
つまりは,秘密鍵から公開鍵を生成できないというのは,僕の単なる思い込みなのであった。
正確には decryption exponent (d) と moduli (n) の組み合わせ(これが厳密な意味での秘密鍵だ)からは,encryption exponent (e) と moduli (n) の組み合わせ -- 公開鍵 -- は推測できない。だが,秘密鍵を格納しているファイルには,公開鍵を生成するための encryption exponent (public exponent)が仕込まれていたんである。
ソースを追いかけること 3時間。無駄だったのか,楽しかったのか...
公開鍵の秘密 -4- ― 2007/02/08 23:07
転生編。
普段職場で RTM とというと,それは Release To Manifacturer である。製品の CD / DVD をプレスする工場へゴールデンマスター(製品のマスターコピー)を送る作業のことをいう。転じて,製品の開発が終了した状態を指すようになった。「次期バージョンの RTM が二ヶ月遅れる」というのは,開発期間が伸びて市場に投入する時期が二ヶ月遅れるという悪い知らせだ。
もちろん,今日の RTM はもうひとつの RTM: Read The Manualである。
そもそもの疑問は,「秘密鍵から公開鍵は計算できないはず」というものであった。であるのに,SSH-AUTH の段階でクライアントは平然と id_rsa (秘密鍵を納めたファイル)から公開鍵を生成しているんである。
OpenSSH のソースをあちこち這いずり回ったあげく,load-identity-file() 関数のその先は,openssl の rsa.c を見ないと答えがわからないことがわかった。でもって openssl のソースはいま手元にない。
ところで,ひょんなことから ssh-keygen(1)のマニュアルを読んでいたら,次のオプションがあることに気がついた。
-y This option will read a private OpenSSH format file and print an OpenSSH public key to stdout.
ここにははっきりと秘密鍵を納めたファイルから公開鍵を生成できることが書いてある。
ためしてみると,
$ ssh-keygen -y Enter file in which the key is (/Users/ats/.ssh/id_rsa): Enter passphrase: ssh-rsa AAAAB3NzaC1yc2EAAAABIwAAAQEAuSlWJTJpZ8pKPCbOyYyVhmQaTSvmfz1r8uZ5cnakts8K x1Vgsruu9bfSqC7CF2zVs2QNSOo8BotkjVBEg3npf8RaPRit4i/f2MYihveUustg9HT56bD4ZMQq/+0W SZpYedzL2AMTeqzGgj2Z6CoY3ypMOEmvMpArTcwAapv9esxUpeikjggcY+99c50gCGjf0Gb6MJT8eSqA yL5oh5chcYOS1PevCihoo5qoESr7ZAdVvzplsjsRwmKhHDjpo6jxGpqqGaf/5jz2OE78tUV2uhd2FHts NtZw7ewRiDLSdEO1z2iPYXyXyu+M+ZwuzY37u6ZoFkuKCCKs3/l+db6Isw== $ cat id_rsa.pub ssh-rsa AAAAB3NzaC1yc2EAAAABIwAAAQEAuSlWJTJpZ8pKPCbOyYyVhmQaTSvmfz1r8uZ5cnakts8K x1Vgsruu9bfSqC7CF2zVs2QNSOo8BotkjVBEg3npf8RaPRit4i/f2MYihveUustg9HT56bD4ZMQq/+0W SZpYedzL2AMTeqzGgj2Z6CoY3ypMOEmvMpArTcwAapv9esxUpeikjggcY+99c50gCGjf0Gb6MJT8eSqA yL5oh5chcYOS1PevCihoo5qoESr7ZAdVvzplsjsRwmKhHDjpo6jxGpqqGaf/5jz2OE78tUV2uhd2FHts NtZw7ewRiDLSdEO1z2iPYXyXyu+M+ZwuzY37u6ZoFkuKCCKs3/l+db6Isw== ats@mika.local
まさしく,id_rsa から id_rsa.pub と同一の内容を生成している。
... となると,秘密は id_rsa のファイル形式にある。
まだまだ続く。
公開鍵の秘密 -3- ― 2007/02/08 17:58
... さらにつづく。
早速 OpenSSH 4.5p1 のソースを落としてきて眺めてみた。
sshconnect2.c の userauth_pubkey() 関数あたりが、実際に公開鍵認証を実行しているクライアント側のコードのようである。
userauth_pubkey() の中盤あたりはこうなっている。
1121 if (id->key && id->key->type != KEY_RSA1) { 1122 debug("Offering public key: %s", id->filename); 1123 sent = send_pubkey_test(authctxt, id); 1124 } else if (id->key == NULL) { 1125 debug("Trying private key: %s", id->filename); 1126 id->key = load_identity_file(id->filename); 1127 if (id->key != NULL) { 1128 id->isprivate = 1; 1129 sent = sign_and_send_pubkey(authctxt, id); 1130 key_free(id->key); 1131 id->key = NULL; 1132 } 1133 }
つまり、ここまでの流れの中で id->key に値が設定されていないと、公開鍵が見つからなかったと判断して、load_identity_file()関数を呼んで秘密鍵を得る。(1126行目)。引数の id->filename は ssh コマンドを実行したときに -i オプションで渡したファイル名がセットされている。
id->key に秘密鍵を読み込んだところで、sign_and_send_pubkey() を呼び出す。この関数は同じ sshconnect2.c に定義されていて、サーバーへの接続はこの関数の中で行われる。sign_and_send_pubkey() では、
869 if (key_to_blob(id->key, &blob, &bloblen) == 0) { 870 /* we cannot handle this key */ 871 debug3("sign_and_send_pubkey: cannot handle key"); 872 return 0; 873 }
と、869行目で key_to_blob() 関数に読み込んだ秘密鍵を渡している。
key_to_blob() 関数は id->key に格納されている秘密鍵から "blob"へと変換する。blob とは「ひとかたまり」を意味する英単語で、データベースの Binary Large Object のことではない。
その key_to_blob() は key.c で定義されている。実際に秘密鍵から blob に変換する部分のコードは次の通りだ。
757 switch (key->type) { 758 case KEY_DSA: 759 buffer_put_cstring(&b, key_ssh_name(key)); 760 buffer_put_bignum2(&b, key->dsa->p); 761 buffer_put_bignum2(&b, key->dsa->q); 762 buffer_put_bignum2(&b, key->dsa->g); 763 buffer_put_bignum2(&b, key->dsa->pub_key); 764 break; 765 case KEY_RSA: 766 buffer_put_cstring(&b, key_ssh_name(key)); 767 buffer_put_bignum2(&b, key->rsa->e); 768 buffer_put_bignum2(&b, key->rsa->n); 769 break;
ここで問題となるのが 767行目と 768行目の key->rsa->e と key->rsa->n だ。RSA とはつまりは秘密鍵と公開鍵の二つの非対称鍵を使うしくみなのだが、rsa->e は encryption exponent (暗号化指数)、rsa->n は RSA moduli (OpenSSH では public moduli: 係数) を意味する。rsa->e と rsa->n の組み合わせが公開鍵となり、秘密鍵は rsa->d (decryption exponent: 復号化指数) と rsa->n の組み合わせになる。
上記の流れで行くと、userauth_pubkey() で秘密鍵を id->key にロードし、さらに key_to_blob() で id->key にセットされている秘密鍵から暗号化指数 rsa->e と係数 rsa->n を読み出している。
さて。困った。
秘密鍵がもっているのは、復号化指数 (rsa->d)と係数(rsa->n)ではないのか?
userauth_pubkey() で秘密鍵を読み出しておきながら、つづく key_to_blob() でその秘密鍵から暗号化指数 (rsa->e)を読み出せているリクツはなんだろう。
load_identity_file() で id->key になにをロードしているのか調べる必要がある。
まだつづく... が...
どうも、RSA の基本からやりなおさなければだめなようだ...
公開鍵の秘密 -2- ― 2007/02/06 23:51
つづき。
RFC4252- The Secure Shell (SSH) Authentication Protocolを読んでみた。
7. Public Key Authentication Method: "publickey" -- snip -- To perform actual authentication, the client MAY then send a signature generated using the private key. The client MAY send the signature directly without first verifying whether the key is acceptable. The signature is sent using the following packet: byte SSH_MSG_USERAUTH_REQUEST string user name string service name string "publickey" boolean TRUE string public key algorithm name string public key to be used for authentication string signature
と書いてある。読む限り,やはり Public Key Authentication では public key を実際にクライアントから送っても『よい(MAY)』送ることになっている。
『よい』というのは,必須(MUST)ではない。よく読むと、MAY なのは、この前段で boolean に FALSE を設定したパケットを送って、サーバが公開鍵認証を受け付けるかどうかを調べる手間を省いて、いきなり上記のパケットを投げつけても『良い』ということだった。
ここから先は実装依存ということか。OpenSSH のソースを見る必要があるのか... くぅ。
公開鍵の秘密 ― 2007/02/06 17:52
わけあって SSH と戯れている今日このごろ。
基本から勉強しようと思い、新山祐介著『入門 OpenSSH』を Amazon で購入。文章は読みやすく説明も丁寧なので,すらすらと2時間ほどで読破したわけだが...
この本の P.41 の脚注に気になる記述がある。ユーザーが公開鍵認証でログインする仕組みを説明している本文についている脚注なのだが、全文引用すると、
厳密には、クライアントはまず自分の持っている秘密鍵に対応する公開鍵をサーバに送ります。その公開鍵がサーバに登録されている場合、サーバはある秘密の値をその鍵によって暗号化してクライアントに送ります。公開鍵によって暗号化された情報を正しく復号するにはそれに対応する秘密鍵が必要なため、もしクライアントがその値を正しく復号して送り返してくれば、そのクライアントは対応する秘密鍵をもっていると確信できます。
とある。さて問題となるのは冒頭の『厳密には、クライアントはまず自分の持っている秘密鍵に対応する公開鍵をサーバに送ります。』の部分だ。
TeraTerm Pro でも PuTTY でもなんでもいいのだが、SSH クライアントの導入手順をネットで調べてみるとすぐに疑問にぶつかる。どの説明でも、クライアントに公開鍵 (id_rsa.pub もしくは id_dsa.pub)をコピーする手順がないのだ。ほとんどの説明で、秘密鍵(id_rsa もしくは id_dsa)のみをクライアントにコピーしている。
『入門 OpenSSH』の記述間違いなのか。それにしては、サーバ側の ~/.ssh/authorized_keys に複数の公開鍵が登録されていても、sshd はクライアントが保持している秘密鍵に対応する公開鍵を迷うことなく見つけ出している。sshd のログをみながら確認してみたが、ユーザーの正しい公開鍵を見つけだすのに苦労しているそぶりはない。
クライアントはどうやって公開鍵をサーバへ送っているのだろう。秘密鍵から公開鍵が生成できるはずもなく...
sshd はどうやって、クライアントが保持している秘密鍵に対応する公開鍵をみつけるの?
だれかおしえて。
Backup... ― 2005/12/02 09:55
ずっと使っていなかったけれど、iMac G5 は DVD を焼けるので、溜まった写真を DVD で保存しておこうと思い立ち、試しに使ってみた。
なんと、Backup で DVD を焼くと、Backup でリストアしない限りは読めない。プロプライエタリな形式...
写真の保存は単なるフォルダコピーにして、Backup は Key Chain を .mac に保存する用途だけに使おうと思ったのであった。
Music on the Air ― 2005/12/02 00:01
iTunes で音楽の再生をすると、無線 LAN 経由でステレオに接続された Air Mac Express まで「音楽」が飛んでいき、ステレオから音楽が流れ出してくる。iMac とステレオは無線 LAN で接続されているから、物理的な結線はいっさい必要ない。音楽が空を飛んでいってステレオのスピーカーから再生されるわけだ。
これはいい。
CD をかけかえる必要がない。iTunes で音楽を流しっぱなしにしておけば、つぎからつぎへとステレオから流れ続ける。さながらジュークボックスだ。便利だねぇ。
iMac G5 届く ― 2005/11/29 23:07
G4 Cube からメールやら写真やらを転送して、それから Office v.X を入れてアップデートかけて、Illustrator と Photoshop Elements 入れてこれもアップデートかけて... 結構やることあるなぁと思いながらセットアップを開始したら、あなた。
「他の mac からデータや設定を移動しますか?」と聞いてくるではないか。
やおらに Cube をターゲットモードで起動し、FireWire ケーブルで iMac G5 と直結し、「次へ」ボタンを押す。30G byte 分のデータの転送を待つこと 20分。ネットワークの設定も .Mac への接続も、iTunes や iPhoto のライブラリ、Safari のブックマーク、Mail のデータ、もちろん Cube に導入していたたくさんのアプリケーションもすべてが移行された形で Mac OS X Tiger が起動したのであった。
うーん。手間いらず。かゆいところに手が届く。だからすきなんだよ、Apple。
最近のコメント