[비대칭키 암호 시스템] RSA

RSA Encryption

Public keys

• n = p x q, where p and q are primes : 아주 긴 소수이기 때문에 n으로부터 p,q를 알아낼 수 없다
• e : relatively prime to (p-1)(q-1)

private key

• d = $e^{-1}$ mod (p-1)(q-1) : e에 대한 역원

Encryption

• $C \equiv M^e mod\ n$
• 상대의 공개키로 암호화한다

Decryption

• $M \equiv C^d mod\ n$
• 상대의 비밀키로 복호화한다

 

이게 어떻게 가능한 것인가?

$M^{ed}$ mod n이 다시 M이 되는가?

d = $e^{-1}$ mod (p-1)(q-1) 이므로 $ed \equiv 1$ mod (p-1)(q-1)인데, mod n에 대해서 되는가?

 

예제

Let p = 3 and q = 17, so N = 51

Choose e = 3 (32의 서로소) and d = 11 (de mod 32 = 1)

Public key = (n,e) = (51, 3)

Private key = (n,d) = (51, 11)

Message, M = 2

Encryption : E(51,3)(2) = $2^3$ mod 51 = 8

Decryption : D(51, 11)(8) = $8^11$ mod 51이 2이 되어야한다

 

이러한 곱셈 연산을 얼마나 빨리 할 수 있는지에 대한 것도 중요한 것이다

 

증명

$ed \equiv 1$ mod (p-1)(q-1)이다.

따라서 $ed -1 \equiv 0$ mod (p-1)(q-1)이 된다. 

\(ed -1 \equiv\ 0) mod (p-1)

\(ed -1 \equiv\ 0) mod (q-1)

ed -1 = k(p-1)이다. (배수)

1. ed = k(p-1) + 1

2. ed = l(q-1) + 1

 

1번에 대해서 확인하겠다

$c^d$ mod p = M

$c^d = M^{ed} = M^{k(p-1)+1}$

$M^{k(p-1)+1}$ mod p $equiv M^{k(p-1)} \cdot M$ mod p

$\equiv (M^{p-1})^k \cdot M$

페르마 소정리에 의하여 M mod p이 된다

 

2번에 대해서 확인하겠다.

$c^d$ mod q = M

$c^d = M^{ed} = M^{l(q-1)+1}$

$M^{l(q-1)+1}$ mod q \(equiv M^{l(q-1)} \cdot M\) mod q

$\equiv (M^{q-1})^l \cdot M$

페르마의 소정리에 의하여 M mod q가 된다.

 

따라서 $c^d$ mod p $\equiv$ M mod p and $c^d$ mod q $\equiv$ M mod q

$c^d - M \equiv 0$ mod p and $c^d - M \equiv 0$ mod q

$c^d$ -M = k'p, $c^d$ -M = l'q가 된다.

 

$c^d$ - M = mpq이다 

$c^d$ - M $\equiv$ 0 mod pq가 된다 

 

따라서 $c^d \equiv M$ mod n이다.

 

현재

1024bits의 키를 사용한다

복호화 하는데에 우주의 나이만큼 필요하다

장단점

장점

• 보안 강도가 높음 (안전함)
• 키 분배가 매우 효율적
• 키 관리가 매우 효율적 - 사용자 수가 늘어도 비밀로 유지해야하는 키의 개수가 증가하지 않음

단점

• 연산이 복잡하고 느림
• 공개키 관리 (공개키를 위변조할 수 있음) -> 추가 인증이 필요하다