2

「RSA暗号化または復号化の時間は、指数のビット数にほぼ比例します」.

ビットの位置をより重視していると思います。たとえば、M^e です。e1 = 10001 = 17 e2 = 00111 = 7

M=5だと5^7よりも5^17の方が計算に時間がかかると思います。

私は正しいですか？

4

1 に答える 1

3

最も単純な累乗剰余アルゴリズムは、「2 乗と乗算」です。

tビットの指数を想定します。指数値は2 t-1 (包括的) から2 t (排他的) の間です。言い換えると、インデックスt-1 (0 からカウントする場合) でゼロ以外の最上位ビットがあり、すべての上位 (別名「先行」) ビットは 0 です。たとえば、17 は 5 ビットの指数です (次のように記述されます)。 '10001') であり、7 は 3 ビットの指数 ('111') です。

次に、eによるmのべき乗は次のように機能します (必要なのはm e mod nです)。

  1. r = mで始まる
  2. t-2から0までの範囲のkの場合:
    • 二乗r : セットr = r 2 mod n
    • eのインデックスkのビットが 1 の場合、r = r*m mod nを設定します。
  3. 累乗結果はr

したがって、累乗にはt-1の二乗と、mによるs-1 の余分な乗算が必要になります。ここで、sはeのバイナリ表現におけるゼロ以外のビットの数です。剰余二乗のコストは、剰余乗算とほぼ同じです。

ウィンドウベースの最適化を使用すると、余分な乗算の数を減らすことができます。アイデアは、グループごとに指数ビットを処理することです。たとえば、指数に 2 つの連続するゼロ以外のビットがある場合、上記のアルゴリズムはこれらのビットに対して次の処理を行います: rを 2 乗し、 rをmで乗算し、 rを 2 乗し、 rをmで乗算します。このシーケンスは次のように置き換えることができます: rの 2 乗、 rの 2 乗、 rにm 3を掛ける。したがって、m 3を事前計算すると(これには 2 つの乗算が必要です)、指数にゼロ以外のビットが 2 つ連続するたびに、1 つの乗算を保存できます。これにより、余分な乗算がt/2を超えないことが保証されます。このプロセスは、3 ビット以上のグループに拡張できます。サイズwのウィンドウを使用する場合、約2 w-1乗算の事前計算を行う必要がありますが、その後の余分な乗算は多くてもt/wだけです。

要するに、大きな指数 (数百ビット以上) の場合、計算コストの 80% 以上がt-1 の2 乗に由来します。つまり、「指数のビット数にほぼ比例します」。余分な乗算 (実際の指数ビット値によって異なります) の合計は、総コストの 20% 未満になります。

さて、上記のすべては「大きな指数」を前提としています。累乗剰余を実装する効率的な方法には、モンゴメリ リダクションの使用が含まれます。これは、計算の最初と最後に実行される変換ステップを意味します。指数が大きい場合、これらのコンバージョンの相対的なコストは無視できます。ただし、指数が短い場合 (7 や 17 など)、これは当てはまらず、実際には変換ステップのコストが支配的になります。

また、RSA秘密鍵操作 (秘密指数を使用するもの) では、中国剰余定理を使用するのが通例です。CRTはモジュラスの特別な構造を使用します (つまり、 pとqの場合、n = pqべき乗法を 2 倍の小さい値の 2 つのべき乗法に置き換えます)。CRT ベースの実装では、いくつかの追加の手順が必要になりますが、4 倍のスピードアップが可能です。また、(操作を高速化するために) 秘密指数がモジュラスよりも大幅に短くなるように RSA キーを設計することは、セキュリティ リスクであると付け加える必要があります。指数がモジュラスの長さの 29% よりも小さい場合、キーはクラックされる可能性があります。 . したがって、指数化の速度と指数の長さに関する上記のすべてのテキストは、公開指数のみに実際に適用されます。公開指数は小さく選択できます。その時点で、ウィンドウベースの最適化に関する議論は適用されません。

より完全な処理については、Handbook of Applied Cryptography (無料でダウンロードできます)の第 14 章をお読みください。

于 2011-03-21T13:05:39.187 に答える