[비대칭키 암호 시스템] 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의 키를 사용한다

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

장단점

장점

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

단점

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