it-swarm-korea.com

보안 고려 사항으로 인해 RSA 공개 지수는 {3, 5, 17, 257 또는 65537}에만 있어야합니까?

내 프로젝트에서 4451h의 공개 지수 값을 사용하고 있습니다. 상용 RSA 암호화 라이브러리를 사용하기 시작할 때까지 안전하다고 생각했습니다. 이 지수를이 라이브러리와 함께 사용하면 예외가 발생합니다.

이 라이브러리의 개발자에게 연락하여 다음과 같은 응답을 받았습니다. "이 기능은 RSA 키에 대한 일부 공격을 막기위한 것입니다. 결과적으로 지수 값은 {3, 5, 17, 257 또는 65537}로 제한됩니다. 위험이 클 수 있으므로 여전히 조사 중입니다. "

내 인생에서 처음으로 RSA를 깨는 데 {3, 5, 17, 257 또는 65537} 이외의 값이 사용된다고 들었습니다. 부적절한 패딩이 취약한 3 만 사용하는 것을 알았습니다.

정말 그래요? 분명히 다른 라이브러리를 사용할 수는 있지만 그러한 답변을 얻은 후에 솔루션의 보안에 대해 걱정했습니다.

70

공개 지수가 "올바른"(즉, 상대적으로 소수 p-1 모든 소수에 대해 p 인 한, RSA의 단기 또는 장기 공개 지수에 대해서는 알려진 약점이 없습니다. 계수를 나누는 것).

If 작은 지수를 사용합니다 and 암호화에 패딩을 사용하지 않습니다 and 여러 개의 공개 키를 사용하면 메시지가 위험에 노출 될 수 있습니다. if e = 3, 공개 키로 m 메시지를 암호화합니다 n1, n2n, 그러면 c나는 = m mod n나는i = 1 ~ 3. Chinese Remainder Theorem 에 의해 m을 다시 빌드 할 수 있습니다 mod n12, m으로 밝혀 짐 (모듈로없이) n12는 더 큰 정수입니다. (비 모듈 식) 큐브 루트 추출은 m을 추출하기에 충분합니다.

여기서 약점은 작은 지수가 아닙니다 . 오히려 암호화에 부적절한 패딩 (즉, 패딩이 아님)을 사용하는 것입니다. 패딩은 암호화 또는 서명 여부에 관계없이 RSA 보안에 매우 중요합니다. - PKCS # 1 에 설명 된 것과 같은 적절한 패딩을 사용하지 않으면 많은 약점이 있으며 위 단락에 요약 된 것이 가장 크지 않습니다. 그럼에도 불구하고, 누군가가 지수 크기 관련 약점을 언급 할 때마다, 그는이 사건을 어느 정도 직접적으로 언급합니다. 그것은 조금 오래되고 잘못된 지식입니다. 때로는 big 지수에 대한 금지로 거꾸로 나타납니다 (신화이므로 역 신화도 신화이며 더 이상은 아닙니다. 덜-입증 된); 나는 이것이 당신이 여기서 관찰하는 것이라고 믿습니다.

그러나 큰 공개 지수를 피해야하는 몇 가지 이유를 찾을 수 있습니다.

  • 소규모 공개 지수는 효율성을 향상시킵니다 (공개 키 운영).

  • 작은 private 지수에 대한 보안 문제가 있습니다. 비공개 지수 길이가 공개 지수 길이의 29 % 이하인 경우 키 복구 공격이 설명되었습니다. 개인 지수를 짧게 만들려면 (예 : 개인 키 작업 속도를 높이려면) 큰 공개 지수를 사용해야합니다 (계수만큼 큰). 공개 지수를 짧게 요구하는 것은 일종의 간접 대책으로 간주 될 수 있습니다.

  • 널리 배포 된 일부 RSA 구현은 대규모 RSA 공개 지수에 질식했습니다. 예 : Windows의 RSA 코드 (HTTPS 용 Internet Explorer에서 사용되는 CryptoAPI)는 단일 32 비트 Word 내에서 공개 지수를 인코딩해야합니다. 더 큰 공개 지수로 공개 키를 처리 할 수 ​​없습니다.

