Criptografía - Sesión 2

7/25/2019 Criptografa - Sesin 2

1/16

Three can keep a secret, if two of them are dead.

Benjamin Franklin

CriptografaSesion 2

Symmetric Ciphers

Yoan Pinzon, PhD

Universidad Nacional de Colombiahttp://disi.unal.edu.co/ypinzon/2023700/

c 2013

Session 2

Symmetric Ciphers Introduction to Notation Block Ciphers

Substitution Ciphers Monoalphabetic Substitution Ciphers

Polygraphic Example: Porta Cipher Example: Playfair Cipher

Unilateral Example: Caesars Cipher Example: Rot13 Cipher Example: Dots Cipher

Multilateral Example: Garbage-in-between Cipher

Polyalphabetic Substitution Ciphers Example: Vigenere Cipher Example: Hills Cipher

Homophonic Substitution Ciphers Example: Homophonic Cipher

Transposition Ciphers Example: Turning Grille

Product Ciphers Example: Lucifer Cipher

12


2/16

Introduction to Notation

A, the alphabet of definition, eg. A= {0, 1},

M is the message space; set of strings over A, M A

C is the ciphertext space; set of strings over A

K denotes the key space; each e K uniquely determines a bijection

m is a plaintext (message), m M

Ee: M C is the encryption function (bijection)

Dd: C M is the decryption function (bijection)

Applying Ee (or Dd) is called encryption (or decryption).

13

Introduction to Notation (cont.)

An encryption scheme (or cipher) consist of a set {Ee: e K} anda corresponding set {Dd : d K} with the property that e K aunique d K s.t. Dd= E

1e ; i.e.,

Dd(Ee(m)) =m m M

Alice Bob

Eve

c

cc E m= ( )e m D c= ( )d

To construct an encryption scheme requires fixing a message spaceM, a cipher space C, and a key space K, as well as encryption trans-formation {Ee: e K} and corresponding {Dd: d K}.

14


3/16

Symmetric-Key Encryption

Symmetric-key encryption uses the same key (or are easily derivedfrom each other) to encrypt and decrypt. e= d = k.

Alice Bob

Eve

c

c

secure channel

unsecure channel

c E m= ( )k m D c= ( )kk

Is simpler and faster, but their main drawback is that the two parties

must somehow exchange the key in a secure way.

Symmetric-key encryption schemes are often characterised as block ci-phers or stream ciphers although the distinction can be fuzzy.

15

Block Ciphers

A block cipher is a symmetric-key encryption scheme that breaks upthe plaintext message into strings (blocks) of a fixed length t over analphabet A and encrypts one block at a time.

There are three classes of block ciphers

Substitution ciphers: replace symbols (or groups of symbols) byother symbols or groups of symbols.

Transposition ciphers: simply permutes the symbols in a block.

Product ciphers: is a composite of substitution and transpositionciphers.

16


4/16

Substitution Ciphers

A substitution cipher is a cipher that replaces each plaintext symbol(or group of symbols) with another ciphertext symbol. The receiverdeciphers using the inverse substitution.

Encryption using Substitution cipher is an one of the most simple meth-

ods used even by ancient cryptographers.

There are three basic types of substitution ciphers

Substitution

Polygraphic Unilateral Multilateral (Polyphonic)

PolyalphabeticMonoalphabetic Homophonic- Vigenere- Hill

- Homophonic

- Garbage-in-between- Ceasar- Rot13- Dots

- Porta- Playfair

17

Monoalphabetic Substitution Ciphers

The main idea of these ciphers is an one by one substitution of a symbolfrom plaintext to corresponding symbol in ciphertext.

There are three types of Monoalphabetic ciphers

Polygraphic: the plaintext units are consistently more than one plain-text letter long.

Unilateral: the ciphertext unit is always one character long.

Multilateral (Polyphonic): the ciphertext unit is more than onecharacter in length. The ciphertext characters may be letters, num-bers, or special characters. ciphers.

18


5/16

Following slides show examples of different monoalphabetic ciphers:

Porta Cipher: Polygraphic monoalphabetic substitution cipher.

Playfair Cipher: Polygraphic monoalphabetic substitution cipher.

Caesars Cipher: Unilateral monoalphabetic substitution cipher.

Rot13 Cipher: Unilateral monoalphabetic substitution cipher.

Dots Cipher: Unilateral monoalphabetic substitution cipher.

Garbage-in-between Cipher: Multilateral monoalphabetic substitu-tion cipher.

The prefixes mono- and uni- mean one, and graphic and literal referto letters or other characters.

19

Porta Cipher (Polygraphic)(Giovanni Battista della Porta, 1563)

Based on the following 2020 tableau filled with 400 unique glyphs.

Use the table to give different symbols for every pair of letters.

20


6/16

