Transcript Introduction to Cryptology

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*2 + 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*2 + 1)
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 = (AP + 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 AD ≡ 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)