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