Playfair Cipher (Polygraphic)(Sir Charles Wheatstone, popularized by Baron Lyon Playfair, 1854)

To encipher, pick a keyword and write it into a 55 square, omittingrepeated letters and combining I and J in one cell.

Y O A N PIJ Z B C D

E F G H KL M Q R ST U V W X

We need break the plaintext up into two-letter groups. If letters in apair are the same, insert X between them. If there is only one letter inthe last group, add X to it. To encrypt find each two-letter group in thesquare and if they are:

in the same column use the letter below it as the cipher text,

in the same row use the letter to the right as the cipher text,

neither each letter is exchanged with the letter at the intersectionof its own row and the other column.

For deciphering, the rules are the exact opposite.

21

Example: Encrypt THIS SECRET MESSAGE IS ENCRYPTED

TH IS SE CR ET ME SX SA GE IS EN CR YP TE DX

Y O A N P

IJ Z B C D

F G K

L M Q R S

U V X

E H

T W

TH=WE

Y O A N P

IJ Z B D

E F G K

L M Q S

T U V X

C

H

R

W

CR=HW GE=HF

Y O A N P

IJ Z B C D

K

L M Q R S

T U V W X

E F G H

Y O A N P

IJ Z B C D

E F G H K

L M Q R S

T U V W X

TH IS SE CR ET ME SX SA GE IS EN CR YP TE DXWE DL LK HW LY LF XP QP HF DL HY HW OY YL KP

It was in military use from the Boer War through World War II.

Exercise: Using the same key above, decipher the following ciphertext:

ZO MH LC HY ZK MN SO NQ DL KT OQ CY KI EC LK SO YI EQ PQ RX EY KR WM NSDL GY LD GF AB YA QN YE AP GN IX PG HY YS NB HT EC TL KF VN RP YT PU PFCY EB YA WM KI MP LF UZ LH TC YH NP CK KL LY YT KI GB DH CY EC RD GN CLGO IH YE TY KI XO UY VN SC LX KF MX PW

22


7/16

Caesars Cipher (Unilateral)(Julius Caesar, 50-60 BC)

A= {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 }

M= C = strings of length 5

k= permutations of 3

Example: Cipher the message RETURN TO ROME

plaintext = RETUR NTORO MEciphertext = UHWXU QWRUR PH

Exercise: DecryptWKLVL VHAWU HPHOB LQVHF XUHHQ FUBSW LRQGR QRWXV HLWWRSURWH FWYDO XDEOH LQIRU PDWLR Qand LWLVF ODLPH GWKHH DUOLH VWNQR ZQUHIHUHQF HWRWK LVWBS HRIFL SKHUL VLQWK HNDPD VXWUD ZKLFK VDBVZ RPHQV KRXOGOHDUQ WKHDU WRIVH FUHWZ ULWLQ JWRFR QFHDO WKHLU OLDVR QV and Encryptthe message we will attack at dawn through the left flank.

This type of cipher is easily defeated by frequency analysis

23

Rot13 Cipher (Unilateral)

(USENET net.jokes newsgroup, mid-1980s)

Replaces each letter with the letter thirteen places down the alphabet. Abecomes N, B becomes O and so on.

Examples:

aha nun ant nag balk onyx bar onebarf ones be or bin ova ebbs roofenvy rail er re errs reef flap syncfur she gel try gnat tang irk vex

The algorithm is used in online forums as a means of hiding joke

punchlines, puzzle solutions, movie and story spoilers and offensivematerials from the casual glance. ROT13 has been described as

theUsenet equivalent of a magazine printing the answer to a quiz

upside down

Exercise: Decrypt VSGUR AFNUN FGVZR GBERN QZLRZ NVYVJ VFUGU RLFRAQZRNO YBBQL

24


8/16

Dots (Unilateral)

Symbols in the plaintext will be replaced by squares with or withoutpoints and with or without surrounding lines using the following rules:

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

Example: Encrypt the message WE TALK ABOUT FINNISH SAUNAMANY TIMES LATER

WE TALK ABOUT FINNISH SAUNA MANY TIMES LATER

: : : :: : : :

: :

. . .

...

..

: : : :. . .

:

25

Garbage-in-between Cipher (Multilateral)

(Cardinal Richelieu, 1626)

In garbage-in-between cipher, the message is written in positions de-termined by the key. After that, empty positions are filled by arbitraryletters, in a misleading way so that the whole message looks like a dif-ferent story.

Example:

I LOVE YOUI HAVE YOUDEEP UNDER

MY SKIN MYLOVE LASTSFOREVER INHYPERSPACE

I LOVE OUI HAVE Y UD EE P N DE R

MY S N MYOVE S S

F REVER IHYPERSPA

YO

U

KIL LA TO N

CE

Ciphertext Key Plaintext

The encrypted message is YOU KILL AT ONCE

26


9/16

