Cryptography: Introduction

PRINCIPLE

2
 The Three Eras of Cryptography

The artisanal era (until the year 1918)

The scientific and technical era (1919-1975)
The modern era (1976 to present)

The quantum era (future)

3 3
 The artisanal era

Caesar cipher
Substitution encryption
Encryption with Transpositions
Vigenère Cipher
Steganography
etc.
4 4
 EXAMPLE 1: The shift

We associate each letter of the French alphabet (26 letters) with its rank from 1 to 26. We make a
shift of 3 letters in this alphabet. (it is said that 3 is the encryption key)
1) Fill in a table with the 26 letters of the alphabet and their correspondents by this offset.
What is the equivalent of x, y, z?
2) We consider the text:
Let's give to Caesar what is Caesar's.
We associate with each letter of this text its corresponding one by this shift.
Find the new text obtained.
3) Reverse path: let the text obtained by the same shift of 3 letters:
« do not forget to take »
Find the original text.
4) Establish a method to make this reverse path. (i.e., find a decryption key)

We can improve the concealment by adding rank 27 to an empty space.

5) What new text do we get in question 2?
What is the method allowing the reverse path in this case?
5
 EXAMPLE 2: Multiplication

Instead of shifting the letters, we will multiply their rank by 7 and calculate the remainder of the division by.
26 of these products. Let's take the text again:
Render unto Caesar what is Caesar's
1) By associating each letter of this text with its corresponding one through this multiplication, find the
new text obtained.
Inverse path: let the text obtained by this multiplication be:
avbktgjiqv
Find the original text.
3) Find a decryption key

4) To see if the choice of 7 has a particularity, redo the same calculations by multiplying.
By 8, the ranks of the letters, before calculating the remainders of the division by 26.
What is the disadvantage that we find in this case?

6
 Cryptography to Secure the
communications
Cryptography allows for communication with
hidden, concealed messages (information)
to prevent them from being read by third parties
(confidentiality).
The user or users authorized to access these
messages have keys that allow them to
access and read them

7
 cryptography Definition

Cryptography: a set of principles,

methods or techniques enabling to
encrypt data (with keys) for
preserve their confidentiality.
The basic principle of cryptography is therefore
to be able to communicate secretly.
Only the recipient is allowed to know the key.
and can decrypt encrypted data for the
read.
8
 Cryptography: an Art

Cryptography: crypto/secret, graphy/writing

The art of communicating secretly
Inventing syntactic transformations of
information to prevent reading by
third parties (privacy)
Only the recipient knows the secret of these
transformations and can access these
information
9 9
 Terminology
Plain text: message to protect
•Ciphered text: result of the encryption (concealment) of
clear text
Encryption: method or algorithm used to
transform a plain text into encrypted text
Decryption: method or algorithm used to
transform an encrypted text into plain text
•Key: shared secret used to encrypt plaintext in
encrypted text and to decrypt the encrypted text into text in
clear 10
 Caesar cipher

We make a shift of 3 (or 13) letters in the French alphabet.

We fill in a table with the 26 letters of the alphabet and their
correspondents by this shift.
Since there are twenty-six letters in the French alphabet this corresponding is
calculate modulo 26 where we only keep the remainder of the division by 26
Encryption is achieved by replacing each letter with its
corresponding to this shift.
Le déchiffrement s’obtient aussi par décalage en sens opposé équivalent à
a direct shift of 23 (or 13) letters.

11
 Caesar cipher
The previous encryption uses a
substitution technique. Each letter of
the French alphabet is replaced by a
unique other letter from the same alphabet. We
can be replaced by the letters of another
alphabet or other symbols. It is necessary
only that each letter be transformed
in a unique other symbol to be able to
decipher.
12
 Substitution mono-alphabetic
In the previous example, each letter of the alphabet
French is encrypted by one and only one other.
letter of this alphabet.
We have a permutation (bijection) of the set of
letters of this alphabet.
How many possibilities are there to
monographic substitution with the alphabet
French? 26! = 26 x 25 x 24 x 23 x ...... x 2 x 1

=403291461126605635584000000 13
 Encryption with substitutions

EXAMPLE:
The text appears to be a random string of characters and does not convey a meaningful sentence in any language.
ARMEPRXUPZFPMXMPXEFJEPZXPEEPPMMPZJEKQRXKRVCJXEZKUPEKPFPVNCJUKZZPMJEVEUPZHJEZ
RAMPFPMRCARZZRFPFPQURESPLVXRQRXKMPKJVUFPFPVNBJHXKRVN

How to decipher this message?

Each letter is encrypted in the same way...
Certain letters are used more often.

Substitution mono or polyalphabetic

14 14
 Frequency analysis

Attack by analysis of
frequencies

Al-Kindi IX ecentury

15 15
 Frequency analysis

French Alphabet

