Содержание |
2024
Новый квантовый алгоритм приближает крах шифрования
23 августа 2024 года американские исследователи из Массачусетского технологического института (MIT) сообщили о разработке нового алгоритма для квантовых компьютеров, который приближает крах традиционного шифрования. В долгосрочной перспективе результаты работы могут способствовать появлению криптографических методов, способных противостоять взлому при помощи квантовых компьютеров.
Широко распространенной схемой шифрования является RSA (Rivest, Shamir и Adleman): это криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации (разложения числа на простые множители) больших полупростых чисел. В 1994 году американский ученый Питер Шор предложил квантовый алгоритм факторизации, позволяющий осуществлять взлом криптографических систем с открытым ключом.
Однако для запуска алгоритма Шора квантовому компьютеру потребуется около 20 млн кубитов. По состоянию на август 2024 года мощнейшие квантовые системы оперируют примерно 1100 кубитами. Чем больше у квантового компьютера кубитов, тем более сложные вычисления он может выполнять. Но при этом возрастает вероятность ошибок из-за помех. В то время как некоторые исследователи занимаются созданием более мощных квантовых компьютеров, другие пытаются улучшить алгоритм Шора, сделав его менее требовательным к ресурсам.
В 2023 году специалист из Нью-Йоркского университета Одед Регев (Oded Regev) предложил теоретическое улучшение алгоритма Шора, которое позволяет ускорить его работу, но требует больше памяти. Основываясь на этих результатах, исследователи MIT разработали подход, сочетающий в себе скорость метода Регева и эффективность использования памяти алгоритма Шора. Они нашли способ рассчитывать экспоненты при помощи чисел Фибоначчи: это требует простого умножения, а не возведения в квадрат. Таким образом, необходимо всего две единицы квантовой памяти для вычисления любого показателя степени. Кроме того, ученые решили проблему ошибок, используя технику фильтрации некорректных результатов. В будущем исследователи надеются сделать свой алгоритм еще более эффективным, что сделает возможным быстрый взлом систем традиционного шифрования.[1]
Российские ученые опровергли вывод исследователей из Китая о возможности взлома квантовых алгоритмов
Коллектив ученых Университета МИСИС, РКЦ и Сбер провел глубокий анализ вычислений, используемых исследователями из Китая при имитации взлома криптосистемы с помощью 400+ кубитного квантового компьютера, и поставил под сомнение их вывод о революции в криптографии. Российские ученые считают, что алгоритм коллег нерабочий из-за "подводных камней" в классической части и сложности реализации квантовой. Об этом МИСИС сообщил 10 января 2024 года.
RSA является одной из первых криптосистем с открытым ключом и используется для безопасной передачи данных. Считается, что большинство используемых в на январь 2024 года криптосистем с открытым ключом защищены от атак через обычные мощные компьютеры, но не через квантовые.
В декабре 2022 года ученые из Китая опубликовали статью, в которой рассказали, что им удалось разложить на множители 48-битовое число, смоделировав взлом RSA-алгоритма, с помощью 10-кубитного квантового компьютера. Основываясь на классическом методе факторизации Шнорра, авторы используют квантовое ускорение для решения задачи поиска короткого вектора в решетке (SVP, shortest vector problem) небольшой размерности – что позволило им сделать сенсационное заявление о том, что для факторизации, т.е. разложения большого числа на множители, требуется меньше кубитов, чем его длина, а также квантовые схемы меньшей глубины, чем считалось ранее. Исследователи пришли к выводу, что можно взломать 2048-битовое число с помощью компьютера с 372 физическими кубитами, хотя ранее считалось, что для этих целей необходимо 20 миллионов. После того как IBM продемонстрировала готовность 433-кубитового квантового процессора Osprey, многие усомнились в надежности асимметричной криптографии и постквантовых криптосистем, основанных на SVP-вычислениях.
Исследователи НИТУ МИСИС, РКЦ и Сбер считают вывод о возможности взлома 2048-битового RSA-алгоритма поспешным.
 | Метод Шнорра не имеет точной оценки сложности. Основная трудность заключается не в решении одной кратчайшей векторной задачи, а в правильном подборе и решении множества таких задач. Из этого следует, что этот способ, вероятно, не подходит для чисел RSA таких размеров, которые используются в современной криптографии, – сказал Алексей Федоров, директор Института физики и квантовой инженерии НИТУ МИСИС, руководитель научной группы «Квантовые информационные технологии» РКЦ. |  |
Ученые подчеркивают, что метод, используемый исследователями из Китая, дает только приближенное решение задачи, которое можно легко получить для небольших чисел и маленьких решеток, но практически невозможно для реальных параметров криптосистем. Подробности исследования опубликованы в одном из научных журналов IEEE Access (Q1).
| | Наука двигается вперед не только за счет получения собственных позитивных результатов, но и за счет скрупулезного, критического анализа результатов других исследовательских команд. Мы показали подводные камни, которые возникают в предложенном китайскими коллегами алгоритме для взлома современных алгоритмов шифрования. Однако несмотря на то, что конкретная реализация может быть неэффективной, квантовый компьютер все же может стать серьезным риском информационной безопасности в будущем. Поэтому имеет смысл рассматривать способы минимизации этих рисков, – отметил Альберт Ефимов, к. ф. н., заведующий кафедрой инженерной кибернетики НИТУ МИСИС, вице-президент-директор Управления исследований и инноваций ПАО «Сбербанк». | |
Исследователи утверждают, что метод ученых из Китая не ведет к мгновенному взлому существующих криптоалгоритмов, однако появление новых классических и квантовых алгоритмов криптоанализа – это неизбежный шаг к внедрению постквантовой криптографии.
2022: Взлом с помощью квантового компьютера
23 декабря 2022 года обнародованы результаты исследования китайских учёных, говорящие о том, что RSA-ключи шифрования взломаны с помощью квантовых компьютеров.
Криптографический алгоритм с открытым ключом RSA основан на вычислительной сложности задачи факторизации (разложения на множители) больших простых чисел. Но теоретически данный процесс может быть значительно ускорен с помощью передовых квантовых компьютеров и алгоритма Шора. Ранее считалось, что для взлома RSA необходимо использовать квантовую систему с несколькими тысячами логических кубитов. Теперь исследователи из Китая продемонстрировали, что существует возможность обойтись несколькими сотнями кубитов.
Как сообщается, авторы работы связаны с рядом самых престижных университетов КНР, а также с государственными исследовательскими лабораториями, которые получают непосредственное финансирование и поддержку из Пекина. Учёные использовали 10-кубитный квантовый компьютер, при помощи которого, как утверждается, удалось достаточно быстро взломать 48-битный ключ шифрования RSA. При этом группа исследователей заявляет, что для взлома полноценного 2048-битного ключа RSA потребуется квантовая система с 372 кубитами.
Квантовый процессор, располагающий более чем 400 кубитами, уже представила корпорация IBM. Таким образом, теоретически в скором времени будет возможен взлом ключей RSA с 2048 битами, а это фактически поставит крест на алгоритме, история которого уходит корнями в 1976 год. Но многие специалисты ставят под сомнение результаты работы китайских учёных. Дело в том, что исследование не прошло какую-либо значимую экспертную оценку, что обычно считается необходимым минимальным стандартом для подтверждения практической ценности представленного научного труда.[2]
Примечания
