非常に大きな数の処理について質問があります。私は RSA アルゴリズムを実行しようとしていますが、512 ビットの数値 d と 1024 ビットの数値 n があるとしましょう。復号化された単語 = 暗号化された単語^d mod nですね。しかし、これらの d と n は非常に大きな数です。標準の変数型以外は、512 ビットの数値を処理できません。どこでも、rsa は最後に 512 ビットの素数が必要だと書かれていますが、実際にそのような数に対して数学演算を実行するにはどうすればよいでしょうか?
そしてもう一つ考えます。追加のライブラリを使用できません。BigInteger を使用して Java で素数を生成しますが、私のシステムでは基本的な変数型しかなく、STRING256 が最大です。
最大整数サイズが 64 ビットであるとします。文字列は、ほとんどの言語で数学を行うのにそれほど有用ではないため、文字列型は無視してください。次に、そのサイズの半分の整数、つまり 32 ビットを選択します。これらの配列は、基数 2 32の数字として解釈できます。これらを使用すると、基数 10 とペンと紙で慣れているのと同じように、長い足し算と掛け算を行うことができます。各基本ステップでは、2 つの 32 ビット量を組み合わせて、32 ビットの結果と、場合によってはキャリーの両方を生成します。64 ビット算術で初等演算を行う場合、これらの両方が 1 つの 64 ビット変数の一部として含まれ、それを 32 ビットの結果桁に分割する必要があります (ビット マスクまたは単純な切り捨てキャスト) と残りのキャリー (ビット シフトによる)。
分割は難しいです。ただし、除数がわかっている場合は、定数による除算を行うことで回避できます代わりに乗算を使用します。例を考えてみましょう: 7 による除算。7 の逆数は 1/7=0.142857… です。したがって、それを掛けて同じ結果を得ることができます。明らかに、ここでは浮動小数点演算を行いたくありません。ただし、単純に 14286 を掛けて、結果の下 6 桁を省略することもできます。配当が十分に小さい場合、これはまさに正しい結果になります。どのくらい小さい？x/7 を x*14286/100000 として計算すると、エラーは x*(14286/100000 - 1/7)=x/350000 になるため、x<350000 である限り安全です。RSA セットアップのモジュラスがわかっている限り、つまりキー ペアが同じままである限り、このアプローチを使用して整数除算を行うことができ、それを使用して剰余を計算することもできます。基数 2 32を使用することを忘れないでくださいただし、基数 10 の代わりに、逆定数に必要な桁数を確認してください。
おそらくnが変数であっても、モジュロリダクションをより簡単に行うために、検討したい代替手段があります。剰余を 0 から n-1 までの数字で表す代わりに、2 1024 -n から 2 1024 -1 を使用することもできます。したがって、最初の数値が 2 1024 -nより小さい場合は、n を追加してこの新しいエンコーディングに変換します。これの利点は、除算をまったく実行せずに削減ステップを実行できることです。2 1024は、この設定では 2 1024 -n に相当するため、初等モジュロ削減は、ある数を下位 1024 ビットと上位残りに分割することから始まります。より高い残りは1024ビットだけ右にシフトされ（これは配列のインデックス付けの変更にすぎません）、次に2倍されます1024 -n そして最後に下部に追加。結果が 1024 ビット以下であることを確認できるまで、これを行う必要があります。その頻度はnに依存するため、固定nの場合はそれを事前計算できます（大きなnの場合、加算後は2つの削減ステップですが、乗算後は3つのステップになると予想されますが、再確認してください）変数nの場合実行時に確認する必要があります。最後に、通常の表現に戻ることができます。結果が n より小さくない場合は、n を引きます。n>2 512の場合、これはすべて説明どおりに機能するはずです。そうでない場合、つまりモジュラスの最上位ビットがゼロの場合は、さらに調整する必要があります。これまでのところ、2 の累乗に近い固定モジュラスに対してのみこのアプローチを使用したため、これについては考えていませんでした。
さて、その累乗です。そのためにバイナリアプローチを行うことを強くお勧めします。x dを計算するときは、x、x 2 =x*x、x 4 =x 2 *x 2、x 8 =… から始めます。つまり、すべての 2 の累乗指数を計算します。また、1 つに初期化する中間結果も保持します。すべてのステップで、対応するビットが指数 d に設定されている場合、対応する累乗をその中間結果に乗算します。d=11 だとしましょう。次に、d=11=1+2+8=1011 2であるため、1*x 1 *x 2 *x 8を計算します。. そうすれば、指数が 512 ビットの場合、最大で約 1024 回の乗算しか必要ありません。半分は 2 のべき乗、もう 1 つは 2 のべき乗を組み合わせます。メモリ要件を低く抑えるために、これらすべてのすべての乗算の直後にモジュロ リダクションを実行する必要があります。
上記の累乗プロセスの速度は、この単純な形式では、実際に設定されている d のビット数に依存することに注意してください。したがって、これによりサイド チャネル攻撃が開始され、攻撃者が d に関する情報にアクセスできるようになる可能性があります。しかし、サイド チャネル攻撃が心配な場合は、専門家に実装を開発してもらう必要があります。