PRFを使用してPRGを構築することに関する質問

Dec 21 2020

Fを128ビットキーと256ビットブロック長の安全な疑似ランダム関数とします。次の関数Gは安全な疑似乱数ジェネレータです。(該当するものをすべて選択。)

A。 $G(x)=F_x(0...0)$、 どこ $x$$128$-ビット入力。

B。 $G(x)=F_x(0...0)|| F_x(0...0)$、 どこ $x$$128$-ビット入力。

C。 $G(x)=F_x(0...0)||F_x(1...1)$、 どこ $x$$128$-ビット入力。

D。 $G(x)=F_{0...0}(x)|| F_{1...1}(x)$、 どこ $x$$256$-ビット入力。

私たちの先生が答えたのは $A,D$。でもわかりません。そしてなぜCは間違っているのですか?

回答

1 SAIPeregrinus Dec 23 2020 at 03:33

宿題の質問に直接答えることはありませんが、ヒントを提供します。

攻撃者は、すべての非秘密入力を制御していると見なされます。キーは秘密ですが、ブロックは秘密ではありません。この回答には、PRGの適切な定義があります。簡単に言うと、PRGは、固定長のシークレット入力シードビットストリングを受け取り、無視できない確率でランダムビットストリングと区別できない長いビットストリングを出力する関数です。

A。 $G(x)=F_{x}(0...0)$、ここで、xは128ビットの入力キーです。

攻撃者は入力のいずれかを制御しますか?攻撃者は、無視できない確率で出力をランダム関数の出力と区別できますか(つまり、出力に観察可能なパターンがありますか)?出力は入力よりも長いですか?

唯一の入力変数は秘密鍵です。余分なパターンは出力に追加されません。出力はどのくらいですか?

B。 $G(x)=F_{x}(0...0)||F_{x}(0...0)$、ここで、xは128ビットの入力キーです。

同じ質問。

唯一の入力変数は秘密鍵です。出力は、あるシーケンスを2回繰り返します。出力はどのくらいですか?

C。 $G(x)=F_{x}(0...0)||F_{x}(1...1)$、ここで、xは128ビットの入力キーです。

同じ質問。

唯一の入力変数は秘密鍵です。出力に余分なパターンがありますか?出力はどのくらいですか?

D。 $G(x)=F_{0...0}(x)||F_{1...1}(x)$、ここで、xは256ビットの入力データブロックです。

同じ質問。

唯一の入力変数はパブリックデータブロックです。出力に余分なパターンがありますか?出力はどのくらいですか?

パターンを継続するオプションがありません:E。 $G(x)=F_{0...0}(x)||F_{0...0}(x)$、ここで、xはパブリック256ビットデータブロックです。

ADに答えることができれば、Eは取るに足らないはずです。