Click here to Skip to main content
Click here to Skip to main content

The Scramble-Anagram Algorithm

, 4 Dec 2011 GPL3
Rate this:
Please Sign up or sign in to vote.
Algorithm that performs an encryption in an anagram-like manner

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

License

This article, along with any associated source code and files, is licensed under The GNU General Public License (GPLv3)

Share

About the Author

Bruno Tabbia
Software Developer
Switzerland Switzerland
c#, Silverlight, C++, c, VBA, SQL, Oracle

Comments and Discussions

 
QuestionLack of analysis PinmemberLorenzo Gatti5-Dec-11 23:11 
AnswerRe: Lack of analysis Pinmembervictorbos6-Dec-11 4:47 
GeneralRe: Lack of analysis PinmemberBruno Tabbia6-Dec-11 8:42 
AnswerRe: Lack of analysis PinmemberBruno Tabbia6-Dec-11 8:37 
Well, more than a lack of analysis, there is an absence of that in this article: I am not a crypto analyst, and one of the reasons I published this article was to find someone who could give suggestions, regarding analysis, improvement, applications etc. I got this idea and then implemented it also because I wanted to share it with other peoples: it could be a new idea and maybe someone could find it useful.
 
Anyway, I have been probably too synthetic in my exposition, so I'll try to explain better here:
First, this alghorithm was intended for use mainly on files, and not on streams (see second paragraph of my article "when cyphering files", and the 'Other uses' when I wrote "very weak in stream cyphering"); streams are cyphered block by block, while files could be cyphered as a whole.
Second, this alghorithm was intended to be used together with an existing algorithm.
 
Now... cyphering a file as a whole block (instead of many 32byte blocks) is quite an effort, but the result would be more secure than cyphering it in blocks (that's why, I guess, in some coutries it is illegal to perform block cyphering with blocks longer than a given size (usually 128 or 256 bits)).
When trying to decrypt a cypher text without knowing the password, and using, for example, a brute force attack, we usually try to break the first blocks, and then, after finding a possible key, we try it on the remaining blocks. We do it because breaking one or two 32byte block is easier than breaking for example a whole book as the 'Divine Comedy' in a single block. So the idea was: how could I give the code breakers a hard time without adapting the Rijndael (or other block cypher) algorithm for longer block sizes?
If I scramble ALL the bytes in the file before and after applying the Rijndael, then I could obtain an encrypted file that is more difficult to break than a file encrypted using only the Rijndael Alghorithm (and scrambling the bytes is very fast, so it would be a very 'low cost' solution).
But I am not sure about that: that's why I wrote "Could it be stronger than using a simple Rijndael? This question is for crypto analysts.". I was hoping that someone with experience in the field could give me an 'expert' answer, or at least some advice.
I hope this answers also your second message "Applications?" (the weakness I spoke was the fact that R. algorithm uses small blocks (mainly 128 or 256 bits, sometimes 192)).
 
About the 'read the input twice': this is the easiest implementation, but I tried also
1) a single read, while writing to two output arrays and then joining them;
2) a single read writing to the output in non-sequential order, but this needs to count the ONEs in the password before starting the scramble (which, if you use directly the password provided by the user is quite fast, but if you use an algorithm to expand the password to the lenght of the file, then it could be slower).
 
Regarding the repeated scrambling with the same key, you are probably right: I said 'hopefully', and I hoped wrong. Probably in this case it would be interesting to add a new step, before the five operations mentioned in the article: expand the password and then divide it in N chunks (where N is the number of repetitions of the cycle) and then use a different chunk of password for every repetition. What is your opinion about this ?
 
And, please, let me know your thoughts about the rest.
Bye.
QuestionApplications? PinmemberLorenzo Gatti5-Dec-11 22:51 
AnswerRe: Applications? PinmemberBruno Tabbia6-Dec-11 8:45 
GeneralRe: Applications? PinmemberSeptimus Hedgehog11-Mar-14 7:45 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.141223.1 | Last Updated 4 Dec 2011
Article Copyright 2011 by Bruno Tabbia
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid