Cryptography

in E-Commerce

CSI 5389 1
 Outline
• Basic Concepts
• Secret-Key (Symmetric)
Cryptography
• Public-Key (Asymmetric)
Cryptography
• Modes
• Protocols
• Key Management

CSI 5389 2
Basic Concepts

CSI 5389 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.
CSI 5389 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).

CSI 5389 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.

CSI 5389 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).
CSI 5389 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).

CSI 5389 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)
CSI 5389 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

CSI 5389 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.

CSI 5389 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.

CSI 5389 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!

CSI 5389 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.

CSI 5389 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.
CSI 5389 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.

CSI 5389 16
Secret-Key (Symmetric)
Cryptography

CSI 5389 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 Plaintext

Encrypt Decrypt

Key Key

CSI 5389 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.
CSI 5389 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.
CSI 5389 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.
CSI 5389 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.
CSI 5389 22
Public-Key (Asymmetric)
Cryptography

CSI 5389 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 Plaintext

Encrypt Decrypt

Encryption Key Decryption Key

CSI 5389 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.

CSI 5389 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.
CSI 5389 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.
CSI 5389 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).
CSI 5389 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).

CSI 5389 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).
CSI 5389 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].

CSI 5389 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
same ciphertext block. Ciphertext 1 Ciphertext 2
– 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

CSI 5389 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
CSI 5389 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.

CSI 5389 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.

CSI 5389 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.

CSI 5389 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.

CSI 5389 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.

CSI 5389 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

CSI 5389 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.

CSI 5389 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.

CSI 5389 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.

CSI 5389 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.
CSI 5389 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).
CSI 5389 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.

CSI 5389 45