Рейтинг:0

При использовании простой факторизации для генерации ключей существует ли ограничение на размер простых факторов?

флаг it

Если есть ограничение, остается ли ограниченное количество простых чисел, которые можно использовать для генерации ключей? И если это так, уязвима ли система шифрования?

user avatar
флаг in
Да, если вы можете перечислить каждые 16 КБ (или любой другой произвольный размер бит) простые множители большого составного числа, то вы можете взломать 16 КБ RSA и аналогичные криптосистемы, которые полагаются на сложность простой факторизации. Между прочим, это довольно большие цифры.
Рейтинг:1
флаг ng

«Простая факторизация» не представляет интереса, поскольку простые числа — это их собственная факторизация.

Разложение на простые числа не используется для генерации ключей.

Я заключаю, что вопрос спрашивает:

При генерации простых чисел во время генерации пар открытого/закрытого ключей для критосистем на основе сложности факторизации (RSA, Rabin, Pailler…) существует ли ограничение на размер простых множителей? Если да, то остается ли ограниченное количество простых чисел, которые можно использовать для генерации ключей? И если да, делает ли это систему шифрования уязвимой?

Математически нет верхнего предела размера простых множителей. Существует бесконечно много простых чисел и (таким образом) простых чисел любого размера.

Некоторые стандарты устанавливают ограничения. Например FIPS 186-4 имеет верхний предел $1536$ кусочек; точнее, для этого размера каждое из двух простых чисел, образующих составной модуль, должно находиться в интервале $[2^{1535.5},2^{1536}]$, так что произведение $3072$-кусочек. Посредством теорема о простых числах, есть примерно о $2^{1524}$ простые числа в этом интервале. Это о $600\underbrace{\text{миллион}\ldots\text{миллион}}_{76\text{умножить на слово "миллион}}$. Это ограничено, но настолько велико, что не делает систему уязвимой для каких-либо практических целей.

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

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