[블록체인] 9. 암호학 개념들

암호학(Cryptology)은 비밀 통신과 관련된 과학 분야를 말한다.

암호학은 크게 Cryptography 와 Cryptanalysis 로 분류된다.

Cryptography는 암호를 만드는 것과 관련된 분야, Cryptanalysis 는 암호를 깨는 것과 관련된 분야이다.

위 3개 개념을 통틀어서 Crypto 라고 부르기도 한다.

 

물론 암호학을 공부하는 사람은 이 두 분야를 모두 공부해야 한다.

자신이 만든 암호화 알고리즘이 얼마나 공격에 강력한지 입증하려면 공격 수단에 대한 이해도 필요하기 때문이다.

 

암호학 분야가 달성하려는 목표는 4가지가 있다.

 

1. Confidentiality (기밀성)

A가 B에게 메세지를 보낼 때, B 이외에는 아무도 이 메세지의 내용을 알 수 없도록 만드는 것

현대에는 Symmetric-key ciphers (대칭키 암호화) 방법과 Public-key cipher(비대칭키 암호화) 방법이 사용된다.

 

대칭키는 키가 1개라는 뜻이고, 비대칭키는 키가 2개라는 뜻이다.

키는 암호를 푸는데 필요한 핵심적인 데이터로서 고유한 비밀 값이어야 한다.

대칭키 암호화 방법에는 Block ciphers, Stream ciphers 2가지 종류가 있다.

 

ciphers는 암호화 하려는 메세지를 말한다.

Block ciphers 는 메세지를 블록 단위로 나눠서 암호화 하는 것이고, (요즘 대세)

Stream ciphers 는 계속 이어지는 데이터에 대해서 어떤 특정 연산을 해서 (보통은 exclusive or) 연산 결과를 상대편에게 보내면 상대편이 같은 방법으로 해독하는 방법을 말한다.

 

구체적으로는 원본 메세지와 키패드가 있으면 키 패드와 원본 메세지를 exclusive or 연산한 결과를 보낸다.

암호를 해독하는 상대방은 같은 키 패드에 대해 똑같이 exclusive or 연산을 적용하여 원본 메세지를 알아낸다.

A ⊕ B 를 상대방에게 전달하면 상대방은 여기에 대해 한번 더 exclusive or 연산하므로

A ⊕ B ⊕ B 를 하게 된다.

같은 것을 exclusive or 한 것은 모두 0이고, 어떤 값과 0을 exclusive or 하면 어떤 값이 그대로 나오므로 원본 메세지를 알 수 있게 된다.

 

이때 Stream ciphers 는 어떻게 상대방과 동일한 key 패드를 공유할 것인지가 관건이다.

 

기존의 비트코인은 누구나 비트코인의 트랜잭션을 열람할 수 있어서 기밀성 문제가 대두되었다.

그래서 최근에는 비트코인에 넣는 트랜잭션을 암호화해서 필요하다면 트랜잭션 내용을 복호화해서 보도록 하는 방법이 떠오르고 있다.

 

 

비대칭키(Public-key ciphers) 방식은 비트코인에서 자주 사용하는 방식이다.

이전 글에서 정리하였듯, 공개키와 비밀키 2개가 존재하며, 공개키로 암호화한 것을 비밀키로 해독하거나, 비밀키로 서명한 것을 공개키로 검증하는 두 가지 방식으로 사용될 수 있다.

비트코인에서는 주로 비밀 키로 서명한 것을 공개키로 검증하는 방식을 주로 사용한다.

 

 

 

2. Data Integrity (무결성)

데이가 조작되었거나 바뀌지 않았음을 보장하는 것

데이터를 훼손하는 것을 막는 것은 힘들기 때문에, 무결성을 보장할 때는 훼손 여부를 확인하는 방향으로 접근한다.

훼손 여부를 확인할 때는 해시 함수를 사용해서 해시값이 원본과 같은지 비교하여 검증한다.

대표적으로 성적 데이터의 변경 여부를 확인하기 위해 해시값을 같이 저장해두는 것이 예시이다.

 

하지만 인터넷 상에서는 이것만으로 부족하다.

내가 원본 데이터와 해시값을 인터넷으로 같이 보내는 경우, 공격자가 메세지를 가로채서 자신이 임의로 메세지를 바꾼 뒤 바꾼 메세지에 대해 알려진 해시함수를 다시 적용해서 그 해시값을 보낼 수 있기 때문이다.

 

- Message Authentication Code (MACs)

공격자가 자신의 해시값을 만들어서 보내는 것을 방지하기 위해, 메세지에 송신자와 수신자만 식별할 수 있는 무언가를 포함시켜서 해시를 하자는 아이디어

 

메세지에 더해 A, B가 공유하는 키값을 추가적으로 더한 해시값을 같이 보낸다.

그러면 공격자가 자신 마음대로 메세지를 바꾸고 싶어도, 이 키 값을 알지 못하므로 속일 수 없다.

 

