Cryptography - Pr Aziz Ifzarne

MODULE: Cryptography
This course is an introduction to cryptography. It allows you to acquire the
theoretical knowledge necessary for a good understanding of the
cryptography. This knowledge allows for the protection of messages in order to
CRYPTOGRAPHY better secure information systems.

Evaluation
Written exam: 70%
Projet : 30%

Program
I. Introduction: Basic notions of cryptography (history, encryption and
decryption, cryptanalysis, qualities of a cryptosystem, ...
II. Ancient Cryptography
Introduction
2. Transposition Cipher
3. Substitution cipher
III. Modern Cryptography
4. Asymmetric encryption
5. Symmetric encryption
Project: Programming an encryption algorithm
3

1
Cryptography - Pr Aziz Ifzarne

Issue What is cryptography?

Since ancient Egypt, humans have wanted to be able to exchange information in a way Origin of the word:
confidential.
Cruptos: caché, dissimulé ;Graphein: écrire
There are many areas where this need is vital:
Cryptography
military (on a battlefield, protecting access to atomic weapons, ...)
Cryptography is the art of making unintelligible (incomprehensible), of encrypting,
—commercial (protection of industrial secrets) ; coder, a message for those who are not authorized to be aware of it.
banking (protection of information related to a financial transaction);
Cryptography is traditionally used to conceal messages from view.
— of privacy (protection of messaging between individuals); of certain users. This use is today of even greater interest because
internet communications travel through infrastructures that we cannot
—diplomatic (the famous 'red telephone' between the United States and the Soviet Union);
ensure reliability and confidentiality.
Cryptography is a tool that allows achieving security objectives.
(other tools include antivirus software, hardware, etc.)
5 6

Message chiffré et message en clair Encryption and decryption

The act of coding a message to make it secret is called encryption.
Cryptography is essentially based on arithmetic. The inverse method, which consists of recovering the original message, is called
deciphering.
In the case of a text, it is about transforming the letters that
compose the message in a succession of numbers, then afterwards of Le chiffrement se fait généralement à l'aide d'uneclef de chiffrement,
make calculations on these figures to modify them in such a way as to decryption requires a decryption key.
make incomprehensible.
The result of this modification (encrypted message) is called
cryptogram (in English ciphertext) as opposed to the message
initial, called clear message (in English plaintext).

7 8

2
Cryptography - Pr Aziz Ifzarne

Encryption and decryption functions

Cryptanalysis and cryptology
A sender Alice wants to send a message to a recipient Bob while avoiding the
Cryptanalysis is the art for an unauthorized person to decrypt. Eve's prying ears and Martin's malicious attacks.
(decode, decipher) a message. It is therefore the set of attack methods. For this, Alice agrees with Bob on the cryptosystem they will use.
of a cryptographic system.
Let us be:
Thus, every cryptosystem must necessarily be resistant to methods of M: the clear text (the information that Alice wishes to convey to Bob).
cryptanalysis. When a method of cryptanalysis allows deciphering a
message encrypted using a cryptosystem, it is said that the algorithm of C: the encrypted message,
encryption has been "broken". E: encryption function defined by:
C = E(M).
Lacryptologieest la science qui englobe la cryptographie et la cryptanalyse.
D: decryption (or decoding) function. It is the process of reconstructing the
clear message from the encrypted message.
Cryptology = Cryptography + Cryptanalysis It is requested that for every clear message M:
D(C) = D(E(M)) = M

9 10

Ancient methods of cryptography:

Cryptographic algorithm Substitution and transposition
A cryptographic algorithm is the set of functions (mathematical or
not used for encryption and decryption. Ancient encryptions start from a message containing letters to
In practice, the E and D functions are parameterized by keys: a cryptogram containing letters as well.
Kela encryption key These methods are divided into two main families of encryption:
Kdla decryption key; 1) By transposition: Change the order of the letters in the plaintext, to
These keys can take one of the values from a set called the keyspace. obtain the encrypted text. We use the mathematical principle of
permutations.
We thus have the following relationship:
2) By Substitution: Replace the characters of the plain text with others
characters.

11 12

3
Cryptography - Pr Aziz Ifzarne

cryptography during the two Modern methods of cryptography

world wars
Nowadays, two main types of encryption are generally distinguished:
Just before the First World War occurred Symmetric encryption (private key): The same key must be used to encrypt and
place a technological revolution. The decipher the message. (Example DES code). Sender and recipient must exchange
communications between the staff and the this key, which must remain secret under penalty of a third party being able to decipher the
troops are now primarily made correspondences.
by radio. But these communications are
easily intercepted by the enemy. It
They must be encrypted!
The work of the mathematician Alan Turing Asymmetric encryption (public key): One key is used for encryption and one
The encryptions will become automated, especially
with the birth of the first computer. to decipher the German messages another for decryption. (Example: RSA code)
encrypted by the German machine Enigma
permission to save several hundreds of
ships with their crews!
13 14

Modern applications of cryptography

Important principle (Kerckhoffs 1883)
Since the 1970s, cryptography is no longer just the business of the military.
Civil applications of encryption are becoming a fundamental driver of progress.
(banks, telecommunications, computing,...) The security of a cryptosystem should not rely on the secrecy of
the coding algorithm but only on the secret key.
Bank cards: Banks are among the first users of systems. This secret key is an easy-to-change parameter, of small size.
cryptographies. Bank cards generally have three levels of security (the code
confidential, RSA signature, DES authentication
(currently from 64 to 2048 bits) and therefore quite easy to transmit
secretly.
Web browsers: Browsers, or web browsers, such as Mozilla Firefox or Internet
Browsers use the SSL (Secure Sockets Layers) security protocol, which is based on a
public key cryptography method: RSA.

15 16

4
Cryptography - Professor Aziz Ifzarne

Essential qualities of a cryptosystem. Computational security

1) Confidentiality: only authorized individuals have access to the content. It is the computational security that is used in most assessments of
message. An attacker cannot see the message. security of cryptographic systems.
2) Authenticity: the recipient is sure of the identity of the sender, and Computational security relies on the impossibility of doing so in a time
reciprocally. reasonable, given the available computing power, the calculations
3) Integrity: the message cannot be altered by an attacker without us necessary to decrypt a message.
realize it. The notion of computational security is based on complexity theory.
Example: even with computers doing10 basic operations by
second, a calculation that requires2 elementary operations are out of
currently effective because it takes about 4 x to carry it out10 years!

