程序代写代做代考 algorithm 17crypto_L04

17crypto_L04

Traditional Encryption
Algorithms (2)

Crpto & SecDev 2017 © Ron Poet: Lecture 4 1

Algorithms (2)

Polyalphabetic Substitutions

� Polyalphabet substitutions destroy single letter frequencies
by using several different substitutions one after the other.

� The actual substitution used for each letter is different and
depends on the letter position in the plain text as well as its

Crpto & SecDev 2017 © Ron Poet: Lecture 4 2

depends on the letter position in the plain text as well as its
value.

Vigenere/Beaufort Cipher

� This is a form of shift substitution, where the shift depends
on the position of the plain text letter.

� ci = (pi + ki) % n

� The series of keys k , k … repeat with a period d.

Crpto & SecDev 2017 © Ron Poet: Lecture 4 3

� The series of keys k0, k1 … repeat with a period d.

Example

� A simple example has a period of 3 (d=3).

�The first letter is shifted 3 (k0=3).

�The second letter is shifted 7 (k1=7).

�The third letter is shifted 5 (k =5).

Crpto & SecDev 2017 © Ron Poet: Lecture 4 4

�The third letter is shifted 5 (k2=5).

� The next block of 3 is treated similarly.
� sec uri tya ndc ryp tog rap hy

�becomes (s+3 → v, e+7 → l, c+5 → h)
� vlh xyn wff okh ufu wvl uhu kf.

Kasiski’s Method of Attacking Periodic
Ciphers

� The Beaufort cipher will repeat with a period that is not too
long.

� Look for identical plain text phrases (typically trigrams)
that are an exact multiple of the period apart.

Crpto & SecDev 2017 © Ron Poet: Lecture 4 5

that are an exact multiple of the period apart.

� Each phrase will be encoded to form the same cipher text.

� The previous message is not long enough to illustrate this.

�Short messages were relatively secure.

Rotor Machines

� A rotor machine uses several different substitutions, each
one implemented as a rotor.

� Each rotor has a circle of metal contacts on the left and
right faces, one contact for each letter in the alphabet.

� Each contact on the left face is connected to one on the

Crpto & SecDev 2017 © Ron Poet: Lecture 4 6

� Each contact on the left face is connected to one on the
right face by wiring.

� Several rotors are combined so that each contact on the left
face of one rotor press against a contact on the right face of
the next rotor.

� The input keyboard connects to the corresponding position
on the right face of the first rotor.

� The left face of the last rotor connects to the output.

Rotor Machines (2)

� The rotor positions are changed after each key is input.

� Sometimes all the rotors change positions each time.

� In other cases only one rotor moves each time, with the
others moving occasionally, similar to the way a car’s

Crpto & SecDev 2017 © Ron Poet: Lecture 4 7

others moving occasionally, similar to the way a car’s
mileage is recorded.

� The key is the starting position of each rotor.

� These machines only repeat after a very long period and
are not vulnerable to Kisiski’s attack.

� They have good confusion and diffusion.

The Enigma Machine

� This was a three or four rotor machine.

� There was also a reflector, a fixed rotor with only one face,
with letters connected in pairs.

� A plug board connected several pairs of letters with a wire.

Crpto & SecDev 2017 © Ron Poet: Lecture 4 8

� A plug board connected several pairs of letters with a wire.
It was a simple permutation.

� When a key was pressed, an electrical circuit was created,
connecting a plug board circuit, each rotor, the reflector,
each rotor again, and then an indicator light.

� The reflector meant that the same setup could be used for
encryption and decryption.

Enigma: Key

� The key was the choice of rotors and the order in which
they were inserted in the machine, together with the plug
board settings.