- Digital Signature

비트코인에서 사용하는 전자 서명도 무결성을 위한 방법이다.

서명은 비밀키를 갖고 있는 사람이 할 수 있고, 이 서명이 내 서명이라는 것은 사람들이 나의 공개키로 검증할 수 있으므로 서명을 통해서 메세지의 조작 여부를 확인할 수 있다.

 

 

3. Authentication (인증)

아이디 패스워드, 간편 인증번호와 같은 수단을 통해 이 메세지를 보내는 사람이 수신자가 아는 그 사람이 맞다는 것을 인증한다.

앞서 설명한 MAC, 디지털 서명도 인증에 활용될 수 있다.

 

 

4. Non-repudiation (부인 봉쇄성)

내가 하지 않았다고 발뺌할 수 없도록 하는 것이다.

이를 위해서도 디지털 서명을 활용할 수 있다.

 

비밀키는 나 이외에는 아무도 갖고 있지 않고, 디지털 서명에는 비밀키가 필요하므로, 어딘가에 디지털 서명이 되었다면 그 서명은 내가 한 것으로 간주될 수 밖에 없다. 다른 사람이 나인척 서명했다고 말할 수 없는 것이다.

 

---

기본 정의

cipher, cryptosystem : 평문(plaintext, cleartext)을 암호화(encrypt) 하는데 사용되는 암호화 알고리즘.

chiphertext : 암호문

 

decrypt (복호화) : 암호문을 다시 원래의 평문으로 복원시키는 것

 

키 기반 분류 : 0key (해시), 1key (대칭키 암호화), 2key(비대칭키 암호화, public key crypto)

 

대칭키 : 암호화와 복호화에 사용되는 키가 같은 것

비대칭키 : public key 로 암호화하고, private key로 복호화하는 것 

 

 

Crypto의 기본 가정

crypto 에서는 암호화 시스템(알고리즘)이 완전히 공격자에게 알려져있다고 가정한다.

가볍게 생각해보면 암호화 알고리즘 자체가 숨겨져있는 것이 더 안전하다고 생각할 수 있지만,

암호화 알고리즘의 취약점이 노출되는 순간 어떤 취약점이 공격자에 의해 발견될지 모른다.

따라서 그냥 암호화 알고리즘을 공개를 해두고, 암호학자와 수학자들이 알려진 취약점이 어떤 것들이 있는지 보고서를 작성하도록 해서 폐기하거나 보완하는 식으로 접근하는 것이 더 안전하다.

 

비트코인에서 사용하는 SHA256 해시 알고리즘은 공모전을 통해 선택된 알고리즘이고, 안전하다고 평가받는다.

 

 

---

암호화 알고리즘의 종류

Random Functions (해시 함수)

해시 함수는 임의 길이의 인풋이 들어왔을 때 고정된 길이의 output을 내보내는 함수이다.

이 output은 실제로 해싱을 하기 전까지 어떤 값이 나올지 알 수 없기 때문에 랜덤 함수의 일종으로도 볼 수 있다.

 

 

자료구조에서 배우는 해시는 위 그림과 같은 구조를 하고 있다.

즉, 크립토 해시에서 크립토가 빠진 해시가 위 그림과 같은 구조이다.

키를 해싱한 결과를 256으로 나눈 나머지를 기반으로 데이터를 저장하는 모습을 보여주고 있다.

 

이런 해시는 크립토로는 사용할 수 없다. 빨갛게 칠해진 152번으로 보면 현재 해시 충돌이 발생하여 overflow entry에 데이터가 추가적으로 있는 것을 볼 수 있다.

크립토 해시가 되려면 해시 충돌의 확률을 매우 낮춰야 한다.

 

 

 

크립토그래피 해시 함수는 해시 함수와 다르게 위와 같은 3가지 특징을 가져야 한다.

 

1. Collision resistance

서로 다른 키 값에 대해 같은 결과가 발생하는 것을 해시 충돌이라고 말한다.

Cryptographic Hash Function은 해시 충돌이 발생할 확률이 매우 낮아서 같은 결과를 내는 키 값을 찾는 것이 불가능에 가까워야 한다.

(이론적으로는 반드시 해시 충돌이 발생할 수 있다. 매우 큰 크기의 input에 대해 고정된 output 크기를 내려면 반드시 겹치는 데이터가 존재할 수 밖에 없기 때문이다. 하지만 충돌하는 경우를 찾는 것이 매우 어렵다.)

 

2. Preimage resistance

해시 결과값을 알고 있을 때, 이로부터 원래의 키 값을 알아내는 것이 불가능에 가까워야 한다.

즉, H(x) = y 라고 할 때, y로부터 x를 구하는 것이 매우 어렵다.

다른 말로는 일방향성 성질 (one-wayness)이라고도 한다.

 

3. 2nd-preimage resistance

