Document Version 3.0 (23/10/2000)
Document based on my BSc Project in Computer Science at TEESSIDE (UK, March 1998)
INTRODUCTION TO CRYPTOGRAPHY
30 RUE GEORGES-BRASSENS
42650 SAINT JEAN BONNEFONDS
This document is part of the BUGS Cryptography project documentation.
It is based on the report of my final year project in Computer Science at the
University of TEESSIDE (UK) which consisted of finding information about
cryptography, creating my own cryptography algorithm and creating a Windows 95
This project started as a personal project back in 1995, became my Bsc
project in 1998. In 2000, I have created a new algorithm based on the original one.
BUGS is now a personal project again.
Each chapter's contents is divided into several parts which should help the
reader to easily find what he is looking for. Most of the chapters and sections
have an introduction to help their understanding and to give a quick overview
of their content.
As a background in cryptography is needed to evaluate the work done, this
introduction to cryptography should help the reader to appreciate the work done
in this BUGS cryptography project.
The reader does not require any special computer skills to understand this
report, but a previous knowledge of computer programming would be helpful.
Finally, a lot of people asked me: "Why creating another Symetric Cryptography Algorithm" especially
since AES is now available. This project is an amateur one, it is Open Source, free, for developpers and
it is not just a cryptography library but also a suit of cryptography softwares. I do not pretend to
have created something better than DES, AES, whatever_ES but just something I hope is secure enough to
protect personal data. The security level of this algorithm is currently being tested on the Internet,
and the feedback is very good so far.
I would like to thanks Trevor Tippins who highlighted many weaknesses in my
previous algorithm and then pushed me to improve it. I would especially like to
thank Joanne ELLIS who corrected the first version of this report in 1998. I
would like to thanks the University of TEESSIDE to let me do the previous
version of this algorithm as my Bsc project. The GNU, Linux and KDE team who
provide a lot of free development software. All the people around the world
who tested my applications and sent me feedback emails. My parents who support
me in my choices. My Brother Florent for the different BUGS logos. Finally my
other brother Thierry Martinez, 15 years old, who pushed me into the cryptography world
in 1995 by asking me a simple question: "Why cryptography is difficult to master ?" and always
pushed me to do my best by being unusually good at computing at his age.
Privacy is a sensitive subject that affects everyone. We all use various
techniques to safe guard our privacy, such as:
- When you write a letter for a job, your wife, or anything else private you
use an envelope to send it.
- When you use your credit card you use a secret code number.
- You sometimes have to speak to someone in private.
There are many other examples, but already you can see how important privacy
is for everybody, everyday.
With computers, most of the time you use sensitive data that has to be
secret (e.g. assessment marks, financial accounts, etc). With the
Internet you can use your computer like a telephone or like a post office, with
the disadvantage that everybody connected to the network could have access to
your data. This is why, especially with computers, privacy is important.
Different levels of security (computer security, network security, etc) have to
This area became one of my first interests since 1995, particularly one
part, cryptography. Cryptography can be compared to an electronic safe where
you put your private data. One of the reason for this interest is that I think
with cryptography you always have to think about what an intruder could do. I
usually compare cryptography to a chess game, in that you have to think about
your own tactics and also your opponents'.
I.2 BUGS PROJECT
The BUGS Cryptography project is a good example about how a block cipher cryptography algorithm works.
After reading this document the reader should read how this new block cipher algorithm has been designed as
it is quite easy to understand.
BUGS also has some interesting features such as dynamic algorithm, multiplaform, open source and free.
When you have an English text and you want to translate it into French, you
use language translation. In this case, any French person could read your new
text and understand it. However, if you have the same English text but you do
not want anybody else, except yourself, to be able to understand it, you use
Cryptography has been used for a very long time, the roman emperor Cesar is
the first famous person who used it for his military campaigns. These last few
years the army has mainly used it but since the computer has become a common
tool, cryptography is used and needed by everyone.
Each country has different laws about the use of cryptography for various
reasons, because in some country the use of strong cryptography is illegal, it
is a sensitive subject that makes it really interesting and in a way,
dangerous. Because fact that more and more
companies want to sell products on the Internet, the cryptography status is changing
to allow the customers to secure their transactions.
Cryptography usually uses a lot of mathematical formulas and logical functions. The
science is quite new for the public, this is why it is a very difficult subject,
but more and more people are interested in it and a lot of book dealing with
the subject have been written and it is now easy to find good cryptography
information. It seems that the strongest cryptography algorithms are now
available to the public even if it is very difficult to understand them.
Indeed, the best way to know if a cryptography algorithm is strong is to make its source code and
documentation available to the public. If no one can break it then it is safe to use it:
if you hide a message somewhere, once someone finds it, he can read it. However, if you
put this message in a safe that is publicly available and nobody is able to open it
then your message is safer. The point is to know if it is more difficult to
find a hidden message than to open a safe, keeping in mind that a mole could be
anywhere. With cryptography it is the same problem.
To make this report easier to understand, I will
give the definition of different terms I will use.
Clear text: An understandable message,
usually the original.
Cipher text: An incomprehensible message,
usually the result.
Password: A secret string of characters.
Crypt: Transform a clear text into a
cipher text, usually with a password.
Decrypt: Transform a cipher text into a
clear text, usually with a password.
Key: Some data that will be used into the
message crypt process. It can also be used like a password, the difference is
in this case that it is a long string of characters and numbers you can not
remember as is very long and complex. A key could be compare to a cipher
Private key: This key is personal
and only known by one person.
Public key: This key is available to everybody, it is now secret.
Many different cryptography algorithms have been
done, but there are two main algorithms used in cryptography. Here is a general
overview of these two cryptrography standards.
II.2.2.1 Private key algorithm
A private key algorithm uses one password (or one
private key) to crypt a message, to decrypt it the same password is used,
Figure 2.1 shows this process. The same
algorithm or a different one can be used to crypt and decrypt.
II.2.2.2 Public key algorithm
A public key algorithm consists of a public key
(B) used to crypt a message and a private key (A) used to decrypt the message,
for one public key there is one private key (A1, B1) and only the private key
that belongs to the public key can decrypt a message crypted by the public key,
Figure 2.2 shows this process.
Thanks to that, you can give your public key to
everybody, if they want to send you a message, they crypt the message with your
public key, and only you, who know your private key, can decrypt this message.
If you want to send them a message, then you have to use their public key to
crypt the message.
This algorithm can also be used to sign a message
to prove that it is really you who is sending a message, to do so you crypt the
message with your private key that can be decrypted only with the public key.
This is a bit difficult to understand, but just means that if you crypt a
message with one of the keys (public or private) you can decrypt it only with
the other key; if someone wants to imitate your signature he will fail because
he will crypt his message with your public key, but as this message can only be
decrypted with the private key, nobody will be able to decrypt it!
This feature is really useful in business or for
Figure 2.1 Private key algorithm
Figure 2.2 Public key algorithm
II.3 CRYPTOGRAPHY STANDARDS
A lot of cryptography algorithms have been
created, it is not the aim of this report to go into great detail about
cryptography, so only two of the most famous and used cryptography algorithms
are going to be quickly explained to give a general idea of how to crypt a
DES stands for "Data Encryption
Standard" and is at the moment the most used algorithm in the world ,
being used by the American government to secure their sensitive data. It has
been created by IBM (International Business Machines Corporation)  in 1977
and is a private key algorithm.
It is a block cipher algorithm that crypts data
by 64 bits length block, that means that the clear text is divided into 64 bits
length block and each block is crypted by 16 complex operations. The entire 64-bit
length crypted block constitutes the final cipher text. The decrypt algorithm
is nearly the same as the crypt algorithm, the same key (the private key) is
used to crypt and to decrypt a message; the bigger your private key is the
safer it is. Then, if you want to send a secret message to someone you have to
find a secure way to communicate to him the private key used to crypt it; that
is the weak point of the algorithm.
RSA [3,4] is the initial of the name of its
creator: Ron RIVEST, Adi SHAMIR and Leonard ADLEMAN. It is one of the first
public key algorithms and was created in 1978. In fact there are two
algorithms, one to generate the keys and one to crypt/decrypt the message; the
pair of keys, one public and one private, are based on big first numbers and
are the result of some calculations (modulo, Euclide's algorithm, etc). The
algorithm that crypts/decrypts a message is a bloc cipher algorithm that is simpler
than the DES algorithm but is much slower.
The security of this algorithm is based on
mathematical theories (big numbers factorisation), even if no real proof has
been given to demonstrate that these mathematical theories are not easily
"breakable", they have not been broken for 20 years.
These two algorithms have different concepts, but
neither of them is better than the other, they have their own advantages. A
good idea is to use both of them choosing which one depending on its
suitability to a specific job. It is why DES is usually used to crypt the
message, and RSA is used to communicate only the DES private key used to crypt
The reason for this choice is because DES is
faster than RSA and more difficult to break. However, to communicate the DES
private key a secure solution has to be found. RSA has a pretty good level of
security and you do not have to send your private key to the recipient, only
your public key. This is why RSA is used to crypt the DES private key, then the
crypted message and the DES crypted key are both sent to the recipient.
Here is an example represented by Figure
The "Sender(1)" wants to send a message to the "Recipient (2)", he
knows his own DES private key (A1) and gets the "Recipient (2)"
RSA public key (B2).
(1)" crypts his message using his own private key (A1) with the DES
algorithm and crypts this private key (A1) using the "Recipient
(2)" RSA public key (B2) with the RSA algorithm.
"Sender (1)" sends the crypted message and the crypted key to
the "Recipient (2)".
"Recipient (2)" receives them, he first has to decrypt the DES
private key (A1) to be able to decrypt the message; so he decrypts it
using his RSA private key (A2), the only key able to decrypt something
that has been crypted with the RSA public key (B2).
When he knows the private
key (A1) used to crypt the message, he uses it with the DES algorithm to
decrypt the message sent by the "Sender (1)".
Figure 2.3 Use of private and public algorithm
at the same time
II.4 POSSIBLE APPLICATIONS
The aim of this section is to give concrete
examples of professional cryptography used, which will help the reader to
appreciate more the work done on the project.
II.4.2 Login password
In a computer network like at the University of
Teesside, each student has an account were he works during the year, store his
reports, tutorials and other personal data. This data is private to each
student. To protect it from any evil possible action from someone other than
the owner, the students have a password that they must use to access their
data. This password is secret and stored in a password database. When a student
logs onto the network he types his password, which is then checked with the one
stored in the database. If someone succeeded to access these passwords it could
be dangerous. This is why these passwords are crypted, thanks to this even if
someone accesses the password database he will not be able to do anything
To increase security, the algorithm used is a
"one way" algorithm. This means that you can crypt but not decrypt.
The interest of this is because as you cannot decrypt this cipher text it
should be more difficult for an intruder to find the original clear text (in
this case, the password).
You may want to ask now: "if it is not
possible to decrypt the password stored in the password database, how does the
system know if it is the right password that has been typed at the login
?". The answer is you do not try to decrypt the password present in the
password database. You just crypt the password typed by the user and you
compare the cipher text generated (the password is crypted and the result is
cipher text) with the user's crypted password stored in the password database.
If the user did not make any mistakes while typing his password then the two
cipher texts will be identical and the user is allowed to log onto the system.
PGP means "Pretty Good Privacy" and is
an application used to crypt messages . It has been created by Philip
ZIMMERMANN and uses two different algorithms: RSA and IDEA which is similar to
To have a general idea of how this application
works, you can have a look at Figure 2.3 that
describes the use of a private key and a public key algorithm at the same time
This is the most famous application for crypting
personal data such as letters, emails, a file or anything else you can find on
a computer; because it is very powerful and has been developed on almost all
existing computers (PC, Macintosh, Amiga, etc). In fact, it is the first
application that has been developed for public as a pose to military use. It is
maybe why PGP is becoming a standard application on computers. The only problem
is the lack of a good Graphical User Interface (GUI) could discourage someone
if he never used cryptography before.
These two cryptography application examples show how it is possible to use
cryptography practically, they are the most common. There are many other
possible uses, for example, when two banks exchanging information, staff
identification in a big company, military communication, computer voting,
electronic money, mobile phones, etc…
Most of the time, cryptography is used invisibly
for the user.
II.5 COMMON CRYPTOGRAPHY ATTACKS
There are different ways to attack a cryptography
algorithm. If the algorithm security is only based on its secret, once someone
finds the algorithm source code it will be very easy to break it. Otherwise the
two most common attacks are "brute force" and algorithm attacks .
II.5.2 Algorithm attacks
Sometimes a cryptography algorithm can have weak
points, for example, with algorithms that just consist of adding the same
number to all the password letters they are easier to break. This is because
they are less complex, all you have to do is find the number used. This attack
needs strong cryptography knowledge and understanding. It is only used for bad
cryptography algorithms, but as with everything relating to computer science,
it is very difficult to totally avoid making errors, so this attack is always
the first one attempted. If no weak points are found the only attack that can
be done is the "brute force" attack.
II.5.3 Brute force attack
This attack is based on the cipher text generated
by a cryptography algorithm. If someone can get into the password database then
even if all the passwords in it are crypted, some software exists that simply
try every possible passwords, crypts them and compares the cipher text
generated with the one held in the password database. Of course, it would take
too long to try all the possible passwords, present computers are not fast
enough and there are too many possibilities. However, these software are quite
intelligent and before trying a password like "12%%*$$ù*r4" they will
try to find some information that concern the user like "sister",
"05/06/1995" or "Joanne". Therefore, the user is warned to
choose his password carefully otherwise it could be easy for someone to find
II.6 LAWS IN DIFFERENT COUNTRIES
Cryptography is a sensitive subject because not
all countries have common laws about it. Some countries ban its use or limit it
and others let everybody use it.
II.6.2 The United States
In the United States, everybody can use strong
cryptography. This means that even the American government and the army are
"not supposed" to be able to break crypted messages from American
citizens. There is, however, a cryptography export restriction; indeed, the
American government does not allow other countries to use their strong
cryptography algorithm (e.g. DES with very long keys). This is understandable,
in case of war, the United States want to be able to decrypt any crypted
messages from a hypothetical enemy country. However, more and more American
civil rights are in danger, because the NSA (National Security Agency) keeps
asking the federal government to declare cryptography illegal for public use
because of its importance to the national security. In addition, the American
government wants to have the power to break any crypted messages even those
from fellow Americans, therefore, restricting its use.
In France it is even worse, French citizens
cannot use strong cryptography because it is illegal and considered to be a
"Second class" Weapon!
The French government wants to be able to read
any electronic conversation made by French citizens, in other words, privacy on
the Internet is non-existent for the French…
The current laws only allow the use of strong
cryptography if you give your private key to the government to let them decrypt
your messages and only if the cryptography algorithm you want to use is one of
those that are authorised.
To get authorisation to use a new cryptography
application or algorithm you have to make a request to the SCSSI (Service
Central de la Securite des Systemes d'Information) which is a national French
security agency, and depends to the first French minister himself.
Laws about cryptography seems likely to change
soon on France allowing French citizens to use any key length. The laws exists
but still remains to be "activated". Things should change in 2002,
wait and see!
II.6.4 The United Kingdom
In United Kingdom, the use of cryptography is
free, i.e., there are no limitations to use any kind of cryptography algorithm
within the country. However you need to get an authorisation to export
encrypted data. This could be why, more foreign people are coming to work in
this country to do what they cannot do in their own country.
These 3 countries show how cryptography laws
differ in each country. These laws are changing because governments are under
pressure. For example, with the Internet, electronic business is more important
everyday. Some people say this is bad for the "Internet way of
thinking" i.e., free for everybody. However, people should be aware that
the more electronic business there is on the Internet then the more strong
cryptography algorithms will be used. This in turn, therefore, is good for data
security in general. Because privacy is needed to buy any kind of product on
the Internet, customers want to be sure their credit cards numbers are going to
be secure. More and more companies ask governments to allow them to offer a
high level of privacy to their customers. It seems that governments listen to
companies more than the public, especially if these companies are big…
Privacy is something essential in computing, therefore so is cryptography.
It is a difficult subject to understand as it is quite new for the public
and its use could be dangerous. This is why cryptography is so interesting, and
why more people start studying it every day.
The different government attitudes in different countries towards
cryptography could be worrying for their citizens regarding their civil rights.
People do not want the government to listen to their phone calls, so why should
they agree to let them to listen to their electronic conversations by not
In fact to be able to see how important cryptography is in computing we need
to look at the computer's increasing importance in our day to day lives.
There are three important things to remember about using cryptography:
Even if the cryptography
used is very powerful if to crypt clear text, a weak key is used (e.g., a
password with only one or two letters), the cipher text generated will be
easy to break, so the key has to be chosen carefully.
We can judge the quality
of a cryptography algorithm in function of the data's life span that is
going to be crypted. This means that if you are sure that the cipher text
needs X years to be decrypted without the original password and the data
that has been crypted will be useless in X - 1 years, the algorithm is
powerful enough. This is because when the intruder decrypts the cipher
text, it will be useless as it will be one year out of the date. Indeed,
in the case of an intruder: intercepting a cipher text is possible,
however, finding the password is much more difficult!
It is forbidden in some
countries, and could be dangerous because computers are used more and more
by the army, and those that control privacy, control secret data.