사실 오늘 공부한 건 아니지만 오늘 정리해 봐야겠다.
이놈의 게으름 ㅡㅡ
고전암호는 이전 포스트에도 올렸듯이, substitution과 transposition이 있다. 처음에는 substitution을 얘기해 보려고 한다.
그래도 사진 다시 한 번 올리자.
여기선 Substitution을 다룰 것이다!
Substitution은 말 그대로 p의 문자를 치환하는 방법이다.
여기에는 여러가지 방법이 있다.
isomorphism, monomorphism 등.
하나하나 소개해 볼까? ㅋㅋ
사실 내 공부지만;
1. 시저암호
첫번째는 시저암호다. 시저는 카이사르의 영어 이름이다. (그 유명한 로마의 율리우스 카이사르)
암호화는 간단하다. 알파벳을 순환고리라고 생각하고 n번 만큼 알파벳을 옮기면 된다.
n=3
p = ABCZYX
이라고 하면,
c = E_3(p)= DEFCBA
가 된다.
복호는 -n만큼 알파벳을 옮기면 되므로,
d=DEFCBA라고 하면,
p = D_n(c) = ABCZYX
를 얻을 수 있다.
p = ABCZYX
n = 3 (Kaesar cipher)
c = E_3(p) = DEFCBA
물론 여기서 E_n^-1 = D_n = E_(-n) 이다.
물론 행렬로도 볼 수 있다.
p의 알파벳들를 column vector라고 하면 E_n의 standard matrix는 26*26 matrix가 되는데, i 번째 row의 i+n(mod 26)번째 성분만 1이고 나머진 0인 매트릭스가 된다.
레이텍으로 작업하면 n=3 일 때의 E_3를 금방 보여줄 수 있겠지만...
생략한다.
어쨌거나, 위 행렬은 elementary row operator고, invertable하다. E_n^-1 = E_(-n)과 직관적으로 잘 연결된다.
단점은, E_n 의 개수가 25개 밖에 안된다는 것이다. n=0, 26 인 경우는 E가 identity가 되고 c=p가 된다.
즉, D_n의 개수도 25개 밖에 되지 않기 때문에 decrypt가 너무 쉽다.
시저암호는 isomorphism한 암호화의 예이다. 알파벳을 알파벳으로 변경하기 때문이다.
2. 다른 isomorphism한 암호화
위의 시저암호는 decrypt가 너무 쉽기 때문에 좀 더 복잡한 암호화가 필요하다.
그러면 위의 경우처럼 행렬로 보자.
p의 알파벳들 벡터 p' 의 rows를 바꿔주는 elementary operator를 생각해 보자. 모두 substitution의 암호가 될 수 있다.
invertable하므로 D_k(c)의 계산도 어렵지 않다.
하지만! D_k 를 구하기가 쉽지 않다. 위의 시저 암호를 포함해서, identity를 제외하면 경우의 수는 26!-1 이 나온다.
물론 이런 암호들도 암호문만 있다면 알파벳 빈도수를 계산하면 어렵지 않게 decrypt할 수 있지만,
그래도 시저암호보다는 훨씬 안전하다.
3. monomorphism한 암호화
알파벳을 알파벳으로만 치환하라는 법은 없다.
00부터 99까지 100개의 숫자 중에서 임의로 26개를 고른다.
각각을 알파벳에 대응시키면, 그것 또한 substitution!
isomorpic한 이전의 암호들과 비교해보면, 마침표나 특수기호, 심지어 띄어쓰기까지 치환이 가능하다는 것이다.
그러면 거의 해독이 매우 힘들어진다.
I am a boy. 와 같은 짧은 문장도(사실 문장이 짧으면 해독하기가 더 어렵다) isomorpism으로 변환시키면
K zu z tlh. 등으로 변환되지만, monomorphism으로 변환시키면,
31415926415953589793 으로 변환되어 decrypt를 안드로메다로 보낼 수 있다.
p = I am a boy.
E_i is the encryption key that isomorphism.
E_m is the encryption key that monomorphism.
c_i = E_i(p) = K zu z tlh.
c_m = E_m(p) = 3141592641594153589793
공백과 마침표를 사라지게 함으로 a-z 의 대응이나 단어, 문장의 길이와 같은 정보들를 좀 더 안전하게 만들 수 있다.
4. substitution의 boss
암호는 길이의 영향을 크게 받는다. Eve가 충분히 많은 암호문(ciphertext)을 수집하면 암호를 해독할 확률이 높아진다.
따라서 위 암호들은 충분히 긴 ciphertext에 대해 영문장에 자주 등장하는 'e'와 'the'등으로 눈대중 decrypt가 가능하다.
출현 빈도를 통해 해독이 가능하다는 것이다.
이런 단점을 보완할 수 있다.
planetext의 한 원소를 다양하게 대응시키는 것이다.
즉, i am a boy에서 두 번이나 등장하는 a를 각각 59대신에 하나는 59, 하나는 23에 대응시키는 것이다.
물론 공백도 41과 더불어 84, 62로 치환할 수 있다!
그러면 해독이 더욱 어려워진다.
3141592684236253589793
이 쯤 되면 해독이 거의 불가능하다. (ciphertext의 길이가 충분히 짧고, 왠지 익숙한 숫자배열이다.)
물론 힌트 역시도 익숙한 숫자 배열인데, 원주율을 아는 사람이라면 숫자 두 자리가 문자 하나에 대응된다는 것을 눈치 챌 수 있다.
암호문이 충분히 길어지면 해독될 암호이다.
역시 substitution은 키보드에 있는 모양으로 할 필요 없다. 직접 모양이나 문양 등을 만들어도 되고 한자로 대응시켜도 된다.
한글도 있다.
이제 자야지.
추신. 깔끔하게 정리하지 않은 건,
찾아보는 사람이 아닌 나를 위해 공부했기 때문.
