Information security  1

Chapter Three
Contents

Cryptography  Introduction, cipher texts, plain text, encryption,

decryption.
 Symmetric and asymmetric algorithms.
 Cesar cipher.

3. Introduction to Cryptography
Cryptography is a science of secrete writing or hidening secrets. So much has been said
and so much has been gained; thousands of lives have been lost, and empires have
fallen because a secret was not kept. Efforts to keep secrets have been made by humans
probably since the beginning of humanity itself. Long ago, humans discovered the
essence of secrecy. The art of keeping secrets resulted in victories in wars and in
growth of mighty empires. Powerful rulers learned to keep secrets and pass information
without interception; that was the beginning of cryptography. Although the basic
concepts of cryptography predate the Greeks, the present word cryptography, used to
describe the art of secret communication, comes from the Greek meaning ―secret
writing.‖ From its rather simple beginnings, cryptography has grown in tandem with
technology, and its importance has also similarly grown. Just as in its early days, good
cryptographic prowess still wins wars.

As we get dragged more and more into the new information society, the kind of face-to-
face and paper-traceable communication that characterized the nondigital
communication before the information revolution, the kind of communication that
guaranteed personal privacy and security, is increasingly becoming redefined into the
new information society where faceless digital communication regimes are
guaranteeing neither information and personal security nor personal privacy.
Centuries old and trusted global transactions and commercial systems that guaranteed
business exchange and payment systems are being eroded and replaced with difficult to
trust and easily counterfeitable electronic systems. The technological and
communication revolution has further resulted in massive global surveillance of
millions of individuals and many times innocent ones by either their governments or
private companies; the fight for personal privacy has never been any more fierce, and
the integrity and confidentiality of data have become more urgent than ever before. The
security and trust of digital transaction systems have become of critical importance as
more and more organizations and businesses join the e-commerce train. The very future
of global commerce is at stake in this new information society unless and until the
security of e-commerce can be guaranteed.
Modern cryptographic security services include:
 Security services Cryptographic mechanism to achieve the service
 Confidentiality Symmetric encryption
 Authentication Digital signatures and digital certificates
 Integrity Decryption of digital signature with a public key to obtain the message
digests. The message is hashed to create a second digest. If the digests are identical,
the message is authentic and the signer’s identity is proven

Information Security Chapter-3

Prepared by: - Tsehay.A
2  Information Security

 Nonrepudiation Digital signatures of a hashed message then encrypting the result

with the private key of the sender, thus binding the digital signature to the message
being sent
 Non replay
Encryption, hashing, and digital signature
Cryptography is being increasingly used to fight off this massive invasion of individual
privacy and security, to guarantee data integrity and confidentiality, and to bring trust in
global e-commerce. Cryptography has become the main tool for providing the needed
digital security in the modern digital communication medium that far exceeds the kind
of security that was offered by any medium before it. It guarantees authorization,
authentication, integrity, confidentiality, and nonrepudiation in all communications and
data exchanges in the new information society.

3.1. Cryptographic terms

The terms used in cryptography are the following;

 Plain text-the original message to be sent.
 Cipher text-the result of applying an encryption algorithm to the original message
before it is sent to the recipient.
 Key- string of bits used in the two mathematical algorithms used in encryption and
decryption process
 Cryptographic system (cryptosystem) or a cipher – consisting of mathematical
encryption and decryption algorithms.
 Encryption—Encryption is the process of changing information using an algorithm
(or cipher) into another form that is unreadable by others—unless they possess the
key to that data. Encryption is used to secure communications and to protect data as
it is transferred from one place to another. The reverse, decryption, can be
accomplished in two ways: First, by using the proper key to unlock the data, and
second, by cracking the original encryption key. Encryption enforces confidentiality
of data.
A cipher or a cryptosystem is a pair of invertible functions, one for encrypting or
enciphering and the other for decrypting or deciphering. The word cipher has its origin
in an Arabic word sifr, meaning mptyor zero. The encryption process uses the
cryptographic algorithm, known as the encryption algorithm, and a selected key to
transform the plaintext data into an encrypted form called ciphertext, usually
unintelligible form. The ciphertext can then be transmitted across the communication
channels to the intended destination.
A cipher can either be a stream cipher or a block cipher. Stream ciphers rely on a key
derivation function to generate a key stream. The key and an algorithm are then applied
to each bit, one at a time. Even though stream ciphers are faster and smaller to
implement, they have an important security gap. If the same key stream is used, certain
types of attacks may cause the information to be revealed. Block ciphers, on the other
hand, break a message up into chunks and combine a key with each chunk, for example,
64 or 128 bits of text. Since most modern ciphers are block ciphers, let us look at those
in more details.

