7

私はRSA暗号をゼロから実装する方法を理解しようとしています(知的演習のためだけに)、私はこの点で立ち往生しています:

暗号化の場合、c = m e mod n

現在、e は通常 65537 です。m と n は 1024 ビットの整数です (たとえば、128 バイトの配列)。これは明らかに標準的な方法には大きすぎます。これをどのように実装しますか？

ここで累乗について少し読んでいますが、クリックしていません：

ウィキペディア - 二乗による累乗

この章(セクション 14.85 を参照)

ありがとう。

編集：これも見つかりました-これは私が見るべきものですか？ウィキペディア-剰余累乗

4

4 に答える 4

8

二乗によるべき乗：

例を見てみましょう。17 23を見つけたいとします。23 は101112 進数であることに注意してください。左から右に組み立ててみましょう。

           // a      exponent in binary

a = 17     //17^1          1

a = a * a  //17^2         10

a = a * a  //17^4        100
a = a * 17 //17^5        101

a = a * a  //17^10      1010
a = a * 17 //17^11      1011

a = a * a  //17^22     10110
a = a * 17 //17^23     10111

2 乗すると、指数が 2 倍になります (1 ビット左にシフトします)。m を掛けると、指数に 1 が加算されます。

modulo を減らしたい場合はn、各乗算の後に行うことができます (数値が非常に大きくなる最後まで残すのではなく)。

65537 は10000000000000001バイナリ形式なので、これらすべてが非常に簡単になります。それは基本的に

a = m
repeat 16 times:
    a = a * a
    a = a mod n
a = a * m
a = a mod n

もちろん、a、n、m は「大きな整数」です。a は (n-1) 2まで大きくなる可能性があるため、少なくとも 2048 ビットである必要があります。

于 2010-07-07T00:52:34.370 に答える
3 
結果=1
e> 0の場合：
  if（e＆1）！= 0：
    結果=結果*m
    結果=結果modn
  m = m * m
  m = m mod n
  e = e >> 1
結果を返す

これにより、最下位ビットから始まる指数のビットがチェックされます。少し上に移動するたびに、mの累乗が2倍になることに対応します。したがって、eと2乗mをシフトします。結果は、指数がその位置に1ビットを持っている場合にのみ、mの累乗を掛けたものになります。すべての乗算はmodnで減らす必要があります。

例として、m^13を考えてみましょう。11=1101のバイナリ。したがって、これはm ^ 8 * m ^ 4*mと同じです。ビット1101と同じ8、4、（2ではない）、1の累乗に注意してください。次に、m ^ 8 =（m ^ 4）^2およびm^ 4 =（m ^ 2）^2であることを思い出してください。

于 2010-07-07T01:43:01.343 に答える
3

mod効率的なアルゴリズムを得るには、二乗によるべき乗と、各ステップの後に を繰り返し適用することを組み合わせる必要があります。

奇数eの場合、次のことが成り立ちます。

m e mod n = m ⋅ m e-1 mod n

eの場合:

m e mod n = (m e/2 mod n) 2 mod n

基本ケースとしてm 1 = mを使用すると、これは効率的な剰余累乗を行うための再帰的な方法を定義します。

しかし、このようなアルゴリズムでも、mとnは非常に大きくなるため、そのようなサイズの整数を処理できる型/ライブラリを使用する必要があります。

于 2010-07-07T00:47:49.837 に答える
1

2 で割り切れない Ng(x) = x mod 2^kよりも bignum ライブラリの計算の方が速い場合は、モンゴメリー乗算の使用を検討してください。剰余累乗で使用すると、各ステップでモジュロ N を計算する必要がなくなります。最初と最後に「モンゴメリ化」/「非モンゴメリ化」を実行するだけで済みます。f(x) = x mod N

于 2010-07-07T22:53:32.547 に答える