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を試す
やりたいことは単純です。
まず楕円曲線の鍵ペアを作ります。
C#
AsymmetricCipherKeyPair keyPair =
ECCUtilities.GenerateKeyPair();
AsymmetricKeyParameter publicKey =
keyPair.Public;
AsymmetricKeyParameter privateKey =
keyPair.Private;そして、公開鍵で暗号化します。
C#
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);
}復号側では秘密鍵を渡します。
C#
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);
}呼び出し側は、
C#
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の場合には、
C#
basicAgreement = new ECDHBasicAgreement();が生成されています。
さらに、
C#
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() を見てみます。
すると、
C#
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 = ...「待てよ。これ、wg0.conf でいつも書いているアレじゃないか？」
となるわけですが、それは③で。