このアルゴリズムは、他人に知られてもかまわない情報を2人が交換するだけで、共通の秘密の数を創りだすという方法です。作り出した秘密の数を対象鍵の鍵として使うのです。 (『新版暗号技術入門』 p280)

通信部分は省略します。今回はC言語側が素数Pと生成元Gを作るものとしました。

Javaのみでやる方が楽です。

用語とか

素数P、生成元Gという用語は文献やAPIでも大差がない気がします。今回はJavaの流儀にならって公開しない秘密の値をX (== G^A mod P) 公開の値をY (== G^B mod P) としておきます。共有する秘密は G^(A*B) mod P となります。

通信の両端とも、P,G,自分のX,Y、相手のYの5種類の情報から共通の秘密を得ます。証明詳細を差っ引いていえば「P,Gを共有して、相手のYを得て、相手に自分のYを送って、そして秘密が出来る」というだけなので、理屈の上では大変簡単なプロトコルです。ただしそれぞれの数値は非常に大きくなる可能性があり、なのでintやlongといった大して大きくない整数型ではなくBigIntegerなどの型を使うことになります。

Cサイド

『OpenSSL』がそこそこ役に立ちます。

DH_new()でまず構造体としてのDHを作ります。DHというのはこんな感じ

dh_nanodesu.h

typedef struct dh_st
{
    BIGNUM *p;  // P
    BIGNUM *g;  // G
    BIGNUM *pub_key;  // Y
    BIGNUM *priv_key;  // X
} DH;

次にDH_generate_parameters()もしくはDH_generate_parameters_ex()でDH内のPとGを作ります。これによってPとGが出来上がります。DH_check()でPとGが妥当であることもチェックします。

なお、OpenSSL (上記の書籍では0.9.6, 私が試したのは1.0.1) の実装上、Gは2か5であることが推奨されているか必須なようです。ところで、とあるJavaの実装でPとGを作らせたら、Gも大層大きなものになりました。

この段階ではまだDHのpub_key, priv_keyが出来てません。それぞれJava側のYとXに相当します。BIGNUM型です。非常にシンプルです。それらを生成するためにDH_generate_key()を使います。ひと通り生成するのはこれでおしまいです。Java側からYを得てから次のステップへ行きます。

PとGが既に与えられている場合にはDH構造体のpとgにその値を入れます。pとg自体BIGNUM構造体であるため、ネットワーク越しに来た文字列などであれば適宜変換する必要があるでしょう。例えば16進文字列であれば BN_hex2bn() を使えます。/usr/include/openssl/bn.h　といったところにBN_*についてのヘッダがあるので、そこから役に立ちそうなものを探してください。

(BN_clear_free() とか呼ぶのはもちろん忘れないように。DH_free()もあるんだよ)

上記のようによろしくp,g,pub_key,priv_keyが準備できたらDH_compute_key()で相手方から送られてきたpub_keyと組み合わせて共通の秘密をゲットします。このpub_keyは、JavaのDHPublicKey (後述します) のgetY()で取れる値です。

なお、DHPublicKeyが持つgetEncoded()はder形式の全く別のフォーマットで、Cで受け取るには多分ASN.1関係のデコードが必要です。OpenSSLにはその機能もありますが、結構面倒です。単にDHPublicKey.getY().toString(16)をネットワーク越しに投げればBN_hex2bn()でそのままデコードできます。

鍵長 (512bitsの自然数とかでしょう) を考えるとBase64にまでする理由はあまりないような気がします (あと、よく分かりませんがBase64関係のライブラリがJDKになく3rd party製を頼る必要があるのは何なんでしょう。いつも無駄に怖い)。ネットワーク挟んだ上でのランダムな素数のエンコードデコードに絡んだバグは、自分で試した限りでは結構めんどくさい。あんまり最初のうちからここで最適化するのはおすすめしません。

Javaサイド

わざわざ解説するのがめんどくさいのでコードで語ります

dh.java

      KeyFactory keyFactory = KeyFactory.getInstance("DH");
      DHPublicKeySpec senderKeySpec = new DHPublicKeySpec(y, p, g);
      PublicKey senderPublic = keyFactory.generatePublic(senderKeySpec);
      KeyPairGenerator receiverKeyPairGen =
               KeyPairGenerator.getInstance("DH");
      receiverKeyPairGen.initialize(((DHKey) mSenderPublic).getParams());

      KeyPair receiverKeyPair = receiverKeyPairGen.generateKeyPair();
      PrivateKey receiverPrivate = receiverKeyPair.getPrivate();
      PublicKey receiverPublic = receiverKeyPair.getPublic();
      KeyAgreement receiverAgreement = KeyAgreement.getInstance("DH");
      receiverAgreement.init(mReceiverPrivate);

      receiverAgreement.doPhase(mSenderPublic, true);

慣れるまでわっかりづらいんですが、PとGとYがどうやってデータ構造に流れ込んでて、いつ(Java側の)Xが準備されるかを想像すればそれなりに動きが分かります。なお、senderPublicやreceiverPublic,receiverPrivateから再びPとGを取るためにはgetParams()経由にします。

receiverAgreement.generateSecret() でbyte[] 型の shared secret が出てきます。これが G^(A*B) mod P そのものなので、これを16進の文字列に変換すればC側は受け取りやすいと思われます。

poor_enc.java

    // あんまり良い実装でない気がするがないよりはまし
    public static String toHexString(byte[] array) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < array.length; i++) {
            String hex = Integer.toHexString(array[i] & 0xff);
            if (hex.length() == 1) {
                builder.append('0');
            }
            builder.append(hex);
        }
        return builder.toString();
    }

C側が同じ結果を生成できる必要があるので、あわせて((DHPublicKey)receiverPublic).getY().toSring(16)も返しておく必要があります。

でばっぐ

一般論としてはP,GはともかくX,Yの所有者情報を忘れないようにしたほうが良いです。getY()……はて、このYはどちらの公開した値なのだろうか、という話です。Javaの型情報にしろCのDHにしろ、所有者は型に記載されてません。"sender"とか"receiver"とかいうプレフィックスをつけてアプリケーションハンガリアン記法の恩恵を得ましょう (参考)

C側については値が丸見えなのでそれをdumpしてがんばるしかありません。生のDiffie Hellmanなので分かりやすいっちゃ分かりやすいです。

Java側はいい具合に邪魔な抽象化がされているので少し注意が必要な部分があります。

getEncoded() は今回のようにC/Java間で遊ぶだけなら使わないほうがマシです。Java同士で通信する場合は正反対で、X509EncodedKeySpec が getEncoded() の結果をそのまま良きに計らって解釈してくれるので、Java間の通信ならこちらを使うのが流儀でしょう。

少なくともgetEncoded()をYそのものだと勘違いすると地獄が待っています。

Java単体であってもまともに実装している例があまりに見受けられないので、コピペするときはいつも注意しましょう。

で？

結果共有されるのはとっても大きな自然数一つだけです。中間者攻撃にも弱いのがDHの特徴だと思われます。

というわけで他の人が必要な知識かどうかはよく分かりませんが、出来ることは分かりました。

C (OpenSSL) とJava間でDiffie Hellman 鍵交換

用語とか

Cサイド

Javaサイド

でばっぐ

で？