id: Гость   вход   регистрация
текущее время 04:42 29/03/2024
Автор темы: Гость, тема открыта 16/04/2006 16:00 Печать
https://www.pgpru.com/Форум/Криптография/ФакторизацияРешетом
создать
просмотр
ссылки

Факторизация решетом


Правильно ли я понимаю, что методы поиска ключей асимметричных систем полным перебором с применением методов типа "решето" основаны на математическом определении областей чисел в которых поиск является наименее вероятным или бессмысленным вовсе?


 
Комментарии
— unknown (16/04/2006 17:50)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Правильно ли я понимаю, что методы поиска ключей асимметричных систем полным перебором с применением методов типа "решето" основаны на математическом определении областей чисел в которых поиск является наименее вероятным или бессмысленным вовсе?

Сложно в простом виде описать все виды решета сразу.

Если кратко, то выбирается число или ряд чисел для факторизации. Затем производят поиск чисел у которых значение "гладкости" меньше этого фактора. "Гладкость (smooth)" – это максимальный простой множитель, который надо возвести в степень для получения числа из всего ряда сомножителей. Всё это записывается в виде матриц или массивов большого объёма, над которыми проводят сравнения, "просеивание" результатов вычисления наибольших общих делителей, итерации и т.д.

И для нахождения гладких чисел и для просеивания и для последующих вычислений используется много методов из теории чисел, линейной алгебры, и т.д. Не берусь сказать, насколько корректно это всё можно свести к фразе о "поиске наименее вероятных областей", но если не использовать специальную математическую терминологию и в первом приближении, то процесс можно представить и так.

Единственно, здесь не вполне неуместно слово "полный перебор", т.к. процесс итеративный и критерия "полноты перебора" нет.
— SATtva (16/04/2006 20:44)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
В продолжение можно почитать отсюда и ниже (раздел "Факторизация ключа")
— Гость (17/04/2006 12:56)   <#>
Вообще, тут стоит заметить, что ресурсы для поиска делителей методами решета зависят исключительно от размера модуля. Ресурсы для поиска методом перебора зависят от размера простых делителей. Если модуль — продукт двух простых чисел, то это значительно больше, чем в случае решета, то есть стойкость системы против разных атак неуравновешена, а значит ресурсы защиты распределены нерационально.
Для уравновешанно стойкой защиты использyются RSA модули с несколькими (не двумя) простыми делителями. Например, для ключа в 1024 битов, уравновешенным выбором считается 8 простых чисел по 128 битов каждое.
К сожалению, такие ключи поддерживаются стандартом OpenPGP только частично и в некоторых юрисдикциях (например в США) метод запатентован (компанией Compaq) и патент еще действует.
Хотя скорость операций с закрытым ключем (подпись и расшифрование) на порядок быстрее такими RSA ключами. В англоязычной литературе это называется multiprime RSA и включен в последнюю редакцию PKCS#1.
— RElf (18/04/2006 09:16)   профиль/связь   <#>
комментариев: 32   документов: 0   редакций: 0
[quote:6f0aa5100a="Д. Надь"]Для уравновешанно стойкой защиты использyются RSA модули с несколькими (не двумя) простыми делителями. Например, для ключа в 1024 битов, уравновешенным выбором считается 8 простых чисел по 128 битов каждое.
]>
Странно. Простые делители такого размера как правило эффективно находятся с помощью fileалгоритма ECM.
— Гость (22/04/2006 05:15)   <#>
@RElf
Вы правы. Я должен был написать 4 делителя по 256 битов каждый.
Факторизация решетом (NFS) подобралась вплотную к модулям в 768 битов, а факторизация ECM к простым делителям в 192 бита.
Mea culpa.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3