암호

암호는 비밀을 유지하기 위하여 당사자끼리만 알 수 있도록 꾸민 약속 기호이다.
자칫 패스워드와 혼용되기도 하나 패스워드는 접근에 대한 제어를 하는 것이고 암호(cypher)는 정보의 내용을 숨기는 기법이라는 데에서 암호는 패스워드와 구별된다.

과거에는 암호화기법 자체가 암호의 수준을 좌우했다. 즉 남들이 알지 못하는 새로운 기법을 사용하는 것이 관건이었다. 그러나 암호를 거는 사람과 푸는 사람이 그 기법을 알고 있어야 하기 때문에, 기법 자체를 보호하는 것이 또한 문제가 되며, 암호 기법이 공개되면 해당 기법을 사용한 암호는 쉽게 풀리곤 했다.

현대의 암호는, 암호화기법보다는 그 암호를 풀기 위한 키(key)로써 그 암호의 보안성을 조절한다. 즉 기법 자체는 학술논문(만천하에 공개되는)에 있는 기법을 사용하나, 키를 알아내기가 매우 힘들기 때문에 '알지만 풀 수 없는' 암호를 사용하는 것이다. 그렇다면 키의 보안은 또 어찌할 것이냐..라는 것이 문제가 된다. 정수론과 컴퓨터의 발달, 그리고 비대칭키 알고리즘이 해답이 된다. 즉 '알아내기 어려운 키를 결정하는 것'은 정수론의 이론과 컴퓨터의 계산능력에 의해 해결하고, '결정한 키를 남들이 알아내지 못하게 하는 것'은 비대칭키 알고리즘을 사용하여 극복한다. 즉, 암호를 거는 쪽과 푸는 쪽이 서로 다른 키를 사용할 수 있게 하는 것이다.

수학적인 관점에서 암호란 trap-door one-way function이다. 모든 암호는 수식으로 나타낼 수 있으며, 비효율적인 방법일지언정 코드화 할 수 있다. 이론적으로 One time pad를 제외한 모든 암호는 깰 수 있다. 깨지 못하는 암호란 수학적으로 Plain text와 동일한 양의 암호를 사용하였을 때(one time pad)나 가능하며, 이건은 암호를 서로 주고받는 과정과 Plain text를 주고 받는 과정에 동일한 노력과 보안이 필요하기 때문에 군사목적을 제외하곤 일반적으로 쓰이지 않는다. 모든 암호는 깰 수 있는데 왜 암호를 사용하며, 업체와 학자들은 안정하다고 주장하는 것일까? 그 이유는 암호의 존재의미는 그 암호로 암호화된 정보의 존재의미와 운명을 같이 하기 때문이다. 즉, 누군가의 계좌 비밀번호를 알아낼 수는 있지만, 천년뒤에나 알 수 있다면, 암호를 깨는 과정은 그 의미가 없는 것이다.

우리가 상식적으로 생각할 수 있는 정해진 암호로 암호화하고 똑같은 암호로 해독하는 방법이며 현존하는 모든 대팅 암호체계는 Large Finite Field의 수학적인 성격을 이용한 것이다. 대략적인 과정을 설명하자면, 다음과 같다.
{{|Plain text : P
Encoded text : Pe
Key : K
Encoding function : c(x)
Decoding function : d(x)
이다|}}

우리가 항상 인터넷을 하면서 암호를 입력할 때, 돌아가는 암호화 과정이다. 여기서 잠시 의문이 생길지도 모른다. 'P를 암호화 하는 건 알겠는데, 난 K밖에 입력을 안했는데 도대체 P는 뭘 쓰는거지?' 정답은 ' ' 즉 빈칸(blank)이다. 빈칸을 우리가 입력한 암호로 암호화하고 복호화 하는 것이다. DES는 62bit 블럭 단위로 56bit의 키를 이용하여 암호화를 한다. DES는 key의 크기를 키울 수 없다는 단점으로 인해, 암호화 과정을 3번 반복하는 triple DES를 사용하여 빠르게 발전하는 컴퓨터의 연산속도에 대응한다.

