1

これは、比較的弱いと思われる RSA アルゴリズムを使用するしかなかった私の以前の投稿に関連しています。35 ビットの数値 (0 から 34359738367 まで) を 36 ビットのモジュロ (34359738368 から 68719476735 までの間) でエンコードしたいとします。

http://en.wikipedia.org/wiki/RSAを参照すると、私の n は 34359738368 から 68719476735 までのランダムな totient (p-1 * q-1 の形式) であることがわかります。ランダムな d と e を選びます。数値をエンコードして UI に表示します。

議論の目的のために、ユーザーが最大 1,000 のそのような出力を見ることができると仮定しましょう。彼は、Polla のアルゴリズムなどを使用して、私の d、e、または n をクラックし、それによって新しい数の予測を開始できますか? もしそうなら、それはどれほど難しいでしょうか？（1000セットの入力/出力を知っているだけで）

例として (入力/出力形式のサンプルとして 6 つの出力を考えてください)、

  1. 10001621865,31116156015
  2. 10001621866,33031668326
  3. 10001621867,37351399313
  4. 10001621868,06071714212
  5. 10001621869,01188523761
  6. 10001621870,18341011998

誰かが私のn、d、eが何であるか教えてもらえますか? (34359738368 ～ 68719476735 の間の N)

私は単にそれがどれだけクラック可能かを知りたいので、どのくらいの時間、どれくらいの速さで、どれだけの出力を表示する必要があるか、どのアルゴリズムを使用できるかなどについての情報を教えていただければ幸いです。

PS: ユーザーには、標準の RSA アルゴリズムのように「e」は表示されません。彼は入出力セットしか見ることができません。

詳細が追加 されました db からユーザーに連続したユーザー ID を提示しようとしています。シーケンシャルであるため、ユーザーがいくつかの登録を行って別のユーザーの ID を推測することは望ましくありません。これを避けるには、<= 12 桁の数字にスクランブルする必要があります。これには、この質問で説明されている多くの制約がありました。

また、n、d、および e の値はユーザーにはわかりません。ユーザーが見ることができる最大値は、いくつかの入力出力サンプルです (繰り返し登録することにより)

「Jacobi」アルゴリズムを使用して数秒でこれをクラックできるため、Accipitridae によって投稿された回答を受け入れます。n、e、またはpを知らなくても。

4

3 に答える 3

4

RSAは、選択暗号文攻撃に対して脆弱です。つまり、暗号文yを解読したい場合、暗号文と平文のペアの1つを使用してそれを破ることができます。

それを壊す方法：

x0とy0を選択します。ここで、x0とy0は、提供されている平文と暗号文のペアです。

y1 = y0 * y mod n y1は、この基準を満たす、ユーザーに与えられる1000個の暗号文のもう1つです。x1はy1の復号化であり、これも指定されています。これは次のことを意味します。

x1 = y1 ^ d mod n（これは私たちに与えられました、私たちはすでにx1を知っています）

x1 =（y0 * y）^ d mod n x1 = y0 ^ d * y^dmodnΞx0*x

x1 * x0 ^ -1 = x

xはyの復号化です。

もちろん、これはy0 * y mod nがすでに持っている別の暗号文を生成するかどうかに依存します。また、このようなペアは1000しかないため、壊れることはほとんどありませんが、実行不可能ではありません。ペアを非常に慎重に選択する必要があります。

また、使用しているnのサイズにより、因数分解ヒューリスティックがnの素因数分解をかなり迅速に見つけることができることを付け加えたいと思います。また、RSAはタイミング攻撃に対して脆弱ですが、それは簡単に阻止できます。

追加情報付き： n、d、またはeを知らなければ、情報はまったく提供されません。つまり、n、d、またはeの組み合わせを推測することは、平文自体を推測することと同じくらい優れています。nとeを見つけるには、推測するnの組み合わせが少なくとも43,359,738,367あり、eの組み合わせもすべてあります。1000の暗号文と平文のペアを持っていても、nとeを解読するのは簡単ではありません。

于 2009-05-18T15:01:13.610 に答える
1

攻撃者は、n と e mod (p-1) の因数 p を推測できます。各推測は、メッセージ m を取得し、m^e mod p を計算してから c mod p と比較することで確認できます。ここで、c は対応する暗号文です。p と e mod (p-1) はおそらくそれぞれ 20 ビットなので、これはスキームのセキュリティが 40 ビットを超えないことを意味します。

しかし、40 ビットは非常に大雑把な上限にすぎません。攻撃者は、はるかにうまくやることができます。たとえば、因子 p を推測できます。次に、メッセージと暗号文のヤコビ記号を計算します。メッセージ m が p を法とする 2 次剰余である場合、暗号文は p を法とする 2 次剰余でなければならず、逆もまた同様です。したがって、メッセージ/暗号文のペアでこの関係が満たされない場合、p の推測を拒否できます。または、攻撃者はメッセージと暗号文の間の離散対数を計算できます。これにより、e mod (p-1) のはるかに高速な候補が得られます。

これにより、20 ～ 30 ビットのセキュリティ レベルが得られるため、解除するのに数秒かかります。サンプルの数を 20 に拡張する場合は、いくつかのベンチマークを試すことができます。

更新:実験を実行するための 20 個のサンプルが提供されなかったので、自分で生成する必要がありました。以下のサンプルで

m = 10001621865  c = 31116156015
m = 10001621866  c = 33031668326
m = 10001621867  c = 37351399313
m = 10001621868  c = 6071714212
m = 10001621869  c = 1188523761
m = 10001621870  c = 18341011998
m = 10001621871  c = 7620400191
m = 10001621872  c = 36106912203
m = 10001621873  c = 37615263725
m = 10001621874  c = 7795237418
m = 10001621875  c = 34774459868
m = 10001621876  c = 4555747045
m = 10001621877  c = 33123599635
m = 10001621878  c = 34836418207
m = 10001621879  c = 33962453633
m = 10001621880  c = 6258371439
m = 10001621881  c = 7500991556
m = 10001621882  c = 5071836635
m = 10001621883  c = 911495880
m = 10001621884  c = 39558568485

入力として、上記のアルゴリズムは係数 201821 と 206153 を 20ms で見つけます。説明したように、これは e を知る必要はありませんが、e=65537 の選択は推測しやすく、悪用される可能性もあります。

RSA の強みは、大きな整数の素因数分解の難しさに基づいていることです。ここでは、この困難を取り除くと、RSA のすべての弱点 (つまり、数学的関係) が残ります。RSA に基づいてブロック暗号を構築するのは恐ろしい考えです。前に提案したように、Luby-Rackoff 構造を使用したくない理由が本当にわかりません。

于 2009-05-18T18:43:34.923 に答える
0

これは恐ろしい考えです、36 ビット RSA?? 単純にブロックまたはストリーム暗号を使用しないのはなぜですか? そうすれば、1 対 1 のマッピングをより安全な方法で取得できます。

私がお勧めする代替ソリューションは、SHA ハッシュを UID として使用し、データベース内の各ユーザーの連続番号を個別の列として格納することです。

于 2009-05-24T10:47:21.997 に答える