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

Уточнение по расчету одноразовых столкновений

флаг gb
PaulV1990

Я работаю над реализацией AES256-GCM (на Java). Я немного застрял в той части, где мне нужно решить, как часто мне нужно поворачивать ключ.

Я получил много информации из этого поста: Безопасность случайного одноразового номера с AES-GCM?

И веб-сайт, если он ссылается на: https://www.imperialviolet.org/2015/05/16/aads.html

В нем приводится следующая цитата:

Это потому, что если вы бросите 2$^{32}$ мячи в 2$^{96}$ ведра, то у вас есть примерно 2$^{-33}$ шанс получить два в том же ведре.

Как производится этот расчет? Единственное решение, о котором я могу думать, это:

2$^{(95-128)}$=2$^{-33}$

Я хотел бы знать следующее:

  1. Это правильный расчет?
  2. 2$^{95}$ выбрано, потому что нужно только 50% и 2$^{96}$ / 2 = 2$^{95}$
  3. Вычитание на 128 относится к общей длине IV или к чему-то еще?
42
0 + 0
Рейтинг:1
Daniel S avatar Crypto
флаг ru
Daniel S

Боюсь, это значительно более сложный расчет, основанный на математике проблема дня рождения. По ссылке, если кинуть $n$ шары в $д$ ведра, то вероятность $р(н;д)$ столкновения примерно $$p(n;d)\приблизительно 1-\exp\left(-\frac{n(n-1)}{2d}\right)= \frac{n(n-1)}{2d}+O \left(\frac{n^4}{d^2}\right)$$ (второе приближение, следующее из ряд Тейлора для $\ехр(х)$).

Подключение $n=2^{32}$ и $d=2^{96}$ дает $p\примерно 2^{-33}$. В более общем случае, если $n=2^a$ и $ д = 2 ^ б $ у нас будет $p\приблизительно 2^{2a-b-1}$ при условии, что $2а$ заметно меньше, чем $b$.

0 + 0
PaulV1990 avatar
флаг gb
PaulV1990
Спасибо за этот ответ.
0
Ответить
PaulV1990 avatar
флаг gb
PaulV1990
Добавляя этот комментарий, нажмите Enter вскоре после того, как поблагодарите, и форматирование займет некоторое время. Я рассчитывал немного по-другому, согласно этим сообщениям: - https://math.stackexchange.com/questions/883983/день рождения-парадокс-огромные числа - https://preshing.com/20110504/hash-collision-probabilities/ Это дает тот же результат с упомянутым вами правилом: $a^2
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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