암호에 대한 이해 - RSA

RSA Encryption에 대해서 공부해 봅시다~

 

 

● 사용자 public key(n,e)

임의의 두 소수 p,q의 곱으로 이루어진 합성수 n만 공개를 하고 어떤 p,q로 곱해져있는지 절대로 공개하면 안됩니다.

(p-1)(q-1)의 서로소인 아무거나 e를 공개키로 합니다.

 

● 사용자 private key(n,d)

d를 구하려면 e는 공개된 값이고 은 multiplicative group이기 때문에 역원이 존재합니다. d는 mod (p-1)(q-1)상에서 역원만 구하면 되는데 p,q를 알아야 구할 수 있습니다. p,q만 알면 이미 알려진 e의 역원 구하는 것은 쉽습니다. 따라서 n에 대한 p,q를 아는 사람만 비밀키를 구할 수가 있습니다.

 

그러면 비밀키의 안정성은 결국 현재 n을 구성하는 p,q가 무엇인 모른다는 것에 있습니다. p,q를 모르면 (p-1)(q-1)을 절대 알아내지 못합니다. 아직까지도 큰 합성수가 주어지면 이것에 대한 p,q를 알아내는 알고리즘이 없습니다. 따라서 소인수분해의 어려움에 기반을 하고 있다고 말할 수 있습니다.

 

● Encryption

상대방의 공개키를 e라고 했을 때

 

입니다. 아주 간단합니다. (원래는 이렇게 되면 모든 평문에 대해서 암호화한 암호문이 같게 되서 안되지만..기본은 이렇다)

 

● Decryption

상대방은 C를 가지고 자신의 비밀키 d승만 해주면 복호화가 됩니다.

 

입니다. 이기 때문에 M이 나옵니다.

결론적으로 입니다.

 

 

1977년에 RSA공개를 할때 독자들에게 N값 한 개를 공개했는데 1994년에 되어서야 600명으로 이루어진 지원자팀이 p,q를 발견할 수 있었습니다. 이때만 하더라도 256bit키를 사용을 했는데 현재는 1024bit키를 사용하기 때문에 N이 어마무시하게 큰 숫자가 되고 이 숫자에 대한 p,q를 찾는 것이 굉장히 힘들어서 그만큼 RSA가 안전하다고 할 수 있습니다.

 

 

비대칭키 암호 알고리즘의 장점

☞ 보안 강도가 높습니다. 키 분배, 키 관리가 굉장히 효율적입니다.

 

비대칭키 암호 알고리즘의 단점

☞ 수학적 연산을 기반(지수 연산)하고 있어서 연산이 복잡하고 수행 속도가 느립니다.

 

대칭키와 비대칭키가 명확하게 장단점이 존재하는 것을 알 수 있습니다. 사람들은 두 개의 것의 장점만을 뽑아내서 더 좋은 것을 만들기 마련입니다. 그래서 나온 것이 Hybrid 암호 알고리즘 입니다.

 

다음 글에서는 Hybrid 암호 알고리즘에 대해서 짧게 공부해 보겠습니다~