17 18

Encryption
PART 1 by transposition
CRYPTOGRAPHY
Grid method
ANCIENT

5
Cryptography - Pr Aziz Ifzarne

Transposition Encryption Example: grid method (-450 BC)

On veut envoyer le message suivant:
In transposition (permutation) encryption, we divide the text
MEET TOMORROW AT NOON IN VILLETANEUSE
in blocks, we keep the same alphabet but change the position of the letters The sender and the recipient of the message agree on a grid of a predetermined width.
(here a grid of 6 boxes wide, it’s the number of columns).
within a block (they are permuted).
The sender writes the message in the grid by replacing the spaces between words with the symbol □.

He reads the text in columns and thus obtains the encrypted message:
R□D□VAEVEMINNOMILEDUADLUESIIESZ□N□TE

21 22

Grid method with secret key

Exercise
In order to easily change the encryption of a message while
keeping the same coding algorithm, we add a secret key that Using the grid method and the key 'MASTER', encrypt the following message:
will indicate the order of reading of the columns. This too shall pass.
There are 6! different encodings.
For example, we choose the key: CAPTURE
We number the columns according to the
ranking of the letters of the word CAPTER in the alphabet:
2, 1, 4, 6, 3, 5
and we read the columns in the order indicated to find the message
encrypted
EVEMIN R□D□DAVA DUADLU Z□N□TE NOMILE ESIIES

23 24

6
Cryptography - Pr Aziz Ifzarne

Substitution encryption
It involves replacing the characters of the clear text with other characters.
Encryption The most common encryptions:
by substitution
Substitution monoalphabetic: consists of replacing each letter of the
message through another letter (Example: Caesar code, affine code)

Polyalphabetic substitution: involves the use of a sequence of encryption

monophonic periodically reused (Example: Vigenère cipher)

26

Why arithmetic?
arithmetic is at the heart of message encryption. To encrypt a message
we start by transforming it into numbers.
The process of encoding and decoding can involve several concepts.
Reminders of arithmetic:
Modular arithmetic Calculations in Z/nZ
Prime numbers and the decomposition into prime factors
Fundamental theorems such as Fermat's little theorem.

28

7
Cryptography - Professor Aziz Ifzarne

Divisibility and Euclidean division Congruence modulo n

Let a and b be two integers. We say that a divides b, or that a is a divisor of b, Let a and b be two relative integers and n a natural integer.
if there exists k∈Let b = ka. It is also said that b is a multiple of a. It is said that a and b are congruent modulo n, and we denote a ≡ b[n] (or a ≡ b (mod n)), if n divides a-b.
Remarks a is congruent to b modulo n⟺ n/a-b⟺ ∃ k∈Such that a−b=kn
(a/betb/a)⟹ b = ±a The equivalence class modulo n of an element x of Z is called, denoted ̅ , the whole of y
• (a/betb/c)⟹ air conditioning who are congruent to x modulo n: ̅ = { ∈ ℤ ∶ ≡ [ ]}
(a/beta/c)⟹ a/(b+c) On a : ̅= ⟺ ≡ [ ]⟺ ≡ [ ] ⟺ n/x-y.
Theorem (Euclidean division): Let a∈Z and b∈N*There exists a unique pair (q,r)∈Z2 There are n equivalence classes. The set of all equivalence classes is Z/nZ.
such that a=bq+r and 0≤r<b. Let the entire quotient of Z by the congruence modulo n.
q is called the quotient and r is called the remainder.
Z/nZ{0, 1, 2, … , n - 1}
r = 0 if and only if subdivides.

29 30

Modular arithmetic
Exercise
In Z/nZ, we can define addition and multiplication:
1) Calculate2018 in Z/7Z.
̅+ = + .̅ = .
2) Calculate213+ 17and213 − 17 in Z/7Z.
(Z/nZ; +, .) is a commutative ring.
3) Tracer la table de multiplication modulo 7 (Z/7Z)
Example. Addition and multiplication tables in Z/4 Z.

31 32

8
Cryptographie - Pr Aziz Ifzarne

Caesar Cipher
It is easier to manipulate numbers than letters.
To code, we replace each letter with its rank in the alphabet.
A=1, B=2, C=3,....,M=13, N=14,...,S=20,...,X=24, Y=25, Z=26
We are dealing with a monoalphabetic substitution code with a secret key. Julius Caesar
Substitution mono-alphabetic During the Gallic War, Julius Caesar used the following substitution code:
coded letter = clear letter shifted by 3
Caesar cipher Mathematically, this is written as:
encoded letter = clear letter + 3 modulo 26
The plaintext message
MEET TOMORROW AT NOON IN VILLETANEUSE
becomes
UHQGHC YRXV GHPDLQ PLGL YLOOHWDQHXVH

34

Caesar cipher with shift k Caesar decryption of shiftk

We can consider the entire family of codes: To decipher, you just need to go the other way, that is, to subtract.
coded letter = clear letter + k modulo 26 clear letter = coded letter - k mod 26
where k is an integer between 0 and 25 called the key of the code (the shift) The decryption function of Caesar shift k is:

Caesar cipher is simply an addition in Z/26Z.

The Caesar cipher function with shift k is given by:
Dkis the reciprocal bijection of Ck, which implies that for every x∈Z/26Z :

It is noticed that Dk(x) = C-k(x).

For example, for k = 3: C3(0) = 3, C3(1) = 4...

35 36

9
Cryptography - Professor Aziz Ifzarne

Exercise Special case: Rot 13

