RSA의 보안이란?
RSA는 가장 널리 사용되는 공개키 암호 알고리즘 중 하나로, 큰 소수의 곱을 인수분해하는 것이 수학적으로 매우 어렵다는 사실에 기반하여 보안성을 확보합니다. 하지만 RSA 역시 다양한 공격 기법에 노출될 수 있으며, 이를 이해하고 사전에 대비하는 것이 중요합니다. 아래에서는 RSA를 위협하는 대표적인 공격 유형과 각각의 대응 방법을 살펴봅니다.
1. 평문 공격(Plain Text Attack)
평문 공격은 세 가지 세부 유형으로 분류할 수 있습니다.
짧은 메시지 공격(Short Message Attack)
공격자가 평문의 일부 블록을 이미 알고 있다고 가정하는 공격입니다. 이 가정이 참이라면, 공격자는 알고 있는 각 평문 블록을 직접 암호화해 보고 그 결과가 알려진 암호문과 일치하는지 확인함으로써 정보를 추론할 수 있습니다.
이러한 짧은 메시지 공격을 방지하려면, 암호화하기 전에 평문에 패딩(padding)을 추가하는 것이 권장됩니다.
순환 공격(Cycling Attack)
순환 공격에서는 공격자가 암호문이 평문에 어떤 형태의 치환(permutation)을 적용하여 얻어졌다고 가정합니다. 이 가정이 맞다면, 공격자는 반대 과정을 수행하여 알려진 암호문에 치환 연산을 계속 반복함으로써 원래의 평문을 얻어내려 시도할 수 있습니다.
비은폐 메시지 공격(Unconcealed Message Attack)
이론적으로 일부 극히 제한적인 평문 메시지의 경우, 암호화 결과가 원래 평문과 동일하게 나오는 경우가 발견되었습니다. 이런 상황이 발생하면 원래의 평문 메시지는 더 이상 비밀로 유지될 수 없습니다. 이러한 이유로 이 공격은 '비은폐 메시지 공격'이라고 불립니다.
2. 선택 암호문 공격(Chosen Cipher Attack)
선택 암호문 공격에서는 공격자가 확장 유클리드 호제법(Extended Euclidean Algorithm)을 활용하여 암호문으로부터 평문을 도출해낼 수 있습니다.
3. 인수분해 공격(Factorisation Attack)
RSA의 전체적인 보안은 공격자가 N을 두 개의 소인수 P와 Q로 분해하는 것이 불가능하다는 가정에 의존합니다. 만약 공격자가 N = P × Q라는 식에서 P 또는 Q를 찾아낼 수 있다면, 개인키(private key)까지 알아낼 수 있게 됩니다.
다만 N이 최소 300자리(10진수 기준) 이상의 길이를 가진다면, 공격자가 P와 Q를 쉽게 찾아내는 것은 불가능하므로 인수분해 공격은 실패하게 됩니다.
4. 암호화 키에 대한 공격(Attack on the Encryption Key)
RSA의 수학적 구조에 능숙한 사람들은 때때로 RSA가 매우 단순하다고 느낄 수 있는데, 그 이유는 공개키 즉, 암호화 키 E로 매우 큰 숫자가 필요하기 때문입니다.
사실 큰 E 값을 사용하는 것이 RSA를 더 안전하게 만듭니다. 따라서 작은 E 값을 사용해 RSA의 연산 속도를 높이려고 하면, 암호화 키에 대한 공격이라는 잠재적 위협에 노출될 수 있습니다. 이를 방지하기 위해서는 E를 216 + 1 = 65537 또는 이 값에 가까운 수로 사용하는 것이 권장됩니다.
5. 복호화 키에 대한 공격(Attacks on Decryption Key)
복호화 키를 대상으로 하는 공격은 다음 두 가지로 나눌 수 있습니다.
노출된 복호화 지수 공격(Revealed Decryption Exponent Attack)
공격자가 어떤 방식으로든 복호화 키 D를 추측해낼 수 있다면, 해당 암호화 키 E로 암호화된 기존 암호문뿐만 아니라 미래에 전송될 메시지까지도 모두 위험에 처하게 됩니다. 이러한 노출된 복호화 지수 공격을 피하려면, 발신자가 P, Q, N, E의 새로운 값들을 함께 사용하는 것이 좋습니다.
낮은 복호화 지수 공격(Low Decryption Exponent Attack)
작은 복호화 키 D 값을 사용하면 RSA의 처리 속도를 높일 수 있어 매력적으로 보입니다. 그러나 이렇게 하면 공격자가 낮은 복호화 지수 공격을 통해 복호화 키 D를 추측해낼 가능성이 커집니다.
결론
RSA의 보안은 큰 소수의 곱을 인수분해하는 어려움에 기반하지만, 짧은 메시지 공격, 선택 암호문 공격, 인수분해 공격, 키 관련 공격 등 다양한 위협에 노출될 수 있습니다. 안전한 RSA 운영을 위해서는 적절한 패딩 적용, 충분히 긴 키 길이 확보, E 값으로 65537 사용, 작은 복호화 지수 회피, 그리고 필요시 새로운 키 값으로 재생성하는 것이 핵심입니다.