ComputerSecurity-3.ppt this is for students

Computer security

1. Introduction To Ciphers
Computer Security-3
A crypto system should be secure even if the attacker knows all the
details with the exception of the secret key.

2. Classical Cipher Algorithms
•Two basic methods:
–Substitution Ciphers
•Mono-alphabetic ciphers 
uses fixed
substitution over the entire message.
•Polyalphabetic ciphers  
uses a number of
substitutions at different positions in the
message
–Transpositions Ciphers
•Columnar Transposition

3. Mono-alphabetic Substitution Ciphers
•Each letter is translated or substituted by a fixed letter
after it in the alphabet.
•E.g. Caesar Cipher uses a shift 3.
•The plaintext letter pi is encipher as ciphered letter ci by
the rule.
Encryption: c
i
= E(p
i
) = (p
i
+ 3) mod 26
Decryption: p
i = D(c
i) = (c
i - 3) mod 26
Plaintext MEET ME AFTER THE TOGA PARTY
Ciphertext phhw ph diwhu wkh wrjd sduwb

4. Shift Cipher
It is a type of substitution
 
cipher 
in which each
letter in the plaintext is replaced by a letter some
fixed number of positions down the alphabet.
Key - k
c
i = (p
i + k) mod (26)
p
i = (c
i– k) mod (26)
Eg: K=5
Encryption: Decryption:

6. Home Work
•Encrypt the message MATH with the shift cipher with 4 as the
key.
•Encrypt the message CRYPTO with the shift cipher with 6 as the
key.
•The message QIIX PEXIV was encrypted using the shift cipher
with 4 as the key. Decrypt the message.
•The message SKKZ NKXK was encrypted using the shift cipher
with 6 as the key.

7. Affine Ciphers
•The affine cipher works through a combination
of modular multiplication and modular
addition.
• To encrypt a plaintext letter with a key given by
a pair of numbers (a; b),
E(x) = y = (ax+b) mod (26)
D(y)= x = a
-1
(y-b) mod (26)

8. Affine Cipher
•Let's see how this works when encrypting the
message MEET AT TEN with the affine cipher,
using the key (3; 10):
•Encryption

9. Modulo Inverse
where
 
a
−1
 
is the 
modular multiplicative
inverse 
of 
a modulo m. I.e., it satisfies the
equation.
1= a a
−1
mod m
Example
1 = 3.9 mod 26
2= 5.21 mod 26
Multiplicative inverses modulo 26: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, and 25,
whose inverses are 1, 9, 21, 15, 3, 19, 7, 23, 11, 5, 17, and 25, respectively.
The numbers which have no inverse modulo 26 are
0, 2, 4, 6, 8, 10, 12, 13, 14, 16, 18, 20, 22, and 24.

10. Affine Ciphers
Decryption
Y= u w w p k p p w x
20 22 22 15 10 15 15 22 23
X= 9(y-10) mod 26
12 4 4 19 0 19 19 4 13
M E E T A T T E N

11. Home Work
•Encrypt the message MATHI SFUN using the
affine cipher with key (7; 11).
•Encrypt the message CRYPT OISFU N with the
affine cipher with (11; 15) as a key.
•Decrypt the message OAAXG XLCSX YD, which
was encrypted with the affine cipher using (5;
6) as a key.

12. Other Mono-alphabetic Substitutions
•Simple substitution with key word: use a key, a word that
controls the enciphering
•If sender and receiver agree on a keyword then a simple
substitution can be generated from that keyword.
•Consider the key word DEERHOOF. First write the word
without letter repetitions DERHOF. Place this at the beginning
of the table and then proceed alphabetically to fill in the rest
Plaintext A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Ciphertext w o r d a b c e f g h i j k l m n p q s t u v x y z

13. Cryptanalysis of the mono-alphabetic
substitution Cipher
•Suppose you are given the following Ciphertext message
wklv phvvdjh lv qrw wrr kdug wr euhdn
1.There is a strong clue in the repeated r of the word wrr.
2.Common words see and too. Less common add, odd, off.
3.And two letter word wr., first two letters of the three letter
word also form a two letter word: to
4.English has relatively few small words, such as am, is, to, be,
he, we, and, are, you, she, and so on. Therefore, one way to
attack this problem and break the encryption is to substitute
known short words at appropriate places in the ciphertext
until you have something that seems to be meaningful.

