Mohammed I University

Higher School of Technology

Oujda

Made by: Directed By:

Mohamed EL HAMDAOUI Mr. BENAZZI
Zouhaire EL AKIOUI

Department: Field:
Computer science TR & ASR
Cryptography

2
 Cryptography

Introduction

I- Definition
II - History
Antiquity
Middle Ages...................................................................................................................................................................................................................................................7
After 1800
III- Methods
Classical cryptography
Modern cryptography
IV- Use

Conclusion......................................................................................................................................................................................................................................................18
References .....................................................................................................................................................................................................................................................19

3
 Cryptography

Man has always felt the need to conceal information, even long before
the emergence of the first computers and calculating machines. Where the history of the
Cryptography is already old. Its use can be traced back to Egypt 4000 years ago.
However, for centuries, the methods used often remained very
primitives. On the other hand, its implementation was limited to the needs of the army and
diplomacy.

Encryption and cryptanalysis methods have seen significant development.

important during the Second World War and had a profound influence on the
course of this one.

But it is the current proliferation of communication systems that has brought to light the
military domain cryptography. Moreover, it has diversified demand and caused the
development of new cryptographic techniques. It is at the origin of a
rapid development over the last few decades, which does not seem to be slowing down
today, quite the opposite.

Moreover, the Internet has evolved so much that it has become an essential tool for
communication. However, this communication increasingly involves
problems of business economics present on the Web. Transactions made at
through the network can be intercepted, especially since laws struggle to be implemented
on the Internet, it is necessary to ensure the security of this information, it is the
cryptography that takes care of it.

4
 Cryptography

I-Definition:
Crypto: from the Greek kruptos "hidden", entering into the composition of many didactic terms,
notably of natural sciences and, more recently, of political terms.

Graphy: from the Greek graphein 'to write' forming part of many words.

Cryptography, according to the Grand Robert, is the graphical code that can be deciphered by the sender and the
recipient only.

In the scientific field, is defined as one of the disciplines ofcryptologyattaching to

