Difference between revisions of "One-Time Pad"

From TheAlmightyGuru
Jump to: navigation, search
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
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.
+
A '''''one-time pad''''', sometimes called a '''''Vernam cipher''''', is a form of encryption that, when encrypted with an unpredictably random key, can only be decrypted with the key, so cracking is imposiible. 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 such a basic cipher was impossible to crack, but as I read more about it, it became obvious that this is the case.
  
 
==Encryption==
 
==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 add the value of the plaintext rotate the character along the alphabet a number of times equal to rotate along an alphabet. 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, rotated right for the key letter of R (18 places), would result with ciphertext letter U. If the rotation were to reach the end of the alphabet, for example a plaintext X, rotated with a key letter of G (7 places), we would rotate to the right until we hit the end, return to A, and continue counting yielding a ciphertext of D. Using this technique, we can do the following:
+
To encrypt with a one-time pad, you first generate a random key that must be at least as long as the information you want to encrypt. Then, 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 right the number of characters equal to the place value of the key letter (and returning to the beginning of the alphabet 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
 
   plaintext: ATTACK TONIGHT
Line 16: Line 18:
  
 
==Benefits==
 
==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.
+
* The largest benefit of an unpredictably random one-time pad is that the encryption is unbreakable without the key. This is because every key will give you an answer, and many of those answers will be valid. 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.
 
* 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.
  
Line 24: Line 26:
 
** 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.
 
** 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.
 
** 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.
** Since the keys are both long and random, 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.
+
** 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==
 
==Program==
Line 77: Line 80:
  
 
[[Category: Cryptography]]
 
[[Category: Cryptography]]
 +
[[Category: Scripts]]

Latest revision as of 15:02, 9 November 2017

A one-time pad, sometimes called a Vernam cipher, is a form of encryption that, when encrypted with an unpredictably random key, can only be decrypted with the key, so cracking is imposiible. 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 such a basic cipher was impossible to crack, but as I read more about it, it became obvious that this is the case.

Encryption

To encrypt with a one-time pad, you first generate a random key that must be at least as long as the information you want to encrypt. Then, 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 right the number of characters equal to the place value of the key letter (and returning to the beginning of the alphabet 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. This is because every key will give you an answer, and many of those answers will be valid. 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