H(x1) = H(x2) = y 에서 x1 과 y 값을 알고 있을 때 x2 의 값을 알아내는 것이 불가능에 가까워야 한다.

충돌을 찾는다는 점에서 1번 성질과 비슷한데, 1번은 아무것도 모르는 상태에서 무작정 충돌을 찾아야 하고, 3번은 어떤 해시 인풋과 결과를 알고 있을 때, 충돌이 발생하는 또 다른 값을 찾아야 한다는 차이점이 있다.

 

 

 

 

크립토 해시 함수는 다음과 같은 성질도 있다.

위 그림을 보면 어떤 문장이 주어졌을 때 over를 ouer 로 바꾸너나, over를 oevr로 바꾸거나, over를 oer로 바꾸는 등, 정말 작은 변화를 주었음을 알 수 있다. 그런데 이 작은 변화에 대해 해싱한 결과 값은 아무 연관성이 없는 결과가 나오고 있다.

따라서 어떤 값을 지웠다고 해시도 일부값만 지워진 결과가 나온다거나 하는게 아니라 연관성이 없는 다른 값이 나오므로, 해시 결과를 토대로 해시 동작을 유추하거나 input 값을 유추하는 것이 불가능하게 된다.

하지만 이런 특징은 일반 해시 함수라면 가지지 않을 수도 있다. (아스키 코드 값의 합을 나눈다거나 하는 경우)

 

그 밖에도 해시 함수는 다음과 같은 기능을 제공해야 한다.

 

1. Compression : output 크기는 input 크기에 상관없이 고정되어 있어야 한다.

2. Efficiency : h(x)를 계산하는 것은 어떤 x가 오더라도 빠르게 계산할 수 있어야 한다.

3. One-way : pre-image resistance, 결과값으로부터 입력값을 알아내는 것이 어려워야 한다.

4. Weak collision resistance : 2nd preimage resistance, h(x1) 과 x1 을 알고 있을 때, 같은 해시값을 갖는 x2를 알아내는 것이 어려워야 한다.

5. Strong collision resistance : preimage resistance, 어떤 해시 함수에 대해, h(x1) = h(x2) 가 되는 x1, x2 쌍을 찾는 것이 어려워야 한다.

 

 

이 특징 중 4번, 5번 특징이 나타내는 충돌과 관련하여 Birthday Paradox 에 대해 알아보자.

 

- Pre-Birthday Problem

방 안에 N명의 사람들이 있다고 해보자.

이때 N이 얼마나 커져야 내 생일과 같은 사람이 방안에 있을 확률이 1/2을 넘어갈까?

 

이 문제의 풀이 과정은 간단하다.

전체 확률에서 모든 사람들이 나와 생일 다를 확률을 구하면 된다.

 

나와 생일이 다를 확률은 364/365 이므로, 1 - (364/365)^N >= 1/2 을 계산하면 된다.

그리고 이 값의 계산 결과는 N =  253명이다. 생각보다 많은 사람들이 있어야 한다.

 

- Birthday Problem

방 안에 N명의 사람들이 있다고 해보자.

이때 N이 얼마나 커져야 방에 있는 사람들의 생일이 같은 경우가 존재할 확률이 1/2을 넘어갈까?

(이때는 나와 상관없이 방안에 존재하는 사람들에 대해 한 쌍이라도 생일 같기만 하면 된다.)

 

이때의 N = 23 이다.

이전 문제에 비해서 매우 작은 수가 되는 것을 알 수 있다.

 

이 확률 계산은 바구니에 공을 나눠 담되, 어떤 바구니에도 공이 2개 이상 담기지 않게 만드는 것을 생각하면 된다.

(바구니는 생일, 공은 그 생일에 해당하는 사람을 생각하면 된다.)

 

첫 번째 사람이 먼저 생일을 결정하고, 그 생일 바구니에 자신의 공을 넣는다.

두 번째 사람이 자신의 생일을 결정하고, 그 생일 바구니에 자신의 공을 넣는다.

이때 첫 번째 사람이 선택한 바구니에는 공을 넣을 수 없으니 자신의 공이 겹치지 않을 확률은 1 - 1/365 이다.

세 번째 사람이 자신의 생일을 결정하고, 그 생일 바구니에 자신의 공을 넣는다.

이때 첫 번째, 두 번째 사람이 선택한 바구니에는 공을 넣을 수 없으니, 자신의 공이 겹치지 않을 확률은 1 - 2/365 이다.

 

이렇게 k 명의 사람들이 존재한다고 하면 확률은 다음과 같이 계산된다.

 

 

이 값이 1/2 보다 커지도록 하는 k를 찾으면 k = 23이 나온다.

 그리고 이 값은 대략적으로 √n 에 근접한다.

 

방안에 n명이 존재할 때, 이 중에 두 명을 뽑고 이 두 명의 생일이 같을 확률을 구하면 1/365 이다.

다시 또 2명을 뽑았을 때 생일이 같을 확률을 구하면 또 1/365 이다.

