If the plaintext is “HORSELSP” and the block size is 5, what is the key?

Encryption

Published on IST 554 (https://online.ist.psu.edu/ist554)

Topic 4:

Encryption

The incredible growth of the Internet has changed the way people live and work. But Internet
security is a major concern, especially with sensitive information such as credit card numbers, Social
Security Numbers (SSNs), personal details, and bank account information. Concerns about the lack of
security online and potential loss of privacy prevent many computer users from fully realizing the
potential of the Internet.

To protect this information, security can be set up on computers and over the Internet by a variety of
methods, allowing users to communicate on the Internet with confidence, knowing their security and
privacy are protected. By far the most important and straightforward method for network and
communication security is encryption, the process of encoding information in such a way that only
the intended person (or computer) with the key can understand it. Two forms of encryption in
common use are symmetric (conventional, private key, or secret key) encryption and public key
(asymmetric) encryption.

This topic covers the fundamentals of encryption and cryptosystems, explores basic principles of
symmetric and asymmetric encryption, and discusses two widely used symmetric and asymmetric
algorithms.

Topic objectives:

Give an overview of encryption including relevant concepts and terminology, different types
of encryption, and cryptanalysis.
Describe the symmetric cryptosystem, basic encryption techniques, and the Data Encryption
Standard (DES) algorithm.
Describe the public key cryptosystem and its features.
Explain how the RSA algorithm works.

Contact Webmaster

Page 1 of 22

mailto:onlinelearning@ist.psu.edu

http://ist.psu.edu

Published on IST 554 (https://online.ist.psu.edu/ist554)

Lesson 1: Encryption Fundamentals
Cryptography, or “secret writing,” is derived from the Greek words kryptos, for “hidden,” and
graphos for “I write.” In a very broad sense, it is the study of techniques related to aspects of
information security. It is far older than today’s technology; it has been used throughout history to
ensure the confidentiality of information and communications. In today’s electronic age,
cryptography has evolved into a mathematical discipline that plays a major role in business and
government.

Computer encryption is based on the science of cryptography. It is increasingly employed in
protecting widely-used systems, e.g., in the financial industry to protect money transfers, in
electronic commerce to protect credit card information, and in data communication to secure
exchanges of proprietary information.

This lesson covers encryption and cryptosystems, including relevant concepts and terminologies. It
then discusses two different categories of cryptosystems, attacks against cryptosystems, and
different types of cryptanalysis.

Lesson objectives:

Explain basic concepts and terminologies involved in encryption systems.
Discuss two different categories of cryptosystems.
Describe cryptanalysis and four types of cryptanalysis.

Basic Encryption Concepts

Encryption

Process to encode or cipher a message to conceal its meaning.
Ensures that a message remains confidential when it is stored or transmitted electronically.

Decryption

Encryption run in reverse to decode or decipher an encrypted message into its original form.

Plaintext

Message in its original form.

Ciphertext

Encrypted message. The ciphertext message contains all the information of the plaintext
message, but is not in a format readable by a human or computer without the proper
mechanism to decrypt it.

Cryptosystem

A cryptosytem is a system of cryptography using encryption and decryption. The encryption
algorithm encrypts the plaintext message into encoded ciphertext, and the decryption algorithm
decrypts the ciphertext into the plaintext message. Such an encryption algorithm is also known as a
cipher, or encipherment, as is the decryption algorithm.

The operation of cryptosystems requires the use of a secret (encryption) key. With each key, the
encryption algorithm produces a different ciphertext output. The secret key is given to the receiver
of the message to decrypt the ciphertext back to its plaintext form. Without the key, the
cryptosystem cannot be used to encrypt or decrypt.

Contact Webmaster
© Copyright 2013 College of IST

Page 2 of 22

mailto:onlinelearning@ist.psu.edu

http://ist.psu.edu

Published on IST 554 (https://online.ist.psu.edu/ist554)

Figure 1.1 illustrates a simple model of a cryptosystem, in which an encryption algorithm replaces
each letter in the original message “fire” with the letter that appears “k” positions later in the
alphabet. In this example, the key is 5. Therefore, the encryption algorithm replaces each letter in
“fire” with the letter that is 5 positions later in the alphabet. So, “f” is replaced with “k,” “i” is
replaced with “n,” “r” is replaced with “w,” and “e” is replaced with “j.”

Figure 1.1. A Simple Model of a Cryptosystem

This creates the ciphertext, “knwj.” To read the original meaning, the ciphertext message will be run
through a decryption algorithm which replaces each letter in the ciphertext message with the
original letter based on the key. This process reproduces the plaintext message “fire.”

To read an encrypted message you need to know how it was created. Once you crack the key,
meaning you figure out how each letter was replaced, you gain access to all the information that has
been encrypted with the encryption algorithm and the key. The encryption key must be kept secret
in order to make the encryption secure.

Before the advent of the Internet, a cryptosystem was primarily concerned with the ciphering and
deciphering of messages in secret code to ensure privacy and confidentiality of information. Now,
cryptosystems have developed to encompass other features such as integrity protection and
authentication. Integrity protects data from unauthorized alteration. Authentication assures the
identity of the receiver or originator of data.

Cryptosystem Types

There are two kinds of cryptosystems: symmetric and asymmetric.

Symmetric cryptosystems use the same key (secret key) to encrypt and decrypt a message.
Asymmetric cryptosystems use one key (public key) to encrypt a message and a different key
(private key) to decrypt it.

Until 1976, people had been using only symmetric cryptosystems. In 1977, two American

Contact Webmaster
© Copyright 2013 College of IST

Page 3 of 22

mailto:onlinelearning@ist.psu.edu

http://ist.psu.edu

Published on IST 554 (https://online.ist.psu.edu/ist554)

mathematicians, W. Diffie and M. E. Hellman, introduced the asymmetric (public key) cryptosystem.
This system requires two keys, an unguarded public key used to encrypt the plaintext and a guarded
private key used for decryption of the ciphertext. The two keys are mathematically related but
cannot be deduced from one another.

Symmetric encryption streamlines the process of encrypting and decrypting large messages using
the same key, while asymmetric encryption uses matched public/private key pairs. Anyone can
encrypt the original message with the public key, but only an authorized user with the private key
can decrypt it.

Today, there are many popular encryption methods that are publicly available and thoroughly
tested. The Data Encryption Standard (DES) and the International Data Encryption Algorithm (IDEA)
are the two most commonly used symmetric techniques. Other symmetric methods include Double
DES (2DES), Triple DES (3DES), and Blowfish. The most common asymmetric technique is the RSA
algorithm. Others include Pretty Good Privacy (PGP), Secure Sockets Layer (SSL), and the Advanced
Encryption Standard (AES).

Four Types of Cryptanalysis
Cryptanalysis is the study of the principles and methods used to break ciphers or cryptosystems.
Cryptanalysis analyzes the characteristics of the ciphers or cryptosystems and attempts to find
weaknesses in their design or implementation that will permit the secure keys to be deduced. Once a
key is cracked, a cryptanalysis is able to figure out the plaintext for all past and future messages
that continue to use the compromised setup.

The following are four common types of cryptanalysis that differ based on how much information
about the system under attack is available for analysis. The list begins with the most difficult to
attack (ciphertext-only) and moves through to the easiest to attack (chosen ciphertext):

Ciphertext-only analysis: The attacker has only the transmitted ciphertext and the
algorithm from which to determine the plaintext. Ciphertext is easy to obtain through
methods such as eavesdropping. Although difficult, successful decryption using cyphertext-
only is always a possibility, and the resistance to this type of attack depends on how strong
the algorithm is.
Known plaintext analysis: The attacker has a set of ciphertexts to which he knows the
matching plaintext from an arbitrary message. Plaintext can be known if it is part of a
standard greeting or it is something so common that it is almost guaranteed to be in a
message. For example, a letter beginning with “Dear Sir,” or a computer session starting with
“LOGIN:”. In some systems, one known ciphertext and plaintext pair will reveal the key and
compromise the overall system for both prior and subsequent transmissions. The resistance
to this type of attack depends on the security of the keys.
Chosen plaintext analysis: The attacker arbitrarily chooses a plaintext message and is
able to find and translate its corresponding cyphertext message. The plaintext is selected
specifically to have certain mathematical characteristics. The attacker attempts to reveal the
structure of the key by comparing the ciphertext with the original plaintext.
Chosen Ciphertext Analysis: The attacker arbitrarily chooses a ciphertext message and is
able to find and translate its corresponding plaintext message. The attacker attempts to
reveal the structure of the key by comparing the ciphertext with the original plaintext.

Cryptanalysis is actively practiced by a broad range of companies to test the strength of their
security products or to exploit weaknesses in their secure Web sites. In order to create a secure
cryptosystem, you have to design against possible cryptanalysis.

Lesson Wrap-Up
With respect to the Internet, there are many types of data and messages that people would want to

Contact Webmaster
© Copyright 2013 College of IST

Page 4 of 22

mailto:onlinelearning@ist.psu.edu

http://ist.psu.edu

Published on IST 554 (https://online.ist.psu.edu/ist554)

keep secret. Data encryption is an important security measure that plays a central role in ensuring
privacy and confidentiality when data is exchanged electronically. The use of encryption restricts
unintended recipients from viewing data deemed confidential and potentially dangerous if accessed
by unauthorized or malicious parties. Today’s encryption technology hinders attacks by even
relatively powerful computers, requiring months or even years for those computers to break the
encryption system.

Now that you have completed this lesson, you should be able to:

Explain basic concepts and terminologies involved in encryption systems.
Describe the symmetric cryptosystem, basic encryption techniques, and the DES algorithm.
Describe the public key cryptosystem and its features.
Explain how the RSA algorithm works.

Lesson 2: Symmetric Encryption
Symmetric encryption, also referred to as conventional encryption, secret key, or single key
encryption, was the only type of encryption in use prior to the development of public key encryption
in the late 1970s. It remains the most widely used type of encryption today.

This lesson focuses on symmetric encryption and begins with a discussion of a general model of the
symmetric cryptosystem. The lesson then proceeds to discuss the four basic symmetric encryption
techniques and ends with a description of the data encryption standand (DES) algorhythm, one of
the most important symmetric encryption algorithms.

Lesson objectives:

Describe a general model of the symmetric cryptosystem.
Discuss four basic symmetric encryption techniques.
Describe the data encryption standard (DES) and how it works.

The Symmetric Cryptosystem
In symmetric key encryption, each computer has a secret key that it uses to encrypt a message
before it sends the message over the network to another computer. Symmetric key encryption
requires the same key to be installed in each of the computers that will be communicating with each
other. Successful decryption of ciphertext into original plaintext is accomplished using the same key
as was used for the corresponding encryption of plaintext into ciphertext.

Figure 2.1: Symmetric Cryptosystem

As shown in Figure 2.1, a symmetric cryptosystem consists of two hosts. Host A encrypts the original
plaintext message using a specific encryption algorithm and a shared secret key, K. It then transmits
the encrypted ciphertext message over the Internet to Host B. When Host B receives the ciphertext
message, it decrypts it using its decryption algorithm and the same secret key, K.

Note: The security of symmetric encryption depends on the secrecy of the key, not the secrecy of
the algorithm. The encoded message is sent through an insecure channel (e.g., the Internet);

Contact Webmaster
© Copyright 2013 College of IST

Page 5 of 22

mailto:onlinelearning@ist.psu.edu

http://ist.psu.edu

Published on IST 554 (https://online.ist.psu.edu/ist554)

however, the shared secret key, K, must be transmitted through a secure channel.

Example
Two parties involved in a communication can meet somewhere or call each other to obtain the key.

It is assumed that it is not feasible or practical to decrypt a message or figure out a key on the basis
of the ciphertext plus knowledge of the encryption/decryption algorithm. In other words, with the use
of symmetric encryption, the principal security challenge is maintaining the secrecy of the key. Both
the sender and recipient must have obtained copies of the secret key in a secure fashion and must
keep the key secure. If someone discovers the key and knows the algorithm, all communication
using this key is readable.

Symmetric Encryption Types

Block Cipher

A block cipher is a type of symmetric encryption algorithm that transforms a fixed-length block of
plaintext data into a block of ciphertext data of the same length. This transformation takes place
under the action of a user-provided secret key. Decryption is performed by applying the reverse
transformation to the ciphertext block using the same secret key. The fixed length is called the block
size, which is usually 64 bits for many block ciphers.

Stream Cipher

A stream cipher is a type of symmetric encryption algorithm that operates on one unit of plaintext at
a time. The unit is most often a bit, although it could be a byte or word. Stream ciphers typically
execute at a faster speed than block ciphers. A stream cipher generates what is called a keystream
(a sequence of bits used as a key). Encryption is accomplished by combining the keystream with the
plaintext, usually with the bitwise XOR operation. The ith symbol of plaintext is encrypted with the ith
part of keystream. Stream ciphers are used in applications where plaintext comes in quantities of
unknowable length.

Contact Webmaster
© Copyright 2013 College of IST

Page 6 of 22

mailto:onlinelearning@ist.psu.edu

http://ist.psu.edu

Published on IST 554 (https://online.ist.psu.edu/ist554)

Basic Encryption Techniques
There are four basic encryption techniques: substitution, permutation (or transposition), product
ciphers (combinations and iterations of substitution and permutation), and perfect secrecy (Vernam
One-Time Pad).

1. Substitution

A substitution cipher encodes the plaintext (usually with letters or numbers) using a substitution
rule. It maintains the order of the units in the message, but replaces them with other symbols or
groups of symbols.

Simple Alphabetic Substitution

The simple alphabetic substitution is based on the string operation of substitution in which each
letter of the message is replaced by another letter or symbol according to a fixed mapping rule.

Example
The Caesar cipher system replaces each letter with the letter that appears three positions later in
the alphabet. So, each occurrence of A in the plaintext was replaced by D, each B by E, …, each Y by
B, and each Z by C.

For example, using the following character set:

A B C D E F G H I J K L M

N O P Q R S T U V W X Y Z

Using the Caesar cipher scheme, we would encrypt the string ENCRYPTION to ciphertext
HQFUBSWLRQ. To decode the message, the recipient uses the same key, 3, and recovers the
plaintext by applying the reverse transformation which replaces each character by the character
three positions earlier in the alphabet. This scheme is vulnerable because it is easy to figure out the
key by simply trying the 26 possible values for the key.

Scenario
Simple alphabetic substitution is based on the same principle as a toy decoder ring. Using the
decoder ring, someone could send an encrypted or secret message, then the decoder ring is used to
identify what letters are necessary for substitution to make the message readable (to decrypt the
message).

Poly-Alphabetic Substitution

More than one alphabet can be used to make substitution ciphers more secure. Such ciphers are
called poly-alphabetic, which means that the same letter of a message can be represented by
different letters when encoded. Such a one-to-many correspondence makes it much more difficult to
crack the code.

The following example illustrates how to encode a message based on different positions of each
character. Suppose the character set and positions of characters are given by the following:

Pos
itio
n

0 1 2 3 4 5 6 7 8 9 10 11 12

Contact Webmaster
© Copyright 2013 College of IST

Page 7 of 22

mailto:onlinelearning@ist.psu.edu

http://ist.psu.edu

Published on IST 554 (https://online.ist.psu.edu/ist554)

Cha
ract
er

A B C D E F G H I J K L M

Pos
itio
n

13 14 15 16 17 18 19 20 21 22 23 24 25

Cha
ract
er
N O P Q R S T U V W X Y Z

As we can see, each letter has a unique position number.

For example, the position number of H is 7. The ciphertext is determined by adding the position
number of the key character-by-character to the plaintext string. If the sum is less than 26, then the
position number of the ciphertext is the sum. If the sum is greater than 26, then the position number
of the ciphertext is the sum minus 26.

Example 1
Assume the key is E and the plaintext is B; the position number for the ciphertext is the sum of the
position number of B and the position number of E. That is, 1 + 4 = 5. Therefore, the ciphertext is F.

Example 2
Assume the key is Y and the plaintext is X. The ciphertext is V (24 + 23 – 26 = 21)

Example 3
Given the plaintext ENCRYPTION and the key SECRET as shown below, this method creates the
ciphertext WREICILMQE.

Plaintext: E N C R Y P T I O N

Repeated key: S E C R E T S E C R

Ciphertext: W R E I C I L M Q E

To decrypt the ciphertext, the recipient must know the key and recover the plaintext by subtracting
the position number of the key, character by character, from those in the ciphertext.

The Substitution Table

Contact Webmaster
© Copyright 2013 College of IST

Page 8 of 22

mailto:onlinelearning@ist.psu.edu

http://ist.psu.edu

Published on IST 554 (https://online.ist.psu.edu/ist554)

A different substitution operation is to use a substitution table. For example:

Original Character: ABCDEFGHIJKLMNOPQRSTUVWXYZ

Substitute Character: ZYXWVUTSRQPONMLKJIHGFEDCBA

In this case, the plaintext ENCRYPTION is encrypted to be VMXIBKGRLM. To decode the ciphertext
string, the recipient must again know the key, that is, the substitution table.

The substitution table scheme is considerably more secure than the simple Caesar cipher because it
has a huge key space. Key space is the range of possible values of a key. The substitution table has
a key space of 26!, which is approximately 1,028. However, the substitution table can be still be
trivially broken in a known plaintext attack and is also easily broken in a ciphertext-only attack (for
natural language plaintext).

Note: Doing multiple substitutions in sequence will not strengthen the encryption.

Example
When we apply a simple alphabetic substitution with key 3 to the string ENCRYPTION, the resulting
ciphertext is HQFUBSWLRQ.

If we perform another simple alphabetic substitution with key 2, the resulting ciphertext is
JSHWDUYNTS.

Together these two substitutions achieve the same result as a single substitution with key 5, and the
decipherment is easy by simply finding the key 5. In this case, deciphering the result of these two
substitutions is no more difficult than deciphering the result of one substitution.

2. Simple Permutation (Transposition)

Contact Webmaster
© Copyright 2013 College of IST

Page 9 of 22

mailto:onlinelearning@ist.psu.edu

http://ist.psu.edu

Published on IST 554 (https://online.ist.psu.edu/ist554)

A simple permutation cipher is an encoding process that does not change any of the letters of the
original message, but rearranges the position of the letters. One simple permutation cipher reverses
the order of the letters.

Example 1
The string ENCRYPTION becomes encoded as NOITPYRCNE.

Such backward writing is easy to recognize and decode.

Example 2
The rail fence is another example of a simple permutation cipher in which the plaintext is staggered
between two rows and then read off to give the ciphertext. In a two-row rail fence the message
ENCRYPTION becomes:

E C Y T O

N R P I N

Which is ECYTONRPIN.

Permutation works as a block cipher. The above two examples use a block size of 1. When the block
size is greater than 1, a common method of permutation is to divide the plaintext string into blocks
(substrings) and reorder the position of each block based on the key. In the following example, the
plaintext string is divided into blocks of size 4 and the position of each block is permuted based on
the key:

Example key:

The string ENCRYPTION is encrypted (after the addition of a randomly selected character X so that
the string length is a multiple of the block length) as follows:

Contact Webmaster
© Copyright 2013 College of IST

Page 10 of 22

mailto:onlinelearning@ist.psu.edu

http://ist.psu.edu

Published on IST 554 (https://online.ist.psu.edu/ist554)

Plaintext: ENCR YPTI ONXX XXXX

Ciphertext: XXXX ONXX ENCR YPTI

Using the same key and the same block size, the string THISISASECRETMESSAGE will be encrypted
to be as follows:

Plaintext: THIS ISAS ECRE TMES SAGE XXXX XXXX XXXX

Ciphertext: TMES ECRE THIS ISAS XXXX XXXX SAGE XXXX

To decode the ciphertext string, the recipient must know the key for permutation and then put them
in the correct order.

The permutation scheme has key space of N! for block size N. It can be trivially broken for a known
plaintext attack and be easily broken for a ciphertext-only attack (for natural language plaintext).
Similar to substitution, multiple encipherment does not help. Permutation is a group. The
combination of the two permutations is also a permutation. Thus, there is no point in doing two
permutations in sequence. In modern cryptography, permutation cipher systems serve mainly as one
of several methods used as a step in forming a product cipher.

3. Product Ciphers

The purpose of product ciphers is to try to produce a stronger cryptosystem through combinations
and iterations of substitution and permutation. A strong cryptosystem needs to have a large key
space and will produce ciphertext that appears random to all standard statistical tests. A strong
cryptosystem will resist all known previous attacks.

For example, the image above is a combination of substitution and permutation to encrypt a
plaintext message to ciphertext.

A well known example of a product cipher is Data Encryption Standard (DES), which is discussed
later in this lesson.

Contact Webmaster
© Copyright 2013 College of IST

Page 11 of 22

mailto:onlinelearning@ist.psu.edu

http://ist.psu.edu

Published on IST 554 (https://online.ist.psu.edu/ist554)

4. Perfect Secrecy – Vernam One-Time Pad
The perfect secrecy scheme, Vernam One-Time Pad algorithm is a stream cipher, which requires only
a file (keystream) called the one-time pad (OTP) for the encryption of a plaintext message. The one-
time pad has some important characteristics, including:

it has the same length as the plaintext message;
it consists of a series of bits generated completely at random using a pseudo-random number

generator (PRNG); and
no sequences in the pad may be used twice for encryption.

Figure 2.2: Perfect Secrecy

As shown in Figure 2.2, the one-time pad is a simple XOR algorithm. Using the XOR operation, we
get:

First Bit Operation Second Bit Result 0 XOR 0 0 0 XOR 1 1 1 XOR 0 1 1 XOR 1 0

We will make these assumptions:

M (initial plaintext message M of finite length) M1, …, Mi, …, Mn K (one-time pad K) K1, …, Ki, …, Kn
C (encoded ciphertext C) C1, …, Ci, …, Cn

Each byte of the initial plaintext Mi is encrypted by XOR-ing with a byte of the Pad Ki to produce each
byte of ciphertext Ci. The recipient obtains the initial plaintext Mi by XOR-ing each byte of the
ciphertext Ci with Ki. Then, the next byte of the initial plaintext and the next byte of the Pad are used
(and so on). A party who does not have the pad will not have the least chance to decrypt the
message. The intended recipient, however, has no problem at all.

Example 1
Let’s start with a particular (the ith) byte of plaintext Mi. Assume the following bit values in each byte
in this example:

Mi = [0, 0, 1, 1, 0, 1, 0, 1] Ki = [0, 1, 0, 1, 0, 0, 0, 1] Ci = [0, 1, 1, 0, 0, 1, 0, 0]

A byte of ciphertext Ci is produced by XOR-ing plaintext Mi with the Pad Ki. Mi Operation Ki Ci 0 XOR
0 0 0 XOR 1 1 1 XOR 0 1 1 XOR 1 0 0 XOR 0 0 1 XOR 0 1 0 XOR 0 0 1 XOR 1 0

The recipient obtains the initial plaintext Mi by XOR-ing ciphertext Ci with the Pad Ki.

Ci Operation Ki Mi 0 XOR 0 0 1 XOR 1 0 1 XOR 0 1 0 XOR 1 1 0 XOR 0 0 1 XOR 0 1 0 XOR 0 0 0 XOR 1
1

Example 2
Now, let’s examine the encryption for a real message. Let’s say the initial message M is LOGIN. One
letter is one byte. The binary code for each byte of M is:

L = [0, 1, 0, 0, 1, 1, 0, 0]

O = [0, 1, 0, 0, 1, 1, 1, 1]

G = [0, 1, 0, 0, 0, 1, 1, 1]

Contact Webmaster
© Copyright 2013 College of IST

Page 12 of 22

mailto:onlinelearning@ist.psu.edu

http://ist.psu.edu

Published on IST 554 (https://online.ist.psu.edu/ist554)

I = [0, 1, 0, 0, 1, 0, 0, 1]

N = [0, 1, 0, 0, 1, 1, 1, 0]

Let’s assume the randomly generated One-time Pad happens to be MYKEY. The binary code for each
byte of the pad is:

M = [0, 1, 0, 0, 1, 1, 0, 1]

Y = [0, 1, 0, 1, 1, 0, 0, 1]

K = [0, 1, 0, 0, 1, 0, 1, 1]

E = [0, 1, 0, 0, 0, 1, 0, 1]

Y = [0, 1, 0, 1, 1, 0, 0, 1]

The ciphertext is produced by XOR-ing each byte of plaintext M with each byte of the pad K. Each
byte of ciphertext is shown below in both binary code and ASCII code:

C1 = [0, 0, 0, 0, 0, 0, 0, 1] = SOH, Start of Header (in ASCII code) C2 = [0, 0, 0, 1, 0, 1, 1, 0] = SYN
(Synchronous Idle) C3 = [0, 0, 0, 0, 1, 1, 0, 0] = FF (Form Feed) C4 = [0, 0, 0, 0, 1, 1, 0, 0] = FF
(Form Feed) C5 = [0, 0, 0, 1, 0, 1, 1, 1] = ETB (End of Transmission, Block)

Note: Each byte of ciphertext is a non-printable character.

For instance, SOH doesn’t mean it has three characters; rather, it is a format specification character
meaning Start of Header. Similarly, SYN, FF, and ETB are all non-printable one-byte characters.

To obtain the original message, each byte of ciphertext is XOR-ed with each byte of the pad as
shown below:

C1 XOR M = [0, 0, 0, 0, 0, 0, 0, 1] XOR [0, 1, 0, 0, 1, 1, 0, 1] = [0, 1, 0, 0, 1, 1, 0, 0] C2 XOR M = [0,
0, 0, 1, 0, 1, 1, 0] XOR [0, 1, 0, 1, 1, 0, 0, 1] = [0, 1, 0, 0, 1, 1, 1, 1] C3 XOR M = [0, 0, 0, 0, 1, 1, 0, 0]
XOR [0, 1, 0, 0, 1, 0, 1, 1] = [0, 1, 0, 0, 0, 1, 1, 1] C4 XOR M = [0, 0, 0, 0, 1, 1, 0, 0] XOR [0, 1, 0, 0, 0,
1, 0, 1] = [0, 1, 0, 0, 1, 0, 0, 1] C5 XOR M = [0, 0, 0, 1, 0, 1, 1, 1] XOR [0, 1, 0, 1, 1, 0, 0, 1] = [0, 1, 0,
0, 1, 1, 1, 0]

The matching message in ASCII code is LOGIN.

Two advantages of the OTP system are that the key is random and, unlike the other three techniques
(substitution, permutation, and product ciphers), the key cannot be reused. Attacks such as known-
plaintext cryptanalysis can reveal the portion of the key that has been used, but cannot reveal
anything about the future bits of the key. However, perfect secrecy is generally impractical because
the key needs to be as long as the message, though theoretically it should produce the most secure
ciphertext possible. Stream ciphers were developed as an approximation to the one-time pad.

Additionally, just like other symmetric encryption schemes, one weak point in perfect secrecy is the
exchange of the OTP between the sender and the recipient. Obviously, the pad should be
transmitted in a secure manner. Should the pad reside on a hard disk, it is imperative that the pad
file be erased after use. and if it resides on a compact disc, thorough cutting up will suffice.

Data Encryption Standard (DES) Overview
Most modern encryption algorithms use techniques by combining several substitution and
permutation operations. One of the best known is the Data Encryption Standard (DES) developed in
the early 1970s by the federal government and the IBM Corporation. It was approved as a federal

Contact Webmaster
© Copyright 2013 College of IST

Page 13 of 22

mailto:onlinelearning@ist.psu.edu

http://ist.psu.edu

Published on IST 554 (https://online.ist.psu.edu/ist554)

standard in 1977, but it was abandoned due to the concern that it may become too widespread and
an enticing target for cryptanalysis. In the years since, it has stood up remarkably well against public
cryptanalysis.

Figure 2.3: DES

As shown in Figure 2.3, DES is a block cipher with a block size of 64 bits. It enciphers and decrypts
data in blocks of 64 bits of binary data. The key used by DES has a length of 64 bits, of which 56 bits
are used for encryption in the classical sense. The remaining 8 bits are parity bits used in checking
for errors. Even with just 56 bits, there are over seventy quadrillion possible keys (simply 2^56).

The mechanics of DES are very simple. Given a message that requires encryption, one must first pick
a 64-bit key and then convert the plaintext into binary form. DES uses 16 rounds to transform the
plaintext, meaning the main algorithm is repeated 16 times to produce the ciphertext. DES uses the
product cipher technique. During each round, it does permutation, then substitution, and then
permutation again. Each round uses part of the key.

How DES Encrypts Data
The first step in the DES procedure is to change the order within each block, called initial
permutation. Within a block of 64 bits, the leftmost bit is known as the first bit, and the rightmost bit
is the sixty-fourth bit. For example, a table can be specified to make the fifty-eighth bit in the original
string become the first bit in this new block, the fiftieth bit become the second bit, and so forth. In
this step, permutation is used in the strict mathematical sense that only the order is changed (unlike
the permutation matrix in linear algebra).

In the second step, the results of this initial permutation are broken down into two halves. The left 32
bits become L0. The right 32 bits become R0. Now the data is processed through the following
transformation 16 times, for 1<=n<=16:

Ln = Rn-1 where R0 occurs at n=1

Rn = Ln-1 + f(Rn-1,Kn) where L0 occurs at n=1

Contact Webmaster
© Copyright 2013 College of IST

Page 14 of 22

mailto:onlinelearning@ist.psu.edu

http://ist.psu.edu

Published on IST 554 (https://online.ist.psu.edu/ist554)

Here function f( ) denotes substitution operation on two blocks–a data block of 32 bits and a key Kn
of 48 bits–to produce a block of 32 bits. The “+” symbol denotes XOR addition (bit-by-bit addition
modulo 2). Modulo returns the remainder of a number N divided by another number M.

Example
29 modulo 9 equals 2, and 1 modulo 2 equals 1.

Figure 2.4: DES Operation

This procedure is performed sixteen times. Figure 2.4 illustrates how these two strings, Ln and Rn,
are generated during each round, where Rn-1 (the previous round) forms the new left thirty-two bits
Ln, and Ln-1 (the previous round) combined with Rn-1 and the key forms the new right thirty-two bits
Rn for 1<=n<=16.

Example
During the first round, the new left part L1 (32 bits) is formed by the right 32 bits R0, and the new
right part R1 (32 bits) is determined by the left 32 bits L0, the right 32 bits R0 and 48 bits of the key.
The following is what happens after the first iteration:

L1 = R0, R1 = L0 + f(R0,K1)

These two strings L1 and R1 are united to be a new 64-bit string (or block). Then the second round
will happen as shown below:

L2 = R1, R2 = L1 + f(R1,K2)

The result after sixteen rounds is a final block (ciphertext), for n = 16, of L16R16. Decoding is
accomplished by simply running the process backwards.

Attacks on DES
No easy attack on DES has yet been discovered, despite research efforts over many years. There is
no feasible way to break DES other than an exhaustive search–a process which takes 255 steps on
average because of DES’ key space of 2^56. However, cryptanalysis methods that rely on
knowledge of some of the plaintext have had some success. The consensus of the cryptography
community is that, if it is not currently so, DES will soon be insecure. As a result, DES was no longer
used by the US Government as of November 1998.

Example
For a DES known-plaintext attack, the 56-bit key can be broken on average in 2^55 ? 3.6 * 10^16
trials.

As shown in the following table, the time required to break DES is 10^9 years if one trial can be
made in one second. If the attacker can attempt 10^3 trials in one second, the time to break DES is
10^6 years. If the attacker can attempt 10^6 trials in one second, the time required is 10^3 years.
For 10^9 trials made in one second, the time is one year. For 10^12 trials made in one second, time
to break DES is ten hours.

Contact Webmaster
© Copyright 2013 College of IST

Page 15 of 22

mailto:onlinelearning@ist.psu.edu

http://ist.psu.edu

Published on IST 554 (https://online.ist.psu.edu/ist554)

Time required Trials/second

10^9 years 1

10^6 years 10^3

10^3 years 10^6

1 year 10^9

10 hours 10^12

The fastest DES chip can perform close to one million encryption (trials) per second. If we use a
million such chips, we can break DES in ten hours on average. Such a system would cost millions of
dollars.

In addition, Biham and Shamir have shown that differential cryptanalysis can break DES in 2^48 ?
2.8 * 10^14 trials. Differential cryptanalysis is usually a chosen plaintext attack, meaning that the
attacker must be able to obtain encrypted ciphertexts for some set of plaintexts of his choosing and
study how a difference in an input relates to the resultant difference in the output. The basic method
uses pairs of plaintext related by a constant difference. The attacker computes the differences of the
corresponding ciphertexts, hoping to detect statistical patterns in their distribution. More
sophisticated variations allow the key to be recovered faster than by an exhaustive search. DES-like
ciphers with larger keys would also be susceptible to such attacks. However, differential
cryptanalysis requires vast amounts of chosen ciphertext (2^47 pairs) and is not very practical.

The question we need to ask is “How do we use DES to create stronger encryption?”

Given the increase in the computational power of today’s computers, in the real world, people tend
to use a series of DES encipherments with different keys to enhance security.

Lesson Wrap-Up
The symmetric encryption scheme discussed in this lesson requires that all parties involved in
communications know the key or keys used in encrypting the plaintext. This means that although the
plaintext message may be transmitted through some insecure public channel such as electronic
mail, the secret keys must be transmitted from the sender to the recipient in some secure channel. If
you could send the secret key securely, then, in theory, you would simply use that secure channel to
send your message and would not need the symmetric cryptosystem. This problem of maintaining
secrecy of the key is compounded when the key must be shared by multiple users.

We soon will learn about another efficient and reliable type of encryption solution that eliminates this
problem.

Now that you have completed this lesson, you should be able to:

Describe a general model of the symmetric cryptosystem.
Discuss four basic symmetric encryption techniques.
Describe DES and how it works.

Page 16 of 22

mailto:onlinelearning@ist.psu.edu

http://ist.psu.edu

Published on IST 554 (https://online.ist.psu.edu/ist554)

Lesson 3: Public-Key Encryption
All cryptosystems must deal with key management issues, which involve the generation,
transmission and storage of keys. With the use of symmetric encryption, the principal security
problem is maintaining the secrecy of the key. The other major form of encryption is public-key
encryption. It was designed to solve the key management problem of symmetric encryption by using
two keys, one for encryption and one for decryption. This lesson introduces public-key encryption
and examines the RSA algorithm in detail.

Lesson objectives:

Describe the basic concept of a public-key cryptosystem and how it works.
Identify the features of a public key cryptosystem.
Describe the RSA algorithm.

The Public-Key Cryptosystem
The concept of the public-key cryptosystem was conceived in 1976 by Whitfield Diffie and Martin
Hellman. Because of this, it is sometimes called the Diffie-Hellman encryption.

The public-key cryptosystem relies on one key for encryption and a different but related key for
decryption. Each computer gets a pair of keys, the one used for encryption is the public key and the
other one used for decryption is the private key. The private key is kept secret and is known only to
your computer, while the public key is given by your computer to any computer that wants to
communicate securely with your computer. That is, anyone can send a confidential message to you
by using the public key for encryption, but only you, the intended recipient of the message, can
decrypt it with the companion private key.

The public key does not need to be distributed to other parties via secure channels. The public key
can be known to anybody; however, it needs to be distributed through reliable channels so that it
cannot be altered. If the public key is altered, then using the companion private key cannot decrypt
the message.

Figure 3.1: Public-Key Cryptosystem

Figure 3.1 illustrates a general-purpose public-key cryptosystem consisting of two hosts (A and B),
an encryption algorithm, and a decryption algorithm. Host A needs to send confidential messages to
Host B via some insecure channel, such as the Internet. In this example, the system operates in the
following steps:

1. Each host generates a pair of two keys to be used for the encryption and decryption of
messages.

2. Each host places its public key in a public register or other accessible file. The companion
private key is kept secure and only known to the host itself. Generally, each host maintains a
collection of public keys obtained from others.

3. When Host A wishes to send a private message to Host B, A encrypts the message using B’s
public key.

4. When Host B receives the message, it decrypts it using its private key. Other hosts cannot
decrypt the message because only B knows B’s private key.

Note:

Host A cannot use B’s private key to encrypt the message because nobody knows B’s private

Page 17 of 22

mailto:onlinelearning@ist.psu.edu

http://ist.psu.edu

Published on IST 554 (https://online.ist.psu.edu/ist554)

key, except B.
Host A cannot use A’s public key to encrypt the message because nobody can decrypt it,
except A.
Host A cannot use A’s private key to encrypt the message because anybody knows A’s public
key, and anybody can decrypt!

In a public-key cryptosystem, for each encryption key (public key) there is exactly one corresponding
decryption key (private key). The public and private keys are related in such a way that only the
corresponding private key can be used to decrypt a message that is encrypted by the public key.
However, the public key also needs to be significantly distinct from the private key such that it is
virtually impossible to derive the private key from the public key. The security of public key
encryption is based on such infeasibility of deriving B’s private key given knowledge of B’s public
key, chosen plaintext, and maybe chosen ciphertext.

Features of the Public-Key Cryptosystem

Figure 3.2: Hosts Communicating in an Open Environment

With the advent of the public-key cryptosystem, the need for the sender and recipient to share
secret information is eliminated. All participants have access to public keys; public keys need not be
distributed to other parties by secure channels. Private keys are generated locally by each
participant and need never be transmitted or shared. As long as each host protects its private key,
incoming communication is secure. At any time, a host can change the private key and publish the
companion public key to replace the old public key.

Notice that key distribution is very easy for public-key cryptosystems because one pair of keys can
be used to communicate with an unlimited number of other parties.

Example
Consider the kind of open communication environment as shown in Figure 3.2. With a public-key
cryptosystem, Host B, Host C, and Host D can use Host A’s public key to encrypt all their
communications with A, and A can simply use its own private key to decrypt all messages coming to
it.

Page 18 of 22

mailto:onlinelearning@ist.psu.edu

http://ist.psu.edu

Published on IST 554 (https://online.ist.psu.edu/ist554)

In secret-key systems, by contrast, you must use different keys when communicating with different
parties; and you must transmit the secret keys to them through some secure channel before you can
initiate communication.

Example
In the same environment as in Figure 3.2, Host A and Host B have to share a secret key KAB.

KAB needs to be distributed to Host A and B in such a secure manner that Host C and Host D cannot
get the key.

Host B encrypts the message using KAB, and Host A decrypts it using the same secret key KAB.

Host A and Host C must use a different key, KAC, for all communications between them such that
Host C encrypts the message using KAC and Host A decrypts it using KAC upon receiving the message.

If Host C encrypts the message with KAB, then both Host A and Host B can decrypt the message.

Similarly, a different key is required for communications between Hosts A and D.

In addition, the use of two keys in public key systems has profound consequences in the areas of
confidentiality, key distribution, and authentication. It is no longer necessary to trust the security of
some means of communication. The only requirement is that public keys be associated with their
users in a trusted (authenticated) manner (for instance, in a trusted directory). For example, if Host
C’s public key is associated with Host B, then other computers will use Host C’s public key to encrypt
messages that are intended for Host B. In such a case, Host B will not be able to decrypt the
received messages; however, Host C will be able to decrypt these messages.

Hybrid Cryptosystems: Public Key and Secret Key
A disadvantage of using public-key cryptosystems for encryption is speed. Many secret-key
encryption methods are significantly faster than the public-key encryption methods currently
available. Therefore, public-key cryptosystems are not commonly used in the real world to encrypt
long texts. In these instances, the best solution is to combine these two systems to get both the
secure-key management advantages of public-key systems and the speed advantages of secret-key
systems. For instance, the public-key system can be used to encrypt a secret key, which is then used
to encrypt a file or messages in a secret-key system.

Figure 3.3: A Cryptosystem Combining Public Key and Secret Key Methods

Figure 3.3 illustrates how to combine public-key cryptosystem and secret-key cryptosystem
methods. Host B has two keys – KB1 as a private key and KB2 as a public key. Host A and Host B also
share a key KAB for confidential communications between themselves. Remember, KAB needs to be
transmitted securely between A and B so nobody else can get the key. Therefore, Host A encrypts
KAB with Host B’s public key KB2. When Host B receives KAB, B decrypts it with B’s own private key KB1.
Nobody can decrypt KAB because only B has KB1 to decrypt the message encrypted by KB2. In this
way, the shared secret key KAB is distributed securely from A to B. Next, host A and B can encrypt
and decrypt messages between themselves using the shared secret key KAB.

RSA Overview
RSA is one of the first public key schemes developed in 1977 by Ron Rivest, Adi Shamir, and Len

Page 19 of 22

mailto:onlinelearning@ist.psu.edu

http://ist.psu.edu

Published on IST 554 (https://online.ist.psu.edu/ist554)

Adleman (RSA) at MIT. Since then, the RSA algorithm has been the most widely accepted and
implemented approach to public-key encryption.

In a public-key cryptosystem, the private key is always linked mathematically to the public key.
Therefore, it is possible to attack a public key system by deriving the private key from the public key.
The defense against this generally is to make it computationally infeasible to perform derivation. For
instance, some public-key cryptosystems are designed in such a way that deriving the private key
from the public key requires the attacker to factor large integers. This is the idea behind the RSA
public-key cryptosystem.

RSA is a block cipher in which the plaintext and ciphertext are integers between 0 and n-1 for some
n. The following steps describe the generation of RSA public and private keys:

1. Choose two large random prime numbers P and Q. A prime number is a positive integer that
has no other factors other than 1 and itself. For example, the only factors of 13 are 1 and 13,
making 13 a prime number.

2. Let N be determined by P and Q such that N = PQ.
3. Compute PHI such that PHI = (P-1)(Q-1).
4. Choose an integer E such that 1 < E < N, and E and PHI are relatively prime, which means

they have no prime factors in common. E does not have to be prime, it must be odd. PHI is a
even number.

5. Choose D such that 1 < D < PHI, and let D be determined by E and PHI through a one-way function, that is, from E to D is easy, but from D to E is almost impossible. This is easy to do--simply find an integer X such that D = (X*PHI + 1)/ E to be an integer, then use that value of D.

6. Publish public key (N, E).
7. Keep private key (N, D) and P, Q secret.

Note: N, E, and D are three specific numbers. N is the modulus. E is the public exponent, or
encryption exponent. D is the secret exponent, or decryption exponent.

The sender does the following to encrypt a message before sending it out to the recipient:

1. Obtains the recipient’s public key (N, E).
2. Represents the plaintext message as a positive integer.
3. Computes the ciphertext C = ME mod N.
4. Sends the ciphertext C to the recipient.

The recipient does the following to decrypt a message:

1. Uses his private key (N, D) to compute M = CD mod N.
2. Extracts the plaintext from the integer representative M.

Related Links
Wikipedia RSA Entry [1] – Explanations, along with helpful links, relating to RSA.
[2]

RSA Security [3] – This is an organization who designs and implements RSA security solutions for
other organizations. Look at some of the solutions on the website for examples of how RSA security
is utilized in real-world applications.

Page 20 of 22

http://en.wikipedia.org/wiki/RSA

http://rsasecurity.com/solutionsPrimary.asp

mailto:onlinelearning@ist.psu.edu

http://ist.psu.edu

Published on IST 554 (https://online.ist.psu.edu/ist554)

RSA Encryption/Decryption Example

1. Choose two large prime numbers P = 47, and Q = 71.
2. Compute N = P * Q = 47 * 71 = 3337.
3. Compute PHI = (P-1) * (Q-1) = (47-1) * (71-1) = 3220.
4. Choose E relatively prime to PHI, that is choose E such that it does not have any factor in

common with PHI = 3220. Suppose we select E = 79.
5. Compute D = E-1 Mod (P-1)* (Q-1) = 79-1 Mod 3220 = 1019
6. Public key = (N, E) = (3337, 79)
7. Private key = (N, D) = (3337, 1019)

Let’s suppose the block size is 3. To encrypt an original message 688232687966688, first divide the
message into blocks of three, as shown: 688 232 687 966 688 3 3 3 3 3

Do the following to encrypt the message block by block:

68879 mod 3337 = 1570
23279 mod 3337 = 2756
68779 mod 3337 = 2714
96679 mod 3337 = 2276
68879 mod 3337 = 1570
The encrypted ciphertext becomes: 1570 2756 2714 2276 1570 4 4 4 4 4

Note: Each block of three-digit plaintext becomes the block of four-digit ciphertext.

Next, do the following to decrypt the message block by block:

15701019 mod 3337 = 688
27561019 mod 3337 = 232
27141019 mod 3337 = 687
22761019 mod 3337 = 966
15701019 mod 3337 = 688

The key size of RSA is normally selected by the user. 512 bits is now no longer considered secure
although, in practice, it is still effectively impossible to crack a message encrypted with a 512-bit
key. In the real world, many implementations choose N to be 1024 bits. For more security, use 2048
or even 4096 bits. With the faster computers available today, the time taken to encrypt and decrypt
a 4096-bit modulus really isn’t an issue anymore.

Lesson Wrap-Up
The primary advantage of a public-key cryptosystem is increased security and convenience–private
keys never need to be transmitted or revealed to anyone. Thus, a public-key cryptosystem can be
used for secure key establishment in a secret-key system.

A public-key cryptosystem is not necessary when secure secret key distribution can take place (e.g.,
users can meet in private to exchange keys). Also, it is generally not necessary in a single-user
environment where secret-key cryptosystem is sufficient. For example, you can encrypt your
personal files using any secret key encryption algorithm along with, say, your personal password as
the secret key. In general, public-key cryptography is best suited for open systems with a large
number of users.

Page 21 of 22

mailto:onlinelearning@ist.psu.edu

http://ist.psu.edu

Published on IST 554 (https://online.ist.psu.edu/ist554)

Describe the basic concept of a public-key cryptosystem and how it works.
Identify the features of a public-key cryptosystem.
Describe the RSA algorithm.

Wrap-Up: Encryption
Internet connections are increasingly cited as the most frequent point of attack, ranging from 18%
for dial-up to 78% for high-speed. Data encryption is a major security measure to protect electronic
data (e-assets) of organizations and authorities against unauthorized access. It ensures business
processes and administrative procedures in the electronic world are binding and confidential.

Encryption schemes can be broken. However, a good scheme can be designed to be very difficult to
break. Symmetric cryptography combined with public-key cryptography offers the best solution for
encryption. Public-key cryptography is not meant to replace secret-key cryptography, but rather to
supplement it and to make it more secure. Secret-key cryptography remains extremely important
and is undergoing continued study and research.

Now that you have completed this topic, you should be able to:

Give an overview of encryption including relevant concepts and terminology, different types
of encryption, and cryptanalysis.
Describe the symmetric cryptosystem, basic encryption techniques, and the DES algorithm.
Describe the public-key cryptosystem and its features.
Explain how the RSA algorithm works.

Professor Preneel’s talk at SecureComm ’09 [4]

Source URL: https://online.ist.psu.edu/ist554/topicencryption

Links:
[1] http://en.wikipedia.org/wiki/RSA
[2] http://www.grc.nasa.gov/WWW/price000/pfc/htc/zz_rsaalg.html
[3] http://rsasecurity.com/solutionsPrimary.asp
[4] https://online.ist.psu.edu/sites/ist554/files/classpptsandpdfs/topic4preneelsecurecom09

Page 22 of 22

https://online.ist.psu.edu/sites/ist554/files/classpptsandpdfs/topic4preneelsecurecom09

https://online.ist.psu.edu/ist554/topicencryption