The Unbreakable Cipher

  • [アーティクル]

The concept of perfect secrecy is that given the cipher text, and any resources and amount of time, the adversary has no way of getting to the plain text. Having the cipher text makes no difference and provides absolutely no additional information. The adversary can try a brute force approach, by trying each and every key, one by one, but this will still require the adversary to guess the plaintext. A cipher that enables this is an unbreakable cipher.

The contemporary symmetric encryption algorithms like AES and Triple-DES are not unbreakable ciphers in this sense. If you know that the plain text is a sentence in English, you have the cipher text, and you brute force, it may take you a long time, but eventually you will get only a few (probably only one) sentence in English as the plain text. This would beyond doubt be the plain text that you were looking for.

There is only one unbreakable cipher, which provides perfect secrecy as defined above. This is the One-time pad. In a One-time pad, the key size is equal to the size of the data to be encrypted. A key is used only once to encrypt data. This one-time key is random. When Alice wants to send an encrypted message (a sentence in English) to Bob, Alice generates a random sequence of bits, equal in length to the message and XOR’s this key and the message. To decrypt, Bob then XOR’s the cipher text with this One-time random key and the plain text is retrieved.

If Eve gets hold of the cipher text in transit, she may decide to get the plain text by brute forcing. If the message is n-bits, Eve can one by one, try all n-bit sequences as the key. But this will create every sentence in English of that length. In other words, given any sentence in English (constructed from n-bits), there will be a key that will transform the given cipher text to that sentence. Hence even knowing the cipher text requires Eve to guess the plaintext and provides absolutely no additional information.

The reason One-time pad is rarely used is because it requires the key to be transferred securely before the cipher text is transmitted, and since the key length is equal to the message length, key distribution becomes a problem.

Comments