암호화 간단하게 알아보기

우선 암호화에 대한 얘기부터 해보도록 한다. 누군가 내 정보를 탈취해가는 것을 막는 방법 중 하나는 암호화다. 암호화 방법 중에는 치환과 전치가 있는데, 치환(substituation)은 글자를 바꾸는 것이고 전치(transposition)는 순서를 바꾸는 것을 의미한다.

어느 방법을 선택해야 할까? 답은 치환과 전치를 적절히 섞어 암호화를 해줘야 한다. 암호화도 너무 간단하게 하면 좋지 않다. abcd1234를 efgh5678로 바꾸는 것처럼 투명하고 뻔한 걸 하면 좋지 않다. 그렇담 암호화는 어떻게 해야 하는 걸까? 정부에서 권고하는 알고리즘들이 있다.

 

소프트웨어 개발보안 가이드(행정안전부, 2021)

해당 표를 보면 분류로 대칭키 암호 알고리즘, 해시함수, 공개키 암호 알고리즘이 있다.

• 대칭키 암호 알고리즘 : 대칭키 암호에서 ‘암호화키'와 ‘복호화키’는 같다 → 똑같은 키를 가지고 있는 사용자가 아니라면 해당 정보를 확인할 수 없다. 송, 수신자가 같은 키를 가지고 있어야 한다.
  • 키의 안전한 교환이 중요
  • 공개키에 비교하면 빠르다
• 해시 함수 : 수학적인 연산으로 원본 메시지를 변경한다. (ex → A : 65)
  • 원본 메시지를 알면 암호화된 메시지를 구하기 쉬우나, 암호화 메시지로는 원본 메시지를 구하기 어렵다.
  • 원본과 암호화 메시지가 1:1 대응되는 점을 악용한다면 금방 어떤 글자가 어디에 대응되는지 알아낼 수 있는 단점이 있다.
  • 이를 해결하기 위해 SALT를 사용한다. 마치 양념을 치는 것처럼, 원본 메시지에 임의의 문자열을 덧붙인다. 따라서 원본 비밀번호의 암호화 된 값을 알아내더라도 솔트가 붙어 있다면 비밀번호를 알아내기가 힘들어진다. 비밀번호에 고유 솔트가 있을 때 암호화된 값을 비교하면 인증에 성공한다 🙂
• 공개키 암호 알고리즘 : 공개키 암호에서 ‘암호화키'와 ‘복호화키’는 다르다

여기서 공개키 암호 알고리즘을 조금 더 자세히 정리해보고자 한다.

---

공개키 암호 알고리즘(Public Key Cryptography)

수신자는 사전에 암호화 키를 송신자에게 알려준다. 이 암호화 키는 아무나 알게 되도 상관없기 때문에 공개키라고 한다.
송신자는 그 암호화 키를 써서 메시지를 암호화 해서 수신자에게 보낸다. 수신자는 자신의 복호화키(개인키)로 복호화 한다.

Alice, Bob, Eve 세 사람이 있다.

공개키 암호 알고리즘, 출처 위키백과

Story : Bob은 데이터를 보내고, Alice는 데이터를 받는다. 이때 보내는 게 중요한 정보라서 중간에 Eve가 탈취하려고 한다. 그러한 일을 방지하기 위해 Bob은 (Alice가 공개한) Public 키로 데이터를 암호화해서 보낸다. 그리고 Alice는 Bob에게 받은 메시지를 자신의 Private Key로 복호화한다. 만약 Eve가 Bob이 보낸 메시지를 뺏더라도, 복호화 할 수 있는 키가 없기 때문에 오리무중에 빠진다.

 

어떤 느낌이냐면 대칭키의 경우 보내는이와 받는이는 모두 같은 열쇠를 가지고 있다. 보내는이가 상자 안에 보물을 넣고 잠군 다음 받는이에게 보낸다. 받는 이는 가지고 있는 열쇠로 보물상자를 열수있다.

