Caesar, Shift and Affine Ciphers
Download
Report
Transcript Caesar, Shift and Affine Ciphers
CSCI 391: Practical
Cryptology
Substitution Monoalphabetic
Ciphers
Julius Caesar Cipher
The letters of the alphabet are coded as:
A B C D ... Z
0 1 2 3 ... 25
Caesar Cipher
One of the simplest examples of a substitution or shift
cipher.
Entire alphabet is shifted (or rotated) by 3 letters. The last
three letters are shifted to the first three letters of the
alphabet.
Used by Julius Caesar to communicate with his army
Caesar is considered to be one of the first persons to have
ever employed encryption for the sake of securing
messages
Caesar Cipher
• Caesar decided that shifting each letter in
the message would be his standard
algorithm
• Caesar simply replaced each letter in a
message with the letter that is three places
further down the alphabet - encryption
A
B C D E F G H I
D
E F G H I
J K L M N O P Q R S T U V W X Y Z
J K L M N O P Q R S T U V WX Y Z A B C
Caesar Cipher
Ciphertext may be deciphered or decrypted by
replacing each letter by the third previous letter.
Example:
Plaintext: dog
Ciphertext: GRJ
Example:
Ciphertext: BDQD
Plaintext: yana
Caesar Cipher
Remember: we think of each letter as
corresponding to a number from 0 to 25
To encrypt, we map numbers according to
C = ( P + 3 )(mod 26)
To decrypt, we map numbers according to
P = (C – 3) (mod 26)
General Shift Cipher
To encrypt: C = (P + K) (mod 26), K is the KEY
To decrypt: P = (C - K) (mod 26), K is the SAME
KEY
The sender and receiver of the messages agree in
advance upon a key – a shared secret
Brute Force Attack – the naive but determined
adversary to start trying every possible shifting,
and wait to see which message seemed to make
sense
Shift Cipher Attack Example
RCC FW XRLC ZJ UZMZUVU ZEKF KYIVV GRIKJ
Shift back by 01: qbb ev wqkb yi tylytut ydje jxhuu fqhji
(P = C – 1 )(mod 26)), a is encrypted by B, b is encrypted
by C, etc.)
Shift back by 02: paa du vpja xh sxkxsts xcid iwgtt epgih
(P = (C – 2) (mod 26)), a is encrypted by C, b is encrypted
by D, etc)
…….
Shift back by 17: all of gaul is divided into three parts
Modular Arithmetic
Division Principle Definition:
Let m be a positive integer and let b be any integer.
Then there is exactly one pair of integers q and r satisfying
0 ≤ r < m, such that b = q* m + r
q is called quotient, q = b/m
r is called a remainder, r = b % m
examples:
17 = 3*5 + 2 (b = 17, m=5, q = 3, r = 2) , 12 = 3*4 + 0,
-8 = -3*3 + 1 (b = -8, m = 2, q = -3, r = 1)
Modular Arithmetic
If b is a positive number, the following
simple rule can be applied:
If r = b % m, then m – r = -b % m
Examples:
17 % 5 = 2 and -17 % 5 = 5 – 2 = 3, (-17 = -4*5 + 3)
8 % 3 = 2 and -8 % 3 = 3 – 2 = 1 (-8 = -3*3 + 1)
Practice:
-24 % 5 = ?
-13 % 2 =
Modular Arithmetic
Let m be a positive integer (the modulus of
our arithmetic).
We say that two integers a and b are
congruent modulo m if b - a is evenly
divisible by m and we write a ≡ b (mod m).
Examples:
3 ≡ 3 (mod 10), - 6 ≡ 4 (mod 10)
we write a ≡ b (mod m).
Examples:
3 ≡ 3 (mod 10), - 6 ≡ 4 (mod 10)
Affine Cipher
To encrypt: C = (AP + B) (mod 26)
A and B are KEYS.
A is relatively prime to 26
0 ≤ B ≤ 25
To decrypt: P = A-1 (C - B) (mod 26)
A-1 is multiplicative inverse of A mod 26
There are 12 choices for A, and 26 for B, giving a total of
12*26 = 312 transformations of this type.
Decimation Cipher: C = A P (mod 26) (case B = 0)
we write a ≡ b (mod m).
Examples:
3 ≡ 3 (mod 10), - 6 ≡ 4 (mod 10)
Multiplicative Inverse
Multiplicative inverse of an integer A modulo M is an integer D such
that AD ≡ 1(mod M)
Solution exists if and only if (A, M) = 1, means A and M are relatively
prime.
We denote multiplicative inverse of A by A-1
Examples:
2-1 = 3 (mod 5)
3 is a multiplicative inverse of 2 (mod 5)
5-1 = 21 (mod 26)
21 is a multiplicative inverse of 5 (mod 26)