4
\$\begingroup\$

I'm toying around with a Caesar cipher that supports keys. The cool thing about it is that, unlike most Caesar ciphers you see, it works with byte arrays, not just strings, so you can encode text as well as files and other data. Of course, if you're looking for true security, you wouldn't want Caesar encryption of any kind, but it's still fun to play with.

I am wondering if my method can be improved/optimized at all. I left comments explaining how specific parts work, but will provide additional details if needed.

public static class Caesar
{
    public static byte[] Encrypt(byte[] key, byte[] plaindata)
    {
        return Crypt(key, plaindata, 1);
    }

    public static byte[] Decrypt(byte[] key, byte[] cipherdata)
    {
        return Crypt(key, cipherdata, -1);
    }

    static byte[] Crypt(byte[] key, byte[] dataIn, int switcher)
    {
        //Initialize return array at same length as incoming array
        var dataOut = new byte[dataIn.Length];

        var i = 0;
        var u = 0;

        //Since we'll be iterating over each character in blocks the
        //length of the key, will use modulus to limit interations to
        //final full block and handle remainder in the second pass
        var mod = dataIn.Length % key.Length;

        //First pass: 
        for (
            ; 
            i < dataIn.Length - mod; //Stop at last block
            i = i + key.Length //Step through bytes in blocks of key length
            )
            //Inner iteration steps through byte array per each byte in key
            for (u = 0; u < key.Length; u++)
            {
                var c = dataIn[i + u];

                //This one's hard to explain. Caesar enryption is all about 
                //incrementing/decrementing bytes. Rather than increment by 1
                //for encryption and decrement by 1 for decryption, we'll
                //encrement/decrement by the current key byte value and
                //leverage .NET's unchecked mode to overflow the byte values.
                //Switcher will be 1 or -1 and multiplied by the current byte 
                //value to toggle it between positive and negative for to
                //encrypt or decrypt respectively.
                c = (byte)(c + (key[u] * switcher));
                dataOut[i + u] = c;
            }

        if (u == key.Length) u = 0;

        //Second pass: Iterate over the remaining bytes beyond the final block.
        for (; i < dataIn.Length; i++)
        {
            var c = dataIn[i];
            c = (byte)(c + (key[u] * switcher));
            dataOut[i] = c;
            u++;
        }

        return dataOut;
    }
}

Use it like this:

var correctKeyBytes = Encoding.UTF8.GetBytes("this_is_my_key");
var incorrectKeyBytes = Encoding.UTF8.GetBytes("hmmm.what.is.the.key");

var plaintext = "This is some text that I would like to encrypt.";

var cipherBytes = Caesar.Encrypt(correctKeyBytes, Encoding.UTF8.GetBytes(plaintext));

//Returns yNDS5n/S5n/g6MzQhe3Z4N2T09HU043Cf+LU7uDMid/I1Nh/4eh/0NPc5uHZ540=
var cipherText = Convert.ToBase64String(cipherBytes);

//Decrypting with key returns original string
plaintext = Encoding.UTF8.GetString(Caesar.Decrypt(correctKeyBytes, Convert.FromBase64String(cipherText)));

//Decrypting with incorrect key returns
//`ceyQ[~\u001el�c]Wyq{�(nXlf UQkl�l� l�`p\u001a�}\u001aWkoyt�p%
plaintext = Encoding.UTF8.GetString(Caesar.Decrypt(incorrectKeyBytes, Convert.FromBase64String(cipherText)));

I am using the two-pass method to avoid having to use if statements to determine the course of action relative to the current location in the byte array. It might be a little extra code, but seems more optimized that way.

BTW, here's very simple Caesar without keys to contrast between arbitrary byte transformation vs. the key-based byte transformation I used above:

public static class CaesarBasic
{
    public static byte[] Encrypt(byte[] plaindata)
    {
        return Crypt(plaindata, 1);
    }

    public static byte[] Decrypt(byte[] cipherdata)
    {
        return Crypt(cipherdata, -1);
    }

