C#で楕円曲線暗号を使いたい① ― BouncyCastleのECIESでつまずく

C#で楕円曲線暗号を使いたい①

BouncyCastleのECIESでつまずく

RSAみたいなことを楕円曲線暗号でもやりたい

公開鍵暗号として、まず思い浮かぶのはRSAです。

ものすごく単純化すると、秘密鍵と公開鍵のペアを作り、公開鍵は相手に渡してよい。相手はその公開鍵を使って暗号化し、暗号文は対応する秘密鍵を持っている本人だけが復号できる、という仕組みです。

もちろん実際のRSAでは、パディング方式なども重要ですし、大量のデータをRSAで直接暗号化するわけでもありません。

ただ、

「公開鍵は配ってよい。しかし復号できるのは秘密鍵を持った本人だけ」

という考え方は非常に分かりやすい。

ところが暗号技術について調べていると、RSAとは別に楕円曲線暗号（ECC: Elliptic Curve Cryptography）というものが頻繁に出てきます。

RSAが素因数分解の難しさを利用するのに対し、ECCは楕円曲線上の離散対数問題という、まったく別の数学的問題を利用します。

また、ECCは同程度の安全性をRSAより短い鍵で実現できる、という特徴があります。

そこで思いました。

RSAでできる「相手の公開鍵で暗号化し、相手の秘密鍵で復号する」ということを、楕円曲線暗号でもできないものだろうか。

今回の話は、そこから始まります。

楕円曲線では何をしているのか

「楕円曲線暗号」と聞くと、かなり取っつきにくい名前です。

私も最初はそうでした。

ただ、実数上の楕円曲線を使って幾何学的に眺めると、雰囲気は少し掴みやすくなります。

曲線上の点 P で接線を引きます。

接線はもう一度曲線と交わります。

その交点を R として、R を x 軸について反転すると 2P が得られます。

このGIFはあくまで幾何学的なイメージです。

実際の楕円曲線暗号では、実数の滑らかな曲線上ではなく、有限体上で点演算を行います。

それでも、

ある点に対して点の加算や倍算を繰り返し、別の点を得る。

という感覚を掴むには、この図が分かりやすいと思います。

楕円曲線暗号では、基準となる点 G に対して、秘密の整数 k を使い、

Q = kG

という計算をします。

G : みんなが知っている基準点
k : 秘密にしておく整数
Q : 公開してよい点

k から Q を計算するのは簡単です。

しかし、G と Q が分かっていても、

Q = kG

を満たす k を逆算するのは非常に困難です。

これが楕円曲線離散対数問題です。

kG は簡単に計算できるのに、G と kG から k を求めるのは極端に難しい。

この非対称性が、楕円曲線暗号の安全性の土台になっています。

なぜ順方向は速く、逆方向は難しい？

秘密の回数 k が分かっている本人は、倍算を使って kG を効率よく計算できます。

たとえば k = 13 なら、

13 = 8 + 4 + 1

なので、

G → 2G → 4G → 8G

と倍々に進めて、最後に必要な 4G と G を足せば、

13G = 8G + 4G + G

と求められます。

つまり、回数 k が分かっている順方向では、2進数展開を使って目的の点まで「飛び飛び」に計算できます。

しかし第三者は、出発点 G と到着点 kG を見ても、その k を知りません。

そのため、本人と同じように「8まで飛んで、4を足して、1を足す」といった進み方ができません。

回数が分かっていれば、倍算を使って目的の点まで飛び飛びに計算できる。
しかし回数が分からないと、その“飛び方”自体が分からないため、広い候補を探索する必要がある。

厳密には、単純に G, 2G, 3G... と一つずつ試すしかないわけではありません。より効率のよい探索アルゴリズムも存在します。

それでも、十分に大きなパラメータを使えば、現実的な時間で秘密の k を求めることは困難です。

ECIESを見つけた

さて。

楕円曲線でも秘密鍵と公開鍵のペアが作れる。

だったら次に考えることは単純です。

この公開鍵を使って、RSAのように暗号化できないのか？

調べてみると、いかにもそれらしい名前の方式が見つかりました。

ECIES

Elliptic Curve Integrated Encryption Scheme。

名前だけ見れば、

Elliptic Curve
Encryption Scheme

です。

まさに探していたものに見えます。

「これだろう」

と思いました。

ECIESを使えば、受信者の公開鍵で暗号化し、受信者の秘密鍵で復号する、というRSAに近い見え方ができます。

そこでC#から利用できるライブラリを探し、試してみたのが、

BouncyCastle.Cryptography

です。

当時使用していたバージョンは、

BouncyCastle.Cryptography 2.4.0

でした。

BouncyCastleでECIESを試す

やりたいことは単純です。

まず楕円曲線の鍵ペアを作ります。

