Тут в соседней ветке http://wasm.ru/forum/viewtopic.php?id=42450 обсуждалась интересная тема - факторизация больших чисел - атака на ключи RSA. Вопрос - а никому не попадались программы атаки на DSA Код (Text): y = g^x mod p - отыскания логарифма Код (Text): x = log(g) y mod p Читал об алгоритме исчисления порядка и его модификации Number Field Sieve, как об одном из самых быстрых... есть ли реализации? А также, возможно, кому-то попадались программы атаки на ECC - ткните носом в ссылки... буду благодарен...
Ага - оказывается тот же msieve http://sourceforge.net/projects/msieve/ может это делать.. осталось разобраться - как...
в основе DSA лежит Задача дискретного логарифмирования(discrete logarithm problem). Для решения есть алгоритмы с экспоненциальной сложностью: Pohlig–Hellman, Pollard's rho, Baby-step giant-step и пр.
kyprizel Есть и субэкспоненциальные алгоритмы - Адлемана, COS, Решето числового поля ... Вопрос в другом - найти эффективные реализации...
Нашел информацию, что некоторые математические пакеты реализуют дискретное логарифмирование больших чисел по модулю. Если кто-то юзает MAXIMA (http://maxima.sourceforge.net/ru/) или MAGMA (http://magma.maths.usyd.edu.au/magma/) - поделитесь опытом по логарифмированию ...
если тебе нужен не сам код, а реализованное решение - используй PARI/GP, напрямую, или через Sage. подробная документация есть в сети.
Продолжаем разговор по теме... Есть система DSA с базой (p,q,g) длина(p) = 128 байт длина(q) = 20 байт длина(g) = 128 байт (p,q - простые, (p-1)|q) y = g^x mod p y - открытый ключ (длина 128 байт) x - закрытый ключ (длина 20 байт, 0 < x < q) Известно, что ключ x - вырожденный и его битовая длина всего 64 бит (или 8 байт). Вопрос: какой алгоритм лучше всего использовать для нахождения x по известному y? Пока самое приемлемое решение - использовать алгоритм Baby-step giant-step (в идеале решаемо за 2*2^32 итераций), но он кушает много памяти... (и в лучшем случае сложность будет 2^44 + 2^22) Возможно ли ро-алгорим Полларда подстроить под такую задачу (и получить ответ за 2^32 итераций)? (в классическом варианте для ро-алгоритма Полларда потребуется 2^80 итераций...)
