CHAPTER 1



Classical Cryptography

1.1 Defining Terms:

Definition No.1:

Cryptology: The Study of secure communications, which encompasses both cryptography and cryptanalysis.

Channel

Information Source Info-Destination

Plaintext

Sealed Envelope

Definition No. 2:

Cryptography: Deals with the design of algorithms for encryption and decryption, intended to ensure the secrecy and/or authenticity of messages.

Definition No. 3:

Encryption: The Process of transforming plaintext into a disguised text (or cipher-text) is called encryption. The reverse process is called decryption.

Plaintext

Alice “See You” Bob

Plaintext: SEE YOU

Cipher Scheme: Replace each letter in the message forward by 5 positions in alphabet.

Ciphertext: XJJ DTZ “???”

Ciphertext

Alice “XJJ DTZ” Bob

Ciphertext (encrypted message) = message letter + 5 places forward in alphabet

Cipher Key

Uses the “decipher key”

XJJ DTZ SEE YOU

Ciphertext Plaintext

Bob

Decipher Text = each letter in ciphertext – 5 places in alphabet

Decipher Key

Definition No. 4:

Plaintext: The input to an encryption process (or function) or the output of a decryption function.

Definition No. 5:

Ciphertext: The output of an encryption function.

Definition No. 6:

Cryptanalysis: Deals with the breaking of a cipher to recover information.

Note 1: The ciphertext obtained by substituting one letter from alphabet with another one called “substitution (encryption) rule”. The number of places moving forward (or backward) in the alphabet called a “Key”.

Note 2: The “keyspace” (or the finite set of possible keys) for the above Caesar’s Substitution Cipher is the finite number of letters in alphabet, i.e., 26.

te 3: Substitution Cipher: Add to plain letter + (5 places)

Algorithm + Key

Note 4: Algorithm is the same; the only difference for getting differing cipher-text from the original plaintext is due only to the key (i.e., number of places advancing in alphabet).

Cryptosystem

.. Z A..

.. z a..

..n m..

..N M..

Caesar’s Cryptosystem for “Substitution Cipher”

Note 5: In this substitution cipher if you decipher “one letter” you have found the key! (i.e., the number of shifts in the alphabet).

Definition: (Mathematical Definition) A cryptosystem is a 5-tuple (P, C, K, E, D), where

1) P is a finite set of possible plaintexts

2) C is a finite set of possible ciphertexts

3) K, the key-space, is a finite set of possible keys

4) For each k (K, there exists an encryption rule such that ek ( E, and a corresponding decryption rule

dk (D, if x(P, then dk (ek (x)) = x

Exercise: Determine the 5-tuple (P, C, K, E, D) for the Caesar’s shift cipher.

1 Modular Arithmetic

The Caesar’s shift cipher is based on modular arithmetic.

Definition: Congruence - If a and b are integers and m is a positive integer,

then we write

a ( b (mod m) congruence

If m divides (b-a).

We say, “a is congruent to b modulo m”. m is called the modulus.

Example 1: Let m = 16. Find 11(13 modulus 16.

Solution: 11(13 = 143

143 = 8m+15 Remainder

11(13(mod 16) (15

Example 2: The key for a “shift cipher” is k = 11, and the plaintext is

“wewillmeetatmidnight”, find the ciphertext.

Solution:

Step-1 Set up the correspondence between alphabetic characters and residues modulo 26 as follows:

|A |B |C |D |E |F |G |H |

Step-3 Add 11 to each value, reducing each sum modulo 26:

7, 15, 7, 19, 22, 22, 23, 15, 15, 4, 11, 4, 23, 19, 14, 24,19, 17, 18, 4

Step 4 Convert the above sequence of integers to alphabetic characters by using the Table in Step 1.

“HPHTWWXPPELEXTOYTRSE”

Example 3: ( Exercise 1.1 on page 38 of Stinson Book)

(a) Evaluate (7503) mod 81

Solution:

a mod m ( b iff

a = k(m + b b ( (0, 1, …, m-1)

That is b is the remainder when m divides a:

7503 = k(81 + b

[pic] , remainder is b = 51

Thus,

7503 (mod 81) = 51

b) Evaluate ((7503) mod 81

Solution:

((7503) mod 81 = (51mod(81) = 30

Note: (7503 = (93(81+30 remainder

c) Evaluate 81 mod 7503

81 mod 7503 ( 81

d) Evaluate –81 mod 7503

–81 mod 7503 = (-7503 + 7421) mod 7503

Note: –81 = 7422 – 7503 = 7422

Remainder

1.2.1 Properties of Modular Arithmetic

Recall that given any positive integer n and any integer a, if we divide a by n, we get:

a=qn+r 0( r ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download