one time pad encryption

[adam2016]

hi guys,

I am studying for a cryptography exam,

not a particular programming question but it will relate as we will soon have to implement a one time pad algorithm but before that we need to understand how the math is done for this encryption,I can't seem to find any resources to help me understand this equation.

below is what is in one of the slides,the consistency equation,we are using this in conjunction with OTP(one time pad)

the equation is never explained,could someone try explain to me what is meant below and how the equation works

or have a link to a tutorial thanks

A cipher defined over (K,M,C)
is a pair of “efficient” algorithms (E, D) where
E: 𝒦 ∗ ℳ→ 𝒞, D: 𝒦 ∗ 𝒞 → ℳ
s.t. ∀m∈ ℳ, k ∈ 𝒦: D( k, E(k, m) ) = m
consistency
equation

here is the question I may be asked in the exam

Prove that the OTP satisfies the consistency equation?

[Repeater]

The consistency equation in question is this bit:

D( k, E(k, m) ) = m

This says:

Decrypt( key, Encrypt(key, message) ) = message

which says:

Having encrypted a message with a given key, decrypting it with the same key gives you back the original message.


So you need to prove that your OTP algorithm does this. Prove that with your OTP algorithm, the same key applied to encrypot and then decrypt a message will give you back the original message.

[jonnin]

you may want to look at some math sites online. This is written in the language of mathematical proofs, and if you can't read it, you can't answer your question! It should not be too hard to find a site that has the symbols and how to read it. I am a bit rusty on it.. st is such that ... you should have had some of this in your class and book but if you can't read it, proof language is what you need to research.

[Repeater]

As a simple example, if your OTP is a series of numbers, and your encryption algorithm operates on the letters a-z and space by assigning each a number:

SPACE = 0
a = 1
b = 2
...
z = 26

and your E is "add the next OTP number, and then apply modulus 27"

and your D is "subtract the next OTP number, and then apply modulus 27"

you "just" have to prove that

(( (letter_value + some_number) % 27) - some_number) % 27 == letter_value

i.e. given a letter value from 0 to 26, adding some_number and taking the % 27 (i.e. encrypting the letter ) , and then subtracting some_number and taking the % 27 (i.e. decrypting the letter) , will give you back the original letter value.


Hell, as a brutally simple encryption algorithm, if your E is just "add the next number from the OTP" and your D is "subtract the next number from the one time pad" you just need to prove that

x + some_number - some_number = x

[adam2016]

thanks so much guys,you never let me down =)

@repeater yes that actually makes sense now! we did an example in class without the formula and to encrypt the message then decrypt the message we used something similar but from a-z 0 - 25

and E was add each of the letters corresponding numerical value with the OTP's numerical value,if the value was greater than 26 subtract 26

then D was subtract 26 if value is a negative add 26 or something similar

thanks =)

btw can you recommend any good cipher sites which will give me some OTP challenges

[adam2016]

thanks guys for all the help here is my encrypt decrypt program using OTP,

works great,

but how would you encrypt if the OTP key is longer than the message?

#include <iostream>

using namespace std;


// E: K*M , D: K*C
// D(K,E(K,M)) = M

int getValue(char& key){

     switch(key){

 case 'a':
    return 0;
 case 'b':
    return 1;
 case 'c':
    return 2;
 case 'd':
    return 3;
 case 'e':
    return 4;
 case 'f':
    return 5;
 case 'g':
    return 6;
 case 'h':
    return 7;
 case 'i':
    return 8;
 case 'j':
    return 9;
 case 'k':
    return 10;
 case 'l':
    return 11;
 case 'm':
    return 12;
 case 'n':
    return 13;
 case 'o':
    return 14;
 case 'p':
    return 15;
 case 'q':
    return 16;
 case 'r':
    return 17;
 case 's':
    return 18;
 case 't':
    return 19;
 case 'u':
    return 20;
 case 'v':
    return 21;
 case 'w':
    return 22;
 case 'x':
    return 23;
 case 'y':
    return 24;
 case 'z':
    return 25;
     }
}

char getNumber(int num){

     switch(num){

 case 0:
    return 'a';
 case 1:
    return 'b';
 case 2:
    return 'c';
 case 3:
    return 'd';
 case 4:
    return 'e';
 case 5:
    return 'f';
 case 6:
    return 'g';
 case 7:
    return 'h';
 case 8:
    return 'i';
 case 9:
    return 'j';
 case 10:
    return 'k';
 case 11:
    return 'l';
 case 12:
    return 'm';
 case 13:
    return 'n';
 case 14:
    return 'o';
 case 15:
    return 'p';
 case 16:
    return 'q';
 case 17:
    return 'r';
 case 18:
    return 's';
 case 19:
    return 't';
 case 20:
    return 'u';
 case 21:
    return 'v';
 case 22:
    return 'w';
 case 23:
    return 'x';
 case 24:
    return 'y';
 case 25:
    return 'z';
     }
}

string encrypt(string& word,string& key){

   string cipher = "";
   int value = 0;
   int keyValue = 0;
   int newValue = 0;


   for(int i = 0; i < word.size(); i++){

       value = getValue(word.at(i));
       keyValue = getValue(key.at(i));
       newValue = value + keyValue;

       if(newValue >= 26){

          newValue = newValue - 26;
       }

       char letter = getNumber(newValue);
       string temp = string(1,letter);
       cipher.append(temp);
   }

   return cipher;
}

