[Etc] One-time Pad

 

 

Alice가 Bob에게 message b를 전달하고자 한다.

Eve도 내용을 확인할 수 있으므로 plain text를 cipher text로 암호화하여 보낸다.

암호화하는 데 사용되는 secret key r은 Alice와 Bob만 공유하며, 이는 uniform random bit이어야 한다.

cipher text를 만들 때는 xor을 사용한다. Bob이 plain text로 해독할 때에도 xor을 사용한다.

 

 

만약 Alice가 전송하는 message는 2-bit이고, Alice와 Bob이 공유하는 secret key가 1-bit면 어떻게 될까?

Eve가 xor의 특성을 이용하여 다음과 같이 message를 추측할 수 있으므로 위험하다.

따라서 message가 2-bit라면 secret key 역시 2-bit인 것이 안전하다.

 

 

만약 secret key가 랜덤으로 생성되지 않는다면 어떻게 될까?

예를 들어 secret key가 0일 확률이 1/4라면, 1일 확률은 3/4일 것이다.

이 경우 Eve가 secret key가 1일 것이라고 추측하고 message를 알아낼 수 있으므로 위험하다.

 

Von Neumann's trick은 biased coin을 fair coin으로 바꾸는 방식을 설명한다.

연속하는 두 비트가 같으면 버리고, 연속하는 두 비트가 같으면 첫 번째 비트를 가진다.