Polyalphabetic Substitution Ciphers

The main idea behind the polyalphabetic cipher is that a single symbolcan be encrypted to several different symbols instead of just one.

The reason behind using polyalphabetic ciphers is to flattenfrequency distributions.

Following slides show two examples of polyalphabetic ciphers:

Vigenere Cipher

Hill Cipher

27

Vigenere Cipher (Polyalphabetic)(Blaise de Vigenere, 16-th century)

Based on the tableau shown below and the use of a keyword.

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 ZB C D E F G H I J K L M N O P Q R S T U V W X Y Z AC D E F G H I J K L M N O P Q R S T U V W X Y Z A BD E F G H I J K L M N O P Q R S T U V W X Y Z A B CE F G H I J K L M N O P Q R S T U V W X Y Z A B C DF G H I J K L M N O P Q R S T U V W X Y Z A B C D EG H I J K L M N O P Q R S T U V W X Y Z A B C D E FH I J K L M N O P Q R S T U V W X Y Z A B C D E F GI J K L M N O P Q R S T U V W X Y Z A B C D E F G HJ K L M N O P Q R S T U V W X Y Z A B C D E F G H IK L M N O P Q R S T U V W X Y Z A B C D E F G H I JL M N O P Q R S T U V W X Y Z A B C D E F G H I J KM N O P Q R S T U V W X Y Z A B C D E F G H I J K L

N O P Q R S T U V W X Y Z A B C D E F G H I J K L MO P Q R S T U V W X Y Z A B C D E F G H I J K L M NP Q R S T U V W X Y Z A B C D E F G H I J K L M N OQ R S T U V W X Y Z A B C D E F G H I J K L M N O PR S T U V W X Y Z A B C D E F G H I J K L M N O P QS T U V W X Y Z A B C D E F G H I J K L M N O P Q RT U V W X Y Z A B C D E F G H I J K L M N O P Q R SU V W X Y Z A B C D E F G H I J K L M N O P Q R S TV W X Y Z A B C D E F G H I J K L M N O P Q R S T UW X Y Z A B C D E F G H I J K L M N O P Q R S T U VX Y Z A B C D E F G H I J K L M N O P Q R S T U V WY Z A B C D E F G H I J K L M N O P Q R S T U V W XZ 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

28


10/16

Example: Encrypt the message TO BE OR NOT TO BE THAT ISTHE QUESTION, using the keyword=RELATIONS and t= 5.

Keyword = RELAT IONSR ELATI ONSRE LATIO NSRELPlaintext = TOBEO RNOTT OBETH ATIST HEQUE STION

Ciphertext = KSMEH ZBBLK SMEMP OGAJX SEJCS FLZSY

Exercise: Encrypt the message THERE IS A SECRET PASSAGE BE-HIND THE PICTURE FRAME, keyword=CRYPTO (k = {P2, P17,P24, P15, P19, P14}), and t= 3.

This cipher is the basic idea behind the Enigma machine, which used

three rotors to encode.

For 300 years the Vigenere cipher was considered to be unbreakable.

Then in 1863 a Prussian military devised a method to determine the

length of the keyword and then divide the message into a simplerform to which letter frequency analysis could be applied.

29

Hill Cipher (Polyalphabetic)

(Lester S. Hill, 1929)

Each letter is treated as a digit in base 26: A = 0, B =1, and so on.

Let M= C = (Z26)t

The idea is to take t linear combinations of the t alphabetic charactersin one plaintext element, thus producing the m alphabetic characters inone cipher element.

For example, if t = 2, we could write the plaintext element as m =(m1,m2) and a ciphertext element as c = (c1, c2), Here, c1 would be alinear combination ofm1 and m2, as would c2. We might take

c1 = 11m1+ 3m2c2= 8m1+ 7m2

which can be written more succinctly in matrix notation as follows:

(c1, c2) = (m1,m2)

11 8

3 7

Students familiar with linear algebra will realize that we use the inversematrix K1 to decrypt. The ciphertext is decrypted using the formulam= cK1.

30


11/16

The inverse matrix to a matrix A (if it exists) is the matrix A1 suchthat AA1 =A1A= I, where I is the identity matrix (matrix with 1son the main diagonal and 0s elsewhere).

Not all matrices have inverses, but if an inverse exists, it is unique.

11 8

3 7

1=

7 18

23 11

since 11 8

3 7

7 1823 11

=

11 7 + 8 23 11 1 8 + 8 11

3 7 + 7 23 3 1 8 + 7 11

=

261 286182 131

=

1 00 1

Remember that all operations are done modulo 26.

31

Example: Encrypt the message JULY using K=

11 83 7

.

(9, 20) JU and (11, 24) LY, then

(9,20)

11 8

3 7

= (99 + 60, 72 + 140) = (3,4)

and

(11,24)

11 8