Information Security, Chapter-6

 Information security  3

6.1.Block Ciphers
Block ciphers operate on combinations of blocks of plaintext and ciphertext. The block
size is usually 64 bits, but operating on blocks of 64 bits (8 bytes) is not always useful
and may be vulnerable to simple cryptanalysis attacks. This is so because the same
plaintext always produces the same ciphertext. Such block encryption is especially
vulnerable to replay attacks. To solve this problem, it is common to apply the ciphertext
from the previous encrypted block to the next block in a sequence into a combination
resulting into a final ciphertext stream. Also to prevent identical messages encrypted on
the same day from producing identical ciphertext, an initialization vector derived from
a random number generatoris combined with the text in the first block and the key. This
ensures that all subsequent blocks result in ciphertext that doesn’t match that of the first
encrypting. Several block cipher combination modes of operation are in use today. The
most common ones are described below:

 Electronic Codebook (ECB) mode – this is the simplest block cipher mode of
operation in which one block of plaintext always produces the same block of
ciphertext. This weakness makes it easy for the cryptanalysts to break the code and
easily decrypt that ciphertext block whenever it appears in a message. This
vulnerability is greatest at the beginning and end of messages, where well- defined
headers and footers contain common information about the sender, receiver, and
date.
 Block chaining (CBC) mode is a mode of operation for a block cipher that uses.
What is known as an initialization vector (IV) of a certain length. One of its key
characteristics is that it uses a chaining mechanism that causes the decryption of a
block of ciphertext to depend on all the preceding ciphertext blocks. As a result, the
entire validity of all preceding blocks is contained in the immediately previous
ciphertext block. A single bit error in a ciphertext block affects the decryption of all
subsequent blocks. Rearrangement of the order of the ciphertext blocks causes
decryption to become corrupted. Basically, in cipher block chaining, each plaintext
block is XORed (exclusive ORed) with the immediately previous ciphertext block
and then encrypted.
 Cipher feedback (CFB) is similar to the previous CBC in that the following data is
combined with the previous data so that identical patterns in the plaintext result in
different patterns in the ciphertext. However, the difference between CBC and CFB
is that in CFB, data is encrypted a byte at a time and each byte is encrypted along
with the previous 7 bytes of ciphertext.
6.2.Symmetric Encryption
Symmetric encryption or secret-key encryption, as it is usually called, uses a common
key and the same cryptographic algorithm to scramble and unscramble the message.
The transmitted fi nal ciphertext stream is usually a chained combination of blocks of
the plaintext, the secret key, and the ciphertext.
The security of the transmitted data depends on the assumption that eavesdroppers and
cryptanalysts with no knowledge of the key are unable to read the message.
However, for a symmetric encryption scheme to work, the key must be shared between
the sender and the receiver. The sharing is usually done through passing the key from

Information Security Chapter-3

Prepared by: - Tsehay.A
4  Information Security

the sender to the receiver. This presents a problem in many different ways, as seen in
the figure below.

Figure 6.1. Symmetric encryption

Fig. 6.2 Encryption and decryption with symmetric cryptography

The question which arises is how to keep the key secure while being transported from
the sender to the receiver.
Symmetric algorithms are faster than their counterparts, the public-key algorithms.

6.3.Symmetric Encryption Algorithms

The most widely used symmetric encryption method in the United States is the block
ciphers Triple Data Encryption Standard (3DES). 3DES developed from the original
and now cracked DES uses a 64-bit key consisting of 56 effective key bits.

6.4.Problems with Symmetric Encryption