SecurityTechNet의 설명
DES의 표준문서
하단부에 Triple DES 알고리즘

DES가 처음 발표 되었을 때, 타국에서 가장 우려 했던점은 DES가 단순히 공개된 알고리즘으로 암호화되는 것이 아니라, 8개의 정체를 알 수 없는 permutation function(일종의 행렬)을 거친다는 점이다. 이 행렬이 어떤 규칙에 의해서 생성됐는지 미 국방부는 발표하지 않았으며, 사람들인 미국이 이 안에 자신들만의 trap door를 심어두었다고 의심하였다. 하지만, 사람들의 연구에도 불구하고 그런 부분은 밝혀지지 않았으며, 사람들은 DES의 간편함과 대중성, 보안성을 이유로 널리 사용하게 되었다.

Advanced Encryption Standard의 약자이며, NIST가 3년여에 걸쳐 공개적으로 알고리즘을 선정하였다. 후보 알고리즘 중 하나는 우리나라에서 제출했던 것으로 알려져 있다. 여러가지를 고려한 결과 유력한 후보였던 Twofish를 제치고 Rijndael이 선정되었다. AES는 DES를 이을 표준으로 승인되었다.

개발자의 이름을 따서 Verman cipher방식이라고 불리우며, 수학적으로 해독이 절대 불가능하다. 잠시 생각하면 당연한 것으로, 어떤 글자 하나가 어떤 암호 한글자로 암호화 되었다. 그리고 다음 글자는 또 다른 암호로 암호화 되었다. 암호는 다시 사용되지 않으며, 암호화된 결과는 같은 글자라도 다른 경과가 나오며 다른 글자라도 같은 글자로 암호화됐을 가능성이 있다. 대신 이 방식은 서로 메세지를 주고 받기 전에 암호표를 미리 가지고 있어야 한다. 가장 쉽게 접하는 예로, 잠수함 영화를 보면 통신이 왔을때, 이상한 플라스틱을 쪼개서 그 안에 있는 종이를 '알파 브라보 찰리....' 이렇게 읽는 장면이 있다. 이것이 미리 나누어 가진 암호표이며, 이 일회용 암호를 이용해서 아군과 안전하게 통신할 수 있는 것이다.

필요는 발명의 어머니라고 했다. 비대칭 암호체계는 왜 필요하게 되었을까? 대칭암호체계의 근본적인 단점은 무엇일까? 만난적 없는 사람과는 통신할 수 없다는 점이다. 서로 암호를 통일하기 전에는 통신을 할 수 없기 때문이다. 자, 그럼 비대칭 암호는 그것이 가능할까? 물론 가능하다. (가능해야 할거 같지 않은가;;) 비대칭 암호는 공개키와 개인키로 통신이 이루어진다, 공개키는 암호화에 사용되며, 누구나 상대방의 공개키만 알 수 있으면 메세지를 보낼 수 있다. 물론 개인키는 메세지를 받아서 복호화할 때 사용한다. 텀즈에 보면 디지털 서명도 함께 공개키와 개인키의 의미를 알 수 있다.

RSA는 현재 일반적으로 가장 많이 쓰이는 암호화알고리즘으로, 그 알고리즘은 극히 단순하다. 하지만, 이것은 수학적으로 shortcut이 없는 것으로 알려진 DLP(Dicrete Log Problem)으로서 전형적인 one way function이다. 그 과정은 다음과 같다.
{{|
1. 키 생성 : 큰 소수(prime) 두 개 p와 q를 선정하고 곱해서 n 을 만든다. (p-1)(q-1)과 서로 소인 정수 e를 고르고, d = (e^(-1))mod ((p-1)(q-1))의 관계를 가지는 d를 찾는다. 앞에서 즉 e*d mod (p-1)(q-1) = 1이다.
2. 암호화 : C = (M^e) mod n
3. 복호화 : M = (C^d) mod n
|}}
간단하게 증명할 수도 있다. 오일러함수란 것을 알아야한다. 오일러함수 E(N) 은 N 보다 작고 N과 서로소인 자연수의 개수를 나타내며, E(AB) = E(A)E(B)인 성질을 가지고 있다. 또한, P가 소수(prime)일 경우 E(P) = P-1이다. 왜냐하면 소수보다 작은 모든 수는 소수와 서로소이기 때문이다. 이 때 오일러정리란 a와 N이 서로소일 때, a^(E(N)) mod N = 1 이다. 이때,
{{| C^d mod n = (M^e)^d = M^ed = M^((p-1)(q-1)+1) = (M^(p-1)(q-1))*M mod n = 오일러정리에 의해 M|}}

