RSA 알고리즘

1) 소수 입력받기 , 서로수 체크

 

SCANNER를 통해 값을 소수 p,q 를 입력받습니다. 이때 두값이 서로수인지 체크를 하기위하여 numCheck()를 호출합니다. numcheck()는p,q를 파라미터로 받아서 두 수중 큰값을 기준으로 I값을 1씩 감소시켜 p,q를 나누어서 나머지가 0이면 해당 I값을 result값에 값을 넣어주고 최대공약수의 성질에 맞게 result가 1이면 해당 두값은 서로수 임을 확인하고 ture를 리턴 그렇지 않으면 false를 리턴해서 서로수를 확인합니다.

 

 

2) 암호화키 e 생성 , 복호화키 d 생성 , n 생성

 

 

n = p*q로 n에는 14가 들어갑니다.

 

2. 오일러파이 함수 = (p-1)(q-1) 이라는 공식에서 1<e<오일러파이함수 중 e를 5로 택하였습니다.

 

3. e * d mod 14 =1 의 공식으로 d는 11를 택하였습니다.

 

 

 

3) 평문을 입력하고 암호화와 복호화 과정

 

msg 는 평문을 받는 배열로 scanner 객체로 입력받은 값인 평문의 길이 만큼 msg 배열크기를 지정했습니다. 이후 for 문과 charAt을 통해 평문의 글자 하나씩 msg에 넣어 주었습니다. 그리고 encrypt_Msg(msg,e,n)을 호출합니다. 매개변수 msg는 암호호할 평문, e는 암호화키입니다. encrypt_Msg의 리턴값으로 암호화된 값의 배열을 받습니다. 이 암호화된값이 들어있는 배열을 decrypt_Msg(en_msg,d,n)을 호출하면서 , 복호화키 d 와 함께 넣어주어 복호화를 진행합니다.

 

 

 

4) 암호화 알고리즘

 

암호화된 값이 있는 배열의 수만큼 for문을 수행합니다. RSA 암호화 공식 C = M^e mod N을 진행하기위하여 Math.pow를 사용하여 거듭제곱을 실행하고 %로 나머지를 계산해주었습니다 이때 암호화키 e는 5, n은 14가 입력됩니다. 이렇게 만들어진 결과를 txt 배열에 하나씩 넣어줍니다. 이렇게 만들어진 암호화 된 문자가 들어있는 배열을 리턴하여 이후 복호화과정에서 사용되어집니다.

 

 

 

 

5. 복호화 알고리즘

 

암호화된 문자가 들어있는 배열을 받아 복호화 공식인 M = C^d mod 14를 수행하기 위하여 Math.pow를 사용하여 거듭제곱을 실행하고 %로 나머지를 계산해주었습니다. 이 때 d는 11이 입력되었습니다. 이렇게 만들어진 복호화된 값을 읽어 출력시켜줍니다.

 

 

 

 

 

6. 실행화면

 

 

1. 소수 p는 2 , q는 7을 입력을 받습니다

2. 2와7이 서로수인지 체크합니다.

3. 소수 p, 소수q, n, 암호화 키 e, 복호화키 d를 출력합니다

4. 평문 3을 입력받습니다

5. encrypt_Msg(msg,e,n)를 호출하여 평문3을 암호화를 진행하고 결과는 5가 나옵니다.

6. decrypt_Msg(en_msg,d,n)를 호출하여 암호화된 값인 5를 복호화 합니다. 그결과 원래의 평문 3이 출력됩니다.

 

 

 

 

 

-소스코드 

import java.math.BigInteger;
import java.util.Scanner;

public class RSAtest {
    

    public static void main(String[] args){
    	
    	Scanner sc = new Scanner(System.in);
    	int p;
    	int q;
    	while(true) {
    		System.out.println("정수1을 입력해주세요");
    		p = sc.nextInt(); // 소수 p = 2
    		System.out.println("정수2을 입력해주세요");
    		q = sc.nextInt(); // 소수 q = 7 , n = 14
    		boolean check = numCheck(p,q);
    		if(check!=true) continue;
    		else break;
    	}
    	int n = p*q; // n = p *q 공개키
		int e = 5; // 오일러 파이 함수 = (p-1)(q-1)  임으로 1< e < 오일러 파이 함수로 e는 5로 택하였습니다.
		int d = 11; // e * d mod 14 = 1 임으로 (5 * d )mod 14 = 1 로 d=11로 택하였습니다.
		System.out.println("P : "+ p);
		System.out.println("Q: "+ q);
		System.out.println("N : "+ n);
		System.out.println("E : "+ e);
		System.out.println("D : "+ d);
		int[] msg;
		String input;
		sc.nextLine();
		System.out.println("평문을 입력해주세요.");
		input = sc.nextLine();
		msg = new int[input.length()]; 
		System.out.print("평문 : ");
		for (int i = 0; i < input.length(); i++) {
			msg[i] = Character.getNumericValue(input.charAt(i));
			System.out.print(msg[i]);
		}
		System.out.println();
		// 암호화
		int[] en_msg = encrypt_Msg(msg,e,n);
		// 복호화
		decrypt_Msg(en_msg,d,n);
	}
    public static boolean numCheck(int p , int q) {
    	int result = 0;
		if (p <= q) {
			for (int i = p; i > 0; i--) { // 정수1이 정수2보다 작을 때
				if ((p % i == 0) && (q % i == 0)) { // 정수1의 약수이면서 정수2의 약수인 수. 가장 클 때부터 시작
					result = i;
					break;
				}
			}
		} else {
			for (int i = q; i > 0; i--) {
				if ((p % i == 0) && (q % i == 0)) {
					result = i;
					break;
				}
			}
		}
		if (result == 1) {
			System.out.println("두 수는 서로소입니다."); // 최대공약수가 1이라는 말은 서로소라는 뜻.
			return true;
		} else {
			System.out.println("두 수의 최대공약수는 " + result + "입니다.");
			return false;
		}
	}

    //암호화 함수
	public static int[] encrypt_Msg(int txt[],int e ,int n) {
		System.out.println("암호화를 진행합니다.");
		for (int i = 0; i < txt.length; i++) {
			txt[i] = (int) (Math.pow(txt[i], e) % n);
			System.out.print(txt[i]);
		}
		System.out.println();
		return txt;
	}
	//복호화 함수 
	public static void decrypt_Msg(int txt[], int d , int n) {
		System.out.println("복호화를 진행합니다.");
		for (int i = 0; i < txt.length; i++) {
			txt[i] = (int) (Math.pow(txt[i], d) % n);
			System.out.print(txt[i]);
		}
		System.out.println();

		
	}
           
    }