이산수학 문제를 푸는데 RSA 공개키 암호 시스템을 복호화하라는 문제를 마주했다. 마침 자바도 좀 배웠겠다, 한번 이걸 프로그래밍해보면 재미있겠다 하는 마음이 들었다.

코드와 결과

코드

public class FindPrivateKey { 
	
	public static void main(String[] args) {
		// RSA 암호 시스템의 암호화와 복호화
		System.out.println("<RSA 암호 시스템>\n");
		
		/**송신자의 정수 a 암호화 과정**/
		// 두 개의 소수 p,q와 정수 n, 암호화하고자 하는 a를 입력받음.
		int p = Integer.parseInt(args[0]); 
		int q = Integer.parseInt(args[1]); 
		int n = Integer.parseInt(args[2]); // 공개키
		int a = Integer.parseInt(args[3]); // 암호화하고자 하는 메시지
		
		System.out.println("-------------송신자의 암호화 과정-------------");
		System.out.println("송신자가 암호화할 메시지 >> " + a);
		
		int z = p*q; // 공개키
		int pi = (p-1)*(q-1);
		
		System.out.println("z >> " + z);
		System.out.println("pi >> " + pi);
		
		int s = 1; //s의 초기값 임의 설정
		while(s > 0 && s < pi) {
			if (((n*s) % pi) == 1) { // ns mod pi = 1을 만족하는 s를 개인키로 사용함.
				System.out.println("개인키 s >> " + s );
				break;
			}else
				s++;
		}
		
		int c = (int) (Math.pow(a, n) % z); // c는 수신자에게 보낼 암호화된 메시지
		System.out.println("수신자에게 보낼 암호화된 메시지 c >> " + c);

		/**수신자의 정수 a 복호화 과정**/
		System.out.println("\n-------------수신자의 복호화 과정-------------");
		int a2 = (int) (Math.pow(c, s) % z); // a2는 a를 구하기 위해 수신자가 복호화한 값
		System.out.println("수신자가 복호화한 메시지 >> " + a2);
	}
}

Run Configuration

결과

Problem

이론적으로는 위와 같이 코드를 짜는 게 맞다. 하지만 수신자에게 보낼 암호화된 메시지인 c값이 이상하게 나왔다. 원래는 168이 아닌 113이 나와야 한다. c가 이상하니까 이를 이용해서 복호화하는 수신자의 메시지 값도 이상하게 구해졌다.

원인

내가 계산하고자 한 값이 감당 가능한 숫자의 범위를 벗어난 것이 원인이었다. 인터넷에 검색해보니, 자바에서는 이렇듯 큰 수를 다룰 때 BigDecimal이나 BigInteger 등을 사용해서 표현한다고 한다.
여기 https://coding-factory.tistory.com/604 에 잘 나와있다.
여기에서도 https://stackoverflow.com/questions/4591206/arithmeticexception-non-terminating-decimal-expansion-no-exact-representable 도움을 받았다.