AsymmetricCipherKeyPair keyPair =
    ECCUtilities.GenerateKeyPair();

AsymmetricKeyParameter publicKey =
    keyPair.Public;

AsymmetricKeyParameter privateKey =
    keyPair.Private;

AsymmetricCipherKeyPair keyPair =
    ECCUtilities.GenerateKeyPair();

AsymmetricKeyParameter publicKey =
    keyPair.Public;

AsymmetricKeyParameter privateKey =
    keyPair.Private;

そして、公開鍵で暗号化します。

public static byte[] Encrypt(
    string plaintext,
    AsymmetricKeyParameter publicKey)
{
    byte[] inputBytes =
        Encoding.UTF8.GetBytes(plaintext);

    IBufferedCipher cipher =
        CipherUtilities.GetCipher("ECIES");

    ParametersWithRandom pwr =
        new ParametersWithRandom(publicKey);

    cipher.Init(true, pwr);

    return cipher.DoFinal(inputBytes);
}

public static byte[] Encrypt(
    string plaintext,
    AsymmetricKeyParameter publicKey)
{
    byte[] inputBytes =
        Encoding.UTF8.GetBytes(plaintext);

    IBufferedCipher cipher =
        CipherUtilities.GetCipher("ECIES");

    ParametersWithRandom pwr =
        new ParametersWithRandom(publicKey);

    cipher.Init(true, pwr);

    return cipher.DoFinal(inputBytes);
}

復号側では秘密鍵を渡します。

public static string Decrypt(
    byte[] encryptedBytes,
    AsymmetricKeyParameter privateKey)
{
    IBufferedCipher cipher =
        CipherUtilities.GetCipher("ECIES");

    cipher.Init(false, privateKey);

    byte[] decryptedBytes =
        cipher.DoFinal(encryptedBytes);

    return Encoding.UTF8.GetString(decryptedBytes);
}

public static string Decrypt(
    byte[] encryptedBytes,
    AsymmetricKeyParameter privateKey)
{
    IBufferedCipher cipher =
        CipherUtilities.GetCipher("ECIES");

    cipher.Init(false, privateKey);

    byte[] decryptedBytes =
        cipher.DoFinal(encryptedBytes);

    return Encoding.UTF8.GetString(decryptedBytes);
}

呼び出し側は、

string originalText = "Hello, world!";

byte[] encrypted =
    ECCUtilities.Encrypt(originalText, publicKey);

string decrypted =
    ECCUtilities.Decrypt(encrypted, privateKey);

Console.WriteLine("Original : " + originalText);
Console.WriteLine("Decrypted: " + decrypted);

string originalText = "Hello, world!";

byte[] encrypted =
    ECCUtilities.Encrypt(originalText, publicKey);

string decrypted =
    ECCUtilities.Decrypt(encrypted, privateKey);

Console.WriteLine("Original : " + originalText);
Console.WriteLine("Decrypted: " + decrypted);

期待する結果は、

Original : Hello, world!
Decrypted: Hello, world!

これで、「楕円曲線の公開鍵で暗号化できた！」となる。

……はずでした。

NotImplementedException

ところが実行すると、暗号化そのものに入る前の初期化処理で例外になりました。

System.NotImplementedException
IES

発生箇所はここです。

cipher.Init(true, pwr);

最初は、

鍵の作り方がおかしいのか？

と思いました。

あるいは、

"ECIES" という指定方法が違うのか？

とも考えました。

しかし、少し妙です。

もしBouncyCastleがECIESという暗号方式そのものを知らないのであれば、

CipherUtilities.GetCipher("ECIES")

の時点でエラーになってもおかしくありません。

ところが、ここは通ります。

GetCipher("ECIES") は、ちゃんとCipherオブジェクトを返してきます。

その次の、

cipher.Init(true, pwr);

で、

NotImplementedException

になる。

ECIESという名前は認識している。

なのに、

実行しようとすると「未実装」と言われる。

どういうことでしょう。

こうなると、ライブラリの外側だけ眺めていてもよく分かりません。

BouncyCastleのソースコードを追ってみることにしました。

CipherUtilities.GetCipher(“ECIES”)の中を追う

入口はここです。

CipherUtilities.GetCipher("ECIES");

CipherUtilities のコードを見ると、指定されたアルゴリズム名から実際に使用するCipherを生成しています。

概略はこんな流れです。

GetCipher("ECIES")
        ↓
GetMechanism("ECIES")
        ↓
GetCipherForMechanism("ECIES")

そして GetCipherForMechanism() の中を見ると、ECIESの場合には、

basicAgreement = new ECDHBasicAgreement();

basicAgreement = new ECDHBasicAgreement();

が生成されています。

さらに、

return new BufferedIesCipher(
    new IesEngine(
        basicAgreement,
        new Kdf2BytesGenerator(new Sha1Digest()),
        new HMac(new Sha1Digest())
    )
);