"this is unsolvable" to decipher 16 16

Frequency of letters in English

17 17
 Example of cryptanalysis
A coded message
HUPZFPKUJXZREZRHUPZHMVZXPVUZAJCAPZJEKPNHMJZPRLVPMLVPZCXEVKPZFPSRUKFREZF
PZZKRKXJEZARMEPRXUPZFPMXMPXEFJEPZXPEEPPMMPZJEKQRXKRVCJXEZKUPEKPFPVNCJU
KZZPMJEVEUPZHJEZRAMPFPMRCARZZRFPFPQURESPLVXRQRXKMPKJVUFPFPVNBJHXKRVN
•Comptez les occurrences des lettres 34P,21 Z, 15 E, 13 R, 13 X, 12 K, 9 FP, 8PZ
•Intuition: P = e Z = s; {E, R, X, K} corresponds to {A, I, N, T} but in which
order?
•Intuition : PZ = is FP = the or of
After some trial and error, we obtain:

It is not clear if it is even understandable.

.[Link]..nesienneell
It seems like there is a code or a puzzle in the text that isn't clear enough to translate.
the..ass..e.e..an.e..[Link]....e.e.....ita...

18 18
 Cryptanalysis (continued)
It is easy to find the word 'stations' so
the or
-..[Link]..es...sie..s.o..es
onte..losea..el..[Link]
.[Link]
[Link]..oins
[Link].e...[Link].
he..says..that..he..loves..you...
e.e...[Link]...

19 19
 Cryptanalysis (finance)
It is easy to find the word "beach resorts" so the b
and the r
the other house is not there
The station is intense.
[Link]
ta..oinstrente.e...[Link]
She is a great person.
..[Link]..

20 20
 Encryption with Transpositions

The characters of the text remain unchanged.

but their positions in the encrypted text
different.
Example: Greek technique used BC

21 21
 Encryption with Transpositions

She uses a stick called scytale with a diameter

fixed. A leather belt was wrapped in a spiral
around this stick and the plain text was written on
the belt. Then we unroll the belt and we
I send it to the recipient (without the stick).
To decipher, one must use a stick of the same.
diameter, wrap the leather belt and the text in
clear can be proofread.
22 22
 Vigenère cipher

Blaise Vigenère (1523-1596) is one of the

first cryptographers to use a key (or
a password) to encrypt a message.
His technique is based on a 26x26 square.
cases, each box includes a letters
of the French alphabet.

23 23
 Vigenère Square

So is the Casablanca message

that we want to encrypt using the
Vigenère technique using
the key: beta
Casablanca
betabetabe
belacm…

24 24
 Steganography
(from Greek steganos: covered and graphein: writing)
An alternative to cryptography:
Covered writing hides a message in clear in
the dispersant in an innocuous message.
Historically: skull, mask, wax tablet,
invisible ink, microfilm dot.
Currently: watermarking.
Disadvantage: Takes up a lot of space
25 25
 Steganography in an image

Hiding information in image files

by modifying a few bits (the least
significant) of the file that represents the image.
The human eye is not capable of discerning
small bits changes on a large one
image.

26 26
Steganography

27 27
 The Enigma machine

The Enigma machine is a family of

electromechanical machines
encryption, invented by Doctor Arthur
Scherbius and patented in 1918. Its
commercialization was a failure, but it
used during the Second World War
worldwide by the German army in order to
secure its communications. The outcome of
this war was largely the
consequence of his failure.

28
 The Enigma machine

the Enigma machine encrypts information by making the passage

of an electric current through a series of components. The
current is transmitted by pressing a letter on the keyboard. After its
crossing through a complex network of wires, a lamp indicates the
ciphered letter. The first component is a series of wheels
adjacent, called "rotors", which contain the electrical wires
used to encode the message. The rotors turn, varying the
complex network configuration whenever a letter is
taped. The Enigma machine usually uses another wheel,
named "reflector", and a component called desk of
connection, allowing to further complicate the process of
encryption.
29
The Enigma machine

30
 Kerckhoffs' Principles (1883)

The difficulty should not depend on the secret of

algorithms but the secret of the keys.
A figure must be stable (it can only be changed)
very rarely).
Simple and quick implementation of encryption and the
decoding (to achieve high throughput).

The algorithm must be made public, leaks about

this algorithm will arrive sooner or later

31 31
The Scientific and Technical Era
 Cryptography: a science

Cryptography has become a science that relies on

mathematics, computer science, mechanics
electronics, ... quantum mechanics ...
Cryptography gave birth to cryptanalysis,
another science that studies the means of reconstructing the
plaintext without knowing the encryption keys
to test the robustness
used algorithms.
Cryptology = Cryptography + Cryptanalysis

33 33
 Cryptography: 2 Types

Cryptography now uses some

keys
symmetric key cryptography
public key cryptography

