문제 설명
RSA 암호화는 큰 수의 소인수분해가 어렵다는 점에서 기인한 공개키 암호화 시스템이다. 공개키 암호화란, 암호화와 복호화에 사용되는 키가 서로 다른 암호화 방식으로, 비대칭 암호화라고도 불린다. 다음은 RSA 암호화의 기본적인 원리이다.
1. 두 소수 p, q를 고른다.
2. N=p*q인 수 N을 구한다.
3. (p-1)*(q-1)과 서로소인 최소인 자연수 e를 구한다.
5. e*d mod (p-1)(q-1) = 1를 만족시키는 d를 구한다.
*모듈로 연산이란? A 나누기 B의 나머지를 A mod B = R 로 나타낸다.
6. 입력 받은 평서문을 e제곱한 후 N으로 나누어 암호문을 구한다.
이때, e는 공개키고, d는 개인키를 나타낸다. RSA 암호화에선 N과 e값만을 공개하고, d값은 데이터를 복호화하고자 하는 사람만 소유한다. 암호화된 메시지와 개인키를 출력하는 프로그램을 작성해보자.
**** 어떤 수와 서로소인 자연수를 구하기 위해선 다음을 활용한다 ****
유클리드 호제법을 이용한 최대공약수를 찾는 함수 선언한다. (int main() 앞에 따로 선언하기를 권장한다.) 아래 코드에 따르면, gcd(a, b)는 a와 b의 최대공약수의 값을 반환한다.
int gcd(int x, int y){
while (y!=0){
int temp=y;
y = x % y;
x = temp;
}
return x;
}
입력 설명
두 소수 p, q를 띄어쓰기를 기준으로 한 줄에 입력받는다. 그 다음 줄에 암호화하고자 하는 평서문을 입력 받는다.
(2<=p<1,000, 2<=q<1,000, 평서문은 100,000 이하의 정수형이다.)
출력 설명
첫째 줄에 암호화된 메시지와, d를 띄어쓰기를 구분으로 출력한다. 두번째 줄에는 N과 e를 띄어쓰기를 구분으로 출력한다.
입력 예시 Copy
3 11
5
출력 예시 Copy
14 3
33 3