� There were a small number of networks (army, navy, air

Crpto & SecDev 2017 © Ron Poet: Lecture 4 9

� There were a small number of networks (army, navy, air
force etc), and each network used the same key, which
changed daily at midnight.

� It was highly likely that a large number of documents with
the same starting letters would be encrypted with the same
key, leading to the same cipher text.

� This was prevented by the use of an “indicator key”

Enigma: Indicator

� The indicator key was another set of three letters chosen at
random by the operator and different for each message.

� The operator first encrypted the indicator key using the
standard daily settings.standard daily settings.

� He then changed the rotor settings to the indicator key.

� Then he typed the rest of the message.

� Thus 2 identical plain text messages were unlikely to result
in identical cipher text messages.

Crpto & SecDev 2017 © Ron Poet: Lecture 4 10

Breaking the Enigma

� The Enigma was broken with a brute force attack using a
set of mechanical devices called Bombes.

� It was mainly a known plain text attack, testing a number
of standard phrases, called cribs.of standard phrases, called cribs.

� Many messages started with ANX. An is German for To,
and X was used for spaces.

� Ein, German for 1, appeared in 90% of messages.

� Many messages contained the German for “Nothing to
report”.

Crpto & SecDev 2017 © Ron Poet: Lecture 4 11

Breaking the Enigma (2)

� The reflector was a big weakness, because it meant that each cipher
text letter was different from the plaintext.

� If the cipher text started with ‘A’, then the plaintext could not be
‘ANX’.

�One code breaker noticed that a cipher text message did not �One code breaker noticed that a cipher text message did not
contain the letter L, and correctly deduced that the plaintext was
LLLLLL…

�This greatly restricted the number of keys that had to be tested.

� The bombes would stop if they found a key that produced the crib.

� This was usually a false stop because several possible keys could
produce the crib (see unicity distance).

Crpto & SecDev 2017 © Ron Poet: Lecture 4 12

Running Key Encryption

� The key is English text, the same length as the plain text.

� The encryption and decryption is then very simple.

ci = (pi + ki) mod n

p = (c – k ) mod n

Crpto & SecDev 2017 © Ron Poet: Lecture 4 13

pi = (ci – ki) mod n

� This seems to destroy letter frequency analysis and is not
periodic, but it can be broken if the key is not chosen well.

Literature Based Key

� The key might be based on a book that is available to both
the coder and decoder.

�Macbeth, Act 2 Scene 3, line 4, say.

�That is the starting point for the letters.

Crpto & SecDev 2017 © Ron Poet: Lecture 4 14

�That is the starting point for the letters.

� This is vulnerable to Friedman’s attack because both the
key and plaintext are English and have redundancy.

Friedman’s Attack

� Friedman’s approach assumes initially that all cipher text
characters are caused by high frequency letters in both the
plain text and the key text.

� This means that there will only be a few possibilities for

Crpto & SecDev 2017 © Ron Poet: Lecture 4 15

� This means that there will only be a few possibilities for
each plain text and key text letters. They must both add up
to produce the given cipher text letter.

Friedman’s Attack (2)

� Digram and trigram frequencies are then used to guess the
actual letters used.

� A significant proportion of the plain text and cipher text
can be guessed by this approach

Crpto & SecDev 2017 © Ron Poet: Lecture 4 16

can be guessed by this approach

� The rest can be filled in using natural language
redundancy.

Example

� Plain text
�thetreasureisburied . . .

� Key
�thesecondcipheris . . .

Crpto & SecDev 2017 © Ron Poet: Lecture 4 17

�thesecondcipheris . . .

� Ciphertext
�moilvgofxtmzflz . . .

Example (2)

� Assume that there are only high frequency letters
(aehinorst) in the key and plaintext.

� Then looking at the 1st 3 letters in the cipher text (trigram)
�Letter m can be caused by: ei, ie, tt.

�Letter m can be caused by: ei, ie, tt.
�Letter o can be caused by: ao, oa, hh
�Letter i can be caused by: ai, ia, ee, rr

� There are 36 possible combination (rather than 17576 for
all letters), with plaintext and key combinations:

� (eaa,ioi); (eai,ioa); … (the,the) … (thr,thr)
� Most are impossible in English, limiting the choices.

Vernam Cipher

� A variant of the running key cipher converts the characters
of the key and plain text to binary form first before
combining them.

� This was first used with the 5 bit Baudot telegraph code,

� This was first used with the 5 bit Baudot telegraph code,
but will also work with modern ASCII.

Vernam Cipher (2)

� The bits are combined using the exclusive-or operation.
ci = pi ⊕ ki
pi = ci ⊕ ki

� Properties of Exclusive Or

2 bits the same → 0, different → 1

a ⊕ a = 0
a ⊕ 0 = a

� p’ = c ⊕ k = p ⊕ k ⊕ k = p ⊕ 0 = p
� Exclusive or with the same key twice cancels out.
� This makes exclusive or good for cryptography.

One Time Pad

� If the key is a random series of letters, then this encryption
algorithm cannot be broken.

� The key however is very long and cannot be used more
than once.

than once.

Pseudo-Random Number Running Key
Cipher

� One apparent way of generating a large number of key
values from a small actual key is to use a pseudo-random
number generator.

� Just provide the initial value for the generator, the actual

� Just provide the initial value for the generator, the actual
key

� Then use pseudo-random numbers, which appear to be
random, in the running key algorithm.

Pseudo-Random Number Running Key
Cipher (2)

� This does not work in general, and there are standard
techniques for breaking such ciphers

�Which are surprisingly common among amateur
cryptographers.

cryptographers.

� The apparently random values do in fact have a structure
which can be exploited.

� This technique will work if a cryptographically secure
pseudo-random number generator is used.

Lorenz Cipher

� This was a Vernam cipher with a running key provided by
a pseudo-random number generator.

� The pseudo-random number was a mechanical device (12
gear wheels) that produced a series of 5-bit values.

gear wheels) that produced a series of 5-bit values.

� It was used to encrypt quite long documents.

� The weakness in the random number generator was
exploited by differential cryptanalysis.

�Two cipher text letters are combined using xor.

� It was broken by Colossus, the first large scale electronic
computer, which became operational in December 1943.

Polygram Substitution Ciphers

� Frequency attacks are weakened by encrypting blocks of
characters at a time rather than single letters.

� There is a smaller chance that two blocks will be the same.

� This is too complicated to do with a mechanical device, but

� This is too complicated to do with a mechanical device, but
electronic computers make it possible.

� This brings us into the block ciphers of the modern era.

Related Posts