34
Symmetric Cryptography
or to Secret Key

35 35
 Secret key cryptography

The key Kd decryption can be calculated in

function of the encryption key Ke.
In general: Kd= Ke= K

36 36
 Secret key cryptography

The key being shared between the sender and the

recipient, the secret of the key must be very well kept
kept.
How to transmit the key reliably?

For N correspondents, N(N-1)/2 secret keys are needed, one key per
couple of people.

37 37
 Secret key cryptography

The multiplication of keys:

User A
User J User B

Utilisateur C

User I

User D

User H
User E
User F
User G

38 38
 Secret key cryptography

Secret key cryptography includes two

parties :
Stream or continuous bit-by-bit encryption
Stream Ciphers
Block encryption (of the same sizes)
Block Ciphers

39 39
 Continuous encryption
Streaming encryption (or on-the-fly) converts the text
en clair en texte chiffré bit par bit.

Key K

40 40
 Continuous encryption
key
Examples: Clair encrypted

Vernam Cipher, stream cipher, uses a stream of numbers

random (the key) that will be combined by an operation (xor: exclusive or) on the text
in clear to generate the encrypted text.

Key as long as the message

Key should be used only once (it's called a disposable mask)

With these 2 conditions, it is the encryptionThe most secure.

These 2 conditions are actually disadvantages. (difficult to achieve)
each time).

This encryption was used between the United States and the USSR (telephone
41 41
red).
 Continuous encryption RC4

1) Proprietary secret key cipher of the company RSA-DSI (1987)

2) Secret algorithm but the program has been disassembled and published
In 1994. The name RC4 remained protected (Rivest Cipher No. 4).
3) Variable key length: e.g. length 40, 104 bits
(up to 2048 bits !!)
4) Operation in stream encryption mode 'Stream cipher'.
Generation of a pseudo-random byte sequence.
The encrypted message is obtained by an exclusive OR of the encrypted message with
this sequence.
Extremely simple and very effective implementation, in hardware or
in software.
The operations used are transpositions.
42 42
 RC4 Encryption Algorithm
1) Initialization of an array S of 256 bytes
pouri = 0..255
S[i] := i ;
pouri = 0..255
j:=(j+S[i]+key[i mod key_length]) mod 256;
aux := S[i]; S[i] := S[j]; S[j] := aux; (swap S[i], S[j])
2) Byte-by-byte encryption/decryption loop
i:=0; j:=0;
repeat
i:=(i+1) mod 256;
j := (j + S[i]) mod 256;
aux := S[i]; S[i] := S[j]; S[j] := aux; (swap S[i], S[j])
k = S[(S[i] + S[j]) mod 256]
octet_chiffré := octet_en_clair XOR k ;
until the end of the plain text; 43 43
 RC4: APPLICATIONS

Extremely fast: about 10 times faster than DES

So a lot of interest in this encryption.
Use in many tools: SSL, Password Encryption
Windows, MS Access, Adobe Acrobat, Oracle Secure SQL, Wifi ...
Easy cryptanalysis of the RC4/Wifi implementation in Wep:
Poor installation of 24-bit initialization vectors.
Poor security of the integrity mechanism.
Very easy for short keys (40 + 24 bits), not more difficult for keys
of 104 + 24 bits (successful attack in a relatively short time).
Recommendation: a number to avoid in Wifi.
RC4, when used properly with long keys, is still considered as
safe.

44 44
 Block Ciphering
The plaintext is divided into blocks of a certain length.
fix according to an alphabet, and the algorithm encrypts block by block.
Examples: DES, 3DES, AES by [Link] (Standard since 2000)

45 45
 Block cipher (DES)

The DES algorithm is a symmetric algorithm.

