[암호학] 암호학의 미궁 - 암호학의 발달 과정, Diffie-Hellman, RSA, 공개키 암호화

암호학의 미궁

암호학은 정보를 보호하기 위한 언어학적 및 수학적 방법론을 다루는 학문으로 수학을 중심으로 컴퓨터, 통신 등 여러 학문 분야에서 공동으로 연구, 개발되고 있다. 초기의 암호는 메시지 보안에 초점이 맞추어져 군사 또는 외교적 목적으로 사용되었지만, 현재는 메시지 보안이외에도 인증, 서명 등을 암호의 범주에 포함시켜 우리의 일상에서 떼 놓을 수 없는 중요한 분야가 되었다. 현금지급기의 사용, 컴퓨터의 패스워드, 전자상거래 등은 모두 현대적 의미의 암호에 의해 안정성을 보장받고 있다. - wiki

Cypher와 Code

Cypher와 Code는 암호학의 기본 언어라고 보면 된다.

Cypher	Code
정보를 이해할 수 없도록 암호화 하거나 다시 해독하기 위한 일련의 단계를 정의한 알고리즘이다.	어떠한 평문의 부호화 과정이나 숨겨진 뜻을 일컫는 말이다. 하지만 암호학에서는 좀더 깊은 뜻이 들어 있다; 이는 평문의 어떠한 부분을 대체한 것(예를들어 단어, 문장 등) 을 말한다.

Alice가 Bob에게 “Hello~”라는 메시지를 보낸다고 하자. Cypher와 Code로 인코딩하면 다음과 같다.

Cypher: “324··” 메시지와 1대 1로 대응한다.
Code: ⭐️ 그냥 하나의 이모티콘으로 대체했다.

Steganography vs Cryptography

Steganography

데이터 은폐 기술 중 하나이며, 데이터를 다른 데이터에 삽입하는 기술 혹은 그 연구를 가리킨다

Cryptography

정보를 보호하기 위한 언어학적 및 수학적 방법론을 다루는 학문으로 수학을 중심으로 컴퓨터, 통신 등 여러 학문 분야에서 공동으로 연구, 개발되고 있다.

Cryptography안에 cypher, code가 포함되어 있다.

Cryptography	Steganography
Alice가 Bob에게 공개적으로 메시지를 보냈다는 것을 공개해도 이 둘을 제외한 다른 사람들은 못 알아듣게 전달하는 방법	그 자체를 숨기는 기법으로, Alice가 Bob에게 메시지를 보냈다는 것 자체를 아무도 모르게 전달하는 방법

Steganography 단점

만약 적에게 해당 메시지가 넘어가게 되면 중요한 기밀이 바로 노출된다. (여러 사례)

제 2차 세계 대전 중과 전후에 스파이 요원들은 사진을 찍어 만든 마이크로도트를 이용해 정보를 주고받았다. 제 2차 세계 대전 마이크로도트는 종이에 박혀 있었고, 빛이 반사되는 것을 관찰함으로써 반사 될 수 있는 콜로디온(collodion)과 같은 접착제로 덮여 있었다. 대체 기법은 엽서 가장자리에 잘린 슬릿에 마이크로도트를 삽입하는 것이 있다.
예를들어, 신문에 “is dead**.**” → . 이 점에 마이크로도트를 붙였다가 적이 신문이 반짝거리는 것을 보고 노출된 사례가 있다.

Cryptography 발달 과정

Caesar Cypher란?

암호학에서 다루는 간단한 치환암호의 일종이다. 카이사르 암호는 암호화하고자 하는 내용을 알파벳별로 일정한 거리만큼 밀어서 다른 알파벳으로 치환하는 방식이다

“I love you”를 2칸씩 오른쪽으로 밀기 → “k mgxg agw”
1587.2.18 엘리자베스 1세 암살 혐의로 메리가 처형당한 사건이 있었다. 메리는 암호가 해독되어서 처형되었는데 그 암호가 Caesar Cypher 였다.

1977 Diffie-Hellman 키 교환 방식