이 각각의 사건은 독립적이지는 않지만, 러프하게 계산하기 위해 독립적이라고 치면 nC2 (1/365) 를 계산한 결과가 1/2 보다 커지는 n값을 구하는 것과 같다. 그러면 1/2 은 약분 되고, n(n-1) = 365 가 되므로 대략 n² = 365 가 되어 n = √365가 되는 것을 알 수 있다.

 

 

이를 통해서 한 명의 생일을 기준으로 그 사람의 생일과 같은 생일을 갖는 사람이 존재하기까지 필요한 모수와, 임의의 두 명의 생일이 같은 경우가 존재하기까지 필요한 모수에는 큰 차이가 있음을 알 수 있다.

 

이를 해시 충돌의 내용으로 가져와서 생각해보면, 하나의 x값을 알고 있을 때 h(x) 와 같은 값을 갖는 y 를 찾는 것은 매우 어렵지만,

h() 에 대해서 충돌이 발생하도록 하는 x1, x2 쌍을 찾는 것은 상대적으로 쉽다는 것을 알 수 있다.

 

만약 해시 함수의 결과가 n bit 라면, 가능한 모든 경우의 수가 2^n 이다.

이 해시 함수에 대해 같은 해시값을 갖는 (같은 생일을 갖는) 경우를 찾기까지 랜덤 인풋을 시도해본다면 2^(n/2) 번 시도 했을 때 충돌을 찾을 확률이 1/2 이라는 것과 같다. (위에서 √n 을 구했던 것에 넣으면 된다.)

 

비트코인에서 사용하는 해시 함수는 256bit 결과를 내는 해시 함수를 사용하고 있고, 이 해시 함수에 대해 충돌을 찾으려면 2^128 경우를 시도해봐야 한다. 이 값은 매우매우 큰 값이라서 깨지기가 쉽지는 않지만, 미국 NSA 에서는 이에 근접한 정도는 금방 깰 수 있을 것으로 믿고 있다.

 

반면 대칭키 알고리즘은 해시에 비해서는 깨기가 힘들다.

해시 함수는 0-key 이므로, h(x) = y 를 만족하는 x 값 2개를 찾으면 되기에 2^128만 해보면 1/2 확률로 찾을 수 있지만,

대칭키 알고리즘은 1-key 이므로 정해진 하나의 키 값을 찾을 확률이 1/2이 되기 위해서는 모든 가능한 경우의 수 중에서 절반은 해봐야 하기 때문에 2^255 가지를 해봐야 한다.

 

 

유명한 해시 알고리즘

1. MD5 : 현재는 충돌이 발견되어서 사용을 권장하지 않는다.

2. SHA (secure hash algorithm)

 

SHA-1 : 2017 년에 깨졌다.

SHA-2 family : 비트코인에서 SHA2 family에 속하는 SHA-256 을 사용하고 있다.

SHA-3 family : Keccak 이라는 알고리즘이 선정되어 SHA-3 이라는 이름을 갖게 되었다.

 

해시의 활용

우리가 인터넷에 아이디 비밀번호를 입력하면 서버에 저장되어 있는 비밀번호 값과 비교하여 일치하면 인증이 성공한다.

이때 서버는 비밀번호를 그냥 저장하지 않는다.

만약 공격자가 서버의 데이터베이스를 해킹하는데 성공했다면 모든 사용자의 비밀번호가 그대로 유출될 수 있기 때문이다.

 

그래서 보통은 해싱을 해서 저장하는데, 이렇게만 하는 것도 안전하지는 않다.

왜냐하면 많이 사용하는 해시 알고리즘은 정해져있고, 공격자들은 그 해시 알고리즘에 대해 어떤 값을 넣으면 어떤 결과가 나오는지를 딕셔너리로 저장해서 갖고다니기 때문이다.

 

그래서 이를 방지하기 위해 보통은 salt 라는 임의 값을 비밀번호에 붙여서 함께 해싱한다.

이 salt 값은 데이터베이스에도 그대로 저장되어 있기 때문에 공격자들은 salt 값을 알 수 있지만, 자신이 시도해보려는 비밀번호와 salt 값을 합해서 해싱을 해야 하기 때문에 자신이 갖고 있는 딕셔너리가 무용지물이 된다.

 

사용자 입장에서도 공격자들이 이렇게 딕셔너리를 들고 다니는 것을 인지하고, 평소에 복잡한 비밀번호를 사용하는 것을 권장한다.

 

해시는 공격자들이 암호를 알아내지 못하게 만들면서도, 알고리즘을 알고 있으니 사용자의 입력을 해시 함수에 넣어서 해시값만 비교하면 그 암호가 정확하게 뭔지는 몰라도 맞다 / 틀리다는 판별할 수 있으므로 유용하다.

 

 

Random Generators

크기가 작은 input을 받아서 크기가 큰 output을 내보내는 것을 말한다.

