Friday, September 26, 2008

N-byte symmetric key N-level encryption algorithm

Summary
This article describes an algorithm to encrypt data using a N-byte symmetric key. It is not based on any well-known algorithms.

The DES (64-bit) or AES (128/192/256-bit) algorithms have fixed key length. The encrypted byte array generated would have length in multiples of this key length. Any change in the input data byte would affect only that particular group of either 8 or 16 bytes. Rest of the bytes following the changed character's key-length number of bytes group would be unaffected.

In this algorithm, I have allowed the key to have any length. The key is used in circles to keep on encrypting the incoming bytes. I.e. if you have 10-byte key, the first byte would be encrypted with the first byte of the key, the second byte with the second and so on till tenth byte. After this, again the eleventh byte would be encrypted using the first byte of the key and so on. Also, each of the encrypted byte is dependent on the preceding encrypted byte also. So, change in a single byte of input data would cause the entire following encrypted byte stream to be totally different then what would have been earlier.

Also since the encryption logic depends on a single byte, using this algorithm Encrypted/Decrypted Input/Output streams can also be developed.


Illustration


Initialization
First we need to take a constant

final int ENC_CONST = 100;

This constant can be different for different implementations.
We also need to take a few variables
int _encLevel = 5;
String _encKey = "";
int _encKeyTotal = 0;
_encLevel and _encKey can have any value set by implementation, or in case of a library, a public setter can also be provided so its value can be changed at runtime.

_encLevel defines how many times a string will be encrypted over and over again. More value of _encLevel means it would be more complicated to decrypt the encrypted string without the key.
Whenever value of the _encKey is changed, the _encKeyTotal should be recalculated as per the following logic:
long lKeyTotal = 0;
for (int nIdx = 0; nIdx < _encKey.length(); nIdx++)
{
    lKeyTotal += _encKey.charAt(nIdx);
}
_encKeyTotal = (int)(lKeyTotal % Character.MAX_VALUE);
A typical value of the Character.MAX_VALUE would be 65535 (supporting unicode characters).

Encryption
String sValToEncrypt is a parameter passed to the encrypt subroutine.

Now, initialize a few variables,
char[] sAryValToEncrypt = sValToEncrypt.toCharArray();
int nLen = sValToEncrypt.length();
int nCh1 = 0, nCh2 = 0, nCh3 = 0;
int nEncKeyLen = _encKey.length();
char[] sRetStr = new char[nLen];

Now, run a loop for _encLevel times. This will keep on encrypting the string (first time the input string and then the encrypted string) number of times to make it more and more secure.

for (int nEncCtr = 0; nEncCtr < _encLevel; nEncCtr++)
{
    //Run a loop for nLen times (length of
    the string to be encrypted)
    for (int nChCtr = 0; nChCtr < nLen; nChCtr++)
    {
        //Take the current character in nCh1
        nCh1 = sAryValToEncrypt[nChCtr];
        //Calculate the encryption factor
        //based on one of the characters of
        //the Key and Key's checksum
        //One character from the key should
        //be selected based on the current
        //character's index
        nCh3 = nEncKeyLen > 0 ?
            _encKey.charAt(nChCtr % nEncKeyLen) +
            _encKeyTotal : 0;
        if (nChCtr > 0)
        {
            //From second character onwards,
            //calculate the encrypted character as
            //last encrypted character + current
            //character's encryption factor
            //modulus max character (65535) and add
            //this factor to the current character
            nCh1 += (nCh2 + nCh3) %
                Character.MAX_VALUE;
        }
        else
        {
            //For the first character, calculate
            //checksum of the string to be encrypted
            //(from second to the last character)
            long lDataCheckSum = 0;
            for (int k = 1; k < nLen; k++)
            {
                lDataCheckSum += sAryValToEncrypt[k];
            }
            //If length of the string is greater
            //than 1, add this factor to
            //the first character, or add a constant
            //factor ENC_CONST to the first character
            //Add length of the string and encryption
            //factor and then only
            //add remainder of this factor and
            //max character (65535) to the
            //current character
            nCh1 += (int) ((nLen + (nLen > 1 ? lDataCheckSum :
                ENC_CONST) + nCh3) % Character.MAX_VALUE);
        }
        //If the final encrypted character's value
        //exceeds max character value, reduce
        //it by that factor to make it lesser than 65535
        if (nCh1 >= Character.MAX_VALUE)
            nCh1 -= Character.MAX_VALUE;
        //Put the encrypted character in the Return character array
        sRetStr[nChCtr] = (char) nCh1;
        //Remember the encrypted character to give its
        //effect on the next character in the next
        //iteration of this loop
        nCh2 = nCh1;
    }
}
return new String(sAryValToEncrypt, 0, nLen);

Decryption
Decryption also works in the similar way. It processes the encrypted string in the reverse order (i.e. from last character to the first character).
Consider String sValToDecrypt as the subroutine parameter having previously encrypted string using the same key and same encryption level.
char[] sAryValToDecrypt = sValToDecrypt.toCharArray();
int nLen = sValToDecrypt.length();
int nCh1 = 0, nCh3 = 0;
int nEncKeyLen = _encKey.length();
char[] sRetStr = new char[nLen];
for (int nEncCtr = 0; nEncCtr < _encLevel; nEncCtr++)
{
    for (int nChCtr = nLen - 1; nChCtr >= 0; nChCtr--)
    {
        nCh1 = sAryValToDecrypt[nChCtr];
        nCh3 = nEncKeyLen > 0 ? _encKey.charAt(nChCtr % nEncKeyLen) +
            _encKeyTotal : 0;
        if (nChCtr > 0)
        {
            nCh1 -= (sAryValToDecrypt[nChCtr - 1] + nCh3)
                % Character.MAX_VALUE;
        }
        else
        {
            long lDataCheckSum = 0;
            for (int k = nLen - 1; k > nChCtr; k--)
            {
                lDataCheckSum += sRetStr[k];
            }
            nCh1 -= (int) ((nLen + (nLen > 1 ?
                lDataCheckSum : ENC_CONST) + nCh3) %
                Character.MAX_VALUE);
        }
        if (nCh1 < Character.MIN_VALUE)
            nCh1 += Character.MAX_VALUE;
        sRetStr[nChCtr] = (char) nCh1;
    }
    System.arraycopy(sRetStr, 0, sAryValToDecrypt, 0, nLen);
}
return new String(sAryValToDecrypt, 0, nLen);