그리고 1,2차 세계 대전때 암호가 해독되어 수천명이 처형당했다. Alice가 Bob에게 메시지를 암호화해서 전달해야 하는데 독일인이 대륙에가서 key를 전달하는 역할(spy)를 하다가 많은 사람이 Eve(첩보기관)에 검거된 사례가 빈번했다.

Alice→ key전달자(spy) → Bob
Eve는 적의 첩보기관이다

그래서 Diffie가 암호학 전달 기법에 대해 새로운 생각을 해냈는데 바로 Key를 안 보내고 Bob이 열 수 있는 방법이었다. 지금 '디피-헬먼 키 교환(Diffie–Hellman key exchange)'라고 불린다. 이 방식은 두 사람이 암호화되지 않은 통신망을 통해 공통의 비밀 키를 공유할 수 있도록 한다. 휫필드 디피와 마틴 헬먼이 1976년에 발표하였다.

Alice의 자물쇠를 a라 하고, Bob의 자물쇠를 b라 하자.

Alice가 자신의 자물쇠 a를 채워서 상자를 보낸다. → Alice 자물쇠
Bob이 해당 상자를 받고 자신의 자물쇠 b를 채워서 Alice에게 다시 보낸다. → (Alice 자물쇠, Bob 자물쇠)
Alice는 자신의 자물쇠를 풀고 다시 Bob에게 보낸다. → Bob 자물쇠
Bob은 자신의 자물쇠를 풀어 메시지를 확인한다.

단, 통신이 2번이나 왔다갔다해야 된다는 단점이 있었다.

Diffie-Hellman 키 교환 방식

이 단점을 보완하고자 니온 것이 바로 DH 키 교환 방식이다. 공개키 암호시스템의 하나로 통신 한번에 끝낼 수 있는 방법을 고안해냈다.

공개 키에 대해서 먼저 알아보자. 마찬가지로 Alice와 Bob이 있고, 이를 감시하는 Eve가 있다. Eve는 A → B에서 보낸 것, B → A로 보낸 것을 완벽히 파악한다고 하자. Alice와 Bob은 최초의 약속을 맺어 "빨강"을 서로 알고있다. A가 갖고있는 자신의 색은 "노랑"이고, B가 갖고있는 자신의 색은 "파랑"이다. 이는 자신을 제외하고 아무도 모른다. 그리고 이들은 통신을 위해 공유 비밀(빨강)과 개인 키(노랑, 파랑)을 각각 섞어 서로에게 전송한다.

A : 노랑, B : 파랑
A: (빨노), B: (빨파)
A는 B가 파란색을 섞은지 모름. B는 A가 노란색을 섞은지 모름. 각자 개인 키만 알고 있을 뿐이다.
Eve가 보는 것은 주황색, 보라색으로 노랑, 파랑, 빨강의 존재를 모른다.

A와 B는 서로 메시지를 받고 자신의 색을 섞으면 둘이 모두 (빨노파)를 갖게 된다. 서로의 공통 약속(공개 키)만으로 상대방의 개인 색을 모른 채 공통 키가 생성된다.

이게 강력한 이유가 뭐냐면 A, B는 서로가 갖고있는 색(private)을 모르는 상태에서 공통된 색(common)을 갖게 되는 것이다. 이제 두 사람 만이 아는 공통된 색(common, 비밀 키)로 대칭 키 암호 통신을 할 수 있다.
그러면 Alice는 Bob의 암호 통신을 (공통 약속 + 자신의 키=빨강)로 복호화할 수 있고, 반대로 Bob은 Alice가 보낸 암호 통신을 (공통 약속 + 자신의 키=파랑)로 복호화할 수 있다.

이렇게 디피-헬먼 키 교환은 기초적인 암호학적 통신 방법을 수립하였다. 암호 키를 교환하는 하나의 방법으로 두 사람이 암호화되지 않은 통신망을 통해 공통의 비밀 키를 공유할 수 있게 되었다. 그렇게 발견한 Diffie, Merkle, Hellman 암호를 수학적으로 시스템 해줄 수 있는 사람을 구했는데 1978년 그 사람들이 바로 Rivest, Shamir, Adleman이었다. 그렇게 1978년 RSA 시스템이 탄생한다. 일명 RSA가 고안해낸 수학적인 방식은 modulator 함수를 이용한 방법이었다.