As we pointed out earlier, symmetric encryption, although fast, suffers from several
problems in the modern digital communication environment. These are a direct result of
the nature of symmetric encryption. Perhaps the biggest problem is that a single key ust
be shared in pairs of each sender and receiver. In a distributed environment with large
umbers of combination pairs involved in many-to-one communication topology, it is
difficult for the one recipient to keep so many keys in order to support all
communication.

Information Security, Chapter-6

 Information security  5

In addition to the key distribution problem above, the size of the communication space
presents problems. Because of the massive potential number of individuals who can
carry on communication in many-to-one, one-to-many, and many-to-many topologies
supported by the Internet, for example, the secret-key cryptography, if strictly used,
requires billions of secret key pairs to be created, shared, and stored. This can be a
nightmare! Large numbers of potential correspondents in the manyto- one, one-to-
many, and many-to-many communication topologies may cause symmetric encryption
to fail because of its requirement of prior relationships with the parties to establish the
communication protocols like the setting up of and acquisition of the secret key.
Besides the problems discussed above and as a result of them, the following additional
problems are also observable:
The integrity of data can be compromised because the receiver cannot verify that the
message has not been altered before receipt.
 It is possible for the sender to repudiate the message because there are no
mechanisms for the receiver to make sure that the message has been sent by the
claimed sender.
 The method does not give a way to ensure secrecy even if the encryption process is
compromised.
 The secret key may not be changed frequently enough to ensure confi dentiality.
3.2. Public-Key Encryption

Since the symmetric encryption scheme suffered from all those problems we have just
discussed above, there was a need for a more modern cryptographic scheme to address
these flaws. The answers came from two people: Martin Hellman and Whitfield Diffie,
who developed a method that seemed to solve at least the first two problems and
probably all four by guaranteeing secure communication without the need for a secret
key. Their scheme, consisting of mathematical algorithms, led to what is known as a
public-key encryption (PKE).
Public-key encryption, commonly known asymmetric encryption, uses two different
keys, a public key known to all and a private key known only to the sender and the
receiver. Both the sender and the receiver own a pair of keys, one public and the other a
closely guarded private one. To encrypt a message from sender A to receiver B, as
shown in Fig. 11.4, both A and B must create their own pairs of keys.
Then A and B publicize their public keys – anybody can acquire them. When A has to
send a message M to B, A uses B’s public key to encrypt M. On receipt of M, B then
uses his or her private key to decrypt the message M. As long as only B, the recipient,
has access to the private key, then A, the sender, is assured that only B, the recipient,
can decrypt the message. This ensures data confidentiality.
Data integrity is also ensured because for data to be modified by an attacker, it requires
the attacker to have B’s, the recipient’s, private key. Data confidentiality and integrity
in public- key encryption are also guaranteed.
The core of public-key encryption is that no secret key is passed between two
communicating parties. This means that this approach can support all communication
topologies including one to one, one to many, many to many, and many to one, and
along with it, several to thousands of people can communicate with one party without
exchange of keys. This makes it suitable for Internet communication and electronic
commerce applications. Its other advantage is that it solves the chronic repudiation

Information Security Chapter-3

Prepared by: - Tsehay.A
6  Information Security

problem experienced by symmetric encryption. This problem is solved, especially in

large groups, by the use of digital signatures and certificates.
The various cryptographic algorithms used in this scheme rely on the degree of
computational difficulty encountered as an attempt is made to recover the keys.
3.3.Public-Key Encryption Algorithms
Various algorithms exist for public-key encryption including RSA, DSA, PGP, and
ElGamal.
3.3.1. Problems with Public-Key Encryption
Although public-key encryption seems to have solved the major chronic encryption
problems of key exchange and message repudiation, it still has its own problems.
The biggest problem for public-key cryptographic scheme is speed. Public-key
algorithms are extremely slow compared to symmetric algorithms. This is because
public-key calculations take longer than symmetric key calculations since they involve
the use of exponentiation of very large numbers which in turn take longer to compute.
For example, the fastest public-key cryptographic algorithm such as RSA is still far
slower than any typical symmetric algorithm. This makes these algorithms and the
public-key scheme less desirable for use in cases of long messages.
In addition to speed, public-key encryption algorithms have a potential to suffer from
the man-in-the-middle attack. The man-in-the-middle attack is a well-known attack,
especially in the network community where an attacker sniffs packets off a
communication channel, modifies them, and inserts them back on to the channel. In
case of an encryption channel attack, the intruder convinces one of the correspondents
that the intruder is the legitimate communication partner.
3.3.2. Public-Key Encryption Services
As it strives to solve the flaws that have plagued other encryption schemes, public- key
encryption scheme offers the following services:
 Secrecy which makes it extremely difficult for an intruder who is able to
