Написал программу генерации RSA ключей с 512-битным модулем (она в аттаче). Не могу понять одну вещь. Программа получилась жутко тормозная. Ну это в принципе понятно. Но когда ее запускаешь после работы в винде, послушав там чего нибудь в винампе, то скорость работы программы возрастает в несколько раз. Никак не могу понять в чем может быть причина. Кто чего думает по этому поводу? Еще вопрос: можно ли сделать процедуру деления с остатком более быстрой? (в смысле алгоритма). И еще возник один вопрос: Насколько надежен будет RSA-512? А то может модуль можно разложить на множители всего лишь за неделю? То есть как сейчас в мире обстоят дела с факторизацией?

2070832811__KEY512.ASM

512 бит использовать не рекомендуется, т.к. при наличии серьезных вычислительных мощностей разложение вполне возможно. Впервые 512-битный модуль был разложен 5 лет назад... Думаю, комментарии излишни? :)
Текущий рекорд факторзации -- 576 бит.

Icebp
„Но когда ее запускаешь после работы в винде, послушав там чего нибудь в винампе, то скорость работы программы возрастает в несколько раз. “
Ничего удивительного. Если слушаешь mp3, то для его распаковки процессор тоже нужен. Все остальное - игра на приоритетах. Подними приоритет своей программы. Но тогда в winamp-е будет рваный звук :-)

Ухмм... А что ты собрался им шифровать ? ;)
Если ничего серьёзного, то можешь смело использовать
512 битный ключ. Никто его не поломает... ;)

Ну только, если за тебя ФСБ что-ли возьмётся, тогда возможно, а так не слушай басни типа RSA-576 факторизовали, так мол - всё - конец..... :p

Icebp „Программа получилась жутко тормозная.“

У меня на w2k ничего не делает , висит .

Вот для сравнения виндовый способ генерации ключей , тормоза немного есть из-за CryptAcquireContext , а основное находиться в CryptGenKey , там можешь продебажить до CPGenKey .

А у тебя вообще какой там RNG ?

_1998730008__rsakeys.zip

valterg
Ты меня неправильно понял. Я имел в виду следующее: вот запустил я генерацию ключей под чистым ДОС-ом. При этом генерация ключей идет жутко проторможенно. Потом я чтобы отдохнуть запускаю Винды и слушаю музыку винампом. Потом, решив вернуться к своей программе, я закрываю винамп, выхожу нафиг из виндов и из под чистого ДОС-а снова запускаю свою программу. Так вот, после этого она работает гораздо быстрее. Никак не могу понять в чем тут причина.
snatch
Эти ключи я собираюсь использовать для цифровой подписи (шифрование односторонней функции от содержимого файла секретным ключом). А насколько сложно будет факторизовать 512-битное число для злоумышленников? Я почему опасаюсь, так это потому, что видел как в основном используют RSA-1024. Это делают для перестраховки или есть реальная угроза факторизации 512-битных чисел?

"А насколько сложно будет факторизовать 512-битное число для злоумышленников?"

Хех... Ну вообщем это зависит от того, кому это надо и какими вычислительными мощностями они обладают. В домашних условиях это дело ближайших ~ 1,5 - 2 лет, если вообще удасться.
Ну а если у челов есть специализированная вычислительная система: кластер какой-нибудь навороченный + программное обеспечение написанное для этого, то может за пару месяцов и управятся... :)

Ты главное используй для генерации RSA ключей нормальный RNG. ;)

„Эти ключи я собираюсь использовать для цифровой подписи “

Обычно ЭЦП подразумевает булевый результат - верна, не верна . Т.ч. быстрее будет найти и поправить пару байт чем факторизовать . Или у тебя не так ?

„или есть реальная угроза факторизации 512-битных чисел?“

Смотря какая реализация и на сколько будет выгоден взлом .
Кстати snatch уже говорил , что и RSA-2048 ломали .
Я не математик , но возможно что на схему с цифровой подписью , существует больше атак .
Самому интересно , т.к. если существует некое множество зашифрованных подписей удовлетворяющих одному ключу , то возможно что быстрее найти одну подпись из множества , чем факторизовать "ключ" ?

Кстати snatch уже говорил , что и RSA-2048 ломали .


Я бы жутко хотел услышать как. NFS такие числа не берет. О MQFS и PPQFS я уж вообще промолчу. Я понимаю, что, если уж оно попадет к АНБ или ФСБ в гости - там, конечно, разломают, но ДАЖЕ для серьезного концерна крякнуть что-нибудь уровня 1024-бита - да заломаются!

Вот , ты в отпуске был :)

bogrus

Солнышко, ну так это же не взлом RSA! Это самый обычный ЛЯП людей, которые толком не знают как БЕЗОПАСНО генерировать сильные простые числа. Такие дыры быстро закрываются... А ты говоришь, взломали-взломали... Фиг там!

Самому интересно , т.к. если существует некое множество зашифрованных подписей удовлетворяющих одному ключу , то возможно что быстрее найти одну подпись из множества , чем факторизовать "ключ" ?

Ха-ха-ха. Даже атака дней рождения здесь будет давать примерно то же время, что и факторизация. Там не идиоты эти схемы выдумывали. Хотя искать коллизии тоже можно достаточно утонченно... С этим пока не разбирался.

2volodya про RSA-2048.

Насколько я понял, ресь идет о ключах аспра... дык там был *очень* дырявый RNG, вот его и поломали...

а 512 бит я все-равно использовать бы не советовал... сейчас я на своем компе могу за пару недель разложить числа порядка 400 бит, возьмите небольшой клестер, вершин так на 32, и 512 бит разложатся за месяц-другой.

Понятно. Согласен.

"...числа порядка 400 бит..."
вот именно... :p

"...возьмите небольшой клестер, вершин так на 32, и 512 бит разложатся за месяц-другой."
Ну-ну... давай-давай... шутник... ;)
Разве что на Cray X1 system какой-нибудь... Да плюс еще алгоритм факторизации оптимизированный понадобится...

А вообще чего спорить... Давайте браться за дело... ;D