공개키 기반 암호알고리즘 중 하나이다. 비대칭 암호알고리즘 이라고도 불린다. 대표적인 사용예로 전자서명(Digital Signature)을 들 수 있다. 과연 전자서명에 RSA가 어떻게 적용이 되는지 살펴보자.
보통 어떠한 종이문서에 검수자의 서명이 되어있으면 독자에게 신뢰를 줄 수 있다. 문서에 서명이 되어있다는 것은 문서의 내용이 정확하고 누군가에 의해 검증이 되었다는 뜻이기 때문이다. 전자서명도 이와 마찬가지다. 차이점은 종이문서 대신 디지털문서에 서명을 하는 것이다. 전자서명은 크게 서명(Signing)과 인증(Verification) 두가지 과정으로 나뉜다. 서명은 문서가 검증되었음을 알리는 과정이고, 인증은 독자가 해당 문서에 서명이 되었는지를 확인하는 과정이다. 
원리는 문서 데이터의 해쉬(Hash)값을 비교해서 일치하는지 여부를 검증하는 것이다. 서명자는 문서의 데이터를 해쉬함수(Hash function)를 통해 해쉬값을 생성하고, 생성된 해쉬값을 비밀키(Private key)로 암호화(Encryption)한 후 문서에 첨부한다. 반대로 서명된 문서인지 검증하기 위해서 서명부분을 따로 떼내어 공개키(Public key)로 복호화(Decryption)하고, 문서에서 서명을 제외한 데이터를 다시 같은 해쉬함수를 통해 해쉬값을 얻어낸다. 두가지 값이 일치하는지 확인하여 일치하면 서명된 문서이고, 그렇지 않으면 서명되지 않은 문서인 셈이다.


여기서 RSA에 대해 알아보자. RSA의 기본은 누구든지 공개키로 데이터를 암호화 할 수는 있지만, 단 한명만 암호화된 데이터를 비밀키로 복호화할 수 있다는 것이다. RSA가 강력한 이유중 하나는 바로 큰 수를 소인수분해하기 어렵다는 것에 기반을 두고 있기 때문이다. 우선 RSA의 기본 흐름을 간단히 살펴보자.

공개키/비밀키를 구하는 과정
1. 두개의 소수(prime number) p와 q를 선택한다. 보안상 p와 q는 safe prime이 되는것이 좋다. (Safe prime: p = 2p_1 + 1, q = 2q_1 + 1)
2. 다음으로 각 키의 Modulus로 사용될 N = pq 을 구한다.
3. φ(pq) = (p - 1)(q - 1) (φ는 Euler's totient function)
4. e를 선택한다. (1 < e < φ(pq), e, φ(pq)는 서로소(coprime))
    e는 보통 짧은 bit길이를 가진다. 하지만 너무 짧으면 보안상 문제가 될 수 있다.
5. de ≡ 1 (mod φ(pq))를 만족시키는 d를 구한다.
   de - 1 은 φ(pq)에 의해 나눠진다.
   확장 유클리드 알고리즘(Extended Euclidean algorithm)을 사용하여 계산
d는 비밀키이고, e는 공개키이다.

암호화(Encryption)/복호화(Decryption)
Alice                                       Bob
N, e, d                                 m (m: 원본 데이터)
     ------------ N, e ----------->  
                                           c = m**e (mod N) (c: 암호화된 데이터) (**는 거듭제곱을 나타냄)
    <------------- c -------------
m = c**d (mod N)

위 그림은 Bob이 Alice에게 데이터를 보내는 과정을 보여준다. Bob은 공개키로 데이터를 암호화하고 Alice가 암호화된 데이터를 받아서 복호화한다.

...
신고
1 2 3 4 5 6 7 8 ··· 12 

글 보관함

카운터

Total : 27,879 / Today : 17 / Yesterday : 17
get rsstistory!

티스토리 툴바