You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Public-key cryptography, or asymmetric cryptography, is any cryptographic system that uses pairs of keys: public keys that may be disseminated widely paired with private keys which are known only to the owner. There are two functions that can be achieved: using a public key to authenticate that a message originated with a holder of the paired private key; or encrypting a message with a public key to ensure that only the holder of the paired private key can decrypt it. 출처
공개 키 암호 방식
두 개의 비대칭적인 키(공개 키, 개인 키)를 기반으로 동작.
공개 키 : 누구에게나 알려진 키. 암호화와 서명 확인 수단으로 사용됨.
개인 키 : 본인만 알고 있는 키. 복호화와 서명 생성 수단으로 사용됨.
동기
두가지 이슈를 해결하기 위해 등장.
키 배포 : 신뢰받는 키 배포 센터(KDC) 없이 어떻게 키를 안전하게 배포할 것인가
디지털 서명 : 메세지를 받았을 때 실제로 전송자가 보낸 것인지, 중간에 변경이 되진 않았는지 어떻게 입증할 것인가
기본적인 동작 원리
메세지 전송 : 평문을 수신자의 공개 키(와 자신의 개인 키)를 이용해 암호화.
메세지 수신 : 암호문을 본인의 개인 키(와 송신자의 공개 키)를 이용해 복호화.
공개 키 암호의 경우 굉장히 큰 수의 사용을 필요로 하고, 때문에 대칭 키 암호화 방식들에 비해 상대적으로 느리다.
Diffie–Hellman key exchange (D–H) is a specific method of securely exchanging cryptographic keys over a public channel and was one of the first public-key protocols as originally conceptualized by Ralph Merkle and named after Whitfield Diffie and Martin Hellman. D–H is one of the earliest practical examples of public key exchange implemented within the field of cryptography. Traditionally, secure encrypted communication between two parties required that they first exchange keys by some secure physical channel, such as paper key lists transported by a trusted courier. The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure channel. This key can then be used to encrypt subsequent communications using a symmetric key cipher. 출처
공개 키를 이용한 비밀 키 배포
공개 키를 이용해 암호화 / 인증 등 다 가능함!
하지만 이런 알고리즘들은 상대적으로 느림
그러니 서로 동의한 비밀 키를 이용해 암호화를 하고 싶은데...
그럼 비밀 키는 어떻게 교환하는데?
디피-헬만 키 교환Diffie-Hellman Key Exchange
공개 키에 기반한 첫 번째 시도. 1976년, 휫필드 디피와 마틴 헬만에 의해 제안됨. 사실은 머클-디피-헬먼이라 불러야 한다? 공개적으로 비밀 키를 교환하기 위한 효과적인 방법. 키를 교환하는데에만 사용되는 알고리즘. 이산 로그를 계산하는 것이 매우 어려운 일이라는 것에 기반.
비밀 색깔 교환하기
다음과 같은 상황을 생각해보자. 앨리스와 밥은 서로 둘 만 아는 비밀 색깔을 갖고 싶다. 하지만 이들의 관계를 질투하던 트루디가 그들 사이에 오고가는 모든 색깔을 볼 수 있다면, 이 둘은 어떻게 비밀 색깔을 가질 수 있을까?
공개적으로 교환할 공개 색을 하나 정한다 (노란색).
앨리스와 밥이 각각 자기의 비밀 색(빨간색, 청록색)을 정한다. 이 색은 누구에게도 알려주지 않는다.
앨리스가 노란색과 빨간색을 섞은 주황색을 밥에게 보낸다.
밥이 노란색과 청록색을 섞은 하늘색을 앨리스에게 보낸다.
앨리스는 밥에게 받은 하늘색을 자신의 빨간색과 섞는다 => 똥색
밥은 앨리스에게 받은 주황색을 자신의 청록색과 섞는다 => 똥색
이 과정을 거치면 앨리스와 밥은 공통의 비밀 색깔(똥색)을 알게 되었지만, 질투의 화신 트루디는 노란색, 주황색, 하늘색에 대한 정보만 알고 있고 똥색에 대해선 알지 못하는 상황이 발생한다! (이 색들을 어떻게 섞어도 저 똥색이 나오지 않는다) 이러한 상황이 발생한 근본적인 원인은 두 가지 색의 물감을 섞기는 쉽지만 분해하기는 힘들기 때문이다.
이 비유를 실제로 디피-헬만 키 교환에서 일어나는 일과 매치시키기 위해서는 약간의 수학이 필요하다.
수학
소수, 서로소
소수 : 자연수 a가 1로만 나누어질 시 a는 소수 (e.g. 2, 3, ...)
서로소 : 두 숫자 a, b가 1 이외의 공약수를 가지지 않을 시 a와 b는 서로소 관계 (e.g. 8 & 15)
페르마의 소정리
p가 소수이고 a가 p의 배수가 아니면,
증명 생략!
오일러 피 함수
어떤 자연수 n에 대해 오일러 피 함수 **φ(n) = (n 이하의 자연수 중 n과 서로소인 수의 개수)**로 정의된다. 어떤 수의 오일러 피 함수를 찾기 위해 기본적으로는 소인수분해가 필요하지만, 다음과 같은 특수한 경우가 존재한다.
φ(p) = p - 1 if p is prime
φ(p*q) = (p-1) * (q-1) if p, q are both prime
오일러의 정리
a와 n이 서로소일 때,
페르마의 소정리의 일반화. 이 때, a^m = 1 (mod n) 을 만족하는 가장 작은 m이 φ(n)일 때, 이 a를 n의 _원시근(primitive root)_이라고 한다.
p가 소수일 때, 원시근 a의 거듭제곱들로 modulo p 군을 생성할 수 있다. 즉, {a, a^2, ... , a^φ(n)} ≡ {1, 2, ..., p-1} (mod n) 이 된다. 다음과 같이 귀류법을 이용해 증명할 수 있다.
증명)
a가 p의 원시근이고, 0 < x, y < φ(p) 인 x, y 에 대해 a^x ≡ a^y (mod p)이지만 x != y 이라 가정
일반성을 잃지 않고 x > y라 가정하면, a^(x-y) ≡ 1 (mod p)
이 때, 원시근의 정의와 가정에 의해 0 < x-y < φ(p) 를 만족하는 x, y는 존재할 수 없으므로 모순
따라서 a^x ≡ a^y (mod p)면 x = y\r\n- 그러므로 {a, a^2, ... , a^φ(p)} (mod p) 은 φ(p) 개의 서로 다른 수의 집합.
p가 소수이므로 φ(p) = p-1 이 성립, 따라서 {a, a^2, ... , a^φ(p)} ≡ {1, 2, ..., p-1} (mod p)
다시 말해, 소수 p의 원시근 a, 그리고 임의의 자연수 x에 대해 a^x가 modulo n 체제에서 1부터 p-1 사이 자연수 중 한 값을 가질 확률은 모든 가능한 선택지(1~p-1)에 대해 동일하다. 이 성질은 암호화에 유용하게 쓰일 것이니 기억해두자!
이산 로그
a^k ≡ x (mod n) 의 근 k를 모듈로 n의 _이산 로그(discrete logarithm)_라 한다.
이 때, a가 원시근일 시 근 k는 항상 존재하지만, 만약 a가 원시근이 아니라면 존재한다는 보장은 없다.
디피-헬만 키 교환 (이어서)
위의 물감 예시와 실제 디피-헬만 키 교환 알고리즘의 요소들을 매치시켜보면 다음과 같다.
공개 색 → 충분히 큰 소수 p와 원시근 a
각자의 비밀 색 → 0 < x, y < p 인 자연수 x, y
물감 섞기 → a^x (mod p) 계산하기
섞여있는 물감 분해 → a^x ≡ k (mod p) 식에서 a, p, k가 주어졌을 때 x 구하기(즉, 이산 로그 구하기)
공유하는 비밀 색 → (a^x)^y ≡ a^(x*y) (mod p)
물감 예시와 마찬가지로, a^x (mod p)를 계산하는 과정은 쉬운 반면 이산 로그를 구하는 과정은 매우 어렵다는게 핵심이다. 예시를 통해 단계별로 살펴보면 다음과 같다.
거듭제곱의 밑으로 p의 원시근 a를 사용하는 이유는, 앞서 언급했듯 밑 a가 원시근이여야만 a의 거듭제곱이 modulo p 체계에서 고르게 분포하기 때문이다. 이를 통해 공격자에게 도움이 될 통계적 특성 자체를 없애버릴 수 있다.
분석
충분히 큰 소수를 사용했을 때, 효율적인 시간 내에 이산 로그를 구하는 것은 사실상 불가능
커뮤니케이션을 할 때마다 디피-헬만 키를 만들어서 그걸로 사용할수도
맨 인더 미들 어택에 취약 (양 말단의 중간에서 두 개의 디피-헬만 키 교환에 관여하는 공격자가 생길 수 있음)