RSA가 고안해낸 암호의 안정성은 큰 숫자를 소인수 분해하는 것이 어렵다는 것에 기반을 두고 있다. 그러므로 큰 수의 소인수 분해를 획기적으로 빠르게 할 수 있는 알고리즘이 발견된다면 이 암호 체계는 가치가 떨어질 것이다. 안정성에 대해서는 아래에서 Modular와 페르마 소정리를 통해 더 깊게 알아 볼 것이다.

대칭 키 암호 생성 방법

Alice와 Bob이 보안이 보장되어 있지 않은 환경에서 서로 비밀 메시지를 주고 받고 싶다고 가정하자. Bob이 Alice에게 메시지를 전달하기 위해서는 Alice의 공개키가 필요하다. Alice는 아래와 같은 방법을 통해 공개키와 개인키를 제작한다. (단, 서로가 최초의 약속을 알고 있어야 한다.)

최초의 약속(빨강): f(x) = 7^x (mod 11)
A는 3(노랑), B는 5(파랑)을 가지고 있다. 서로 이 숫자에 대해서 모른다.

먼저, 서로가 가진 키를 최초의 약속과 섞는다.

A는 f(3) = 7^3(mod 11) = 2(a)를 가진다.
B는 f(5) = 7^5(mod 11) = 10(b)를 가진다.

이젠 서로가 보유한 정보를 공유한다. 그리고 이는 Eve가 파악할 수 있다.

A는 B에게 2(a)를 보낸다
B는 A에게 10(b)을 보낸다.
Eve는 2, 10이란 정보를 알 수 있다. 그런데 이를 알아도 최초의 약속이 뭔지 모르므로 공개키가 뭔지 알 방도가 없다.

A가 아는 정보	Eve	B가 아는 정보
최초의 약속: f(x) = 7^x (mod 11) A 개인키: a = 3 B에게 건네받음: β = 7^b(mod 11) = 10	최초의 약속: f(x) = 7^x (mod 11) A → B에게 전달: 7^a(mod 11) = 2 A ← B에게 전달: 7^b(mod 11) = 10	최초의 약속: f(x) = 7^x (mod 11) B 개인키: 5 A에게 건네받음: α = 7^a(mod 11) = 2

서로에게 받은 정보에 각각 자신의 개인 키를 넣어 계산한다.

A는 β^a = 10^3 = 1000 (mod 11) = 10
B는 α^b = 2^5 = 32 (mod 11) = 10
서로의 정보를 대입시켜 공통적으로 10을 얻게되어 대칭 암호키를 얻게 된다. modulator 공식에 의해 α^b = β^a이므로 서로 공개키를 공유하게 된다.

A가 아는 정보	Eve	B가 아는 정보
최초의 약속: f(x) = 7^x (mod 11) A 개인키: a = 3 B에게 건네받음: β = 7^b(mod 11) = 10 대칭키: β^a = 10^3 = 1000 (mod 11) = 10	최초의 약속: f(x) = 7^x (mod 11) A → B에게 전달: 7^a(mod 11) = 2 A ← B에게 전달: 7^b(mod 11) = 10	최초의 약속: f(x) = 7^x (mod 11) B 개인키: 5 A에게 건네받음: α = 7^a(mod 11) = 2 대칭키: α^b = 2^5 = 32 (mod 11) = 10

공개키 알고리즘의 핵심 modulator

그럼 이제 이를 수학적으로 어떻게 RSA 알고리즘을 만들었는지 알아보자. a를 m으로 나눈 나머지와 b를 m으로 나눈 나머지가 같으면 a와b는 법 m에 대하여 합동이라고 표현한다. 기호로는 a≡b (mod m) 이라고 표시한다. ex. 5 ≡ 3 (mod 2)

