그들은 RSA-2048 키를 해독하는 방법을 제안합니다.
의 그룹 다양한 과학 센터 및 대학의 연구원 중국어 나는 제안했다n 새로운 최적화 방법r RSA 키 매개변수 분해 프로세스 양자 컴퓨터에서.
연구원들에 따르면 그들이 개발한 방법은 양자 컴퓨터의 사용을 허용합니다. 372 큐비트 RSA-2048 키를 해독합니다. 이에 비해 현재 구축된 가장 강력한 양자 프로세서인 IBM Osprey에는 433큐비트가 포함되어 있으며 IBM은 2026년까지 4000큐비트의 Kookaburra 시스템을 구축할 계획입니다.
언급 할 가치가 있습니다. 그 방법은 여전히 이론적일 뿐이며, 그것은 실제로 테스트되지 않았으며 일부 암호 작성자 사이에서 회의론을 생성합니다.
RSA 암호화는 큰 수의 지수 연산을 기반으로 합니다. 공개 키에는 모듈러스와 차수가 포함됩니다. 모듈은 개인 키의 소유자만 알고 있는 두 개의 임의의 소수를 기반으로 구성됩니다. 양자 컴퓨터는 공개 키에서 개인 키를 합성하는 데 사용할 수 있는 소인수로 숫자를 분해하는 문제를 효율적으로 해결할 수 있습니다.
지금까지 현재 개발 상황을 감안할 때 양자 컴퓨터, 2048비트 크기의 RSA 키는 오랫동안 해독할 수 없습니다., 고전적인 Shor 알고리즘을 사용하기 때문에 수백만 큐비트의 양자 컴퓨터는 2048비트 RSA 키를 분해하는 데 많은 시간이 필요합니다.
중국 연구자들이 제안한 방법은 이러한 가정에 의문을 제기합니다. 확인되면 먼 미래의 시스템이 아니라 이미 존재하는 양자 컴퓨터에서 RSA-2048 키를 해독할 수 있습니다.
이 방법은 Schnorr fast factorization 알고리즘을 기반으로 합니다. 2021년에 제안된 작업 수를 대폭 줄일 수 있습니다. 기존 컴퓨터에서 선택할 때. 그러나 실제로 이 알고리즘은 작은 모듈로 값(소수로 분해되어야 하는 정수)이 있는 RSA 키에만 작동했기 때문에 실제 키를 크래킹하는 데 거의 사용되지 않는 것으로 나타났습니다. 이 알고리즘은 큰 숫자를 인수분해하는 데 적합하지 않은 것으로 나타났습니다. 중국 연구원들은 양자 방법의 도움으로 슈노르 알고리즘의 한계를 피할 수 있었다고 주장합니다.
회의론 일부 암호 작성자로부터 사실 때문이다 중국 연구원의 기사가 증명하는 방법을 작은 숫자에만 적용, Schnorr의 알고리즘이 작동하는 것과 거의 동일한 순서입니다. 크기 제한을 초과했다는 주장에도 불구하고 아직 증거나 세부 정보가 제공되지 않았습니다. 실제로 이 방법은 48큐비트 양자 컴퓨터를 사용하여 10비트 정수를 분해하는 것으로 표시됩니다.
Shor의 알고리즘은 공개 키 암호 시스템을 기반으로 하는 정보 보안에 심각하게 도전했습니다. 그러나 널리 사용되는 RSA-2048 체계를 깨기 위해서는 수백만 개의 물리적 큐비트가 필요하며 이는 현재의 기술 능력을 훨씬 능가합니다. 여기에서는 고전적인 격자 감소를 양자 퍼지 최적화 알고리즘(QAOA)과 결합하여 정수 분해를 위한 범용 양자 알고리즘을 보고합니다.
필요한 큐비트 수는 O(logN/loglogN)이며 정수 비트 길이 N에서 부선형이므로 현재까지 가장 큐비트를 절약하는 분해 알고리즘입니다. 우리는 양자 장치에서 가장 큰 정수인 48개의 초전도 큐비트로 최대 10비트의 정수를 분해하여 알고리즘을 실험적으로 시연합니다. 우리는 알고리즘을 사용하여 RSA-372에 도전하려면 2048개의 물리적 큐비트와 수천 개의 깊이를 가진 양자 회로가 필요하다고 추정합니다. 우리의 연구는 오늘날 시끄러운 양자 컴퓨터의 적용을 가속화할 수 있는 큰 가능성을 보여주고 현실적인 암호화 중요성의 큰 정수를 분해할 수 있는 길을 열어줍니다.
372개의 물리적 큐비트가 RSA-2048 키를 분해하는 데 충분할 것이라는 가정은 이론적이므로 Schnorr의 알고리즘을 기반으로 하는 양자 방법은 동일한 스케일링 문제가 있고 숫자를 분해할 때 작동하지 않을 가능성이 매우 높습니다. .
스케일링의 문제가 정말로 해결된다면, 큰 소수 인수분해의 복잡성에 기반한 암호 알고리즘의 보안은 예상대로 장기적으로가 아니라 이미 오늘날 약화될 것입니다.
마지막으로, 그것에 대해 더 알고 싶으시면 자세한 내용을 참조하십시오. 다음 링크.