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

Как рассчитать n в n-битной безопасности криптоалгоритма?

флаг ng
ystark

Я думаю, что я, вероятно, пропустил термин, потому что поиск по нему дает не такие точные результаты. Я хочу рассчитать n-битную безопасность, скажем, Paillier vs ElGamal vs EC ElGamal, когда я использую x-битный ключ.

Этот В документе говорится, что «для достижения 128-битного уровня безопасности в ElGamal обычно используются 4096-битный p и 256-битный q, а в Paillier размер n обычно выбирается равным 4096 битам».

Как рассчитать, какие значения необходимы для 256-битной безопасности? Здесь просто умножить на два?

221
3 + 0
Рейтинг:5
ckamath avatar Crypto
флаг ag
ckamath

TLDR: Размер группы/кольца определяется самым быстрым известный в настоящее время атака (как описано в это статью в Википедии).

Подробности. Для случая дискретного входа $\mathbb{Z}_p^*$ и факторинг $\mathbb{Z}_N^*$, самым быстрым из известных на данный момент алгоритмов является сито общего числа (ГНФС). GNFS имеет время работы (примерно) $L_n(1/3,2)$, куда $$L_n(\alpha,c):=e^{(c+o_n(1))n^\alpha\ln^{1-\alpha}(n)}$$ это $L$-обозначение и $n$ обозначает битовую длину (стандартное представление) $р$ или же $N$ (т.е. $\lceil(\log(p)\rceil$ и $\lceil(\log(N)\rceil$, соответственно).$^*$ С $b$-бит безопасности для схемы означает, что она должна принимать любой алгоритм $2^б$ операции, чтобы разбить его, чтобы вычислить $n$ за $\mathbb{Z}_p^*$ и $\mathbb{Z}_N^*$ что достигает $128$-бит безопасности нужно решить для $$2^{128}\приблизительно е^{2n^{1/3}\ln^{2/3}(n)}\Leftrightarrow n\ln^2(n)\приблизительно64^3.$$ Это даст приблизительную цифру того, каким должен быть размер модуля - как вычислено в это ответ это оказывается вокруг $3072$ биты (или $4096$ биты, чтобы быть на более безопасной стороне?). Поскольку мы не знаем лучшего средства для решения DDH/CDH (задач, лежащих в основе схем типа Эль-Гамаля), чем вычисление дискретных журналов, Эль-Гамаль в (частном) $\mathbb{Z}_p^*$ необходимо развернуть с простыми размерами $\приблизительно3072/4096$ биты.

Точно так же, поскольку мы не знаем лучшего средства для решения решение квадратичной задачи остаточности в $\mathbb{Z}_{N^2}^*$ (проблема, которая лежит в основе Крипосистема Пайе), чем фактор $N$, по тому же аргументу выше, нам нужно работать $N$ размера $\примерно 3072/4096$ биты.

Я считаю, что для дискретно-логарифмических операций на эллиптических кривых мы не знаем ничего лучше, чем общие алгоритмы дискретно-логарифмических операций (например, Ро Полларда), которые выполняются за время, равное квадратному корню из размера группы. Следовательно, для $128$-битовая безопасность EC-Эль-Гамаля, достаточно работать с эллиптическими кривыми над полем размером $2^{256}$. (Это также означает, что EC-El-Gamal значительно более эффективен в общении, чем El-Gamal в $\mathbb{Z}_p^*$.)

$^*$Первоначальная GNFS является эвристикой. Но, как указал @djao (см. это комментарий), есть доказуемые варианты, которые выполняются в $\приблизительно L_n(1/3,3)$.

0 + 2
djao avatar
флаг cn
djao
Было доказано, что решето числового поля работает за заявленное время и, в частности, (доказуемо) быстрее, чем квадратичное решето. https://cstheory.stackexchange.com/questions/32508/
2
Ответить
ckamath avatar
флаг ag
ckamath
Спасибо! Я не знал. Обновлю ответ.
0
Ответить
Рейтинг:1
TurkBitig avatar Crypto
флаг fr
TurkBitig

n-битная безопасность каждого алгоритма рассчитывается с помощью «наилучшего метода атаки». Например, RSA основан на проблеме факторизации, и ее можно решить с помощью алгоритма «Сито числового поля», поэтому мы используем «сложность вычислений» NFS для определения n-битного уровня безопасности RSA. Для криптографических хеш-функций мы используем «атаку дня рождения» для расчета n-битной безопасности и т. д.

0 + 0
Рейтинг:0
SAI Peregrinus avatar Crypto
флаг si
SAI Peregrinus

Нет единого простого ответа. n-битная безопасность означает логарифм по основанию 2 (обычно записывается просто $\лог$) количества «операций», необходимых для взлома примитива.

Для симметричного шифра, такого как AES-128, «операция» обычно представляет собой пробное шифрование или дешифрование, что намного больше, чем один цикл ЦП. AES-128 обычно имеет 128-битную безопасность, потому что $2^{128}$ возможные ключи, и нет общей атаки быстрее, чем попробовать все ключи, и $\лог(2^{128})=128$.

Асимметричные системы, такие как Paillier, ElGamal и EC ElGamal, атакуют гораздо быстрее, чем перебирают все возможные ключи. Таким образом, чтобы рассчитать «эквивалентную симметричную безопасность» в битах, вам нужно рассчитать стоимость самой известной атаки на используемые параметры.

Вам также необходимо решить, сильно ли отличается стоимость «операции» в такой атаке от «операции», атакующей симметричные шифры, с которыми вы сравниваете, и если да, то масштабируйте количество операций соответствующим образом.Это последнее соображение объясняет, почему асимметричные системы, подобные Эль-Гамалю, будут иметь вдвое меньше битов защиты от атак универсальных квантовых компьютеров с исправлением ошибок, чем от современных компьютеров.

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

0 + 0
флаг Moldova
Admin
Этот вопрос на других языках:

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

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