Performance
The algorithm is pretty optimized. The performance depends on the length of the string to be encrypted and the encryption level. The key also makes a difference, but not much.

Java implementation of this algorithm and taking into consideration the string "My name is Ishan" and with low encryption levels (upto 2000) it hardly takes 10 milliseconds. With encryption level of 100,000 also it takes only 70 milliseconds to encrypt / decrypt. Normally, decryption takes slightly more time as compared to encryption. This was tested on a Virtual Machine installed on a Core2Duo E4500 CPU @ 2.2GHz with 2 GB RAM - Windows Vista Home Basic (allocated 1GB to the guest OS - Windows XP SP2).

Examples
Following are some example encryptions generated using this algorithm

Example 1
Source String = "My name is Ishan"
Key = "Ishan"
Encryption Level = 10
Encrypted String (series of unicode hex characters) =
0x68db 0x4bc5 0x87f6 0x9c15 0xf8ef 0xec69 0xfe85 0x5a58
0x6293 0x236b 0x1707 0x9ecd 0x9be7 0xddfa 0x8549 0x1aa2

Example 2
Source String = "My name is Ishan"
Key = "Ishan"
Encryption Level = 15
Encrypted String (series of unicode hex characters) =
0xf379 0x5af5 0xafec 0x8d9d 0x72e1 0xafe0 0x68bf 0xf087
0x2f05 0xc696 0x2c81 0x4be2 0x222b 0xa061 0x32d3 0xdcff
Just by changing the encryption level from 10 to 15 makes the encrypted string totally different.

Example 3
Source String = "My name is Ishan"
Key = "Ishan1"
Encryption Level = 15
Encrypted String (series of unicode hex characters) =
0x32ec 0x0a33 0xece9 0x0310 0xdabc 0x3bd6 0x32a7 0xf438
0x7992 0x6bb1 0x29b0 0xb7e9 0x139c 0x3e3d 0xdf86 0x791c
Just by adding a single character at the end of the key, but keeping the encryption level the same also makes a huge difference in the final encrypted string.

This makes this algorithm highly difficult to break.

Example 4
Source String = "My name is Ishan"
Key = "Ishan1"
Encryption Level = 100000
Encrypted String (series of unicode hex characters) =
0xea92 0xa551 0xc88a 0xecb3 0x4cdb 0xb22e 0xf453 0xf322
0xce4f 0xdd75 0x7c64 0x648d 0xd7ec 0x2243 0x054a 0xa88b
Time taken to encrypt = approx 70 mSec
Time taken to decrypt = approx 70 mSec

Some stuff for Crackers
Here are some example encrypted strings. Try to extract the original string out of this. The encrypted examples are provided in the form of a series of unicode hex characters.

Example 1
0x6332 0xdaaf 0x4a08 0xd14d 0x6fc5 0x53bb 0x2c3e 0x9b6c
0x0991 0xadb1 0x183b 0xc0a2 0x9e63 0xe839 0xf5be 0xaf91
0x1f45 0x1e61 0xdd1e 0x5bf1 0x44f1 0x30dd 0x7384 0x2a72
0x3198 0xc30b 0x59e4 0x5144 0xc0d5 0xd3bc 0xd86b 0xb211
0x690c 0xf813 0xf585 0x0638 0x1e28 0xcc3c 0xd20a 0x9a9b
0x60be 0x469a 0x8e65 0x9156 0xabb4 0x11b0 0x6e5b 0x5425
0x6f2f 0xc57c 0x73df 0x2669 0x2c2b 0xdf49 0x1578 0xbf6d
0x8a16 0x355e 0x9d8c 0xf7db 0x7ac2 0xf3a8 0x2a5c 0x52c2
0x4c19 0x6885 0x6081 0x59e3 0x662b 0xa166 0x7c75 0xa40d
0x884f 0x30df

Example 2
0x8488 0x9789 0xaaf3 0x0852 0xeba9 0xcea4 0x1b47 0xc1e9
0xb357 0x22d7 0xa877 0x5d40 0x9623 0x675c 0x1481 0x64ae
0x4a25 0x832d 0x32ff 0x85c6 0x0f4a 0x46b2 0xa5cd 0xfb57
0x1913 0xd13f 0x034c 0xf6f2 0xa980 0xa89d 0xd63e 0x2a4b
0x6257 0xe5d3 0xcf04 0xe930 0x70a0 0x9c85 0xdf46 0x9ee8
0xa643 0x84da 0xb1cb 0x5d64 0x8dfe 0x92cd 0x67ba 0x593c
0x7087 0x7d66 0x734e 0x6502 0x5613 0x9200 0x9f86 0xef10
0x60c0 0x2766 0x6565 0xc55a 0x78c5 0xdbd0 0xa7e6 0x74fd
0xcde0 0x2a58 0xb610 0x06b1 0xc1ac 0x6773 0x825a 0x799d
0x9b28 0xf3eb 0x496d 0xf65c 0xd9c7 0x93e8 0x9923

Followers