# Difference between revisions of "One-Time Pad"

(5 intermediate revisions by the same user not shown) | |||

Line 1: | Line 1: | ||

− | A '''''one-time pad''''' is a form of encryption that, when encrypted with | + | 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 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 9: | Line 11: | ||

==Decryption== | ==Decryption== | ||

− | Decryption is done using the reverse of the encryption, so, if modular addition was used for the encryption, the decryption is performed with modular subtraction. Thus: | + | 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 | ciphertext: BPQ QXI | ||

Line 16: | Line 18: | ||

==Benefits== | ==Benefits== | ||

− | * The largest benefit of | + | * 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, only 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. |

==Deficiencies== | ==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== | ==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. | + | 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 | ' This program will encrypt a message with a randomly generated one-time pad using modular addition, and | ||

Line 73: | Line 80: | ||

[[Category: Cryptography]] | [[Category: Cryptography]] | ||

+ | [[Category: Scripts]] |

## Revision as of 16:02, 9 November 2017

A * one-time pad*, sometimes called a

*, 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.*

**Vernam cipher**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

- en.wikipedia.org/wiki/One-time_pad - Wikipedia.