Регистрация Войти
Рейтинг:0
cryptonoob avatar Crypto

Определить, является ли функция PRG, когда PRG объединяется с Seed?

флаг bd
cryptonoob

Я новичок в криптографии и не могу решить следующий вопрос.

Позволять $G: \{0,1 \}^n \rightarrow \{0,1 \}^{l(n)}$ быть PRG и $х \эпсилон \{0,1 \}^n$. Определите, является ли функция $Z: \{0,1 \}^n \rightarrow \{0,1 \}^{(l(n)+n)}$ с.т. $Z(x) := G(x)||x$ также является ПРГ.

Мое первое предположение состояло в том, что это PRG, потому что объединение выходных данных PRG G(x) как псевдослучайной строки с равномерно распределенной случайной строкой x также является случайной строкой. Следовательно, он также не может быть распознан противником. Кроме того, l(n)+n > n, так что с расширением тоже все в порядке.

Как я могу это доказать? Моя идея заключается в том, что если существует различитель D, который нарушает Z(x), он также нарушает G(x) с ненулевой вероятностью, что противоречит исходному предположению, что G(x) является PRG.

Я на правильном пути или совсем заблудился?

223
0 + 6
Maarten Bodewes avatar
флаг in
Maarten Bodewes
Итак, ваша функция Z выводит начальное число вместе со случайными значениями, полученными из него? Алгоритм тоже известен.
1
Ответить
cryptonoob avatar
флаг bd
cryptonoob
@MaartenBodewes Да, именно так. Но что вы имеете в виду под «алгоритм тоже известен»? G ist далее не уточняется. Следовательно, если мне нужно привести контрпример для случая, когда Z не является PRG, я могу спроектировать G как захочу.
0
Ответить
Maarten Bodewes avatar
флаг in
Maarten Bodewes
Нет, обычно это неправильно. Обычно мы исходим из принципа Керкхоффа: любая безопасность заключается не в алгоритме, а в ключе или, в данном случае, в семени. Вы можете спроектировать $G$ как хотите, но вы должны предполагать, что любой злоумышленник знает алгоритм. Другими словами: вы не можете предполагать, что $G$ генерирует какую-либо секретность, кроме начального значения $x$. Что произойдет, если вы сначала сгенерируете ключ, а затем IV, используя $Z$?
0
Ответить
SEJPM avatar
флаг us
SEJPM
Подсказка: возможно, есть какой-то тест / различитель, который может проверить, исходит ли данная строка случайного вида из $ Z $ или просто случайно? Предположим, что противник также может вычислить $G$.
2
Ответить
cryptonoob avatar
флаг bd
cryptonoob
@MaartenBodewes Единственная идея, которая у меня есть, заключается в том, что злоумышленник может получить ключ / начальное число из вывода Z, выполнив разрез (потому что противник знает алгоритм и знает, что длина ключа равна n). Затем он может ввести этот «ключ» в функцию и проверить, тот же ли это вывод или нет. Насколько я знаю, PRG является детерминированным. И в этом случае он даже знает ключ. Правильном пути?
0
Ответить
Maarten Bodewes avatar
флаг in
Maarten Bodewes
Да, это правильный трек. Как правило, невозможно получить состояние ГСЧ, поскольку это приведет к утечке информации обо всех других байтах в потоке.
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.