Pages

Thursday, October 8, 2015

One-Time Pad Cipher

In cryptography, the one-time pad (OTP) is an encryption technique that cannot be cracked if used correctly. It was invented near the end of WWI by Gilbert Vernam and Joseph Mauborgne in the US. It was mathematically proven unbreakable by Claude Shannon, probably during WWII, his work was first published in the late 1940s.

How it work

In this technique, a plaintext is paired with a random secret key (also referred to as a one-time pad). Then, each bit or character of the plaintext is encrypted by combining it with the corresponding bit or character from the pad using modular addition. If the key is truly random, is at least as long as the plaintext, is never reused in whole or in part, and is kept completely secret, then the resulting ciphertext will be impossible to decrypt or break.

Are one-time pads really unbreakable?

Yes. But only if used properly. A one-time pad must be truly random data and must be kept secure in order to be unbreakable. Consider if the one-time pad is used to encode the word "otter." If an attacker tries to brute force "guess" the contents of the pad, the message will "decrypt" into every possible combination of 6 characters (e.g.: "lemur." "badger" etc..) Since the pad is truly random there are no statistical methods that the attacker can hope to use to infer which combination is correct.

Below is the example of one time cipher work



In this example, the technique is to combine the key and the message using modular addition. The numerical values of corresponding message and key letters are added together, modulo 26 (%26). So, if key randomly begins with "XMCKL" and the message is "HELLO", then the coding would be done as follows:

Calculation:

A B C D E F G H I J K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

H + X = E because 7 + 23 = 30 % 26 = 4 is E
E + M = Q because 4 + 12 = 16 % 26 = 16 is Q
so on..


      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  → ciphertext


Ciphertext = EQNVZ
This is similar with caesar cipher. This simply means that if the computations "go past" Z, the sequence starts again at A.

Now, Let's Decrypt

The ciphertext is "EQNVZ". Use the matching key and the same process but in reverse to obtain the plaintext. Here the key is subtracted from the ciphertext again using modular arithmetic:

       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

Text = HELLO

However, it is difficult to ensure that the key is actually random is used only once, never becomes known to the opposition and is completely destroyed after use. The auxiliary parts of a software one-time pad implementation present real challenges: secure handling/transmission of plaintext truly random keys and one-time-only use of the key.



ATTACKERS
In attempting of cryptanalysis, suppose the ciphertext is "EQNVZ". If receiver had a lot of time, he/she would find that the key "XMCKL" that would produce the plaintext "HELLO" but if he/she randomly use the key "TQURI" would produce the plaintext "LATER". completely wrong message

    4 (E)  16 (Q)  13 (N)  21 (V)  25 (Z) ciphertext
−  19 (T)  16 (Q)  20 (U)  17 (R)   8 (I) possible key
= −15       0      −7       4      17     ciphertext-key
=  11 (L)   0 (A)  19 (T)   4 (E)  17 (R) ciphertext-key (mod 26)
           
Text = LATER

In fact, it is possible to "decrypt" out of the ciphertext any message what so ever with the same number of characters, simply by using a different key, and there is no information in the ciphertext which will allow attackers to choose among the various possible readings of the ciphertext.



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/*
   modified by hafiq
   One time pad cipher and decrypt
   any expert can advise me to improve this code...tq..
*/
import java.util.*;

public class OTPCipher{
   public static void main(String[] args){
      String text = "REPEAT ATTACK TONIGHT";
      String key = RandomAlpha(text.length());
      
      String enc = OTPEncryption(text,key);
      System.out.println("Plaintext : "+text);
      System.out.println("Encrypted : "+enc);
      System.out.println("Decrypted : "+OTPDecryption(enc,key));
   }
   
   public static String RandomAlpha(int len){
      Random r = new Random();
      String key = "";
      for(int x=0;x<len;x++)
         key = key + (char) (r.nextInt(26) + 'A');
      return key;
   }
   
   public static String OTPEncryption(String text,String key){
      String alphaU = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
      String alphaL = "abcdefghijklmnopqrstuvwxyz";
      
      int len = text.length();
      
      String sb = "";
      for(int x=0;x<len;x++){
         char get = text.charAt(x);
         char keyget = key.charAt(x);
         if(Character.isUpperCase(get)){
            int index = alphaU.indexOf(get);
            int keydex = alphaU.indexOf(Character.toUpperCase(keyget));
            
            int total = (index + keydex) % 26;
            
            sb = sb+ alphaU.charAt(total);
         }
         else if(Character.isLowerCase(get)){
            int index = alphaL.indexOf(get);
            int keydex = alphaU.indexOf(Character.toLowerCase(keyget));
            
            int total = (index + keydex) % 26;
            
            sb = sb+ alphaL.charAt(total);
         }
         else{
            sb = sb + get;
         }
      }
      
      return sb;
   }
   public static String OTPDecryption(String text,String key){
      String alphaU = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
      String alphaL = "abcdefghijklmnopqrstuvwxyz";
      
      int len = text.length();
      
      String sb = "";
      for(int x=0;x<len;x++){
         char get = text.charAt(x);
         char keyget = key.charAt(x);
         if(Character.isUpperCase(get)){
            int index = alphaU.indexOf(get);
            int keydex = alphaU.indexOf(Character.toUpperCase(keyget));

            int total = (index - keydex) % 26;
            total = (total<0)? total + 26 : total;
            
            sb = sb+ alphaU.charAt(total);
         }
         else if(Character.isLowerCase(get)){
            int index = alphaL.indexOf(get);
            int keydex = alphaU.indexOf(Character.toLowerCase(keyget));
            
            int total = (index - keydex) % 26;
            total = (total<0)? total + 26 : total;
            
            sb = sb+ alphaL.charAt(total);
         }
         else{
            sb = sb + get;
         }
      }
      
      return sb;
   }
   
}

8 comments: