Lakhasly

1.1 Overview of Cryptology If we hear the word cryptography our first associations might be e-mail encryption, secure website access, smart cards for banking applications or code breaking during World War II. Cryptography seems closely linked to modern electronic communication. However, cryptography is a rather old business, with early examples dating back to about 2000 B.C., when non-standard “secret” hieroglyphics were used in ancient Egypt. Since Egyptian days cryptography has been used in one form or the other in many, if not most, cultures that developed written language. For instance, there are documented cases of secret writing in ancient Greece, namely the scytale of Sparta (Fig. 1.1), or the famous Caesar cipher in ancient Rome, about which we will learn later in this chapter. Fig 1.1 Scytale of Sparta Let’s now have a look at the field of cryptography (Fig. 1.2). The first thing that we notice is that the most general term is cryptology and not cryptography. Cryptology splits into two main branches: Cryptography is the science of secret writing with the goal of hiding the meaning of a message. Cryptanalysis is the science and sometimes art of breaking cryptosystems. You might think that code breaking is for the intelligence community or perhaps organized crime, and should not be included in a serious classification of a scientific discipline. 5 However, most cryptanalysis is done by respectable researchers in academia nowadays. Cryptanalysis is of central importance for modern cryptosystems: without people who try to break our crypto methods, we will never know whether they are really secure or not. Fig 1.2 Overview of the field of cryptology Because cryptanalysis is the only way to assure that a cryptosystem is secure, it is an integral part of cryptology. Nevertheless, the focus of this book is on cryptography: We introduce most important practical crypto algorithms in detail. These are all crypto algorithms that have withstood cryptanalysis for a long time, in most cases for several decades. In the case of cryptanalysis, we will mainly restrict ourselves to providing state-of-the-art results with respect to breaking the crypto algorithms that are introduced, e.g., the factoring record for breaking the RSA scheme. Let’s now go back to Fig. 1.2. Cryptography itself splits into three main branches: Symmetric Algorithms are what many people assume cryptography is about: two parties have an encryption and decryption method for which they share a secret key. All cryptography from ancient times until 1976 was exclusively based on symmetric methods. Symmetric ciphers are still in widespread use, especially for data encryption and integrity check of messages. 6 Asymmetric (or Public-Key) Algorithms In 1976 an entirely different type of cipher was introduced by Whitfield Diffie, Martin Hellman and Ralph Merkle. In public-key cryptography, a user possesses a secret key as in symmetric cryptography but also a public key. Asymmetric algorithms can be used for applications such as digital signatures and key establishment, and also for classical data encryption. In asymmetric encryption, there are two keys: one to encrypt and another to decrypt. The encryption key is called a public key and is generally considered publicly available to anyone who wants to send you encrypted messages. The decryption key, however, must remain secret and is called a private key. Cryptographic Protocols Roughly speaking, crypto protocols deal with the application of cryptographic algorithms. Symmetric and asymmetric algorithms can be viewed as building blocks with which applications such as secure Internet communication can be realized. The Transport Layer Security (TLS) scheme, which is used in every Web browser, is an example of a cryptographic protocol. Strictly speaking, hash functions, form a third class of algorithms but at the same time they share some properties with symmetric ciphers. In the majority of cryptographic applications in practical systems, symmetric and asymmetric algorithms (and often also hash functions) are all used together. This is sometimes referred to as hybrid schemes. The reason for using both families of algorithms is that each has specific strengths and weaknesses. The main focus of this book is on symmetric and asymmetric algorithms, as well as hash functions. However, we will also introduce basic security protocols. In particular, we will introduce several key establishment protocols and what can be achieved with crypto protocols: confidentiality of data, integrity of data, authentication of data, user identification, etc. 7 1.2 Cryptographic goals Of all the information security objectives listed in Table 1.1, the following four form a framework upon which the others will be derived: (1) privacy or confidentiality; (2) data integrity; (3) authentication; and (4) non-repudiation.

1. Confidentiality is a service used to keep the content of information from all but those authorized to have it. Secrecy is a term synonymous with confidentiality and privacy. There are numerous approaches to providing confidentiality, ranging from physical protection to mathematical algorithms which render data unintelligible.
2. Data integrity is a service which addresses the unauthorized alteration of data. To assure data integrity, one must have the ability to detect data manipulation by unauthorized parties. Data manipulation includes such things as insertion, deletion, and substitution.
3. Authentication is a service related to identification. This function applies to both entities and information itself. Two parties entering into a communication should identify each other. Information delivered over a channel should be authenticated as to origin, date of origin, data content, time sent, etc. For these reasons this aspect of cryptography is usually subdivided into two major classes: entity authentication and data origin authentication. Data origin authentication implicitly provides data integrity (for if a message is modified, the source has changed).
4. Non-repudiation is a service which prevents an entity from denying previous commitments or actions. When disputes arise due to an entity denying that certain actions were taken, a means to resolve the situation is necessary. For example, one entity may authorize the purchase of property by another entity and later deny such authorization was granted. A procedure involving a trusted third party is needed to resolve the dispute. A fundamental goal of cryptography is to adequately address these four areas in both theory and practice. Cryptography is about the prevention and detection of cheating and other malicious activities.

