RSA 문제

RSA problem

암호학에서 RSA 문제는 공개 키만 주어진 RSA 개인 키 작업을 수행하는 작업을 요약한다.RSA 알고리즘은 인자를 알 수 없는 복합 번호 N인 지수에 메시지를 전달한다.따라서 과제는 임의의 수인 modulo N의 eth 루트를 찾는 것으로 깔끔하게 설명할 수 있다.대규모의 RSA 키 크기(1024비트 초과)의 경우 이 문제를 해결하기 위한 효율적인 방법이 알려져 있지 않으며, 효율적인 방법이 개발되면 공개 키 암호화와 디지털 서명 모두를 위한 RSA 기반 암호 시스템의 현재 또는 최종 보안에 위협이 될 수 있다.

보다 구체적으로, RSA 문제는 RSA 공용 키(N, e)와 암호 텍스트 C(mod N)가 e 부여된 P를 효율적으로 계산하는 것이다.RSA공개 키의 구조물 N규모가 크semiprime(즉, 두개의 큰 소수의 제품), 2<>e<>N은 e coprime φ(N)할 것이라고 하며, 0≤ C<>N.C무작위로 이 범위 내에서 선택된다;완전한 정확성으로 문제를 지정하는 것은 또한 어떻게 N, e가 생성되는에 의존할 것이다를 지정해야 한다. 그 precRSA 랜덤 키페이어 생성 수단.

RSA 문제를 해결하기 위해 알려진 가장 효율적인 방법은 N이 충분히 크면 비실용적이라고 생각되는 과제인 계량 N을 먼저 인수하는 것이다(정수 인자화 참조).RSA 키 설정 루틴은 이미 이 주요 인자화(primary factorization)와 함께 공개 지수 e를 사설 지수 d로 변환하므로 정확히 동일한 알고리즘을 통해 N을 요소화하는 사람은 누구나 개인 키를 얻을 수 있다.그러면 C는 개인 키로 해독될 수 있다.

정수 인자화가 계산적으로 어렵다는 증거가 없듯이, RSA 문제도 마찬가지로 어렵다는 증거도 없다.위의 방법에 따르면 RSA 문제는 최소한 인수인계만큼 쉽지만, 아마도 더 쉬울 것이다.실제로, 이러한 결론을 가리키는 강력한 증거가 있는데, RSA 방법을 깨는 방법이 반드시 큰 반을 인수하는 방법으로 변환될 수 없다는 것이다.[1]이는 아마도 인수접근법의 순전히 지나친 과장법으로 볼 수 있을 것이다: RSA 문제는 우리에게 하나의 임의의 암호문을 해독하도록 요구하는 반면, 인수접근법은 모든 임의의 암호문을 해독하는 개인키를 드러낸다. 또한 임의의 RSA 개인키 암호화를 수행할 수 있다.이러한 같은 선에서, RSA 문제가 d를 요구하지 않더라도, 실제로 암호 해독 지수 d를 찾는 것은 계산적으로 N을 인수하는 것과 동등하다.[2]

RSA 문제 외에도 RSA 문제를 직접 해결하지 않고도 잠재적으로 악용할 수 있는 특별한 수학적 구조를 가지고 있다.RSA 문제의 최대 강점을 달성하려면 RSA 기반 암호 시스템도 OAEP와 같은 패딩 방식을 사용하여 RSA의 구조적 문제로부터 보호해야 한다.

참고 항목

참조

  1. ^ Boneh, Dan; Venkatesan, Ramarathnam (1998). "Breaking RSA may not be equivalent to factoring". Advances in Cryptology — EUROCRYPT'98. Lecture Notes in Computer Science. Vol. 1403. Springer. pp. 59–71. doi:10.1007/BFb0054117. ISBN 978-3-540-64518-4.
  2. ^ 이를 위한 알고리즘은 예를 들어 다음과 같다.

추가 읽기

  • RSA를 깨는 것은 인수인계만큼 어려울 수 있다, D.브라운, 2005.이 승인되지 않은 사전 인쇄는 RSA 문제를 스트레이트 라인 프로그램을 사용하여 해결하는 것이 팩토링 e가 작은 요소를 가지고 있는 만큼 어렵다는 것을 의미한다.
  • RSA를 일반적으로 중단하는 것은 팩토링, D와 동일하다.아가왈과 U. Maurer, 2008.본 Eurocrypt 2009 논문(링크는 프리프린트 버전에 대한 링크)은 일반 링 알고리즘을 사용하여 RSA 문제를 해결하는 것이 팩토링만큼 어렵다는 것을 증명한다.
  • e-th 루트가 팩토링보다 쉬워질 때, 앙투안 주스, 데이비드 나카체, 그리고 에마뉘엘 토마, 2007.본 Asiacrypt 2007 문서(사전 인쇄 버전에 대한 링크)는 RSA 문제의 일부 다른 특수 사례에 대한 오라클을 사용하여 RSA 문제를 해결하는 것이 인수보다 쉽다는 것을 증명한다.