Avec le code de César de décalage 8, chiffrer le mot «SOS». A classic example is 'rot13' (for rotation by a shift of 13):
Indication: C13(x) =x+ 13

Use the MOD function in Excel: and since -13 ≡ 13 (mod 26) then D13(x) = x + 13.
MOD(x;y) returns the remainder of the division of x by y. The decryption function is the same as the encryption function!

37 38

Cryptanalysis of the Caesar cipher Another more secure mono-alphabetic code

The shift is called the encryption key, it is the information necessary to To better secure the Caesar code, each letter is now associated with
Encrypt the message. There are therefore 26 different keys and the key space is Z/26Z. another letter (without fixed order or general rule). For example:
There are therefore 26 possibilities for encryption using the Caesar method.

It is clear that this Caesar cipher has very weak security. To encrypt the message
If Linda sends a secret message to Sara and Farid intercepts that message, he TO BE OR NOT TO BE THAT IS THE QUESTION
it will be easy for him to decrypt it even if he does not know the secret key.
The simplest attack for Farid is to test what each of the 26 produces. we look at the correspondence and replace the letter E with the letter X, then the
possible combinations and to recognize among these combinations which one letter T by letter G,..
give a comprehensible message. The encrypted message is then:
THIS IS AN EXAMPLE OF ENCRYPTED TEXT

39 40

10
Cryptography - Pr Aziz Ifzarne

Cryptanalysis of a mono-alphabetic substitution cipher:

Space for keys Frequency analysis technique (Statistical attack)

Mathematically, there are 26! possible keys. This amounts to about 4 x10 keys. The main weakness of monoalphabetic encryption is that the same
The letter is always encrypted in the same way.
There are more different keys than grains of sand on Earth!
A cryptanalysis technique used to attack an encryption by
If a computer could test 1,000,000 keys per second, it would then take substitution mono-alphabetical relies on frequency analysis of
12 million years to list everything. symbols used in the encrypted text. It uses the fact that, in every language,
certain symbols or combinations of symbols appear more
more frequently than others.
If the encrypted message is long enough, the search for a symbol having
A high frequency will sometimes allow you to recover all or part of the message.
clear associated.
In French, the most commonly encountered letters are in the order:
ESAINTRULODCPMVQGFHBXJYZKW

41 42

frequencies of letter occurrence in French

Exercise
For a written text
in French, we
Decrypt the following phrase encrypted by mono-alphabetic substitution:
let's obtain THE QUICK BROWN FOX JUMPS OVER LAZY DOG
generally the
frequencies
of appearance (in
percentage) close
the following values:

43 44

11
Cryptography - Pr Aziz Ifzarne

Monoalphabetic substitution cipher

Advantage:
The key space is gigantic and it is no longer a question of enumerating all the
possibilities.
Disadvantages: Substitution mono-alphabetic
the key to remember is much longer, as it is necessary to share the composed key Affine code
of the 26 letters
The fact that a letter is always encrypted in the same way represents too
great weakness. This encryption protocol is quite easy to 'crack' by a
statistical attack. Polyalphabetic encryption (for example Vigenère)
remedy to this problem.

45

Affine cipher (extension of the Caesar code)

Exercise
Affine encryption is a monoalphabetic substitution encryption system. We consider the affine code in Z/26Z with a = 7, b = 5.
more general alphabetical than that of Caesar.
1) Show that 7 is invertible in Z/26Z.
The key consists of a pair of integers (a,b)∈ (Z/26Z) × (Z/26Z), with a invertible (Indication: 26x3 - 11x7 = 1)
in Z/26Z.
2) Deduce that this affine code is valid.
An affine code over this alphabet is a code whose encoding function is
3) Code the following phrase:
C: Z/26Z → Z/26Z
No worries
↦ +
Note: Use the MOD function in Excel to calculate the modulo in
Since it is invertible in (Z/26Z), this transformation is well a Z/26Z (the remainder of the division by 26)
permutation (bijection) of (Z/26Z).

47 48

12
Cryptography - Pr Aziz Ifzarne

Weakness of monoalphabetic codes

The weakness of the Caesar cipher and generally of systems
mono-alphabetic means that a letter is always encrypted
in the same way. The frequency of the letters is therefore preserved.
which allows for easy cryptanalysis through frequency analysis.
Polyalphabetic substitution
Vigenère cipher To improve security, we can use a Caesar cipher in blocks.
in which we change substitution for each letter of a
block. This gives us the Vigenère code, developed by Leon Blaise de Vigenère.
Batista Alberti in the 15th century and developed by Blaise de
Vigenère.

50

Vigenère Cipher: Example Vigenère Cipher: Method

We group the letters of our text into blocks, for example here in blocks of length 4: We set a block length of k, and we cut the message into blocks of k.
THIS PHRASE MEANS NOTHING letters.
Becomes CETT EPHR ASEN EVEU TRIE NDIR E A key is chosen consisting of numbers from 0 to 25: (n1, n2, ..., nk).
if we choose the key (3, 1, 5, 2) then for the first block "CETT": The encryption consists of performing a Caesar cipher, whose shift
a shift of 3 for C gives F depends on the rank of the letter in the block:
a shift of 1 for EdonneF, a shift of den1 for the first letter of each block,
a shift of 5 for the first T gives Y a den2 offset for the second letter of each block,
• a shift of 2 for the second T gives V. • ...
Thus "CETT" becomes "FFYV". We then continue with the second block, ... etc
a shift for the penultimate and last letter of each block.
Note: The two letters are not encrypted by the same letter.

51 52

13
Cryptography - Prof. Aziz Ifzarne

Vigenère cipher: encryption function Cryptanalysis of the Vigenère cipher

The encryption function associates a block of length k with another block of The Vigenère cipher will remain unbroken for several
length, which gives:
centuries.

Charles Babbage carried out a true cryptanalysis of the

Each of the components of this function is a Caesar cipher.
Vigenère cipher around 1854.
The decryption function is correct:

53 54

Exercise 1: Encryption
With the Vigenère code, encrypt the text 'SECRET' with the key
TOP

