Chap 2: Elementary
Cryptography
Concepts of encryption
Cryptanalysis: how encryption systems are
“broken”
Symmetric (secret key) encryption and the DES
and AES algorithms
Asymmetric (public key) encryption and the
RSA algorithm
Key exchange protocols and certificates
Digital signatures
Cryptographic hash functions
SE571 Security in Computing Dr. Ogara
2
Cryptography - practice and study of
hiding information/using encryption to
conceal text
Cryptoanalysis - to find some weakness
or insecurity in a cryptographic scheme
Cryptology - research into and study of
encryption and decryption; it includes
both cryptography and cryptanalysis
SE571 Security in Computing Dr. Ogara
3
Decryption – the method of turning cipher
text back into plaintext
Encryption algorithm – set of rules or
procedures that dictates how to encrypt and
decrypt data, also called an encryption
cipher
Encryption – method of transforming data
(plaintext) into an unreadable format
Plaintext – the format(usually readable) of
data before encrypted
SE571 Security in Computing Dr. Ogara
4
Ciphertext – the scrambled format of
data after being encrypted
Key – a value used in the encryption
process to encrypt and decrypt/ also
called cryptovariable
SE571 Security in Computing Dr. Ogara
5
SE571 Security in Computing Dr. Ogara
6
Uses one key for both encryption and
decryption
Receiver and sender share same key
(private key) to lock and unlock
Also called private key encryption
Must securely distribute keys to other
parties
SE571 Security in Computing Dr. Ogara
7
Anyone with key can either encrypt or
decrypt (similar to password)
Very fast to encrypt or decrypt
Provides authentication as long as key
remains secret
Problem
• How do A and B obtain their shared secret key?
• Key distribution is e.g. n users communicating in
pairs need n*(n-1)/2 keys
SE571 Security in Computing Dr. Ogara
8
Receiver and sender have two keys –
public and private
Public key can be sent in an e-mail
message or posted in a public directory
Public key used to encrypt and private
key to decrypt or vise-versa
Requires a lot of resources
SE571 Security in Computing Dr. Ogara
9
Secret Key Public Key
(Symmetric) (Asymmetric)
No. of keys 1 2
Protection of Must be kept secret One key must be kept
keys secret; the other can be
freely exposed
Best uses Cryptographic workhorse; secrecy Key exchange,
and integrity of data—single authentication
characters to blocks of data,
messages, files
Key Must be out-of-band Public key can be used
distribution to distribute other keys
Speed Fast Slow
SE571 Security in Computing Dr. Ogara
10
SE571 Security in Computing Dr. Ogara
11
break a single message
recognize patterns in encrypted messages,
to be able to break subsequent ones by
applying a straightforward decryption
algorithm
infer some meaning without even breaking
the encryption, such as noticing an unusual
frequency of communication or determining
something by whether the communication
was short or long
SE571 Security in Computing Dr. Ogara
12
deduce the key, to break subsequent
messages easily
find weaknesses in the implementation
or environment of use of encryption
find general weaknesses in an
encryption algorithm, without
necessarily having intercepted any
messages
SE571 Security in Computing Dr. Ogara
13
Confusion (substitution)
• One letter is exchanged for another
• Basis of many cryptographic algorithms used for
diplomatic communication through the first half
of the twentieth century
• Basis for some widely used commercial-grade
encryption algorithms
• Examples:
Ceasar cipher
One-Time Pad
The Vernam cipher
SE571 Security in Computing Dr. Ogara
14
Diffusion (Transposition)
• Order of the letters is rearranged
• Basis for some widely used commercial-grade
encryption algorithms
• Goal - widely spread the information from the
message or the key across the ciphertext
(diffusion)
• Also known as permutation (rearrangement of
symbols of a message)
SE571 Security in Computing Dr. Ogara
15
Romans used a shift cipher called Ceasar
cipher
Shift ciphers simply shift characters in an
alphabet
Advantages
• Easy to memorize and implement
Disadvantage
• Pattern is obvious
SE571 Security in Computing Dr. Ogara
16
Large, non-repeating set of keys is
written on sheets of paper, glued
together into a pad
Requires a prearranged chart called
Vigenere table (contains 26 letters in
each column in some scrambled order)
Receiver needs a pad similar to the
sender
SE571 Security in Computing Dr. Ogara
17
Example:
• Message has 300 characters in length
• Keys are 20 characters long
• Sender needs 15 pages of keys
• Sender writes keys one at a time above the
letters of plain text
• Sender encipher plain text with Vigenere chart
• Receiver uses appropriate number of keys to
decipher message
SE571 Security in Computing Dr. Ogara
18
Problems
• Requires absolute synchronization between
sender and receiver
• Difficult to store and account for the keys
SE571 Security in Computing Dr. Ogara
19
Developed by Gilbert Vernam for AT&T
Is immune to most cryptanalytic attacks
Uses long non-repeating sequence of
numbers that are combined with the
plaintext
Used long punched paper tape that fed into
a teletype machine
Tape contained random numbers that were
combined with characters typed into the
teletype
sequence of random numbers had no
repeats, and each tape was used only once
SE571 Security in Computing Dr. Ogara
20
SE571 Security in Computing Dr. Ogara
21
Plain
text - VERNAM CIPHER
Ciphertext - tahrsp itxmab
SE571 Security in Computing Dr. Ogara
22
Plaintext characters are rearranged into
columns
Example:
• Plain text - THIS IS A MESSAGE TO SHOW HOW
A COLUMNAR TRANSPOSITION WORKS
• Ciphertext - tssoh oaniw haaso lrsto imghw
utpir seeoa mrook istwc nasns
SE571 Security in Computing Dr. Ogara
23
SE571 Security in Computing Dr. Ogara
24
The amount of secrecy needed should
determine the amount of labor
appropriate for the encryption and
decryption
The set of keys and the enciphering
algorithm should be free from
complexity
SE571 Security in Computing Dr. Ogara
25
The implementation of the process
should be as simple as possible
Errors in ciphering should not propagate
and cause corruption of further
information in the message
The size of the enciphered text should be
no larger than the text of the original
message
SE571 Security in Computing Dr. Ogara
26
It is based on sound mathematics
It has been analyzed by competent
experts and found to be sound
It has stood the test of time
SE571 Security in Computing Dr. Ogara
27
Stream ciphers - encrypt one bit or
character or symbol of plaintext into bit
or symbol of Ciphertext at a time e.g.
diffusion
Block ciphers encrypt a group of
plaintext symbols as one block e.g.
columnar transposition
Block ciphers can effectively act as a
stream cipher
SE571 Security in Computing Dr. Ogara
28
SE571 Security in Computing Dr. Ogara
29
Speed of transformation - the time to
encrypt a symbol depends only on the
encryption algorithm itself, not on the
time it takes to receive more plaintext
Low error propagation - error in the
encryption process affects only a
character
SE571 Security in Computing Dr. Ogara
30
Low diffusion - Each symbol is separately
enciphered. Therefore, all the information of
that symbol is contained in one symbol of
the ciphertext.
Susceptibility to malicious insertions and
modifications - Because each symbol is
separately enciphered, an active interceptor
who has broken the code can splice
together pieces of previous messages and
transmit a spurious new message that may
look authentic.
SE571 Security in Computing Dr. Ogara
31
High diffusion - Information from the
plaintext is diffused into several ciphertext
symbols. One ciphertext block may depend
on several plaintext letters
Immunity to insertion of symbols - Because
blocks of symbols are enciphered, it is
impossible to insert a single symbol into
one block. The length of the block would
then be incorrect, and the decipherment
would quickly reveal the insertion
SE571 Security in Computing Dr. Ogara
32
Slowness of encryption - The person or
machine using a block cipher must wait
until an entire block of plaintext symbols
has been received before starting the
encryption process
Error propagation - An error will affect
the transformation of all other characters
in the same block
SE571 Security in Computing Dr. Ogara
33
DES – Data Encryption Standards
AES – Advanced Encryption Standards
RSA – Rives-Shamir-Adelman Encryption
SE571 Security in Computing Dr. Ogara
34
Developed by U.S government for
general public (adopted in 1976)
Based on data encryption algorithm
developed by IBM
Combines two fundamental building
blocks of encryption – substitution and
transposition
Uses only standard arithmetic and logical
operations on numbers up to 64 bits long
SE571 Security in Computing Dr. Ogara
35
Lack of trust with DES 56-bit key length
Development of double encryption for
greater secrecy
Two keys perform two encryptions thus
making it hard to unlock [C=E(k2,
E(k1,m))]
Unfortunately the assumption is false
Three keys adds significant strength [C =
E(k3, E(k2, E(k1,m)))]
SE571 Security in Computing Dr. Ogara
36
1997 researchers using over 3,500
machines in parallel were able to infer a
DES key in four months’ work
1998 for approximately $100,000,
researchers built a special “DES cracker”
machine that could find a DES key in
approximately four days
Hence need for better and stronger
algorithm
SE571 Security in Computing Dr. Ogara
37
Algorithm is called Rijndael – named
after the two creators (Vincent Rijmen
and Joan Daemen)
Adopted in 2001
Uses substitution; transposition; and the
shift, exclusive OR, and addition
operations
Keys based on 128, 192 and 256 bits
SE571 Security in Computing Dr. Ogara
38
Does it have flaws?
How long will it remain sound?
Cryptanalysts have not found any flaws
yet
SE571 Security in Computing Dr. Ogara
39
Public key system introduced in 1978
Named after three inventors
Uses two keys for encryption and
dceryption
SE571 Security in Computing Dr. Ogara
40
Hash functions
Key exchange
Digital signatures
Certificates
SE571 Security in Computing Dr. Ogara
41
Important for integrity
Put a shield or seal around a file by
computing a cryptographic function
called hash or checksum or message
digest of a file
Examples:
• MD4, MD5 (Message Digest) – produce 128 bit
• SHA/SHS (Secure Algorithm or Standards) –
produce 160-bit digest
SE571 Security in Computing Dr. Ogara
42
Example: Web browser connecting to
shopping website
Encrypted session must be established
S = sender of protected information
R = receiver of protected information
Establish assurance that information
came from S
Public key cryptography can help here
SE571 Security in Computing Dr. Ogara
43
Use lockboxes and keys
S puts protected information into lockbox
that can be opened by S public key
S puts lockbox into another one that can
be opened by ONLY by R’s private key
R uses private key to open outer box and
S public key to open inner box (proof it
came from S)
SE571 Security in Computing Dr. Ogara
44
Does not require preshared public keys
S and R uses simple arithmetic to exchange
a secret
They agree on field number n and starting
number g
Each thinks of a secret number, say, s and r.
S sends to R gs and R sends to S gr.
Then S computes (gr)s and R computes (gs)r,
which are the same, so grs = gsr becomes
their shared secret.
SE571 Security in Computing Dr. Ogara
45
Provide reliable means to ensure the
origin of data
Cryptographic hash codes are used to
support digital signatures
Cryptographic hash codes offer a fast,
fairly reliable way of determining
whether a piece of data has been
modified between sender and receiver
SE571 Security in Computing Dr. Ogara
46
It must be unforgeable
It must be authentic
It is not alterable
It is not reusable
SE571 Security in Computing Dr. Ogara
47
Ideally suited to digital signatures
If S wishes to send M to R, S uses the
authenticity transformation to produce
D(M, KS). S then sends D(M, KS) to R. R
decodes the message with the public key
transformation of S
SE571 Security in Computing Dr. Ogara
48
Binds a public key and users’ identity
Signed by Certificate of Authority (CA)
Example – Two people
Edward posts his public key in public but
retains private key
Diana creates public key and includes it into
message with her identity
Edward signs (affirms Diana’s public key
and identity) by creating has value and then
encrypting message and hash value with
private key
SE571 Security in Computing Dr. Ogara
49
