1. 암호의 뜻
암호란 비밀을 유지하기 위하여 당사자끼리만 알 수 있도록 꾸민 부호나 신호 를 뜻하는 말.
2.암호의 종류
1.대치식 암호 : 하나의 기호를 다른 기호로 대체하는 암호.
2.더하기 암호 : 알파벳의 순서에서 더하기를 하는 형식으로 해서 a를 d 로나타내는 암호.
3.힐 암호 : 알파벳과 정수 집합 사이의 지정된 대응 규칙을 지정된 키 행렬 k 를 이용하여 나타내는 방법
3. 암호의 역사
1.인류 역사가 시작되기 전부터 사용됨
2. 국가가 형성되면서 국가와 국가 간의 이권, 그리고 상업이 발달함에 따라 개인과 개인 간의 이권에 따른 비밀 보전의 필요성이 증대되면서 암호 방식의 사용이 증가.
3. 정보화 사회의 상거래의 핵심 요소인 전자화폐, 전자송금, 전자 지갑 실현 및 전자 상거래의 신뢰성과 비밀성을 제공해주는 방법으로 암호 방식이 이용
(1) 에니그마
에니그마(Enigma)는 독일어로 '수수께끼'라는 뜻을 가진 암호 기계의 한 종류로, 암호의 작성과 해독이 가능하며 육군용, 해군용 등 여러 모델이 있다.
기계는 1918년 독일인인 아르투르 슈르비우에 의해 처음 고안되어 사용되었는데, 특히 2차 세계대전 중 나치 독일이 군 기밀을 암호화하는 데 주로 사용됨.
(2) 암호 해독기(bomb)
암호 해독기(bomb) 은 앨런 튜링(1921~1954)이 만든 암호 해독기
2차 세계대전 당시 독일이 유럽을 침공할때 모든 명령을 에니그마를 통해 암호화 하였는데 앨런 튜링이 암호 해독기를 만들어 에니그마를 해독함.
(3) 시프트 암호
시프트 암호는 로마 제국의 카르가 만든 글자 바꾸기 암호( 카이사르 암호문)
평문의 문자와 암호문의 문자가 1:1로 대응하는 방식을 사용한 것으로 알파벳을 일정하게 띄어 쓰는 방법
(4) 악보 암호
악보 암호는 세계 1차대전 때 비밀 통신에 사용된 것으로 일정한 형태의 음표에 알파벳을 하나씩 대응시킨 형태로 평범한 악보처럼 보이지만 실제로 연주하면 음악이 되진 않음
이 암호학 강좌의 핵심인 ‘안전한 통신’(Secure communication)에는 두가지 필수요소가 있습니다. 첫째는 키 생성(key establishment)이고, 둘째는 생성한 키 교환을 통해 실제로 안전한 통신을 어떻게 수행할 것인가에 대한 것입니다. 지난 시간에 이미 언급했듯이, Alice와 Bob이 프로토콜의 양 끝단에서 서로에게 메세지를 보내려고 하는 상황을 상상해봅시다. 두 사람의 합의하에 K라는 key값을 생성하고, 그것을 둘이서 공유합니다. 그리고 그 K를 사용해서 Alice는 Bob에게, Bob은 Alice에게 메세지를 보냅니다. 하지만 해커는 안타깝게도 K값을 알지 못하기 때문에 중간에서 내용을 도청하거나 위변조 할 수 없습니다. 그러므로, 이것은 암호화를 통해 기밀성(Confidentiality)와 Integrity(무결성)을 보장한 예시라고 할 수 있습니다. 하지만 실제로 암호화를 사용한다면 단순히 이 2가지 장점외에도 아주아주 많은 다양한 이점을 제공합니다. 그것들을 활용한 다양한 예시를 살펴보도록 하겠습니다.
먼저 알려드릴 것은 디지털 서명(Digital Signature)입니다. 이것은 실제로 여러분이 종이 위에 펜으로 서명을 하는 것을 그대로 디지털화 했다고 볼 수 있습니다. 동일한 사람이 서명을 했다면, 그 싸인(한국식표현 의역)은 거의 일치한다고 볼 수 있겠죠? 디지털 세계에서는 어떨까요? 쉽지 않습니다. 만약 제가 서명한 디지털 문서가 해커에 의해 유출되었다면 어떻게될까요? 디지털 문서의 특성상 아주 손쉽게 복사 + 붙여넣기(Ctrl + C, V)함으로써 저의 서명을 제가 동의하지 않는 다른 문서에 감쪽같이 위조할 수 있을 것입니다. 그렇기 때문에, 디지털 세계에서의 서명은 현실 세계의 서명과는 약간 다르게 구현해야만 합니다. 그래서 우리는 Digital Signature를 어떻게 구현해야하는지에 대해 Course 후반부에서 다루도록 할 것입니다. (이것은 매우 흥미로운 주제입니다!)
힌트를 드리자면, 디지털 서명에서는 특정 문서에서 서명한 것을 다른 문서에 붙여넣었을 때 서명검증에 실패하도록 설계되어 있습니다. 공격자는 메세지와 서명의 내용을 수정할 수는 있지만, 검증하는 사람은 그 문서의 내용이 수정되었다는 사실을 검출할 수 있기 때문에 신뢰할 수 없는 내용이라는 것을 알 수 있도록 하는 것입니다. 즉, 변경하지 못하도록 방지하는 것이 아니라 문서에 변경행위가 있었는지 아닌지를 검출하는 차원에서 유용합니다. 우리는 앞으로 디지털 서명을 만들어내는 구조와 작동원리에 대해 학습할 것입니다.
다음으로는 무기명 통신(Anonymous Communication)에 대해 말씀드리겠습니다. Alice가 채팅서버인 Bob과 통신하려고 한다고 가정해봅시다. Alice는 자신의 민감한 개인정보인 의료정보, 질병과 관련된 내용 등을 말하려고 합니다. 이때 Alice는 이 내용을 익명으로(anonymously) 처리하고 싶어합니다. 서버인 Bob은, 채팅 서비스를 열심히 제공하지만, 그 대화에 참여하고 있는 사람이 누구인지는 알 수 없게됩니다. 이것은 일명 Mix network라고 불리우는 방법을 사용합니다. Mixnet은 다수의 프록시 서버를 사이에 두고, 각각의 노드가 암호화된 메세지를 주고 받는 과정을 여러번 수행합니다. 또한 각 MIX내부의 순서조차 짐작하기 어렵게 만들기 때문에, 중간에서 도청을 당하더라도 해커는 메세지의 송신자와 수신자 사이의 상관관계를 추측하기조차 어렵습니다. 이를 통해 Alice는 완전히 개방된 인터넷을 사용하면서도, Bob에게 자신의 존재를 철저히 숨길 수 있습니다. 또한, 흥미롭게도 이 익명성은 양방향성(bi-directional)을 갖습니다. Bob 또한 자신의 작업내용을 숨길 수 있다는 것이죠. 이러한 무기명 통신을 사용하면 다양한 보안 매커니즘에 응용할 수 있습니다.
대표적으로 전자 화폐(digital cash)가 있습니다. 실생활에서의 상거래는 어떤가요? 책을 사러 서점에 갔다고 해봅시다. 판매원에게 돈을 지불하였습니다. 판매원은 그것을 구입하는 제가 누구인지(who I am)에 대해서는 크게 신경쓰지 않아도 됩니다. 그저 물건을 팔고, 돈을 받는 것이죠. 이와 동일한 개념을 싸이버 세상에서는 어떻게 구현해야할까요? 기본적으로 전자 화폐(digital dollar, digital coin)를 사용하여 온라인 상의 서점이나 판매원으로부터 물건을 구매할 것입니다. 여기에서도 실생활에서의 거래처럼, 익명성(anonymity)을 보장하고자 합니다. 서점은 책을 구매하는 Alice가 누구인지 상관없이 그저 책을 파는 일에만 집중하게 하려고합니다. 이때 Alice는 1 dollar coin을 가지고 있었다고 가정해봅시다. 그런데 digital로 된 data의 특성상 손쉽게 복제가 가능합니다. 만약 Alice가 1달러를 사용하기 전에 이것을 copy했다면 어떻게될까요? 이와 같이 위조복제 된 화폐(replicas of a dollar coin)가 남용되는 것을 방지해야 할 필요가 있어보입니다. 그러기 위해서는 그 화폐의 소유자에 대한 명확한 정보가 있어야할 것 같습니다. 그렇다면, Alice가 돈을 복제하는 것을 방지하기 위해서는 익명성(anonymous) 보장은 포기해야하는 것일까요? 익명성을 지키기 위해서 코인의 출처를 숨길 경우, 그 코인의 유효성은 어떻게 보장할 수 있을까요? 이것이 누구의 돈인지 모르는데 어떻게 사기 거래(fraud)가 아니라고 확신할 수 있을까요? 이러한 가치들이 서로 충돌하는 것 같기 때문에 매우 모순되어 보입니다. 이러한 긴장을 해소할 수 있을까요? 그렇습니다. 우리는 추후에 anonymous digital cash에 관련하여 다음에 다룰것입니다.
약간의 힌트만 드리자면, Alice는 자신의 신분을 감춘 상태로 자유롭게 전자화폐를 사용할 수 있도록 합니다. 하지만 만약 복제된 화폐를 사용했다는 사실이 탄로난다면 그녀의 신분을 노출시켜버리는 것입니다! 그렇게되면 Alice는 그에 합당한 법적인 책임을 져야할 상황에 처하게 됩니다. 이것이 바로 Anonymous digital cash의 핵심 아이디어이며, 자세한 구현은 추후에 설명해드리도록 하겠습니다.
또 다른 여러 암호학 응용들을 살펴보겠습니다. 먼저, 전자투표(election system)시스템입니다. 두가지의 정당(parties)가 있다고 생각해볼까요? 예를들면, '0'과 '1'입니다. 그리고 유권자(voters)들은 그 둘중 하나에 투표권을 행사하게 됩니다. 누군가는 '0'당에, 누군가는 '1'당에 투표하겠지요. 만약 '0'정당은 3표를, '1'정당은 2표를 획득했다고 가정해봅시다. 그럼 당연하게도 '0'이 당선되었다고 볼 수 있습니다. 이러한 투표에서 중요한 것은, 투표결과 어떤 정당이 우세했는지를 판가름하는 것입니다. 하지만 그러면서 동시에 유권자 각각의 개별 정보는 비밀로 유지되어야만 합니다. 이를 구현하기 위해 일종의 선거관리 위원회(An election center)를 두고, 각각의 유권자가 자신의 투표내용을 암호화해서 center로 보냅니다. 모두의 투표가 끝나면, center는 판세분석 결과의 계산을 맡습니다. 물론, 그 내용은 보안이 지켜져야합니다. 뿐만아니라, Center는 각각의 유권자 한명이 여러번 중복으로 투표하는 등의 부정행위가 있었는지를 검출해내야할 의무가 있습니다. 이 또한 매우 모순적이지 않나요? input이 감추어져있는데, 그 input을 구별하고 구분할 수 있어야한다니!
이와 비슷한 또하나의 예시가 바로 비공개 입찰(Private auction)입니다. 여기에 참여하는 모든 입찰꾼들은 그들이 원하는 만큼의 가격을 제시하게됩니다. 이때 auction mechanism을 통해 가장 높은 가격을 부른 사람이 경매에서 승리하도록 해줍니다. 그러나 승자는 자신이 불렀던 가장 높은 값이 아닌, 다른 사람이 제시한 ‘두번째로 높은’ 값을 지불하는 방식입니다. 이러한 방식의 경매를 Vickrey auction이라고 부릅니다. 여기에서는 가장 높은 값을 부른 Winner 외에, 다른 모든 정보는 철저하게 비공개되어 처리되어야 합니다. 그러면서 동시에, Winner가 부른 가격이 아닌, Second highest bid가 공개되어야합니다. 그러기위해 Auction Center는 모든 입찰꾼(Bidder)로 부터 암호화 된 가격을 전달받고 계산하여 승자를 가려내야 합니다. 하지만 그 외의 모든 정보는 철저하게 비밀로 처리해야 합니다. 이러한 문제를 일반적으로 Secure multi-party computation이라고 합니다.
Secure Multi-party computation란, 어떤 행위에 참여하는 사람들이 비밀내용을 입력값으로 갖는 경우에, 그 입력값의 정렬된(sort)결과를 계산하여 출력(Output)하는 상황을 말합니다. 이것을 함수 f(x)로 정의하겠습니다. 투표의 경우에서는 입력값(Input)이 ‘투표내용’일 것이고, 출력값(Output)으로는 ‘투표 누적합의 과반수’가 될 것입니다. 마찬가지로 경매에서는 입력값이 ‘가격’이 되고, 출력값으로는 ‘가장 높은 가격(을 부른 사람)’, ‘두번째로 높은 가격’이 되겠죠. 문제는, 출력값인 f(x)의 값은 공개하면서, 동시에 입력값이었던 각각의 x1, x2, x3, x4등은 전부 비밀로 처리해야한다는 것입니다. 이를 어떻게 구현할 수 있을까요? 제가 한가지 방법을 제시해보겠습니다. 일종의 신뢰할 수 있는 기관(Trusted authority)이 있다고 가정해봅시다. 유권자나 입찰꾼들은 이 기관을 절대적으로 신뢰하는 마음으로 그들의 정보를 이 기관에 넘겨줍니다. 그리고 그 기관이 계산결과를 처리해서, 공개해줍니다. 아주 간단하죠? 그렇지만 이것은 매우 이상적이기에 불가능한 가정일테고, 실제로 그렇게 신뢰할 만한 기관이 있을까요? 그들을 믿었는데, 사기를 당하게된다면 어떡하죠?
여기에서 아주 중요한 암호학의 핵심(very central theorem) 한가지를 언급하고자 합니다. A trusted authority를 이용하여 당신이 무엇을 계산하려고 할 때에, 사실상 그런 기관의 도움이 전혀 없어도 충분히 안전하게 처리할 수 있습니다. 그러므로 그런 기관은 필요 없습니다. (you can compute with a trusted authority, you can also do without a trusted authority.)
이게 무슨뜻이나고요? 간단한 아이디어만 설명드리겠습니다. 여기 그림에서 유권자들은 Authority기관에 자신의 입력정보를 보내지 않기로 합시다. 쓸모없어진 Authority기관을 지워버리겠습니다. 앞으로 유권자들은 그저 특정 ‘프로토콜’을 사용하여 서로간에 각자 개별적인 소통을 합니다. 그 프로토콜의 양 끝단에서만이 최종 계산결과가 모두에게 발표됩니다. 그리고 그 외의 정보는 일절 공개되지 않습니다. 즉, 개별 input값은 비밀로 유지됩니다. 놀랍게도 이 모든게 다 됩니다!(it's kind of a surprising fact that is at all doable) 이렇게 만드는 방법을 이 강의에서 앞으로 다루도록 하겠습니다.
다음으로 보여드릴 몇개의 예시는, 뭐 어떻게 설명드려야할지 고민하다가 도저히 적절한 제목을 찾지 못해서 ‘Magic’이라고 밖에 표현을 못하겠습니다. 먼저 '비밀을 보장하고 심부름을 대행해주는 흥신소’입니다. 일종의 ‘해결사’랄까요. (역주 : 정확한 학술적 용어 동형암호, Homomorphic Encryption) 그 예시가 바로 Google과 같은 검색엔진의 기능입니다. Alice가 자신이 원하는 내용에 대해 인터넷을 통해 정보를 얻고자 합니다. Alice는 원하는 정보를 찾고, Google은 그 질문에 대한 답을 전송합니다. 여기에는 암호화 Scheme가 내장되어있어서, 이 모든 내용에 대해 보안이 유지됩니다. 구글은 요청문(query) 자체가 암호화된 상태에서 받아보기 때문에, 그 원래 내용(평문, plain text)을 모른채로 그저 정해진 규칙에 따라 검색 알고리즘을 수행한 뒤에, 그 결과값마저도 암호화된 상태로 Alice에게 응답해줍니다. Alice는 자신도 모르는 사이에 암호화된 결과를 받아서 자동적으로 복호화한 뒤에 내용을 확인하게 됩니다. 이러한 Magic같은 기술은 최근 2~3년 사이에 개발되어 유행하고 있습니다. 자신이 처리하는 데이터의 내용이 무엇이도 모르는채로 그 암호화된 데이터를 처리하는 기법입니다. 물론 굉장히 이론적으로 설명했는데다가, 실제 구글 검색의 모든 데이터 처리를 이런식으로 암호화하려면 백만년이 걸릴지도 모르겠지만.. 그럼에도 불구하고! 이 모든 것이 놀랍게도! 가능하다는 것이며, 비교적 간단한 계산에는 이미 충분히 적용하여 입증되었다는 사실입니다. 이러한 응용프로그램(Application)들에 대해서도 곧 살펴보도록 하겠습니다.
두번째로 설명드릴 Magic Application은 일명 ‘영지식 증명’(Zero knowledge, proof of knowledge) 입니다. Alice만 아는 N이라는 특정 숫자가 있습니다. 이 N은 두개의 매우 큰 소수(Prime Number, 약수의 개수가 2개인 자연수)의 곱으로 표현됩니다. 이 소수들은 둘다 1000자리가 넘는 매우 큰 숫자이며, 이를 각각 P와 Q라고 가정하겠습니다. 숫자가 아무리 크더라도, 그 둘을 곱하는 것은 비교적 쉽습니다. 하지만, 그 곱셈의 결과값N만 주어지고, 각각 어떤 P와 Q를 갖는지를 질문한다면 어떻겠습니까? 이것은 매우매우 (수학적으로) 어렵습니다. 이러한 발상이 바로 공개키 암호(public key crypto system)의 기본개념이며, 이 강의의 후반부에서 추후에 다룰 것입니다. 어쨌든, Alice는 N을 알고, 각각의 P와 Q를 알고 있다고 칩시다. 그런데 Bob은 N만 알고, 그것이 무엇의 곱으로 이루어진 숫자인지는 모르는 상태입니다. 이것이 바로 영지식 증명(Proof of knowledge)의 Magic입니다. Alice는 Bob에게 자신이 알고 있는 N 값을 제시함으로써, 서로가 같은 숫자를 공유하고 있음을 서로 확인하고, 서로의 신분을 확신할 수 있습니다. 일종의 암구호 같은 것이죠. 이러한 방식을 통해 Alice는 자신이 N값을 알고있다는 사실을 입증해 보임과 동시에, 그외 다른 정보(P와 Q)는 숨길 수 있습니다. 스도쿠 퍼즐(Sudoku Puzzle)을 아시나요? 정답을 찾은게 맞는지 아닌지를 판별하는 것은 쉽고 빠르지만, 실제 답이 무엇인지를 찾는 과정은 상당히 오래걸립니다. 이처럼 Alice는 P와 Q를 공개하지 않으면서도 자신이 N값을 알고있다는 사실을 남들에게 공표하고, 쉽게 검증받을 수 있습니다.
이번 강의에서 마지막으로 말씀드리고자 하는 것은, 암호학이란 매우매우 엄밀하고 정교한(rigorous) 학문이라는 것입니다. 우리가 앞으로 배울 모든 개념들을 다음의 세가지 단계에 입각하여 살펴볼 것입니다. 앞으로 digital signature와 같은 새로운 기법들을 소개할 것인데, 각 기법의 개념을 설명할 때에는 가장 먼저 해당기법의 위협모델(Threat model)이 무엇인지 정확하게 설명할 것입니다. 위협모델이라함은, 공격자가 digital signature의 어떤 부분을 공격할 수 있고, signature를 공격함으로써 얻는 이득은 무엇인가?에 대한 것입니다. 우리는 이것을 정확히 어떻게 대처해할 수 있는지에 대해 배울 것입니다. 방금은 digital signature를 예로 들었지만, 기타 다른 여러 보안기법에 대해서도 동일하게 Threat model을 정의할 것입니다. 그리고나서, 우리는 그에 알맞은 설계를 제안할 것이고, 동시에 그것이 해당 Threat model과 관련하여 과연 정말 안전하다고 볼 수 있는 것인지, 공격자가 그것을 해독하거나 깨기가 굉장히 어려운지, 등등을 확인하는 단계를 밟을 것입니다.
4. 우리 생활 속 암호
<주민등록번호>
주민 등록을 할 때에, 국가에서 국민에게 부여하는 고유 번호로 남녀노소 모두에게 자신만의 고유번호가 존재함. 고유 번호이기 때문에 주민번호 뒷자리는 겹쳐서는 안 되기 때문에 이러한 특정 법칙에 의해 정해짐
(예시) 991201-1796212
첫째번호
1 - 남녀성별의 의미
둘째-다섯째번호
7962 - 출생지역조합번호
여섯째번호
1 - 출생지역의 같은 성씨출생신고순서
일곱번째번호
2 - 오류검증번호
앞의 12자리 숫자에 각각 순서대로
2,3,4,5,6,7,8,9,2,3,4,5를 곱한 뒤 모두 더한다.
그 다음 11로 나눠서 나온 나머지를 11에서 뺀다.
9*2+9*3+1*4+2*5+0*6+1*7+1*8+7*9+9*2+7*3+2*4+1*5 = 185
<신용카드>
신용카드의 번호 검증을 위해 사용되는 개방형 공식으로 1960년대에 개발됨
1.신용카드의 매 홀수자리 숫자마다 2를 곱하여 더한다.
(이때 곱해서 나온 숫자가 두자리 수라면 각 자리의 숫자를 더한다)
홀수자리숫자 * 2 의 합 : 4*2+6*2+2*2+0*2+2*2+4*2+6*2+8*2 = 64
2.앞에서 곱하지 않은 짝수 자리의 각 숫자를 더한다.
짝수자리숫자의 합 :1+7+1+1+3+5+7+9 = 34
3. 1에서 나온 숫자와 2에서 나온 숫자를 더한다.
4. 이렇게 나온 값이 10으로 나누어 떨어지면 유효하고 그렇지 않다면 가짜이다.
(예시) 4011 4745 0703 0068
1.(홀수 자리 숫자 ×2)의 합 = (4×2)+(1×2)+(4×2)+(4×2)+(0×2)+(0×2)+(0×2)+(1+2)=29
2.짝수 자리 숫자의 합 = 0+1+7+5+7+3+0+8=31
3.29+31=60
4.60÷10=6
→10으로 나누어 떨어지므로 유효한 번호
<바코드>
첫번째 - 세번째자리
880 - 제조국가
네번째 - 일곱번째자리
1234- 제조업자
여덟번째 - 열두번째자리
56789 - 상품의 자체코드
열세번째자리
3 - 체크숫자
체크숫자 확인법
1. 홀수번째 자리에 있는 수들은 그대로 더한다.
2. 짝수번째 자리에 있는 수들을 더해 세배를 한다.
3. 1과 2를 더한 값에 체크숫자를 더한 수가 10의 배수가 되도록 체크숫자를 정한다