Substitution poly-alphabetic
Exercise 2: Decryption
Hill cipher
Decode the following text by hand using the Vigenère cipher.
utilisant le mot-clef «BIEN » (équivalent numérique 1 8 4 13):
CZEIP

55

14
Cryptography - Pr Aziz Ifzarne

Reminder:
Determiner
Inverse of a matrix

58

59 60

15
Cryptography - Pr Aziz Ifzarne

The sign (-1)i+j can be quickly evaluated starting from square a11with a
sign + and by switching to the opposite sign each time when moving by one
61 move horizontally or vertically to the a squareij. 62

63 64

16
Cryptography - Pr Aziz Ifzarne

65 66

67 68

17
Cryptography - Pr Aziz Ifzarne

Hill Cipher
On décrit maintenant un autre système cryptographique appelé chiffrement de Hill. Ce chiffre Case m=2: Encryption
published in 1929 by Lester S. Hill (1891-1961) is polyalphabetic.
The idea is to transform m characters from a block of clear text into m characters of a block
of text encrypted by linear combinations.
We take a square matrix of size mxm as key K.
For x = (x1; … ; xm) a block of clear text in m characters and y = C(x) = (y1; …. ; ymthe block of
encrypted text, we have:

69 70

Decryption
Conditions for application of the code
A matrix K with coefficients in Z/nZ is invertible.
if and only if its determinant is invertible modulo n,
That is to say, gcd(det K; n) = 1.

In our case, for the matrix K to be invertible modulo 26, we must have
gcd(det K, 26) = 1, that is to say, det K and 26 are coprime (do not have
the positive common divisor other than 1.
Otherwise, it is necessary to check that (ad–bc) is odd and not a multiple of 13.

71 72

18
Cryptography - Pr Aziz Ifzarne

Encryption
Example Each letter is replaced by its rank. Then we encode the message:
THIS IS A TEST
Using a matrix whose determinant is coprime with 26, we seek to
encrypt the following message: We group the letters in pairs, thus creating 7 vectors of dimension two, the last pair being
arbitrarily completed:
TEXTENCRYPT
We take:
We then multiply these vectors by matrix A while working on congruences modulo 26:

whose determinant is 21. Since 5 × 21 = 105 ≡ 1 (mod 26), 5 is an inverse We then obtain 7 vectors, or 14 letters. The first vector is (25; 0). The first two letters
the det(A) modulo 26. encoded are therefore "ZA".
Question: Find the entire encrypted text. How can we decrypt this text?

73 74

Exercise Encryption using a coding matrix

ExampleConsider the message
PREPARE TO NEGOTIATE
A type of code that is extremely difficult to
decipher, uses a coding matrix.
For example, let the coding matrix be:

75 76

19
Cryptography - Pr Aziz Ifzarne

Encryption using a coding matrix Encryption using a coding matrix

We assign a number to each letter of the alphabet:

Since we are using a 3x3 matrix,
A = 1, B = 2, … , Z = 26
we break down the message into a sequence of
Space between two words = 27 3x1 vectors:

77 Note: to complete the last vector, we add a space. 78

Encryption using a coding matrix Encryption using a coding matrix

We encode the message by multiplying the matrix of Coded message
vectors by the coding matrix.

The columns of this matrix give the coded message:

PREPARE TO NEGOTIATE

79 80

20
Cryptography - Professor Aziz Ifzarne

Encryption using a coding matrix Encryption using a coding matrix

Decoding the message Decoding the message

The columns of this matrix, written in linear form,

give the original message:

81 82

Exercise: Encryption using a coding matrix

Encrypt then decrypt the message 'NOT TOMORROW' using the following coding matrix: PART2
CRYPTOGRAPHY
MODERN
We assign a number to each letter of the alphabet:
A = 1, B = 2, … , Z = 26; Space between two words = 27

83

21
Cryptography - Pr Aziz Ifzarne

Modern methods of cryptography

Nowadays, we generally distinguish between two types of encryption:
Symmetric encryption (private key): The same key must be used for encrypting and
decrypt the message. (Example DES code). Sender and recipient must exchange
this key, which must remain secret under penalty of a third party being able to decipher the
Cryptography
correspondences.
symmetric
Asymmetric encryption (public key): One key is used for encryption and another
another for decryption. (Example: RSA code)

85

Symmetric encryption (private key) Types of symmetric encryption

Symmetric cryptography, also known as private key (as opposed to There are two main categories of modern encryptions. The main one
asymmetric cryptography allows both encryption and decryption of The difference comes from the cutting of the data into generally fixed-size blocks.
messages using the same keyword.
The sender and recipient must exchange this key, which must remain secret.
provided that a third party manages to decipher the correspondences. 1) Stream cipher encryption (in English: stream cipher):

2) Block encryption (in English block cipher)

87 88

22
Cryptography - Pr Aziz Ifzarne

1. Stream encryption 2. Block encryption

This encryption can handle data of any length and does not need to Each clear text is divided into blocks of the same length and encrypted block by block. The size of
cut The block is between 32 and 512 bits. The blocks are then encrypted one after the other.
In the mid-1990s, the standard was 64 bits, but since 2000 and the AES competition.
the standard is 128 bits.
Examples:
A5/1, algorithm published in 1994, used in GSM mobile phones, Examples.
RC4, the most widespread, designed in 1987 DES (Data Encryption Standard): DES transforms a 64-bit block into another 64-bit block. It
manipulates individual 56-bit keys. This system is based on the Feistel scheme (named after
E0 used by the Bluetooth protocol. by Horst Feistel). Designed in the 1970s, the use of DES is no longer recommended today,
due to its slowness in execution and its too small key space allowing an attack
systematic in a reasonable time.
AES (Advanced Encryption Standard), the replacement for DES. Since 2000, it has become the
new encryption standard for organizations of the United States government. It is
currently the most used and the safest
Blowfish, Serpent, and Twofish, alternatives to AES.

89 90

The disposable mask (Vernam cipher)

The disposable mask, also known as the Vernam cipher, is a stream encryption invented
by Gilbert Vernam in 1917. This encryption consists of combining the plaintext with a key

Example of symmetric encryption presenting the very specific characteristics as follows:

The key must be a string of characters at least as long as the message to be encrypted.

The characters composing the key must be chosen completely randomly.

THE DISPOSABLE MASK Each key, or "mask", should only be used once (hence the name mask.
disposable).

92

23
Cryptography - Pr Aziz Ifzarne

Simplicity and absolute theoretical security Disposable mask: hand method

The method of combining the light and the key is simple enough to
to be employed "by hand" without any computer, mechanical or other device.
It will be described below. Suppose the retained random key, or 'mask', is:
The considerable interest in this encryption method is that if the three rules WMCKL
if strictly adhered to, the system offers theoretical security
absolute, as proven by Claude Shannon in 1949. This key is chosen in advance between the two people wishing to.
Although this encryption is theoretically impossible to break, it presents communicate. She is only known to them.
significant implementation difficulties that make it impossible to use
in many cases such as securing exchanges on the Internet.

93 94

Encryption Decryption
We want to encrypt the message 'HELLO'. To do this, we assign a number (by It is done in a similar way, except that the mask is subtracted from the text.
example from 0 to 25) to each letter. Then we add the value of each encrypted instead of summing it. Here again, we may add 26 to the
letter with the corresponding value in the mask (modulo 26 calculation): result to obtain numbers between 0 and 25:
HELLO 3 (D) 16 (Q) 13 (N) 21 (V) 25 (Z) encrypted message
+ 22 (W) 12 (M) 2 (C) 10 (K) 11 (L) mask
- 22 (W) 12 (M) 2 (C) 10 (K) 11 (L) mask
29 16 13 21 25 mask + message
-19 4 11 11 14 encrypted message - mask
= 3 (D) 16 (Q) 13 (N) 21 (V) 25 (Z) mask + message mod 26
HELLO encrypted message - modulo 26 mask
The initial message 'HELLO' is indeed found.
The text received by the recipient is 'DQNVZ'.

95 96

24
Cryptography - Pr Aziz Ifzarne

2. Disposable mask: Computerized method

When the data is computerized, thus converted into binary form, the plaintext message, at
ciphering is presented as a sequence of bits. The key is another sequence of bits, the same
length.
The bits of the plaintext are processed one by one, combining each with the bit of the same rank in the key.

Call A a bit of the clear and B the bit of the same rank of the key. Encryption consists of calculating
a bit C by performing the exclusive OR function, noted XOR (eXclusive OR), on A and B. This is
defined by the following table, which indicates for all possible values of A and B the value of
result, which we denote A⊕ B :
A B C = A⊕ B
0 0 0
0 1 1
1 0 1
1 1 0

97 98

Encryption and decryption Example

Encryption: To encrypt, we calculate C = A⊕ B. The result is the figure of A. Here is a numerical example of the previous method:
The operation is performed for each bit of the plaintext with the corresponding bit of the key.
A= 0110101011010100 (plain text message)
Decryption is done by combining the ciphertext C with the key bit B through simple
operation :C⊕ B. It turns out that she gives back the clearA, as we will demonstrate. B= 0101011011100110 (the key; to keep secret of course)
It should be noted that the XOR operation has the following two properties, which are easy to verify:
So: A⊕ B = C. The 'C' represents the encrypted message:
A⊕ A=0 ; A⊕ 0=A
Encryption: C=A⊕ B= 0011110000110010 (encrypted message)
The decryption calculation can therefore be written as:
Decryption: A=C⊕ B= 0110101011010100 (decrypted message)
C⊕ B= (A⊕ B)⊕ B=A⊕ (B⊕ B) =A⊕ 0=A
It is good to find the bit of clearA. The application of the XOR operation is simple in
In computing, these processes can be carried out at very high speed.

99 100

25
Cryptography - Pr Aziz Ifzarne

Applications Disadvantages of disposable masks

This encryption system was used for the red phone, in Difficulty in producing a perfectly random key: Perfectly random keys do not
cannot be produced by a computer through a simple calculation: indeed, this calculation is
send a telex directly linking the Kremlin to the White House, deterministic, whose result is completely predictable when you know the algorithm and the
initial data.
keys passing through diplomatic bags.
Problem of the unique use of each key: The risk posed by the reuse of one
All symmetric ciphers use the XOR operator. the key is easy to show.
Let it be a message M1masked
thanks to the keyK, we obtain the cipherC1Let us suppose that another
The new high-security cryptography algorithm AES in messageM2be encrypted with the same mask K, providing the encrypted C2We have:
particular, it uses a very large number.
It's dangerous, because any masking effect of the key K has disappeared. If, for example, an adversary ...
knows the two encrypted messages and one of the plaintext messages, he can find instantly
the second message in plain by calculation:

101 102

Exercises Exercises
Exercise 1. Exercise 2.
Avec le code de Vernam, déchiffrer le mot « SSXHMAZCUA » en utilisant la clé "SHRTVSGVIW". Encrypt the message 'SOS' using the one-time pad method, going through binary code
(See the ASCII table below) and using the XOR operator. Take 'YEN' as the key.
How do we find the plaintext? Justify your answer.
Decipher the message.

103 104

26
Cryptography - Prof. Aziz Ifzarne

DES (Data Encryption Standard) - 1976

DES is a symmetric encryption developed in the 1970s by IBM. The DES method was
adopted and made standard by the United States government. It uses keys of a size of

Symmetric cryptography
56 bits which makes it easy to break today with new cryptanalysis technologies.
Principle of the algorithm

DES & AES The algorithm uses a 56-bit key. The number of keys is:
2^56=72,057,595,037,927,936
The plaintext is divided into blocks of 64 bits that will be encrypted one by one.
The algorithm is based on easy operations (a total of 19 steps) to be performed by a processor.
Offset;
— "or exclusive" ;
Transposition/copying

106

DES: Operating principle AES (Advanced Encryption Standard) - 1997

AES is a symmetric encryption standard intended to replace DES that

became too weak in the face of attacks. DES was replaced in 2001 by
the AES.
Also called Rijndael in the name of its two Belgian designers Joan
Daemen and Vincent Rijmen, AES became the new encryption standard.
for organizations of the United States government. He is currently the
the most widely used and secure symmetric code.
The AES
is a standard, free to use, without restrictions on use or patents;
is a block cipher algorithm (like DES);

107 108

27
Cryptography - Pr Aziz Ifzarne

AES: cryptanalysis

AES was designed to withstand classical attack methods.

Cryptography
AES has not yet been broken, even theoretically, in the sense that it asymmetric
There is no significantly more effective attack than a brute force attack.
brute force (testing each possible combination one by one).
(to public key

109

Public key cryptography

Code RSA
RSA Encryption Reminders in arithmetic

28
Cryptography - Pr Aziz Ifzarne

Euclidean Algorithm Example

Let's calculate the gcd of a = 600 and b = 124.

Let a∈Z and b∈N*. There exists a unique pair (q,r)∈Z2such as:
a = bq + r and 0 ≤ r < b.

Furthermore, we know that: a∧b=b∧r.

We deduce the following algorithm to calculate the gcd for a≥b≥0:
We set r0=a and r1=b.
For i∈N*yes ri=0, on pose ri+1 =0 Thus gcd(600, 124) = 4.
yes rI≠0, on note ri+1 the remainder of the Euclidean division of ri-1 by ri.
The last non-zero remainder is the gcd of a and b.

113 114

Exercise Coprime numbers

Calculate GCD(25872;484) It is said that two integers relative
are first among themselves
if their gcd is 1.

Example
6 and 35 are coprime.

115 116

29
Cryptographie - Pr Aziz Ifzarne

Bézout's theorem. Remarks

Let a, b be integers.
So there exist two integers u, v∈ Z such as If we find two integers u', v' such that au' + bv' = d, this does not imply
gcd(a,b).
au + bv = gcd(a, b). For example, a = 12, b = 8; 12 x 1 + 8 x 3 = 36 but gcd(a, b) = 4.

The integers u, v are Bézout coefficients. They are not

uniques. They are obtained by "backtracking" the Euclidean algorithm.

117 118

Example Exercise
Let's calculate the Bézout coefficients for a = 600 and b = 124. The left part is the algorithm.
of Euclid. The straight part is obtained from bottom to top.
Calculate the Bézout coefficients of 50 and 17.

Thus for u = 6 and v = -29, then 600 x 6 + 124 x(-29) = 4.

119 120

30
Cryptography - Pr Aziz Ifzarne

Modular inverse Properties

In Z/nZ, a class is invertible if there exists as such is invertible in Z/nZ⟺ gcd(x; n) = 1.

. = . If n is prime, then every non-zero element of Z/nZ is
In this case is called the inverse of inversible. (Z/nZ is called a field)
(y is said to be the inverse of x modulo n). Yes is not invertible in Z/nZ, then there exists call
This inverse is unique. We note it . what . = . is said to be a divisor of zero.
. = ⇔ ≡ ⇔∃ ∈ℤ + = Thus, every element of Z/nZ is either invertible or
divisor of zero.
121 122

Bézout's theorem Practical method for finding

(case of coprime integers) the modular inverse of n
If xy + nv = 1 then y is an inverse of x modulo n.
In other words, to find an inverse of x modulo n
Let (a,b)∈Z2. On a: returns to calculating the Bézout coefficients
associated with the pair (x, n).
a∧b=1⟺∃(u,v)∈Z2, au+bv=1.

123 124

31
Cryptography - Pr Aziz Ifzarne

Example Exercise 1. (Extended Euclidean Algorithm)

Let's find the inverse of 17 modulo 50.
1) Using the Euclidean algorithm, calculate the GCD of 120 and 23.
GCD(17;50) = 1, moreover, the calculation of Bézout's coefficients gives:
1 = 17x3 + 50x(-1) 2) With the extended Euclidean algorithm, deduce the coefficients of
So 17x3 ≡ 1 [50], hence the inverse of 17 modulo 50 is 3. Bézout (two integers such that 120u + 23v = GCD(120, 23))

