[암호] 공개키 암호 - RSA

RSA 개요

RSA 암호는 공개키 암호시스템의 하나로 1978년 로널드 라이베스트(Ron Rivest), 아디 샤미르(Adi Shamir), 레너드 애들먼(Leonard Adleman)의 연구에 의해 체계화되었으며, RSA라는 이름은 이들 3명의 이름 앞글자를 따서 만들어졌다.

 

RSA 알고리즘

☞ key 계산 알고리즘

서로 다른 큰 소수 p, q 를 뽑는다.
p와 q 를 곱해 N 을 만든다. (N = p * q)
φ(n) 를 계산한다. (φ(n) = (p-1)*(q-1))
e를 선택한다. ( e ∈ {1,2,3 ... (φ(n)-1)} )
d를 계산한다. (e*d = 1 mod φ(n))
키를 계산한다. ( private key(d, p, q, N) , publickey(e, N) )

+ N = p*q 여기서 p와 q를 알고있으면 N을 계산하기는 쉽지만 N 하나를 가지고 p와 q를 알아내는 것은 어렵다.(소인수 분해의 어려움) 이러한 특성을 일방향 함수의 성질을 가지고 있다고 이야기한다.

+ 공개키 암호의 특징인 개인키(publicKey)를 가지고 공개키(privateKey)를 만들 수 있지만 개인키를 가지고 공개키를 만들 수 없는 이유는 N=p*q 가 일방향 함수의 성질을 가지고 있기 때문이다.

+ 오일러 함수(φ(n))

 

1. 암/복호화에 사용될 경우

 

☞ RSA Encryption - publicKey(e,N)

m : plaintext ( 1 <= m < N ) , c : ciphertext
c = m^e mod N

☞ RSA decryption - privateKey(d,p,q,N)

c : ciphertext , m' : decrypted text
m' = c^d mod N

 

2. 서명에 사용될 경우

 

☞ RSA sign - privateKey(d,p,q,N)

m : plaintext , s : signed value
s = m^d mod N

☞ RSA verify - publicKey(e,N)

s : signed value , m : origin plaintext
m' = s^e mod N
if m' == m :
    올바른 서명값
else :
    올바르지 않은 서명값

 

RSA-OAEP(Optimal Asymmetric Encryption Padding)

RSA를 개량해서 선택암호문공격으로부터 안전하게 만든것으로 인증을 추가한 것이다.

평문 해시 값과 정해진 개수의 0 등으로 만들어진 인증정보를 평문 앞에 추가한 뒤, 그 후에 RSA로 암호화 한다.

복호화시 RSA로 복호화한 후 선두에 올바른 인증 정보가 나타나지 않으면 오류로 판정한다.

RSA-OAEP