[Blink]

One Time Pad: The only unbreakable encryption

---

Encryption is one of the fundamental concepts in computer science.  In this tutorial, we'll be talking about one time pad encryption.  One time pad is an extremely simple encryption scheme, that is mathematically unbreakable.  It used to be used by various government agencies, including the KGB.

How does it work?

If you want to send a message to someone, first, you and the receiver must obtain a large enough amount of the same random data which is known as the 'pad'.
Then, add that each number in the pad to the message, where A = 0, B = 1, C = 2, etc.
You start with the first number in the pad, with each new character in the message, you move to the next number in the pad.
If one of the resulting numbers is greater than the size of the character set (26, in the English alphabet), loop back around from 0.

In order for the recipient to decode the message, they need to have the same pad.  
They subtract each part of the pad from the message, and if the result is lower than 0, they loop back from the largest number. (if it was the English alphabet, they would loop back from 26)

Psudocode:

Here's how the algorithm looks in psudocode

Code:

function encode(message, n):
   static x
   for i in message:
       z = i + pad[x]
       if z > n:
           z = 0 + (z - n)
       encoded.append(z)
       x++
   return encoded

function decode(message, n):
   static x
   for i in message:
       z = i - pad[x]
       if z < 0:
           z = n + z
       decoded.append(z)
       x++
   return decoded

Take a look at that, you should fully understand it before moving on. (pad is global btw)

How is this uncrackable?

Lets try to crack "HELLO", which has a pad of "1,2,3,4,5"
H -> 7 (we're starting from 0)
E -> 4
L -> 11
L -> 11
O -> 14

Now, let's apply our pad
7 + 1 -> 8
4 + 2 -> 6
11 + 3 -> 14
11 + 4 -> 15
14 + 5 -> 19

Now, let's try to crack it...
Wait...
Since the shift changes with each character, every 5 letter word is equally likely...
On top of that, if we encode the space character, and loop back at 27 instead of looping at 26, then for any size of text, every possible piece of text that is the size of the encoded text is equally likely.  So, if the encoded text comes out to "XCVSFENSE", "HELLO ABE" is as likely as "HEY ENDER".  Because of this, it is mathematically uncrackable.

Why don't we use this everywhere then?

There's a few issues with this.  It's annoyingly hard to use securely.  To start, you need a good source of random data; however, not only that, but you also need to transfer that securely.  On top of that, you can't safely reuse the same pad, so you need to transfer a new pad each time you use up the old one.  It is for these reasons that it isn't used a lot.

---

I hope you learned from this.  Don't forget to post below with comments, questions, or general discussion related to this.

[phyrrus9]

One Time Pad: The only unbreakable encryption

---

Encryption is one of the fundamental concepts in computer science.  In this tutorial, we'll be talking about one time pad encryption.  One time pad is an extremely simple encryption scheme, that is mathematically unbreakable.  It used to be used by various government agencies, including the KGB.

How does it work?

If you want to send a message to someone, first, you and the receiver must obtain a large enough amount of the same random data which is known as the 'pad'.
Then, add that each number in the pad to the message, where A = 0, B = 1, C = 2, etc.
You start with the first number in the pad, with each new character in the message, you move to the next number in the pad.
If one of the resulting numbers is greater than the size of the character set (26, in the English alphabet), loop back around from 0.

In order for the recipient to decode the message, they need to have the same pad.  
They subtract each part of the pad from the message, and if the result is lower than 0, they loop back from the largest number. (if it was the English alphabet, they would loop back from 26)

Psudocode:

Here's how the algorithm looks in psudocode

Code:

function encode(message, n):
   static x
   for i in message:
       z = i + pad[x]
       if z > n:
           z = 0 + (z - n)
       encoded.append(z)
       x++
   return encoded

function decode(message, n):
   static x
   for i in message:
       z = i - pad[x]
       if z < 0:
           z = n + z
       decoded.append(z)
       x++
   return decoded

Take a look at that, you should fully understand it before moving on. (pad is global btw)

How is this uncrackable?

Lets try to crack "HELLO", which has a pad of "1,2,3,4,5"
H -> 7 (we're starting from 0)
E -> 4
L -> 11
L -> 11
O -> 14

Now, let's apply our pad
7 + 1 -> 8
4 + 2 -> 6
11 + 3 -> 14
11 + 4 -> 15
14 + 5 -> 19

Now, let's try to crack it...
Wait...
Since the shift changes with each character, every 5 letter word is equally likely...
On top of that, if we encode the space character, and loop back at 27 instead of looping at 26, then for any size of text, every possible piece of text that is the size of the encoded text is equally likely.  So, if the encoded text comes out to "XCVSFENSE", "HELLO ABE" is as likely as "HEY ENDER".  Because of this, it is mathematically uncrackable.

Why don't we use this everywhere then?

There's a few issues with this.  It's annoyingly hard to use securely.  To start, you need a good source of random data; however, not only that, but you also need to transfer that securely.  On top of that, you can't safely reuse the same pad, so you need to transfer a new pad each time you use up the old one.  It is for these reasons that it isn't used a lot.

---

I hope you learned from this.  Don't forget to post below with comments, questions, or general discussion related to this.

God I love OTP. The only unbreakable encryption algorithm ever (since the plaintext and the cipher depend on each other). The only problem with OTP is it loses it's security (to effectively nil) if you tell anyone the pad (or use it twice). This was the sort of concept that broke the enigma machines.