3) Deduce the inverse of 23 modulo 120.

125 126

Prime numbers Properties

Every integer n > 2 has a divisor that is a number

An integer p≥2 is said to be prime first
if its only positive divisors are 1 and p. The set of prime numbers is infinite.
Two different prime numbers are coprime.
them.
Let a,b∈If z and p are prime. If p divides ab then p divides a or p divides b.

127 128

32
Cryptography - Pr Aziz Ifzarne

Prime factorization Note

The main reason why one chooses to say that 1
is not a prime number, otherwise there would not be
Every integer n≥2 can be written uniquely.
= ……
more uniqueness of the decomposition:
where p1<p2<⋯<prare prime numbers and α1,…,αk are in N*. 24 = 23x 3 = 1 x 23x 3 = 12x 23x 3 = .....
It is said that = …… is the decomposition into a product of
prime factors of.
Example: 24 = 23x 3

129 130

Modular exponentiation
The naive calculation of modular exponentiation mod n is as follows:
the number is multiplied by itself multiple times, and once by the integer beobtained, we calculate its
remaining modular of the Euclidean division algorithm.
However, this method is not practical for large numbers. The exponential
quick modular drastically reduces both the number of operations and the space in
memory required for the execution of modular exponentiation.

132

33
Cryptography - Pr Aziz Ifzarne

