Difference between revisions of "One-time pad"

From TheAlmightyGuru
Jump to: navigation, search
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 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.
  
 
==Encryption==
 
==Encryption==

Revision as of 15:28, 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.

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:

 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.
    • 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.

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