Difference between revisions of "One-time pad"

From TheAlmightyGuru
Jump to: navigation, search
(Created page with "A '''''one-time pad''''' is a form of encryption that cannot be cracked, so decryption is only possible with the key. It was first professionally described in 1882 by Frank Mi...")
 
(7 intermediate revisions by the same user not shown)
Line 1: Line 1:
A '''''one-time pad''''' is a form of encryption that cannot be cracked, so decryption is only possible with the key. It was first professionally described in 1882 by Frank Miller. Despite being uncrackable, it has several failings that make it unattractive for modern use.
+
A '''''one-time pad''''', sometimes called a '''''Vernam cipher''''', is a form of encryption that, when encrypted with an unpredictably random key, cannot be cracked, meaning decryption is only possible with the key. It was first professionally described in 1882 by Frank Miller, though a patent was later awarded to Gilbert S. Vernam in 1919. Despite being uncrackable, a one-time pad has several deficiencies that make it unattractive for modern use.
 +
 
 +
I learned about one-time pads while reading the [[Cryptonomicon]]. At first I didn't believe that this cipher was impossible to crack, but as I read more about it, it became obvious that this is the case.
  
 
==Encryption==
 
==Encryption==
Using a one-time pad, you must have a key that is at least as long as the plaintext. To encrypt the plaintext, you process each bit of the plaintext with each bit of the key and perform a reversible calculation like modular addition. The result is the ciphertext. For example:
+
To encrypt the plaintext, you process each letter of the plaintext with each letter of the key with a reversible calculation like modular addition or an XOR to yield the ciphertext. For most humans, the simplest way is to layout the alphabet, start on the letter of the plaintext, and move to the right the number of characters equal to the place value of the key letter while rotating back when you reach the end, like a [[Caesar cipher]]. For example, assuming our alphabet consists of 27 values (A = 1, B = 2, C = 3, ... Z = 26, and space = 27), a letter of plaintext that is C, moved right for the value of the key R (18 places), would result the ciphertext letter U. If the rotation were to reach the end of the alphabet, for example a plaintext X, rotated with a key letter G (7 places), we would rotate to the right until we hit the end, return to A, and continue counting, which yields a ciphertext of D. Using this technique, we can do the following:
 
 
Assuming A=1, B=2, C=3, ... Z=26, and space=0.
 
 
   
 
   
 
   plaintext: ATTACK TONIGHT
 
   plaintext: ATTACK TONIGHT
 
         key: IQENEPLRB ZAZF
 
         key: IQENEPLRB ZAZF
  ciphertext:  
+
  ciphertext: JJYOH LIQNHHGZ
 +
 
 +
==Decryption==
 +
Decryption is done using the reverse of the encryption, so, if modular addition (rotating to the right) was used for the encryption, the decryption is performed with modular subtraction (rotating to the left). Thus:
 +
 
 +
ciphertext: BPQ QXI
 +
        key: KKCILWP
 +
  plaintext: RETREAT
 +
 
 +
==Benefits==
 +
* The largest benefit of an unpredictably random one-time pad is that the encryption is unbreakable without the key because you can get any possible result from a different key. For example, in the decryption example above, the key KKCILWP would accurately decrypt the text to RETREAT, but the key PVWEDPN would decrypt the text to OFFENSE, while NQIAXKJ would decrypt it to LASAGNA.
 +
* It's very simple to encrypt and decrypt a one-time pad. Most modern encryption methods require the use of powerful computers, but to use a one-time pad you don't even need to know how to add or even read, you only need to know how to count.
 +
 
 +
==Deficiencies==
 +
* What makes the one-time pad so impractical is the difficulty of dealing with keys. There are several problems that make them difficult to generate and maintain.
 +
** Until recently, it was difficult to create an unpredictably random (or, cryptographically secure pseudorandom) key. To this day, it is still a hard problem, and most random number generators found on computers are not sufficient for cryptographic use. Poorly made random keys contain patterns which can be exploited so the ciphertext may be cracked.
 +
** While a key doesn't have to be randomly generated--you could use an agreed upon book and include a page and paragraph in your message, for example--anything other than an unpredictably random key introduces patterns into the ciphertext which make it possible to crack.
 +
** Keys should be as long or longer than the plaintext, and since you won't know how long the plaintext will be in advance, you have to generate keys that are as long as the longest message you plan to send. You can create a longer key by looping the same key, but, again, this introduces patterns which may allow the ciphertext to be cracked.
 +