Fast modular exponentiation Reminder: convert from decimal to binary

First, you need to convert the exponent into binary notation, which means we write:

In this notation, the length of the string is in [Link] take the value 0 or 1
for all titles that 0 ≤ i < n - 1. By definition, an1= 1.

The valueandcan then be written:

133 134

Example: convert from decimal to binary

Exercise. (Modular exponentiation)
Calculate 5144721mod 17

Calculate 15617mod 437

135 136

34
Cryptography - Pr Aziz Ifzarne

RSA (1977) RSA: the most popular encryption

RSA encryption, named after the initials of its three inventors
Ronald Rivest, Adi Shamir, and Leonard Adleman, is in the world
an asymmetric cryptography algorithm (key system
public), which was described in 1977.
RSA has become a universal system
servant in a multitude
applications: operating systems
(Microsoft, Apple,…), smart cards
banking and of course the Internet network
to ensure the confidentiality of the mail
electronics. It is everywhere!

137 138

Principle of operation of RSA

The idea of genius (RSA) The RSA system is a public key system, which means that:
The calculation algorithm is not hidden, nor is the coding key (called the public key);
The knowledge of the recipient's public key allows everyone to
Easy emitters of encrypting the messages that can only be decrypted by the
p , q: nombres recipient, thanks to his secret key.
first having
n = p x q a name of
numbers >300
A public key system is based on the existence of one-way functions.
unique. It is easy to apply this function to a message, but
extremely difficult to find this message once you've got it
transformed.

