logo

English

이곳의 프로그래밍관련 정보와 소스는 마음대로 활용하셔도 좋습니다. 다만 쓰시기 전에 통보 정도는 해주시는 것이 예의 일것 같습니다. 질문이나 오류 수정은 siseong@gmail.com 으로 주세요. 감사합니다.

RSA 암호화 알고리즘 개요

by 엉뚱도마뱀 posted Nov 17, 2017
?

Shortcut

PrevPrev Article

NextNext Article

Larger Font Smaller Font Up Down Go comment Print Attachment
?

Shortcut

PrevPrev Article

NextNext Article

Larger Font Smaller Font Up Down Go comment Print Attachment

1. 개요

RSA는 공개키 암호시스템의 하나로, 암호화 뿐만 아니라 전자서명이 가능한 최초의 알고리즘으로 알려져 있다. RSA가 갖는 전자서명 기능은 인증을 요구하는전자 상거래 등에 RSA의 광범위한 활용을 가능하게 하였다.

 

RSA 암호체계의 안정성은 큰 숫자를 소인수분해하는 것이 어렵다는 것에 기반을 두고 있다. 그러므로 큰 수의 소인수분해를 획기적으로 빠르게 할 수 있는 알고리즘이 발견된다면 이 암호 체계는 가치가 떨어질 것이다. 1993년 피터 쇼어는 쇼어 알고리즘을 발표하여, 양자 컴퓨터를 이용하여 임의의 정수를 다항 시간 안에 소인수분해하는 방법을 발표하였다. 따라서 양자 컴퓨터가 본격적으로 실용화되면 RSA 알고리즘은 무용지물이 될 것이다. 그러나 양자 컴퓨터가 이 정도 수준으로 실용화되려면 아직 여러 해가 더 필요할 것으로 보인다.

 

RSA는 두 개의 키를 사용한다. 여기서 키란 메시지를 열고 잠그는 상수(constant)를 의미한다. 이 중 공개키(public key)는 모두에게 알려져 있으며, 메시지를 암호화(encrypt)하는데 쓰인다. 이렇게 암호화된 메시지는 개인키(private key)를 가진 자만이 복호화(decrypt)하여 열어볼 수 있다. 다시 말하면, 누구나 어떤 메시지를 암호화할 수 있지만, 그것을 해독하여 열람할 수 있는 사람은 개인키를 지닌 단 한 사람 뿐인 것이다. RSA는 소인수분해의 난해함에 기반하여, 공개키만을 가지고는 개인키를 쉽게 짐작할 수 없도록 디자인되어 있다.

 

 

2. 키의 생성

A와 B가 보안이 보장되어 있지 않은 환경에서 서로 비밀 메시지를 주고 받고 싶다고 가정하자. B가 A에게 메시지를 전달하기 위해서는 A의 공개키가 필요하다. A는 아래와 같은 방법을 통해 그만의 공개키와 개인키를 제작한다.

 

스크린샷 2017-11-17 오전 11.47.34.png

 

A의 공개키는 위에서 구한 두 개의 숫자로 이루어진 <N, e>이고, 개인키는 d이다. A는 <N, e>만을 B에게 공개하고, B는 이 공개키를 사용하여 자신의 메시지를 암호화하게 된다. 여기서 p와 q의 보안은 매우 중요하다. 이를 가지고 d와 e의 계산이 가능하기 때문이다. 그리하여 공개키와 개인키가 생성이 된 후에는 이 두 숫자를 지워버리는 것이 안전하다.

 

 

3. 암호화

B가 M이란 메시지를 A에게 보내고 싶다고 하자. 일단 B는 이 M를 N보다 작은 숫자로 변환한다. (이 변환법(padding scheme)은 A에게도 미리 알려져 있어야 한다. 이를테면, 메시지를 토막내어 하나의 메시지가 일정 수의 비트를 넘지 않게 하는 방법이 있다. 하지만 실제로는 이중보안을 위해 더욱 복잡한 변환법이 사용된다.) 그리고 B는 A의 공개키 <N, e>를 획득하고, 다음과 같이 c를 계산한다.