해시 알고리즘은 랜덤 넘버 제너레이터로 쓸 수도 있다. (입력값의 크기가 output보다 클 필요는 없기 때문이다.)

랜덤 넘버의 분량이 많지 않다면 해시 알고리즘으로도 충분하다.

 

Random Generator는 Stream ciphers 와 관련이 있다.

stream cipher는 두 사용자 공통으로 사용하는 키 패드가 얼마나 랜덤하고 예측할 수 없는지가 중요하다.

예를 들어 내가 암호화하려는 문장이 길다면, 그 만큼의 큰 키 패드가 필요하고, 이 키패드를 생성할 때 Random Number Generator를 활용해서 만들 수 있다.

 

Stream Cihpers에서 실제로 사용하는 랜덤 넘버 제너레이터 알고리즘은 C언어에서 사용하는 rand() 함수와 같은 경우보다 좋은 퀄리티의 랜덤 넘버를 만들 수 있다고 한다.

 

예를 들어 어떤 포커 게임 같은 것을 만들기 위해 랜덤을 활용하는 경우,

하드웨어 기반의 랜덤 넘버를 얻고자 하는 경우, 시간이 지나면 생성 가능한 모든 랜덤 넘버를 소진하는, 수량이 부족한 문제가 발생할 수 있어서 소프트웨어로 랜덤 넘버를 생성한다. 다만 소프트웨어의 경우, 특정 인풋을 넣으면 언제나 같은 값을 내보내기 때문에, 진짜 랜덤이 아니라 슈도 랜덤이라고 부른다. 이런 슈도 랜덤 넘버 제너레이터를 줄여서 PRNG 라고 부르기도 한다.

 

프로그래밍 언어에서 지원하는 랜덤의 경우에도 seed 라는 인풋을 기반으로 랜덤 넘버를 생성한다.

이때 진짜 랜덤처럼 동작하게 하려면 이 인풋값을 적절하게 잘 넣어주어야 한다.

하드웨어 (마우스 움직임, 하드디스크의 arm 움직임), unix 시간 등을 넣을 수 있다.

(보통 시간을 많이 넣는데, 이 방법은 공격자도 많이 사용하기 때문에 안전하지는 않다.)

 

이 seed 인풋값은 작은 값이며, 이 작은 값으로부터 충분히 많은 수의 랜덤 넘버를 만들기 위해 큰 수를 생성해야 하고,

stream cipher는 이 기능을 사용한다.

 

내가 암호화할 원본 메세지의 길이만큼 키 패드를 랜덤 넘버 제너레이터를 통해 생성한 뒤, 원본 메세지와 exclusive or 연산을 해서 상대방에게 보내면 된다.

 

과거에는 rc4 라는 알고리즘을 많이 사용했다.

취약점이 알려져 있어서 보안 시스템에 사용하는 것은 어렵지만, 충분히 좋은 랜덤 넘버를 생성한다.

 

 

Random Permutation

Block Ciphers 에 활용되는 분류의 ciphers

블록은 고정된 크기의 데이터 덩어리고, 이 고정된 크기의 블록을 같은 크기의 output으로 변환하는 함수를 사용한다.

 

예를 들어 2bit 크기의 블록이 있다면 이 블록이 가질 수 있는 데이터의 가짓수는

 

00

01

10

11

 

이렇게 4가지가 있다.

이제 이 각각의 블록을 같은 크기를 갖는 다른 블록으로 1:1 대응을 시킨다.

 

단순하게는 입력값을 그대로 내보낼 수도 있겠지만 (이것도 일종의 암호화다.)

이건 실제로 사용할 수 없으니, 어떻게 매핑할지 결정할 key 를 통해서 매핑 정보를 결정한다.

 

00     ->    01

01     ->    10

10     ->    00

11     ->    11

 

따라서 이 관계를 함수로 생각한다면 invertable 즉, 역함수가 존재하는 함수이다.

또한 매핑 정보는 하나의 '순열' 로 생각할 수 있다.

왼쪽에 들어오는 초기 정보에 순번을 (1, 2, 3, 4) 로 매기면, 오른쪽 cipher 결과를 만드는 순열은 (2, 3, 1, 4) 이다.

그래서 키를 가지고 이 순열을 결정하기 때문에 random permutation 기법이라고 부르는 것이다.

 

정리하면 Block Ciphers는 인풋 블록과 키를 조합해서 아웃풋 블록을 만들어서 암호화하는 기법이고,

모든 input block 은 서로 다른 하나의 output block 으로 매핑되어야 한다.

이 매핑 정보는 키에 의해 결정되고, 따라서 키를 모르면 어떤 블록이 어디로 매핑되는지 알 수 없다.

 

Block chipers 는 다음 특성을 갖는 것이 중요하다.

- confusion : key와 cipher text 사이의 관계를 모호하게 만드는 것

