RSA decryption

import java.math.BigInteger;

public class RSAHW {
	
	public static void main(String[] args) {
		BigInteger n = new BigInteger("3174654383");
		BigInteger e = new BigInteger("65537");
		BigInteger C = new BigInteger("2487688703");
		BigInteger p = n;
		BigInteger q = new BigInteger("2");
		BigInteger pi; // (p-1)*(q-1)
		BigInteger k = new BigInteger("1");
		BigInteger d, M;
		
		while(p.compareTo(q)==1) { //p>q
			if(p.mod(q)==BigInteger.ZERO){
				p = p.divide(q);
				break;
			}
			else {
				q = q.add(BigInteger.ONE);
			}
		}
		System.out.println("p= "+p);
		System.out.println("q= "+q);
		p = p.subtract(BigInteger.ONE);
		q = q.subtract(BigInteger.ONE);
		pi = p.multiply(q);
		BigInteger tmpResult;
		
		while(true) { //ed = k*pi + 1
			tmpResult = ((k.multiply(pi)).add(BigInteger.ONE)).mod(e);
			if( tmpResult == BigInteger.ZERO) {
				d = ((k.multiply(pi)).add(BigInteger.ONE)).divide(e);
				break;
			}
			else {
				k = k.add(BigInteger.ONE);
			}
		}
		System.out.println("d= "+d);
		
		M = C.modPow(d, n);
		System.out.println("M= "+M);
		
		String plaintext = Integer.toHexString(1198485348);
		System.out.println("Plaintext= "+plaintext);
		
	}
}

---

 

우선 주어진 수는 n, e 와 암호문인 C 이다. Java의 BigInteger class를 이용하여 코딩을 하였다.

우선, n= p*q (p,q는 소수)로 이루어져서 p에는 n값을, q에는 2를 넣어 소인수 분해를 하듯이 while문을 작성하였다.

p mod q를 하여 나누어 떨어지지 않으면 q값을 1씩 증가하여 나누어 떨어질 때 까지 진행하여 p, q 값을 구한다.

또한, k를 몫으로 두고 ed = k(p-1)(q-1)+1 을 이용하여 private key인 d를 구할 수 있다.

M = C^d mod n 을 이용하여 암호화되기 전 message를 알 수 있고 이를 16진수로 변경하여 아스키코드표를 참고하면 'Good' 이라는 메시지를 얻을 수 있다!

 

2020/04/18 - [Language/Java] - Java 기반의 AES 복호화 프로그램