Факторизация решетом
Правильно ли я понимаю, что методы поиска ключей асимметричных систем полным перебором с применением методов типа "решето" основаны на математическом определении областей чисел в которых поиск является наименее вероятным или бессмысленным вовсе?
Сложно в простом виде описать все виды решета сразу.
Если кратко, то выбирается число или ряд чисел для факторизации. Затем производят поиск чисел у которых значение "гладкости" меньше этого фактора. "Гладкость (smooth)" – это максимальный простой множитель, который надо возвести в степень для получения числа из всего ряда сомножителей. Всё это записывается в виде матриц или массивов большого объёма, над которыми проводят сравнения, "просеивание" результатов вычисления наибольших общих делителей, итерации и т.д.
И для нахождения гладких чисел и для просеивания и для последующих вычислений используется много методов из теории чисел, линейной алгебры, и т.д. Не берусь сказать, насколько корректно это всё можно свести к фразе о "поиске наименее вероятных областей", но если не использовать специальную математическую терминологию и в первом приближении, то процесс можно представить и так.
Единственно, здесь не вполне неуместно слово "полный перебор", т.к. процесс итеративный и критерия "полноты перебора" нет.
В продолжение можно почитать отсюда[link1] и ниже (раздел "Факторизация ключа")
Вообще, тут стоит заметить, что ресурсы для поиска делителей методами решета зависят исключительно от размера модуля. Ресурсы для поиска методом перебора зависят от размера простых делителей. Если модуль — продукт двух простых чисел, то это значительно больше, чем в случае решета, то есть стойкость системы против разных атак неуравновешена, а значит ресурсы защиты распределены нерационально.
Для уравновешанно стойкой защиты использyются RSA модули с несколькими (не двумя) простыми делителями. Например, для ключа в 1024 битов, уравновешенным выбором считается 8 простых чисел по 128 битов каждое.
К сожалению, такие ключи поддерживаются стандартом OpenPGP только частично и в некоторых юрисдикциях (например в США) метод запатентован (компанией Compaq) и патент еще действует.
Хотя скорость операций с закрытым ключем (подпись и расшифрование) на порядок быстрее такими RSA ключами. В англоязычной литературе это называется multiprime RSA и включен в последнюю редакцию PKCS#1.
[quote:6f0aa5100a="Д. Надь"]Для уравновешанно стойкой защиты использyются RSA модули с несколькими (не двумя) простыми делителями. Например, для ключа в 1024 битов, уравновешенным выбором считается 8 простых чисел по 128 битов каждое.
]>
Странно. Простые делители такого размера как правило эффективно находятся с помощью алгоритма ECM[link2].
@RElf
Вы правы. Я должен был написать 4 делителя по 256 битов каждый.
Факторизация решетом (NFS) подобралась вплотную к модулям в 768 битов, а факторизация ECM к простым делителям в 192 бита.
Mea culpa.