    static byte[] Crypt(byte[] dataIn, int switcher)
    {
        var dataOut = new byte[dataIn.Length];

        for (int i = 0; i < dataIn.Length; i++)
        {
            dataOut[i] = (byte)(dataIn[i] + (1 * switcher));
        }

        return dataOut;
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Jun 13 '18 at 20:45
3
\$\begingroup\$

You do not need to declare i and u outside the loop: to do this you need to change your code: u is useless here (it's always key.Length then you do not need to keep track of it) and i holds a value which might be calculated (pick the one you find more readable for i but absolutely drop u).

First of all I'd move the "encrypt block" code to a separate function: you're repeating the same code twice.

static ProcessBlock(byte[] output, byte[] input, byte[] key) { }

You added a comment to explain checked/unchecked behaviour however you assume that code is compiled as unchecked. It's a fragile assumption only documented in a comment deep inside a single function, many people prefer to develop in an checked environment and to release as unchecked. Some (nowadays) always use checked. If your code need an exact setting you can tell the compiler:

unchecked
{
    byte c = (byte)(dataIn[i + u] + (key[u] * switcher));
}

Your code will then work regardless compiler settings. If you focus on this line you can see few more things:

Maybe surprisingly in C# integer math is performed with int when operands are byte or short (and anyway switcher is int then promotion will happen even if it was not). What does it mean? That you do not need checked/unchecked at all because byte + byte won't ever overflow int and it might be done with a simple (byte)(value & 0xff) (note the & because checked cast will not simply drop bits but check the actual value). Not that it really matters but it's maybe nice to know.

On the same line you can also see that you do not need to declare c on a separate line (what for? I just need to watch up and down to understand what it is). Also it's recommended to avoid var for primitive types. More on this: all that code might be written into a single readable self-contained line. i, u, c...you're introducing too many single letter variables! I'd even introduce a separate function for this:

static byte CryptByte(byte input, byte key, int switcher)
    => unchecked ((byte)(input + key * switcher));

Do not add extra parenthesis, they make the expression to look more complicate than it is and standard math operators precedence does the job. Inside the loop you will then have:

dataOut[i + u] = Crypt(dataIn[i + u], key[u]);

That i + u really bothers me but in a previous step we already moved this code into a separate function then...

One more word about names. mod doesn't explain what it is, merely how it's calculated. It may be worthy to name it numberOfBlocks.


Now I will start to rewrite more of your code, I will do it step by step to show the reasoning (hoping I'll be clear enough). Be aware that I'm writing code here then there might be typos here and there, add proper tests to ensure it works as expected.

Can we rewrite that ugly nested loop? Let's start from the simple code you posted at the end. The "problem" is only to calculate the correct index to access key:

static byte[] Crypt(byte[] dataIn, byte[] key, int switcher)
{
    var dataOut = new byte[dataIn.Length];

    for (int i = 0; i < dataIn.Length; ++i)
    {
        int keyIndex = i % key.Length;
        dataOut[i] = unchecked((byte)(dataIn[i] + key[keyIndex] * switcher));
    }

    return dataOut;
}

Much simpler, maybe we're on the right track. Now let's add some validation, you can call those functions with invalid parameters and error messages won't be helpful without inspecting the code:

public static byte[] Encrypt(byte[] key, byte[] plainData)
{
    if  (key == null)
        throw new ArgumentNullException(nameof(key));

    if  (plainData == null)
        throw new ArgumentNullException(nameof(plainData));

    if (key.Length == 0)
        throw new ArgumentException("You must give an encryption key." nameof(key));

    return Crypt(plainData, key, 1);
}

All this said if performance aren't a measured issue you may greatly simplify your code with some LINQ. First of all generate indices for the key corresponding to each input byte:

var keyIndices = Enumerable.Range(0, dataIn.Length)
    .Select(x => x % keys.Length);

Here for simplicity I'm working with indices but you may produce values directly (anyway enumeration is lazy evaluated then you do not create a huge array with all the repeated values). These indices are the index of corresponding value of key for the value in dataIn with the same index.

Now match (zip) them with input values:

Enumerable.Range(0, DataIn.Length)
    .Zip(keyIndices, ProcessByte);

Zip() "Applies a specified function to the corresponding elements of two sequences, producing a sequence of the results.". Again enumeration is lazily evaluated then we do not create a possibly huge copy of anything.

Putting all together:

static IEnumerable<T> Crypt(byte[] input, byte[] key, int switcher)
{
    var keyIndices = Enumerable.Range(0, input.Length).Select(x => x %, keys.Length);
    return Enumerable.Range(0, input.Length).Zip(keyIndices, CryptByte);

    byte CryptByte(int inputIndex, int keyIndex)
        => unchecked ((byte)(input[inputIndex] + key[keyIndex] * switcher));
}

Convert.ToBase64String() has not an overload which accepts IEnumerable<byte> then if you need to always use them together you need to add a call to ToArray().

Do we need keyIndices? Actually we do not, let's simplify more, finally we have:

static IEnumerable<T> Crypt(byte[] input, byte[] key, int switcher)
{
    return Enumerable.Range(0, input.Length)
        .Select(i => unchecked ((byte)(input[i] + key[i % key.Length] * switcher)));
}

Performance

You seem to be extremely concerned about performance. First of all let's run a small benchmark to see the numbers (warm-up + average of 500 iterations, 2 MB input, 32 bytes key running on Intel i7-7600 @ 2.8 GHz, 20 GB RAM, Win10 64 bit, compiled in release):

                   Time [ms]    Difference [%]
Original                5                100
Simple for              8                140
LINQ                   36                623

The "simple for" (with modulus calculated inside the loop) seems to take 40% more time. Now let's put this ON CONTEXT. We're talking about 3 ms (for a pretty huge string). Does it matter? If you're encoding once some text you read from disk (or user typed) then answer is definitely: NO. It doesn't. If you sacrifice readability for performance where it's not required then you're making your code error-prone (see later) and more costly than it should be (I won't repeat these basic principles here, just Google them out).

On the other hand if you're encrypting a huge amount of big documents then 3 ms per file might make a noticeable difference (let's say 1000 documents, each one few megabytes...around 3 seconds). Is it enough to pay its price? If your answer is yes then we may think better about performance.

Is performance affected by key length? Marginally, running few tests (8, 16, 32, 128 bytes key length) we can see that values are pretty stable (below the 1 ms error which we can't improve without setting-up a much better benchmark).

Can we remove the modulus?

static byte[] Crypt(byte[] input, byte[] key, int switcher)
{
    var output = new byte[input.Length];

    int keyLength = key.Length - 1;
    for (int i = 0, k = 0; i < input.Length; ++i)
    {
        output[i] = unchecked((byte)(input[i] + key[k] * switcher));
        k = k == key.Length ? 0 : k + 1;
    }

    return output;
}

How does it perform?

                   Time [ms]    Difference [%]
Original                5                100
No modulus              5                100
Simple for              8                140

Definitely better, sometimes I measure 0.5 ms better (and sometimes worse) than the original version but it's below the threshold I consider an error of the measure. Code again gained in Clarity (let me repeat myself: 90% of the times it must be our goal). Targeting a specific architecture and a specific JIT compiler version (!!!) we may organise our code to produce a better assembly output (I'm thinking about that k = ...) but I'm pretty sure you don't want (or need) to go that far.

Just for completeness let's try with the input string you suggest (4 KB):

                   Time [us]
Original                10
No modulus              8
Simple for              14
LINQ                    64

Note that time is in microseconds. However we better measure the difference for all the 500 iterations because we're well below the error of the measure for this test. Once again: a theoretic 4 microseconds gain is worthy of a less readable code? Even LINQ version is practically acceptable. You may note a difference when processing more than 1,000,000 documents, not a common use-case and then we should probably point our efforts to minimise memory pressure.

However

We focused on the performance of the Crypt() function (which I still consider an useless exercise). Is it the bottleneck (what a terrible word when talking about performance) of our code? If you do not need a text output then you can skip this paragraph. If you do...

If we run the benchmark again to include the call Convert.ToBase64String() we see that:

                   Time [ms]    Difference [%]
Original                13                100
No modulus              13                100
Simple for              16                123

Most of the time is spent converting the byte array to a base64 string (and if you include Encoding.UTF8.GetBytes() the difference will reduce even more). What's the morale here? We were trying to optimise the wrong function. Convert.ToBase64String() is optimised and finely tuned but if we need to really squeeze performance we had to integrate its code in the Crypt() function directly: there is no need to create a possibly huge byte array that will be soon discarded and ad-hoc algorithm will definitely perform better: doing this you will better use your time to maximise the benefits.

Why so? Take u in the original code: as I said in the very first paragraph when trying to optimise for performance it's easier to introduce bugs or misleading code. u won't ever go above keys.Length then your second loop may effectively rewritten as:

//Second pass: Iterate over the remaining bytes beyond the final block.
for (int u=0; i < dataIn.Length; i++) { }

The other u may become local the the inner loop and that if (u == key.Length) may be simply dropped. This is a few lines snippet but this approach has terrible effects when code becomes big or complex.

\$\endgroup\$
  • \$\begingroup\$ If i and u are not declared outside they are not available to second pass. \$\endgroup\$ – paparazzo Jun 13 '18 at 12:30
  • \$\begingroup\$ @paparazzo u is used in the second pass but it shouldn't be (it's always key.Length and then set to 0). i...well...it has not to be (difference is known) but right. \$\endgroup\$ – Adriano Repetti Jun 13 '18 at 12:42
  • \$\begingroup\$ Great analysis and good call on the unchecked block. However, when I made most of these optimizations, my original code still performed 160% faster. I included your optimizations at the bottom of my question. Can you confirm I got them right based on not using LINQ? Edit: I am wondering if it's the use of the modulus operator within a loop. The main reason I went with the inner iteration was to mitigate excessive calculations and logic within an iteration. Will do some more research before making any determinations. \$\endgroup\$ – oscilatingcretin Jun 13 '18 at 20:37
  • \$\begingroup\$ I didn't benchmark this code but modulus inside such simple loop will definitely impact performance (as you measured). If (and only if) this snippet is performance critical then you may keep the loops and apply other small improvements (removing u from second part, for example). Also moving duplicated code to separate functions will not impact performance but increase readability. LINQ is definitely slower, avoid it if your target are pure performance (are they?) \$\endgroup\$ – Adriano Repetti Jun 13 '18 at 20:57
  • \$\begingroup\$ Performance should always be critical over readability if the gain is more than marginal. I also wouldn't be in favor of moving single lines of code into a separate function as this would generate stack overhead. Plus, if I keep my two passes then it means I will need to iterate slightly differently. This would require some code acrobatics to consolidate which I think would worsen readability. So, in the end, it seems my original code will remain unchanged, though I will make superficial changes such as to remove c and rename i and u to dataIndex and keyIndex. \$\endgroup\$ – oscilatingcretin Jun 13 '18 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.