Факторизация 400 разрядного числа будет выполняться квантовым компьютером за какой период
Самый мощный в мире на сегодняшний день суперкомпьютер "Фугаку" (Япония) способен производить 400 квадриллионов операций в секунду. Но для квантового компьютера (КК) подобная невообразимая скорость - все равно что бег черепахи с препятствиями. Он "думает" в миллиарды раз быстрее. Как такое возможно? И что это за восьмое чудо света - компьютер, напичканный транзисторами, в роли которых выступают. атомы?
Руслан Юнусов в квантовой лаборатории: Сейчас нажму кнопку - и появится гомункул, не верите? Фото: Олег Кармаза
Об этом рассказывает руководитель проектного офиса по квантовым технологиям госкорпорации "Росатом" и глава недавно созданной в России Национальной квантовой лаборатории Р. Юнусов.
- Руслан Рауфович, сейчас в мире происходит гонка, которую большинство ученых сравнивает с послевоенными "атомной", "космической" и "лунной" гонками. При этом миллионы людей о ней даже не догадываются. Потому, что речь идет о "квантовой" гонке, а квантовый мир - самая серьезная и фундаментальная область физики, и посвящены в нее немногие. Кто первый создаст универсальный компьютер на квантах - это сейчас вопрос вопросов. 10 самых продвинутых научных центров в США, Китае, Германии, Японии стремятся обогнать друг друга в конструировании, по сути, холодильника высотою 2 метра, внутри которого расположен один-единственный чип размером с ноготь. При этом одни ученые, среди которых немало нобелевских лауреатов, утверждают, что с помощью КК мы вполне способны разгадать большинство тайн мироздания, а другие уверяют, что потолок КК - это расшифровка любой засекреченной информации и создание любых, самых сложных и чудотворных лекарств. Где правда?
- Я однозначно отношу себя к первой группе. Компьютер, использующий в работе законы квантового мира, а они совсем не такие, как в окружающей нас действительности: там все мизерное, кругом лишь атомы, фотоны, ионы - кванты, одним словом - так вот подобный компьютер нам стопроцентно расскажет, кто мы такие во Вселенной, откуда появились, как была создана она сама.
- Вот это вряд ли. Я, будучи студентом, наткнулся однажды на любопытный фантастический рассказ. В нем люди придумали совершенный искусственный разум, и оператор с надеждой спрашивает его: "Есть ли Бог?" Разум отвечает: "Теперь есть". После чего оператор сгорает в электрическом разряде.
Все-таки как была создана Вселенная и кем она была создана - вопросы разного порядка. На первый ответить можно, на второй вряд ли. Он, мне кажется, так и останется лишь вопросом веры.
8. Навыки решения проблем
Квантовые компьютеры могут запускать классические алгоритмы, однако для получения эффективных результатов они используют алгоритмы, которые кажутся изначально квантовыми, или используют некоторые особенности квантовых вычислений, такие как квантовое запутывание или квантовая суперпозиция.
Неразрешимые проблемы классов остаются неразрешимыми в квантовых вычислениях. Что делает квантовый алгоритм увлекательным, так это то, что они смогут решать проблемы быстрее, чем классические алгоритмы. Они могут решить задачу коммивояжера за считанные секунды, что занимает 30 минут на обычных компьютерах.
Более того, квантовый компьютер может помочь обнаруживать далекие планеты, осуществлять точное прогнозирование погоды, раньше выявлять рак и разрабатывать более эффективные лекарства, анализируя данные секвенирования ДНК.
10. Не все может быть сделано быстро
Хотя квантовые компьютеры находят наиболее оптимальный способ решения проблемы, они используют некоторые основные математические принципы, которые ваш персональный компьютер использует ежедневно. Это относится к базовой арифметике, которая уже хорошо оптимизирована.
Нет лучшего способа добавить набор чисел, чем просто сложить их. В таких случаях классические компьютеры столь же эффективны, как квантовые компьютеры.
6. Почему сложно построить квантовые компьютеры
Проблема с квантовым компьютером - стабильность. Оказывается интерференция, любой вид вибрации расстроит вибрацию атомов, создавая ерунду. Электроны в квантовой механике ведут себя как волны и описываются волновой функцией. Эти волны могут мешать, вызывая странное поведение квантовых частиц, и это называется декогеренцией.
9. ИИ начало игры
Искусственный интеллект находится в начальной фазе. Современный продвинутый робот может входить в комнату, распознавать материал, форму и движущиеся тела, но ему не хватает факторов, которые делают их по-настоящему умными. Квантовые компьютеры намного лучше в области обработки информации - с 300 битами мы сможем отобразить всю вселенную.
Квантовые компьютеры смогут экспоненциально ускорить скорость машинного обучения, сократив время с сотен тысяч лет до нескольких секунд.
Для измерения расстояния между двумя большими векторами размером 1 зеттабайт обычному компьютеру с тактовой частотой ГГц потребуются сотни тысяч лет. В то время как квантовый компьютер с тактовой частотой ГГц (если он будет построен в будущем) займет всего лишь около секунды после того, как векторы запутаются с вспомогательным кубитом.
Чаша Грааля
- Известный итальянский ученый Томмазо Каларко, с которым сотрудничает ваша лаборатория, заявил, что никто в мире до сих пор не знает, как построить универсальный КК. Мы, дескать, даже не можем нормально транспортировать атомы. Руководитель квантовой лаборатории в США, в Гарварде, Михаил Лукин, выпускник, кстати, нашего Физтеха, и профессор Кристофер Монро из университета Мэриленда, напротив, уверены, что он появится в ближайшие 10 лет. Ваш прогноз?
- В ближайшие три года будут созданы прототипы КК, перешагнувшие рубеж в тысячу кубит. Тысячные кубитники намереваются сделать тот же Миша Лукин на "холодных" атомах, Кристофер Монро на ионах, француз Антуан Брауэрс на атомах, компания IBM на сверхпроводниках. Ориентировочно к 2030 г. использовать квантовый компьютер станет экономически выгодно. К этому времени появится и универсальный КК, и мощные квантовые симуляторы. Они будут применяться при разработке вакцин от большинства тяжелых болезней, того же рака, например, а также для создания уникальных материалов с новыми, фантастическими по сегодняшним меркам характеристиками. Это кардинально изменит транспорт, всю нашу жизнь. Если уходить от прогнозов к совсем фантастической футурологии, то когда-нибудь с помощью КК мы поймем, как устроена наша Вселенная и создадим модель новой Вселенной, нового мира. А заодно и новых людей. Вот тут и начнется самое интересное. (смеется).
- Сделаем такие же атомы с ножками, как мы сами. И с большими амбициями, что нехарактерно для атомов, поэтому экзамен на цивилизацию они тоже не пройдут. А можете поделиться своими соображениями по поводу модели Вселенной, загодя, так сказать? Вы же, наверняка, не раз об этом думали.
- Мне кажется, что мы вполне можем существовать в матрице. Эта теория очень хорошо согласуется и с нашей реальностью, и с законами квантового мира. Но так ли это, нам, вполне возможно, расскажет именно квантовый компьютер.
- То есть наш мозг додуматься до модели не в состоянии. Слабоват. Хотя многие ученые считают его чуть ли не самым загадочным объектом в той же Вселенной.
- Видите ли, человеческий мозг изначально не создавался для научных открытий. Его задачей было наладить коммуникацию в социальном обществе - с остальными нашими прародителями, человекообразными обезьянами и т.д. Все гениальные идеи, невероятный креатив, талантливые творческие произведения - для мозга всего лишь побочные явления. Поэтому-то мы и пришли к неизбежности создания КК. Знаете закон Мура, одного из основателей Intel? Что каждые 18 месяцев производительность компьютеров удваивается. То есть за последние 50 лет эта производительность увеличилась в миллиард раз. Транзисторы уже стали размером порядка 10 нанометров, это примерно в 10 раз меньше диаметра частицы коронавируса. Дальше уже фундаментальный предел. А человечеству для разных нужд нужны еще более мощные машины. Что делать? Всю Землю обложить процессорами? Но и тогда мы не получим требуемой скорости вычислений. А КК масштабируется очень быстро, уже со ста кубитами он недостижим для настоящих и будущих суперкомпьютеров.
- Другими словами, КК - это что-то вроде чаши Грааля для современной науки и нашей будущей жизни.
4. Энергоэффективность
Потребляемая мощность является критическим фактором для любого устройства, работающего на электричестве. Огромному массиву процессоров требуется изрядное количество блоков питания для поддержания их производительности. Самый быстрый суперкомпьютер в мире Sunway TaihuLight (по состоянию на апрель 2017 года) потребляет 15,37 МВт электроэнергии.
Однако, это становится захватывающим с квантовыми компьютерами. Поскольку они используют квантовое туннелирование, они уменьшат энергопотребление в 100-1000 раз.
5. Альтернативные реальности
Согласно квантовой физике, мы имеем дело с тем, что называется Мультивселенной, где проблема может иметь много или бесконечное количество возможных решений. Например, вы можете читать эту статью на своем Macbook. В другом вы, возможно, читаете это по мобильному телефону во время путешествия.
Квантовый компьютер может выполнять «n» задач в «n» параллельных вселенных и достигать конечного результата. Если традиционный компьютер делает «N» вычисления в «N» секунд, квантовый компьютер может выполнить «N 2» вычисления в то же время.
Возможно, вы помните, что Deep Blue IBM был первым компьютером, победившим чемпиона мира по шахматам Гарри Каспарова в 1997 году. Компьютер сделал это, изучая 200 миллионов возможных ходов в секунду. Вдали от способностей человеческого мозга! Но если бы это была квантовая машина, она бы рассчитала 1 триллион ходов в секунду, 4 триллиона ходов за 2 секунды и 9 триллионов ходов за 3 секунды.
7. Низкая температура
Температура, необходимая для поддержания стабильного состояния для лучшей производительности, должна быть действительно низкой. Чтобы квантовые компьютеры работали, атомы должны быть стабильными. И единственный известный эффективный способ поддержания стабильности этих атомов - это снижение температуры до нуля Кельвина, где атомы становятся стабильными без выделения тепла.
В настоящее время система D-Wave 2000Q является самым совершенным квантовым компьютером. Его сверхпроводящий процессор охлаждается до 0,015 Кельвина (в 180 раз холоднее, чем межзвездное пространство).
Атомный "выстрел"
- А мы на каком месте с хвоста этой гонки?
- Ну, зачем так. В России есть программа, на которую выделено 24 миллиарда рублей. Через три года мы должны создать 100-кубитный прототип квантового компьютера, а также разработать софт и алгоритмы. Задача, конечно, грандиозная. Но выполнимая.
- Вы это серьезно?
- Абсолютно. Иначе бы я просто не руководил "квантовой" программой. Мы уже полным ходом работаем на всех четырех платформах - с атомами, охлажденными почти до абсолютного нуля, ионами, которые захватывают в ловушки лазеры, фотонами, со сверхпроводниками. Что в конце концов "выстрелит", на какой основе будет создан в будущем КК - в мире не знает никто. Поэтому все работают по нескольким направлениям. Китайцы сильны в оптике и сверхпроводниках, американцы - в сверхпроводниках, атомах и ионах, европейцы в атомах и ионах. Наша задача - встать в число лидеров. Начать тоже что-то создавать первыми в области квантовых вычислений. И это нам по силам. Мозги-то в России еще остались, уверяю вас. Знаете, как в теоретической физике ученые шутят? Если на пути исследования встретилась проблема - поройся в книгах русских физиков, они, скорее всего, уже решили ее лет 40 назад.
3. Переопределение безопасности
Скорость квантового компьютера также является серьезной проблемой в области шифрования и криптографии. Современные системы финансовой безопасности в мире основаны на факторизации больших чисел (алгоритмы RSA или DSA), которые буквально не могут быть взломаны обычными компьютерами в течение жизни Земли. Тем не менее квантовый компьютер может рассчитывать числа в разумный период времени.
С другой стороны, квантовые компьютеры смогут обеспечить небьющиеся функции безопасности. Они могут блокировать важные данные (например, онлайн-транзакции, учетные записи электронной почты) с гораздо лучшим шифрованием.
Многие алгоритмы были разработаны для квантовых компьютеров - наиболее известными являются алгоритм Гровера для поиска в неструктурированной базе данных и алгоритм Шора для факторизации больших чисел.
Проблема Y2Q
Исследователи придумали термин, обозначающий момент, когда "черепаха" будет проходить мимо "зайца". Это год Y2Q, когда возможности квантового взлома кода станут угрозой существованию классической криптографии. Когда это произойдет, остается только догадываться, но вопрос о том, произойдет ли это, для многих уже решен. В 2018 году в отчете Национальной академии наук, инженерии и медицины США (NASEM) было предсказано, что мощный квантовый компьютер, использующий алгоритм Шора, сможет взломать 1024-битную реализацию шифрования RSA менее чем за 24 часа.
Математик Питер Шор, ответственный за один из алгоритмов, в конце 2020 года добавил свое собственное предупреждение: «Я думаю, что единственным препятствием для замены RSA [криптосистемы с открытым ключом] на безопасную постквантовую криптосистему будет сила воли и время программирования. Если мы будем ждать слишком долго, будет слишком поздно».
В конце 2018 года редакторы журнала Nature объяснили риск, связанный с продуктами блокчейн. Так, безопасность блокчейна основана на односторонних математических функциях. Их легко запустить на обычном компьютере и трудно рассчитать в обратном порядке. Например, умножить два больших простых числа легко, но найти простые множители данного произведения сложно — обычному компьютеру может потребоваться много лет, чтобы решить.
Но алгоритм Шора разработан для работы на квантовом компьютере, который может принимать число и выводить его множители за короткий промежуток времени. С математической точки зрения, это потребует логарифмического а не экспоненциального количества времени. Алгоритм Гровера также является квантовым алгоритмом, предназначенным для ускорения поиска в несортированных базах данных.
Сегодня RSA зависит от сложности, связанной с большими простыми числами. Учёные предсказывают, что в течение десяти лет квантовые компьютеры смогут вычислять односторонние функции, включая блокчейны, которые используются для защиты Интернета и финансовых транзакций. Широко распространенное одностороннее шифрование мгновенно устареет.
Еще несколько интересных фактов и открытий
12. Квантовые вычисления впервые были упомянуты Ричардом Фейнманом в 1959 году в его знаменитой лекции «Внизу много места». Он рассматривал возможность манипулирования отдельными атомами как расширенную форму синтетической химии.
13. Первый в мире протокол распространения квантовых ключей, BB84, был разработан исследователями IBM Джиллис Брассард и Чарльзом Беннеттом в 1984 году. Это метод безопасной отправки секретного ключа из одной точки в другую для использования в одноразовом шифровании с использованием клавиатуры.
14. В феврале 2018 года физики придумали новую форму света, включающую трифотонные связанные состояния в квантовой нелинейной среде, которая могла бы привести к революции квантовых вычислений.
15. В марте 2018 года Лаборатория квантового искусственного интеллекта, управляемая Ассоциацией космических исследований университетов, НАСА и Google, выпустила 72-битный процессор под названием Bristlecone.
16. Реалистичная модель квантовых вычислений работает на квантовых алгоритмах, которые могут быть классифицированы по типу задачи, которую они решают, или технике/идеям, которые они используют. В настоящее время у нас есть алгоритмы, основанные на усилении амплитуды, квантовом преобразовании Фурье и гибридных квантовых алгоритмах.
17. В настоящее время рассматривается несколько различных кандидатов на физическую реализацию квантовой машины. Среди них самыми популярными являются -
- Спиновая и пространственная квантовая точка
- Квантовый компьютер на алмазной основе
- Полость квантовая электродинамика
- Молекулярный магнит
18. До сих пор 5 компаний производили квантовые чипы - Google (Bristlecone), IBM (IBM Experience and Q), Intel (Tangle Lake), Rigetti (19Q) и D-Wave (Ranier).
Безопасность таких методов основана на времени, которое классический компьютер тратит на расшифровку информации. Современные методы шифрования практически не ломаются, поскольку сегодняшним компьютерам потребуются тысячи лет для расшифровки их кода.
Однако квантовые компьютеры могли бы легко взломать этот код, и эти машины гораздо ближе к реальности, чем ожидалось.
Модульное экспонирование
Их метод выполняет модульное возведение в степень - тип возведения в степень, выполненный по модулю - эффективным способом. Эта математическая операция является вычислительно дорогой в алгоритме Шора.
Исследователи нашли разные способы оптимизировать эту операцию, резко сократив ресурсы, необходимые для запуска алгоритма.
Хотя квантовый компьютер с 20-миллионным кубитом в ближайшем будущем невозможен, эксперты по безопасности должны подумать о новой форме шифрования, которую даже мощный квантовый компьютер не сможет взломать.
В настоящее время, как в известной басне, ведется опасное соревнование «черепахи и зайца» между квантовыми вычислениями и классической криптографией. Последняя же защищает Интернет, регистры блокчейнов, средства коммуникации и многое другое. Не похоже, что медленно развивающиеся сегодня квантовые вычисления скоро поймают классическую криптографию, но предупреждение в басне всё равно уместно.
Квантовые компьютеры обладают неограниченным потенциалом и особыми талантами — векторами атаки, такими как алгоритмы Шора и Гровера, которые могут взломать криптографию. Причина, по которой эти двое еще не закончили гонку, заключается в том, что все необходимые вычисления на обычных компьютерах могут занять годы. Но многие ожидают, что это изменится по мере роста масштабов и скорости квантовых компьютеров.
2. Пылающая скорость
Поскольку квантовый компьютер может существовать не только в 0 и 1, они могут выполнять вычисления параллельно. Давайте рассмотрим простой пример, если кубит находится в суперпозиции состояния 0 и состояния 1, и он выполнил вычисление с другим кубитом в аналогичной суперпозиции, он оставил бы четыре результата - 0/1, 0/0, 1/0 и 1/1.
Квантовый компьютер покажет вышеуказанный результат, когда он находится в состоянии декогеренции, которое длится, пока он находится в суперпозиции состояний, пока он не упадет до одного состояния. Возможность одновременного выполнения нескольких задач называется квантовым параллелизмом.
Бег за лидерами
- Конкуренция в "квантовом" мире жесткая или жестокая?
- Скажу так: в лоб тяжело, конечно, конкурировать. Например, Китай сейчас собирается потратить на очередной квантовый центр 11 миллиардов долларов. Германия, Япония, не говорю уж о США, тоже тратят гигантские суммы на развитие квантовых технологий. У нас экономика всего 2 процента от мировой, поэтому позволить себе суммы, как в Китае или США, мы просто не в состоянии. Однако программа по созданию КК у нас тоже запущена. Мы догоняем всех. Бежим за лидерами и стараемся не отстать от основной группы.
- Честно? Как создать 100-кубитный прототип квантового компьютера к 2024 году - мы понимаем. А вот как выйти в лидеры в этой области - пока нет.
- Канадская фирма D-Wave объявила недавно, что любой желающий может купить ее квантовый компьютер за 15 миллионов долларов. Может, вам стоит прицениться, надо же с чего-то начинать.
- Прицениваться не к чему (улыбается). Это опять-таки не компьютер, а симулятор. Хотя, не спорю, какие-то квантовые эффекты в его работе есть. Но о чем это говорит? Гонка ускоряется, и бежать нам надо, как у Высоцкого "Я на десять тыщ рванул, как на пятьсот. "
Квантовые компьютеры не должны проверять вашу электронную почту, обновлять статус или выполнять обычные программные/аппаратные задачи. Вместо этого они основаны на чем-то более сложном - квантовой механике.
Квантовый компьютер имеет дело с частицей, намного меньшей, чем размер атома. В таком меньшем масштабе правила физики не имеют никакого смысла. Именно здесь начинают происходить захватывающие вещи. Частицы могут двигаться вперед и назад или даже существовать одновременно. Эти типы компьютеров могут увеличить вычислительную мощность сверх того, что достижимо на современных обычных компьютерах.
Давайте уточним, что мы знаем о квантовых вычислениях в настоящее время. Мы собрали некоторые интересные факты о квантовых компьютерах, которые определенно ошеломят вас.
Квантовые компьютеры становятся все более мощными
В 1994 году американский математик Питер Шор разработал квантовый алгоритм для экспоненциального вычисления больших чисел по сравнению с лучшими существующими алгоритмами, работающими на классическом компьютере. Он предположил, что достаточно мощная квантовая машина могла бы легко сломать современные методы шифрования.
В последнее десятилетие в квантовых вычислениях был достигнут большой прогресс. В 2012 году ученые смогли использовать квантовый компьютер с 4 кубитами, чтобы получить коэффициент «143». Два года спустя они использовали похожую машину с коэффициентом «56153».
Учитывая скорость прогресса, квантовые компьютеры скоро смогут превзойти современные компьютеры. По крайней мере, это то, что ученые ожидали несколько лет назад.
Оказывается, факторинг больших чисел в квантовых машинах намного сложнее, чем предполагалось. Это связано со значительным шумом в больших квантовых компьютерах. Проблема может быть решена с помощью кодов, исправляющих ошибки, которые сами требуют дополнительных кубитов.
Существующие атаки
Для примера, рассмотрим атаку, которая нацелена именно на алгоритм RSA. Суть этой атаки заключается в поиске ключа путем факторизации большого числа (алгоритм Шора для этого как раз заточен!). Если мы сможем вычислить простые числа, которые использовались для генерации конкретного ключа, то фактически получим значение этого ключа.
Итак, мы должны перебрать большой набор чисел. Это очень сложно сделать, но теперь в наших руках грозное оружие — алгоритм Шора. Если наш процесс пройдёт успешно, у нас будет возможность атаковать систему RSA. Фактически, вся сложность состоит во времени, которое нужно для перебора чисел.
По существующим оценкам учёных, при наличии квантовых компьютеров нам потребуется около 20 миллионов физических кубитов для ключа размером 2048 бит. Вы удивитесь, но даже и при таком огромном количестве кубитов нам нужно будет ждать 8 часов.
Если у нас в распоряжении не такие мощные квантовые компьютеры, то оценки показывают, что с 13436 квантовыми единицами информации мы должны будем потратить 177 дней. Сегодня мы не располагаем такой возможностью. Хорошо это или плохо? Поговорим в следующем разделе.
1. Схема хранения информации
Компьютеры, которые мы используем сегодня, хранят данные в двоичном формате - серии 0 и 1. Каждый компонент памяти называется битом, и им можно манипулировать с помощью шагов булевой логики.
С другой стороны, квантовый компьютер будет хранить данные в виде 0, 1 или квантовой суперпозиции двух состояний. Такой квантовый бит (также известный как кубиты) обладает гораздо большей гибкостью по сравнению с двоичной системой.
Кубиты могут быть реализованы с помощью частиц с двумя спиновыми состояниями - "вверх" и "вниз". Такая система может быть отображена на эффективную систему со спином 1/2.
Перспективы развития
Адаптируя стратегию "если ты не можешь кого-то победить, присоединяйся к ним", сейчас начинается гонка за право использования тех же квантовых вычислений. Возможно, эта гонка ведётся даже за мощь "квантового Интернета", который приведёт к созданию новых, более сложных процедур шифрования. Конечная цель — постквантовая криптография.
Можно выделить несколько перспективных методов, на которых основана постквантовая криптография:
Обмен ключами с использованием суперсингулярных изогений
Эти подходы не являются решением на века, но способны составить большую конкуренцию квантовым протоколам взлома. Заинтересовавшиеся могут ознакомиться подробнее по ссылкам выше.
Стоит отметить, что проблема массового исчезновения информационной безопасности не нова. Шифрование, созданное немецкими военными машинами Enigma во время Второй мировой войны, в конечном итоге было взломано союзниками, но на этом криптография не закончилась. А в 1977 году в ходе публичного конкурса был нарушен современный стандарт шифрования данных (DES).
Сегодня особого внимания требует предупреждение Питера Шора о своевременном выполнении решений. Очевидно, что давление оказывается потому, что технологии шифрования глубоко встроены во многие различные системы. По этой причине их взлом и внедрение новых может занять много времени.
Не все предсказывают, что гонка завершится через несколько лет. Например, Роджер Граймс, специалист по обеспечению безопасности KnowBe4, объявил, что 2021, вероятно, станет первым публичным признанием квантового криптографического взлома, когда квантовые компьютеры будут способны взламывать традиционные криптографические ключи с открытым ключом. Как мы можем наблюдать, этого пока не случилось.
Заключение
Итак, в нашей статье мы рассмотрели опасность квантового вычисления для классического шифрования Y2Q, представили краткое описание алгоритма Шора и поговорили о перспективах развития криптографии.
Очевидно, что когда-то всё учёное сообщество верило в абсолютную стойкость классических криптографических систем. Но мир не стоит на месте, и вот уже мы с Вами говорим не просто о квантовой криптографии, а о постквантовых системах. Наверняка, через много лет люди будут писать о рассматриваемом нами алгоритме Шора как об устаревшем и очень медленном, но это и называется прогрессом.
2 декабря 2019 года в рассылке по теории чисел nmbrthry@listserv.nodak.edu сообщили о RSA Factoring Challenge.
Вот число и его множители:
Многие алгоритмы шифрования с открытым ключом полагаются на чрезвычайно большие числа, являющиеся произведением двух простых чисел. Другие полагаются на трудность решения некоторых дискретных логарифмических задач. При достаточно больших размерах ключей нет известного способа взломать такое шифрование. Факторизация больших чисел и вычисление дискретного логарифма разрушают криптографические гарантии для заданного размера ключа и заставляют пользователей увеличивать количество бит энтропии при генерации секрета.
Всё более сложные шифры постепенно поддаются взлому по мере роста производительности CPU и благодаря совершенствованию алгоритмов.
После изобретения алгоритма решета числового поля (general number field sieve, GNFS) в начале 90–х в области факторизации целых чисел не появилось ничего революционного, хотя проведены некоторые существенные оптимизации. Например, в последние несколько лет исследователи смогли сильно ускорить фазу нахождения подходящего многочлена.
Та же группа исследователей вычислила и дискретный логарифм того же размера. Впервые в истории рекорды на дискретное логарфмирование и факторизация чисел одинакового размера установлены одновременно, да ещё на одном и том же оборудовании и программном обеспечении.
Оба типа вычислений проводились с помощью алгоритма решета числового поля в опенсорсной программе CADO-NFS. Среди оптимизаций — улучшенная параллелизация и использование памяти, а также большая работа по нахождению более оптимальных параметров расчёта (было разработано специальное программное обеспечения для тестирования и ранжирования разных параметров расчёта).
Сумма вычислительного времени для обеих новых записей составляет около 4000 лет работы физических ядер процессоров Intel Xeon Gold 6130 (на частоте 2,1 ГГц), если этот процессор взять в качестве эталона.
Грубая разбивка времени на факторизацию и логарифмирование:
- Просеивание RSA-240: 800 ядро-лет
- Матрица RSA-240: 100 ядро-лет
- Просеивание DLP-240: 2400 ядро-лет
- Матрица DLP-240: 700 ядро-лет
Изобретатели шифра RSA опубликовали числа RSA всех размеров вплоть до RSA-2048. Все желающие могут попробовать их взломать.
Исходя из текущего тренда можно посчитать, когда будут взломаны RSA-1024 (309 знаков) и RSA-2048 (617 знаков). Если экстраполировать график, получаются примерно 2031 год и 2073 год, соответственно. Но мы видим, что оптимизация программного обеспечения и алгоритмов способны существенно приблизить этот срок. Возможно, RSA-2048 взломают ещё при нашей жизни.
На практике подтверждаются рекомендации RSA использовать минимальный размер ключей RSA 2048 или 4096 бит.
Судя по развитию квантовых компьютеров, они нескоро приблизятся к взлому ключей такого размера, хотя здесь трудно что-то прогнозировать. В 2012 году алгоритм Шора справился с факторизацией числа 21 (3×7), пять бит энтропии. Это число долго оставалось рекордом квантовой факторизации, но в 2018 году на 5- и 16-кубитных процессорах IBM была продемонстрирована факторизация произведения простых чисел 4088459, а это уже 22 бита.
Алгоритм Шора
Питер Шор
В этом параграфе кратко рассмотрим сам алгоритм Шора. Цель алгоритма: для нечетного составного числанужно найти целое число(строго от 1 дона которое делится
Алгоритм Шора состоит из следующих частей:
Преобразование проблемы факторизации в задачу нахождения периода. Эта часть может быть реализована классическими средствами.
Нахождение квантового периода с помощью квантового преобразования Фурье, которое отвечает за квантовое ускорение и использует квантовый параллелизм.
Общая последовательность действий:
Алгоритм Шора содержит несколько шагов, причём только на втором шаге требуется использование квантовых компьютеров.
Выбираем любое случайное число такое, что и — взаимно простые числа.
Квантовый компьютер используется для определения неизвестного периода функции
Если — нечетное целое число, возвращаемся к шагу 1. В противном случае переходим к следующему шагу.
Поскольку — четное целое число, то
Теперь, если значение то возвращаемся к шагу 1.
Если значение переходим к следующему шагу.
Получаем требуемое значение
11. Последние достижения в области квантовых вычислений
Ученые из Университета Нового Южного Уэльса разработали первый квантовый логический элемент в кремнии в 2015 году. В том же году НАСА представило первый операционный квантовый компьютер, созданный D-Wave, стоимостью 15 миллионов долларов.
В 2016 году исследователи из Университета Мэриленда успешно создали первый перепрограммируемый квантовый компьютер. Два месяца спустя Базельский университет определил вариант квантовой машины на основе электронных дырок, которая использует электронные дыры (вместо того, чтобы манипулировать электронными спинами) в полупроводнике при низких температурах, которые гораздо менее уязвимы для декогеренции.
Биты - убиты
- А вы можете объяснить для профана-гуманитария - в чем главное отличие квантового компьютера от обычного. На пальцах, что называется. Я постараюсь напрячь мозг.
- Давайте попробуем (улыбается). В обычном компьютере вся информация зашифрована в битах. 1 бит - 1 единица информации. А биты, в свою очередь, состоят из одних только нулей и единичек. Все, что содержится в вашем планшете, смартфоне, ноутбуке, тексты, фото, картинки - все зашифровано с помощью единиц и нулей. Которые - внимание! - могут составлять одномоментно лишь одно состояние, пусть даже и сложное. Для 10 битов, например, 1001101010.
В КК вся информация зашифрована в кубитах (к слову "биты" просто добавлена приставка "ку" - от английского слова quantum, что означает "квант"). В роли этих кубитов могут выступать или атомы редкоземельных металлов итербия, тулия, или частицы света фотоны, или ионы - заряженные атомы, "потерявшие" или, наоборот, "приобретшие" один или несколько электронов. Или просто электрические цепи в сверхпроводниках.
Все эти атомы или фотоны в квантовом мире могут быть там и тут одновременно. И единицей, и нулем. Это называется суперпозицией. Обычный компьютер оперирует только одним состоянием. А квантовый. У него возможных состояний 2 в той степени, сколько заложено в нем кубитов. Если кубитов 10, то он одновременно в 1024 состояниях, а если всего лишь 300, то 2 в 300-й степени - это больше, чем атомов во всей Вселенной, можете себе такое представить? КК "соображает" сразу на всех уровнях. Параллельно. Поэтому он всегда будет на голову выше любого обычного компьютера, пусть даже и с приставкой "супер". Можно и дальше углубляться в странные законы квантового мира, например, для КК нужна еще и квантовая запутанность. Слышали про такое?
- Ну, кто ж не знает про квантовую запутанность. Кстати, не так давно ученые из Шанхайского университета представили КК "Цзючжан", который, как они заявили, является на сегодняшний день самым мощным квантовым компьютером. Во время демонстрации он всего за несколько минут решил задачу по отбору проб гауссовских бозонов. Это я цитирую информационное агентство, не пугайтесь моей грамотности. С подобной задачей самый мощный современный суперкомпьютер справился бы только за 2,5 миллиарда лет. Получается - КК уже создан, гонка завершилась?
- Что вы, только начинается. Китайский продукт - это не полноценный, не универсальный квантовый компьютер. Он так называемый симулятор, который предназначен лишь для демонстрации "квантового превосходства". Другими словами, "Цзючжан" делает на публике то, чего никогда не сможет сделать обычный суперкомпьютер, пусть даже с миллионами ядер. В прошлом году, кстати, Google представила свой прототип КК - Sycamore. Китайские ученые сообщили, что скорость вычислений их КК в 10 миллиардов раз выше, чем гугловского. Но последний уже программируется, то есть может решать разные задачи, а китайский нет. Что, конечно, никак не умаляет заслуг шанхайских ученых. К слову, один из руководителей программы, профессор Лю Чаоян сказал, что создание КК - это гонка не между странами, а между человечеством и природой. Очень точное замечание.
Читайте также: