Рейтинг:2

Выполнение OTP два или более раз с предвзятым TRNG: будет ли это иметь такую ​​же безопасность, как если бы это было сделано с непредвзятым TRNG?

флаг pf

Предположим, я хочу сделать одноразовый блокнот а у меня только предвзятое генератор истинных случайных чисел (TRNG).

Я XOR к блоку зашифрованного текста с другим блоком со случайными данными, полученными из TRNG, e повторите процесс два или более раз с разными случайными блоками.

Сделает ли эта схема одноразовый блокнот более безопасным? Будет ли это обеспечивать такую ​​же безопасность, как если бы это было сделано с беспристрастным TRNG?

флаг ar
Учитывая, что операция XOR блока, подлежащего шифрованию, $n$ раз с разными случайными блоками эквивалентна операции XOR один раз с XOR всех $n$ случайных блоков, более плодотворным способом переформулировать этот вопрос может быть «(сколько) Объединение XOR $n$ блоков смещенных случайных битов вместе уменьшает смещение?" Кроме того, FWIW, этот процесс (и другие подобные методы улучшения качества TRNG) широко известен как «отбеливание».
Reinstate Monica avatar
флаг gd
Более эффективный подход и совершенно беспристрастный, предполагающий независимость подбрасывания монеты: подбрасывать дважды для каждого бита и устанавливать бит в 0, если подбрасывания одинаковы.
Рейтинг:10
флаг dz

Лучше, чем использовать его один раз, но не так хорошо, как беспристрастный TRNG.

Чтобы увидеть это, предположим, что наш TRNG очень предвзят, выдавая ноль в 10% случаев и единицу в 90% случаев.

Если мы используем TRNG дважды, для каждого бита у нас есть четыре возможности:

  • Оба раза мы получаем 0 от TRNG. Это произойдет в 10% * 10% = 1% случаев.
  • В первый раз мы получаем 0, а во второй раз мы получаем 1: это произойдет в 10% * 90% = 9% случаев.
  • В первый раз мы получаем 1, а во второй раз мы получаем 0: это произойдет в 90% * 10% = 9% случаев.
  • Оба раза мы получаем 1 от TRNG. Это произойдет в 90% * 90% = 81% случаев.

Таким образом, после XOR первый и последний случаи дают 0, а второй и третий случаи дают 1. Таким образом, в 82% случаев мы получаем 0 и в 18% случаев мы получаем 1. Таким образом, результат все еще предвзятый TRNG, но не такой плохой, как исходный TRNG. Если вы повторите это достаточное количество раз, вы можете приблизиться к 50/50 настолько, что на практике это не будет иметь значения. Менее предвзятый TRNG доберется туда быстрее, но будут применяться те же принципы.

Рейтинг:8
флаг sa

Сходимость предложенного вами процесса к несмещенным битам определяется леммой о накоплении. Это будет медленно. Более эффективно использовать процедуры несмещения, такие как несмещение фон Неймана. См. например этот вопрос

Но это конечно проще из-за прямого XOR.

За $n$ независимые одинаково распределенные $\{0,1\}$ ценные случайные величины, $X_1, X_2, \ldots X_n$:

$$ Pr(X_1 \oplus \ldots \oplus X_n = 0) = \frac{1}{2} + 2^{n-1} \prod_{i=1}^n \epsilon_i $$ куда $\epsilon_i$ является предвзятость $X_i.$ Это дает окончательное смещение как

$$ \epsilon_{1,2, \ldots, n} = 2^{n-1} \prod_{i=1}^n \epsilon_i $$

Для каждого бита ваших комбинированных блоков и на примере смещения $\эпсилон_i = 0,4$ за $i=1,\ldots, n$ (соответствует 90% в другом ответе) мы получаем смещения, как показано ниже

\начать{массив}{с|с|с} \textrm{Число } & \textrm{Результирующая погрешность} & \textrm{Вероятность 1} \ \textrm{комбинированные блоки ($n$)} & & \ 2 и 0,32000 и 82,0\%\ 4&0,20480&70,4\%\ 8 и 0,083886 и 58,4\%\ 16 и 0,014074 и 51,4\% \конец{массив}

К вашему сведению, эта медленная сходимость из-за $2^{n-1}$ фактор является причиной работы линейного криптоанализа.

phantomcraft avatar
флаг pf
Спасибо за ответ, но мне пришлось выбрать другой ответ как «лучший ответ», потому что я очень новичок в криптографии и не очень хорошо понял ваши формулы.
kodlu avatar
флаг sa
Совершенно никаких проблем. Формулы показывают, что происходит в общем случае
Рейтинг:3
флаг cn

В значительной степени да.

Многие конструкции TRNG полностью основаны на цифровых схемах и не содержат каких-либо аналоговых компонентов [см. примечание]. Это упрощает их нанесение на кремний. Но, к сожалению, цифровые схемы имеют тенденцию работать в цифровом виде и поэтому довольно плохо генерируют энтропию. Поэтому вместо того, чтобы давать вам теоретический пример, вот реальный TRNG с очень плохой погрешностью:

Это из бумага создание FPGA TRNG.

плл

Обратите внимание на Дециматора. Его роль заключается в последовательном XOR $K_D$ выборки вместе, чтобы увеличить энтропию на выходную выборку. В таком случае, $K_D=7$, с вашей точки зрения эффективно объединяя семь одноразовых паролей XOR вместе. Позже в этой статье $K_D$ достигает 185 для другого дизайна. Это 185 предвзятых выборок TRNG, объединенных XOR вместе с использованием Лемма о накоплении. Я не могу найти ссылку для вас, но я видел коэффициент прореживания 512 в кольцевом генераторе TRNG.

Таким образом, вы обнаружите, что последовательное множественное XOR распространено во всех цифровых TRNG в форме прореживания. Это позволяет избежать более сложных методов извлечения энтропии, таких как хеширование, которые требуют больше кремниевой недвижимости.


Запись.Я утверждаю, что в этом случае существует чисто цифровая схема, понимая, что все схемы в основном аналоговые на микроуровне.

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

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