웃엉의 프로그래밍 타임라인

포스트를 작성하기 전

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

음...이 이야기를 한 이유는 이번 포스트에서 수학과 관련된 글을 올리게 되기 때문입니다.
'정수론' 이라는 전공시간에 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;
	}
}

안녕하세요! 암호화 두번째 'MD5'암호화를 정리해볼까 합니다.

이전 AES암호화를 설명하면서 돌아가는 원리를 설명해보면 어떨까 생각을 해봤는데
원리보다 조금 더 실무에 맞는 포스트로 정리하고 싶어 암호원리에 대해서는 작성하지 않았고

어떤 경우에 사용하는지? 어떻게 사용하는지? 에 대해 가볍지만

제가 실무에 적용 할 수 있고 이해 할 수 있을(이제 시작하는 초급프로그래머) 정도로 자세하게 써보겠습니다.

제 글을 보는 개발자님들과의 많은 소통이 있었으면 좋겠습니다.

- MD5 소개

MD5(Message-Digest Algorithm 5)

'128비트 암호화 해시 함수이며 기존 MD4를 대체하기 위해 고안되었다.'

라는 설명이 구글에서 찾아보면 대부분이다. 더 자세히 찾는다면 찾을 수 있지만 핵심이 아닌 것 같아 짧게 설명만 찾아보았다.

위 설명에 보면 '암호화'가 아닌 '해시' 라는 단어를 사용하는데 두 단어의 차이점을 비교하면 MD5의 특징을 바로 파악 할 수 있다.

○ 암호화(Encryption)

- 양방향 암호화 기법

- 평문을 암호화 된 문장으로 만들고, 암호화 된 문장을 다시 평문으로 만드는 복호화 기능을 가짐

○ 해시(Hash)

- 단방향 암호화 기법

- 평문을 암호화 된 문장으로 만듬

이 둘의 차이점은 '복호화의 가능 여부' 이다.

단방향 암호화로 원래의 데이터 찾기가 불가능 하나 같은 평문을 암호화 시킬 때 같은 해시값을 출력함으로써

사용자 자신만 알고 이 외의 관리자와 3자가 알지 못하게 하는 비밀번호 암호화나 두 파일의 무결성을 확인하는데 주로 사용한다.

충돌로 인해 보안이 매우 중요한 곳에서는 사용하지 않지만 간단한 작업에서는 지금도

- MD5 특징

1. 임의의 길이의 값을 입력 받아 128비트(32자리) 길이의 해시값으로 출력

2. 단방향 암호화로 원래의 데이터 값을 찾기 불가능 (해시계산과정에서 비트단위로 박살)

3. 고속연산이 가능

4. 충돌의 가능성이 낮아 네트워크로 전송된 큰 파일의 무결성 확인이나 비밀번호 암호화에 주로 사용

5. But, MD5의 충돌의 찾아내는데 주력하여 뚫린 경험이 있어 보안이 중요시 되는 데이터는 해시연산 암호화를 사용하지 않는다.

   (MD5의 충돌로 SHA로 대체해 사용하길 권장 하였지만 이마저도 박살 당하고 이외의 몇 개의 상위 해시 암호화도 크래커들이 박살내버림!!!!!)

- MD5 알고리즘 (Java 코드)

import java.io.UnsupportedEncodingException;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import org.apache.commons.net.util.Base64;

public class MD5 {
	
	String result="";
	
	public String encrypt(String inputStr) throws NoSuchAlgorithmException, UnsupportedEncodingException{
	try {
		MessageDigest md5 = MessageDigest.getInstance("MD5");
		byte[] byteValue = md5.digest(inputStr.getBytes());
            
		Base64 base64EnDe = new Base64();

		result = base64EnDe.encodeToString(byteValue).replaceAll("\r\n", "");
	} catch (NoSuchAlgorithmException e) {
		e.printStackTrace();
		throw e;
	}

		return result; 
	}
}

안녕하세요! 티스토리에서 처음으로 인사드리는 신입 프로그래머 호파 입니다.

제 첫번째 포스트를 암호화 시리즈로 시작하려 합니다.

개발 업무를 하다보면 웹프로그래머로 있어서 그런지

다른 업체와 협업을 할 때 주로 RestFul API를 통해 작업을 진행합니다.

그 안에서 사용자 개인정보를 포함한 중요정보들을 암호화하여 넘겨 받게 됩니다.

이렇게 많이 쓰이는 암호화를 첫 글로 작성하면서 다른 개발자들에게 참고용 포스트가 됨과 동시에

스스로 공부한 것을 정리해 내것으로 만듦과 많은 개발자들과의 소통과 조언을 기다립니다.

