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

© Copyright 2013 College of IST

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.

Contact Webmaster

© Copyright 2013 College of IST

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

Contact Webmaster

© Copyright 2013 College of IST

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.

Contact Webmaster

© Copyright 2013 College of IST

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

Contact Webmaster

© Copyright 2013 College of IST

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.

Contact Webmaster

© Copyright 2013 College of IST

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.

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

Contact Webmaster

© Copyright 2013 College of IST

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

Powered by TCPDF (www.tcpdf.org)

Contact Webmaster

© Copyright 2013 College of IST

Page 22 of 22

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

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

http://www.tcpdf.org

mailto:onlinelearning@ist.psu.edu

http://ist.psu.edu