14. Cryptanalysis of the mono-alphabetic Cipher

15. •The important thing to notice from this
example is that if we can guess just one letter
of the plaintext correctly, we can break a
whole message encrypted with the shift
Cipher.
It's clear that the spacing of a message already gives lots of
information which can be used to break it. For this reason, encoded
messages have traditionally been written without their original
spacing so that someone trying to break the code can't use this
information.

16. Home Work
Break these shift ciphers:
(a) PAXG LAHNEW B KXMNKG
(b) QUCN ZIL U JBIHY WUFF
(c) GUR ENOOVG PENJYRQ BHG BS VGF UBYR
(Hint: what three letter words are likely to
appear at the beginning of an English sentence?)

17. Cryptanalysis of Monoalphabetic Ciphers
•Short words, words with repeated patterns, and
common initial and final letters all give clues for
guessing the permutation.
• A lot like working crossword puzzle
• try a guess
• continue to work to substantiate that guess
until you have all the words in place, or until
you reach a contradiction.
• we can use more advanced technique
• frequency distribution

18. Frequency Analysis – Mono-substitution cipher
Relative frequencies of characters in English text
The methodology behind frequency analysis relies on the fact that
in any language, each letter has its own personality. 
"E" is the most common letter in English,
appearing about 12% of the time. The next
most common letter is "T" at 9%.

19. •Ciphertext
hqfubswlrqlvdphdqvridwwdlqlqjvhfxuh
frpsxwdxlrqryhulqvhfxuhfkdqqhovebxvlqj
hqfubswlrq zh glvjxlvh wkhphvvdjh vr wkdw
hyhqliwkhwudqvplvvlrqlvglyhuwhg whk phvvdjh
zloo qrwehuhyhdohg

20. •h may be one of e, a, i, o, etc
•Rule
h -> e, d ->a, l ->i, r -> o
•Results
– Ciphertext
hqfubswlrq lv d phdqv ri dwwdlqlqj vhfxuh…
– Plaintext
ENCRYPTION IS A MEANS OF ATTAINING
SECURE

21. Ex:
An affine Caesar cipher, has the following form:
For each plaintext letter p, substitute the
ciphertext letter: c = (ap + b) mod 26.
A ciphertext has been generated with an affine
cipher. The most frequent letter of the
ciphertext is ‘b’, and the second most frequent
letter of the ciphertext is ‘u’. Break this code
(Assume that the most frequent plaintext letter
is e and the second most frequent letter is t).

22. (ap+ b ) mod 26 = c
4a+b mod 26 = 1
19a+b mod 26 = 20
15a mod 26 =19
=> a=3
12+b mod 26= 1
=>b=15

23. Polyalphabetic Substitution Cipher
•Weakness of mono-alphabetic ciphers
– The major weakness of the cipher is that each plaintext
symbol always maps to the same ciphertext symbol.
-Their frequency distribution reflects the distribution of the
underlying alphabet.
-If an analyst who deduce the transformation of few letters can
also predict the remaining.
• Polyalphabetic substitution cipher
– one way to flatten the distribution
– to combine distributions that are high with ones that are low
e.g T is sometimes enciphered as ‘a’ and sometimes as ‘b’

24. One-Time Pads
•A one-time pad is sometimes considered the perfect
cipher.
•Plain text length = Key length
•The sender would write the keys one at a time above the
letters of the plaintext and encipher the plaintext with a
prearranged chart (called a Vigenère tableau) that has all
26 letters in each column, in some scrambled order.
•Recipient need identical pad
•Pad position should be synchronized
•Ciphertext bears no statistical relationship to the plaintext
since for any plaintext & any ciphertext there exists a key
mapping one to other.

25. VIGENERE CIPHER
Plaintext: A T T A C K A T D A W N
Key: L E M ON L E M O N L E
Ciphertext: L X F OP V E F R N H R
To encrypt, a table of alphabets can be used, termed a
 
