RSA는 아래의 형태와 같이 암호화되고 복호화 되는 공개키 암호 시스템이고 주로 적은 양의 데이터나 전자서명에 사용합니다. 또한 RSA 암호는 대칭키인 DES나 AES보다 속도가 느리므로 메시지 암호화에는 쓰이지 않고 주로 키를 암호화하는데 쓰입니다.
 일단 RSA 암호화와 복호화는 모듈로 연산으로 수행되고 식으로 나타내면 다음과 같습니다.
암호문 C의 길이는 n의 길이 따라 결정되므로 n 이상의 평문을 암호화할 수 없습니다. mod 연산(나머지 연산) 때문에 결과값의 범위는 0 ~ n - 1까지이기 때문입니다. 평문(M)의 공개키(e) 제곱을 n으로 나눈 나머지가 암호문(C)인데 암호문에 개인키(d) 제곱을 n으로 나눈 나머지가 평문으로 나옵니다. 이렇게 되는 이유는 밑에서 다시 설명하겠습니다. 모듈로 연산은 나머지 연산으로 5 mod 3이라고 하면 5를 3으로 나눈 나머지라는 뜻이므로 결과 값은 2가 됩니다. 합동은 도형에서 서로 완전히 겹쳐지는 도형 사이의 관계를 뜻하지만 여기서는 나머지가 서로 같은 두 정수 사이의 관계를 뜻합니다. 예를 들면 5 ≡ 8 mod 3 은 5를 3으로 나누었을 때 나머지가 2이고 8도 3으로 나누었을 때 나머지가 2이므로 5와 8은 mod 3에 대해 합동 관계에 있는 것입니다. 더 쉽게 말하자면 나머지가 서로 같은 것을 합동이라고 생각하면 됩니다. 위에서 보면 알 수 있듯이 먼저 RSA 암호화/복호화를 하기 전에 개인키와 공개키를 먼저 생성해야 합니다. 공개키와 개인키를 만드는 방법은 다음과 같습니다.
아래와 같이 소수 p와 q를 선택합니다. (원래 RSA 암호에서 쓰이는 소수는 1024비트가 넘는 큰 소수이지만 여기서는 계산의 편의성을 위해서 작은 소수를 선택하였습니다.)
여기서 말하는 소수는 0.1, 0.25와 같은 수가 아니라 약수가 1과 자기 자신 밖에 없는 수를 뜻합니다. (ex. 2, 3, 5, 7, ···)
φ(n)는 오일러 함수로 기약잉여계에서의 원소의 개수를 나타내는 함수입니다.라고 어렵게 이야기했지만 사실은 n과 서로소인 정수 집합의 원소의 개수를 뜻합니다.
gcd는 최대공약수를 뜻합니다. gcd가 1이라는 것은 두 정수의 관계가 서로소라는 뜻입니다. 즉, 두 정수의 공약수가 1밖에 없다는 뜻입니다. 이 값을 공개키로 하는 이유는 gcd 값이 1이어야 역원이 존재하고 그 역원이 개인키이기 때문입니다. 위의 정수들 중 공개키(e)로 3을 선택하겠습니다.
이 과정은 확장된 유클리드 알고리즘을 사용해야 합니다.
위의 식은 유클리드 알고리즘을 통해 아래와 같이 곱셈식으로 표현되고 나머지가 1(여기서는 더하기(+) 이후의 숫자를 말합니다.) 될 때까지 반복해줍니다.
그리고 확장된 유클리드 알고리즘을 사용하여 공개키 e(여기서는 3이 공개키)의 역원 d를 구해줍니다. + 1을 기준으로 나머지는 좌변으로 넘겨주면 아래와 같은 식이 되고 3과 곱해져 있는 7이 개인키 d가 됩니다.
개인키 d는 말 그 자체로 개인이 가져야 되는 키이므로 자신을 제외한 어느 누구도 알아서는 안되는 값입니다. 또한 p, q를 알면 당연히 개인키를 알아낼 수 있기 때문에 비밀로 해야 되고 φ(n)을 통해 p와 q를 알아낼 수 있기 때문에 φ(n)도 비밀로 해야 합니다. 공개키 e도 말 그 자체로 공개되는 키이고 n은 암호화 복호화 할 때 모듈로 연산을 하기 위해서 공개가 되어야 합니다. 그러나 n을 공개해도 되는가에 대해 의문을 가질 수 있으시겠지만 큰 소수 p와 q를 곱해서 n이 나온다는 것은 쉽게 알 수 있어도 n에서 p, q를 구하는 것은 쉽지 않습니다. 그렇기 때문에 n은 공개가 돼도 효율적인 소인수분해 알고리즘이 없는 이상 계산적으로 안전합니다. 공개키와 개인키를 만들었으니 RSA 암호화와 복호화를 할 차례입니다.
RSA 암호는 아래와 같은 증명으로 암호문을 개인키로 제곱하였을 때 평문이 나온다는 것을 알려줍니다.
|
공개키 암호화 예제 - gong-gaeki amhohwa yeje
관련 게시물
저작권 © 2024 nguoilontuoi Inc.
