{"id":20533,"date":"2023-01-09T12:21:20","date_gmt":"2023-01-09T17:21:20","guid":{"rendered":"https:\/\/me-en.kaspersky.com\/blog\/quantum-computers-and-rsa-2023\/20533\/"},"modified":"2023-01-10T21:19:56","modified_gmt":"2023-01-10T17:19:56","slug":"quantum-computers-and-rsa-2023","status":"publish","type":"post","link":"https:\/\/me-en.kaspersky.com\/blog\/quantum-computers-and-rsa-2023\/20533\/","title":{"rendered":"Will quantum computers break RSA encryption in 2023?"},"content":{"rendered":"

In the final days of 2022, the IT community was rather stirred by a study<\/a> presented by a group of Chinese scientists. It claimed that in the nearest future it will be possible to crack the RSA crypto algorithm with a key length of 2048 bits \u2013 which is fundamental for the operation of internet protocols \u2013 by skillfully combining classical and quantum computing. So how real is this threat? Let\u2019s figure it out.<\/p>\n

Quantum basics<\/h2>\n

\nThe theoretical ability of a quantum computer to perform ultra-fast factorization of giant integers and thus match keys for a number of asymmetric crypto-algorithms \u2013 including RSA encryption \u2013 has long been known. Our blog post<\/a> explains in detail what a quantum computer is, how it works, and why it\u2019s so difficult to build. So far, all experts have agreed that a quantum computer large enough to crack RSA would probably be built no sooner than around a few dozen decades. To factorize an integer 2048 bits long, which is usually used as an RSA key, the Shor algorithm needs to be run on a quantum computer with millions of qubits (quantum bits). That is, it\u2019s not a matter of the nearest future, since the best quantum computers today work at 300-400 qubits \u2014 and this is after decades of research.<\/p>\n

But the future problem has already been actively thought about, and security experts are already calling for adoption of post-quantum cryptography<\/a>; that is, algorithms that are resistant to hacking with a quantum computer. There seemed to be a decade or more for a smooth transition, so the news that RSA-2048 might fall as early as in 2023 came as a bolt from the blue.<\/p>\n

News from China<\/h2>\n

\nChinese researchers have been able to factor a 48-bit key on a 10-qubit quantum computer. And they calculated that it\u2019s possible to scale their algorithm for use with 2048-bit keys using a quantum computer with only 372 qubits. But such a computer already exists today, at IBM<\/a> for example, so the need to one day replace crypto-systems throughout the internet suddenly ceased being something so far in the future that it wasn\u2019t really thought about seriously. A breakthrough has been promised by combining the Schnorr algorithm<\/a> (not to be confused with the aforementioned Shor algorithm) with an additional quantum approximate optimization algorithm (QAOA) step.<\/p>\n

\"The<\/a>

The proposed scheme of the hybrid factorization algorithm<\/p><\/div>\n

Schnorr\u2019s algorithm is used for supposedly more efficient factorization of integers using classical computation. The Chinese group proposes to apply quantum optimization at the most computationally intensive stage of its work.<\/p>\n

Open questions<\/h2>\n

\nSchnorr\u2019s algorithm was met by the mathematical community with certain skepticism. The author\u2019s claim that \u201cthis will destroy the RSA cryptosystem\u201d in the description of the study was subjected to scrutiny and didn\u2019t stand up. For example, famous cryptographer Bruce Schneier said that it \u201cworks well with smaller moduli \u2014 around the same order as ones the Chinese group has tested \u2014 but falls apart at larger sizes.\u201d And no one has succeeded in proving that this algorithm is scalable in practice.<\/p>\n

Applying quantum optimization to the \u201cheaviest\u201d part of the algorithm seems like a good idea, but quantum computing experts doubt<\/a> that QAOA optimization will be effective in solving this computational problem. It\u2019s possible to use a quantum computer here, but it will unlikely lead to time savings. The authors of the work themselves carefully mention this dubious moment at the very end of their report, in the conclusion:<\/p>\n

\nIt should be pointed out that the quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA.
\n\u2026
\nBesides, the quantum speedup is unknown, it is still a long way to break RSA quantumly.\n<\/div>\n

Thus, it looks like even if you implement this hybrid algorithm on a classical + quantum system, it will take as long to guess RSA keys as with a regular computer.<\/p>\n

The icing on the cake is that in addition to the number of qubits there are other important parameters of a quantum computer, like levels of interference and errors, and the number of gates. Judging by the combination of required parameters, even the most promising computers of 2023-2024 are probably not suitable for running the Chinese algorithm on the needed scale.\n<\/p>\n

Practical takeaways<\/h2>\n

\nWhile the crypto revolution is once again being delayed, the buzz around this study highlights two security-related challenges. First, when choosing a quantum-resistant algorithm among numerous proposals for a \u201cpost-quantum standard\u201d, new algebraic approaches \u2013 such as the aforementioned Schnorr\u2019s algorithm \u2013 should be studied scrupulously. Second, we definitely need to raise the priority of projects for the transition to post-quantum cryptography<\/a>. It will seem like a non-urgent matter only until it\u2019s too late\u2026<\/p>\n","protected":false},"excerpt":{"rendered":"

Everybody knows that we should prepare ourselves for a \u201cquantum future\u201d, but it was expected to come about in 10-20 years\u2019 time. Is a breakthrough possible this year?<\/p>\n","protected":false},"author":2722,"featured_media":20536,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1318,1916,1226],"tags":[1737,261,448],"class_list":{"0":"post-20533","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-business","8":"category-enterprise","9":"category-technology","10":"tag-advice","11":"tag-encryption","12":"tag-quantum-computers"},"hreflang":[{"hreflang":"en-ae","url":"https:\/\/me-en.kaspersky.com\/blog\/quantum-computers-and-rsa-2023\/20533\/"},{"hreflang":"en-in","url":"https:\/\/www.kaspersky.co.in\/blog\/quantum-computers-and-rsa-2023\/25039\/"},{"hreflang":"en-us","url":"https:\/\/usa.kaspersky.com\/blog\/quantum-computers-and-rsa-2023\/27605\/"},{"hreflang":"en-gb","url":"https:\/\/www.kaspersky.co.uk\/blog\/quantum-computers-and-rsa-2023\/25365\/"},{"hreflang":"es-mx","url":"https:\/\/latam.kaspersky.com\/blog\/quantum-computers-and-rsa-2023\/25692\/"},{"hreflang":"es","url":"https:\/\/www.kaspersky.es\/blog\/quantum-computers-and-rsa-2023\/28248\/"},{"hreflang":"ru","url":"https:\/\/www.kaspersky.ru\/blog\/quantum-computers-and-rsa-2023\/34503\/"},{"hreflang":"x-default","url":"https:\/\/www.kaspersky.com\/blog\/quantum-computers-and-rsa-2023\/46733\/"},{"hreflang":"fr","url":"https:\/\/www.kaspersky.fr\/blog\/quantum-computers-and-rsa-2023\/19969\/"},{"hreflang":"pt-br","url":"https:\/\/www.kaspersky.com.br\/blog\/quantum-computers-and-rsa-2023\/20551\/"},{"hreflang":"de","url":"https:\/\/www.kaspersky.de\/blog\/quantum-computers-and-rsa-2023\/29645\/"},{"hreflang":"ru-kz","url":"https:\/\/blog.kaspersky.kz\/quantum-computers-and-rsa-2023\/25746\/"},{"hreflang":"en-au","url":"https:\/\/www.kaspersky.com.au\/blog\/quantum-computers-and-rsa-2023\/31406\/"},{"hreflang":"en-za","url":"https:\/\/www.kaspersky.co.za\/blog\/quantum-computers-and-rsa-2023\/31118\/"}],"acf":[],"banners":"","maintag":{"url":"https:\/\/me-en.kaspersky.com\/blog\/tag\/encryption\/","name":"encryption"},"_links":{"self":[{"href":"https:\/\/me-en.kaspersky.com\/blog\/wp-json\/wp\/v2\/posts\/20533","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/me-en.kaspersky.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/me-en.kaspersky.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/me-en.kaspersky.com\/blog\/wp-json\/wp\/v2\/users\/2722"}],"replies":[{"embeddable":true,"href":"https:\/\/me-en.kaspersky.com\/blog\/wp-json\/wp\/v2\/comments?post=20533"}],"version-history":[{"count":5,"href":"https:\/\/me-en.kaspersky.com\/blog\/wp-json\/wp\/v2\/posts\/20533\/revisions"}],"predecessor-version":[{"id":20541,"href":"https:\/\/me-en.kaspersky.com\/blog\/wp-json\/wp\/v2\/posts\/20533\/revisions\/20541"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/me-en.kaspersky.com\/blog\/wp-json\/wp\/v2\/media\/20536"}],"wp:attachment":[{"href":"https:\/\/me-en.kaspersky.com\/blog\/wp-json\/wp\/v2\/media?parent=20533"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/me-en.kaspersky.com\/blog\/wp-json\/wp\/v2\/categories?post=20533"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/me-en.kaspersky.com\/blog\/wp-json\/wp\/v2\/tags?post=20533"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}