cryptography unit1-1

cryptography 라는 단어의 뜻은 아래와 같다.

symmetric crytosystems

symmetric cryptosystems  에서 symmetric의 사용은 encryption이랑 decryption에서 사용하는 key가 같을때를 의미한다. m은 메시지의 전체 집합 M에서의 부분집합 혹은 원소. 엘리스가 메시지 m을 암호화해서 insecure channel로 흘려 보낼거고 Bob이 이 암호화된 ciphertext를 받아서 decryption 시켜서 plain text로 만들것. E와 D는 역함수 관계. 이 cryptosystem에서 가장 중요한 key이다. encryption algorithm이나 decryption algorithm이 노출 된다고 하더라고 key를 비밀로 한다면 이는 유지가 된다(cipher must not depend on secrecy mechanism it must not matter if it fall into the hands of enemy).

Encryption function은 message m과 key k를 받아서 cipher를 만들고 Decryption function은 cipher c와 key k를 받아서 message m을 다시 만든다. correctness property란 모든 m과 k에 대해 E와 D가 역함수 관계인것.

perfect cipher인 one-time pad 에 대해 알아본다.

여기서 perfect 라는 뜻은 key랑 message를 전혀 노출하지 않는다는 것. 그러나 이 cipher의 문제점은 impractical 하다는 것. 이를 이해하기 위해 XOR("exclusive or" 혹은 위 그림의 오른쪽 끝 기호로 표시) 를 이해하여야 한다. A XOR B 이면 A와 B가 같은 값이면 A XOR B 값은 0이 되고 A 와 B가 서로 다르면 A XOR B는 1이 된다.

XOR은 결합법칙이 성립한다.  곧 X xor Y xor X = X xor X xor Y와 같게 되고 이는 0 xor Y가 되므로 y 값과 동일하게 된다. 여기서 X를 key K로 생각하면 이것이 바로 one-time pad. key가 딱 한번만 사용되기 때문에 one-time pad 라 한다.

예를 들어보면

CS라는 문자열을 message 화 한다. 여기서 message 는 0 혹은 1 인 bits 가 되고 key 역시 마찬가지. C와 S를 python의 ord 함수를 이용해서 10진수화 하고 이를 2진수로 바꾸면 위와같은 숫자의 나열로 되고 key인 k는 random하게 0과1을 생성한다. 그래서 xor 을 이용해서 cipher인 c를 생성.

perfect cipher의 정의를 알아본다.

perfect cipher의 정의는 attacker, 그러니까 insecure line에서 cipher를 훔친 사람에게 그 어떠한 추가적인 정보도 제공하지 않는 cipher를 의미한다. 이를 수식화 하면 아래와 같다. 그림과 같다.

one-time pad가 perfect cipher 라는 것을 증명하는 과정이다. 

perfect cipher를 수식화 하면 위의 조건부 확률과 같게 된다. c를 알고 있다는 조건부 확률이 원래의 확률 P(m=m*) 와 같은 것이 바로 perfect cipher의 조건. one time pad가 위 식을 만족함을 보임으로 perfect cipher가 됨을 증명하는 것이다. 위 퀴즈에서 보듯이 one time pad인 encrypt mechanism을 가지고 message m과 ciphertext c 가 주어졌을 때 m이 c가 되게 하는 key k는 하나밖에 없게 된다. 길이가 1bit인 예와 2bit인 예에서 보듯이 한 m에서 한 k로의 edge, 즉 key는 하나밖에 없음을 보인다. 이 사실을 근거로 조건부 확률의 분모 P(B)를 구하게 되는데 one time pad에서는 P(B) 는 P(Ek(m)=c) 이다. P(Ek(m)=c)는 설명하자면 ciphertext 인 c가 나올 확률을 의미한다. 즉 모든 k와 모든 m가 encrypt mechanism에 의해 c가 될 확률들의 합을 전체 경우의 수 |M|*|K| 로 나누어 준 값이 되겠다. 여기서 모든 k에 대한 시그마, 곧 합은 1 이 되고 시그마m, 모든 m에 대한 합은 |M|이 되서 결국 P(Ek(m)=c) = 1/|K| 이다(이해가 잘 되지 않는다면 1bit 예제를 생각해보자. c가 1이 나올 확률은 모든 m, 곧 0과 1이 모든 key, 즉 0과 1에 의해서 1이 되는 확률은 1/2, 즉 1/|K|가 됨을 볼수 있다). 

위 conditional probability의 분자를 구해보자.

모든 message가 uniformly distribute 되어 있다고 가정하면 두번째 역시 정답이다. 하지만 일반적으로 message는 uniform distribution이 아니다(message가 영어라고 가정하면 특정 알파벳의 조합,즉 단어가 좀더 많은 분포를 차지하는 것을 알 수 있다). 오른쪽 그림과 같이 matrix를 만드는데 y 축은 M이 되겠고 x 축은 K가 되겠다. m=m* 교집합 Ek(m)=c 은 그림에서 빨간색 선과 카키색 선의 교차점이 되겠다(Eki(mi)=c 가 사실 꼭 y=-x 그래프가 되는 것은 아니지만 그렇게 되게끔 matrix를 구성했다고 가정한다). 곧 m*가 특정 m일 확률에 k*가 특정 k가 될 확률의 곱으로 표현된다. m*가 특정 m일 확률은 message가 uniform distribution이 아닌 관계로 P(m=m*)가 되겠고 key의 분포는 uniform distribution이기에 1/|K|이 되므로 이 두 확률의 곱으로 m=m* 교집합 Ek(m)=c 의 확률이 표현된다.

결론적으로 one-time pad 일때 perfect cipher의 조건부 확률 수식의  분자는 P(m=m*)*1/|K| 가 되겠고 분모는 1/|K| 가 됨으로 결국 P(m=m*) 가 되므로 perfect cipher의 조건부 확률을 만족하게 됨으로 one-time pad 는 perfect cipher가 된다.

그러나 one-time pad에는 심각한 문제가 있다.

한가지가 malleable. active attacker(ciphertext를 modify 하는 사람)가 비록 ciphertext로 부터 어떠한 정보를 얻지는 못하지만 ciphertext를 변형시켜서 Bob이 잘못된 message를 받도록 한다는 것이다. 그리고 또 다른 한가지는 impractical. key의 갯수가 message 만큼 있어야 한다는 것. 

sharmon's theorem : cipher가 완벽하다면 이는 반드시 impractical 하다.

이를 증명하기 위해서 귀류법을 사용. 즉 결론을 부정하여 모순이 되는지를 확인한다. 여기서 결론은 impractical, 즉 |K|가 |M| 보다 크거나 같다라는 결론은 부정한 가정을 이용. |K| < |M|인 perfect encryption 인 E가 있다고 가정한다. cypertext c를 얻게 되면 이를 decryption function을 이용해서 그 모든 key에 대한 합집합인 message Mo를 찾는다. 그런데 합집합인 관계로 decryption해서 나온 |Mo|이 |K| 보다 작거나 같게 된다(물론 one-time pad 일 경우에는 같게 되겠지만). 그리고 이미 가정에서 |K| < |M|이 였기 때문에 |Mo| < |M|이 되고 그 말은 특정 M에 속하는 특정 message는 Mo에 속하지 안을 수 있다는 것. 이때 특정 message의 P(m=m*|Ek(m)=c) = 0이 될것이고 P(m=m*) > 0 이 될 것이므로 이는 perfect cipher의 요건을 만족시키지 않으므로 가정했던 명제는 false가 되고 원래의 명제가 증명이 되는 것.