intercept the ciphertext to be able to determine its corresponding plaintext..
 Authenticity which makes it possible for the recipient to validate the source of a
message.
 Integrity which makes it possible to ensure that the message sent cannot be
modified in any way during transmission.

 Nonrepudiation which makes it possible to ensure that the sender of the message
cannot later turn around and disown the transmitted message.
Symmetric algorithms, although faster than public-key algorithms, are beset with a
number of problems. Similarly, public-key encryption also suffers slowness and the
potential of the ―man-in-the-middle‖ attack. To address these concerns and to
preserve both efficiency and privacy of the communication channel and increase the
performance of the system, a hybrid cryptosystem that uses the best of both and at
the same time mitigating the worst in each system is widely used.

Information Security, Chapter-6

 Information security  7

3.3.3. The Key Exchange Problem

Although symmetric encryption is commonly used due to its historical position in
cryptography and its speed, it suffers from a serious problem of how to safely and
secretly deliver a secret key from the sender to the recipient. This problem forms
the basis for the key exchange problem. The key exchange problem involves the
following:
 Ensuring that keys are exchanged so that the sender and receiver can perform
encryption and decryption
 Ensuring that an eavesdropper or outside party cannot break the code
 Ensuring the receiver that a message was encrypted by the sender
The strength of an encryption algorithm lies in its key distribution techniques.
Poor key distribution techniques create an ideal environment for a man-in-the- middle
attack. The key exchange problem, therefore, highlights the need for strong key
distribution techniques. Even though the key exchange problem is more prominent in
the symmetric encryption cryptographic methods, and it is basically solved by the
public-key cryptographic methods, some key exchange problems still remain in public-
key cryptographic methods. For example, symmetric key encryption requires the two
communicating parties to agree upon their secret key ahead of time before
communicating, and public-key encryption suffers from the difficulty of securely
obtaining the public key of the recipient. However, both of these problems can be
solved using a trusted third party or an intermediary. For symmetric key cryptography,
the trusted intermediary is called a key distribution center (KDC). For public-key
cryptography, the trusted and scalable intermediary is called a certificate authority
(CA).
3.4.Digital Certificates
A digital certificate is a digitally signed message used to attest to the validity of the
public key of a communicating element. As we pointed out, digital certificates must
adhere to a format. Most digital certificates follow the International Telecommunication
Union (ITU-T) X.509 standard. According to RFC 1422, the X.509 digital certificate.
In modern communication, the use of certificates has become common and vital to the
security of such communications. For example, in a network environment, in order to
encrypt transmissions to your server, the client requires the server’s public key. The
integrity of that key is vital to the security of the subsequent sessions. If a third party,
for example, were to intercept the communication and replace the legitimate key with
his or her own public key, that man-in-the-middle could view all traffic or even modify
the data in transit. Neither the client nor the server would detect the intrusion.
So to prevent this, the client demands from the server, and the server sends the public
key in a certificate signed by a certificate authority. The client checks the digital
signature. If the signature is valid, the client knows that the CA has certified that this is
the server’s authentic certificate, not a certificate forged by a man-in-the- middle. It is
important that the CA be a trusted third party in order to provide meaningful
authentication.

Information Security Chapter-3

Prepared by: - Tsehay.A
8  Information Security