** Key should never be reused or future enciphered text may be cracked.
 +
** Since the keys are long, random, and numerous, it's not practical to memorize them, which means they must be written down and kept with both the sender and receiver. Whenever a key is written down, it's always possible your enemy might see them.
 +
 
 +
==Program==
 +
I wrote this [[FreeBASIC]] program that can take a message written in the printable characters of 7-bit ASCII, generate a random pad, encrypt the plaintext with modular addition and decrypt it with modular subtraction. Please note that the random number generator is not cryptographically secure.
 +
 
 +
' This program will encrypt a message with a randomly generated one-time pad using modular addition, and
 +
' then decrypt it using modular subtraction. Since it uses the ASCII code as its alphabet, the math is a
 +
' little more complex than a simple alphabet, but this allows it to be more usable on computers.
 +
' © Copyright 2017, Dean Tersigni
 +
 +
Randomize Timer
 +
Dim As String sPlainText, sKey, sCipherText, sEncyptedLetter, sDecryptedText
 +
Dim As Integer iPlace, iRandom, iEncryptedLetter
 +
 +
' This is the plaintext message.
 +
sPlainText = "Attack tonight @ 9 PM!"
 +
 +
' Generate a random one-time pad key the same length as the plaintext.
 +
For iPlace = 1 To Len(sPlainText)
 +
    iRandom = Int(Rnd * 94) + 32      ' Only use printable characters in the key.
 +
    sKey = sKey + Chr(iRandom)
 +
Next iPlace
 +
 +
' Encrypt the plaintext using modular addition.
 +
For iPlace = 1 To Len(sPlainText)
 +
    iEncryptedLetter = Asc(Mid(sPlainText, iPlace, 1)) + (Asc(Mid(sKey, iPlace, 1)) - 31)
 +
    If iEncryptedLetter > 126 Then
 +
        iEncryptedLetter = iEncryptedLetter - 95
 +
    End If
 +
    sCipherText = sCipherText + Chr(iEncryptedLetter)
 +
Next iPlace
 +
 +
' Decrypt the ciphertext using modular subtraction.
 +
For iPlace = 1 To Len(sPlainText)
 +
    iEncryptedLetter = Asc(Mid(sCipherText, iPlace, 1)) - (Asc(Mid(sKey, iPlace, 1)) - 31)
 +
    If iEncryptedLetter < 32 Then
 +
        iEncryptedLetter = iEncryptedLetter + 95
 +
    End If
 +
    sDecryptedText = sDecryptedText + Chr(iEncryptedLetter)
 +
Next iPlace
 +
 +
Print " Plaintext: " + sPlainText
 +
Print "      Key: " + sKey
 +
Print "Ciphertext: " + sCipherText
 +
Print "Decryption: " + sDecryptedText
 +
 +
Sleep
  
 
==Links==
 
==Links==
 +
