자바(Java)로 구현한 RSA 암호학 알고리즘 예제

/* 

written by kaspy (kaspyx@gmail.com)

*/ 

RSA는 대단히 수학적인 알고리즘으로 200자리가 넘어가면 슈퍼컴퓨터로 푸는데만해도 1만년이상이 걸린다고 한다.

알고리즘은 두개의 소수 p,q 그리고 (p-1)*(q-1)의 서로소 d를 구하고

p,q,d는 비밀키로 개인이 보관(유출금지)한다.

그리고 p*q 의값 n과 e * d % (p-1)(q-1) = 1을 만족하는 e를 구한다.

n과 e는 공개키로 외부에게 공개할수있다.

p = 11, q = 17, d = 23

e = 7, n = 187

메시지가 m이라고 할때 

암호화 c = ( m ^ e  ) % n

복호화 d = ( c ^ d) % n

로 구할수있다. 큰 숫자를 다뤄야하는 특성상, 자바 자료형 BigInteger를 사용하여 구현하였다.

- 컴파일

javac RSAtest.java

- 실행

java RSAtest

1. import java.math.BigInteger;
2. import java.security.SecureRandom;
3. import java.io.*;
4. import java.util.*;
5.  
6.  
7. class RSAtest
8. {
9.         BigInteger p = new BigInteger("11");            // 비밀키 소수 p = 11
10.     BigInteger q = new BigInteger("17");        // 비밀키 소수 q = 17
11.         BigInteger d = new BigInteger("23");            // z = (p-1)(q-1) = 160의 소로소로 d는 23을 택하였습니다.
12.         BigInteger e = new BigInteger("7");             // e * d(7) mod 160 = 1 인 수 e는 7으로 정하였습니다. 공개키
13.        
14.         BigInteger n;                                                   // n = p *q 공개키
15.  
16.         RSAtest()
17.         {
18.                 n = p.multiply(q);      // 공개키 n = p * q
19.         }
20.        
21.         void encrypt_msg(BigInteger txt[])
22.         {
23.                 System.out.println("암호화를 진행합니다.");
24.                 for (int i=0; i < txt.length;i++ )
25.                 {      
26.  
27.                         txt[i] = txt[i].modPow(e, n);
28.  
29.                 }
30.         }
31.  
32.         void decrypt_msg(BigInteger txt[])
33.         {
34.                 System.out.println("복호화를 진행합니다.");
35.                 for (int i=0; i < txt.length;i++ )
36.                 {
37.                         txt[i] = txt[i].modPow(d, n);
38.                 }
39.         }
40.  
41.         public static void main(String[] args)
42.         {
43.                 RSAtest rsa = new RSAtest();
44.                 BigInteger[] key;
45.                 Scanner sc = new Scanner(System.in);
46.                 String s,b;
47.  
48.                 String t;
49.                 Integer t2;
50.  
51.                 System.out.println("평문을 입력해주세요.");
52.                 s = sc.nextLine();
53.                
54.  
55.                 key = new BigInteger[s.length()];
56.  
57.                 for (int i=0;i < s.length() ;i++ )
58.                 {
59.                         t2 = (int)s.charAt(i);
60.                         t = t2.toString();
61.        
62.                         key[i] = new BigInteger(t);
63.                 }
64.                        
65.                 // 암호화
66.                 rsa.encrypt_msg(key);
67.  
68.  
69.                 // 복호화
70.                 rsa.decrypt_msg(key);
71.  
72.                 s = key.toString();
73.  
74.                 for(int i = 0; i < key.length; i++)
75.         {
76.             String s2 = key[i].toString();
77.             Integer integer = Integer.valueOf(Integer.parseInt(s2));
78.             int k = integer.intValue();
79.             System.out.printf("%c", new Object[] {
80.                 Integer.valueOf(k)
81.             });
82.         }
83.  
84.                 System.out.println();
85.                
86.         }
87. }

* 참고 사이트

- http://pulsebeat.tistory.com/56

- http://reinliebe.tistory.com/79