maths and c++ 101

The other day I was talking to a friend of mine who is an art major. One way or another the topic of encryption came up. How I managed that is another story. This article, as I hope, will serve as an introduction to non-majors who has absolutely no exposure to this kind of materials.

Motivations

When datas are transmitted, most commonly over the internet or any large networks, it likely that the information will be seen by unintended parties. This is not a desirable effect but at the same time unavoidable without tremendous cost. To answer the need for confidentiality of data transmitting over networks we “encrypt” the data before transmitting.

Again..

Imagine networks as the roads. Any entity can stand on the side of public roads and observe the traffic on it, see what being transmitted, count how many cars (packets) of each type, when the road is busiest such and such.. Now our main characters here are Alice and Bob, they have the need to communicate constantly and privately. To avoid people seeing her messages when using the public road Alice can build a road from her place directly to Bob. This way any items sent from her to bob will be carried on this private road that no one else has access too. This would be much more secure and preferrable than using the public road, if not for the extra cost. Even worse when Alice now want to send messages to Cooper also. We can see building private roads for each entity you would like to communicate with is not a valid solution.

Reason Alice didn’t want to use the public roads is because people can read her message. Now if she can somehow send something totally unintelligible to Bob, then she wouldn’t mind people reading it. However at the receiving end, bob, through some procedures, must be able to turn the encrypted message back into something meaningful. If they can do this then she can use the public road as much as she wants since she is not afraid of people seeing what she is sending (because they wouldn’t understand). That is the very basic of encryption

The Shift Cipher:

I’ll introduce to you the Caesar Cipher, or Shift cipher. It works as follow. Each letter in the plain text will be replaced with another letter a few places away from it in the alphabet.

For example:

A -> C
B -> D
C -> E
D -> F
E -> G
F -> H
G -> I
H -> J
…

X -> Z
Y -> A
Z -> B

and so on.

Thus to send

HELLO THERE

you would send:

JGNNQ VJGTG

Here every letter is changed to the letter 2 places after it in the alphabet. For this cipher if you know the key k=2 you can encrypt message AND also decrypt (just move letters back 2 spaces). It is obvious that such a method is very insecure because there are only 26 possible keys. With little computational power one can easily attempt to decrypt with all 26 keys and will find one that is the correct key (this is the bruteforce attack).

But if no one know the key, then the ciphertext (the text created after the encryption process) would look totally unintelligible to a 3rd party and the communication is confidential.

And that is the very basic of data encryption.

Modulo 26

When encrypt and decrypt messages it is natural that we assign numbers to letters in the alphabet. ‘A’ would be 0 (zero), ‘B’ is 1, ‘C’ is 2, … , and ‘Z’ is 25. Now when shifting with key = 2. ‘Z’ will be shifted by 2 so it would be 25+2 = 27. But this wouldn’t make sense since we only have 26 letters (would need 28 characters to address the value 27). It is natural to apply modulo 26 to ‘Z’ =25 to give 1, or ‘B’.

we write

27 = 1 (mod 26)

26 here is called the modulo. “27 mod 26″ simply is the remainder you have after you divide the modulo into 27.

As you could imagine

27 = 2 (mod 25)

Brute-force (slowest) to find x mod n is to repeatedly subtract n from x until you get to a value that is smaller than n. Of course if x < n then x mod n is just x. Also n mod n = 0 for all valid n.

In C++ you can use the % operator to find remainder, however it does not always return a positive result. This is a simple implementation of the modulo function:

int mod(int x, int n)
{
if (0==n) return -1;
if (x<0) return (x+(-1)*(x/n)*n+n);
if (x<n) return x;
else
return x-(x/n)*n;
}