3 7

= (121 + 72,88 + 168) = (11, 22)

Hence the encrypted message of JULY is DELW.

Exercise: Decrypt VKFZRVWTIAZSMISGKA using the same key as above.

32


12/16

Homophonic Substitution Ciphers

Homophonic substitution ciphers are ciphers in which several differentciphertext letters can be used to stand for some plaintext letters.

Typically in a homophonic substitution cipher, the cipher alphabet (the

symbols which can appear in a ciphertext) is larger than the plaintextalphabet.

Coding symbols are assigned to each plain letter based on their

frequency.

Following slide show an example of homophonic cipher:

Homophonic Cipher

33

Homophonic Cipher

Example: Encrypt the message: Crypto is fun

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

9,12,33,4

7,53,67,78,92

48,81

13,41,

1,3,45,79

14,16,24,44,46,55,57,64,74,82,87,98

10,

6,25

23,39,50,56,65,68

,70,73,83,88,93

154 26,37,51,84

22,27

18,58,59,66,71,

0,5,7,54,72,

,99

38,

9429,35,

,42,77,80

11,

,36,76,86,96

17,20,30,43,49,

,75,85,97

8,

,63

3460,89

28,52

2

62

31

32

91

90

9540

19

69

61

21

Ciphertext : 62 40 21 95 69 90 32 19 31 61 91

Exercise: Decrypt 1 3 5 2 6 0 2 2 8 1 8 8 4 7

34


13/16

Transposition Ciphers

A transposition ciphers are where the letters are jumbled up together.

Instead of replacing characters with other characters, this cipher just

changes the order of the characters.

Mathematically a bijective function is used on the characters

positions to encrypt and an inverse function to decrypt.

Following slide show an example of transposition cipher:

Turning Grille

35

Turning Grille(Eduard B. Fleissner v. Wostrowitz, 1881)

Used by Germany during the First World War.

This is a square piece of cardboard with holes in it such that each cellin the square appears in no more than one position when the grille isrotated to each of its four positions.

As much message as will fit in the grille is written, then it is turned toanother position and more message is written.

Example: Encrypt JIM ATTACKS AT DAWN using the following 44grille.

2

1

4

3

36


14/16

J

I M

A

2

1

4

3

T

A

C

T

J

I M

A

2

1

4

3S

T

K

A

T

A

C

T

J

I M

A

2

1

4

3

S

T

K

A

T

A

C

T

J

I M

A2

1

4

3

D

N

A

W

JIMA TTAC KSAT DAWNJKTD SAAT WIAM CNAT

Exercise: Decrypt the ciphertext TESHN INCIG LSRGY LRIUS PITSA TLILMREENS ATTOG SIAWG IPVER TOTEH HVAEA XITDT UAIME RANPM TLHIE Iusing thefollowing grille.

2

1

4

3

37

Product Ciphers

A product cipher is a composite of substitution (confusion) and trans-position (diffusion) ciphers.

Diffusion refers to the dissipation of the statistical properties of theplaintext.

Confusion makes relationship between ciphertext and key as complex aspossible.

two substitutions make a more complex substitution

two transpositions make more complex transposition

but a substitution followed by a transposition makes a new muchharder cipher

Product ciphers are the bridge from classical to modern ciphers like

DES (Data Encryption Standard)

38


15/16

Lucifer Cipher(Horst Feistel, IBM, 1971)

This system uses permutations (transpositions) on large blocks for the

mixing transformation, and substitution on small blocks for confusion.Note that there is no key - thus the system is insecure.

Since this system was set up in hardware, they called the chips which didthe permutations P-boxes, and those that did the substitution S-boxes.

Feistel had originally started with a Demonstration Cipher, with

the name truncated toDemon, which led logically to the name

Lucifer, which incidentally suggests Lu(cipher).

39

P-box Example

AP-box(Permutation-Box) is a box which permutes the bits of its input.

0

0

0

0

0

0

0

1

0

00

0

0

0

0

1

0

0

0

0

0

0

0

0

00

0

0

0

0

P-Box

40


16/16

S-box Example

The S-box (Substitution-Box) is a hardware device which encodes n bitnumbers to other n bit numbers.

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

0

0

1

1

1

1

n=3

Low-to-HighBase

Transformer

High-to-Low

Base

Transformer

S-Box

3:8 8:3

(4,8,1,7,3,5,6,2)

permutation

41

Lucifer Illustrative Example

The Lucifer system simply consisted of a number of P & S boxes inalternation:

S1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

S

S

S

S

P P S

S

S

S

S

P S

S

S

S

S

P S

S

S

S

S

P S

S

S

S

S

P 11

0

1

1

1

0

1

1

0

1

1

1

0

1

Lucifer is known as the predecessor for the Data Encryption

Standard (DES).

Documents

Criptografía - Sesión 2