Difficult
139 140

35
Cryptography - Pr Aziz Ifzarne

Advantage of the public key system

This type of systems having a decoding key different from the encoding key THE RSATHEOREM
(asymmetric system) has an advantage over classical systems (called
symmetric, the same key is used for both encoding and decoding) because the Let p and q be two prime numbers and n=pq.
Two interlocutors do not need to meet to agree on a key.
secret and even less to take the risk of circulating it. Only the key Let e be an integer prime with φ(n) = (p-1)(q-1)
public, insufficient for decryption, is known prior to exchanges (φ(n) the Euler indicator enn).
encrypted.
Then there exists a natural integer d such that
ed = 1 mod φ(n) and for every integer M:
M = Medmod (n)

Ingredients of the proof (mathematics of the 18thcentury):

Little Fermat's theorem, Euler's formula, Bézout's theorem

141 142

RSAAlgorithm: Key Generation

1) Choose two prime numbers and calculate their product n=pq;
2) Calculate φ(n) = (p-1)(q-1); (this is the value of the indicator)
of Euler enn)
3) Choose a natural number n that is prime with φ(n) and strictly less than
φ(n), called the encryption exponent;
4) Calculate the natural integer d, the inverse of e modulo φ(n) called the exponent
decryption (extended Euclidean algorithm).

143 144

36
Cryptography - Pr Aziz Ifzarne

Keys RSAAlgorithm: Encryption and Decryption

The first comes with φ(n), according to Bézout's theorem it Encryption:
there exist two integers such that If M is a natural integer representing a message, then the encrypted message
will be represented by the natural integer C:
ed + kφ(n) = 1
that is to say queed ≡ 1 (mod φ(n)): is well invertible modulo
φ(n). Decryption:
To decrypt C, we use d and we recover the plaintext message M by:
The pair (n,e) is the public key of the encryption, while the
private sacred numbers.

Technique used: modular exponentiation

145 146

Simple example (small prime numbers)

We choose two prime numbers p = 3, q = 11;
Their product = 3 × 11 = 33 ;
φ(n) = (3 – 1) × (11 – 1) = 2 × 10 = 20 ;
we choose = 3 (first with 20);
The inverse of 3 modulo 20 is d=7 (extended Euclidean algorithm).
Encryption of M = 4: C = Memod n = 4331 mod 33
Decrypting C: M = Cdmod n = 317≡ 4 mod 33, (we find the
message initialM= 4).
To know p & q to know head waiter to know Mr.
147 148

37
Cryptography - Pr Aziz Ifzarne

TD - RSAEncryption
Quantum alternative? Exercise 1. (Extended Euclidean Algorithm)
1) Using Euclid's algorithm, calculate the GCD of 120 and 23.
Peter Shor (1994): With a quantum computer, one can
efficiently factor integers (response time 2) With the extended Euclidean algorithm, deduce the coefficients of
Bézout (two integers such that 120u + 23v = GCD(120, 23))
polynomial).
3) Deduce the inverse of 23 modulo 120.
Security experts estimated several dozens
years required for a quantum computer to
to break a 2048-bit RSA encryption, and have developed Exercise 2. (Modular exponentiation)
of encryptions that even a quantum computer does not Calculate 15617mod 437
will not be able to crack.
Calculate 5144721mod 17

149 150

Exercise 3. For p = 19 and q = 23, find among the exponents of

encryption following those that are valid: e = 9; e = 14 and e = 17.
For these valid exponents, determine the exponents of
deciphering.

Exercise 4.
The exchange algorithm
1) Let's take p = 29; q = 31 and e = 13: Use the RSA protocol to
Diffie-Hellman keys
encrypt and decrypt M = 123.
2) Same question for p = 47; q = 59 and e = 17.

151

38
Cryptography - Pr Aziz Ifzarne

Public key codes and computational difficulty

The Diffie-Hellman algorithm - 1976
Diffie and Hellman introduced the concept of public key cryptography around 1976. In parallel to their discovery of the principle of the
on computational difficulty (one-way function). public key cryptography, Diffie and Hellman proposed
in 1976 a totally secure key exchange protocol
The other most used asymmetric codes: secured.
•RSA based on the computational difficulty of factorizing large integers. This discovery by Diffie and Hellman is a true
revolution in the history of cryptography. The problem
The ElGamal is based on the computational difficulty of calculating the discrete logarithm. the exchange of keys is indeed resolved. This idea was worth in
in a finite body. 2015 to the two authors the Turing Award.
Menezes-Vanston based on the logarithm associated with the group of points The goal is to enable the establishment of a private key.
of an elliptic curve over a finite field. It is a modification of others between two parties, using messages sent over a
cryptosystems, such as El Gamal. unsecured channel. In addition, anyone who intercepts
these transmitted messages must not be able to deduce the key
generated.

153 154

Reminders about the group of invertible elements of Z/nZ

