9

典型的な RSA 実装には、多精度整数ライブラリが組み込まれています。典型的な多倍精度整数ライブラリは、動的割り当てを使用して、大きな整数を適切なサイズの機械語の配列として表します。

RSA-2048 などで既知の長さのメッセージ (通常は対称暗号化キー) を暗号化または復号化するためにのみ多精度整数を使用する場合に遭遇する可能性のある数学的整数には限界があるはずであり、それは静的またはスタック上で必要なすべての中間結果にスペースを割り当てることで、アルゴリズムを実装できます。

これが可能であることを示唆するこのフォーラムスレッドを見つけました。最大整数サイズを示すものではありません。おそらくそれは明らかです (「すべての整数に 2048 ビットが必要ですよね!」)。いずれにせよ、既存の実装があれば、もっと興味があります。

独自のエントリに値しない副次的な質問として、楕円曲線暗号の一般的な実装には動的割り当てが必要ですか?

4

2 に答える 2

3

動的割り当てなしで多精度整数クラスを実装することは可能ですか?

はい。

C# BigInteger Classでの同様の実装を認識しています。（そして、基礎となるclrランタイムが何をするかにかかわらず）。

C/C++ の静的サイズのバッファーについては知りません。しかし、私は Botan、Crypto++、OpenSSL しか知りません。

私が実装について見てきたことから、公開指数は時々それをoreにする最適化を取得します。しかし、 とは多精度です。（そして、いつかそれがどのように爆発するかを見たいです）。intlongnd

最後に、ルーターやその他の低電力機器では、送受信バッファーでこの最適化が行われることがよくあります (私は以前、電気技師でルーターを設計していた人物と一緒に仕事をしていました)。それらはメモリのチャンクを予約するだけで、ソフトウェアはインデックスを使用して静的バッファにアクセスします。したがって、彼らがあなたが話している最適化を採用したと信じるのは難しくありません.

RSA-2048、および必要なすべての中間結果に静的またはスタック上のスペースを割り当てることにより、アルゴリズムを実装することが可能である.

はい、最大 RSA モジュラス サイズまたは EC 素体サイズを制限することを受け入れた場合、固定サイズのバッファーを使用する符号マグニチュード スキームでそれを行うことができます。

RSA 公開鍵は (e,n) です。small の警告にもかかわらず、e2048/8 = 256 バイまたはオクテットの 2 つのバッファが必要になります。

事前計算のトリックを使用しない RSA 秘密鍵は、単純に (e,d,n) です。したがって、256 バイトまたはオクテットの 3 つのバッファーが必要になります。

12 ビット バイトの PDP-8 で作業している場合は、必要なバイト数が少なくなります。

最大整数サイズを示すものではありません。

詳細の悪魔はおそらく乗算です。そのため、乗算を実行するにはスクラッチ バッファーが必要になります。つまり、~2*2048 ビット サイズのバッファーが必要になります (2 つmのサイズのバッファーを乗算すると、 size の結果が作成されます2m -1 )。次に、乗算の結果を減らす必要があります。それらはさらなる最適化かもしれませんが、私は通常、それらの詳細について気にしません。

関連して、メッセージの最大サイズと暗号文の最大サイズは に関連していnます。MaxPreImageSizeCrpyto++ では、 (平文の場合) とMaxImageSize(暗号文の場合)で取得できます。MaxPreImageSizeとMaxImageSize戻りn - 1ます。

独自のエントリに値しない副次的な質問として、楕円曲線暗号の一般的な実装には動的割り当てが必要ですか?

基礎となる実装に依存します。素体上の曲線はドメイン パラメータによって定義されます (Certicom のSEC1、Elliptic Curve Domain Parameters、セクション 3、16 ページから):

Elliptic curve domain parameters over F_p are a sextuple:

   T = (p, a, b, G, n, h)

  • pは大きな素数であり、多倍長整数が必要です

  • aとbは曲線を定義する係数です。通常は「小さい」(たとえば、a= 3) ですが、非標準曲線では多精度整数が必要になる場合があります。たとえば、DJB の ed25519 曲線はy^2 = x^3 - 102314837768112 x + 398341948620716521344です。

  • Gは基点なので、実際には曲線上の要素 (または点) です。つまり、(X, Y) 座標であり、おそらく多精度整数が必要です。

  • nは順序素数であり、Gその neallyは次の値と同じであることを意味しますn

  • hは補因子であり、通常は非常に小さく、4 または 2 または 1 です。

曲線のキー ペアを作成するときは、ランダムなプライベート指数d(またはx) が必要であり、累乗の後に要素 (曲線上の点) を作成します。つまり、公開鍵 (X, Y) = G^x. したがって、さらに 3 つの多倍精度整数があります。

バイナリ フィールド上の曲線には、多項式を表現する方法が必要です。pしたがって、おそらく多倍長整数 (素体で使用される) が必要になるでしょう。

したがって、楕円曲線上の「もの」のほとんどは、多倍長整数を必要とします。

ドメイン パラメーターの例は、楕円曲線暗号 (ECC) Brainpool Standard Curves および Curve Generation などで確認できます。

于 2013-10-05T23:06:46.540 に答える