3.5.Hash Function
In the previous sections, we have seen how both symmetric and public-key encryptions
are used to ensure data confidentiality and integrity and also user authentication and
nonrepudiation, especially when the two methods are combined. Another way to
provide data integrity and authenticity is to use hash functions.
A hash function is a mathematical function that takes an input message M of a given
length and creates a unique fixed-length output code. The code, usually a 128- bit or a
160-bit stream, is commonly referred to as a hash or a message digest. A one-way hash
function, a variant of the hash function, is used to create a signature or fingerprint of the
message – just like a human fingerprint. On input of a message, the hash function
compresses the bits of a message to a fixed-size hash value in a way that distributes the
possible messages evenly among the possible hash values.
Using the same hash function on the same message always results in the same message
digest. Different messages always hash to different message digests.
A cryptographic hash function does this in a way that makes it extremely difficult to
come up with two or more messages that would hash to a particular hash value. It is
conjectured that the probability of coming up with two messages hashing on the same
message digest is of the order of 2 64 and that of coming up with any message hashing
on a given message digest is of the order of 2 128.
In ensuring data integrity and authenticity, both the sender and the recipient perform the
same hash computation using the same hash function on the message before the
message is sent and after it has been received. If the two computations of the same hash
function on the same message produce the same value, then the message has not been
tampered with during transmission.
There are various standard hash functions of message digest length including the 160-
bit (SHA-1 and MD5) and 128-bit streams (RSA, MD2, and MD4). Message digest
hash algorithms MD2, MD4, and MD5 are credited to Ron Rivest, while Secure Hash
Algorithm (SHA) was developed by the NIST. The most popular of these hash
algorithms are SHA and MD5. Table 11.5shows some more details of these algorithms.
3.6.Digital Signatures
While we use the hash functions to ensure the integrity and authenticity of the message,
we need a technique to establish the authenticity and integrity of each message and each
user so that we ensure the nonrepudiation of the users. This is achieved by the use of a
digital signature.
A digital signature is defined as an encrypted message digest, by the private key of the
sender, appended to a document to analogously authenticate it, just like the handwritten
signature appended on a written document that authenticates it. Just like in the
handwritten form, a digital signature is used to confirm the identity of the sender and
the integrity of the document. It establishes the nonrepudiation of the sender.
Digital signatures are formed using a combination of public-key encryption and one-
way secure hash function according to the following steps:
The sender of the message uses the message digest function to produce a message
authentication code (MAC).
 This MAC is then encrypted using the private-key and the public-key encryption
algorithm.
 This encrypted MAC is attached to the message as the digital signature.

Information Security, Chapter-6

 Information security  9

The message is then sent to the receiver. Upon receipt of the message, the recipient then
uses his or her public key to decrypt the digital signature. First, the recipient must
verify that the message indeed came from the expected sender. This step verifies the
sender’s signature. It is done via the following steps:
 The recipient separates the received message into two: the original document and
the digital signature.
 Using the sender’s public key, the recipient then decrypts the digital signature
which results in the original MAC.
 The recipient then uses the original document and inputs it to the hash function to
produce a new MAC.
 The new MAC is compared with the MAC from the sender for a match.
If these numbers compare, then the message was received unaltered, the data integrity
is assured, and the authenticity of the sender is proven. Because digital signatures are
derived from the message as a digest which is then encrypted, they cannot be separated
from the messages they are derived from and remain valid.
Since digital signatures are used to authenticate the messages and identify the senders
of those messages, they can be used in a variety of areas where such double
confirmation is needed. Anything that can be digitized can be digitally signed. This
means that digital signatures can be used with any kind of message, whether it is
encrypted or not, to establish the authenticity of the sender and that the message arrived
intact. However, digital signatures cannot be used to provide the confidentiality of the
message content.
Among the most common digital signature algorithms in use today are the Digital
Signature Standard (DSS) proposed by NIST and based on the ElGamal public-key
algorithm and RSA. DSS is faster than RSA. Although digital signatures are popular,
they are not the only method of authenticating the validity of the sender and the
integrity of the message.

Verifying a digital signature in message authentication

Information Security Chapter-3

Prepared by: - Tsehay.A
10  Information Security

Diffie-Hellman Key Exchange Algorithm

In the Diffie-Hellman scheme, each user generates a public/private key pair and
distributes a public key to everyone else. After two or more users obtain a copy of the
others’ public keys, they can be used to create a shared secret used as the key for a
symmetric cipher. Due to the varying methods of public key cryptography, the whole
subject can become somewhat confusing. Remember that there will always be a private
and public key involved, and that public key cryptography can use asymmetric keys
alone, or in addition to symmetric keys.
Internet standards, such as SSL/TLS and PGP, use public-key cryptography. Don’t
confuse the term public key cryptography with Public Key Infrastructure (PKI).
Although they are related, they are not the same. PKI is an entire system of hardware,
software, policies, and so on, that binds public keys with user identities by way of
certificates and a certificate authority (server or other such device). A certificate is an
electronic document that uses a digital signature to bind the key with the identity.

