Comments 22
На портрете Декарт.
Если допустим были сгенерированы уязвимые ключи для RSA 2048, то сколько времени потребуется на взлом? А если ключи будут RSA 4096? Стоит ли паниковать?
Если уязвимые — плюс-минус столько же, сколько для RSA512. Если нормальные — так не взломать.
Стоит ли паниковать?
Мне кажется, что речь не о панике, а о знании. Это знание полезно как разработчику, так и пользователю.
Я просто думал, что если в алгоритме идет генерация уязвимых ключей тогда нужно знать сколько времени займет взлом? Если учесть что уязвимость понижает кючи до 512 бит и уже сейчас не рекомендуют использовать ниже 1024 тогда это очень плохо с точки зрения безопастности и нужно перепроверять все библиотеки что занимаются генерацией этих ключей. В статью надобы добавить библиотеки и их версии что имеют проблемы и что нормально генерируют RSA ключи.
В статью надо бы добавить библиотеки и их версии что имеют проблемы и что нормально генерируют RSA ключи.
Ваше предложение полностью поддерживаю, тем более что аналогичный инцендент уже встречался, правда с российским хэшем ГОСТ Р 34.10-2012.
Ферма, Декарт, какая разница :D
Мы хотим представить нечетное N в виде A^2 — B^2. Если N % 4 == 1, то легко убедиться, что A должно быть нечетным, а B — четным. А в случае N % 4 == 3 наоборот: A четное, B нечетное.
Дальше смотрим на N % 3. Если N % 3 == 1, тогда A не кратно 3, B кратно 3. В случае N % 3 == 2 у нас A кратно 3, B не кратно 3.
И дальше, перебирая остатки N по простым модулям, можем ограничить возможные значения A, B по каждому модулю, и собрать по китайской теореме об остатках возможные значения по модулю произведения простых.
Например, по модулю 2*3*5*7 будет меньше 25 возможных значений из 210.
Но это еще не всё! Мы предполагаем, что N — произведение ровно двух простых N = p*q. Тогда из малой теоремы Ферма следует, что для любого x, не кратного p и q, выполняется x^((p-1)*(q-1)/2) % N == 1. Выберем например x = 2. Небольшое преобразование: 2^((N+1)/2) % N == 2^((p+q)/2) % N. Слева известное значение. Справа — неизвестный показатель, то есть свели к дискретному логарифму. Можно использовать небольшую модификацию алгоритма больших и малых шагов. За большой шаг взять произведение маленьких простых, а возможные значения для малых шагов собрать в хеш-таблицу, размер которой мы уменьшили за счет ограничений на (p+q)/2. С таким подходом кажется реальным за несколько минут перебрать значения до abs(p-q) < sqrt((p+q)/2) * 2^64
А почему нельзя после генерации p и q просто проверить на эту уязвимость и перегенерировать, если пара уязвимая?
"Да, могут. Но для этого необходимо, чтобы они были идентичны, по меньшей мере, в своих старших 500 битах. Вероятность такого исхода — 1:2^500"
Даже это уже не так и много, примерно 10^20. При расчётной скорости перебора 10^9 за секунду ("довольно шустрым, но совершенно одноядерным" алгоритмом) уйдёт 10^11 секунд, 300 лет, а на ядрах чего-то ГПУ-образного всё может случиться в несколько сот (а то и тысяч) раз быстрее.
Перед Декартом неудобно...
Атака Ферма на RSA