modulator 공식

a ≡ b (mod p), c ≡ d (mod p)이라고 할때, modulator는 다음과 같은 성질을 지닌다.

(a±c) ≡ (b±d) (mod p)
(ac) ≡ (bd) (mod p)
(a/c) ≡ (b/d) (mod p) (단, a/c, b/d가 자연수일 때)
ex) 28 ≡ 22 (mod 2) → 14 ≡ 11 (mod 2)

안전성 검증 - 페르마의 소정리 증명

RSA의 정확성에 대한 검증은 페르마 소정리에 근거하고 있다. a, p가 서로소일 때 (p는 소수), a^(p-1)을 p로 나누면 나머지가 1이다.

a^(p-1) ≡ 1 (mod p)

증명은 다음과 같다.

a ≡ r(1) (mod p)
2a ≡ r(2) (mod p)
3a ≡ r(3) (mod p)
...
(p-1)a ≡ r(p-1) (mod p)여기서 ri ≠ rj 이다. 즉, p로 나눈 나머지 r(i)~r(p-1)은 1~p-1로 이루어져 있는 것이다. 이를 모두 곱하면 (p-1)!a^(p-1) ≡ (p-1)! mod(p)이 된다. 여기서 공통된 항을 제거해주면 다음과 같은 식이 도출된다.
a^(p-1) ≡ 1 mod( p)

예) a =5, p=7

5^6 을 7로 나누면 나머지 1이다. r값은 전부 다르고 1~6으로 이루어져있는 것을 볼 수 있다.

5 ≡ 5 (mod 7)

2*5 ≡ 3 (mod 7)

3*5 ≡ 1 (mod 7)

4*5 ≡ 6 (mod 7)

5*5 ≡ 4 (mod 7)

6*5 ≡ 2 (mod 7)

이를 모두 곱하면 6!*5^6 ≡ 6! (mod p)가 되고, 5^6 ≡ 1 (mod p)가 된다.

RSA 공개 키 암호시스템

그렇게 발견한 DH키 교환 방식이 나온 이후 RSA가 modulator 함수를 이용한 키 생성 방식을 만들어내고 그렇게 1977년 공개 키 암호 방식인 RSA 암호 시스템이 탄생한다. 일명 대칭키와 비교하여 비대칭키 방식이라고 부르기도 한다.

대칭 키는 암호화와 복호화에 같은 키(공통 키; 대칭 키)를 쓰는 알고리즘을 뜻한다.
비대칭 키는 두 개의 키를 사용한다. 공개 키(public key)는 모두에게 알려져 있고 암호화(encrypt)하는데 쓰이며, 암호화된 메시지는 개인 키(private key)를 가진 자만이 복호화(decrypt)하여 열어볼 수 있다.

1. 메시지 위조 문제 해결

기존 대칭키 방식에 문제가 있었다. 검증까지 완료했으니 전세계 돈 거래를 책임지고 있는 RSA 시스템에 대해 알아보자. 마찬가지로 Alice가 Bob에게 보내고, Eve가 감시한다.

Alice가 메시지를 a라는 자물쇠를 잠궈서 보낸다.
B가 해독한다 끝.

1) 나 편지함 있다.

Bob은 편지함이 생겨서 신났다. 그래서 이를 자랑하기 위해 치킨 기프티콘을 받고 싶은 사람은 자신의 편지함에 각 편지를 상자에 담고 자물쇠로 잠궈서 보내라고 말했다.

Alice가 “Me!”라고 하고 보냈다.
그런데 문제가 있다. 알고보니 Charles가 Alice의 다이어트를 방해하기 위해서 Alice라고 속이고 Bob에게 메시지를 보낸 것이다. Bob은 그것을 Alice가 썼는지 다른 사람이 위장해서 썼는지 알아차릴 방도가 없기 때문에 Alice에게 치킨 기프티콘을 보냈다. 그래서 결국 Alice는 다이어트에 실패하게 되었다...

2) 너만 편지함 있냐?