Alice Bob
Generate random g and p Generate random g and p.
Choose random a Choose random b
Compute XA=ga mod p Compute XB=gb mod p
SK= (XB) a mod p SK= (XA) b mod p

SK

The RSA Algorithm

The pioneering paper by Diffie and Hellman, introduced a new approach to
cryptography and, in effect, challenged cryptologists to come up with a cryptographic
algorithm that met the requirements for public-key systems. A number of algorithms
have been proposed for public-key cryptography. Some of these, thoughinitially
promising, turned out to be breakable.

One of the first successful responses to the challenge was developed in 1977 by Ron
Rivest, Adi Shamir, and Len Adleman at MIT and first published in 1978.
The Rivest-Shamir-Adleman (RSA) scheme has since that time reigned supreme as the
most widely accepted and implemented general-purpose approach to public-key
encryption.
The RSAscheme is a block cipher in which the plaintext and ciphertext are integers
between 0 and n-1 for some n. A typical size for nis 1024 bits, or 309 decimal digits.
That is,nis less than 1024.. We examine RSA in this section in some detail, beginning
with an explanation of the algorithm. Then we examine some of the computational and
cryptanalytical implications of RSA.

Information Security, Chapter-6

 Information security  11

Description of the Algorithm

RSA makes use of an expression with exponentials. Plaintext is encrypted in blocks,
with each block having a binary value less than some number n. That is, the block size
must be less than or equal to log2 (n)+1; in practice, the block size is I bits, where 2i
6n≤2i+1. . Encryption and decryption are of the following form, forsome plaintext
block Mand ciphertext block C.
C=Memod n
M=Cdmodn
Both sender and receiver must know the value of n. The sender knows the value of e,
and only the receiver knows the value of d. Thus, this is a public-key encryption
algorithm with a public key of PU={e,n} and a private key of PR={d,n}.
RSA keygeneration
The key generation involves the following steps:
1) Select two relatively prime numers p and q.
2) Find the modulus n=p*q
3) Find ᴪ(n)= (p-1)*(q-1)
4) Select e such tha 1<e< ᴪ(n) and e and ᴪ(n) are coprime
5) Find d such tah e*d mod ᴪ(n)=1

The public key is the pair {e,n} which is used in encryption of message M and the
private key is the pair {d,n} which is used in decryption of cipher text C.
Example let the two prime numbers used in RSA key generation be, p=3 and q=11, the
find the value of the public and private key pairs and show encryption and decryption
of message M=2.
Solutions
Step: 1 p=3 and q=11…..given
Step 2: n=p*q=3*11=33
Step 3: ᴪ (n) = (p-1)*(q-1) = (3-1)*(11-1) =2*10=20
Step 4: choose e such that 1<e< ᴪ (n), let e be 7, this statisifes the requirement that
1<e< ᴪ (n) and 7 and 20 are coprime.
Step 5: e*d mod ᴪ (n) =1, d=3 because 3*7 mod 20=1 the public key is {7, 33} and the
private key is {3, 33}
Encryption of M=2 is given below
C=Me mod n=2 7 mod 33=128 mod 33=29.
Decryption of cipher text 29 is given below
D=Cd mod n=29 3 mod 33=24389 mod 33=2. Well done! We got the original message
after decryption.
Exercises
1) Discuss the basic components of cryptography.
2) Discuss the weaknesses of symmetric encryption.
3) Discuss the weaknesses of public-key encryption.
4) Why is a hybrid cryptosystem preferred over symmetric and public-key encryption
systems?
5) Explain the stpes involved in RSA key genereation by giving an example, except
the one given above.

Information Security Chapter-3

Prepared by: - Tsehay.A
12  Information Security

Reading Assignment
 Cryptographics hash functions, MD5, SHA algorithm, MAC, message
authentication code.
 Digital certificates and digital signatures
 Block ciphers, stream ciphers

Information Security, Chapter-6