1-(3) [암호] RSA 암호화/복호화 소개 및 코드정리(JAVA 코드)

포스트를 작성하기 전

 

지금 저는 프로그래밍 개발을 직업으로 가지고 있지만
제 대학 전공은 수학입니다ㅎㅎ
컴퓨터관련학과를 복수전공으로 졸업하여 지금의 직업을 가지게 되었습니다.

 

음...이 이야기를 한 이유는 이번 포스트에서 수학과 관련된 글을 올리게 되기 때문입니다.
'정수론' 이라는 전공시간에 RSA암호화를 배운적이 있습니다.(심지어 시험도 봤던 것 같습니다ㅎㅎ)
그 당시 기억나는 건 소인수 분해의 특징을 이용해 암호를 한다고만 배워 이해가 잘 가지 않았지만
프로그램을 만지고 보니 현업에서 아주 많이 쓰이고 있다는 것이 신기했습니다.

 

'정수론'을 알기에 쉽게 이해할 줄 알았으나 다시 공부해보니까..... 직접 손으로 하기는 어려웠습니다ㅠㅠ

 

지금, RSA 암호화에 대해 공부하며 알게된 내용을 이번에는 수학적 원리와 프로그래밍 특징을 같이 녹여 포스트를 작성해 보겠습니다.
원래는 포스트를 프로그래밍 중심으로 작성한다고 했지만 이번 RSA를 공부하면서
소수의 위대함과 해독의 어려움을 수학적으로 보여주기 위함과(쓸때없는 수학적(?) 감성...)
원리를 같이 이해하면 더 쉽게 알게 될 것이라는 생각에 지금부터 RSA암호화 소개를 시작해 보겠습니다!!

 

---

 

- RSA 소개

 

대표적인 공개키 암호화 알고리즘으로 1977년 Ron Rivest, Adi Shamir, Leonard Adleman에 의해 큰 정수의 소인수 분해가 매우 어렵다는 사실을 이용하여 이름의 앞글자를 딴 RSA 암호화 알고리즘을 개발하였다.

 

'공개키 암호화 알고리즘'은 암호화 할 때와 복호화 할 때의 키가 다른 알고리즘으로 '비대칭키 암호화 알고리즘' 이라고도 한다.

 

대칭키 알고리즘인 AES 암호화와 다르게 두개의 키를 가지고 있으며
암호화 할 때의 키를 공개키(public key)
복호화 할 때의 키를 개인키(private key)라고 한다.
공개키로 그 누구나 암호화를 할 수 있지만 개인키를 가지고 있지 않으면 아무나 복호화를 할 수 없다.

 

대표적으로 암호규약(TLS, http, https 등)에서 사용된다. (이에 대한 설명은 제대로 공부해서 다음 포스트에 다룰 예정입니다.)

 

- RSA 특징(공개키 암호화 알고리즘의 특징)

 

1. 암호화, 복호화 키가 다르다.(비대칭키)
2. 대칭키에 비해 속도가 많이 느리다.(그만큼 큰 정수에 대한 소인수분해가 어렵다는 점!)
3. 키공개와 키분배가 용이하다.(공개키와 비밀키의 역할이 바뀌어도 가능)
4. But, 수신자와 발신자의 키 공유과정이 필요하기 때문에 완벽히 보안에서 해결되었다 말할 수 없다.

 

- RSA 원리&구현

(DANGER : 수포자 접근 주의, 코드로 넘어가도 됩니다.)

 

집합 1,2,...,n-1의 원소들 중 서로소 관계에 있는 원소들의 갯수를 φ(n), '오일러 피함수'라고 한다.
이 때 소수 p는 φ(p)=p-1 이라 정의할 수 있다.

 

어떤 큰 정수 n에 대해 φ(n)의 값을 알기 위해서는 반드시 소인수분해를 필요로 하며 만약 큰 정수 n이 소수 p,q에 대해 n=pq로 성립될 때
φ(n)=(p-1)(q-1) 이고 φ(n)은 RSA 암호화를 풀기위한 경우의 수가 된다. 소수는 무한한 값을 가지므로 φ(n)의 값 또한 무한하기에 해독 또한 시간소요가 많아지게 된다.

이 원리를 이용한 RSA 구현을 단계별로 알아보자

 

 

step1. 두개의 큰 소수 p, q를 선정한다.(예시에서는 작은 수로 한다.)
(ex : p=11, q=13)

step2. p-1, q-1과 각각 서로소인 정수 e를 찾는다.
(ex : p=11, q=13, e=7)

step3. ed를 (p-1)(q-1)로 나눈 나머지가 1이 되도록 하는 d를 찾는다.
(ex : p=11, q=13, e=7, d=103)

step4. N=pq를 계산 후 (N,e)는 공개키로 (N,d)는 개인키로 가진다.
(ex : p=11, q=13, e=7, d=103, N=143)

 

 

암호화. 보내려는 평문 a를 x≡a^e (mod N)으로 암호화, x는 암호화 된 암호문
복호화. 받은 암호문 x를 a'≡x^d (mod N)으로 암호화, a'는 복호화 된 평문

 

- RSA 알고리즘 (Java 코드)

거창한 이론에 비해 코드는 이미 구현된 내장라이브러리로 쉽게 구현 가능하다.

import java.io.UnsupportedEncodingException;
import java.security.InvalidKeyException;
import java.security.Key;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.NoSuchAlgorithmException;
import java.security.spec.InvalidKeySpecException;

import javax.crypto.BadPaddingException;
import javax.crypto.Cipher;
import javax.crypto.IllegalBlockSizeException;
import javax.crypto.NoSuchPaddingException;

import org.apache.commons.codec.binary.Base64;

public class RSA {
	private Key publicKey;
	private Key privateKey;
	
	public RSA() throws NoSuchAlgorithmException, InvalidKeySpecException{
		KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("RSA");
		keyPairGenerator.initialize(2048);
        
		KeyPair keyPair = keyPairGenerator.genKeyPair();
		this.publicKey = keyPair.getPublic(); // 공개키
		this.privateKey = keyPair.getPrivate(); // 개인키
	}
	
	public String encrypt (String inputStr) throws InvalidKeyException, NoSuchAlgorithmException, NoSuchPaddingException, IllegalBlockSizeException, BadPaddingException, UnsupportedEncodingException{
		Cipher c = Cipher.getInstance("RSA");
		c.init(Cipher.ENCRYPT_MODE, publicKey);
		byte[] encrypted = c.doFinal(inputStr.getBytes("UTF-8")); // 암호화된 데이터(byte 배열)
		return new String(Base64.encodeBase64(encrypted));
	}
	
	public String decrypt (String inputStr) throws NoSuchAlgorithmException, NoSuchPaddingException, InvalidKeyException, IllegalBlockSizeException, BadPaddingException, UnsupportedEncodingException {
		Cipher c = Cipher.getInstance("RSA");
        		c.init(Cipher.DECRYPT_MODE, privateKey);
        		byte[] decrypted = Base64.decodeBase64(inputStr.getBytes());
        		return new String(c.doFinal(decrypted),"UTF-8");
	}

	public Key getPublicKey() {
		return publicKey;
	}

	public Key getPrivateKey() {
		return privateKey;
	}
}