miércoles, 22 de agosto de 2012

Introductory Assignment: One-time-pad

For the first assignment, we were tasked to do a one time pad program. I chose python as a programming language, and did a simple version of the one-time-pad, which I will explain later.


One-time-pad is a cipher method invented in 1917 by the Major Joseph Mauborgne and Gilbert Vernam from AT&T. Claude Shannon, 25 years later was in charge of proving with information theory that this cipher was infact a perfect secret, which means that the message content cannot give any useful information to the attacker.

In this cryptographic algorithm, plaintext is combined with a random key. It is the only known method to perform mathematically unbreakable encryption.
We can only talk about one-time pad if some important rules are followed. If these rules are applied correctly, the one-time pad can be proven unbreakable.

Even infinite computational power and infinite time cannot break one-time pad encryption, simply because it is mathematically impossible. However, if only one of these rules is disregarded, the cipher is no longer unbreakable.
  • The key is at least as long as the message or data that must be encrypted.
  • The key is truly random (not generated by a simple computer function or such)
  • Key and plain text are calculated modulo 10 (digits), modulo 26 (letters) or modulo 2 (binary)
  • Each key is used only once, and both sender and receiver must destroy their key after use.
  • There should only be two copies of the key: one for the sender and one for the receiver (some exceptions exist for multiple receivers.


First, we have or message, HELLO. Now we can get an integer number which would be the position of the letter in the alphabet. H would be 7, E is 4, L is 11, again L with 11, and finally O which is 14. Then we need to generate a random key, combining letters of the alphabet. This key needs to be the same size as our message, so it should be 5 characters long. Having the key, we add the position of the first letter of the message to the same of the key, then the second, third, etc, and save the values. Said values will be then normalized with the operation mod % 26 (26 letters in the alphabet), which will convert any number greater than 26 to a lesser number. Then this number will be the index of the corresponding letter to get a cipher text.

In the example bellow, we can see the process:

      H       E       L       L       O  message
   7 (H)   4 (E)  11 (L)  11 (L)  14 (O) message
+ 23 (X)  12 (M)   2 (C)  10 (K)  11 (L) key
= 30      16      13      21      25     message + key
=  4 (E)  16 (Q)  13 (N)  21 (V)  25 (Z) message + key (mod 26)
      E       Q       N       V       Z  → cipher text

Assuming this message is sent to someone who also knows the key(B), the person who encrypted this message(A) should delete the key. 

Then that B person, should be able to decrypt the message, doing the inverse operation ( substraction) and using the key.

       E       Q       N       V       Z  ciphertext
    4 (E)  16 (Q)  13 (N)  21 (V)  25 (Z) ciphertext
-  23 (X)  12 (M)   2 (C)  10 (K)  11 (L) key
= -19       4      11      11      14     ciphertext — key
=   7 (H)   4 (E)  11 (L)  11 (L)  14 (O) ciphertext — key (mod 26)
       H       E       L       L       O  → message

from sys import argv, stdout
from random import randint

def letter_pos(letter):
  for i in range(len(alphabet)):
    if alphabet[i] == letter:
 return i

def wiki_cipher(msg, key):
  cipher_msg = ""
  #print msg
  for i in range(len(msg)):
    #print letter_pos(msg[i]), letter_pos(key[i])
    cipher_msg += alphabet[(letter_pos(msg[i]) + letter_pos(key[i])) % 25]
  del key
  #print cipher_msg
  return cipher_msg

def wiki_decipher(cipher_msg, key):
  msg = ""
  for i in range(len(cipher_msg)):
    #print letter_pos(cipher_msg[i]), letter_pos(key[i])
    msg += alphabet[(letter_pos(cipher_msg[i]) - letter_pos(key[i])) % 25]
  del key
  #print msg
  return msg

def print_otp(ciphers):
  for cipher in ciphers:
  print ""

  filename = argv[1]
  f = open(filename, "r")
  msg = f.readlines()[0]
  msg.replace("\n", "")
  print "Message:"
  print msg
except IndexError as err:
  print "File not specified, using default message."
  msg = "Testing the one time pad encryption"
  print "Message: %s"%msg.lower()
alphabet = "abcdefghijklmnopqrstuvwxyz"
forbidden = " .,-!?$%&/()=+{{}}][:;_"
if " " in msg:
  words = [""]
  j = 0
  for i in range(len(msg)):
    if msg[i] in forbidden or msg[i] == "\n":
      words[j] += msg[i]
  del msg
  ciphers = []
  keys = []
  for word in words:
    key = ""
    for letter in word:
     key += alphabet[randint(0, 25)]
    if word != None:
      ciphers.append(wiki_cipher(word.lower(), key))
  print "Encrypted Message:"
  print ""
  msg = ""
  for i in range(len(ciphers)):
    msg += wiki_decipher(ciphers[i], keys[i]) + " "
  print "Decrypted message: %s"%msg

  cipher_msg = wiki_cipher(msg, key)
  del msg
  wiki_decipher(cipher_msg, key)
The python script bellow applies the previous algorithm to simple words or phrases. If specified, the script reads the message from a file, otherwise it will use a default message as an example.

An example run using a file named "msg" with a message "Hello my name is Emmanuel and this is a simple one-time-pad message" produces the following ouput:

As you can see, the message is changed to lowercase, and some "forbidden" characters are ignored replacing them for a space.


1 comentario:

  1. I would not put the spaces visible, but rather include ' ' in the alphabet to code it as well. Also, the code could be more modular, to permit a previous key-generation phase and then later encryption and/or decryption to messages one by one as separate executions. 4 pts for the first homework.