Учёные считали, что для взлома шифрования RSA нужен квантовый компьютер, который появится минимум через 10 лет. Группа китайских исследователей опубликовала работу, в которой показала методику взлома ключа RSA-48, чем сильно взволновала криптографов: ранее никому не удавалось обойти ключи такой длины. Исследование ставит под сомнение безопасность интернета, банков и других сфер, где используется RSA.
Исследователи давно знают теорию взлома сообщений, зашифрованных с помощью алгоритма RSA: для этого нужно применить квантовый алгоритм Шора и иметь компьютер на сотни тысяч кубитов. На сегодняшний день самая мощная квантовая система обладает мощностью всего в 433 кубита.
С момента открытия алгоритма учёные пытались масштабировать его под существующие квантовые системы — именно это сделали китайские исследователи. Они использовали методику Клауса-Питера Шнорра и оптимизировали алгоритм таким образом, что для дешифровки ключа RSA длиной 48 бит хватило 10-кубитного компьютера. Также учёные рассказали, что по их методике для взлома 2048-битного ключа понадобится всего 372 кубита, а не сотни тысяч, как предполагалось ранее.
«Честно говоря, большая часть статьи не укладывается у меня в голове — как математика решёточного сокращения, так и квантовая физика. И ещё есть наболевший вопрос: почему китайское правительство не засекретило это исследование?» — криптограф Брюс Шнайер.
Ранее криптографы считали, что алгоритм RSA станет потенциально небезопасным только к 2033 году.
* * *
RSA (Rivest, Shamir, Adleman): ru.wikipedia.org / en.wikipedia.org
RSA: от простых чисел до электронной подписи: habr.com (20.12.20)
_
359