return new BufferedIesCipher(
    new IesEngine(
        basicAgreement,
        new Kdf2BytesGenerator(new Sha1Digest()),
        new HMac(new Sha1Digest())
    )
);

という形で、

ECDHBasicAgreement
       ↓
    IesEngine
       ↓
BufferedIesCipher

が組み立てられています。

ここで、ひとつ気になる名前が出てきました。

ECDHBasicAgreement

ECDH。

この名前は覚えておいてください。

次回の記事で主役になります。

今回はまず、このまま NotImplementedException の原因を追います。

cipherの正体はBufferedIesCipher

先ほど、

IBufferedCipher cipher =
CipherUtilities.GetCipher(“ECIES”);

としていました。

型としては IBufferedCipher ですが、ECIESを指定した場合に実際に返されているのは、

BufferedIesCipher

です。

では、このクラスの Init() を見てみます。

すると、

public override void Init(
    bool forEncryption,
    ICipherParameters parameters)
{
    this.forEncryption = forEncryption;

    throw new NotImplementedException("IES");
}

public override void Init(
    bool forEncryption,
    ICipherParameters parameters)
{
    this.forEncryption = forEncryption;

    throw new NotImplementedException("IES");
}

……。

ありました。

そのままです。

throw new NotImplementedException("IES");

本当に未実装だった

つまり、

CipherUtilities.GetCipher("ECIES")

という入口は存在します。

ECIESを指定すると、

ECDHBasicAgreement
       ↓
IesEngine
       ↓
BufferedIesCipher

まで組み立てられます。

ところが実際に、

cipher.Init(...)

を呼び出すと、

throw new NotImplementedException("IES");

です。

こちらの公開鍵の渡し方が悪いとか、秘密鍵がおかしいとか、楕円曲線のパラメータが違うとか、それ以前の話でした。

この高水準APIの初期化処理が実装されていません。

「楕円曲線暗号では公開鍵暗号化できない」という意味ではない

ここは誤解しやすいので整理しておきます。

今回分かったのは、

BouncyCastle.Cryptographyで CipherUtilities.GetCipher(“ECIES”) から得られる BufferedIesCipher の Init() が未実装だった

ということです。

したがって、

楕円曲線暗号では公開鍵を使った暗号化ができない

という意味ではありません。

また、

ECIESという方式そのものが未完成である

という意味でもありません。

あくまで、

BouncyCastle C#の、この高水準APIを使うルートでは処理を開始できなかった。

という話です。

しかし当時の自分にとっては、ここで一度行き止まりになりました。

RSAなら、

公開鍵で暗号化
     ↓
秘密鍵で復号

という形が非常に分かりやすい。

ECCでも同じことをしたくてECIESを見つけた。

APIもある。

ところが、実際に使ってみるとその先がない。

ところで、さっき出てきたECDHって何だ？

BouncyCastleのソースを追っている途中で、こんなクラスが出てきました。

ECDHBasicAgreement

ECDH。

Elliptic Curve Diffie-Hellman。

最初に探していたのは、

楕円曲線の公開鍵で本文を暗号化する方法

でした。

ところがECDHを調べ始めると、少し発想の違う仕組みが出てきます。

サーバーが秘密鍵を作る。

クライアントも秘密鍵を作る。

それぞれが公開鍵を生成する。

そして、公開鍵だけを相手に渡す。

秘密鍵そのものは、一度もネットワーク上を流しません。

それなのに、

サーバーとクライアントの双方に、まったく同じ秘密の値を作ることができます。

最初に知ったとき、これはなかなか不思議でした。

そして、

同じ秘密が双方に作れるなら、それをAESなどの共通鍵暗号に使えばいいのでは？

というところにつながります。

楕円曲線
   ↓
ECDH
   ↓
共有秘密
   ↓
暗号鍵を生成
   ↓
共通鍵暗号で通信

「公開鍵で本文そのものを暗号化する」ことにこだわらなくても、安全な通信を作る方法があるわけです。

次回

C#で楕円曲線暗号を使いたい② ― ECDHで共有秘密を作ってみる

次回は、サーバーとクライアントでそれぞれ鍵ペアを作ります。

交換するのは公開鍵だけです。

そして、

秘密鍵を一度も相手に送っていないのに、本当に双方で同じ共有秘密ができるのか。

C#で実際に確認してみます。

その先では、さらに見慣れたものにつながっていきます。

WireGuardの設定ファイル、

INI

[Interface]
PrivateKey = ...

[Peer]
PublicKey = ...

[Interface]
PrivateKey = ...

[Peer]
PublicKey = ...

「待てよ。これ、wg0.conf でいつも書いているアレじゃないか？」

となるわけですが、それは③で。