Cryptography
FRANCES RUGANYUMISA
Msc. in CITSE
CS 623 1
Outline
• Basic Concepts
• Secret-Key (Symmetric) Cryptography
• Public-Key (Asymmetric) Cryptography
• Modes
• Protocols
• Key Management
CS 623 2
Basic Concepts
CS 623 3
Brief Introduction
• The word “cryptography” derives from the Greek
word for “secrete writing”.
• Cryptography is the science of communication over
untrusted communication channels.
• Historically, cryptography has been associated with
spies, governments, military, and has been used in
warfare for thousands of years.
• Over the past 50 years, cryptography has acquired a
sound mathematical foundation, and has moved
from military application to commercial applications.
• This lecture attempts to give an overview of this
broad and specialized topic.
CS 623 4
A Motivating Example
• Consider an e-commerce scenario where Alice, a purchasing
agent, wants to order some products from Bob, her supplier.
• Requirements for the transaction:
1. Alice wants to be sure that she is really dealing with Bob and
not an impostor (authentication).
2. Bob wants to know that Alice is really Alice and not an
impostor (authentication), because Alice gets special prices
as negotiated.
3. Alice wants to keep the order secret from her competitors;
and Bob does not want other customers to see Alice’s special
prices (privacy).
4. Alice and Bob both want to be sure that crackers cannot
change the price or quantity (integrity).
5. Bob wants to ensure that Alice cannot later claim that she did
not place the order (non-repudiation).
CS 623 5
General Requirements
• Authentication: The sender knows that the message
is going to the intended recipient; and the recipient
knows that the message was sent by the proper
sender.
• Privacy: The message is secret: only the sender and
the intended recipient know its contents.
• Integrity: The message was not modified
(intentionally or accidentally) while in transit.
• Non-repudiation: The author of the message cannot
later deny having sent the message.
• Cryptographic techniques can be used to satisfy the
above requirements.
CS 623 6
How Does It Work?
• An ordinary message (the plaintext) is processed by
an encryption algorithm to produce a scrambled
message (the ciphertext).
• The receiver then uses a matching decryption
algorithm to recover the plaintext from the ciphertext.
• There would be no security if these algorithms were
known to everyone.
• Hence, there is an additional piece of input data called
a key.
• The key is secret, even though many people may know
the algorithms.
• The idea is the same as that of combination locks:
Many people may use locks with the same design, but
each one chooses a different combination (i.e., a
different key).
CS 623 7
Two Basic Types
• Secret-key (or symmetric) cryptography:
– Both encryption and decryption operations use the same
key.
– Secret-key systems have been around for many hundreds
of years.
• Public-key (or asymmetric) cryptography:
– Public-key systems use different keys for the encryption
and decryption operations.
– One key can be made public while the other key is kept
secret (and is called private key).
– Recent invention (dating from mid 1970s).
– Can grow more easily to worldwide scale and more easily
permit unaffiliated persons to communicate securely.
– Can be used to provide digital signatures (to be discussed
more later).
CS 623 8
Symmetric Cryptography
Plaintext input Plaintext output
“The quick
Ciphertext “The quick
brown fox “AxCv;5bmEseTfid3) brown fox
jumps over fGsmWe#4^,sdgfMwi jumps over
the lazy r3:dkJeTsY8R\s@! the lazy
dog” q3%” dog”
Encryption Decryption
Same key
(shared secret)
CS 623 9
Asymmetric Cryptography
Plaintext input Plaintext output
“The quick
Ciphertext “The quick
brown fox “Py75c%bn&*)9| brown fox
jumps over fDe^bDFaq#xzjFr@g jumps over
the lazy 5=&nmdFg$5knvMd’r the lazy
dog” kvegMs” dog”
Encryption Decryption
public Different keys private
Public key Private key
CS 623 10
Practical Use
• In practice, cryptographic systems often use both
secret-key and public-key cryptography together.
• Since secret-key algorithms are usually faster, it is
more efficient to use a secret-key algorithm to
encrypt the actual data.
• The system first generates a (random) key for the
secret-key algorithm.
• The system then encrypts that key using the public-
key algorithm.
• The receiver first decrypts the secret key using the
public-key algorithm, and then decrypts the data
using that newly decrypted key.
CS 623 11
Main Components
• There are 4 main components in the use of cryptography for
any practical systems: cryptosystems, modes, protocols,
and key management.
• The term cryptosystems refers to the cryptographic
algorithms and their characteristics.
• Modes refers to how the cryptographic algorithms are
initialized and used to manage messages that are longer
than a single block.
• Protocols refers to the ways in which cryptographic
algorithms are composed and applied to real problems (e.g.,
the securing of a communication channel or information in a
database).
– Very important for e-commerce because they are used for
protecting content as well as for payment systems.
• Key management refers to the essential problems of
creating, distributing, storing, and updating keys.
– Since modern cryptographic algorithms and protocols are
very strong, key management is a tempting target for
attackers.
CS 623 12
Cryptographic Strength
• One way to attack a cryptosystem is to try all possible
keys to decrypt a message (exhaustive search or
brute force attack).
• There must be enough possible keys to make this
attack computationally infeasible.
– The Data Encryption Standard (DES) in 1977 uses 56-bit keys.
– There are 256 possible keys (or 72.1 x 1015 different keys),
which seems sufficiently large.
– Several years ago, Digital Equipment Corporation built a chip
capable of 16,000,000 DES operations per second.
– If one were to build a machine with 1000 such chips, a 56-bit
key DES encrypted message could be broken in less than 8
weeks!
CS 623 13
Key Length
• Given a reasonably strong algorithm, how well the data is
protected depends largely on the length of the encryption key.
• An encrypted message must remain secret during the useful life
of the information.
– Financial credentials must remain secret beyond their
validity period.
– Contract bids must remain secret beyond the contract
award.
– Editorial material must remain secret until published.
– Confidential personal information must remain secret
beyond the lifetime of the person.
• The value of the information in the encrypted message governs
the resources used to attack it.
– An attacker would be foolish to spend $1 million to obtain
information worth $1 thousand.
– He may spend $1 million to obtain a secret worth $2 million.
CS 623 14
Key Length (cont.)
• Today, it is common to use 128-bit keys for
symmetric algorithms, both for
communication security and for the security
of data to be protected for 20 years.
• The current recommendation for asymmetric
algorithms is to use a minimum length of
1024 bits (or 2048 bits) for especially sensitive
applications or long term key.
CS 623 15
Key Updates
• The longer a key has been in used, the greater the
chance that it is discovered by subterfuge (rather
than by brute force attack).
• Hence, keys need to be updated from time to time.
• It is important to note that changing a key does not
increase the time that an attacker will need to break
it using brute force attack.
• However, changing a key will limit the amount of
information revealed if any particular key is
discovered.
• Example: If the encryption key is changed every
month, then only one month’s worth of information is
lost if a key is discovered.
CS 623 16
Secret-Key (Symmetric)
Cryptography
CS 623 17
Overview
• The message (plaintext) is encrypted into ciphertext using a key.
• The resulting ciphertext is sent to the recipient, who will decrypt
it using the same key.
• Hence, the same key must be known to both parties.
• The best known secret-key system is the Data Encryption
Standard (DES).
Sender Receiver
Plaintext ciphertext Decrypt Plaintext
Encrypt
Key Key
CS 623 18
Overview (cont.)
• Privacy is achieved because only those who know the
key can encrypt or decrypt messages.
• Authentication can be achieved if separate keys are
used for each pair of communicating parties.
• Integrity can be achieved if a message integrity code
(MIC) is added to the message.
– An MIC is a cryptographic checksum assigned to a file and
used to test the file later to verify that the data contained in
the file has not been maliciously changed.
• Non-repudiation is not achieved because either the
sender or the intended recipient could have created
the message.
• Example: Bob and Alice communicate using secret-
key cryptography.
– First, they must agree on a key, which only they will know
and which they will keep secret from all others.
– Now, they each can encrypt messages to the other using the
common key.
CS 623 19
Block Ciphers and Stream Ciphers
• Block cipher algorithm takes a fixed-length block of plaintext
(64 or 128 bits) and encrypts it with the key to produce a fixed-
length block of ciphertext .
– Disadvantage: One may notice that certain ciphertext blocks
are repeated, and will therefore know that the
corresponding plaintext blocks are also repeated.
– To combat this problem, an initialization vector (IV) is pre-
pended to the message and then encrypted. Then, the first
block of ciphertext is exclusive-ORed with the second block
of plaintext and then encrypted, and so on. The IV is
different for each message.
– This technique is called cipher block chaining (CBC).
• Stream cipher algorithm uses the key to produce a
pseudorandom key stream, which is exclusive-ORed with the
plaintext to produce the ciphertext.
– Disadvantage: Simple cipher algorithm produces the same
key stream with each new message.
– To prevent this problem, the IV and the key are used to
initialize the key stream generator so that it produces a
different sequence for each message.
CS 623 20
Secret-Key Cryptosystems
• Data Encryption Standard (DES):
– DES is a block cipher algorithm that uses a 56-bit key to
encrypt a 64-bit plaintext block into a 64-bit ciphertext block.
– The most common mode of operation of DES is CBC: Each
output block of ciphertext is exclusive-ORed with the next
plaintext block to form the next input to the DES algorithm.
– This process begins with a 64-bit IV.
– Disadvantage: Its 56-bit key length is too small to resist brute
force attacks by modern computers.
• Triple DES:
– Uses three 56-bit DES keys to encrypt each block.
– The data block is encrypted with the first key, then run in
decryption mode with the second key, and finally encrypted
again with the third key.
– If all the three keys are chosen to be the same then Triple DES
reduces to ordinary DES.
– In its three-key mode, Triple DES requires a 168-bit key.
CS 623 21
Secret-Key Cryptosystems (cont.)
• Blowfish:
– A block cipher algorithm using variable key lengths,
designed by Bruce Schneier.
– Freely available and very fast, running nearly 3 times faster
than DES.
– Widely used in file encryption applications for personal
computers.
– The key length is variable from 32 bits to 448 bits, making it
interesting for variable security applications.
• Advanced Encryption Standard (AES):
– AES is an effort of the National Institute of Standard and
Technology (NIST) to develop and standardize a replacement
for DES.
– AES uses Rijndael algorithm, which is an iterated block cipher
algorithm whose block length and key length can be
independently set to 128 bits, 192 bits, or 256 bits.
– AES is a good choice for new applications, because it is
standard, it is receiving careful study by cryptographers, and
it continues to resist attacks.
CS 623 22
Public-Key (Asymmetric)
Cryptography
CS 623 23
Overview
• In an asymmetric cryptosystem, the encryption key is different
from the decryption key.
• Each participant creates his own pair of keys:
– One is called the public key and is distributed freely.
– The other is called the private key and is kept secret.
– Either key may be used for encryption or for decryption, but
the private key should never be revealed to anyone.
• The best-known public-key cryptosystem is RSA, named after its
inventors: Rivest, Shamir, and Adleman.
Sender Receiver
Plaintext ciphertext Decrypt Plaintext
Encrypt
Encryption Key Decryption Key
CS 623 24
Overview (cont.)
• Bob and Alice communicates using public-key
cryptography.
• First, Bob and Alice each create a key pair (public key
and private key).
• Next, they publish their respective public keys in the
town directory.
• If Bob wants to send Alice a message, he encrypts the
message using Alice’s public key.
– The ciphertext can be read only by Alice, because only Alice
knows her own private key.
• Alice decrypts the message using her private key,
revealing the original message.
CS 623 25
Overview (cont.)
• Authentication problem: How can Alice tell if the
message is really from Bob?
• Answer: Bob applies his digital signature to the
message.
– Bob can do so by encrypting the message using his own
private key, creating a signed message.
– Of course, anyone can decrypt this signed message by using
Bob’s public key.
– The signed message is not secret, but only Bob could have
sent it, because only Bob knows his private key.
• Solution to the authentication problem:
– Bob first signs his message using his private key.
– He then encrypts this signed message using Alice’s public
key.
– Then only Alice can decrypt this message.
– Once she has, she can verify (by using Bob’s public key) that
Bob indeed sent the message.
CS 623 26
Overview (cont.)
• Another problem (security of the key directory):
– When Bob sends a message to Alice, he looks up Alice’s public key
in the directory.
– Suppose someone has substituted his own public key with Alice’s
public key in the directory.
– So Bob will unwittingly encrypt his message using not Alice’s public
key, but the public key of someone else.
• Solution: Public-key certificates.
– A public key certificate is a document containing a name and the
corresponding public key, signed by a trusted certificate authority.
– Suppose the town clerk is operating as a certificate authority.
– When Alice first creates her public key, she appears in person
before the clerk with a document attesting that the public key is
really hers.
– The clerk then signs the document with her private key. The
resulting signed document becomes a public-key certificate.
– Anyone can verify the clerk’s signature using the clerk’s public key.
– Once Alice has a certificate, she can place it in the directory.
– Bob then can be assured that the key he uses to send messages to
Alice is really Alice’s public key.
CS 623 27
Overview (cont.)
• Certificate authorities (CA) are often
organized in a hierarchy (similar to DNS).
• Higher-level certificate authorities sign
certificates for lower-level authorities.
• The certificate authority at the top of the
hierarchy is called the root, and its public key
is called the root key.
• A hierarchy of certificate authorities together
with the widespread use of public-key
certificates constitute a public-key
infrastructure (PKI).
CS 623 28
The RSA Algorithm
• The best known public-key cryptosystem is RSA, whose
algorithm is as follows:
1. Bob chooses two distinct large primes p and q and computes
n = pq.
2. Bob chooses the encryption key e such that the greatest
common divisor gcd(e, (p – 1)(q – 1)) = 1.
3. Bob then computes the decryption key d with
de = 1 (mod(p -1)(q – 1))
(read: de is congruent to 1 mod (p – 1)(q – 1)).
4. Bob makes n and e public, and keeps p, q, and d secret.
5. Alice writes her message as a number m. If m is greater than
n, she will break the message into blocks, each of which is less
than n.
6. For simplicity, let us assume for now that m < n. Alice will
encrypt message m as c = me (mod n) and sends the
ciphertext c to Bob.
7. Bob decrypts c by computing m = cd (mod n).
CS 623 29
The RSA Algorithm (cont.)
• Recall the definition of congruence:
Let a, b, n be integers with n being nonzero. We say that
a = b (mod n)
(read: a is congruent to b mod n)
if (a – b) is a multiple (positive or negative) of n, that is
a = b + kn
for some integer k (positive, negative or zero).
• Examples:
32 = 7 (mod 5), -12 = 37 (mod 7), 17 = 17 (mod 13)
• A text message can be written as a number using some
numbering scheme to number the letters. If we number
a = 01, b = 02, c = 03, …, z = 26
then the message cat can be written as the number
m = 30120.
• Proof of the algorithm (i.e., why m = cd (mod n)?) can be found in
any standard cryptography text book (such as “Introduction to
Cryptography” by Wade Trappe and Lawrence C. Washington,
ISBN 0-13-186239-1).
CS 623 30
Modes
• When the message to be encrypted is longer than the
block length of the cipher, it is necessary to execute
the algorithm several times and to combine the
results in some way.
• The method of combination is called the mode of
operation.
• We shall look at the Electronic Codebook (ECB) Mode
and the Cipher Block Chaining (CBC) Mode.
• There are also other modes such as Cipher Feedback
Mode, Output Feedback Mode etc., whose details can
be found in reference [1].
CS 623 31
Electronic Codebook (ECB) Mode
• The encryption Plaintext 1 Plaintext 2
algorithm is applied
independently to each
block of the message. Encrypt (key) Encrypt (key)
• Disadvantages:
– The same input block is
always encrypted as the
Ciphertext 1 Ciphertext 2
same ciphertext block.
– An attacker can
substitute blocks to alter
part of a message (e.g., Decrypt (key) Decrypt (key)
changing payment
amount by substituting
the block where the
amount appears). Plaintext 1 Plaintext 2
CS 623 32
Cipher Block Chaining (CBC) Mode
Plaintext 1 Plaintext 2
• Each plaintext block
IV
is exclusive-ORed + +
with the preceding Encrypt (key) Encrypt (key)
ciphertext block
before the plaintext
Ciphertext 1 Ciphertext 2
is encrypted.
• The process is
Decrypt (key) Decrypt (key)
bootstrapped using
an initialization IV
+ +
vector (IV).
Plaintext 1 Plaintext 2
CS 623 33
CBC Mode (cont.)
• In CBC mode, each block of plaintext is scrambled by XOR with a
block of ciphertext.
• Because these ciphertext blocks are different, if the same
plaintext block occurs in multiple places, it will be encrypted into
different ciphertext blocks.
• The IV provides this function for the first plaintext block.
• The IV must be random and different for each message, but it
doesn’t need to be secret.
– The IV is often transmitted in the clear as the first part of the
message.
• CBC mode also makes the overall message more resistant to
tampering.
– If an attacker switches blocks around, duplicates blocks, or
substitutes old blocks in new messages, the chaining that
occurs during decryption will result in the output plaintext
being gibberish.
CS 623 34
Protocols
• A protocol is a series of steps taken to
accomplish a task.
• This is similar to the definition of an
algorithm, but
– we use algorithm to refer to the attainment of
internal, mathematical results such as encrypting a
block
– we use protocol to refer to the attainment of user-
visible results such as secret communication and
digital signatures.
CS 623 35
Communications: Session Keys
• A session key is a cryptographic key adopted for
use for a particular message or during a particular
session of communications.
• Session keys are used for two reasons:
1. To achieve greater performance:
– Usually a communications system will use a relatively low-
performance public-key cryptosystem to communicate a
session key.
– The session key is then used in a high-performance secret-
key cryptosystem to encrypt the bulk volume of message
data.
2. To limit the amount of data encrypted with the
master key.
– Because only the session key is encrypted by the master
key, the attacker cannot exploit statistical properties of the
actual message to assist in the attack on the master key.
CS 623 36
Communications: Data Compression
• Data compression refers to the problem of encoding a
message in the minimum amount of space.
• In order to do this, data compression algorithms (e.g., ZIP
and COMPRESS) exploit statistical properties of the source
file to encode the same information with fewer bits.
• In general, it is not possible to compress an encrypted
message, because a good encryption algorithm should
destroy the statistical properties that a compression
algorithm can exploit.
• However, it is possible to encrypt a compressed message.
• Compressing a file before encrypting it may slightly improve
security, because compression algorithms reduce the
redundancy that may be exploited during cryptanalysis.
CS 623 37
Digital Signatures
• A digital signature is an information block
attached to a message that could have been
created only by a particular individual.
• One can use public-key cryptography to
produce a digital signature by creating a
message digest of the message and
encrypting the message digest with one’s
private key.
• Anyone can validate a signature using the
corresponding public key.
CS 623 38
Key Management
• Key management is the tempting target
for attackers (because modern
cryptographic algorithms, modes and
protocols are strong).
• Key management consists of
– Key generation
– Key storage
– Key distribution
– Key destruction
CS 623 39
Key Generation
• Generally, there are two methods for generating
keys (by computer software):
1. User Input:
– Key generators rely on input from users.
– The user is asked to type randomly for a while.
– The letters typed are ignored, but the random variations in
the inter-arrival time of keystrokes are used to generate
the key.
2. Pseudorandom:
– Unpredictable pieces of information such as the
computer’s real time clock, the number of hardware
interrupts received, etc. are combined into a randomness
pool.
– This pool can be used to generate keys that are sufficiently
random for most purposes.
CS 623 40
Key Storage
• During the lifetime of a key, it may be used and
stored in different places, such as the following:
• In memory:
– When a key is used by a computer, it must be in memory.
– Contents of memory may be available to other software
running on the same system.
– PC operating systems provide no protection.
– Multi-user operating systems prevent users from reading or
writing the memory allocated to others. However, a
privileged user has access to memory of other users.
– Hence, keys in memory are only as secure as access to the
machine and the password of the system administrator.
– Good practice: zeroing out all storage used for keys as soon
as they are no longer needed.
CS 623 41
Key Storage (cont.)
• On disk:
– Cryptographic keys are usually stored in disk files, because they are
too long and too random to be entered by hand.
– Disk files containing keys are frequently stored in encrypted form.
Hence, stealing the encrypted file may not benefit the attacker.
– However, the security of all the keys in the file is only as good as
that of the master key (needed to decrypt the file), which is usually a
human-sensible password.
• In protected hardware:
– Commercial systems often use protected hardware devices such as
cryptographic accelerators and smart cards to store keys and to
perform cryptographic operations.
– Since the key never leaves the device (which is designed to be
tamper-proof), the key is physically protected.
– However, it is still possible to rogue software to command the use
of the key to decrypt or encrypt messages.
CS 623 42
Key Distribution
• Sharing a key between two people:
– Meeting in person
– Sending the key by courier
– Using public-key cryptography
– Use a master key to encrypt session keys.
• Sharing keys between more than two people:
– Using a Key Distribution Center (KDC), which is a central,
trusted authority.
• KDC shares a separate master key with each member of
the network and provides a session key for any two
parties that want to communicate.
– Using public-key certificates (discussed in Slide 27):
• A certificate binds a public key to a name by having a
trusted third party (the certificate authority) sign the
certificate.
• These certificates can be freely published and exchanged
over open communication channels.
• Parties wanting to communicate use the public key from
the certificate to encrypt a session key.
CS 623 43
Key Destruction
• Keys should be destroyed when they are no
longer needed.
• Keys stored in memory: Zero out all storage
used for the keys.
• Keys stored on disk: Overwrite the disk
multiple times with 0s and 1s, alternating
patterns and using random patterns (since it
may be possible to analyze erased magnetic
media).
• Keys stored on backup tapes: Destroy the
tapes when they are no longer needed.
• Keys stored on paper: Burn or shred with a
confetti shredder (not a strip shredder).
CS 623 44
References
1. G. Winfield Treese and Lawrence C.
Stewart. Designing Systems for
Internet Commerce (2nd edition):
Chapters 13. Addison Wesley.
2. W. Trappe and Lawrence C.
Washington. Introduction to
Cryptography with Coding Theory (2nd
edition). Pearson Prentice Hall.
CS 623 45