* [https://en.wikipedia.org/wiki/One-time_pad en.wikipedia.org/wiki/One-time_pad] - Wikipedia.
  
  
 
[[Category: Cryptography]]
 
[[Category: Cryptography]]
 +
[[Category: Scripts]]

Revision as of 17:00, 12 October 2017

A one-time pad, sometimes called a Vernam cipher, is a form of encryption that, when encrypted with an unpredictably random key, cannot be cracked, meaning decryption is only possible with the key. It was first professionally described in 1882 by Frank Miller, though a patent was later awarded to Gilbert S. Vernam in 1919. Despite being uncrackable, a one-time pad has several deficiencies that make it unattractive for modern use.

I learned about one-time pads while reading the Cryptonomicon. At first I didn't believe that this cipher was impossible to crack, but as I read more about it, it became obvious that this is the case.

Encryption

To encrypt the plaintext, you process each letter of the plaintext with each letter of the key with a reversible calculation like modular addition or an XOR to yield the ciphertext. For most humans, the simplest way is to layout the alphabet, start on the letter of the plaintext, and move to the right the number of characters equal to the place value of the key letter while rotating back when you reach the end, like a Caesar cipher. For example, assuming our alphabet consists of 27 values (A = 1, B = 2, C = 3, ... Z = 26, and space = 27), a letter of plaintext that is C, moved right for the value of the key R (18 places), would result the ciphertext letter U. If the rotation were to reach the end of the alphabet, for example a plaintext X, rotated with a key letter G (7 places), we would rotate to the right until we hit the end, return to A, and continue counting, which yields a ciphertext of D. Using this technique, we can do the following:

 plaintext: ATTACK TONIGHT
       key: IQENEPLRB ZAZF
ciphertext: JJYOH LIQNHHGZ

Decryption

Decryption is done using the reverse of the encryption, so, if modular addition (rotating to the right) was used for the encryption, the decryption is performed with modular subtraction (rotating to the left). Thus:

ciphertext: BPQ QXI
       key: KKCILWP
 plaintext: RETREAT

Benefits

  • The largest benefit of an unpredictably random one-time pad is that the encryption is unbreakable without the key because you can get any possible result from a different key. For example, in the decryption example above, the key KKCILWP would accurately decrypt the text to RETREAT, but the key PVWEDPN would decrypt the text to OFFENSE, while NQIAXKJ would decrypt it to LASAGNA.
  • It's very simple to encrypt and decrypt a one-time pad. Most modern encryption methods require the use of powerful computers, but to use a one-time pad you don't even need to know how to add or even read, you only need to know how to count.

Deficiencies

  • What makes the one-time pad so impractical is the difficulty of dealing with keys. There are several problems that make them difficult to generate and maintain.
    • Until recently, it was difficult to create an unpredictably random (or, cryptographically secure pseudorandom) key. To this day, it is still a hard problem, and most random number generators found on computers are not sufficient for cryptographic use. Poorly made random keys contain patterns which can be exploited so the ciphertext may be cracked.
    • While a key doesn't have to be randomly generated--you could use an agreed upon book and include a page and paragraph in your message, for example--anything other than an unpredictably random key introduces patterns into the ciphertext which make it possible to crack.
    • Keys should be as long or longer than the plaintext, and since you won't know how long the plaintext will be in advance, you have to generate keys that are as long as the longest message you plan to send. You can create a longer key by looping the same key, but, again, this introduces patterns which may allow the ciphertext to be cracked.
    • Key should never be reused or future enciphered text may be cracked.
    • Since the keys are long, random, and numerous, it's not practical to memorize them, which means they must be written down and kept with both the sender and receiver. Whenever a key is written down, it's always possible your enemy might see them.

Program

I wrote this FreeBASIC program that can take a message written in the printable characters of 7-bit ASCII, generate a random pad, encrypt the plaintext with modular addition and decrypt it with modular subtraction. Please note that the random number generator is not cryptographically secure.

' This program will encrypt a message with a randomly generated one-time pad using modular addition, and 
' then decrypt it using modular subtraction. Since it uses the ASCII code as its alphabet, the math is a 
' little more complex than a simple alphabet, but this allows it to be more usable on computers.
' © Copyright 2017, Dean Tersigni

Randomize Timer
Dim As String sPlainText, sKey, sCipherText, sEncyptedLetter, sDecryptedText
Dim As Integer iPlace, iRandom, iEncryptedLetter

' This is the plaintext message.
sPlainText = "Attack tonight @ 9 PM!"

' Generate a random one-time pad key the same length as the plaintext.
For iPlace = 1 To Len(sPlainText)
    iRandom = Int(Rnd * 94) + 32      ' Only use printable characters in the key.
    sKey = sKey + Chr(iRandom)
Next iPlace

' Encrypt the plaintext using modular addition.
For iPlace = 1 To Len(sPlainText)
    iEncryptedLetter = Asc(Mid(sPlainText, iPlace, 1)) + (Asc(Mid(sKey, iPlace, 1)) - 31)
    If iEncryptedLetter > 126 Then
        iEncryptedLetter = iEncryptedLetter - 95
    End If
    sCipherText = sCipherText + Chr(iEncryptedLetter)
Next iPlace

' Decrypt the ciphertext using modular subtraction.
For iPlace = 1 To Len(sPlainText)
    iEncryptedLetter = Asc(Mid(sCipherText, iPlace, 1)) - (Asc(Mid(sKey, iPlace, 1)) - 31)
    If iEncryptedLetter < 32 Then
        iEncryptedLetter = iEncryptedLetter + 95
    End If
    sDecryptedText = sDecryptedText + Chr(iEncryptedLetter)
Next iPlace

Print " Plaintext: " + sPlainText
Print "       Key: " + sKey
Print "Ciphertext: " + sCipherText
Print "Decryption: " + sDecryptedText

Sleep

Links