스크린샷 2017-11-17 오전 11.48.18.png

 

그리고 이 c를 A에게 보낸다.

 

 

4. 복호화

A는 암호화된 메시지 c를 B에게서 건네받았고, N과 d를 알고 있다. 다음 식을 통해 m을 찾는다.

스크린샷 2017-11-17 오전 11.48.30.png

 

위에서 설명하였듯 m을 가지고 A는 M을 찾아낼 수 있는 방법을 알고 있다.

 

 

다음 소스코드는 공인인증서의 공개키를 이용해 RSA암호화를 수행하는 클래스이다.

 

import java.io.ByteArrayInputStream;  
 
import java.io.ByteArrayOutputStream;  
import java.security.InvalidKeyException;  
import java.security.Key;  
import java.security.NoSuchAlgorithmException;  
import java.security.NoSuchProviderException;  
 
import javax.crypto.BadPaddingException;  
import javax.crypto.Cipher;  
import javax.crypto.IllegalBlockSizeException;  
import javax.crypto.NoSuchPaddingException;  
 
public class RSAEncoder {  
 
    public static int RSA_ENCODING_KEY_SIZE = 64;  
 
    private byte[] toEncode;  
 
    private Key publicKey;  
 
    public RSAEncoder(byte[] toEncode, Key publicKey) {  
        if( toEncode == null || publicKey == null )  
            throw new IllegalArgumentException();  
        this.toEncode = toEncode;  
        this.publicKey = publicKey;  
    }  
 
    public byte[] encode() throws NoSuchAlgorithmException, NoSuchProviderException,   
            NoSuchPaddingException, InvalidKeyException,   
            IllegalBlockSizeException, BadPaddingException {  
        Cipher c = Cipher.getInstance("RSA", "BC");  
        c.init(Cipher.ENCRYPT_MODE, publicKey);  
        int length = toEncode.length;  
        if( length > RSA_ENCODING_KEY_SIZE ) {  
            ByteArrayInputStream bis = null;  
            ByteArrayOutputStream bos = null;  
            try {  
                bis = new ByteArrayInputStream(toEncode);  
                bos = new ByteArrayOutputStream();  
                int count = 0;  
                byte[] buf = new byte[RSA_ENCODING_KEY_SIZE];  
                while( (count=bis.read(buf)) != -1 )  
                    bos.write(c.doFinal(buf, 0, count));  
                return bos.toByteArray();  
            } catch(Exception e) {  
            } finally {  
                if( bis != null ) try { bis.close(); } catch(Exception ignore) {/**/}  
                if( bos != null ) try { bos.close(); } catch(Exception ignore) {/**/}  
            }  
        }  
        return c.doFinal(toEncode);  
    }  
 
    public byte[] getToEncode() {  
        return toEncode;  
    }  
 
    public void setToEncode(byte[] toEncode) {  
        this.toEncode = toEncode;  
    }  
 
    public Key getPublicKey() {  
        return publicKey;  
    }  
 
    public void setPublicKey(Key publicKey) {  
        this.publicKey = publicKey;  
    }  
}

 

공인인증서의 공개키는 1024bit 즉, 128바이트로 이루어져 있다. 위 코드에서는 BouncyCastleProvider를 사용하였는데, RSA암호화시 입력데이터의 길이가 키의 길이보다 크다면 예외가 발생한다. 따라서 키의 크기보다 같거나 작게 입력데이트를 나누어 암호화를 수행한다.

 
RSA암호화된 데이터를 공인인증서의 개인키를 이용해 복호화하는 클래스는 다음과 같다.
import java.io.ByteArrayInputStream;  
import java.io.ByteArrayOutputStream;  
import java.security.InvalidKeyException;  
import java.security.NoSuchAlgorithmException;  
import java.security.NoSuchProviderException;  
import java.security.PrivateKey;  
 
import javax.crypto.BadPaddingException;  
import javax.crypto.Cipher;  
import javax.crypto.IllegalBlockSizeException;  
import javax.crypto.NoSuchPaddingException;  
 
public class RSADecoder {  
 
    public static int RSA_DECODING_KEY_SIZE = 128;  
 
