N ビット RSA モジュロ数値の解読

Question

これは私に関係があります 前の投稿, 、私の唯一の選択肢は、比較的弱いと思われる RSA アルゴリズムを使用することでした。35 ビット数値 (0 から 34359738367 まで) を 36 ビット モジュロ (34359738368 から 68719476735 まで) でエンコードしたいと仮定します。

を参照してください http://en.wikipedia.org/wiki/RSA 私の n は 34359738368 から 68719476735 までのランダムな合計 (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が何だったか教えてくれませんか？(N 34359738368 から 68719476735 まで)

私は単にそれがどれくらい解読可能であるかを知りたいので、どのくらいの時間、どのくらいの速さ、どれくらいの出力を見なければならないか、どのようなアルゴリズムを使用できるかなどについて何か情報があれば教えてください。素晴らしいことになるでしょう。

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

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

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

「Jacobi」アルゴリズムを使用すると数秒でこれを解読できるため、Accipitridae によって投稿された回答を受け入れます。n、e、p が分からない場合。

Answer 1

攻撃者は、n の係数 p および e mod (p-1) を推測できます。各推測は、メッセージ m を取得し、m^e mod p を計算し、c mod p と比較することでチェックできます。ここで、c は対応する暗号文です。p と e mod (p-1) はおそらくそれぞれ 20 ビットであるため、これは、スキームのセキュリティが 40 ビット以下であることを意味します。

ただし、40 ビットは非常に大まかな上限にすぎません。攻撃者はさらに優れた攻撃を行うことができます。たとえば、係数 p を推測できます。次に、メッセージと暗号文のヤコビ記号を計算します。メッセージ m が二次剰余 mod p である場合、暗号文は二次剰余 mod p である必要があり、その逆も同様です。したがって、メッセージと暗号文のペアについてこの関係が満たされない場合、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

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

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

Answer 2

RSA は、Chosen-Ciphertext 攻撃に対して脆弱です。つまり、暗号文 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^d mod nξx0*x

x1*x0^-1 = x

x は y の復号化です。

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

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

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

Answer 3

これは、36ビットのRSA恐ろしい考えであります？なぜ単にブロックまたはストリーム暗号に行きませんか？そのようにあなたは1得る：1マッピングと多くのより強固な方法での

Iであろうお勧め別の解決策は、UIDとしてSHAハッシュを使用して別の列としてデータベースにユーザごとに連続番号を格納する。