- diffusion : input block 과 output block 사이의 통계적인 관계를 알 수 없도록 만드는 것

 

 

* 관련 알고리즘

과거에 DES 라는 알고리즘이 존재했는데, AES 라는 알고리즘으로 대체되었다.

AES는 NSA 라는 미국 첩보 기관이 주최한 공모전에서 선정된 암호화 알고리즘이다.

보통 block cipher를 하는 경우 AES를 자주 사용한다.

AES의 키 사이즈는 128, 192, 256 bit 가 있는데, 보안이 중요하면 256 bit 아니라면 128 bit 를 사용하면 된다.

 

Public key encryption

공개키 암호화는 Block Cipher의 특별한 케이스로, 암호화는 누구나 할 수 있지만, 복호화는 키를 가진 사람만 할 수 있는 특징을 갖는다.

Public key 암호화는 서로 다른 2개의 키를 사용하기 때문에 비대칭키 암호화라고도 부른다.

각각의 키는 공개키 (public key) 와 비밀키 (private key) 라고 부르며, 각각의 키는 크게 2가지 용도로 활용할 수 있다.

 

1. 공개키로 암호화 - 비밀키로 복호화 (기밀성)

이 용도는 많이 사용하지 않는다. Block Cipher 와 같은 대칭키 알고리즘의 성능이 더 좋기 때문이다.

 

2. 비밀키로 서명 - 공개키로 검증 (인증)

블록체인에서 비트코인 트랜잭션이 그 소유자가 원해서 나온 것이 맞는지 검증하는데 자주 사용한다.

 

RSA

비대칭키 암호화에서 주로 사용하는 알고리즘.

매우 큰 두 소수를 곱한 어떤 수가 있을 때, 이 수를 어떤 두 소수로 곱했는지 알아내는 것이 매우 어렵다는 점을 이용한다.

하지만 점점 컴퓨팅 파워가 증가하면서 이 방법도 위협을 받기 시작했다. 2020년 기준으로는 250자리수의 RSA 가 깨졌다.

다행히 소수는 무한히 존재하지만, 점점 숫자가 커질 수록 소수를 찾기가 힘들다는 문제점이 있다.

 

구체적인 방법은 다음과 같다.

먼저 p, q 라는 매우 큰 서로 다른 소수를 고른다.

그리고 p, q를 곱한 N을 modulus (나누는 수) 로 활용한다.

 

다음으로 (p-1), (q-1) 에서 서로소인 e 를 고른다.

그리고 ed = 1 mod (p-1)(q-1) 이 나오도록 하는 d 를 고른다.

그러면 public key 는 (N, e) 가 되고, private key 는 d가 된다.

 

이제 어떤 메세지르 M을 암호화한다고 해보자.

이때 M을 숫자로 나타내면 M < N 이어야 한다. (N은 매우매우 큰 수이므로 보통은 성립한다.)

 

 

그러면 M 을 암호화 할 때는 M^e mod N 을 계산하고, M을 복호화할 때는 C^d mod N 을 계산한다.

 

만약 누군가 N = pq 를 만족하는 매우 큰 소수 p, q를 빠르게 찾을 수 있다면 N, e는 공개되어있으므로 이를 기반으로 d 를 쉽게 얻어낼 수 있게 된다.

 

타원 곡선 암호화 (Elliptic curve cryptography)

RSA 가 컴퓨팅 성능의 증가로 안전성이 위협을 받고 있어서 타원 곡선 암호화라는 새로운 기법이 등장했다.

비트코인에서는 이 기법을 사용한 비대칭키 암호화 방식을 사용한다.

타원 곡선은 원래 연속적인 수를 다루는 순수 수학인데, 암호학자가 여기에 이것 저것 조작을 하여 이산 수학(정수)으로도 다룰 수 있게 바꾸었다. 그래서 이 암호화 알고리즘은 정수론에 기반하고 있다.

 

타원 곡선 암호화의 또 다른 장점은 RSA에 비해 더 작은 크기의 키로도 RSA와 비슷한 보안성을 제공할 수 있으며,

서명과 검증 과정 역시 RSA보다 빠르게 수행할 수 있다.

키의 크기가 작으므로 인터넷을 통해 전송할 때 bandwidth도 작고, 더 적은 저장공간을 사용하는 것도 장점이다.

 

 

타원 곡선은 위와 같은 식의 형태를 갖는 곡선이다.

 

 

그래프로 그리면 위와 같은 모습이 나온다고 한다.

 

암호학에서 사용할 때는 다음과 같은 타원 곡선 식을 사용한다.

 

이때 p 는 소수이고, 나머지 값은 0부터 p-1 사이의 정수값이 나오는데, 이 point, 정수값을 사용한다.

그리고 이 점 외에도 무한대에 있는 점이 존재한다고 가정한다.

 

타원 곡선에서는 덧셈을 위 그림과 같이 정의한다.

 