1.1 Overview of Cryptology
If we hear the word cryptography our first associations might be e-mail
encryption, secure website access, smart cards for banking applications or code
breaking during World War II.
Cryptography seems closely linked to modern electronic communication.
However, cryptography is a rather old business, with early examples dating back to
about 2000 B.C., when non-standard “secret” hieroglyphics were used in ancient Egypt.
Since Egyptian days cryptography has been used in one form or the other in many,
if not most, cultures that developed written language. For instance, there are
documented cases of secret writing in ancient Greece, namely the scytale of Sparta (Fig.
1.1), or the famous Caesar cipher in ancient Rome, about which we will learn later in
this chapter.
Fig 1.1 Scytale of Sparta
Let’s now have a look at the field of cryptography (Fig. 1.2). The first thing that
we notice is that the most general term is cryptology and not cryptography.
Cryptology splits into two main branches:
Cryptography is the science of secret writing with the goal of hiding the meaning of a
message.
Cryptanalysis is the science and sometimes art of breaking cryptosystems. You
might think that code breaking is for the intelligence community or perhaps organized
crime, and should not be included in a serious classification of a scientific discipline.
5
However, most cryptanalysis is done by respectable researchers in academia nowadays.
Cryptanalysis is of central importance for modern cryptosystems:
without people who try to break our crypto methods, we will never know whether
they are really secure or not.
Fig 1.2 Overview of the field of cryptology
Because cryptanalysis is the only way to assure that a cryptosystem is secure, it is
an integral part of cryptology. Nevertheless, the focus of this book is on cryptography:
We introduce most important practical crypto algorithms in detail. These are all crypto
algorithms that have withstood cryptanalysis for a long time, in most cases for several
decades. In the case of cryptanalysis, we will mainly restrict ourselves to providing
state-of-the-art results with respect to breaking the crypto algorithms that are
introduced, e.g., the factoring record for breaking the RSA scheme.
Let’s now go back to Fig. 1.2. Cryptography itself splits into three main branches:
Symmetric Algorithms are what many people assume cryptography is about: two
parties have an encryption and decryption method for which they share a secret key. All
cryptography from ancient times until 1976 was exclusively based on symmetric
methods. Symmetric ciphers are still in widespread use, especially for data encryption
and integrity check of messages.
6
Asymmetric (or Public-Key) Algorithms In 1976 an entirely different type of cipher
was introduced by Whitfield Diffie, Martin Hellman and Ralph Merkle. In public-key
cryptography, a user possesses a secret key as in symmetric cryptography but also a
public key. Asymmetric algorithms can be used for applications such as digital
signatures and key establishment, and also for classical data encryption.
In asymmetric encryption, there are two keys: one to encrypt and another to decrypt.
The encryption key is called a public key and is generally considered publicly available
to anyone who wants to send you encrypted messages. The decryption key, however,
must remain secret and is called a private key.
Cryptographic Protocols Roughly speaking, crypto protocols deal with the application
of cryptographic algorithms. Symmetric and asymmetric algorithms can be viewed as
building blocks with which applications such as secure Internet communication can be
realized. The Transport Layer Security (TLS) scheme, which is used in every Web
browser, is an example of a cryptographic protocol.
Strictly speaking, hash functions, form a third class of algorithms but at the same time
they share some properties with symmetric ciphers.
In the majority of cryptographic applications in practical systems, symmetric and
asymmetric algorithms (and often also hash functions) are all used together. This is
sometimes referred to as hybrid schemes. The reason for using both families of
algorithms is that each has specific strengths and weaknesses.
The main focus of this book is on symmetric and asymmetric algorithms, as well as
hash functions. However, we will also introduce basic security protocols. In particular,
we will introduce several key establishment protocols and what can be achieved with
crypto protocols: confidentiality of data, integrity of data, authentication of data, user
identification, etc.
7
1.2 Cryptographic goals
Of all the information security objectives listed in Table 1.1, the following four
form a framework upon which the others will be derived: (1) privacy or confidentiality;
(2) data integrity; (3) authentication; and (4) non-repudiation.

1. Confidentiality is a service used to keep the content of information from all but those
   authorized to have it. Secrecy is a term synonymous with confidentiality and privacy.
   There are numerous approaches to providing confidentiality, ranging from physical
   protection to mathematical algorithms which render data unintelligible.


2. Data integrity is a service which addresses the unauthorized alteration of data. To
   assure data integrity, one must have the ability to detect data manipulation by
   unauthorized parties. Data manipulation includes such things as insertion, deletion, and
   substitution.


3. Authentication is a service related to identification. This function applies to both
   entities and information itself. Two parties entering into a communication should
   identify each other. Information delivered over a channel should be authenticated as to
   origin, date of origin, data content, time sent, etc. For these reasons this aspect of
   cryptography is usually subdivided into two major classes: entity authentication and
   data origin authentication. Data origin authentication implicitly provides data integrity
   (for if a message is modified, the source has changed).


4. Non-repudiation is a service which prevents an entity from denying previous
   commitments or actions. When disputes arise due to an entity denying that certain
   actions were taken, a means to resolve the situation is necessary. For example, one entity
   may authorize the purchase of property by another entity and later deny such
   authorization was granted. A procedure involving a trusted third party is needed to
   resolve the dispute. A fundamental goal of cryptography is to adequately address these
   four areas in both theory and practice. Cryptography is about the prevention and
   detection of cheating and other malicious activities.