関数F(k,x)が 2 つの 64 ビット値を取り、それらの 10 進数の積を返す操作を実行しています。例えば：
F(123,231) = 123 x 231 = 28413
次に、数値が 2 進数に変換され、最下位ビットが抽出されます。つまり、10 進数の を28413 = 0110111011111101とります。11111101253
この機能はセキュリティ上の Feistel ネットワークの一部です。あるタイプの攻撃 (選択された平文) を実行する253と231、 と があるポイントに到達しますが、 を把握する必要があり123ます。
可能な方法はありますか？
あなたの機能はやっていF(k,x) = k*x mod 256ます。
あなたの質問が与えられF(k,x)、xあなたは見つけることができますkか？
が奇数の場合x、解は 2^56 通りあり、そのすべてが になりますk = x^-1 * F(k,x) mod 256。つまり、 の逆数を計算し、とその値x mod 256の積に 256 の倍数を加算することによって、可能な解がそれぞれ導出されF(k,x)ます。
が偶数の場合x、逆数を計算することはできませんが、同様のトリックを使用して解を決定することはできます。最初に を割る 2 の数 (2 の数) を計算する必要がありますx。たとえば、 2 であるとします。次にとからt割り出し、そこから問題を解きます。すなわち。2^tx256k = (x/2^t)^-1 * F(k,x) mod (256/2^t)
一般に、暗号設計で乗算を使用することは危険です。特に、選択された平文攻撃が原因で、攻撃者は攻撃を単純化するために物事を消滅させることができるためです。私のブログで、そのような暗号を破る例を見つけることができます(混沌としたハッシュ関数とマルチプライムへの攻撃を参照してください)。
いいえ。
最上位ビットをドロップすることにより、操作は単方向になります。 123 を回復するには、結果が必要な値になるまで、あらゆる可能性で関数を力ずくで処理する必要があります。
つまり、F の結果が 253 になるまで、x の値に対して F(x,231) を実行します。
とはいえ、2 つの入力と出力のうちの 1 つを知っていれば、ブルート フォースは比較的簡単に実行できます。x の有効な値の数に依存します (たとえば、常に 3 桁の数字ですか?常に素数ですか?常に奇数ですか?)
231 の数を掛けると得られるパターンによっては、他のいくつかのショートカットがあるかもしれませんが、その数の特定の値には異なるパターンがあります。たとえば、231 ではなく 9 の場合、数字の合計は常に 9 になることがわかります。