Vigenère
table. It consists of the alphabet written out 26 times in different
rows, each alphabet shifted cyclically to the left compared to the
previous alphabet, corresponding to the 26 possible Caesar
ciphers.
At different points in the encryption process, the cipher uses a
different alphabet from one of the rows. The alphabet used at
each point depends on a repeating keyword.

27. Decryption?
Homework
1. Encrypt the message FOLLO WTHEY ELLOW BRICK ROAD with
the keyword OZ.
2. Decrypt the message LOSVW AZBSH DHQID ARSLG EL , encrypted
with the Vigenere cipher using SHOES as a key.

28. The Vernam Cipher - Example
Plaintext VERNAMCIPHER
Numeric
Equivalent
214171301228157417
+ Random
Number (timepad)
7648168244358116054788
= Sum 9752339544156019751251105
= mod 26 19071718158192312251
Ciphertext tahrspitxmzb
The Vernam Cipher is a type of one-time pad devised by Gilbert Vernam.

29. The Vernam Cipher - Decryption
Ciphertext tahrspitxmzb
Numeric equivalent19071718158192312251
- One-time pad 7648168244358116054788
= Difference
-57-48-9-65-2612-508-377-22-87
= mod 26 214171301228157417
Plaintext VERNAMCIPHER
To decrypt: (C
i – K
i) mod 26

30. One-Time Pads
•if a truly random key as long as the message is
used, the cipher will be secure
•The one-time pad method has problems:
•the need for absolute synchronization between
sender and receiver, and the need for an unlimited
number of keys. Although generating a large number
of random keys is no problem, printing, distributing,
storing, and accounting for such keys are problems.
•Can only use the key once
•Have problem of safe distribution of key

31. Transposition Ciphers
•The goal of substitution is confusion; the encryption
method is an attempt to make it difficult for a
cryptanalyst to determine how a message and key were
transformed into ciphertext.
•A transposition is an encryption in which the letters of
the message are rearranged. With transposition, the
cryptography aims for diffusion, widely spreading the
information from the message or the key across the
ciphertext.
•Transpositions try to break established patterns. Because
a transposition is a rearrangement of the symbols of a
message, it is also known as a permutation.

32. Columnar Transpositions
•A rearrangement of the characters of the
plaintext into columns

33. THIS IS A MESSAGE TO SHOW HOW A COLUMNAR TRANSPOSITION WORKS
In this example, the length of this message happens to be a multiple
of five, so all columns are the same length. However, if the message
length is not a multiple of the length of a row, the last columns will
be one or more letters short. When this happens, we sometimes use
an infrequent letter, such as X, to fill in any short columns.

34. Rail Fence cipher
•The Rail Fence cipher is a form of transposition cipher that
gets its name from the way in which it is encoded.
•In the rail fence cipher, the plaintext is written downwards on
successive "rails" of an imaginary fence, then moving up when
we get to the bottom. The message is then read off in rows.
•For example, using three "rails" and a message of 'WE ARE
DISCOVERED. FLEE AT ONCE', the cipher text writes out:

35. Confusion and Diffusion
•The terms confusion and diffusion are the
properties for making a secure cipher.
 
(Shannon)
•Diffusion – dissipates statistical structure of
plaintext over bulk of ciphertext.
•Confusion – makes relationship between
ciphertext and key as complex as possible.
• Confusion is used for creating clueless.

36. Stream Ciphers
•Convert one symbol of plaintext immediately
into a symbol of ciphertext
e.g. Substitution ciphers
Advantage
– Speed of Transposition
– Low error propagation
Disadvantage
– Low diffusion
- Susceptibility to malicious insertions and modifications

37. Block Cipher
Convert a group of plaintext symbols as one block
e.g. Transposition ciphers

38. Block Cipher
Advantages
– High Diffusion:
Information from the plaintext if diffused into several ciphertext
symbols.
one ciphertext block may depend on several plaintext letters.
– Immunity to insertions of symbols:
it is impossible to insert a single symbol into one block, the
length of the block would then be incorrect, and the
decipherment would quickly reveal the insertion.
Disadvantages
-Slowness of encryption
-Error Propagation