암호화
- 암호화 방식은 크게 대칭키와 비대칭키가 있다
https,ssh등 여러곳에서 비대칭키(= 공개키 + 비밀키) 방식을 사용한다
1. 대칭키
- 대칭키는 우리가 간단하게 생각할 수 있는 암호화 방식이다
- 알파벳을 두 칸 옮기는 암호화 방식을 예로 들어보자
암호화 알파벳 + 2 , 복호화 알파벳 - 2
암호화: 알파벳 + 2
a + 2 = c
b + 2 = d...
z + 2 = b
- 이렇게 암호화한
dcpcpc를 복호화해보면banana임을 알 수 있다
복호화: 알파벳 - 2
d - 2 = b
c - 2 = a
p - 2 = n...
c - 2 = a
-
이 방식의 치명적인 단점은 암호화/복호화 방식 둘중 하나라도 털리면 원리가 탈로나 암호문을 해독당할 수 있다는 것이다
-
따라서 한쪽이 털려도 원리가 쉽게 파악되지 않는
비대칭키를 사용한다
2. 비대칭키
- 비대칭키는 공개키와 비밀키로 이루어져 있다
- 공개키와 비밀키는 기능이 완전히 같다
- 공개키로 암호화하고 비밀키로 복호화
- 비밀키로 암호화 하고 공개키로 복호화
비밀키
- 둘 다 알려지면 암호가 해독되므로 하나는 비공개로 보관해야한다
- 두 키의 구분을 위해 비공개키를 비밀키라 부르고 나머지 하나를 공개키라 부른다
공개키
-
인터넷상에서 상대와 서로 암호화/복호화를 하려면 두 명 다 키가 필요하다
-
둘 중 하나의 키를 상대에게 전송해야 하는데 이 때 공개키 를 자유롭게 주고받을 수 있다
- 키 하나로는 복호화가 불가능
https의 비대칭키 사용
서버에서 비밀키로
response 메세지를전부 암호화해서 클라이언트에게 전달한다클라이언트는 해당 사이트의 인증서를 확인해서 인증기관으로부터 공개키를 발급받는다
발급받은 공개키로 암호화된 해당사이트의
response 메세지를 복호화한다
-
이 과정에서 서로 주고 받는
http 메세지를 중간에 ISP나 해커가 알 수 없다 -
그러면 여기서 드는 의문!!!
- 왜 공개키를 해커한테 뺏겨도 암호문이 해독되지 않는것인가?
- 이것을 알기 위해서는 RSA암호방식의 원리를 이해해야한다
3. RSA암호
- RSA는 창시자들의 이니셜을 따서 지었다 (Ron Rivest, Adi Shamir, Leonard Adleman)
- 1983년에 특허가 등록되었고 2000년 9월 특허가 만료되어 현재는 자유롭게 쓸 수 있다
공개키와 비밀키가 왜 이런식으로 만들어지는지 이해하려면 '정수론'을 공부해야한다.
거기까지 공부하면 너무 어려우므로 이런방식으로 만들어지는구나 정도만 생각하면 좋을것 같다.
또한 만들어지는 과정 조차도 수학적인 내용(mod)이 들어있으므로 부담이 가면 1), 2)를 건너뛰고 3)을 보길 바란다.
시작(수학인 어려운부분은 건너뛰어도 좋은 부분) 건너뛰고 3)번으로 가기
1) RSA 공개키, 비밀키 만들기
핵심 공식 2 가지
암호문 = 평문^E (mod N)
평문 = 암호문^D (mod N)
- 위 두 식으로 암호화와 복호화를 할 수 있다
암호화평문 >> 암호문복호화암호문 >> 평문
- 그러면 이제 저 두 식에 필요한
N,E,D를 구해보자
1. N을 구한다
-
두 소수
p,q를 구하고 그 둘의 곱을N이라고 한다. -
쉬운 예제로
p = 3,q = 11를 들어보자N = 3 x 11
= 33
-
N = 33
2. L을 구한다
-
L은E,D를 구하기 위해서만 필요하다 -
lcm은 최소 공배수를 뜻한다> **L = lcm(p - 1, q - 1)** > > p - 1 = 2 > > q - 1 = 10 > > L = 10 -
2와 10의 최소공배수는 10이므로
L = 10
3. E를 구한다
-
1 < E < LE는 1보다는 크고 L보다는 작아야한다 -
gcd(E, L) = 1E와L의 최대 공약수는 1이어야 한다1 < E < 10
gcd (E, L) = 1
E = 3 or 7 or 9
-
L이 10이므로 위 규칙을 만족하는3, 7, 93개가 있다 -
p가 3이었으므로 구분될 수 있게
E = 7로 정하겠다
4. D를 구한다
-
1 < D < LE x D = 1(mod L)
7 x D = 1 (mod 10)
E = 7
-
위를 만족하는 수는 3이 있으므로 3으로 정한다.
결과
N = 33,E = 7,D = 3N 과 E가 한 쌍,N 과 D가 한 쌍으로 총 두 개의 키가 만들어졌다.- 둘 중 하나를 공개키로 둘중 하나를 비밀키로 설정하면 된다
- 서로 이름을 바꿔도 무관하지만 둘 중 하나는 절대 공개돼서는 안된다
2) 공개키와 비밀키로 암호화 및 복호화 하기
N = 33, E = 7, D = 3 을 바탕으로 만들어진 두 개의 키
-
N 과 E -
N 과 D
숫자 평문 = 2를 N과 E 로 암호화 해보자
암호문 = 평문^E (mod N)
암호문 = 2^7 (mod 33)
= 128 (mod 33)
= 29 (mod 33)이다.
- 128를 33으로 나눈 나머지는 29다
- 암호문은 29가 되었다.
29를 N과 D 로 복호화 해보자
- 암호화 하기 전의 평문이 2였으므로 복호화해서 결과가 2가 나오면 성공이다
평문 = 암호문^D (mod N) 이므로
= 29^3 (mod 33)
= 24389 (mod 33)
= 2 (mod 33)
-
24389를 33으로 나눈 나머지는 2이다.
-
원하던 결과인 2가 나왔다.!!!
끝(수학인 어려운부분은 건너뛰어도 좋은 부분)
3) 결론 왜 RSA를 쓰는가?
- p와 q를 통해
N = p x q = 3 x 11과L = (p - 1) x (q - 1) = 2 x 10을 구하고 L로부터E와D를 구했다- 공개키 (
N=33과E=7)를 해커가 알아냈다고 하더라도D를 구하기위해서는 중간과정인L이 꼭 필요하다 - 하지만
L을 구하려면N=33을 두 소수로 인수분해 해야한다
두 소수로 인수분해
33은 작은 숫자이므로 인수분해가 쉽지만 몇백자리 혹은 그 이상이 되는 두 소수의 곱은 인수분해하기가 정말 어렵고 컴퓨터 조차도 구하기 힘들어한다
예를들어 10400은 인수분해하기가 쉽지만 두 소수의 곱인 10403은 인간이 인수분해하기 정말 어려운 수다. 답 확인
구글에 RSA 암호를 해독하는데 걸리는 시간을 검색해 보면
이런 결과가 나온다
300조년
하지만 [양자컴퓨터가 개발되면 성능이 너무 좋아서 이 계산이 10초만에 끝난다](https://www.quintessencelabs.com/blog/breaking-rsa-encryption-update-state-art/#:~:text=It would take a classical,RSA-2048 bit encryption key.)고 한다. (출처: 위 캡처이미지 링크) 그래서 뉴스에서 양자컴퓨터이야기가 나올때마다 현재의 암호화체계가 위험해진다는 말이 나오는 것이다
끝!
답: 10403 = 101 x 103
