많은 설계자가 암호화 체계에 80 비트 보안이 있다고 주장했습니다. 그렇다면 일종의 CPU를 사용하는 80 비트 보안 RSA와 같은이 80 비트 보안 암호화 체계에 접속하는 시간을 계산하는 방법은 무엇입니까?
댓글
- 80 비트 RSA는 다음을 사용하여 순식간에 깨질 수 있습니다. GMP-ECM . RSA 분해 레코드에 대한 자세한 내용은 이 를 참조하세요. 80 비트 보안에 대한 자세한 내용은 여기 를 참조하세요. 키 크기 선택은 이 를 참조하세요.
- 답변 해 주셔서 감사합니다. 이제 128 비트 보안을 예로 들어 보겠습니다. 128 비트 보안은이 방식을 공격하기위한 2 ^ 128의 기본 동작을 의미합니다. 이것이 사실입니까? 그리고 기본 연산은 일반 곱셈 또는 덧셈을 의미합니까? 그리고이 계획을 공격하는 구체적인 시간을 계산하는 방법은 무엇입니까? 2 ^ 128은 일반 곱셈 또는 덧셈을 수행하는 시간을 곱합니까?
- ah 그래서 귀하의 질문은 $ n $ -bit 보안이 무엇을 의미하는지입니다. ' 이에 대한 Q / A를 찾으려고합니다. 간단히 말해서 시스템을 중단하려면 $ 2 ^ n $ 단계가 필요하며, 여기서 " 단계 "는 느슨하게 정의됩니다. 대칭 암호화의 경우 일반적으로 " 하나의 암호화 또는 해시만큼 작동합니다 ". 비대칭 암호화에 대한 이론적 작업의 경우 " 단계 "는 " 한 그룹 ( 또는 필드) 연산 또는 하나의 해시 ". RSA의 경우 1 개의 모듈 식 곱셈 mod N (공개 키) 또는 1 개의 해시가 될 수 있습니다. 그러나 실제로 $ n $ 비트 보안은 종종 다음 용도로 사용됩니다. $ n $ 비트 보안으로 대칭 암호를 해독하는 것만 큼 많은 (컴퓨터) 작업.
- 64 비트 불안정 . Summit과 같은 슈퍼 컴퓨터는 1 년에 $ 2 ^ {72} $에 도달 할 수 있습니다. 그러나 비트 코인 채굴 자와 같은 전용 그룹은 1 년에 $ 2 ^ {92} $에 도달 할 수 있으므로 80 비트는 더 이상 안전하지 않습니다. 다중 표적 공격이 가능한 경우 AES-128도 모든 표적에 안전하지 않은 경우 여기와 다중 표적 공격이란 무엇입니까? 및 여기 AES-128이 완전히 고장 났습니까?
- @fgrieu 답변 해 주셔서 감사합니다. 또한 2 ^ {128}을 클럭 사이클로 볼 수 있는지 알고 싶습니다. 실행 시간은 시계 주기로도 측정 할 수 있습니다.
답변
질문은 크게 요약됩니다. 받는 사람 :
주어진 값에 대해 $ n $ 비트 보안이 실제로 의미하는 것은 무엇입니까? of $ n $ ?
TL; DR : 다음을 사용하는 우수한 대칭 암호만큼 안전합니다. $ n $ 비트 키
클래식을 사용하는 공격자로 제한하더라도 더 정확한 정의는 없습니다. 이 대답처럼 컴퓨터 (양자 컴퓨터가 아님).
일반적으로 인정되는 의미 중 하나는 시스템을 파괴하는 “단계”의 수가 로 여겨진다는 것입니다. $ 2 ^ n $ ; 또는 더 정확하게는 $ s $ “단계”로 시스템을 깨뜨릴 확률이 $ s \, 2 ^ {-n} $ 모든 $ s $ . 그러나 “단계”와 “중단”은 정확하게 정의되지 않습니다.
대칭 암호화 이론에서 “단계”는 일반적으로 새 키를 사용하여 암호를 한 번 실행하는 것으로 간주됩니다. 이렇게하면 키가 $ n $ 비트 인 이상적인 암호는 $ n $ 비트 보안을 갖습니다. 무차별 대입 키 검색에서. 연습으로 이동할 때 공격자는 무차별 대입 키 검색에 얽매이지 않으며 “단계”의 정의는 수와 계산 비용면에서 하나에 필요한 하위 단계에 필적하는 여러 하위 단계가되어야합니다. 키 크기의 일반 텍스트에 대한 새 키로 암호 실행 . 이 정의를 사용하면 키가 $ n $ 비트 인 실제 암호는 최대 $ n $ – 비트 보안이며 그 이상을 목표로합니다.
해시로 이동할 때 단계의 정의는 수와 계산 비용면에서 필요한 하위 단계와 비교할 수있는 여러 하위 단계가 될 수 있습니다. 해시 출력 크기의 새 메시지를 해싱하는 경우 .
위의 여러 문제 중 하나는 메모리 및 메모리 액세스 비용을 계산해야하는지 여부에 대한 합의가 없다는 것입니다. 계산 비용. 사용자의 관점에서 볼 때 안전한 것은 계산하지 않는 것이지만 공격자에게는 이것이 가장 중요 할 수 있습니다.
비대칭 암호화와 관련하여 “단계”의 정의는 더욱 모호해집니다. RSA처럼.이론적으로 “단계”는 암호 시스템에 사용되는 대수 구조에서 하나의 계산 일 수 있습니다. RSA의 경우 임의의 정수 pan class = “math-에 대한 모듈 식 곱셈 $ (a, b) \ mapsto a \, b \ bmod N $ 평가 1 회 $ [0, N) $ 의 container “> $ a $ 및 $ b $ , 여기서 $ N $ 은 공개 모듈러스입니다. 그러나이를 실행으로 옮기는 데 문제가 있습니다. 특히 RSA의 경우 가장 잘 알려진 공격은 iv id = “c9e617e375″를 사용하여 공개 모듈러스 $ N $ 를 인수하는 것입니다. >
GNFS 알고리즘. 계산 비용은 모듈 식 곱셈과 거의 유사하지 않은 연산과 메모리 및 메모리 액세스가 차지하는 실제 비용이 차지합니다. TL; DR의 모호한 정의를 다시 사용합니다.
이 80 비트 보안 암호화 체계를 공격하는 시간을 계산하는 방법은 다음과 같습니다. 일종의 CPU를 사용하는 80 비트 보안 RSA?
“80 비트 보안 RSA”는 80 비트 공용이있는 RSA로 이해되지 않습니다. 모듈러스 $ N $ , 이는 최종적으로 안전하지 않습니다. 크기가 $ N $ 인 경우 그와 이전 경험을 기반으로 난이도를 추정 할 수 있습니다 (이 및 해당 링크). 그러나 우리는 그렇지 않으며 80 비트 보안을 사용하는 RSA의 $ N $ 크기에 대한 합의가 없습니다. 1024 비트가 자주 인용되지만 가설에 따라 다릅니다. , 그리고 누구에게 물어 보면, 그것은 너무 많거나 너무 적습니다. 따라서 가장 좋은 방법은 RSA에 대해 이야기하고 있다는 것을 무시하고 다음으로 돌아가는 것입니다. 80 비트로 좋은 대칭 암호를 해독하는 데 필요한 시간만큼 키입니다.
다음으로 이동합니다. $$ \ text {Time} = \ frac {2 ^ n \ times k \ times p} {\ text {Frequency } \ times \ text {Number-of-CPUs}} $$ 여기서 $ n $ 는 비트 단위의 보안 수준, $ k $ 는 매우 최적화 된 알고리즘과 $ p $ 를 사용하여 양호한 암호를 평가하기위한 CPU주기 수의 추정치입니다. 적의 성공에 대한 잔여 확률입니다. 관점에 따라 $ k = 1 $ (세부 사항을 검토하지 않아도 됨), $ k = 32 $ (범용 컴퓨터를 사용하는 좋은 암호에 대한 최선의 공격보다 여전히 적기 때문입니다) 또는 그 이상. 관점에 따라 $ p = 1 $ (합법적 인 사용자의 관점에서 가장 신중함), $ p를 사용할 수 있습니다. = 1 / 2 $ (블록 암호의 경우 예상 시간 산출) 또는 보안 마진을 원할 경우 더 작은 $ p $ ¹.
예 : $ n = 80 $ , $ k = 1 $ , $ p = 1 / 1000 \ approx2 ^ {-10} $ , $ \ text {Frequency} = 4 \ text {GHz} \ approx2 ^ {32} \ text {s} ^ {-1} $ , $ \ text {Number-of-CPUs} = 1000 \ approx2 ^ {10} $ , $ \ text {Time} \ approx2 ^ {80-10-32-10} \ text {s} = 2 ^ {28} \ text {s} $ , 즉 약 8 년입니다. 즉, 1000 개의 CPU는 기술적으로 쓸모 없게 될 때까지 80 비트 대칭 암호화에 대해 성공할 확률이 매우 적습니다.
다른 한편으로 1000 개의 CPU는 전 세계 CPU 및 비트 코인 채굴은 ASIC를 설계하고 대량으로 구축하고 운영을위한 에너지 비용을 유지할 수있는 능력을 가진 적에게 80 비트 암호화가 더 이상 충분하지 않다는 것을 결론적으로 보여줍니다. 이 를 참조하세요.
¹ $ p $ 용어 이 공식은 합법적 인 사용자의 관점에서 가장 신중하지만 많은 공격 시나리오에서 $ \ text {Time} $ 을 과소 평가합니다. 예를 들어, 충돌 검색에서 올바른 용어는 $ \ sqrt p $ 와 비슷합니다.