즉, RSA를 깨는 방법은 d를 찾는 과정이며 n으로부터 p와 q를 알아내야한다. 이것은 즉, IFP(Integer Factorization problem)으로 환원된다. 이것은 아직까지 풀지 못한다는 증명도 없지만, 효율적인 알고리즘 또한 개발되지 않았다. 관련 논문

RSA 체험(?)하기
아무리 설명을 해도 딴세상 얘기 같을 것이다. 공개키란 것을 눈으로 보도록 하자. 다음과정을 따라한다.
{{|NewWindow("http://www.wooribank.com","우리은행") -> 개인고객 -> 인터넷뱅킹 시작하기|}}라고 하면 잠시만 기다려주십시오라고 나오고 오른쪽 아래 System tray에 자물쇠 모양의 아이콘이 생긴다.
{{|자물쇠 아이콘에서 마우스 오른쪽 버튼 -> 세션정보 보기 -> 익명 사용자 연결 선택 -> 상세보기 -> 접속서버인증서 옆의 ... 클릭 -> 자세히|}}이제 여러가지 정보가 나온다. 공개키알고리즘을 보면 rsaEncryption이라고 나온다. 우리나라(외국은 모르겠지만 외국도 아마) 금융거래의 대부분은 RSA방식을 사용한다. 공개키를 보자. 무지막지하게 길다. 16진수로 나타낸 것이다. 현재 금융거래에선 1024bit의 키를 사용한다. 10bit를 십진수로 대출 3자리수라고 한다면, 약 300자리의 10진수가 된다. 평생계산해도 못한다 -_-; 게다가 코딩을 해본 사람이라면 생각해보길 바란다. 과연 1024bit짜리를 어떻게 연산할 것인가. 걍 언어에서 지원해줘도 오래걸리는 판에 이런 연산을 하기 위해선 새로운 연산 라이브러리를 만들어야 한다.

ECDLP(Elliptic Curve Discrete Logarithm Problem)을 기반으로 하는 암호화방식
기존의 RSA에 비해서 엄청나게 어려운 방식이지만 100bit이하의 암호로 1000bit급의 RSA와 같은 보안성을 가지고 있기 때문에 Data전송량이 중요한 무선 통신에서 주목하고 있다.

오늘은 Julius Caesar가 만든 암호법에 대헤서 말씀 드리겠습니다.
일단 가로 26칸 세로 2칸의 표를 만드시고 이렇게 입력합니다.
평문 ABCDEFGHIJKLMNOPQRSTUVWXYZ
암호 EFGHIJKLMNOPQRSTUVWXYZABCD
여기선 평문과 암호 철자의 자리가 4만큼 차이가 납니다.
이렇게하면 암호문을 작성할 준비가 다 되었습니다

여기선 예문으로 NOATTACK를 들게습니다.
우선 평문철자N을 그와 대응하는 R로 바꿈니다.
그리고 O를 S로
바꾸시면 RSEXXEGO 가됩니다.
이걸 수신자에게 보내면서 암호알파벳과 평문알파벳이 4만큼 차이난다는 것을 알리기 위해 4를 덧붙여서 보내면 끝입니다.
복호는 암호문을 만들때와 반대로 하면돼요

암호깨기
영어의 경우, ETAOIN SHRDLU 순서로 빈도수가 높다. 이 점을 암시하며 호프스태더는 GoedelEscherBach에, SHRDLU라는 인공지능 프로그램에게 질문하는 Eta Oin 박사를 등장시킨다. Weird Words: Etaoin shrdlu
한글을 분석한 것이 있으면 재미있을텐데... 없나요? -- 최종욱
한글의 초성,중성,종성 출현 빈도

