тормоза в RSA

Тема в разделе "WASM.RESEARCH", создана пользователем Icebp, 30 авг 2004.

  1. Icebp

    Icebp New Member

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

    [​IMG] 2070832811__KEY512.ASM
     
  2. flankerx

    flankerx New Member

    Публикаций:
    0
    Регистрация:
    2 июл 2004
    Сообщения:
    423
    Адрес:
    Moscow, Russia
    512 бит использовать не рекомендуется, т.к. при наличии серьезных вычислительных мощностей разложение вполне возможно. Впервые 512-битный модуль был разложен 5 лет назад... Думаю, комментарии излишни? :)

    Текущий рекорд факторзации -- 576 бит.
     
  3. valterg

    valterg Active Member

    Публикаций:
    0
    Регистрация:
    19 авг 2004
    Сообщения:
    2.105
    Icebp



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

    snatch New Member

    Публикаций:
    0
    Регистрация:
    27 июл 2003
    Сообщения:
    27
    Адрес:
    Belarus
    Ухмм... А что ты собрался им шифровать ? ;)

    Если ничего серьёзного, то можешь смело использовать

    512 битный ключ. Никто его не поломает... ;)



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

    bogrus Active Member

    Публикаций:
    0
    Регистрация:
    24 окт 2003
    Сообщения:
    1.338
    Адрес:
    ukraine
    Icebp




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



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



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

    [​IMG] _1998730008__rsakeys.zip
     
  6. Icebp

    Icebp New Member

    Публикаций:
    0
    Регистрация:
    24 дек 2003
    Сообщения:
    39
    valterg

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

    snatch

    Эти ключи я собираюсь использовать для цифровой подписи (шифрование односторонней функции от содержимого файла секретным ключом). А насколько сложно будет факторизовать 512-битное число для злоумышленников? Я почему опасаюсь, так это потому, что видел как в основном используют RSA-1024. Это делают для перестраховки или есть реальная угроза факторизации 512-битных чисел?
     
  7. snatch

    snatch New Member

    Публикаций:
    0
    Регистрация:
    27 июл 2003
    Сообщения:
    27
    Адрес:
    Belarus
    "А насколько сложно будет факторизовать 512-битное число для злоумышленников?"



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

    Ну а если у челов есть специализированная вычислительная система: кластер какой-нибудь навороченный + программное обеспечение написанное для этого, то может за пару месяцов и управятся... :)



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

    bogrus Active Member

    Публикаций:
    0
    Регистрация:
    24 окт 2003
    Сообщения:
    1.338
    Адрес:
    ukraine




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







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

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

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

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

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    Кстати snatch уже говорил , что и RSA-2048 ломали .





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

    bogrus Active Member

    Публикаций:
    0
    Регистрация:
    24 окт 2003
    Сообщения:
    1.338
    Адрес:
    ukraine
    Вот , ты в отпуске был :)
     
  11. volodya

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    bogrus



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

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    Самому интересно , т.к. если существует некое множество зашифрованных подписей удовлетворяющих одному ключу , то возможно что быстрее найти одну подпись из множества , чем факторизовать "ключ" ?



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

    flankerx New Member

    Публикаций:
    0
    Регистрация:
    2 июл 2004
    Сообщения:
    423
    Адрес:
    Moscow, Russia
    2volodya про RSA-2048.



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



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

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    Понятно. Согласен.
     
  15. snatch

    snatch New Member

    Публикаций:
    0
    Регистрация:
    27 июл 2003
    Сообщения:
    27
    Адрес:
    Belarus
    "...числа порядка 400 бит..."

    вот именно... :p



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

    Ну-ну... давай-давай... шутник... ;)

    Разве что на Cray X1 system какой-нибудь... Да плюс еще алгоритм факторизации оптимизированный понадобится...



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

    bogrus Active Member

    Публикаций:
    0
    Регистрация:
    24 окт 2003
    Сообщения:
    1.338
    Адрес:
    ukraine
    Ну вот например схема проверки , для регистрации проги нужно ввести 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 , где я гоню ?
     
  17. volodya

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    Если я правильно вкурил, то, конечно, FALSE. Ведь хеш-то не совпадет! Ведь MD5 считается! А при чем тут RSA?
     
  18. bogrus

    bogrus Active Member

    Публикаций:
    0
    Регистрация:
    24 окт 2003
    Сообщения:
    1.338
    Адрес:
    ukraine




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







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



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

    Funbit Member

    Публикаций:
    0
    Регистрация:
    13 апр 2003
    Сообщения:
    92
    Адрес:
    Russia
  20. volodya

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    bogrus



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



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