[정보보호개론] Java로 RSA 암호문 해독하기 (RSA 복호화)

문제

RSA로 암호화된 값이 있습니다.

n=3173174654383

e=65537

C=2487688703

이 값들을 가지고 Plain Text와 d값을 구하는 것이 문제입니다.

문제풀이방법

RSA 암호문을 복호화하기 위해서는 M=C^d mod N의 공식을 사용해야합니다.

다시말해, M값을 구하기 위해서는 C, d, N을 알아야 한다는 것 입니다.

일단 문제에서 N과 C를 알려줬으므로 d를 구해야합니다.

d는 ed=1 mod Phi를 활용하면 구할 수 있으므로 Phi 를 알아야 하며, Phi는 N 을 활용하여 알 수 있습니다.

 

N=p*q 이므로 p와 q 값을 구해줍니다. 이때 p와 q는 소인수 분해로 나오는 수(소수)여야 합니다.

반복문을 활용하여 N을 1부터 3173174654383까지 나눠줍니다.

나머지가 0인 순간에 p가 결정되고, q도 자동으로 결정됩니다. (q=N/p 이므로)

p와 q를 알았으니 Phi도 구할 수 있습니다. Phi=(p-1)*(q-1) 이므로 Phi 값도 계산합니다.

ed=1mod(p-1)(q-1)=1mod(phi) 의 공식에 의해서 d값도 계산할 수 있습니다.

e는 65537으로 주어졌으므로 d=65537^(-1) mod (phi)입니다.

이를 계산하면 d값이 나오므로

M=C^d mod N에 대입할 변수들을 모두 구했습니다.

이렇게 해서 나온 결과를 정리해보면

p = 52673

q = 60271

phi = (p-1)*(q-1)=3174541440

d = 801567233

M = 1198485348

따라서 M이 1198485348입니다.

M값을 16진수로 변환하면 0x476f6f64 이며

이를 아스키코드에서 찾아보면 good임을 알 수 있습니다.

 

코드

import java.math.BigInteger; 
public class RSA { 
	public static void main(String[] args) { 
    	BigInteger n = new BigInteger("3174654383"); 
        BigInteger e = new BigInteger("65537"); 
        BigInteger C = new BigInteger("2487688703");
        BigInteger p = null; 
        BigInteger q = null; 
        BigInteger phi = null; // phi=(p-1)(q-1) 
        BigInteger d = null; 
        BigInteger M = null;
        for(BigInteger i = new BigInteger("2");i.compareTo(n)<0;i=i.add(BigInteger.ONE)){ //소인수 분해
        	if(n.mod(i).equals(new BigInteger("0"))){
            	p=i; //제일 작은 소인수 
                q=n.divide(p); 
                phi=p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE)); 
                System.out.println("p : "+p+", q : "+q+", phi=(p-1)*(q-1)="+phi);
                break;
            }
        }
	//ed=1mod(p-1)(q-1)=1 mod phi (phi=(p-1)(q-1)) 
    //d=e^(-1) mod phi 
    d=e.modPow(new BigInteger("-1"),phi); 
    System.out.println("d="+d); 
    // M = C^d mod N 
    M=C.modPow(d,n); 
    System.out.println("M :"+M);
    }
}