소수를 암호 알고리츰에 사용하는 이유?

Question

드라마에서 소수(prime number)로 암호화를 한단 얘기를 들었는데요.

제대로 들은건지 모르겠지만 소수로 암호화 알고리즘을 만드는 이윤는 무엇인지 궁금해요?

Answer 1

안녕하세요.

소수(prime number)를 암호 알고리즘에 사용하는 이유는 그들의 수학적 특성과 계산상의 복잡성 때문입니다. 소수는 공개키 암호화 방식에서 중요한 역할을 하는데, 이는 특히 RSA 암호화 알고리즘에서 두드러집니다. RSA는 두 개의 큰 소수를 선택하고 그 곱으로 만들어진 합성수를 이용하여 공개키와 비밀키를 생성합니다. 소수가 중요한 이유는 그들의 곱을 이용한 수 N의 소인수분해가 계산적으로 매우 어렵기 때문입니다. 이러한 계산의 어려움은 암호화된 메세지를 복호화할 수 있는 키를 소유한 사람만이 가능하게 함으로써, 정보의 안전성을 보장합니다.
또한, RSA 알고리즘에서는 오일러의 φ(피) 함수가 중요한 역할을 합니다. 이 φ(N)은 N을 구성하는 두 소수 p와 q에 대해 φ(N)=(p−1)(q−1)로 정의됩니다. 이 함수는 암호화와 복호화 과정에서 사용되는 키의 생성에 필수적입니다. 공개키는 누구나 접근 가능하지만, 비밀키는 해당 수의 소인수분해를 통해서만 유추할 수 있으므로, 소수를 사용함으로써 암호의 안전성이 크게 증가합니다.