완전 비밀성

다음 게임을 봅시다 이브는 밥이 방으로 들어가도록 지시합니다 밥은 방이 비어있는 것을 발견합니다 몇 개의 자물쇠와 빈 상자 하나 카드 덱 하나를 제외하고요 이브는 밥에게 카드 한 장을 고르고 그가 할 수 있는 한 잘 숨겨보라고 이야기합니다 규칙은 간단합니다 밥은 무엇도 가지고 나갈 수 없고 카드와 열쇠를 모두 방안에 두어야 하며 상자에는 최대 한 장의 카드를 넣을 수 있습니다 이브는 그녀가 자물쇠를 본 적 없다는 데에 동의합니다 이브가 그의 카드를 짐작할 수 없다면 그는 게임에서 이기게 됩니다 그렇다면 밥의 최고의 전략은 무엇일까요? 밥은 6 다이아몬드 카드를 골랐고 상자에 던져 넣었습니다 먼저 그는 다양한 종류의 자물쇠를 고려했습니다 그는 열쇠를 이용하여 카드를 박스에 잠가 넣을 수도 있겠죠 하지만, 이브가 자물쇠를 고를 수 있기 때문에 밥은 번호 자물쇠를 고려합니다 암호가 뒤에 있기 때문에 그가 잠근 뒤에 암호를 지워버리면 가장 좋은 방법이 될 것처럼 보입니다 하지만 그는 갑자기 문제점을 깨닫습니다 테이블 위에 남아 있는 카드가 그가 선택한 카드에 관한 정보를 누설하고 있다는 거죠 이제 카드덱에 들어있지 않으니까요 자물쇠는 유인용이었던 겁니다 그는 카드를 덱에서 빼면 안 되는 것이죠 그는 그의 카드를 팩으로 돌려놓지만 그가 고른 카드의 위치를 기억하지 못 합니다 그래서 그는 카드 더미를 섞어 순서를 임의로 바꿉니다 섞는 것은 가장 좋은 자물쇠죠 왜냐하면 그의 선택에 대한 정보를 남기지 않기 때문입니다 그의 카드는 이제 덱 안의 어떤 카드라도 될 수 있습니다 그는 이제 자신감을 가지고 카드를 공개적으로 놔둘 수 있습니다 밥은 게임에서 이기게 됩니다 왜냐하면 그가 선택에 대해 아무런 정보도 남기지 않았기에 이브가 할 수 있는 전부는 그저 예측하는 것뿐이죠 가장 중요한 것은 만일 우리가 이브에게 엄청난 계산능력을 준다고 하더라도 그녀가 할 수 있는 최선은 예측하는 것이라는 겁니다 이것은 우리가 완전 비밀성이라고 부르는 것을 정의합니다 1945년 9월 1일 29살의 클라우드 섀넌 은 이 아이디어를 가지고 기밀 보고서를 발행했습니다 섀넌은 일회용 암호표가 어떻게, 그리고 왜 완전히 비밀로 유지되는지에 대한 첫 수학적 근거를 제시했습니다 섀넌은 암호 시스템에 대해서 다음과 같이 생각합니다 앨리스가 밥에게 20자 길이의 메시지를 쓴다고 상상해 봅시다 이것은 모든 가능한 메시지 공간에서 하나의 특정 페이지를 고르는 것과 같습니다 메시지 공간은 사용 가능한 모든 20자 메시지의 모음으로 생각될 수 있습니다 여러분이 20자 길이로 생각할 수 있는 그 어떤 메시지든 간에 이 공간에서 하나의 페이지 입니다 다음으로 앨리스는 암호 키를 제공하는데, 이는 1과 26 사이에서 임의로 고른 20개의 숫자 목록입니다 키 공간은 모든 가능한 결과의 모음이라, 키를 만들어내는 것은 임의로 이 묶음에서 페이지 하나를 고르는 것과 마찬가지이죠 그녀가 메시지를 암호화하기 위해 변화를 적용하면 결과적으로 암호문이 됩니다 암호문 공간은 암호문의 가능한 모든 결과를 나타냅니다 그녀가 키를 적용하면 그 키는 이 묶음에서 유일한 페이지를 나타냅니다 메시지 공간의 크기는 키 공간의 크기와 같고 암호문 공간의 크기와도 같다는 걸 알아두세요 이것은 우리가 완전 비밀성이라고 부르는 것을 정의합니다 만약 누군가가 암호문에만 접근할 수 있다면 그들이 아는 유일한 것은 모든 가능한 메시지가 동일한 가능성이 있다는 것이죠 그러므로 어떤 계산적 힘도 예측을 개선할 수 없다는 겁니다 이제 이 일회용 암호표의 문제는 우리가 이 긴 암호를 공유해야 한다는 것이죠 이 문제를 해결하기 위해서 우리는 비밀성의 정의를 완화해야 합니다 의사 무작위성의 정의를 개발함으로써 요