## How to

When solving these problems, learning by doing is much better than learning by reading. I encourage to you read only as far in the solution as you need, then trying to solve the problem. If you get stuck, try reading a little further. And of course, let me know if you find a better solution!

## Wednesday, March 14, 2012

### Ceasar Cipher

Problem:  Implement a Caesar cipher to encrypt and decrypt a string

char * caesarEncrypt(char * a, int key) {
...
}

char * caesarDecrypt(char * a, int key) {
...
}

Solution:  It's useful to know what a Caesar cipher is.  It is one of the earliest ciphers where The contents of a character set are shifted by a certain amount to create cipher text.

For example, the string:

"cat in the hat" shifted with a key of 2 becomes:  "ecv kp jcv"

Let's also assume that we'll use only the 128 characters in ASCII.

For the encrypt function, at its core this seems simple.  We can simply increment each character by the key value.  The only potential issue here is what do we do if we reach the end?  In this case, we want to roll over, which we can do with the mod operator.

Let's also assume that we will make a copy of the string to return the cipher text.  Putting this together, we get:

char * caesarEncrypt(char * a, int key) {
char * cipher;
int i;

cipher = strcpy(a);
if (cipher == null) return ERROR;

for (i = 0; i < cipher.length; i++) {
cipher[i] = (cipher[i] + key ) % 128;
}

return cipher;
}

Now, how to decrypt?  Well, it would seem that we could do the same thing in reverse -- simply reduce the value of each element by the key.  This almost works, but consider what happens when we go below 0.  We get negative, which doesn't really make sense in this char set.

There are lots of ways that we can deal with this with if statement, by consider how we can do something similar to the increment.  If we add 128 to each element and then take the % 128, we are guaranteed a positive number -- and it's elegant without lots of if statements.

Putting this together, we get:

char * caesarDecrypt(char * a, int key) {
char * plain;
int i;

plain = strcpy(a);
if (plain == null) return ERROR;

for (i = 0; i < plain.length; i++) {
plain[i] = (plain[i] - key + 128) % 128;
}

return plain;
}

This works too.  The algorithmic run time of both is O(n) since we have to look at each element in the string once.

Well, is this a good cipher?  Not at all!  It's simple, which is about all that you can say for it.  Julius Caesar supposedly used it in his private communications -- and it is well understood.  Truthfully, it's probably better to use no cipher than this one, as this has the appearance of security, with truly none.

/* Please let me know if you find any errors or alternate solutions.  Thank you, Noah */