protect messages (ensuresconfidentialityauthenticityeintegrityoften using secrets or
keys.

The word cryptography is a generic term referring to all the techniques that allow for
encrypting messages, that is to say making them unintelligible without a specific action. The
The verb 'crypter' is sometimes used but the verb 'chiffrer' is preferred.

Cryptology is essentially based on arithmetic.

This is a case of transforming the letters that make up the message into a succession of
numbers (in the form of bits in the case of computing as the operation of computers is based
on the binary), then to perform calculations on these numbers to:

on one hand to modify them in such a way as to make them incomprehensible. The result of this modification
(the encrypted message) is called a cryptogram (in English ciphertext) in contrast to the original message,
called plain text (in English plaintext).
make sure that the recipient will be able to decipher them.

II- History :

Cryptography underwent remarkable developments over the centuries, in this part we

describe the most important periods in chronological order:

Antiquity:

-1900: An Egyptian scribe used hieroglyphs that did not conform to the correct language in a
Kahn describes it as the first documented example of written cryptography.

-1500: A Mesopotamian tablet contains a coded formula for making varnish.

for the pottery.

5
 Cryptography

-487: The Greeks use a device called thescytaleSpartan" (stick of Plutarch) - a stick
around which a long and thin band of leather was wrapped and on which one wrote the
The leather was then worn as a belt by the messenger. The recipient had a
identical rod used to wind the leather to decipher the message.

-150: The Greek historian Polybius (circa 200-125 BC) invented the Polybius square, which
will later inspire many cryptosystems.

The principle:

We then replace each letter with its coordinates in the table, writing first the row,
then the column. For example, A is replaced by 11, B is replaced by 12, F by 21, M
by 32....

6
 La Cryptographie
-60,-50 :Julius Caesar (100-44 BC) used a simple substitution with the normal alphabet
(it was simply a matter of shifting the letters of the alphabet by a fixed amount) in the
government communications. This figure was less [Link] Atbash, but toa time when
very few people could read, that was enough. Caesar sometimes wrote by replacing the
Latin letters by Greek letters.

The Principle:

The principle is very simple: one replaces a letter with the next letter in the order of the alphabet. It
There are many variants: the shift can be more than one unit, or it can vary by one letter.
to the other (for example: the first letter is shifted by 1, the second by 2). We can also group the letters
by 4, etc. In short, loads of variations.

Middle Ages:

1512: Jean Trithème (father of first generation cryptography) wrote the first book
printed on cryptology. He invented a steganographic cipher in which each letter is
represented by a word. The resulting series of words resembles a prayer. He also described some
polyalphabetic ciphers in the now standard form of rectangular substitution tables.

1550: Jérôme Cardan invents the first autoclave process, but this system is imperfect and
it is ultimately another process that bears his name. The Cardan grid consists of a sheet of
rigid material in which windows have been cut out at irregular intervals
rectangular with the height of a line of writing and variable length. The encoder writes the text
in the windows, then remove the cover and fill the empty spaces with innocuous text. The
the recipient places the same grid over the encrypted text to read the hidden message.

7
 Cryptography

1563: Giovanni Battista Della Porta wrote De Futivis Literarum Notis. These four books, dealing with
respectively ancient numbers, modern numbers, cryptanalysis, characteristics
linguistics that favor decoding represent the sum of knowledge
cryptological methods of the time. Among the modern techniques, many of which are of his invention,
the first bigram substitution appears: two letters are represented by a single symbol.
He also invented the first polyalphabetic cipher. He was the first to classify the two principles.
major cryptographic techniques: substitution and transposition.

1585: Blaise de Vigenère wrote his Treatise on Ciphers or Secret Ways of Writing. He presents
among others a table of the Trithème type, which is wrongly referred to today as the Vigenère square.
This number was long considered undecipherable, a legend so tenacious that even in 1917, more
fifty years after being broken, the Vigenère was declared 'impossible to decrypt' by the very
serious Scientific American review.

After 1800:

The new communication technologies (fast means of transport, newspapers, telegraph,

wireless telegraphy) gives a new impetus to cryptology. Modern wars use
abundantly telecommunications; interception becomes simple and the decryption of information
becomes vital. Cryptology enters its industrial era.

1832: the first long-distance Morse message was sent, between Washington DC and
Baltimore (40 miles, 60 km) : "What hath God wrought" ("What God has forged").

8
 Cryptography
From there, the Morse took flight, and only 4 years later, most of the private companies
(Associated Press newspapers mainly) were already using this system.
Finally, it should be noted that - except for enthusiasts - Morse code will not see the 21st century.
actually, the International Maritime Organization decided to officially put an end to it at the end of 1999. It
It must be said that radio messages have already effectively replaced the use of Morse...
It's a whole era that is ending, that of the TSF, Wireless Telegraphy, which is very present
notably in Tintin (e.g., in The Blue Lotus, Tintin receives encrypted and coded messages in
Morse

1922: Thomas Jefferson invented his cipher cylinder, so well designed that after more than a century and
despite rapid technical progress, it was still in use. It was surely the method of encryption the
plus sûr de l'époque, et pourtant il fut classé et oublié. Il fut réinventé en 1891 par Etienne Bazeries,
which failed to have it adopted by the French army. The American army put into service a
almost identical system in.

During the 14-18 war, cryptography saw considerable growth. Mastery

French cryptography helps them considerably to decrypt enemy messages, their
gaining a very significant advantage over the enemy. A lieutenant would have almost succeeded on his own in
change the course of history. Referring to this lieutenant, Clemenceau would have claimed that he alone
it was worth an army corps. The speed of communications benefited from the advances of the 19th century, and
is now instantaneous, but the decoding of coded messages, done manually, remains very slow,
often several hours.

1918: Arthur Scherbius patents his encryption [Link].

The price of a copy was 20,000 pounds in current value.
This price seemed to discourage potential buyers.
It is worth noting that three other inventors, in three countries, had,
each on his side and almost simultaneously, had the idea of a
rotor-based machine: Hugo Alexandre Koch, Arvid Gerhard
Damm and Edouard Hugh Hebern.

9
 Cryptography

SGM: The machine Enigma was not a commercial success but it was taken up and improved for
become the cryptographic machine of Nazi Germany. It was broken by the mathematician
Polish Marian Rejewski, who based himself only on an encrypted text and a list of keys
daily obtained by a spy. During the war, the messages were regularly
decrypted by Alan Turing, Gordon Welchman, and others at Bletchley Park, England, using
of the first computers (the famous bombs).

Cryptology played a decisive role during World War II. The exploits of the Allies in
The field of cryptology could have shortened the war (by one to two years, according to some)
specialists). Churchill cited cryptography as one of the key factors of victory.

1976: DES, for Data Encryption Standard, is an algorithm

very widespread private key derivative of the Lucifer Feistel cipher (from IBM) in its 64 version
bits. It is used for cryptography and data authentication. It has been deemed too difficult to crack by the
United States government that it has been adopted by the United States Department of Defense which has
controlled its exportation since then. This algorithm has been studied intensively and has become
the best known and most widely used algorithm in the world to date.
Although DES is very secure, some companies prefer to use 'triple-DES', which is nothing
other than the DES algorithm applied three times, with three different private keys.

1977 :RSAstands for Rivest-Shamir-Adleman, in honor of its three inventors: Ron Rivest, Adi
Shamir and Leonard Adleman who invented it in 1977. The patent for this algorithm belongs to the
American company RSA Data Security, which is now part of Security Dynamics and to
Public Key Partners, (PKP in Sunnyvale, California, United States) who hold the rights in general
on public key algorithms. RSA is a public key algorithm that is used for both
document cryptography, as well as authentication. Thanks to the fact that it was public key, and to the fact
that it was very secure, the RSA algorithm has become a de facto standard in the world

1991: Phil Zimmermann releases his first version ofPGP(Pretty Good Privacy) in response to the
FBI's threat to demand access to citizens' plaintext messages. PGP offers high security to
citizen and it for free. PGP is indeed freeware and has quickly become a standard
worldwide.

10
 Cryptography
1999: 11 sites distributed in 6 countries factor the first ordinary number of 155 digits.
decimals (512 bits). Such a number could have been used as a key in an encryption system
modern type RSA, which is used in e-commerce. Such a record raises
questioning the use of keys that are too small in such systems.

2001: Rijndael adopted a developed algorithm that consumes little memory, easy to
implement and use keys of 128, 192, or 256 bits. It has become the replacement for DES and
3DES. The data is 'passed' 10, 12, or 14 times and between each round, it undergoes a
XOR mask, the XORed data is then reintroduced ... etc., AES (Advanced Encryption
Standard) is now used in Wifi security, compression tools, encryption of
volumes, It is the only algorithm allowed to bear the name AES.

III- Methods:

Classical cryptography:

The Greek technique:

The first major compilation of cryptographic and steganographic processes practiced during
Antiquity is a transposition cipher technique, meaning that it relies on the change of
position of the letters in the message, using a stick of a determined diameter calledscytale. On
was winding a strip of leather in a spiral aroundthe scytalebefore writing a message on it. Once unfolded,
the message was sent to the recipient who possessed an identical stick, necessary for decryption.
However, the use ofthe scytaleLacedaemonian as a cryptographic procedure is not explicitly
asserted that paPlutarchand Aulus Gellius, authors from the end of Antiquity, and is not mentioned by
Aeneas the Tactician.

The technique of the Hebrews:

From the Vandsiècle av. J.-C., l'une des premières techniques de chiffrement est utilisée dans les textes
religious by the Hebrews who know several methods.

The most well-known called Atbash is a method of reversed alphabetical substitution. Its name is formed
by the initials of the first and last letters of the Hebrew alphabet: aleph, tau, beth, shin.

It consists of replacing each letter of the plaintext with another letter from the chosen alphabet.
the following way: A becomes Z, B becomes Y, etc.

The first 'real' systems of cryptography:

We have to wait until -200 to see the first "real" cryptography systems appear. They are
essentially substitution ciphers.

There are 4 types of substitutions:

mono-alphabetic: replace each letter of the message with another letter from the alphabet
poly-alphabetic: uses a sequence of mono-alphabetic characters (the key) that is reused
periodically
homophonic: allows matching each letter of the plaintext to a possible set
other characters
11
 Cryptography
polygrams: substitute a group of characters in the message with another group of characters

The Caesar code:

The Caesar cipher is the oldest cryptographic method, by monoalphabetic substitution.

(Iercentury BC.

This method is used in the Roman army and although it is much less robust than the
Atbash technique, the low literacy of the population makes it sufficiently effective.

His system is simple; it consists of shifting the letters of the alphabet by a number. For example, if we
replace A with D (n=3), replace B with E, C with F...

shift the letters of the alphabet

is then: "ghfdohu ohv ohwwuhv gh o'doskdehw"

Unfortunately, we will understand that this system is very insecure, since there are only 26 letters in
the alphabet therefore only 25 ways to encode a message with the Caesar code (one cannot substitute
a letter by itself). Yet its simplicity led the southern officers to reuse it during the
Civil War. The Russian army did the same in 1915.

The Caesar cipher was used on internet forums under the name ROT13 (rotation of 13 letters or
A→N...). ROT13 is not meant to make text confidential, but rather to prevent reading.
involuntary (from a response to a riddle, or the plot of a movie, etc.). Its use is simple: it
It is enough to re-encrypt a text, coded in ROT13, a second time to obtain the plaintext.

The Polybius square:

The Greek historian Polybius is the originator of the first homophonic substitution cipher.
unique.

It is a transmission system based on a square of 25 squares (this square can be enlarged to 36 squares,
in order to be able to add numbers or to encode alphabets containing more letters, such as
the Cyrillic alphabet).

In French, we remove W, which will be replaced by V. There is a variant where I and J are the ones that replace.
share the same box. Each letter can thus be represented by a group of two digits: that of
its row and that of its column. Thus e= (1;5), u= (5;1), n= (3;4)...

Polybius suggested transmitting these numbers using torches. One torch on the right and five on the left.
to send the letter, for example. This process allowed for messages to be transmitted about
long distances.

12
 Cryptography
Modern cryptologists have seen in the '25 square' several extremely characteristics
interesting:

the conversion of letters into numbers,

the reduction of numbers, of symbols
the representation of each letter by two separate elements.

This encryption system can be complicated with a password. For example, if the password
is "DIFFICULT", we will start filling the square with the letters of this word, after having removed the
identical letters, then we will complete the table with the unused letters

Modern cryptography:

The private key algorithm:

Private key algorithms are also called symmetric algorithms. Indeed, when one encrypts
information using a symmetric algorithm with a secret key, the recipient will use the same
secret key for decryption. It is therefore necessary that both interlocutors have agreed on a
private key previously, by mail, by telephone or during a private interview. Key cryptography
public key, for its part, was invented by Whitfield Diffie and Martin Hellman in 1976 to avoid this
pre-shared secret key exchange problem.

The public key algorithm:

Public key algorithms are also called asymmetric algorithms. This means that for
To encrypt a message, we use the recipient's public key (known to everyone), who will presumably be the only one to
to decrypt it using his private key (known only to him).

Text-type information, or any other type of information, needs to be encoded first.

to be encrypted using a public or private key algorithm. In other words, it is necessary to establish a
correspondence between information and a number, since key algorithms (public or private) do not
can only encrypt numbers. The problem is easily solved, since most of the time, this type
Cryptography is essentially used on machines. And since the information anyway
On a machine are a sequence of numbers, the problem is already very simplified.

13
 Cryptography
The DES Algorithm:

D.E.S, for Data Encryption Standard, is a very

spread with a private key originally created by IBM in 1977. It is used for cryptography and authentication.
data. It was deemed so difficult to penetrate by the United States government that it was adopted by the
the United States Department of Defense which has since controlled its export. DES was conceived by the
IBM researchers to meet the demands of banks. It has been designed to be implemented
directly into the machine. Indeed, since the steps of the algorithm were simple but numerous, it
it was possible for IBM to create dedicated processors capable of encrypting and decrypting quickly
data with the DES algorithm. This algorithm has therefore been studied intensively over the last 15
years and has become the best-known and most widely used algorithm in the world to date.

Although DES is very secure, some companies prefer to use 'triple-DES'. Triple-DES is not
nothing more than the DES algorithm applied three times, with three different private keys.

The DES algorithm is a block cipher algorithm. In practice, it is used to encrypt a series of
64-bit blocks (8 bytes).

DES uses a 56-bit secret key, which it transforms into 16 'sub-keys' of 48 bits each. The crypt-
The event takes place over 19 stages.

Step 1: The first step is a fixed (standard) transposition of the 64 bits to be encrypted.

16 following steps: the 16 following steps can be divided into 2 'sub-steps' each. In a
first, the 64-bit block is divided into 2x32 bits, and a substitution is performed between these two
blocks, in fact, these two blocks will simply be exchanged with each other. In a second phase, the
bloc de 32 bits ayant le poids le plus fort (le bloc qui va du bit n°32 au bit n°63) subira une transposition
controlled by the subkey corresponding to the current step

Step 18 and 19: The last two steps are two transpositions.

14
 Cryptography
To decrypt a document that was previously encrypted with DES, simply perform the algorithm in reverse.
with the correct key. Indeed, it is not necessary to use a different algorithm or a different key.
since DES is as we have seen a symmetric algorithm. It is therefore totally and easily
reversible, if one has the secret key.

As we have seen, the DES algorithm only allows for 64-bit block encryption. To encrypt or
To decrypt a complete document, it is necessary to use DES in series in an 'operational mode'. There are
many operational modes, we will only look at the ECB mode and the CBC mode.

ECB: stands for Electronic Code Book. In this mode, we divide the
Document to encrypt or decrypt in 64-bit blocks that we encrypt independently of each other.
Since each plaintext block corresponds to an encrypted block for a given key, this may suggest a
catalog of codes

CBC stands for Chain Block Cipher.

previously, the ECB operational mode does not protect against the presence of redundant blocks, since they
are independently encrypted from one another. The second weakness is that a plaintext block, out of context,
and always encrypted with the same key, will always produce the same encrypted block.

The CBC, on the other hand, addresses these two issues. To do this, before encrypting a plaintext block, we will perform
an "exclusive or" between this plaintext block and the previously encrypted block. This will give us a new block.
clearly that which we will encrypt. In addition to having a common secret key, both parties must
from now on, agree on a starting block of 64 bits that we will call 'starting vector', or
initial vector

15
 Cryptography
The RSA Algorithm:

RSA stands for Rivest-Shamir-Adleman, in honor of its inventors: Ron Rivest, Adi Shamir and
Leonard Adleman who invented it in 1977. The patent for this algorithm belongs to the American company.
RSA Data Security, which is now part of Security Dynamics and Public Key Partners, (PKP to
Sunnyvale, California, United States) who generally hold the rights to public key algorithms.
RSA is a public key algorithm that is used for both document cryptography and
authentication. Thanks to the fact that it was public key, and due to the fact that it was very secure, the RSA algorithm is
became a de facto standard in the world.

The entire principle of RSA is based on the fact (which has still not been proven!) that it is very difficult and very
it is difficult to factor a very large number into two prime factors.

To begin with, we need to choose two very large prime numbers p and q (on the order of 100)
There are random prime number generation algorithms that exist. Then we
find the number n easily: n = p * q. Then we need to find an integer e between 2 and f(n).
f(n) is the Euler indicator function, it is actually the number of integers less than n that are prime.
with him, we have af(n)=(p-1)(q-1).f(n) is calculated very easily here, since we have apetq. Now that
We are ready to encrypt. The numbers here form our public key that we
Note. We need to calculate the number d that will be necessary for decryption. According to RSA theory,
We need to have d such that (e*d - 1) is divisible by n. To find d, we then need to solve
The Diophantine equation d + k * f(n) = 1 using arithmetic. Since f(n) and d are coprime,
Bezout's theorem proves that there exist integers k and d such that e * d + k * f(n) = 1.

We will be able to solve the equation using Euclid's algorithm. After solving, we will arrive at a class.
of the solution of the form r.f(n) + d0

To clearly prove that a document was composed by us, it will suffice for us to encrypt, for example, our
Name, First name and position or anything else, with our private key (theoretically known to us)
alone). Thus, anyone who wishes to verify the author of this document only needs to use our public key
for the decryption. And if the decryption works, it means that the signature has been 'forged' with
our private key.

Summary table of key management with RSA:

For ... we use ... Whose?

Send an encrypted document to someone the public key of the recipient
Send an encrypted signature to someone the private key from the sender
Decrypt a document the private key of the recipient
Decrypting a signature the public key from the sender

IV- Utilization:
Cryptography is almost used in all areas around the world, especially in the digital world.
and in this section, we will mention a few examples:

16
 Cryptography
The military woman:

Cryptography is a powerful auxiliary to military tactics.

war.)