Problem position
The problem is as follows: * whole of
Let n be a non-zero natural integer. We denote Z/nZ.* (ouZn the
invertible elements of Z/nZ:
Alice and Bob want to exchange an encrypted message using a
algorithm requiring a key K. They want to exchange this key K, Z/nZ* = { , GCD(k, n) = 1.
but they do not have a secure channel for that. The protocol
It is a multiplicative group.
the Diffie-Hellman key exchange addresses this problem.
If p is prime then Z/pZ* is cyclic, i.e. finite and generated by a
only element
This protocol applies within the framework of a cyclic group.
particularly the multiplicative group Z/pZ* , with p a prime number.

155 156

39
Cryptography - Pr Aziz Ifzarne

Exercises Calculatory difficulty

Exo 1.
The Diffie-Hellman algorithm is based on the following postulate:
a) List all the elements of Z30 *.

b) Calculate the inverse of 13 in Z30

Exo 2.
Suppose that p is prime.
a) Show that every non-zero element of Z/pZ is invertible.
b) Deduce the number of elements in Z/pZ*.

157 158

Key exchange steps Example

Alice and Bob choose a prime number p = 23

and a generator a = 3
Alice chooses a secret number x1= 6 and Bob chooses
in turn a secret number x2= 15.
Give the steps of the Diffie-Hellman protocol
and find the exchange key.

159 160

40
Cryptography - Prof. Aziz Ifzarne

1. Alice and Bob chose a prime number and a generator a. In our

Exercise
exemple,p=23 eta=5 Alice and Bob use the Diffie-Hellman protocol to
2. Alice chooses a secret number x1=6 exchange the key. They choose a prime number p = 233 and a
She sends Bob the value.1= ax1[modp] = 56[23] = 8 generator a = 45.
[Link] takes his turn to choose a secret number x.215

5. Bob sends the value to Alice2= a [mod 15 19

x2 p] = 5 [23] = Alice chooses a secret number x1= 11 and Bob takes his turn
6. Alice can now calculate the secret key: y2x1[mod p] = 196[23] = 2 a secret name x2= 20.
7. Bob does the same and obtains the same key as Alice:
What is the exchange key?
y1 x2[mod p] = 815[23] = 2
The secret key is therefore K=2

161 162

Confidentiality Applications
Confidentiality is guaranteed by the fact that a potential attacker, who The Diffie-Hellman algorithm is a key exchange algorithm,
would intercept the communications between Alice and Bob, would have no way to used notably when opening a connection to a site
retrieve the private key from the information transmitted publicly. secured via the SSL/TLS protocol.
At the end of the protocol, Alice and Bob are therefore in possession of the same key.
secret K, which they did not exchange directly. If someone has spied on their It is also used for matching problems of two
conversations, he knows p, a, y1 and y2. He cannot find K as they do. objects in Bluetooth technology.
Alice or Bob. x1 and x2 being very large numbers, it is indeed extremely
difficult to retrieve their values from the information transmitted in plain text
(discrete logarithm problem).

163 164

41
Cryptographie - Pr Aziz Ifzarne

Public key encryption vs private key encryption

The major problem with symmetric encryption (AES by

example) is the need to share the key. We must transmit the
Symmetric cryptography securely shared keys (on an authenticated channel).
The major problem with asymmetric encryption (RSA by
For example, its slowness is due to the complex calculations involved.
partners, while symmetric cryptography shines through its
Asymmetric cryptography speed. This makes the use of asymmetric encryption.
costly, since such encryption cannot be applied on
a large amount of data to transmit.

166

Hybrid cryptography: Compromise between the two encryptions

FUNCTION
To overcome this flaw, one resorts to hybrid cryptography that combines the two.
systems in order to take advantage of the benefits (speed of symmetric cryptography
for the content of the message) and use of 'slow' cryptography

HASHING
only for the key.
In many modern communication environments, including
Internet, most of the exchanged data is encrypted by the symmetric algorithm
fast AES. Its private key, called the session key, is encrypted with the algorithm
asymmetric RSA.
Private key code: Encryption and decryption of the message
Public key: Encryption and decryption of the key

167

42
Cryptography - Prof. Aziz Ifzarne

Hash function Properties of a hash function

The hash function must be:
A hash function h is a function that allows associating each —deterministic: it associates one and only one summary to a plaintext.
input data an output data, called summary. —one-way (one-way function): that is, it is impossible to retrieve the
The input data of these functions is often called a message. Original message from the summary. It is said that it is resistant to the preimage.
englishInput) y = h(x), but it is impossible to retrieve x from y!
The output value is often referred to as summary, hash value, fingerprint. collision-resistant: that is to say, two distinct messages must have
digital, footprint or also hashed (in English, message digest or very little chance of producing the same summary. This means that the slightest
digest, hash. modification of the document leads to the modification of its summary. The ideal is that h
This function must have certain properties. it is injective but it is far from being true. We say that h is resistant to the second
preimage.
Difficult to find different m1 and m2 such that h(m1)=h(m2)

169 170

Properties of a hash function

Authentication and integrity
A hash function h transforms an input
data (Input) of a variable dimension 'm'
and gives as a result a data output Hashing algorithms are used in the generation of signatures.
(Digest) lower and fixed h(m). digital. Hashing ensures:
Integrity: that is to check if a document has been modified (the change of a part
The entrance can be of variable size; the document changes its fingerprint;
the output must be of fixed dimension; — Authenticity: the recipient is sure of the identity of the sender, and
reciprocally.
h(m) should be relatively easy to calculate;
h must be a one-way function;
The most commonly used hash functions today are SHA-2 (Secure Hash Algorithm). It is
— it must be almost "collision-free". a family of hash functions that includes SHA-256 (32 bits) and SHA-512 (64 bits).

171 172

43
Cryptography - Pr Aziz Ifzarne

Digital signature
Digital signature (or electronic signature) is a mechanism
ensuring the integrity of an electronic document and
to authenticate the author, by analogy with the handwritten signature of a
paper document.
The signature is obtained by first applying a hash function to the
then encrypt the summary using a key (private or public).

Hashing Encryption
Document ----------------> Résumé ------------------> Signature

173

44