тормоза в RSA

Написал программу генерации 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.

 

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

Смотря какая реализация и на сколько будет выгоден взлом .

Кстати 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

 

Ну вот например схема проверки , для регистрации проги нужно ввести Message и Signature .



CryptHashData,Hash,Message

CryptVerifySignature,Hash,Signature,Key



Hash - MD5 хеш от Message

Signature - зашифрованное секретным ключём Message

Key - публичный ключ



CryptHashData - берёт MD5 хеш от Message

CryptVerifySignature - расшифровывает Signature , также берёт MD5 хеш от расшифрованного и сверяет хеши .



Беру любой набор байт наугад (будет Signature) , расшифровываю их публичным Key (будет Message) и ввожу в прогу эти Message и Signature .

Что в этой схеме вернёт CryptVerifySignature - TRUE или FALSE ?

Было бы слишком просто если TRUE , где я гоню ?

 

Если я правильно вкурил, то, конечно, FALSE. Ведь хеш-то не совпадет! Ведь MD5 считается! А при чем тут RSA?

 

Почему , ведь MD5 хеш и там и там , берёться от одного и того-же Message . Т.е. расшифрованная Signature это и будет Message .

Это вроде "стандартная" схема цифровой подписи RSA , публичный ключ у меня RSA-512 , ним расшифровываеться Signature . Это если я конечно правильно всё понимаю .



з.ы. В стойкости RSA я не сомневаюсь , меня интересует именно эта схема . Т.е. CryptVerifySignature должна вернуть TRUE . Как это пропатчить или сделать лоадер я знаю , не предлагайте .

 

Почему , ведь MD5 хеш и там и там , берёться от одного и того-же Message . Т.е. расшифрованная Signature это и будет Message

там не Message, там хеши, вот схема подписи:



создание:

http://bcw.narod.ru/pic/web_5.jpg

проверка:

http://bcw.narod.ru/pic/web_6.jpg



ну и сама статья

http://bcw.narod.ru/cryptoapi.html

 

bogrus



Я запутался с терминами Signature и Message. Если не сложно, то еще раз - для особо одаренных



Fuck. Пока писал, уже Funbit ответил