P1 과 P2를 잇는 직선이 타원곡선과 만나는 점을 y축에 평행하게 내렸을 때 그때 만나는 점 P3

 

이게 P1 + P2 = P3 로 정의된다.

 

 

이제 이 타원 곡선에 임의의 x 값을 넣어보자.

실제로 p 는 매우 큰 값이지만 여기서는 5를 예시로 들었다.

 

x = 0 을 대입하면 y² = 3 이 된다. 어떤 수를 제곱해서 5로 나눈 나머지가 3이 되는 수는 존재하지 않으므로 y값은 존재하지 않는다.

x = 1 을 대입하면  y² = 6 이 되고, 이 수를 5로 나눈 나머지는 1 이다.

어떤 수를 제곱해서 5로 나눈 나머지가 1이 되는 수는 1, 4 가 있다.

이런 식으로 가능한 정수점을 찾고, 이에 더해 임의로 정의한 무한대 점을 포함시킨다.

 

만약 p 가 매우 큰 값이라면 이 타원 곡선 위에는 매우 많은 점들이 존재할 수 있다.

 

 

이제 이 위의 각각의 점에 대해 P1 + P2 를 계산하면 위와 같이 P3를 계산할 수 있다.

P1과 P2는 같을 수 있으며, 만약 계산한 m 이 무한대가 되면, P3 는 무한대 점이 된다.

 

Diffie-Hellman

discrete-logarithm 이라는 수학에 기반한 암호화 기법으로, (타원 곡선 암호화 알고리즘을 기반으로도 할 수 있다)

A 와 B 라는 두 사람 사이에 키를 안전하게 공유하는 알고리즘이다.

특히 대칭키 알고리즘에서 두 사람이 안전하게 같은 키를 공유하는데 활용된다.

 

1. 두 사람이 사전에 어떤 알고리즘을 사용할 지 공유한다. (공격자가 알아도 상관없다.)

2. 두 사람이 각자 정보를 교환한 뒤, 상대방이 보낸 값과 자신이 비밀스럽게 갖고 있던 값을 조합한 결과가 상대방이 똑같이 한 결과와 똑같이 나온다. 이 값을 두 사람의 공통 키로 사용할 수 있다.

 

 

알고리즘은 간단하다 p, g 라는 공개된 값을 두 사람이 알고 있을 때, 각각 x, y 라는 값을 알고 있으면 A, B 는 각자가 자신 x, y를 이용한 연산 결과를 상대방에게 공유하여 두 사람이 같은 값으로 알고 있는 공유 가능한 키 값을 알 수 있다.

 

디피-헬만 알고리즘으로 얻어낸 공유키 자체는 대칭키로 사용될 수 있지만, 이 대칭키를 얻는 과정은 비대칭키를 사용해서 얻어낸다.

p, g 는 public key 이고, A, B 가 각각 알고있는 x, y 를 private key 라고 보면 된다.

그리고 gˣʸ 로 부터 x, y 를 알아내는 것이 매우 어렵다고 수학자들이 말하므로 안전하게 사용할 수 있다.

 

이 방법은 encrypt 나 서명에 직접적으로 사용되는 방법은 아니다.

다만 두 사람이 같은 키를 안전하게 공유하는데 유용하게 사용된다.

 

 

 

위에서 정리한 타원곡선 암호화 알고리즘을 이용하여 디피 헬만 알고리즘을 적용할 수도 있다.

먼저 타원 곡선과 그 위의 한 점이 공개적으로 주어지고, A, B 의 private key 가 정수로 주어진다.

Alice 는 자신이 가진 수 4를 타원 곡선 점에 곱한 (즉, 위에서 정의한 덧셈을 4번한) 결과를 보내고

Bob은 자신이 가진 수 7을 타원 곡선 점에 곱한 값을 보낸다.

 

그러면 Alice, Bob 은 서로가 보낸 값에 자신이 가진 값을 곱한 (그 횟수만큼 더한) 값을 계산하면 둘이 같은 점을 계산하게 된다.

이 값에서 key 를 뽑아낼 때는 x만 쓰거나, y만 쓰거나, 두 값을 더해서 사용하거나 자유롭게 둘이 합의한 방식을 사용하면 된다.

그리고 수학자들은 이 최종 계산된 값을 기반으로 두 사람의 private 값을 알아내는 것이 거의 불가능하다고 한다.

 

 

Digital Signatures

키를 소유한 사람만 서명할 수 있고, 그 서명에 대해 누구나 검증할 수 있다.

타원 곡선 크립토 알고리즘을 이용해서 서명과 검증을 할 수 있다.

 

1. 먼저 크립토 해시 함수를 적용하여 z = h(m) 으로 메세지 m 을 해싱한다.

2. 랜덤 넘버 k 를 정하고, (x1, y1) = kG 가 되는 G를 계산한다. G는 elliptic curve 의 base point 이다.

비트코인에서는 같은 서명자가 이 값을 다르게 주어서 같은 메세지에 대해 서로 다른 서명을 여러개 만들어낼 수 있다.

 

 

