[과제] RSA Decryption

문제

RSA 복호화 문제로 기본적으로 주어진 정보를 이용해 평문과 d을 구하면 된다. 주어진 정보는 다음과 같다.

n	e	C
3173174654383	65537	2487688703

 

 

 

풀이

우선 RSA 암호문을 복호화하기 위해서는 M=C^d mod N 공식을 이용해야 한다. M을 구하기 위해서는 C, d, N의 값이 필요한데 기본적으로 n과 C를 알려주고 있다.

 

이때,  ed = 1 mod phi, N=p*q 공식을 함께 이용하면 d를 구할 수 있다.

phi=(p-1)*(q-1) :  p와 q는 N을 소인수분해 하여 나온 소수를 의미한다.

import java.math.BigInteger;

class DecryptionRSA{
    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; //d=e^(-1) mod phi
    BigInteger M = null; //M=C^d mod N

    public void run(){
        find();
        System.out.println("p: "+p+" q:"+q+" phi:"+phi);

        d=e.modPow(new BigInteger("-1"), phi);
        System.out.println("d:"+d);

        M=C.modPow(d, n);
        System.out.println("M:"+M);
    

    public void find(){
        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));
                break;
            }
        }
    }
}
public class RSA {
    public static void main(String[] args) {
        DecryptionRSA rsa = new DecryptionRSA();
        rsa.run();
    }
}

 

최종적으로 이 문제를 풀며 나온 값들은 다음과 같다.

n	e	p	q	C
3173174654383	65537	52673	60271	2487688703
phi	d	M
3174541440	801567233	1198485348

 

1198485348을 16진수로 변환하면 476F6F64 이 된다. 16진수를 다시 아스키코드로 변환하면 good이 나온다.

 

결과

good