비대칭키의 경우, 받는이는 자물쇠를 전국 곳곳에 뿌린다. 보내는 이는 상자에 보물을 넣고 자물쇠로 잠근 다음, 받는 이에게 보낸다. 받는 이는 가지고 있는 특별한 열쇠로 자물쇠를 열 수 있다.

질문 → 공개키 알고리즘은 해시 함수와 매우 유사하지만 복호화하지 않는다는 차이가 있는 건가? : 그렇다.

공개키 알고리즘 예시 - RSA

약간의 이산수학. RSA는 소인수분해가 힘들다는 것에서 착안했다. 현대 수학과 기술로는 소인수분해를 하는데 너무 많이 힘이 들기 때문에 가능한 알고리즘

 

일단 소수 두 개, p와 q를 준비한다. (보통 매우 큰 소수다)

public key : (N = pq, e)
private key : ((p-1)(q-1), d)
e는 private key와 서로소인 임의의 수다. d는 e mod (p-1)(q-1)의 inverse다.

 

Bob은 Public Key를 알고 있고, Alice는 Private Key와 Public Key를 모두 알고 있다.

엿듣고 싶어 하는 Eve 또한 Public Key만 알고 있다.

 

Encryption :E(x)≡ x^e (mod N) , Bob은 E(x)를 Alice에게 보낸다.

Decryption : y = E(x) , D(y) ≡ y^d (mod N), Alice는 E(x)의 복호화를 해서 원본 메시지 x를 알아낸다.

 

어떻게 알아낼 수 있는가? 라고 묻는다면 수학의 영역이므로 이 글에서 자세히 다루지는 않겠다. 증명은 어렵지 않다!

 

관련해서 RSA 연습문제를 좀 가져왔다. RSA T/F에서 틀린 답만 골라 찍었던 옛일을 개과천선하는 마음으로 정리한다.

1. 만약에 Eve가 d의 값을 알아냈다. Eve는 p와 q도 알아낼 수 있을까 → 못 알아냄. e와 d가 inverse 관계에 있는 걸 알더라도 p와 q를 찾을 수 없다.
2. 앨리스는 공개키 (N, e)와 비밀키 d를 가지고 있다. 이때 Eve는 우연히 공개키 (N,d)를 만들었다. 그렇다면 Alice는 Eve가 받는 모든 메시지를 해독할 수 있을까? →가능하다. 일단 N이 같다면 p와 q를 알고 있다는 셈이다.(왜냐하면 만들었으니까) e의 inverse가 d인것도 알고 있다. 그렇다면~
3. Alice는 공개키 (N, e)를 가지고 있다. 이때 Eve는 공개키 (N,d)를 만들었다. 그렇다면 Alice는 Eve가 받는 모든 메시지를 해독할 수 있을까?→ d와 e가 inverse인걸 모르기 때문에 안된다.
4. Alice가 실수로 p와 q를 그만 잊어버렸지만 d, e, N을 알고 있다. p,q를 구할 수 있을까? → 안됨!
5. Bob이 메시지에 있는걸 한글자씩 암호화한 다음에, Alice에게 한번에 보냈다. Eve는 중간에서 그 메시지가 뭔지 알 수 있을까?→ 된다. Eve도 모든 알파벳을 한글자씩 암호화해보면 된다. 그리고 Bob이 보낸 것과 대조하면 된다. (이는 hash 알고리즘의 취약점과 유사하다.)

활용 : 개인키로 암호화한 내용은 공개키로 해독된다. 그 말은, 개인키로 본인 증명을 할 수 있다는 뜻이다. → 공인 인증서

---

더 알아볼 내용

1. 키 관리를 어떻게 할까?

2. 대칭키의 경우 키 교환방법 -> 디피-헬먼 키 교환

3. 대칭키보다 공개키가 더 좋은 것이 아닌가? -> 암호화 속도는 대칭키가 더 빠르다. 

4. 대칭키 암호화 알고리즘은 어떤 게 있을까?

 

틀린 내용이 있으면 알려주세요. 감사합니다.