The Scramble-Anagram Algorithm

Introduction

The Scramble-Anagram algorithm performs an encryption by changing the position of the bytes inside an array of bytes, using a rule based on a password. Of course, it can be applied also on strings or other kind of data; I chose byte arrays because they are versatile, and can be easily converted to/from strings and can also be easily read from files.

I developed this algorithm while thinking about a way to overcome the weakness of block-cypher algorithms (like, for example, Rijndael, that is used for AES), when cyphering files. I wonder if this algorithm already exists under a different name... (if not, then I'll have to change this name with a more beautiful one).

Algorithm Description

The algorithm needs two input byte arrays: cleardata and password, and returns one byte array (called, from here on: output). The input byte array (cleardata) is read twice, from the start (byte 0) to the end, one byte at a time; at the same time the password is read, one BIT at a time, so that, for every byte in the cleardata, we have a corresponding BIT in the password (should the password byte array be smaller than the cleardata, then we loop over the password to get the corresponding bit; i.e., in other words: position of the BIT in the password = position of the byte in the cleardata MODULO password length; or, in formula words: bitpositioninpassword = bytepositionincleardata % password.length;

Now, we can start writing the output file.

While reading the cleardata the first time, one byte at a time, we add that byte to the output IF the corresponding bit in the password is 1; Then we read again the cleardata for the second time, one byte at a time, and we add that byte to the output IF the corresponding bit in the password is 0; (there are other ways to do this, even with one single pass, but this method seems the easiest to understand).

So, a first part of the output will contain the cleardata bytes corresponding to the ones in the password, while a second part of the output will contain the cleardata bytes corresponding to the zeros in the password.

Using the Code

The algorithm has been implemented here with an encoding and a decoding function, usable as extensions of byte arrays, i.e., usage:

byte[] mydata; byte[] mypass;
// here: allocate and set or read the two arrays
byte[] myoutput = mydata.Cry_ScrambleByteRightEnc(mypass);

The two main functions to ecode/decode to/from an anagram, operating on bytes, can be found in the code below (Cry_ScrambleByteRightEnc, Cry_ScrambleByteRightDec).

The same algorithm can be easily modified to move the BITs of the cleardata, instead of the bytes. The output would, of course, not be an anagram, and it would be more difficult to decode if the password is not known; and it would run slower than the original one. For this implementation, see the functions Cry_ScrambleBitRightEnc, Cry_ScrambleBitRightDec.

public static class ByteArrayExtensions
{
const int bitsinbyte = 8;

public static byte[] Cry_ScrambleByteRightEnc(this byte[] cleardata, byte[] password)
    {
    long cdlen = cleardata.LongLength;
    byte[] cryptdata = new byte[cdlen];
    // first loop: fill crypt array with bytes from cleardata 
    // corresponding to the '1' in passwords bit
    long ci = 0;
    for (long b = cdlen - 1; b >= 0; b--)
        {
        if (password.GetBitR(b))
            {
            cryptdata[ci] = cleardata[b];
            ci++;
            }
        }
    // second loop: fill crypt array with bytes from cleardata 
    // corresponding to the '0' in passwords bit
    for (long b = cdlen - 1; b >= 0; b--)
        {
        if (!password.GetBitR(b))
            {
            cryptdata[ci] = cleardata[b];
            ci++;
            }
        }
    return cryptdata;
    }

public static byte[] Cry_ScrambleByteRightDec(this byte[] cryptdata, byte[] password)
    {
    long cdlen = cryptdata.LongLength;
    byte[] cleardata = new byte[cdlen];
    long ci = 0;
    for (long b = cdlen - 1; b >= 0; b--)
        {
        if (password.GetBitR(b))
            {
            cleardata[b] = cryptdata[ci];
            ci++;
            }
        }
    for (long b = cdlen - 1; b >= 0; b--)
        {
        if (!password.GetBitR(b))
            {
            cleardata[b] = cryptdata[ci];
            ci++;
            }
        }
    return cleardata;
    }

// --------------------------------------------------------------------------------------

public static byte[] Cry_ScrambleBitRightEnc(this byte[] cleardata, byte[] password)
    {
    long cdlen = cleardata.LongLength;
    byte[] cryptdata = new byte[cdlen];
    // first loop: fill crypt array with bits from cleardata 
    // corresponding to the '1' in passwords bit
    long ci = 0;

    for (long b = cdlen * bitsinbyte - 1; b >= 0; b--)
        {
        if (password.GetBitR(b))
            {
            SetBitR(cryptdata, ci, cleardata.GetBitR(b));
            ci++;
            }
        }
    // second loop: fill crypt array with bits from cleardata 
    // corresponding to the '0' in passwords bit
    for (long b = cdlen * bitsinbyte - 1; b >= 0; b--)
        {
        if (!password.GetBitR(b))
            {
            SetBitR(cryptdata, ci, cleardata.GetBitR(b));
            ci++;
            }
        }
    return cryptdata;
    }
public static byte[] Cry_ScrambleBitRightDec(this byte[] cryptdata, byte[] password)
    {
    long cdlen = cryptdata.LongLength;
    byte[] cleardata = new byte[cdlen];
    long ci = 0;

    for (long b = cdlen * bitsinbyte - 1; b >= 0; b--)
        {
        if (password.GetBitR(b))
            {
            SetBitR(cleardata, b, cryptdata.GetBitR(ci));
            ci++;
            }
        }
    for (long b = cdlen * bitsinbyte - 1; b >= 0; b--)
        {
        if (!password.GetBitR(b))
            {
            SetBitR(cleardata, b, cryptdata.GetBitR(ci));
            ci++;
            }
        }
    return cleardata;
    }

// -----------------------------------------------------------------------------------

public static bool GetBitR(this byte[] bytearray, long bit)
    {
    return ((bytearray[(bit / bitsinbyte) % bytearray.LongLength] >> 
            ((int)bit % bitsinbyte)) & 1) == 1;
    }

public static void SetBitR(byte[] bytearray, long bit, bool set)
    {
    long bytepos = bit / bitsinbyte;
    if (bytepos < bytearray.LongLength)
        {
        int bitpos = (int)bit % bitsinbyte;
        byte adder;
        if (set)
            {
            adder = (byte)(1 << bitpos);
            bytearray[bytepos] = (byte)(bytearray[bytepos] | adder);
            }
        else
            {
            adder = (byte)(byte.MaxValue ^ (byte)(1 << bitpos));
            bytearray[bytepos] = (byte)(bytearray[bytepos] & adder);
            }
        }
    }
}

Other Uses (Cryptography)

Anyway, aside using it for anagram-puzzles, this algorithm has (in my opinion) interesting applications in some kind of cryptography. Taken alone, it does not give a sufficient degree of security, since it does not change the cleardata bytes, but it only moves them. Even the bit version has a great weakness: the number of bits 1 is the same in the output and in the cleardata (the same is, of course, true for the bits 0). But, compared to the usual block-cipher alghoritms, it works on the whole input, not just on blocks of 16 or 32 bytes at a time; it means that, the bigger the input, the harder will be the decoding work (which means also that it would be very weak in stream cyphering, since the stream blocks are small). Combining the Scramble-Anagram with, for example, a Rijndael algorithm could give birth to a stronger cypher algorithm, that combines the good features of both algorithms.

The following sequence of operations (using the same password for every operation, and using the output of every operation as input for the following one) could be, for example, tried:

1. Scramble-Anagram byte
2. Scramble-Anagram BIT
3. Rijndael
4. Scramble-Anagram BIT
5. Scramble-Anagram byte

Could it be stronger than using a simple Rijndael? This question is for crypto analysts. Furthermore, to add more security, one could also put the aforementioned operations into a cycle and repeat those operations n times (each time using as input the output of the previous), giving (hopefully) a greater security with each repetition (and having also a greater cost in execution time).

History

• 02 December 2011 - First release