3. r, s 를 위와 같이 계산한다. da 는 서명을 하는 사람이 갖고있는 private key 이다. n은 public 한 값이다.

4. 그러면 최종 서명 결과는 (r, s) 라는 튜플이다.

 

서명을 검증할 때는 원본 메세지, 서명, 퍼블릭키가 필요하다.

1. 먼저 크립토 해시 함수를 적용하여 z = h(m) 으로 원본 메세지 m 을 해싱한다.

2. 다음 값을 계산한다.

 

n은 public한 값이고, r, s 는 서명으로부터 알 수 있다.

 

3. u1, u2  값을 가지고 아래 값을 계산한다.

 

여기서 Qa는 서명을 한 사람의 Public key 이다. (비트코인 지갑은 da를 알고 있고, Qa는 da로부터 계산해서 알아낸다.)

이 (x, y) 는 서명 과정에서 계산했던 점과 동일한 점이다.

이 점의 x 좌표를 n으로 나눈 나머지가 r 과 같다면 서명은 유효하고 다르다면 유효하지 않다.

 

---

Public Key Infrastructure ( PKI )

RSA, ECC 와 같은 것을 이용하기 위해서 필요한 모든 인프라 (소프트웨어, 하드웨어, 기관, 사람 등) 을 통칭한다.

PKI 에서 중요한 개념은 2가지가 있다.

 

1. 인증서

우리나라에서는 과거에 '공인인증서' 라고 불렀었지만, 지금은 '공동인증서' 가 되었다.

어떤 사람이 자신이 홍길동인척하고, 자신의 public key 를 제시하면서 이걸로 암호화해서 자신에게 보내도록 유도하면, 그걸 믿은 상대방이 홍길동의 데이터를 그 사람의 public key 로 암호화해서 사기꾼에게 보낼 수 있다.

이를 방지하려면, 이 사람이 제시한 public key 가 홍길동의 키가 맞는지 확인해야 한다.

 

예를 들면, 은행 사이트와 똑같이 생긴 사이트가 자신이 은행 사이트가 맞으니 로그인 할 때 아이디, 비밀번호, 생체 정보 등을 달라고 요구한다면, 이 사이트가 정말 은행 사이트가 맞는지 검증하기 위해 브라우저가 이 사이트가 보내온 은행 인증서를 확인한다.

그리고 이 인증서가 맞다고 인정해주는 기관이 필요하기 때문에 그 기관을 CA 라고 말한다.

 

CA는 인증 기관으로서, 인증서를 발급하고 관리한다.

(우리나라에서는 대표적으로 yes sign 과 같은 기관이 있다.)

 

브라우저에는 보통 신뢰할 만한 CA의 공개키가 내장되어 있기 때문에, 이 사이트가 보내온 은행 인증서를 CA의 공개키로 검증할 수 있다.

(이 인증서는 CA가 발급했기 때문에 CA의 private key 로 서명이 되어있을 것이다.)

 

 

 

 

그래서 위 식을 보면, Ka는 A에게 발급된 public key 이고, 이 Key 가 A의 것이 맞다는 것을 T시간에서부터 L시간 동안 맞다는 것을 검증하는 내용이 들어있다. 이 내용을 CA가 서명하면 A 에 대한 인증서를 보증하게 된다.

 

 

인터넷 상에서는 이렇게 두가지 암호화 방법이 섞여서 사용되기도 한다.

비대칭키 방식은 크기가 큰 메세지를 암호화/복호화를 하는데 쓰기에는 대칭키 방식보다 효율이 낮다.

따라서 AES 와 같은 대칭키의 키가 있을 때, 이 키를 공유하기 위해서 Diffie-Hellman을 사용할 수도 있지만,

비대칭키 암호화를 사용하여 RSA와 같은 public key crypto 와 AES 같은 대칭키 방식을 섞어서 쓴다.

 

RSA로 먼저 키를 암호화하고, 상대방은 전달받은 키를 복호화해서 secret key 를 얻는다.

key는 크기가 크지 않으니 비대칭키로도 충분히 빠르게 암호화할 수 있다.

그리고 AES 방식으로 암호화한 암호문을 상대에게 전달하면 상대는 복호화해서 얻은 secret key 를 가지고 평문을 얻는다.

 

 

전자 서명의 예시도 다시 한번 정리하면

원문 메세지를 서명자의 비밀키로 서명해서 메세지와 서명을 같이 보낸다.

이때 보내는 통로는 공격자가 들여다볼 수 있어도 괜찮다.

이 서명을 검증하는 사람은 서명자의 공개키로 서명을 검증할 수 있고,

이 과정에서 메세지는 '내용이 바뀌지 않았다' 라는 것을 서명을 통해 검증한다.

 

만약 메세지의 내용을 숨겨야 한다면 메세지 자체도 암호화해서 보내야 할 것이다.