- AES 소개

AES(Advanced Encryption Standard)

1997년 1월 2일, 미국 국립표준기술연구소 'NIST' 는 기존 DES를 대체할 목적으로 더 나은 암호기법을 공모하였다.

기존 DES(Data Encryption Standard)는 블록 암호로 표준으로 두고 있었는데 56비트 대칭키 암호화로 현재 컴퓨터 환경에 비해 너무 짧고 특수한 방법을 사용하면 쉽게 해독할 수 있는 주장이 제기되면서(이는 실제로 약 22시간만에 풀 수 있는 해독알고리즘이 구현되었다.)  새로운 표준의 암호화를 공모하였고 약 30개의 공모된 알고리즘을 1차심사를 거쳐 최종심사를 받게 될 5개의 알고리즘을 선정했다.

MARS : IBM 연구소 제출

RC6 : RSA Security 제출

Serpent : Ross Andersen, Eil Biham, Lors Knudsen 공동 제출

Twofish : Counterpane의 암호학자 bruce Schneier를 비롯한 대규모 연구팀 제출

Rijandael : 벨기에 암호학자 Joan Daemen, Vincent Rijmen 공동 제출

위 알고리즘은 모두 C, Java 언어를 이용하였고 '안전성', '비용', '알고리즘 및 구현 특성' 이란 세 가지 조건을 기준으로 평가받게 되었다.

이 안에서 Rijandael 알고리즘이 안전성, 속도, 효율성, 구현 및 유연성이 다른 알고리즘들 보다 우수하다 평가했고 2000년 10월 2일, AES 암호화/복호화 알고리즘으로 Rijandael을 선정하게 되었다.

- AES 특징

1. 대칭 키 알고리즘

2. 빠르고 공격에 대해 안전하다.

3. 간단한 하드웨어 / 소프트웨어로 구성하기 쉽다.

4. 128비트의 블록 크기 값을 가진다.

5. 기본적으로 128, 192, 256 비트 키 값을 가지나 이론적으로 키의 크기 제한이 없다.

- AES 알고리즘 (Java 코드)

import java.io.UnsupportedEncodingException;
import java.security.InvalidKeyException;
import java.security.NoSuchAlgorithmException;

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

import org.apache.commons.net.util.Base64;

public class AES {

	/** 암호키 (임의지정) */
	String encryptKey = "dladmlwlwjd";

	public String encrypt(String inputStr){
 
		String result = null;
  
		if ((inputStr == null) || (inputStr.length() < 1)) {
			return result;
		}
  
		SecretKeySpec keySpec = new SecretKeySpec(encryptKey.getBytes(), "AES");
		
		try {
			Cipher cipher = Cipher.getInstance("AES/ECB/PKCS5Padding");
			cipher.init(1, keySpec);
    
			byte[] byteValue = cipher.doFinal(inputStr.getBytes("UTF-8"));

			Base64 base64EnDe = new Base64();            

			result = base64EnDe.encodeToString(byteValue).replaceAll("\r\n", "");
		}
		catch (NoSuchAlgorithmException e) {
			e.printStackTrace();
		} catch (NoSuchPaddingException e) {
			e.printStackTrace();
		} catch (InvalidKeyException e) {
			e.printStackTrace();
		} catch (IllegalBlockSizeException e) {
			e.printStackTrace();
		} catch (BadPaddingException e) {
			e.printStackTrace();
		} catch (UnsupportedEncodingException e) {
			e.printStackTrace();
		}
		
		return result;
	}
	
	
	public String decrypt(String encStr){
	
		String result = "";
	
		if ((encStr == null) || (encStr.length() < 1)) {
			return result;
		}
		
		SecretKeySpec keySpec = new SecretKeySpec(encryptKey.getBytes(), "AES");
		
		try {
			Cipher cipher = Cipher.getInstance("AES/ECB/PKCS5Padding");
			cipher.init(2, keySpec);
	  
			Base64 base64EnDe = new Base64();            

			byte[] origianl = cipher.doFinal( base64EnDe.decode(encStr) );
	 
			result = new String(origianl, "UTF-8");
			
		} catch (UnsupportedEncodingException e) {
			e.printStackTrace();
		} catch (NoSuchAlgorithmException e) {
			e.printStackTrace();
		} catch (NoSuchPaddingException e) {
			e.printStackTrace();
		} catch (IllegalBlockSizeException e) {
			e.printStackTrace();
		} catch (BadPaddingException e) {
			e.printStackTrace();
		} catch (InvalidKeyException e) {
			e.printStackTrace();
		}
	
		return result;
	}
}