From a historical point of view, the science of cryptography was created to ensure confidentiality.
military communications from which it was originally confused with military telegraphy, it has
cultivated since ancient times by the Chinese, Persians, and Carthaginians; it has been
taught in the tactical schools of Greece, and held in high regard by the most illustrious generals
romans.

Television:

Nowadays, most digital broadcasting channels adopt cryptography, such as the

Access control for television involves encrypting video data that should only be readable.
that only the users paying a subscription have access. The decryption is done using a terminal.l (Set-top
box) cholding the decryption module.
And as an example of these channels, we find Aljazeera-Sport, Multivision from France, Premier of
The German, Canal+ ...etc.

Telecommunication:

Telecom companies rely on cryptography to maintain security and protection.

the privacy of their clients, for example the GSM technology, SMS ...

The Economy:

This field, like the previous ones, has taken its share of cryptography, where bank cards contain
smart chips containing encrypted information known only by the client and the company.

Daily life:

Currently, it is observed that most identity documents issued by the administrations

Public and private are biometric that contain encrypted information.

17
 Cryptography

Finally, if cryptography is one of the basic building blocks of security, it is the most publicized.
given the secrecy that has long concealed its development and the best built,
since it can be likened to a branch of mathematics, it cannot stand alone
solve all security problems. Regardless of the strength of an algorithm or the
length of the keys used, there may be implantation issues (wanted or not)
in a system that makes it possible to retrieve the information protected by a
indirect means (when these "problems" are intentional, they are referred to as
backdoors). An assessment process for cryptographic products, taking into account
not only cryptographic complexity but also implementation modes, comes
to start under the auspices of the General Secretariat for National Defense (SGDN), but it is
a very heavy task, due to the volume and complexity of the software.

Moreover, cryptography does not protect systems: when a workstation is located

on a local network establishes a connection with the outside world, even if this connection
is protected, it can be used from the outside to carry out intrusions on the
machines on this local network, extract information from them or destroy them. It is necessary to put in
barriers (generally referred to as firewalls) featuring filters and
antivirus. Finally, the problem of connecting to the Internet from a workstation that has on its
discloses confidential data, even when stored encrypted, is extremely difficult to
solve.

18
 Cryptography

Websentry - Authorizes secure access to the Web (access control, encryption), to applications
mainframe (Bull, IBM, Unix) and multimedia.

Fols-Security - Client access management to server services, SEMA-GROUP.

David Kahn- The Story of Secret Writing

[Link]/cryptography

19