АНБ работает над созданием квантового компьютера для взлома любого типа шифрования (но пока далеко от успеха)

    image

    АНБ финансирует разработку квантового компьютера, позволившего бы ему взломать практически любое шифрование, используемое сегодня, пишет The Washington Post. Пока что однако нет никаких свидетельств того, что агентству удалось продвинуться дальше, чем другим исследователям, которые над этим работают.

    Благодаря документу, переданному Эдвардом Сноуденом, стало известно об исследовательской программе «Внедрение в сложные цели» с бюджетом 79,7 млн долларов, одной из целей которой является создание квантового компьютера, который может быть использован для криптографии. Согласно документу, большая часть исследований ведётся в физической лаборатории Мэрилендского университета. Как далеко продвинулась работа, в документе не раскрывается.

    Основной принцип квантовых вычислений известен как «квантовая суперпозиция» — идея о том, что объект одновременно существует во всех состояниях. Если классический компьютер использует двоичные биты, которые являются либо нулями, либо единицами, то квантовый компьютер использует квантовые биты, или кубиты, являющиеся одновременно нулём и единицей, что значительно повышает вычислительную мощность.

    В то время как классический компьютер, какой бы мощный он ни был, должен делать одно вычисление за другим, квантовый компьютер может не проводить расчёты, которые не являются необходимыми для решения проблемы. Это позволяет ему приходить к правильному ответу намного быстрее и эффективнее.

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

    Так, квантовый компьютер мог бы легко взломать широко используемый алгоритм RSA, основанный на вычислительной сложности задачи факторизации больших целых чисел. В 2009 году компьютерные учёные смогли факторизовать 768-битное число, но им потребовалось для этого почти два года и сотни компьютеров. Учёные подсчитали, что для взлома 1024-битного ключа шифрования, который обычно используется для онлайн-транзакций, потребуется в 1000 раз больше времени.

    Однако большой квантовый компьютер теоретически может взломать 1024-битное шифрование гораздо быстрее. Некоторые ведущие интернет-компании уже переходят на 2048-битные ключи, но даже те могут быть уязвимы для быстрой расшифровки с помощью квантового компьютера.

    Тем не менее, даже если до появления квантового компьютера с достаточной мощностью для взлома сложного шифрования пока что далеко, то как говорит профессор Университета Южной Калифорнии Даниэль Лидар: «Ирония квантовых вычислений заключается в том, что если вы можете себе представить создание квантового компьютера, который может взломать шифрование, в ближайшие несколько десятилетий, то вам нужно беспокоиться прямо сейчас».
    Поделиться публикацией

    Комментарии 39

      –7
      Пилите, Шура, пилите, она — золотая…
        +9
        С помощью такой технологии все нынешние системы шифрования с открытым ключом могли бы быть взломаны

        Но ведь есть системы шифрования, для которых не придумали квантового алгоритма взлома, почему же все?
          +2
          Да и название:
          любого типа шифрования
          Во первых — для взлома систем с открытым ключом, во вторых — не любых, а в лучшем случае распространенных.
            0
            Я попытался пересказать то, о чём прочёл в Вашингтон-посте; если вы разбираетесь в теме, то не могли бы, пожалуйста, вкратце описать, какие есть ещё?
              0
              Насколько я понимаю, эллиптическая криптография решит проблему. Хотя, может, я и ошибаюсь
                +4
                Ошибаетесь. Эллиптическая криптография надежней при той же длине ключа, но все так же подвержена вариации алгоритма Шора для дискретного логарифмирования. Есть другие алгоритмы, для которых на данный момент нет эффективных квантовых алгоритмов. Мне кажется наиболее близкой к практическому применению является криптография на решетках, но есть и другие варианты: en.wikipedia.org/wiki/Post-quantum_cryptography.
                  0
                  И правда. Спасибо
                    +4
                    Кстати, криптография на решетках еще перспективна в плане гомоморфного шифрования.

                    Если вкратце — можно производить операции над зашифрованными данными не узнавая самих данных. Например, вам дают зашифрованный запрос в БД, вы его выполняете, отдаете зашифрованный ответ, который клиент расшифровывает. При этом вы не знаете ни что запросил клиент, ни что он получил в ответ.

                    Но до такого еще далеко, пока производительность оставляет желать лучшего, да и аудита бы побольше, слишком уж новая разработка.
                    +1
                    Не решит, т.к. алгоритм Шора [94] достаточно универсален:

                    www.math.uwaterloo.ca/~amchilds/teaching/w08/l03.pdf
                    It is straightforward to use Shor’s algorithm to solve the discrete log problem for an elliptic curve over F_p in time poly(log p).… Ironically, Shor’s algorithm takes a comparable number of steps for both factoring and discrete log (regardless of the group involved)


                    arxiv.org/pdf/quant-ph/0301141v2.pdf
                    It turns out that for this problem a smaller quantum computer can solve problems further beyond current computing than for integer factorisation. A 160 bit elliptic curve cryptographic key could be broken on a quantum computer using around 1000 qubits while factoring the security-wise equivalent 1024 bit RSA modulus would require about 2000 qubits.


                    Спасение вроде бы есть:

                    logic.pdmi.ras.ru/~sergey/teaching/crypto10/12-quantum.pdf
                    В результате получается квантовое решение задачи дискретного логарифма. Эллиптические кривые не спасают — для любой коммутативной группы работает, нужно только умножать уметь.

                    Мы взломали всю коммутативную криптографию. Что делать? Один ответ — строить квантовую криптографию. Другой ответ — строить некоммутативную криптографию.


                    Также есть NTRUEncrypt, которая строится на проблеме, для которой не работает алгоритм Шора и неизвестно, будет ли найден квантовый алгоритм.
                0
                1024 бита — смешно. Почему до сих пор люди используют такие короткие ключи в протоколах? Из-за того, что использование сильных ключей запрещено законом, как правило? Но есть некоммерческие варианты использования, и там тоже короткие ключи.

                Если не ошибаюсь (поправьте, если да), Шнайер в „Прикладной криптографии“ ещё десять лет назад рекомендовал при асимметричном шифровании, основанном на простых числах, 2048 бит для личных целей и 4096-8192 для корпоративных. Потому что уже тогда было ясно, что надо запасаться впрок, что факторизация будет улучшаться, причём она может улучшаться внезапными скачками при появлении новых алгоритмов и компьютерных мощностей.
                  +2
                  А еще лучше переходить на криптографию на эллиптических кривых. Она надежней, чем RSA с идентичной длиной ключа. Но квантовым атакам подвержена ничуть не меньше.
                  +6
                  Кстати, Telegram, если ты меня сейчас читаешь, самое время подудвоить длину своего RSA, на всякий случай.

                  Enlarge your key!
                    +2
                    Удивительно как устроено человечество, что большинство разработок делается ради уничтожения друг друга или власти. Можно голову сломать, если только подумать какой прорыв сделает квантовый компьютер, а разговоров то больше всего о взломе шифров. И замечу, что речи о спасении от четвертого рейха с энигмой v2.0 тоже не идет.
                      +3
                      Зашёл сюда, чтобы написать такой же комментарий :)
                      Компьютер для расшифровки военных сообщений во время Второй Мировой, компьютерные сети и интернет во время Холодной Войны для надёжной связи на случай атомной войны, квантовый компьютер для шпионажа во имя войны с терроризмом — в мирном русле мы развиваться не умеем :)
                        0
                        fit4life.ru/your/78-evolucia.html

                        ЕСТЕСТВЕННЫЙ ОТБОР ПРОИСХОДИТ ВЕЗДЕ, ГДЕ ЕСТЬ ОГРАНИЧЕННЫ РЕСУРСЫ потому что ограниченные ресурсы меняют окружающие условия. А когда меняются окружающие условия, происходит приспособление к ним. И сильные поедает слабого.

                        Так как мы живем в материальном мире ограниченном размерами планета земля, то ЕСТЕСТВЕННЫЙ ОТБОР ИДЕТ ВО ВСЕХ СФЕРАХ (социальных, политических, экономических, научных и т.д.). Абсолютно везде идет борьба между государствами, экономиками, доктринами, религиями и т.д… Везде… Кругом… По всюду… Даже сейчас, когда вы читаете это вы сделали выбор (читать ли это, или что то другое, поверить мне или не поверить). Что является ресурсом в данном случае? Как что? Ваше внимание конечно и ваша вера. А это очень ценный ресурс, который только идиоты пытаются измерить деньгами. По сути он бесценный… Во всяком случае он самый важный, потому что то во что вы верите определят то, что вы будите делать.
                          0
                          Недавно читал что развитие производительности PC просходило благодаря любителям 3д игр, думаю вообще говоря не мало таких примеров когда развите толкали не военные, например средства связи развивались и миниатюризировались благодаря потребителям, которым сначала дали возможнось позвонить откуда угодно по мобилке, а потом в angry bird поиграть на 8 ядерном планшете. По моему взгляд что все из-за разработки для военных это несколько однообразный взгляд сейчас и срабатывает на такие военные новости. Я думаю что тот же самый квантовый компьютер пытаются делать разные лаборатории, не обязательно по заказу военных.

                          > Можно голову сломать, если только подумать какой прорыв сделает квантовый компьютер

                          Кстати, какой прорыв сделает квантовый компьютер кроме шифров?
                            +2
                            Кстати, какой прорыв сделает квантовый компьютер кроме шифров?

                            Моделирование химических соединений и расчеты в физике элементарных частиц. Сейчас химические соединения моделируются полу-эвристическими алгоритмами, которые имеют большую трудоемкость и низкую точность.
                              0
                              Спасибо за ликбез. Прикольно, расчеты в физике элементарных частиц с помощью самих элементарных частиц.
                                0
                                С помощью счетных машин считали ядерную бомбу, с помошью компьютера считали водородную бомбу, боюсь представить, что будут считать на квантовом.
                          0
                          Думаю, когда изобретут квантовый компьютер или ещё что либо, что приумножит вычислительные мощности в десятки раз никто не станет сразу об этом говорить, скорее уж используют мощности для майна криптовалюты что бы отбить стоимость исследований.
                            +2
                            Майнить её не смогут, а вот взломать чужие кошельки — запросто.
                            0
                            Его развивают уже последние 20-ть лет, а мечтают о нём ещё дольше, но толку пока мало…
                              0
                              Собственно, исследования в этой области финансируются давно, и не только АНБ, и не только из-за криптографии. Ну пусть документ указывает на конкретный университет и конкретную сумму, что в этом такого сенсационного? (вопрос не к автору поста, а просто размышления о всей этой шумихе)
                                +2
                                Иногда новости — это просто новости, а не сенсации.
                                –11
                                Новости про АНБ подустали уже. Все на одно лицо: немного бояна из любой области, +АНБ, +Сноуден = Шок, Скандал, Мы все под колпаком.

                                Ожидаем в ближайшем будушем:
                                АНБ разрабатывает квадрокоптеры нового поколения для слежки за всеми
                                АНБ разрабатывает аккумуляторы нового поколения для квадрокоптеров нового поколения.
                                АНБ разрабатывает альтернативу биткойну для финансирования разработки аккумуляторов и квадрокоптеров.
                                Естественно всё подтвердил Сноуден.
                                  +1
                                  Простите, а вы статью то читали?
                                  –4
                                  До квантовых компьютеров ещё далековато всё же. А как они появятся, так и сразу шифровальщики пару килобайт на ключи накинут.
                                    +3
                                    А раньше сюжет «Цифровой крепости» Брауна мне казался шуткой.
                                      +1
                                      Шуткой там по сюжету оказался абсолютно не взламываемый алгоритм, он вероятно и останется шуткой
                                        +2
                                        Вообще-то (спойлер)
                                        По сюжету его там и не было, хотя абсолютно не взламываемый алгоритм в реальности таки есть.
                                        +1
                                        Несмотря на многие технические промахи (серьезно, АНБ даже не догадалась изолировать компьютер, который запускает подозрительный код от остальной сети со сверхсекретными данными?) книжка весьма интересна. Любопытно, изменилась бы концовка в свете недавних событий? Ведь в романе АНБ — хороши парни, несмотря на наличие суперкомпьютера способного вскрывать шифры.
                                          +1
                                          Будем ждать продолжения :) С персонажем, бежавшим в РоссиюВосточную Европу, тайными заговорами корпораций и квантовым компьютером, обретающим разум…

                                        +1
                                        Думаю, что с ростом вычислительных мощностей и сменой алгоритмов работы вычислительных машин появятся и новые возможности в криптографии, так что по прежнему будет некий паритет у желающих взломать шифры и тех кто шифрует данные.
                                        PS: надеюсь это не самоуспокоение.
                                          +4
                                          Я тут опасаюсь ситуации, при которой квантовые компьютеры будут из-за своей сложности доступны только правительствам и крупным корпорациям. Исчезнет простота и равноправие в криптостойкости будь ты хоть крупная компания, хоть безымянный Вася со стареньким компом.
                                            +4
                                            Может как-то не так сформулировал? Первое время, пока квантовые компьютеры будут требовать жидкий гелий/унобтаниум или еще что-то для работы, их смогут себе позволить очень немногие. И сразу получат преимущество над всеми другими. Паритет щита и меча будет нарушен. Кстати, под дешифровку попадет огромный пласт документов, зашифрованных в «доквантовую» эпоху. С ними уже ничего не сделаешь.
                                              0
                                              Так под «секретность» попадают документы только на время в любом случае. И документы «доквантовой» эпохи к моменту построения достаточно мощных КК через 20-30 лет уже устареют, а сейчас должны уже они шифроваться с расчетом на КК. Хотя не знаю как в США, а у нас с этим делом развал как и везде: больше показухи, чем реальной защиты грифами и пр.
                                                0
                                                Может, узнаем, кто убил Кеннеди!
                                            • НЛО прилетело и опубликовало эту надпись здесь
                                                +4
                                                >> но пока далеко от успеха
                                                А они точно сообщат когда достигнут успеха?

                                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                Самое читаемое