えてにつき

次に ssh-keygen が実際に秘密鍵を作成する部分のコードを見てみる。
ssh-keygen.c をたどっていくと、

   1338         private = key_generate(type, bits);
   1339         if (private == NULL) {
   1340                 fprintf(stderr, "key_generate failed");
   1341                 exit(1);
   1342         }

となっている。private は Key 型へのポインタである。key_generate() は key.c で定義されている。

    594 Key *
    595 key_generate(int type, u_int bits)
    596 {
    597         Key *k = key_new(KEY_UNSPEC);
    598         switch (type) {
    599         case KEY_DSA:
    600                 k->dsa = dsa_generate_private_key(bits);
    601                 break;
    602         case KEY_RSA:
    603         case KEY_RSA1:
    604                 k->rsa = rsa_generate_private_key(bits);
    605                 break;
    606         default:
    607                 fatal("key_generate: unknown type %d", type);
    608         }
    609         k->type = type;
    610         return k;
    611 }

key_generate() はとても短い。key->type が KEY_RSA のときには、rsa_generate_private_key() を呼び出す。この関数は key.c で定義されている。

    569 static RSA *
    570 rsa_generate_private_key(u_int bits)
    571 {
    572         RSA *private;
    573
    574         private = RSA_generate_key(bits, 35, NULL, NULL);
    575         if (private == NULL)
    576                 fatal("rsa_generate_private_key: key generation failed.");
    577         return private;
    578 }

鍵が RSA 形式の時には、rsa_generate_private_key() の中で RSA_generate_key() を呼んでいる。紛らわしいが、大文字で始まるほうの RSA_generate_key() は、openssl のソースに含まれているので、これ以上 OpenSSH のソースコードを漁っても何も得られない。

openssl-0.9.8d を展開したあと、crypto ディレクトリに移動するとそこに rsa_depr.c というソースコードがある。RSA_generate_key() はそこに定義されている。

     71 RSA *RSA_generate_key(int bits, unsigned long e_value,
     72              void (*callback)(int,int,void *), void *cb_arg)
     73         {
...中略
     92         if(RSA_generate_key_ex(rsa, bits, e, &cb)) {
     93                 BN_free(e);
     94                 return rsa;
     95         }

とまぁ、RSA_generate_key() のなかでは今度は RSA_generate_key_ex() を呼び出している。_ex つきの関数は rsa_gen.c の定義されている。これで何度目のリダイレクトだ？

rsa_gen.c では、

    78 int RSA_generate_key_ex(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb)
     79         {
     80         if(rsa->meth->rsa_keygen)
     81                 return rsa->meth->rsa_keygen(rsa, bits, e_value, cb);
     82         return rsa_builtin_keygen(rsa, bits, e_value, cb);
     83         }

RSA_generate_key_ex() の関数は、これがすべてである。

本当の鍵の生成は rsa_builtin_keygen() を呼び出しておこなっており、rsa_builtin_keygen() は RSA_generate_key() の直後から定義されている。この関数は長いので割愛。

さて、話を元に戻すと、key_generate() の結果を private (Key 型へのポインタ)に保存すると、その先の処理は大きく分けて二つある。一つは private から公開鍵を生成すること、そしてもうひとつは private を秘密鍵として保存することである。

もう一度 key_generate() の部分を ssh-keygen.c から抜き出すと下記のとおりで、これは今回の冒頭に挙げているものと同じだ。

   1338         private = key_generate(type, bits);
   1339         if (private == NULL) {
   1340                 fprintf(stderr, "key_generate failed");
   1341                 exit(1);
   1342         }

private = key_generate(type, bits); の処理で、private には RSA の鍵情報が入っている。この直後に、

   1343         public  = key_from_private(private);

として、private の内容から公開鍵の情報を取り出して、やはり Key 型へのポインタである public へ代入している。

そして、最終的に、

   1405         if (!key_save_private(private, identity_file, passphrase1, comment)) {
   1406                 printf("Saving the key failed: %s.\n", identity_file);
   1407                 memset(passphrase1, 0, strlen(passphrase1));
   1408                 xfree(passphrase1);
   1409                 exit(1);
   1410         }

と、key_save_private() で identity_file に設定されているファイルへ書き出すのである。

最後に見るのは、key_save_private() だ。この関数は OpenSSH の authfile.c で定義されている。

    204         switch (key->type) {
    205         case KEY_DSA:
    206                 success = PEM_write_DSAPrivateKey(fp, key->dsa,
    207                     cipher, passphrase, len, NULL, NULL);
    208                 break;
    209         case KEY_RSA:
    210                 success = PEM_write_RSAPrivateKey(fp, key->rsa,
    211                     cipher, passphrase, len, NULL, NULL);
    212                 break;
    213         }

と、key->type が KEY_RSA なら PEM_write_RSAPrivateKey() を呼び出す。この PEM_write_RSAPrivateKey() はマクロで、openssl-0.9.8d/crypto/pem/pem.h に次のように定義されている。

    409 #define PEM_write_RSAPrivateKey(fp,x,enc,kstr,klen,cb,u) \
    410                 PEM_ASN1_write((int (*)())i2d_RSAPrivateKey,PEM_STRING_RSA,fp,\
    411                         (char *)x,enc,kstr,klen,cb,u)

つまり、PEM_ASN1_write である、と。

openssl-0.8.9d/crypto/pem/pem_lib.c に実際の PEM_ASN1_write() が定義されている。

結果から言うと、PEM_ASN1_write() からは更に PEM_ASN1_write_bio() を呼び出しており、正真正銘、これが最終最後の場所なのだが、はっきりいって、中身をみても良くわからん... 結局、ssh-keygen で id_rsa を生成するときに、p、q、d、n、e の情報を格納していると確信できる部分までだ取り付けていない。今後の宿題かなぁ...

暗号関連、嫌いです。

完結編。

やはり，まずは標準にあたるべきである。

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時間。無駄だったのか，楽しかったのか...