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 を足せば、
と求められます。
つまり、回数 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
IEScipher.Init(true, pwr);最初は、
鍵の作り方がおかしいのか？
と思いました。
あるいは、
"ECIES"という指定方法が違うのか？
とも考えました。
しかし、少し妙です。
もしBouncyCastleがECIESという暗号方式そのものを知らないのであれば、
CipherUtilities.GetCipher("ECIES")の時点でエラーになってもおかしくありません。
ところが、ここは通ります。
GetCipher("ECIES") は、ちゃんとCipherオブジェクトを返してきます。
その次の、
cipher.Init(...)で、
NotImplementedExceptionになる。
ECIESという名前は認識している。
なのに、
実行しようとすると「未実装」と言われる。
どういうことでしょう。
こうなると、ライブラリの外側だけ眺めていてもよく分かりません。
BouncyCastleのソースコードを追ってみることにしました。
CipherUtilities.GetCipher("ECIES") の中を追う
入口はここです。
CipherUtilities.GetCipher("ECIES");CipherUtilities のコードを見ると、指定されたアルゴリズム名から実際に使用するCipherを生成しています。
概略はこんな流れです。
発生箇所はここです。
GetCipher("ECIES")
↓
GetMechanism("ECIES")
↓
GetCipherForMechanism("ECIES")そして GetCipherForMechanism() の中を見ると、ECIESの場合には、
basicAgreement = new ECDHBasicAgreement();
が生成されています。
さらに、
C#
return new BufferedIesCipher(
new IesEngine(
basicAgreement,
new Kdf2BytesGenerator(new Sha1Digest()),
new HMac(new Sha1Digest())
)
);という形で、
ECDHBasicAgreement
↓
IesEngine
↓
BufferedIesCipherが組み立てられています。
ここで、ひとつ気になる名前が出てきました。
ECDHBasicAgreementECDH。
この名前は覚えておいてください。
次回の記事で主役になります。
今回はまず、このまま 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");本当に未実装だった
C#
using System.Security.Cryptography;
using Org.BouncyCastle.Crypto;
using Org.BouncyCastle.Crypto.Generators;
using Org.BouncyCastle.Crypto.Parameters;
using Org.BouncyCastle.Security;
using Org.BouncyCastle.Crypto.Agreement;
namespace ECC
{
class Program
{
static void Main(string[] args)
{
// 鍵ペアの生成
AsymmetricCipherKeyPair keyPair = ECCUtilities.GenerateKeyPair();
AsymmetricKeyParameter publicKey = keyPair.Public;
AsymmetricKeyParameter privateKey = keyPair.Private;
// 暗号化と復号化のテスト
string originalText = "Hello, world!";
encrypted = ECCUtilities.Encrypt(originalText, publicKey);
decrypted = ECCUtilities.Decrypt(encrypted, privateKey);
Console.WriteLine("Original: " + originalText);
Console.WriteLine("Decrypted: " + decrypted);
}
}
public static class ECCUtilities
{
private static ECDomainParameters GetDomainParameters()
{
// 楕円曲線パラメータの定義（ここではsecp256k1を使用）
BigInteger p = new BigInteger("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 16);
BigInteger a = BigInteger.Zero;
BigInteger b = BigInteger.ValueOf(7);
FpCurve curve = new FpCurve(p, a, b);
Org.BouncyCastle.Math.EC.ECPoint g = curve.DecodePoint(Hex.Decode("04"
+ "79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798"
+ "483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8"));
ECDomainParameters domainParams = new ECDomainParameters(curve, g, p);
return domainParams;
}
public static AsymmetricCipherKeyPair GenerateKeyPair()
{
// 鍵ペアの生成
ECKeyPairGenerator keyGen = new ECKeyPairGenerator();
ECDomainParameters domainParams = GetDomainParameters();
SecureRandom random = new SecureRandom();
ECKeyGenerationParameters eckeygenparam = new ECKeyGenerationParameters(domainParams, random);
keyGen.Init(eckeygenparam);
AsymmetricCipherKeyPair keyPair = keyGen.GenerateKeyPair();
return keyPair;
}
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);
byte[] encryptedBytes = cipher.DoFinal(inputBytes);
return encryptedBytes;
}
public static string Decrypt(byte[] encryptedBytes, AsymmetricKeyParameter privateKey)
{
// 復号化
IBufferedCipher cipher = CipherUtilities.GetCipher("ECIES");
cipher.Init(false, privateKey);
byte[] decryptedBytes = cipher.DoFinal(encryptedBytes);
string plaintext = Encoding.UTF8.GetString(decryptedBytes);
return plaintext;
}
}
}
61行目、関数GetCipherで暗号アルゴリズムを取得します。続いてOrg.BouncyCastle.Securityのコードを追っていきます。関数GetMechanismは引数”ECIES”に対し”ECIES”をそのまま返します。最終的にクラスBufferedIesCipherのインスタンスがIBufferedCipher cipherに返されます。
61行目、関数GetCipherで暗号アルゴリズムを取得します。続いてOrg.BouncyCastle.Securityのコードを追っていきます。関数GetMechanismは引数”ECIES”に対し”ECIES”をそのまま返します。最終的にクラスBufferedIesCipherのインスタンスがIBufferedCipher cipherに返されます。
C#
namespace Org.BouncyCastle.Security;
public static class CipherUtilities
{
中略
public static IBufferedCipher GetCipher(string algorithm)
{
if (algorithm == null)
{
throw new ArgumentNullException("algorithm");
}
IBufferedCipher cipherForMechanism = GetCipherForMechanism(GetMechanism(algorithm) ?? algorithm.ToUpperInvariant());
if (cipherForMechanism != null)
{
return cipherForMechanism;
}
以下略
}
private static IBufferedCipher GetCipherForMechanism(string mechanism)
{
IBasicAgreement basicAgreement = null;
if (mechanism == "IES")
{
basicAgreement = new DHBasicAgreement();
}
else if (mechanism == "ECIES")
{
basicAgreement = new ECDHBasicAgreement();
}
if (basicAgreement != null)
{
return new BufferedIesCipher(new IesEngine(basicAgreement, new Kdf2BytesGenerator(new Sha1Digest()), new HMac(new Sha1Digest())));
}
以下略
}
}
63行目の関数cipher.Initで初期化を行いますが、cipherはクラスBufferedIesCipherのインスタンスであるため、throw new NotImplementedException(“IES”); で例外をスローするようにコーディングされています。つまり、暗号アルゴリズムにECIESを選択して初期化すると、仕様として、NotImplementedException: （メソッドまたは操作は実装されていません）のエラーとなります。
言い換えると、暗号化アルゴリズムに楕円曲線暗号を選択して、公開鍵で文字列の暗号化を行おうとすると、仕様としてエラーになるということです。
C#
namespace Org.BouncyCastle.Crypto;
public class BufferedIesCipher : BufferedCipherBase
{
中略
public override void Init(bool forEncryption, ICipherParameters parameters)
{
this.forEncryption = forEncryption;
throw new NotImplementedException("IES");
}
以下略
}エラーメッセージ
System.NotImplementedException: IES
at Org.BouncyCastle.Crypto.BufferedIesCipher.Init(Boolean forEncryption, ICipherParameters parameters)