Alice는 화가나서 자신의 편지함을 만들었다. 그래서 앞으로 Alice는 자신의 메시지를 자신의 편지함에 잠궈서 보내기로 모두에게 알린다. 그래서 이번에는 진짜 Alice가 “Me!”라고 쓴 것을 자기 편지함에 넣고 거꾸로 잠근다음 자기 편지함을 Bob의 편지함에 넣어서 보냈다.

그러면 Bob은 자신의 편지함에 있는 Alice의 편지함을 Alice가 공개 키로 열 수 있으면 이 메시지는 Alice가 보낸 편지임을 판별할 수 있게 된다. 이러한 방식을 디지털 서명이라고 한다.

자신의 메시지는 자신의 암호로 걸어잠근다. 그리고 오직 자신의 공개키로만 열 수 있다.

2. RSA 비 대칭키 암호 통신 과정 (디지털 서명 + 암호/복호 통신)

디지털 서명 + 암호/복호 통신으로 RSA 암호 통신은 수신자의 신원도 확인되고 서로가 안전하게 통신을 할 수 있게 해준다.

디지털 서명: 송신자는 송신자의 개인키로 메시지에 “서명”하고 수신자는 송신자의 공개키로 수신자의 신원을 “검증” 한다.
암호/ 복호 통신: 송신자는 수신자의 공개키로 메시지를 암호화하고 수신자는 수신자의 개인키로 복호화 한다.

흐름을 이해했다면 이제 비 대칭키 암호 통신 과정을 살펴보자. Alice와 Bob이 보유한 키는 다음과 같다.

Alice: 33 = 3x11

33은 public key
3x11은 private key (소인수분해)

Bob: 65 = 5x13

65은 public key
5x13은 private key (소인수분해)

물론, 실제로는 공개 키의 값을 10^310정도의 수를 사용하기 때문에 소인수분해 해독이 거의 불가능하다.. 이를 해독하려면 우주의 나이보다 더 오래 걸린다. 그래서 Alice와 Bob이 통신하는 방법은 다음과 같다.

Alice는 자기 편지함에 private key(3x11)로 잠근다. → Alice 자물쇠
그리고 Bob의 편지함에 넣고 Bob의 public key(65)로 잠근다. → (Alice 자물쇠, Bob 자물쇠)
이를 받은 Bob은 자신의 편지함을 Bob의 private key(5x13)로 연다. → Alice 자물쇠
그리고 Alice의 편지함을 Alice의 public key(33)으로 연다

암호 통신 발달에 의한 문제점

암호 통신이 거의 완벽하게 발달함에 따라 엄청난 문제점이 생겼다.

무기 밀거래
마약
도박
검은 자금
테러

→ 이와 같은 통신을 국가에서 통제 불능 상태에 빠졌다

→ 이러한 암호 혁신은 그렇게 2001년 9월 테러가 발생하게 된다

어떻게 제어해야 할까?

바로 career(경력)를 쫓는 방법으로 찾아낸다.

잠수함을 어떻게 찾아낼까?

태평양을 모두 물을 퍼낼 수는 없는 노릇이고 SONAR를 바다에 담궈서 반사파로 탐지하는 데에도 한계가 있다. 그래서 career를 사용한다.

잠수함을 만드려면?

→ 수학자, 과학자 들이 필요하다. 돈도 엄청나게 필요하다.

→ 그들은 아파트나 거주 공간이 있을 것이고, 그들의 돈을 추적하고, 그들이 교육받는 기관을 조사한다.

→ 그래서 그들이 만드는 곳을 파악하고 잠수함이 바다에 들어가기 전부터 그 주변에 이미 SONAR를 설치한다.

→ 거기서부터 잠수함의 Career가 작성된다. 그리고 특정 주기마다 최대 움직일 수 있는 거리를 파악하고 계속해서 추적한다.

→ 그래서 서로의 잠수함이 어디있는 지를 파악하고 있다.

resource

https://www.youtube.com/watch?v=PW8opHbVfKE

그릿 속의 해빗