정보보호 RSA

RSA 문제

• 두 소수 p = 3, q= 11 or p = 7, q = 17 (두개 중 하나 이용)
• 임의의 공개키 비밀키 쌍을 생성한 다음 본인의 학번을
  암호화 하고 복호화 하시오.
  (년도 제외하고 2자리씩 암호화/복호화)
  예) 2007406002 -> 40, 60, 02 암호화/복호화

RSA 알고리즘

• RSA는 큰 정수의 소인수 분해를 할때 많은 경우의 수가 나오는 점을 이용해 암호화 시키는 알고리즘이다.
• 공개키 알고리즘으로 A와 B가 있다면 공개키와 개인키를 가지고 정보를 서로 파악할 수 있게 된다. 주로 서명이 필요한 전자상거래에 RSA 알고리즘이 쓰인다.

방식

1. A가 B에게 정보를 준다고 가정해보자
2. B는 공개키와 개인키가 있으며 A에게 공개키만 보낸다.
3. A는 그 공개키를 이용하여 정보를 암호화하고 B에게 보낸다.
4. B가 그 암호화된 정보를 받고 개인키를 이용해 복호화할 수 있다.

RSA 문제풀이

입력받는 학번이 12,50,51 이기 때문에 p = 3, q = 11을 했을 때 n이 33으로 n보다 큰 평문일때는 암호화 복호화가 안되는 문제가 있다. 그래서p = 7, q = 17을 선택해 주었다.

n 구하기

n은 p와 q의 곱으로 구할 수 있다.
n = p * q = 119

Φ(n) 구하기

Φ(n)은 n이 양의 정수 일때 Φ(n)은 n과 서로소인 1부터 n까지의 정수의 개수와 같다.
Φ(n) = (p - 1) * (q – 1) = 96

e 구하기

e는 1 < e < Φ(n)로써 1과 Φ(n) 사이에 있고 Φ(n)와 서로소인 e를 정해주면 된다.

• e는 공개키에 이용이 된다. e = 11 선택

d 구하기

(e * d) mod Φ(n) = 1

• e*d를 Φ(n)으로 나누었을 때 나머지가 1인 d를 구하면 된다.
• 이때 d는 개인키에 사용될 숫자이다.
• d는 확장 유클리드 알고리즘을 이용해서 구함
  d = 35

공개키, 개인키

공개키에 이용될 (n, e)와
개인키에 이용될 (n, d)를 구하였다.
공개키 = { 119, 11 }
개인키 = { 119, 35 }

---

평문이 12일때는
12^11 mod 119 = 108 로 암호화를 시키고
108^35 mod 119 = 12 로 복호화를 시키면 다시 평문으로 돌아오는 것을 알 수 있다.

---

마찬가지로 50일때는
50^11 mod 119 = 50 로 암호화를 시키고
50^35 mod 119 = 50 로 복호화를 시키면 다시 평문으로 돌아오는 것을 알 수 있다.
암호화를 했는데도 평문이 그대로 나왔다.

---

마지막으로 51일때는
51^11 mod 119 = 102 로 암호화를 시키고
102^35 mod 119 = 51 로 복호화를 시키면 다시 평문으로 돌아오는 것을 알 수 있다

import java.io.BufferedReader;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class RSA
{
	public static int extend_gcd(int a, int b)   
		// (e * d) mod pi = 1  ->  gcd(e,pi) =1
	    // -> e*d + pi * [] = 1 에서 d를 구하기
	{
		// 큰값 a로
	    int tmp;
	    if(a<b){
	        tmp = a;
	        a = b;
	        b = tmp;
	    }    
	    
		int [] r = {a, b};
		int [] s = {1, 0};
		int [] t = {0, 1};
		
		int q = r[0]/r[1];
		int remain = r[0] % r[1];
		
		
		while (remain>0) {
			q = r[0] / r[1];
			
			r[0] = r[1];
			r[1] = remain;
			int tempS = s[0];
			s[0] = s[1];
			s[1] = tempS-s[1]*q;
			int tempT = t[0];
			t[0] = t[1];
			t[1] = tempT-t[1]*q;
			
			remain = r[0]%r[1];
		}	
		// 음수면 a를 더해줌 그래도 결과는 동일
		if (t[1] <=0)
		{
			while (t[1]<=0)
			{
				t[1] += a;
			}
			return t[1];
		}
		else
		{
			return t[1];
		}
	}
	
		
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	int p = 7;
    	int q = 17;
        System.out.println("p : " + p);
        System.out.println("q : " + q);
    	
    	int n = p * q;
    	BigInteger nn = new BigInteger(Integer.toString(n));
    	
        int pi = (p-1) * (q-1);
        System.out.println("n : " + n);
        System.out.println("oil : " + pi);
        
        System.out.println("1부터 "+ pi + " 사이에 있고 " + pi + " 과 서로소인 수 e 값을 입력하세요");
    	String str = br.readLine();
        int e = Integer.parseInt(str);
        
        // d값을 찾는 연산
        int d = 0;
        d = extend_gcd(pi, e);
        System.out.println("d : " + d);
    	
        System.out.println("공개키 : { " + e + ", " + n + " }");
        System.out.println("개인키 : { " + d + ", " + n + " }");
         
        System.out.println("연도를 제외한 학번을 입력 하세요 + ex) 2018125051 -> 12 50 51");
    	String str2 = br.readLine();
        StringTokenizer st = new StringTokenizer(str2, " ");
        String a = st.nextToken();
        String b = st.nextToken();
        String c = st.nextToken();
        
        BigInteger aa = new BigInteger(a);
        BigInteger bb = new BigInteger(b);
        BigInteger cc = new BigInteger(c);
        BigInteger result = new BigInteger("0");
        BigInteger result2 = new BigInteger("0");
        
        System.out.println("암호화 평문 " + aa);
        result = aa.pow(e).mod(nn);
        System.out.println(result);
        
        System.out.println("복호화 평문 " + aa);
        result2 = result.pow(d).mod(nn);
        System.out.println(result2);
        System.out.println("--------------------------------------------");
        
        System.out.println("암호화 평문 " + bb);
        result = bb.pow(e).mod(nn);
        System.out.println(result);
        
        System.out.println("복호화 평문 " + bb);
        result2 = result.pow(d).mod(nn);
        System.out.println(result2);
        System.out.println("--------------------------------------------");
        
        System.out.println("암호화 평문 " + cc);
        result = cc.pow(e).mod(nn);
        System.out.println(result);
        
        System.out.println("복호화 평문 " + cc);
        result2 = result.pow(d).mod(nn);
        System.out.println(result2);
        
        br.close();
    }
}