1024-битный шифр RSA взломают через пять лет

    Уже через пять-десять лет 1024-битный RSA-шифр будет взломан. С таким прогнозом выступил Арьен Ленстра (Arjen Lenstra), известный криптолог. Совсем недавно под его руководством был взломан эквивалент 700-битного ключа RSA. Арьен Ленстра считает, что в области распределённых вычислений в ближайшие годы можно ожидать существенного прогресса. Во-первых, процессоры становятся мощнее. Во-вторых, улучшаются математические алгоритмы поиска простых чисел-множителей.

    Арьен Ленстра рассказал об успешном эксперименте, в рамках которого было найдено два множителя 307-значного числа. Правда, это конкретное число (21039 – 1) специально тщательно подобрали так, чтобы оно легче поддавалось факторизации с помощью изобретённого Ленстрой метода «специального решета числового поля» (special number field sieve). При этом процесс занял 11 месяцев в сети из 300–400 компьютеров. В частности, шесть месяцев ушло на высеивание: общее время высеивания было эквивалентно ста годам работы Athlon64/Opteron [2.2GHz]. Решение полученной матрицы заняло 59 дней на 110 процессорах Pentium D [3.0GHz].

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

    via IDG News, Number Theory List
    Support the author
    Share post

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 62

      0
      Мы-то здесь все знаем, что теоретическая стойкость алгоритма - не вполне достаточный показатель стойкости к внешним воздействиям всей информационной системы, рассматриваемой вместе с "потребителями" и операторами :)

      И мы же здесь договорились, что будем рулить квантовыми компьютерами? Зачем нам очередные криптострашилки :)
      • UFO just landed and posted this here
          0
          Запрещает. Только насчет 128 бит я не совсем уверен. И, кажется, это только в США.
          • UFO just landed and posted this here
              0
              У нас ограничение только для информации не содержащей сведений, составляющих государственную тайну.
                0
                В России сейчас разрешен 256 закрытый / 512 открытый ключ (см ГОСТ Р 34.10 2001) хотя раньше можно было использовать 256 / 1024 (ГОСТ Р 34.10 94) но видимо его органам было сложно ломать, поэтому подрезали :)
                • UFO just landed and posted this here
                    0
                    Только всем класть на эти ограничения, ну кому нужно конечно.
                    • UFO just landed and posted this here
                • UFO just landed and posted this here
                    +1
                    чтобы "врагов народа" вычислять :)
                    0
                    если мне память не изменят, но не запрещает, а накладывает некоторые ограничения на испольование :)
                    ...далее следует список "ограниченных" стран..., с целью ...дальше перечень благородных целей, таких как борьба с терроризмом, наркотиками и т.д. и т.п...

                    и вроде далеко не на все системы...

                    >>Интересно, с какой целью?
                    да всё с той-же - суметь расшифровать при необходимости.

                    это не значит что SSL не защиащет, это значит что SSL обеспечивает относительную защиту законопуослушным гражданам. ну а тех кому есть что скрывать есть над чем зауматься ;)

                    З.Ы.: статье речь не про SSL, но вопрос про 128 касается именно его...
                      0
                      В РФ есть ограничения на использования шифрования. Знаю случай, когда дело дошло до суда, за то что контора использовала программу для шифрования, которая чем-то не устраивало органы.
                        0
                        не знал. теперь буду знать.
                      • UFO just landed and posted this here
                          +1
                          доступ к необходимым мощностям... я так думаю :)
                          • UFO just landed and posted this here
                              0
                              !это всего-лишь мое мнение, оно может не совпадать с действительностью...
                        0
                        это относится к симметричным системам.
                        с асимметричными история совсем другая, 1024бит — это вообще разумный минимум (пока)

                        вот еще, кстати, из википедии:
                        15360-bit RSA keys are equivalent in strength to 256-bit symmetric keys.
                          +2
                          Российское законодательство относит изготовление, распространение и обслуживание средств защиты информации, в том числе шифрсистем, к лицензируемой деятельности. Лицензии выдает ФСТЭК, а для средств используемых в государственной деятельности, также Техкоммиссия при Президенте. Законодательно установленных ограничений на длины ключей нет, но какими будут условия лицензии... известно, только сами знаете кому. В личных целях млжно использовать шифрсистемы любых типов и любой сложности. Дискуссия по этому повожу уже была.
                          • UFO just landed and posted this here
                              0
                              Спасибо, буду знать!
                            0
                            RSA — это система шифрования с открытым ключом, почему в тэгах наоборот? :)
                              0
                              Открытым ключом зашифровывают текст для конкретного человека, чтобы тот мог расшифровать его с помощью своего закрытого ключа. Это и есть главаная идея систем шифрования с открытым ключом.
                              +2
                              Арьен Ленстра рассказал об успешном эксперименте, в рамках которого было разложено на два множителя 307-значное число.
                              Там три множителя. Хотя один из 7 десятичных знаков, а другие два — 80 и 277.

                              2^1039-1 = p7*p80*p227

                              Первый делитель p7 был уже давно известен.

                              Для высеивания было затрачено 6 календарных месяцев. Были задействованы различные компьютеры и кластеры в EPFL, NTT и в университете города Бонн. Общее время высеивания эквивалентно 100 лет работы Athlon64/Opteron [2.2GHz].

                              Решение полученной матрицы заняло 59 дней на 110 процессорах Pentium D [3.0GHz]. Календарное время составляет 69 дней, но были периоды, когда вычисления не производились, поэтому общее время работы эквивалентно 59 дням непрерывных вычислений.

                              http://listserv.nodak.edu/cgi-bin/wa.exe…
                                0
                                Круто. Добавил в текст, спасибо.
                                  +1
                                  Вообще-то к стойкости криптосистем это имеет достаточно слабое отношение, так как простые делители чисел Мерсенна (2^p - 1) имеют весьма специальный вид и искать их гораздо легче, чем простые делители произвольного числа.
                                  –1
                                  Всем, кто увлекается криптографией, советую почитать "Цифровую крепость" Брауна.
                                    0
                                    Всем, кто увлекается витрувианским человеком и теорией заговора, читать "Код даВинчи" ;)

                                    Я прочитал "Ангелы и демоны" и "К дВ" Брауна, первые лучше были. За "Крепость" браться не хочу, т.к. Демоны интересней.
                                      +1
                                      А лучше "Криптономикон" Стивенсона. Там реальные шифры и листинги исходников даже есть. Брюс Шнайер помогал.
                                        0
                                        Именно, что "увлекается" :) Я читал, уже забыл, но ощущение "автор не в теме" осталось ;)
                                        0
                                        опасность чересчур преувеличена. Уже полтора года назад заявили о существовании md5 коллизий (возможности создания двух строк с одинаковыми md5 за достаточно короткое время), в недавнем прошлом дело дошло до быстрого алгоритма для таких операций (несколько секунд на настольном компе), но md5 пока еще остается достаточно надежной весчью.

                                        Это я к тому, что от теоретических выкладок и единичных успехов до практического применения - большой разрыв. Не думаю, что через 10 лет станет так уж просто взламывать 1024-битные ключи
                                          0
                                          Криптостойкость RSA-1024 - 3*10^11 MIPS-лет. Intel Core Duo E6600 - 22100 MIPS. Итого для взлома в течении года RSA-1024 нужно 13 млн компьютеров, что составляет немногим более 1% общего числа пользователей Интернет. Объединяем их в грид и, так как это вероятностный процесс, в среднем через полгода 100000$ у нас в кармане. Чтобы привлечь клиентов, организуем партнерку, где 10К получает собственно взломавший, а по 1К его 10 партнеров. Чистая прибыль 80 штук.
                                            0
                                            RSA factoring chellenge отменено. Больше призы не выдаются.

                                            http://www.rsa.com/rsalabs/node.asp?id=2…
                                            http://www.rsa.com/rsalabs/node.asp?id=2…
                                              +1
                                              Чегтовски жаль. А я уже поделил эти 80 штук.
                                              0
                                              Вот возьми и найди 13 миллионов человек с кор2дуо Е6600 согласных в течении года жечь электроэнергию и не выключать компьютеры. Интересно какое количество энергии будет затрачено?

                                              Моё предложение - закупаем Cell (по моему один проц стоит 600 баксов) в количестве десяти тыщ штук, обьединяем, денег много не получим зато получим самый производительный суперкомпьютер на планете :) 10 млн баксов - пустяки :)
                                                0
                                                Ну сломали вы этот код и что дальше? За год информация которая была зашифрована скорее всего уже будет известна из открытых источников.
                                                  0
                                                  Ну и я вот думаю что смысла нет.
                                                    0
                                                    Дело в том, что RSA, а точнее RSA-PSS активно используется для реализации цифровой подписи. Ключи, например в банковской сфере, могут не меняться годами. Я думаю нет необходимости объяснять, какие преимущества может дать знание закрытого ключа для организации подложной подписи.
                                                      0
                                                      Ключ любой сложности необходимо регулярно менять. Лучше всего менять ключ для каждой транзакции. Если этого не делать регулярно, то ничто не поможет.
                                                        0
                                                        Совершенно логично, но это так называемые сеансовые ключи, использующие симметричные алгоритмы. Обмен ими осуществляется с помощью алгоритмов с открытым ключом. В свою очередь депонирование открытого ключа требует невиртуальной аутентификации, так что менять их столь, часто, особенно в схемах без единого центра депонирования, не реально.
                                                        0
                                                        Еще большие преимущества даст успешная вербовка банковского админа. "И по деньгам дешевле".
                                                        • UFO just landed and posted this here
                                                            0
                                                            Ну так года хватит. А вот мне всегда было интересно, как они депонируют открытые ключи - на броневике развозят по банкам? :)
                                                            • UFO just landed and posted this here
                                                                0
                                                                Я имел в виду банки. Яндекс - это несерьезно. Обновление ключей через интернет поддается атаке man-in-the-middle.
                                                                • UFO just landed and posted this here
                                                      0
                                                      рассчитай вероятность того, что 1% пользователей будет объединен в сеть (например, с помощью вируса)
                                                      0
                                                      Просто — нет. Но вполне реально для тех, кто имеет необходимые вычислительные мощности и квалифицированных специалистов.
                                                        0
                                                        Кстати если учесть закон Мура, то через 10 лет для вскрытия RSA-1024 в среднем, в течении полугода, нужно будет всего 420 тыс компьютеров, объединенных в грид. Для сравнения к известным серверам Осла за раз подключается больше народу.
                                                          0
                                                          этот самый закон замечательно работал лет пять назад. Сейчас тенденция уже другая, а не уверен, что производительность отдельных компьютеров продолжает расти теми же темпами
                                                        0
                                                        Будут использовать ассиметричное шифрование основанное на эллиптических кривых. Там размеры ключа существенно меньше по сравнению с RSA при схожей криптостойкости (точно не помню конкретных цифр, но примерно на порядок отличаются).
                                                        Думаю через несколько лет это получит достаточно широкое распрастранение.
                                                          0
                                                          Нельзя ли ссылку не на эллиптические кривые, а на ассиметричное шифрование основанное на эллиптических кривых?
                                                          • UFO just landed and posted this here
                                                                0
                                                                А где-нибудь подобные технологии дальше накладывания ЭЦП ушли? ЭЦП неинтересно.
                                                                  0
                                                                  ЭЦП, обмен ключами, аутентификация, широковещательный криптообмен, разделение секрета и много другое... Могу порекомендовать книгу Брюса Шнайдера "Прикладная криптография": очень широкий охват темы, популярность и особенности реализации алгоритмов.
                                                                  (Этот текст других прошу не читать - pdf 3.41Мб)
                                                                  • UFO just landed and posted this here
                                                                      0
                                                                      Ну вот примерно это я и имею в виду, ничего революционного. Если будет прирост производительности на два порядка, тогда, очевидно, это простимулирует практические применения ранее не использовавшихся широко схем.
                                                              0
                                                              вспомнил советских разведчиков и одноразовые блокноты.
                                                              p.s. спасибо за статью. да и комментарии тоже познавательные.
                                                                0
                                                                Почитайте "Криптономикон", про одноразовые блокноты :))) гарантии случайности нет.
                                                                0
                                                                Ну и чего? Есть успехи?

                                                                Only users with full accounts can post comments. Log in, please.