그래도 "위험이 클 수 있습니다"는 일반적인 정당화처럼 보입니다 ( "이것은 보안 문제입니다"는 "우리는 구현하지 않았지만 어떤 종류의 게으름도 인정하고 싶지 않습니다"라고 말하는 일반적인 방법입니다).

64
Thomas Pornin

개발자는 단순히 틀렸다. 지수 0x4451 (10 진수 17489)에는 아무런 문제가 없습니다. 보안 문제를 일으키지 않습니다.

오래 전에 사람들은 토마스 포르노 인이 여러 명의 수신자에게 같은 메시지를 보내면서 설명한 공격 때문에 작은 지수가 문제라고 생각했습니다. 그러나 오늘날 우리는 지수가 그것과 아무 관련이 없다는 것을 이해합니다. 문제는 부적절한 패딩이었습니다. 패딩을 올바르게 사용하면 이러한 공격을 방지 할 수 있습니다. 그 소금 가치가있는 모든 암호화 라이브러리는 적절한 패딩을 사용하는 것이 훨씬 낫습니다 (그렇지 않으면 훨씬 더 나쁜 문제가 있습니다).

따라서 암호화 라이브러리가 해당 지수의 사용을 평평하게 금지 할 이유가 없습니다.

즉, 성능 관점에서 지수가 작을수록 성능이 향상됩니다. 최상의 성능을 제공하고 알려진 보안 문제가 없기 때문에 최선의 선택은 e = 3입니다. (실제로 e = 2가 더 우수합니다. 라빈 암호화라고도합니다. 그러나이 체계는 잘 알려져 있지 않으며 약간 다른 코드가 필요하므로 널리 사용되지 않습니다.)

21
D.W.

이 다섯 숫자는 Fermat primes 입니다.

그것들은 형태 2이므로 k  + 1, 암호화는 m e  = m · ((( m 2)2... k ...)2일반적인 경우 에서 비슷한 크기의 지수로 지수보다 단순하고 빠릅니다.

소수이므로 e 가 ( p − 1) ( q − 1) 단지 e 나누지 않습니다.

따라서 이것은 보안보다는 속도 나 관습에 관한 것입니다. 효율적이라는 데 문제가있는 것은 아닙니다. 그러나 확실히하기 위해 other answer 제안 된대로 참조를 요청하십시오.

이 게시물 도 참조하십시오.

19
aaz

RSA 키의 공개 지수가 {3,5,17,257,65537} 집합에만 있어야하는 이유는 없습니다. 언급했듯이 구현 오류의 부정적 영향 (예 : 부적절한 패딩)이 더 클 수 있으므로 3 또는 5와 같은 작은 지수는 사용하기에 더 위험합니다. NIST는 2 ^ 16보다 큰 공개 지수 만 허용하지만 결정의 이유를 모르겠습니다.

사용하는 라이브러리 개발자가 제공 한 답변에 만족하지 말고 구체적인 참조를 요청하십시오. 너무 자주, 일부 종이가 잘못 이해되었습니다. 예를 들어 일부 개발자가 Phong Nguyen의 "암호화 소프트웨어를 신뢰할 수 있습니까? 암호화 결함에 GNU Privacy Guard v1.2.3") 섹션 4를 읽고 잘못된 결론에 도달했다고 상상할 수 있습니다. 이 백서에서는 GnuPG에 의해 생성 된 공개 키가 65539와 같은 비정상적인 값으로 밝혀지면 공격자가 비밀 키에 대해 약간의 정보를 알게된다는 결론을 내립니다 .GnuPGs 키 생성 알고리즘은 개선되지는 않지만 65539는 공개 키가 아닙니다.

8
Accipitridae

공개 지수의 다른 값이 취약하다는 언급을 찾을 수 없었습니다. RSA 알고리즘에 대한 RSA.com 가이드에 따르면 성능상의 이유로 2의 거듭 제곱에 가까운 공개 지수를 사용하는 것이 좋습니다.

Wikipedia 에 따르면 NIST는 65537보다 작은 공개 지수를 허용하지 않습니다. 작은 지수는 제대로 채워지지 않으면 문제가되기 때문입니다.

7
Andreas Arnold