    private byte[] toDecode;  
 
    private PrivateKey privatekey;  
 
    public RSADecoder(byte[] toDecode, PrivateKey privatekey) {  
        if( toDecode == null || privatekey == null )  
            throw new IllegalArgumentException();  
        this.toDecode = toDecode;  
        this.privatekey = privatekey;  
    }  
 
    public byte[] decode() throws NoSuchAlgorithmException, NoSuchProviderException,   
            NoSuchPaddingException, InvalidKeyException,   
            IllegalBlockSizeException, BadPaddingException {  
        Cipher c = Cipher.getInstance("RSA", "BC");  
        c.init(Cipher.DECRYPT_MODE, privatekey);  
        int length = toDecode.length;  
        if( length > RSA_DECODING_KEY_SIZE ) {  
            ByteArrayInputStream bis = null;  
            ByteArrayOutputStream bos = null;  
            try {  
                bis = new ByteArrayInputStream(toDecode);  
                bos = new ByteArrayOutputStream();  
                int count = 0;  
                byte[] buf = new byte[RSA_DECODING_KEY_SIZE];  
                while( (count=bis.read(buf)) != -1 )  
                    bos.write(c.doFinal(buf, 0, count));  
                return bos.toByteArray();  
            } catch(Exception e) {  
            } finally {  
                if( bis != null ) try { bis.close(); } catch(Exception ignore) {/**/}  
                if( bos != null ) try { bos.close(); } catch(Exception ignore) {/**/}  
            }  
        }  
        return c.doFinal(toDecode);  
    }  
 
    public byte[] getToDecode() {  
        return toDecode;  
    }  
 
    public void setToDecode(byte[] toDecode) {  
        this.toDecode = toDecode;  
    }  
 
    public PrivateKey getPrivateKey() {  
        return privatekey;  
    }  
 
    public void setPrivateKey(PrivateKey privatekey) {  
        this.privatekey = privatekey;  
    }     
}  
TAG •

List of Articles
No. Subject Author Date Views
67 select 와 epoll 엉뚱도마뱀 2017.12.11 2
66 비밀번호 해쉬에 Salt(소금) 첨가하기 file 엉뚱도마뱀 2017.11.23 20
65 Linux /dev/random vs /dev/urandom 삽질 후기 엉뚱도마뱀 2017.11.22 33
64 리눅스 /dev/random을 이용한 랜덤값 생성 엉뚱도마뱀 2017.11.22 16
63 난수발생기 개론 엉뚱도마뱀 2017.11.22 17
» RSA 암호화 알고리즘 개요 file 엉뚱도마뱀 2017.11.17 22
61 악성코드 종류 구분 digipine 2017.11.13 53
60 대칭키 암호화관련 개념 정리 digipine 2017.11.09 32
59 Ubuntu 16 에 mysql 5.7 설치 및 원격 설정 file digipine 2017.11.08 26
58 Ubuntu 16 에 JAVA 1.7.0 jdk 설치 하기 digipine 2017.11.07 28
57 윈도우 한영 전환 쉬프트 스페이스로 변경 digipine 2017.11.03 8
56 우분투 Nabi 한글 입력기 Tray(트레이) 상단 메뉴바로 옮기기 digipine 2017.11.03 10
55 Ubuntu 12.0.4 LTS에 Nabi 나비 설치하기 digipine 2017.11.03 5
54 Linux init.d 에서 등록하기. 부팅 시 자동실행 설정 digipine 2017.11.03 6
53 초고속망 통신사 DNS 서버 주소 모음 - DNS 설정 digipine 2017.11.03 29
52 git 환경 설정 및 명령어 정리 digipine 2017.11.03 7
51 유닉스/리눅스 명령어 레퍼런스 digipine 2017.11.03 9
50 포렌식을 활용한 정보보호 digipine 2017.11.02 9
49 소프트웨어 테스팅 전문가들을 위한 사이트 digipine 2017.11.02 5
48 MacOS 10.12.2 (OSX) KERNEL DEBUGGING file digipine 2017.11.02 6
Board Pagination Prev 1 2 3 4 Next
/ 4