пришел звиздец RSA

Тема в разделе "WASM.CRYPTO", создана пользователем volodya, 17 фев 2007.

  1. SWR

    SWR New Member

    Публикаций:
    0
    Регистрация:
    11 май 2006
    Сообщения:
    226
    Адрес:
    Russia
    Так и делают (Есть спец процессора которое это реализуют). Это проще и быстрей.
    А все алгоритмы поиска простых чисел нужны чисто для иследований.

    Для практического применения я прогу не писал. Я иследовал распределение простых чисел (невроде тервера)
    Довольно интересная гистограмма получается если строить её по расстояниям.

    Ненадо сравнивать обычный комп и квантовый.
    Полно примерев на которых плохо работает квантовый и на оборот для булевых
     
  2. ECk

    ECk Member

    Публикаций:
    0
    Регистрация:
    9 апр 2004
    Сообщения:
    454
    Адрес:
    Russia
    Разности между простыми числами тебе для нахождения множителя не помогут (особенно на значениях реальных ключей использующих RSA - 512-1024 бита).
    Теперь, условно согласимся что для 2^32 тебе хватит 193 Мб - значит для 2^33 тебе уже нужно как минимум 386 Мб - а для 256-512 бит (размер множителя реального ключа) соответственно 193*2^(224-480) Мб памяти (что нереально ни для спецпроцессоров, ни для всех компьютеров Земли в настоящее время).
    Насчет спецпроцессоров - "не надо песен" (максимум из устройств такого рода - Twinkle, теоретически разработанный в Израиле, да и D. Bernstain с его предположениями по ускорению поиска зависимостей для GNFS путем аппаратных решений) - они юзают ранее упомянутый мной алгоритм GNFS и никакого перебора (и несмотря на свою "аппаратность", для Twinkle нужен ГОД для факторизации 512 битного числа).
     
  3. SWR

    SWR New Member

    Публикаций:
    0
    Регистрация:
    11 май 2006
    Сообщения:
    226
    Адрес:
    Russia
    Для 128 еще можно таблицу хранить (самые распостроненные ключи)

    В остальном я согласен (чем больше число тем больше расстояние -> нужно более 1 байта для его хранения)

    Вопрос:
    Наскока качественно современные реализации RSA выбирают P и Q?

    P.S. Думаю у спецов есть чето помощней если они пропустили этот алгоритм как стандарт. (даже наша гос. противится сложным шифрам неговоря уж про США).
     
  4. ECk

    ECk Member

    Публикаций:
    0
    Регистрация:
    9 апр 2004
    Сообщения:
    454
    Адрес:
    Russia
    P & Q при выборе являются safeprime (P-1)/2 = prime, (Q-1)/2 = prime.
    эээ... ты считаешь, что 128 битное шифрование означает 128 битные ключи???
    Для справки, 128 битный ключ шифрования используется в симметричных шифрах (в которых он передается один раз при установке соединения, зашифрованный ключом RSA гораздо большим чем размер ключа для симметричного шифрования в рамках сессии), так что найти ключ RSA 128 бит тебе не удастся (и зачем городить огород - числа 128мибитные легко раскладываются в Maple, Mathematica, CrypTool), только это не RSA модули.
     
  5. crypto

    crypto Active Member

    Публикаций:
    0
    Регистрация:
    13 дек 2005
    Сообщения:
    2.533
  6. PageFault

    PageFault New Member

    Публикаций:
    0
    Регистрация:
    5 мар 2007
    Сообщения:
    31
    Интересно, где это они самые распостраненные? Ни в одном нормальном решении (не считая глючных ламерских поделок) я никогда не видел использования rsa с ключем меньше 512 (типичные размеры 1024-4096).

    Так что SWR, стены тут будет мало, надо еще и йаду...
     
  7. flankerx

    flankerx New Member

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

    но, справделивости ради, нужно сказать что такая каша не только у SWR в голове... Trillian 3 использует DH на 128 бит (что ломается сложнее чем RSA-128 но все равно ломается), в схемах регистрации некоторых программ используетя RSA-128... и во всех случаях люди думают что 128 бит - это секьюрно )


    Про брутфорс RSA - это глупость. Для RSA-512 нужно 2^256 операций - нереально даже для "правительственных спецвычислителей".
     
  8. SWR

    SWR New Member

    Публикаций:
    0
    Регистрация:
    11 май 2006
    Сообщения:
    226
    Адрес:
    Russia
    PageFault
    Еще ясельки незакончил?

    flankerx
    Я протоже, что многие досих пор думают что 128 - надежно. (очень много таких решений (например для быстроты шиврования )) (не для смешанных шифрах)
    Недавно про винт читал который как раз шифрует 128 битным RSA алгоритмом.

    >>Про брутфорс RSA - это глупость. Для RSA-512 нужно 2^256 операций - нереально даже для "правительственных спецвычислителей".
    Лучше промолчу.
     
  9. ECk

    ECk Member

    Публикаций:
    0
    Регистрация:
    9 апр 2004
    Сообщения:
    454
    Адрес:
    Russia
    SWR
    Так называемые тобой "Смешанные шифры" имеют вполне известное и пожалуй, знакомое всем криптологам-криптографам название - RC4, RC5, RC6 и придуманы соавтором RSA (Роном Ривестом из MIT - http://www.rsa.com/rsalabs/node.asp?id=2512). Так что насчет скорости ты не прав (модулярная эскпоненциация по модулю 128 бит гораздо медленнее шифрования симметричным шифром с помощью ключа в 128 бит).
     
  10. ECk

    ECk Member

    Публикаций:
    0
    Регистрация:
    9 апр 2004
    Сообщения:
    454
    Адрес:
    Russia
    Более конкретно - реализации SSL используют эти "смешанные" шифры
     
  11. PageFault

    PageFault New Member

    Публикаций:
    0
    Регистрация:
    5 мар 2007
    Сообщения:
    31
    Ты с какого дурдома сбежал, убогий?

    Ссылку на этот бред пожалуйста.

    Дада. Молчи, может за умного сойдешь.

    P.S. стену советую выбирать бетонную
     
  12. SWR

    SWR New Member

    Публикаций:
    0
    Регистрация:
    11 май 2006
    Сообщения:
    226
    Адрес:
    Russia
    Смешанные - это когда симметричный клуч передается зашифрованный более медленным не семетричным(например RSA) и дале инфа шифруется им
    , а RC4, RC5, RC6 это отдельные алгоритмы никаким боком тута не косающиеся. Обычно с рса используют дес(к).

    P.S. Насчет скорости я мел ввиду, что 128 быстрее 256 и тд. (от этого его используют в харде и динамич. шивр. (так авторы прог пишут) ) Тонкостей реализации я незнаю (в винте).
     
  13. Scratch

    Scratch New Member

    Публикаций:
    0
    Регистрация:
    1 янв 2005
    Сообщения:
    161
    SWR
    Кури меньше.
    http://www.seagate.com/docs/pdf/marketing/po_momentus_5400_fde.pdf
     
  14. ECk

    ECk Member

    Публикаций:
    0
    Регистрация:
    9 апр 2004
    Сообщения:
    454
    Адрес:
    Russia
    Насчет винта с RSA - считай сам:
    1. Запись (то есть, возведение в степень e, равную открытому ключу, небольшому) - время T1
    2. Чтение (то есть, возведение в степень d, равную закрытому ключу, порядка N) - время T2
    Отношение T2:T1 ~ log2(N):log2(e)
    Теперь вопрос - кому на х. такой винт нужен?
     
  15. Scratch

    Scratch New Member

    Публикаций:
    0
    Регистрация:
    1 янв 2005
    Сообщения:
    161
    :off:
    походу только его изобретателю )
     
  16. flankerx

    flankerx New Member

    Публикаций:
    0
    Регистрация:
    2 июл 2004
    Сообщения:
    423
    Адрес:
    Moscow, Russia
    это разумно =)

    RC4 - обычный потоковый шифр,
    RC5, RC6 - обычные блочные шифры.
    Никакой "смешанности" в них нет.

    Насколько я понимаю, речь идет о т.н. hybrid encryption, когда данные шифруются симметричным алгоритмом на случайном ключе, а сам этот случайный сеансовый ключ зашифровывается на открытом ключе получателя и передается абоненту.

    SWR
    хватит уже нести чушь про 128-битный RSA. Или примеры реальные давай (а не "в каком-то харде, про который я где-то читал и вообще не в курсе"), или иди учить матчасть.
     
  17. SWR

    SWR New Member

    Публикаций:
    0
    Регистрация:
    11 май 2006
    Сообщения:
    226
    Адрес:
    Russia
    flankerx
    вникни в суть потом пиши.

    ECk
    Чето я непонял про ответ с P Q
    Просто по алгоритму эти 2 числа (я так понял) обычно берут близкими -> их разряднасть в 2 раза меньше и для
    перебора нужно меньше пространство простых чисел
    например для 64 хатитит перебрать все числа от 0 до uint32(-1) (если не отходить от правил).

    PageFault
    Иди на другие форумы разводи.
    Не пиши ответ.
     
  18. ECk

    ECk Member

    Публикаций:
    0
    Регистрация:
    9 апр 2004
    Сообщения:
    454
    Адрес:
    Russia
    SWR
    Посмотри в гугле определение safeprime.
    Если числа таковыми не являются, их легко разложить с помощью методов P+1, P-1.
    Если являются таковыми - то только с помощью xS (QS,SIQS,MPQS,SNFS,GNFS) - короче, аглоритмами с решетом (квадратичное решето, самоинициализирующееся квадратичное решето, мультиполиномиальное квадратичное решето, особое решето числового поля, общее решето числового поля). Вообще, все алгоритмы описаны на www.mathworld.wolfram.com
     
  19. PageFault

    PageFault New Member

    Публикаций:
    0
    Регистрация:
    5 мар 2007
    Сообщения:
    31
    SWR
    Ты мне запрещаешь писать ответы? Да пошел ты (очень далеко...).
    Ты видимо тут считаешь себя самым умным. Так вот, таких как ты пора стрелять, чтобы они не отравляли мир своей тупостью.
    Если ты говоришь о легко ломаемом rsa, то докажи свои теории на практике. Вот тебе ключик в 2 раза меньший, чем обычно реально применяют. Традиционным GNFS он раскладывается на крутейшем core duo за 6 лет. Но ты авось сделаешь быстрее (самый умный ведь).

    7E81A05B6D8974362B0645541524163439B2169221C4994734F8AADAC313406C8121B1E5AE23
    E8701F000503B23FF8BEFC2F26123EC62E95066B82C01BC69131
     
  20. crypto

    crypto Active Member

    Публикаций:
    0
    Регистрация:
    13 дек 2005
    Сообщения:
    2.533
    Оффтоп
    По-моему, назрела необходимость добавления в форум темы "Ринг" (как у Соловьева) :)