##
Shift

Posted in Cryptography by #care-crew

Shit cryptography is often called "Caesar cipher", cause he was one of the first users. It shifts elements of the public vocabulary.

In order to reveal the power of shift cryptography, one must think of A-Z as a ring.
We have 26 elements and after the last one "Z" the first one "A" comes again.
This is based on **modular arithmetic**. We assign each character a number. This can be done with ASCII. However the greatest common divsor of a and m must be 1 in order to have a valid ring.

//$a and $b are numbers that will be divided by modulo $m
$a = $b % $m;

Jones tells Jack that he will shift each Character by 21.
Jack can decrypt the message by shitting it backwards by 21.

The first step is to convert the plain text to numbers. This can be done with the ASCII table. Afterwards shift each Number by 21. Use modulo 127, cause the ASCII table got 127 different characters. Convert each shifted number back to Characters.
Jack receives the cipher text and converts it to numbers, shifts each number back by 21 and uses modulo 127 again. Finally he converts each number back to Characters. This allows him to read the plain text from Jones.

*Try to shift a plain text by 13 two time.*
You just discovered rot13.

What's more, we can shift via multiplying instead of adding.
In order to get an injective representation, we need to find a pair of numbers that got "1" as their Greatest Common Divisor.

gcd($a,$m) = 1; //otherwise the representation is not injective.
function ($x){
return ($a*$x) % $m;
}

Both shifts can be combined (affine crypto system)

encryption($x): ($a*$x + $b) % $m;*

*
The decryption is possible by using "gcd" from above.
**$s*$a+$t*$m = 1; //solve using gcd
decryption($x): $s*($x-$b) % $m;

Published at 2011-10-25, Updated at 2011-10-25

next: Vigenere Cryptosystem
prev: Permutation