64-bit block encryption (that is, 8
(octets) functioning with 56-bit keys. It
works on 16 rounds and during each
in rounds, the 64-bit block is divided into 2
32-bit blocks.
DES was designed by IBM in 1970 under the name of
Lucifer, then modified and adopted as standard in
1970. 46
Block cipher (DES)

47
 Block cipher (DES)

Weakness of DES: the key length limited to 56 bits.

Possible solution: build an over-encryption based on the
DES by applying the DES multiple times in succession.
Solution 1: Double DES (2DES)
2DESk1k2 (M) = DESk2 (DESk1 (M))
Difficulty 2DES: not really better than DES.
Solution 2: Triple DES (3DES or TDES)
3DESk1k2k3 (M) = DESk3 (DESk2-1(DESk1 (M))
Advantage: better security thanks to the 168-bit key.
Disadvantage: 3DES takes three times longer than DES.
Conclusion: When performance allows it, 3DES is
recommended.
48
 Block encryption (DES)

DES was the main secret key cipher for 25 years.

From 1976 to 1993, DES is certified (official standard of the U.S. government).
1993: No alternative being available, DES is recertified for
five years.
Problem posed from the start: the key size: 56 bits.
In 25 years, cryptanalysis methods have made progress.
A comprehensive research can be done provided that one puts the
Price. Do not use DES except for encryption against
low-level attacks.
Launch of a competition in 1997 for the successor to the DES.

It is the AES (Rijndael) block cipher that was chosen by NIST.

(American National Institute of Standards and Technology) and adopted
as standard since the year 2000.

49
 The Modern Era

Diffie and Hellman Principle (1976)

Idea: There should be no relationships between
Keand Kd, and knowing KAndit must be practically
impossible to deduce Kd.

Revolution in cryptography

This principle has allowed to solve the problem of

the exchange of keys in key cryptography
secret.
50
 Diffie Principle
Hellman 1976
Two functions Ek and Dk' depending on keys k and k'.
Ek is the encryption method.
Dk' is the decryption method.
Basic properties:
Decryption is the inverse of encryption.
Dk' ( Ek (M) ) = M and vice versa
Major property: It is very difficult to deduce the
decoding Dk' from the knowledge of the method of
encryption Ek. (Ek one-way function)
Ideal property: Ek(M) and Dk’(M’) should be easy to
calculate.

51
 One-way functions

Definition: f is said to be one-way if knowing x,

f(x) is easy to calculate, but knowing f(x), it is
practically impossible to calculate x, that is to say
to solve the equation f(x) = y.
For practically impossible, we hear that the
the computation time is on the order of a few centuries,
even with big and powerful computers
•Examples: factorization, discrete logarithm
Directory (name phone number

52
 Example of a one-way function
The discrete logarithm
If p is a prime number, then (Fp*, x) is a
cyclic group
that is to say, there exists A belonging to Fp* ,
such that for all x in Fp*
on the existence and uniqueness of a
n such that x = a^n
is called the discrete logarithm of x to the base a.

53
 Safe idea

The principle is quite simple. Alice and Bob want to

communicate a message confidentially. For
she, Alice will choose a safe for which she
has the key and sends it to Bob while leaving him
open. Bob is going to put the message in it, close it and
send back to Alice. Thus Alice will receive the safe
that she will be able to open since she has the key. But
all the intermediary people who transported the
chests will not have been able to intercept the message.

54
Diffie-Hellman key exchange

55
public key cryptography

56
 Example 1: RSA Cryptosystem

RSA: Rivest, Shamir and Adleman 1978

57
The RSA cryptosystem

58
RSA Encryption

59
RSA Encryption

60
PRACTICAL EXAMPLE

61
Modular exponentiation
 Modular exponentiation

Excel Table:

63
 Other goals of cryptography

Confidentiality: Only the authorized recipient will have the

possibility to decrypt and read encrypted data
by the sender.
Integrity: assurance that the received data has not been altered.
were modified during transmission
Authentication: identification of individuals or
entities that communicate and certification of this
identity.
Non-repudiation: inability to deny having
complete this act of communication
64
 Hybrid Cryptography

Public key cryptography requires

a lot of calculation so a time cost
high.
In practice, we use cryptography
hybrid: encrypt the keys with crypto at
public key, encrypt the data with the
secret key crypto that is faster.
Examples of hybrid protocols: PGP (Emails), SSL

65
 Example2:
El Gamal encryption

66
 Example2:
El Gamal encryption

Clé publique: p premier, g < p, x = gsmod p.

Private key: s < p.
Encryption:
We choose k prime with p-1 and random
a = gkmod p
c = xkm mod p (m being the plaintext message)
Decryption:
m = c/akmod p

Exercise: verify the previous equality

67
 The El Gamal encryption:
Example

We take p = 181 and g = 23.

Let x = gsmod p = 237mod 181 = 57.
That is to say we take s=7
Public key: (181, 23, 57).
Private key: (7).
Let's suppose that the message to be encrypted is a
date: 31 12 2010
68
 The El Gamal encryption:
Example
Encryption:
We then take a random number k that is coprime with p-1,
example 11 we then determine:
a = gkmod p = ? mod 181 = 131 mod 181.
Then we encrypt each element of this table by multiplying.
by xkmod p = 83 mod 181 :
31 × 83 mod 181 = 39 mod 181
12 × 83 mod 181 = 91 mod 181
2010× 83 mod 181 = 129 mod 181
This gives the table: [ 39, 91, 129 ]
Then we send the message: 3991129, as well as to: 131.
69
Hash functions
Electronic signature
Definition of a hash function

71
Examples of hash functions

72
Cryptographic Hash Functions

73
Cryptographic Hash Functions

74
Objectives of cryptography achieved
by hashing functions

75
Sizing of the number of bits of a
hash function

76
Sizing of the number of bits of a
hash function

77
Sizing of the number of bits of a
hash function

78
Electronic Signature Scheme

79