초성의 자음 빈도 순위.
ㅇ 37184, 25%
ㄱ 18554, 12.7%
ㄷ 13269, 9%
ㅅ 12096, 8.3%
ㄹ 11271, 7.7%
ㄴ 10883
ㅈ 10370
ㅎ 9886
ㅁ 7848
ㅂ 5088
ㅊ 2383
ㄸ 1493
ㅌ 1384
ㅍ 1300
ㄲ 1186
ㅆ 743
ㅋ 521
ㅉ 360
ㅃ 310

합계 146100, 100%

종성의 받침 빈도 순위.
ㄴ 20924, 32.4%
ㄹ 14495, 22.4%
ㅇ 7995, 12.4%
ㄱ 5880, 9.1%
ㅁ 4236, 6.6%
ㅆ 3370
ㅅ 2405
ㅂ 1575
ㄶ 539
ㅎ 535
ㅌ 528
ㅄ 482
ㄷ 441
ㅍ 349
ㅈ 305
ㄺ 270
ㅊ 210
ㄲ 169
ㄻ 121
ㅀ 92
ㄵ 82
ㄼ 64
ㅋ 22
ㄽ 12
ㄿ 12
ㄾ 12
ㄳ 10

합계 64600, 100%

중성의 모음 빈도 순위
ㅏ 34363, 23.5%
ㅣ 22284, 15.3%
ㅡ 20740, 14.2%
ㅓ 15540, 10.6%
ㅗ 14067, 9.6%
ㅜ 9480
ㅕ 6197
ㅔ 6134
ㅐ 5927
ㅢ 2797
ㅘ 2400
ㅛ 1310
ㅚ 1286
ㅑ 1039
ㅟ 810
ㅝ 565
ㅖ 527
ㅠ 475
ㅙ 131
ㅞ 30
ㅒ 26

합계 146100, 100%

-- 두슬

이런 암호풀이를 이용한 추리소설은 에드가 앨런 포의 '황금충', 그리고 그걸 베낀 코난도일의 '춤추는 인형의 비밀'이 있다.

컴퓨터의 이론적 창시자인 영국의 수학자 앨런튜링은 이차대전당시 독일군 암호제작기인 에니그마를 해독하여, 연합군의 승리에 크게 공헌하였습니다. 처칠은 독일의 암호를 풀 수 있다는 사실을 감추기 위하여 런던대공습을 이미 알고 있었으면서도 폭격당했다고 전해지더군요.
인터넷을 찾아본 결과, 도스에 돌아가는 Enigma Program을 발견했습니다. 전에는 Windows에도 돌아가는게 있었는데, 어쩌구 저쩌구 하니 사라져 버렸군요. 윈도우즈꺼는 바퀴 4개도 가능했는데; 그래도 3개짜리라도 변환과정을 보여줘서 도움이 되니 다행. -갈라드리엔

레오나르도 다빈치는 자신의 아이디어를 보호하기 위하여 자신의 노트의 글자들을 모두 거울상으로 반전시켜 썼답니다. 거울로 비쳐봐야 제대로 읽을 수 있죠. 이것도 암호라면 암호.

현대암호학은 '큰수의 소인수분해는 어렵다'라는 사실에 기반하고 있으나, 최근 양자컴퓨터와 shor의 알고리즘에 의해서 위협받고 있다. 그래서 개발되고 있는 것이 양자암호. 양자암호는 '불확정성 원리'에 근거한 것으로, 근본적으로 도청이 불가능하다.
양자컴퓨터
양자암호

소설?

정수론과 암호
역사속의 암호와 암호장치들 --DeadLink(20050909)

See: 암호학책
암호의 역사 : 사이몬 싱(인가?) : 갈라드리엔군이 암호에 대해 접하기 시작한 책.

SeeAlso 정수론 PKI

커뮤니케이션학분류 수학분류