05 May 2015

Transposition cipher

Today's section will be devoted entirely to cryptology. Cryptology is the study of ciphers and the methods of breaking them. I will try to describe one of the simplest methods of encryption, including the way of breaking it. The text includes the attached sources of the program encrypting a specified text by means of transposition, as well as the source file of the program aimed at breaking the encrypted text. The need of information encryption is only a little younger than the information itself. The ways of hiding information in a seemingly incomprehensible text have been known to us for thousands of years. One of them is the transposition method. In order to clearly illustrate what this method is about, I will use some tables. However, at first, a few basic concepts need to be explained:

- Plaintext - the text that we want to hide and encrypt,
- Cryptogram - plaintext after encryption, usually difficult to understand text data (encrypted text),
- Encryption algorithm - a method that was used to create a cryptogram from the plaintext,
- Encryption key - the information necessary for the correct data decryption with the known algorithm, most guarded thing in cryptography.

The transposition method consists in shifting the characters of the plaintext in a specific way and according to specified key. The following example could best explain this:
- Plaintext - ‘How secure is the Windows operating system ?
- Encryption key - 12
- Cryptogram (depending on the encryption key) - ‘Hssso ywtos hptseeee rmcWa uit?rni edn og iw

Cipher window:


Cipher code:
#include < iostream >
#include < stdlib.h >
#include < fstream >

using namespace std;

int main()
    {  
    char sText[500] ;                  // plaintext buffer
    char sCrypt[500] ;                 // encrypted text buffer
    int iKey, iIndexT, iTextLenght ;   // key, plaintext index, plaintext lenght
    int iIndexC ;                      // encrypted text index
    ofstream bdCrypt ;                 // pointer to file with encrypted text

    for (iIndexT=0 ; iIndexT < 500 ; iIndexT++)
        sText[iIndexT] = 0 ;

    cout << "\t------------------------------------------" << endl ;
    cout << "\twww.FiveWithFour.blogspot.com" << endl ;
    cout << "\ttransposition cipher example (c++ version)" << endl ;
    cout << "\t++++++++++++++++++++++++++++++++++++++++++" << endl ;
    cout << "\tConditions:" << endl ;
    cout << "\tplaintext lenght < 500 chars" << endl ;
    cout << "\tencryption key < plaintext lenght" << endl ;
    cout << "\tencryption key must be an integer" << endl ;
    cout << "\t------------------------------------------" << endl ;
    cout << "\n\nEnter plaintext:" << endl ;

    gets(sText) ;

    cout << "\nEnter encryption key:\t" ;
    cin >> iKey ;
    cout << "\nPlaintext:\t\t" << sText << endl ;
    int iTextLenthTemp = strlen(sText) ;
    cout << "Plaintext lenght:\t" << iTextLenthTemp << " chars" ;

    if ((strlen(sText) % iKey) != 0)
        {
        int iAdd = (strlen(sText) % iKey) ;
        int iAddText = iKey - iAdd ; 
        char sAddText[iAddText] ;
        for (int i=0 ; i < iAddText ; i++)
            sText[iTextLenthTemp++] = 32 ;
        }  

    iIndexT = 0 ;
    iIndexC = 0 ;

    for (int i=0 ; i < iKey ; i++)
        {
        iIndexT = i ;
        while (sText[iIndexT] != 0)
            {
            sCrypt[iIndexC++] = sText[iIndexT] ;
            iIndexT += iKey ;
            }
        }

    iTextLenght = strlen(sText) ;
    sCrypt[iTextLenght] = 0 ;

    cout << "\n\nEncrypted text:\t\t" << sCrypt ;  
    cout << "\nEncrypted text lenght:\t" << strlen(sCrypt) << " chars" << endl ;

    bdCrypt.open("crypt.txt", ios::out) ;
    if (bdCrypt.fail())
        cout << "ERROR:\tCan't open file !!!" << endl ;
    else
        {  
        bdCrypt << sCrypt ;
        cout << "\n\nEnd of procedure - encrypted text saved in crypt.txt" << endl << endl ;
        bdCrypt.close() ;
        }  

    system("PAUSE") ;

    return 0 ;
    }        

Clearly, the cryptogram is difficult to read, and it is not easy to deduce the meaning of the plaintext. The transposition method works like follows:

- plaintext 'How secure is the Windows operating system ?' It consists of 44 characters that can be written in the matrix form (vector),
- encryption key - I chose the number 12, the operation of which made the cryptogram complex enough - it is hard to determine what the plaintext looks like on the basis of the cryptogram,
- transposition method encryption - consists in changing the order of the characters in a sentence. All the characters of the cryptogram occur in the plaintext only once. In brief, the transposition method is a simple mingling algorithm. In order to illustrate how to create a cryptogram of the plaintext with a given encryption key, I will use matrixes. The number of columns in the matrix is the same as the encryption key. This is what the transposition encryption is about - we enter the plaintext in the matrix along the rows of the matrix, and read the cryptogram column by column of the matrix. A very important element is to fill the empty places in the matrix so that:

 the length of the plaintext % encryption key = 0

If a few characters are missing in the matrix, it is best to write down at the end of it the SPACE characters, code 0x20 hex in the ASCII standard, which in turn will add invisible characters at the end of the plaintext. Before each encryption, please check that the remainder of the division of the length of the plaintext by the value of the encryption key is 0. It is a prerequisite for the proper decryption of the cryptogram.
By reading row by row we get plaintext, and by reading column by column, we get the cryptogram. The cryptogram contains additional spaces, which result from supplementing the last two fields of the matrix whose dimensions are 12x4 - that is 48 fields, and the plaintext contains 44 characters + 4 SPACE characters at the end of the text.