string decrypt(string& word,string& key){

   string cipher = "";
   int value = 0;
   int keyValue = 0;
   int newValue = 0;


   for(int i = 0; i < word.size(); i++){

       value = getValue(word.at(i));
       keyValue = getValue(key.at(i));
       newValue = value - keyValue;

       if(newValue < 0){

          newValue = newValue + 26;
       }

       char letter = getNumber(newValue);
       string temp = string(1,letter);
       cipher.append(temp);
   }

   return cipher;
}


int main()
{
    string key = "xdslkfjc";
    string word = "security";
    string enc = encrypt(word,key);
    string dec = decrypt(enc,key);

    cout << enc << endl;
    cout << dec << endl;

    return 0;
}

[Ganado]

how would you encrypt if the OTP key is longer than the message?

OTP requires the key length to be greater to or equal to the message length. Having a key that's longer than the message itself doesn't help anything, so you might as well just truncate the key. The other option would be to add buffer to the end of your message to match the key size.

getNumber and getValue

Please do know you don't need a case for every letter of the alphabet. chars are easily convertible to their corresponding int values, with a shift needed to make 'a' <==> 0.

// Example program
#include <iostream>
#include <string>

int getValue(char c)
{
    return static_cast<int>(c - 'a');
}

int main()
{
    std::cout << getValue('c') << std::endl; // 2
}

Quick interesting read:
https://www.khanacademy.org/computing/computer-science/cryptography/ciphers/a/xor-and-the-one-time-pad

[adam2016]

thanks Ganado :)

I figured there must be an easier way to write that =)

[Ganado]

Didn't catch your question before you deleted it, but maybe this will help in your C++ testing:

#include <string>
#include <iostream>
#include <iomanip>
#include <vector>
#include <cstdlib>

using byte = unsigned int;

std::vector<byte> AsciiToBytes(const std::string& ascii)
{
    std::vector<byte> bytes(ascii.length());
    for (size_t i = 0; i < ascii.length(); i++)
    {
        bytes[i] = static_cast<byte>(ascii[i]);
    }
    return bytes;
}

std::vector<byte> HexToBytes(const std::string& hex)
{
    if (hex.length() % 2 != 0)
        std::cout << "Warning: Odd length input" << std::endl;
    
    std::vector<byte> bytes(hex.length() / 2);
    for (size_t i = 0; i < hex.length(); i+=2)
    {
        std::string byte_str = hex.substr(i, 2);
        byte b = static_cast<byte>(std::stoul(byte_str, nullptr, 16));
        bytes[i/2] = b;
    }
    return bytes;
}

std::string BytesToHex(const std::vector<byte>& bytes)
{
    std::ostringstream iss;
    for (size_t i = 0; i < bytes.size(); i++)
    {
        byte c = bytes[i];
        if (c < 16) // poor man's fancy formatting since I don't feel like looking up setw
            iss << '0';
        iss << std::hex << c;
    }
    return iss.str();
}

std::string BytesToAscii(const std::vector<byte>& bytes)
{
    std::ostringstream iss;
    for (size_t i = 0; i < bytes.size(); i++)
    {
        iss << (char)bytes[i];
    }
    return iss.str();
}

// Assume same length...
std::vector<byte> xor_bytes(const std::vector<byte>&  a, const std::vector<byte>& b)
{
    if (a.size() != b.size())
    {
        std::cout << "xor_bytes error" << std::endl;
    }
    
    std::vector<byte> bytes(a.size());
    for (size_t i = 0; i < a.size(); i++)
    {
        bytes[i] = a[i] ^ b[i];
    }
    return bytes;
}

std::ostream& operator<<(std::ostream& os, const std::vector<byte>& bytes)
{
    if (bytes.size() == 0)
        return os;
    
    for (size_t i = 0; i < bytes.size()-1; i++)
        os << std::hex << (int)bytes[i] << " ";
    os << bytes.back();
    return os;
}

int main()
{
    std::string plain = "attack";
    std::string key   = "abcdef"; // should be randomly generated.
                                  // random generation can be the weak-point of OTP...
                                  
    // print plaintext
    std::cout << plain << "\n";
    
    std::vector<byte> plain_bytes  = AsciiToBytes(plain);
    std::vector<byte> key_bytes    = AsciiToBytes(key);
    std::vector<byte> cipher_bytes = xor_bytes(plain_bytes, key_bytes);
    std::string cipher = BytesToAscii(cipher_bytes);
    
    // print cipher
    std::cout << BytesToHex(cipher_bytes) << "\n";
    
    // change something
    cipher_bytes[1] = 17;
    
    // convert back...
    plain_bytes = xor_bytes(cipher_bytes, key_bytes);
    plain = BytesToAscii(plain_bytes);
    
    // print plaintext
    std::cout << plain << std::endl;

}

Note: Not thoroughly checked for bad input or other formatting/input-related bugs.

attack
00161705060d
astack

[jonnin]

xor is your friend. its easy to prove that its self reversing, and its almost always a cpu circuit / instruction of the highest performance, and you can do 8 bytes at a time on a 64 bit computer.