制限された指数のためにC＃で非対称キーを作成するにはどうすればいいですか？

Question

私は、非対称キーを使用してデータを暗号化および復号化するための小さなソフトウェアを作成しています。

問題は、私はC＃でも、私が使用している場合コーディングしています、次のとおりです。

BigInteger.Pow(BigIntenger myNumber, int myExponent); 

指数は「int型」であると、私の値がintのために大きなにあります。

すぐに説明して間違いがないことを確認するには、大きな数字を使用して秘密キーを持たずに解読を難しくする必要があります。

だから私は

• N = P * Q
• PとQは両方の素数ています。
• M =（P-1）+（Q-1）
• Cは次いで、Uを見つけるM
• と素数である：C×U + M×V = 1

公開鍵（N、C）。

秘密鍵（U、N）。

たとえば、「Bonjour！」を暗号化します。 UTF8にあなたが持っているだろう

：

B⇔66/o⇔111/n⇔110/j⇔106/o⇔111/u⇔117/r⇔114/（エスパス）⇔32/⇔33

！

そしてCの電源にそれぞれ数字を上げ、モジュロN.

例：valueOfB =（66^C）％のN。

ここであなたのメッセージは暗号化されています。

あなたはそれを復号化する場合は、指数Uによってそれぞれの値を乗算しなければならないとモジュロN.

例：（valueOfB^U）％N

だから私はこれを行うことができます私が小さな "U"値を "int"に適合させるために小さい番号を使う場合に限りますが、安全ではありません。BigIntegerのようなint型ではどうしたらいいですか？ BigIntegerの

Answer 1

BigInteger.Powは非常に複雑な数字になります。

バイナリ乗算は、nビットの数字にmビットの数値を乗じる（大まかに言えば）約(n+m)ビットの応答を生成するという性質があります。

10 * 4096 = 0b1010 * 0b1_0000_0000_0000 (4 bits, 13 bits) 
40960 = 0b1010_0000_0000_0000 (16 bits) 

16 * 4096 = 0b1_0000 * 0b1_0000_0000_0000 (5 bits, 13 bits) 
65536 = 0b1_0000_0000_0000_0000 (17 bits) 

15 * 4095 = 0b1111 * 0b1111_1111_1111 (4 bits, 12 bits) 
61425 = 0b1110_1111_1111_0001 (16 bits) 

べき乗を繰り返し乗算され、乗算は加算を繰り返しているので、我々は、512ビットの数の電力に1024ビットの数を上げることは1024×512ビットの領域で回答を生成することがわかります（524288ビット、65536バイト）。

しかし、あなたはモジュラス演算でそれをフォローし、1024ビットの数の領域に戻します。それはかなり無駄です。

ありがたいことに、アルゴリズムを効率的に行うために存在します。modular exponentiationありがたいことに二重に、.NETは先に進み、あなたのためにそれを書いた。

あなたが探していることはあなたがここで見たいと思うかもしれません

valueOfB = BigInteger.ModPow(66, U, N);