At first glance, the cryptogram seems complex and difficult to decrypt without knowing the key that the plaintext is encrypted with. The most important information we possess is the encryption algorithm and of course the cryptogram. These two are fully sufficient to decipher the cryptogram and get to know the plaintext. The case I present here is to familiarize the reader with simple encryption methods, in fact, cryptanalysts often do not have the whole cryptogram and do not know which algorithm was used to encrypt the plaintext. Even if they do know, what they deal with is not the transposition algorithm that is described here. The strength of the algorithm described here is 1 in the scale of 1 to 100. The range of possible keys is theoretically unlimited, but in practice the encryption key may refer to numbers in the range of:

 the length of the plaintext - 2

It makes no sense to use the key whose value is 1 or a key whose value equals the length of the plaintext. In practice, the plaintext would not be encrypted at all. It is clear that this type of algorithm is not very ‘powerful’, but it is simple to implement and makes longer texts complex enough. An additional advantage is that the creation of the cryptogram may start from a different point of the matrix than the one described here. A trained eye can easily determine the encryption key, but this not what I would like to write about.
While preparing this material, I thought it would be a good idea to write an encryption program and a program breaking the transposition algorithm. I wrote both programs using DevC++ (yes, I know DevC++ is 'old', but I wrote this tutorial 11 years ago) but, they constitute consoles that allow for practicing the correct functioning of the algorithm.
The encryptor enables to enter any text of a length of up to approx. 500 characters. During the implementation of the encryptor, I managed to avoid matrix operations, which will make it easier to understand the code. The program consists of a single function, several loops and conditions. Despite the seeming chaos, the code is readable and easy to trace.
It is not difficult to create a decryptor for this method of encryption. My task was to write a program that, based on a cryptogram, would return the plaintext and would find the key that was used to encrypt the information. In terms of cryptanalysis, the most effective method of security breaking is to try out the whole range of encryption keys - of course what I mean by that is symmetric algorithms, in which the encryption and decryption of information is performed by means of the same key. This method is known among crackers as a brute force and I presented it while breaking an unusual security written by Lukian. In the case of the presented transposition, the range of keys is rather small - about 500 keys, and there is no point in thinking about the optimization of the breaking algorithm. The cryptogram should be decrypted by trying out all possible keys until the screen displays a meaningful text that will constitute the plaintext. The source file is easy to read. The program consists of two functions, the main one and the decryption function which is called as many times as there are possible decryption keys. The console screen displays only the keys, the outcome of which:

 the length of the cryptogram % encryption key = 0

Brutal window:


Brutal code:
#include < iostream >
#include < stdlib.h >

using namespace std;

void fnTestKey(char*, int) ;

int main()
     {
     char sCrypt[500] ;      // crypted text from crypt.txt fiel
     int iCryptLenght = 0 ;  // encrypted text lenght
     int iKey = 0 ;          // encryption key
     FILE *bdCrypt ;         // pointer to file with encrypted text

     cout << "\t------------------------------------------" << endl ;
     cout << "\twww.FiveWithFour.blogspot.com" << endl ;
     cout << "\ttransposition brutal example (c++ version)" << endl ;
     cout << "\t++++++++++++++++++++++++++++++++++++++++++" << endl ;
     cout << "\tConditions:" << endl ;
     cout << "\tcrypt.txt file is needed" << endl ;
     cout << "\t------------------------------------------" << endl ;

     for (int i=0 ; i < 500 ; i++)
         sCrypt[i] = 0 ;   

     if ((bdCrypt = fopen("crypt.txt", "r")) == NULL)
         cout << "ERROR:\tCan't open file : crypt.txt !!!" << endl ;
     else
         {
         fgets(sCrypt, 500, bdCrypt) ;
         fclose(bdCrypt) ;
         }

     iCryptLenght = strlen(sCrypt) ;
     cout << "\nEncrypted text:\t\t" << sCrypt << endl ;
     cout << "Encrypted text lenght:\t" << iCryptLenght << endl << endl ;
     cout << "\nFind correct sentence:" << endl << endl ;
     for (int j=0 ; j < iCryptLenght ; j++)
         fnTestKey(sCrypt, ++iKey) ;
     cout << endl ;
     system("\nPAUSE");
     return 0;
     }

void fnTestKey(char sCryptTmp[500], int iKey) 
     {
     char sText[500] ;
     int iIndexC = 0 ;
     int iIndexT = 0 ;
     int iKeyTemp = 0 ;

     for (int i=0 ; i<500 ; i++)
         sText[i] = 0 ;

     for (int i=0 ; i < iKey ; i++)
         {
         iIndexC = i ;
         while(sCryptTmp[iIndexC] != 0)
             {
             sText[iIndexT++] = sCryptTmp[iIndexC] ;
             iIndexC += iKey ;
             }
         } 
     if ((strlen(sText) % iKey) == 0)
         {
         iKeyTemp = strlen(sText) / iKey ; 
         cout << "key:\t" << iKeyTemp << "\tdecrypted:\t" << sText << endl ;
         }   
     return ;
     }     


On this basis, one can perform optimizations of methods of cryptogram breaking, because as one can see, only 1/3 of the possible keys meet the condition. For us, this does not really matter, because the key range is small and the computer can do very well with all possible keys. The % character refers to the remainder of the division in C ++ syntax. It is difficult to write a code that would recognize the broken cryptogram for its reasonableness; therefore all possible solutions for the key substitution are provided so that the user could decide themselves which solution is plaintext. In fact, there are algorithms verifying the consistency of the decrypted cryptogram, and it is done so as to reduce the number of checked keys, which can sometimes be of a huge amount. Difficult encryption algorithms cannot be broken in one day, maybe in the future someone will come up with a better method than examining the whole encryption key range. I decided to describe a simple encryption algorithm and an effective method of its breaking.