AUTHENTICATION &

BASIC CRYPTOGRAPHY

Lecture 2
1
Week 2
TOPICS
 What is authentication?
 Password
 Cryptography Concept
 Cryptography Algorithms
 Digital Signature
 Public Key Infrastructure (PKI)
 RSA
 Methods of Attacks in Encryption
Systems 2
WHAT IS AUTHENTICATION?
 Verification of identity of someone who
generated some data
 Relates to identity verification
 classifications of identity verification:
 by something known e.g. password
 by something possessed e.g. smart card,
passport
 by physical characteristics (biometrics)
e.g. finger prints, palm prints, retina,
voice
 by a result of involuntary action :
signature 3
AUTHENTICATION
 Requirements – must be able to verify
that:
 Message came from apparent
source or author
 Contents have not been altered
 Sometimes, it was sent at a
certain time or sequence
 Protection against active attack
(falsification of data and transactions)
4
PASSWORD
 Protection of passwords
 Don’t keep your password to anybody
 Don’t write or login your password at everywhere
 Etc.
 Choosing a good password
 Criteria:
 Hard to guess and easy to remember
 Characteristics of a good password
 Not shorter than six characters

 Not patterns from the keyboard

 Etc.

 Calculations on password
 Password population, N =rs 5
 Probability of guessing a password = 1/N
 Probability of success, P=nt/N
TIME TAKEN TO CRACK PASSWORD
No. Total by human by 1MIPS
Characters Combination Comp
1 36 3 minutes .000018s
2 1300 2 hours .00065s
3 47000 3 days .02s
4 1700000 3 months 1s
5 60000000 10 years 30s
10 37x1014 580 Million y 59years
6
 TECHNIQUES FOR GUESSING
PASSWORDS
 Try default passwords.
 Try all short words, 1 to 3 characters long.
 Try all the words in an electronic
dictionary(60,000).
 Collect information about the user’s
hobbies, family names, birthday, etc.
 Try user’s phone number, social security
number, street address, etc.
 Try all license plate numbers
 Use a Trojan horse
 Tap the line between a remote user and the 7
host system.
 PASSWORD SELECTING
STRATEGIES

 User education
 Computer-generated passwords
 Reactive password checking
 Proactive password checking

8
 EXAMPLE OF PASSWORD
 Based on the passwords given below,
determine which passwords are good or
bad, include one reason for each password:
 UTeM1
 hon05da
 MyviT05
 aleeyah
 king
 zamrud

9
 EXAMPLE OF PASSWORD
CALCULATION
 Assume you choose character from
a-z and 0-9 and the number of
characters required are 5.
 Determine how much time will be
needed to get the right password if
your capability of your computer is
400 MIPS.
 Give your opinion/conclusion from
this problem.
10
CRYPTOGRAPHY CONCEPT
 The idea of a cipher system is to disguise
information in such a way that its
meaning is unintelligible to an
unauthorized person.

 Thetwo most common uses are,

probably, to store data securely in a
computer file or to transmit it across an
insecure channel such as the internet.

 Encrypted document does not prevent

unauthorized people gaining access to it
but, rather, ensures that they cannot 11

understand what they see.

 SECRET WRITING

Steganography
(Hiding)

Secret
Writing Transposition
Codes
(Replace
Cryptography words)
(Scrambling)
Substitution
Cipher
(Replace
letters)
12
 SECRET WRITING
Hiding
Steganography messages
(Hiding)

Message not
changed

Does not
involve key
Secret
Writing
Scrambling
messages

Message
changed
Cryptography 13
(Scrambling) Does involve
key
 STEGANOGRAPHY
-THE ART OF HIDING

Common methods include shaving you head bold, write something on it

and wait for the hair to grow back.

Example of modern stegano methods is watermarking 14

THE EARLIEST INFORMATION
SECURITY TOOL

THE SCYTALE 15
MECHANICAL CRYPTO MACHINE
IN WORLD WAR II

• The Enigma machine.

• During its height, it was thought to be invincible.
• It was believed to be un-crackable.
16
PEOPLE BREAKING ENIGMA

During the Second World War, Alan

In December 1932, a 27-year-old Polish Turing was a main participant in the
mathematician, Marian Rejewski, who efforts at Bletchley Park to break
had joined the Polish Cipher Bureau in German ciphers. Building on
September that year, made one of the cryptanalysis work carried out in
most important breakthroughs in cryptologic Poland by Marian Rejewski, Jerzy
history by using algebraic mathematical Różycki and Henryk Zygalski from
techniques to solve the Enigma wiring. Cipher Bureau before the war, he
contributed several insights into
breaking both the Enigma machine
and the Lorenz SZ . 17
 CRYPTOGRAPHY TERMINOLOGY
 plaintext - original message
 ciphertext - coded message

 cipher - algorithm for transforming plaintext to

ciphertext
 key - info used in cipher known only to sender/receiver

 encipher (encrypt) - converting plaintext to

ciphertext
 decipher (decrypt) - recovering ciphertext from
plaintext
 cryptography - study of encryption principles/methods

 cryptanalysis (codebreaking) - study of principles/

methods of deciphering ciphertext without knowing key
 cryptology - field of both cryptography and
18

cryptanalysis
CRYPTOGRAPHY ALGORITHMS
 Classifiedalong three independent dimensions:
 The type of operations used for transforming
plaintext to ciphertext

 The number of keys used

 symmetric (single key, or private-key
encryption)
 asymmetric (two-keys, or public-key
encryption)

 The way in which the plaintext is processed 19

 CRYPTOGRAPHY ALGORITHMS
 Symmetric algorithms P=D(K,E(K,P))

 Asymmetric algorithms P=D(Kd, E(Ke, P))

20
SYMMETRIC VS. ASYMMETRIC
 Ifthe system is symmetric, then
there may be a need to distribute a
secret key value before secret
messages can be exchanged.
 One of the most difficult aspects of
obtaining a secure system.

 Ifthe system is asymmetric, then it

may be possible to avoid this particular
problem by distributing only the
encryption keys, which do not need to
be secret.
 However it is then replaced by the 21
problem of guaranteeing the authenticity
of each participant’s encryption key.
SYMMETRIC CRYPTOGRAPHY
PRINCIPLES

22
 SYMMETRIC CRYPTOGRAPHY
REQUIREMENTS
 two requirements for secure use of symmetric
encryption:
 a strong encryption algorithm
 a secret key known only to sender / receiver

 mathematically have:
C = EK(P)
P = DK(C)

 assume encryption algorithm is known

23
 implies a secure channel to distribute key
 PUBLIC-KEY CRYPTOGRAPHY
(ASYMMETRIC) PRINCIPLES
 The use of two keys has consequences in:
 key distribution, confidentiality and
authentication.

 The scheme has six ingredients

 Plaintext
 Encryption algorithm
 Public key
 Private key
 Ciphertext 24

 Decryption algorithm
ENCRYPTION USING ASYMMETRIC
CRYPTOGRAPHY

25
 METHODS USE IN CRYPTOGRAPHY
ALGORITHM
 Substitution
 monoalphabetic substitution
 Formed by shifting the letters of the original
alphabet
 polyalphabetic substitution
 Extension of monoalphabetic substitution
system
 Using Vigenere Tableau

 Transposition
 unkeyed transposition
 Rearrange letters by using matrix
 keyed transposition
 Rearrange letters by using matrix where the
26
size of matrix is determined by the length of
the key used.
 CAESAR CIPHERS
 One of the earliest substitution cipher
described by Julius Caesar in the Gallic
Wars.
 In this cipher each of the letters A to W is
encrypted by being represented by the
letter that occurs three places after it in
the alphabet.
 Although Caesar used a ‘shift’ of 3, a
similar effect could have been achieve
using any number from 1 to 25.
 In fact any shift is now commonly
regarded as defining a Caesar Cipher. 27
 CAESAR CIPHERS (CONT.)
 The encryption key and decryption key are both
determined by a shift but the encryption and
decryption rules are different.

 We could have changed the formulation slightly to

make the two rules coincide and have different
encryption and decryption keys.
 A shift of 26 has the same effect as a shift of 0
and, for any shift from 0 to 25, encryption with
that shift is the same as decryption with the
new shift obtained by subtracting the original
shift from 26.
 E.g: encryption with shift 8 is the same as
decryption with shift 26 - 8 =18. 28
 CAESAR CIPHERS (CONT.)
 This enable us to use the same rule for
encryption and decryption with the
decryption key 18 corresponding to the
encryption key 8.

 Caesarciphers are vulnerable to exhaustive

key search attack.
 To work through all the 26 keys.

 Furthermore the key can be determined

from knowledge of a single pair of
corresponding plaintext and ciphertext 29

characters.
 EXAMPLE:

Find The message behind this cipher text

YMJ KPJQ UWNHJ BNQQ

NSHWJFXJ YT WH KTZW
GD SJCY BJJP

30
 CAESAR CIPHER EXHAUSTIVE KEY
SEARCH: CRYPTOGRAM XMZVH
Enciphering Assumed Enciphering Assumed Enciphering Assumed
key message key message key message

0 XMZVH 17 GVIEQ 8 PERNZ

25 YNAWI 16 HWJFR 7 QFSOA
24 ZOBXJ 15 IXKGS 6 RGTPB
23 APCYK 14 JYLHT 5 SHUQC
22 BQDZL 13 KZMIU 4 TIVRD
21 CREAM 12 LANJV 3 UJWSE
20 DSFBN 11 MBOKW 2 VKXTF
19 ETGCO 10 NCPLX 1 WLYUG
18 FUHDP 9 ODQMY

31
CAESAR CIPHERS (CONT.)
 A single key search may not identify the key uniquely.
 It is much more likely merely to limit the number of
possibilities by eliminating some obviously wrong
ones.

 An exhaustive search for the encryption key for

cryptogram HSPPW yields two possibilities that lead
to complete English words for the assumed message.

 These shifts are 4, that gives DOLLS, and 11, that

gives WHEEL.

 When this happens we need more information,

possibly the context of the message, or some extra 32
ciphertext, before we can determine the key
uniquely.
 SIMPLE SUBSTITUTION CIPHERS
(RANDOM)
ABCD EFGH I J KLM
DI QMTB ZSYK VOF

NOPQ R S TUVW XYZ

ERJ A U WPXH L CNG

 For a Simple Substitution Ciphers (or

monoalphabetic ciphers), we write the alphabet in
a randomly chosen order underneath the alphabet
written in strict alphabetical order.

 The encryption and decryption keys are equal.

 The encryption rule is ‘replace each letter by the

one beneath it’ while the decryption rule is the
opposite procedure
33
 SIMPLE SUBSTITUTION CIPHERS
(CONT.)
 The number of keys for a Simple Substitution
Cipher is equal to the number of ways in
which the 26 letters of the alphabet can be
arranged.
 It is called 26 factorial and is denoted by 26!
It is 26 x 25 x 24 x … x 3 x 2 x 1 which
equals 403,291,461,126,605,635,584,000,000
keys.

 Although having a large number of keys is a

necessary requirement for cryptography
security, however having a large number of 34
keys is certainly no guarantee that the cipher
system is strong.
EXAMPLES - SIMPLE SUBSTITUTION
CIPHERS
 Inthe following examples we assume that
the cryptograms given have been
intercepted by someone who knows that
the message is in English and that a
Simple Substitution Cipher was used:
 Example 1: G WR W RWL
 Example 2: HKC
 Example 3: HATTPT
 Example 4: HATTPT (Given that the message
is the name of a country) 35
VIGENÈRE CIPHERS
 The
Vigenère Cipher (the best known of the
manual polyalphabetic cipher) uses a Vigenère
Square to perform encryption.

 The left-hand (key) column of this square

contains the English alphabet and for each
letter, the row determined by that letter
contains a rotation of the alphabet with that
letter as the leading character.
 So each letter in the left-hand column gives
a Caesar Cipher whose shift is determined
by that letter.
 Example: the letter g gives the Caesar 36
Cipher with shift 6.
VIGENERE TABLEAU

37
 EXAMPLE: POLYALPHABETIC
SUBSTITUTION CIPHER

Based on Vigenere, get the ciphertext for the

plaintext “A minutes success pays the failure
of years” in 4-letter words and “failure” as the
repeating key. Use ‘x’ to pad out the blanks.

38
 WHAT IS FREQUENCY ATTACK??

The first page of al-Kindi's

manuscript On Deciphering
Cryptographic Messages,
containing the oldest known
description of cryptanalysis by
frequency analysis.

•First successful formal attack on ciphers was established by

Al-Kindi (801-873).
•It was probably religiously motivated textual analysis of the Qur'an
which led to the invention of the frequency analysis technique for
breaking monoalphabetic substitution ciphers by al-Kindi sometime
around AD 800. 39
LET US LOOK AT THE FREQUENCY OF THE ENGLISH
ALPHABET

40
 BREAKING VIGENERE CIPHER

This cipher was secure from about 1553 till 1854 (301 years!!!)

a.In 1854 Charles Babbage developed a test that succeeded

to attack this cipher.

b. In 1863 Friedrich Kasiski was the first to publish a

successful attack on the Vigenère cipher.

c. The primary weakness of the Vigenère cipher is the

repeating nature of its key.
41
 TRANSPOSITION

 Letter is rearranged
 Letter are retain but moved from its
position
 Two type
 Unkeyed single transposition
 Keyed single transposition

42
 EXAMPLE: UNKEYED SINGLE
TRANSPOSITION
 Encrypt the plaintext : “there is no
security on this earth there is
only opportunity” into a matrix of
10 (vertical) by 5 (horizontal).

 Get the ciphertext horizontally, using 5-

letter words.

43
 EXAMPLE: KEYED SINGLE
TRANSPOSITION
 With the key “86423175”, encrypt the
plaintext “ignorance is the mother of
admiration” using keyed single
transposition into 4 by 8 matrix. Use
“x” to pad out columns.

44
 MODERN ALGORITHMS

 Most modern ciphers use a sequence

of binary digits (bits), that is, zeros
and ones such as ASCII.

 This bit sequence representing the

plaintext is then encrypted to give
the ciphertext as a bit sequence.

45
MODERN ALGORITHMS (CONT.)
 The encryption algorithm may act on a bit-
string in a number of ways.
 stream ciphers where the sequence is
encrypted bit-by-bit.
 block ciphers, where the sequence is
divided into blocks of a predetermined
size.
 ASCII requires 8 bits to represent one
character, and so for a block cipher that
has 64-bit blocks, the encryption 46
algorithm acts on eight characters at
once.
 MODERN ALGORITHMS (CONT.)
 Since most modern
algorithms operate on
binary strings we need
to be familiar with a 0 1
method of combining 0 0 1
two bits called 1 1 0
Exclusive OR and
often written as XOR
or .

 0  0 = 0, 0  1 =1,
1  0 = 1 and 1  1 = 0 47
CLASSIFICATION OF CIPHERS
(TRANSFORMATION)

 Stream ciphers
 they convert one symbol of plaintext
immediately into a symbol of ciphertext
 depends on symbol, key and control
information of encipherment algorithm
 Block ciphers
 encrypt a group of plaintext symbols as one
block
 examples are transposition ciphers
 e.g, in columnar transposition, the entire message is
translated as one block, block size need not have any
particular relationship to the size of the character

48
STREAM CIPHERS
 The plaintext is enciphered bit by bit.
 The value of each bit is changed to the
alternative value or leave unchanged.
 If a bit is changed twice, it returns to its
original value.

 If an attacker knows that a stream cipher has been

used, then their task is to try to identify the
position of those bits which have been changed and
to change them back to their original values.
 If there is any easily detectable pattern that
identifies the changed bits then the attacker
task may be simple.
 The position of the changed bits must be
unpredictable to the attacker but the genuine
receiver needs to be able to identify them
easily. 49
STREAM CIPHERS (CONT.)

 The encryption key is often called a keystream

sequence.
 0 to mean ‘leave unchanged’, 1 to mean
‘change’.
 Plaintext, ciphertext and keystream are all
binary sequences.
 Suppose that we have the plaintext 1100101 and
the keystream is 1000110.
 By applying the rule gives 0100011 as the
ciphertext.
 Changing a bit twice has the effect of returning it
to its original value.
 This means that decryption process is identical
to the encryption process, so the keystream 50
also determines decryption.
STREAM CIPHERS (CONT.)

 If Pi, Ki and Ci are respectively the plaintext,

keystream and ciphertext bits in position i,
then the ciphertext bit Ci is given by Ci = Pi 
K i.
 The decryption is defined by Pi = Ci 
Ki.
 A stream cipher takes a short key to generate a
long keystream.
 Thisis achieved by using binary
sequence generator.

51
STREAM CIPHERS (CONT.)
 The keystream bit in position i, Ki = Pi  Ci
can be determined as the XOR of the
plaintext and ciphertext in position i.
 This highlight the potential weakness for
stream ciphers.
 Anyone who is able to launch a known
plaintext attack, can deduce parts of the
keystream sequence from the
corresponding plaintext and ciphertext bit
pairs.
 Thus the keystream must be
unpredictable in the sense that
knowledge of some of it should not enable 52
an attacker to deduce the rest.
STREAM CIPHERS (CONT.)

 Ifthe keystream generator produces the

same bit stream every time it is turned on,
the resulting cryptosystem will be trivial to
break.
 Anyone who has two different ciphertexts
encrypted with the same keystream, can XOR
them together and get two plaintext
messages XORed with each other.
 When the interceptor gets a single
plaintext/ciphertext pair, they can read
everything.
 That is why all stream ciphers have keys -
the output of the keystream generator is a 53
function of the key.
 BLOCK CIPHERS
 Fora block cipher, the bit-string is divided into
blocks of a given size and the encryption algorithm
acts on that block to produce a cryptogram block
that, for most symmetric ciphers, has the same size.

 Block ciphers have many applications.

 Can be used to provide confidentiality, integrity,
or user authentication and can even be used to
provide the keystream generator for stream
ciphers.

A symmetric algorithm is said to be well designed if

an exhaustive key search is the simplest form of 54
attack.
BLOCK CIPHERS (CONT.)
 There are a few obvious properties that a strong block
cipher should possess.
 Diffusion properties - which a small change in the
plaintext, may be one or two positions, should
produce an unpredictable change in the ciphertext.

 Confusion properties - if an attacker is conducting

an exhaustive key search then there should be no
indication that they are near to the correct key.

 To prevent divide-and-conquer attacks we require

completeness - each bit of a ciphertext must depend
on every bit of the key.

 Statistical testing forms a fundamental component 55 of

the assessment of block ciphers for these three listed
properties and others.
 MESSAGE AUTHENTICATION
CODES (MAC)
A MAC is a key-dependent one-way hash
function.

 Only someone with the identical key can

verify the hash.
 They are very useful to provide
authenticity without secrecy.

 MACs can be used to authenticate files

between users.
 To determine if his files have been
56

altered.
HASH FUNCTION

57
 DIGITAL SIGNATURES
 The digital signature for a message from a
particular sender is a cryptographic value
that depends on the message and the sender.
 In contrast , a hand-written signature
depends only on the sender and is the
same for all messages.

A digital signature provides data integrity

and proof of origin (non-repudiation).
 It can be kept by the receiver to settle
disputes if the sender were to deny the 58

content of the message or even to deny

having sent it.
59
DIGITAL SIGNATURES (CONT.)

 Itis the provision of a means of settling

disputes between sender and receiver that
distinguishes the digital signature
mechanism from the MACing process.

 Such dispute can only be settled if there is

asymmetric between sender and receiver.

60
 DIGITAL SIGNATURES (BASIC
PRINCIPLE)
 For a digital signature scheme based on RSA or El
Gamal:
 Each user has a private key that only they can
use and its use is accepted as identifying them.
 There is a corresponding public key.
 Anyone who knows this public key, can check
that the corresponding private key has been
used, but cannot determine the private key.
 This gives the receiver assurance of both the
origin and content of the message.
61
 GENERATING A DIGITAL
SIGNATURE
 Asymmetric
cryptographic processing requires
much computational processing.

 Thus a condensed version or hash of the

message is produced by applying a hash
function to the message.

 Thesignature is produced from the hash

(which represent the message) by using the
asymmetric algorithm with the private key.

 Thusonly the owner of the private key can

generate the signature.
62
 DIGITAL SIGNATURE
M M M
E E E Hf
S S S
S S S
A A A
G G G
E E E Compare

Hf

E D

Private key Public key 63

HOW TO CREATE A DIGITAL
SIGNATURE USING RSA
MESSAGE

HASHING
FUNCTION

HASH OF MESSAGE

Sign using Private Key

SIGNATURE - 64
SIGNED HASH OF MESSAGE
VERIFYING A DIGITAL SIGNATURE
 The signature can be verified by anyone
who knows the corresponding public key.

 To do this a value is produced from the

signature using the asymmetric algorithm
with the public key.

 Thisvalue should be the hash of the

message, which anyone can calculate.

 Ifthis value and the hash agree, the

signature is accepted as genuine.
65
 HOW TO VERIFY A DIGITAL
SIGNATURE USING RSA
Message
Signature
Verify the Re-hash the
Received Signature Received Message

Signature Message

Hashing
Verify using Function
Public key

Hash of Message
Hash of Message
66
If hashes are equal, signature is
authentic
 CERTIFICATION AUTHORITY (CA)
 AIM:
 To guarantee the authenticity of public keys.

 METHOD:
 The CA guarantees the authenticity by
signing a certificate containing user’s identity
and public key with its secret key.

 REQUIREMENT:
 All users must have an authentic copy of the
Certification Authority’s public key.
67
 CERTIFICATION PROCESS

Centre
Verifies Creates
credentials Certificate

Distribution

Owner

Presents Public Receives

Generates
Key and (and checks)
Key Set
credentials certificate
68
 HOW DOES IT WORK?

 Thecertificate can accompany all

sender’s messages.

 The recipient must directly or indirectly:

 Trust the CA
 Validate the certificate

69
CERTIFICATION AUTHORITIES

 Problems / Questions
 Who generates users’ key?
 How is identity established?
 How can certificates be cancelled?
 Any others?

70
ATTACKS ON DIGITAL SIGNATURE
 Suppose digital signatures are being used
as a means of identification.

 Ifuser A wishes to impersonate user B,

then there are two different forms of attack:
 A attempts to obtain the use of B’s private key
 A tries to substitute their public key for B’s
public key.

71
PUBLIC KEY INFRASTRUCTURE (PKI)
 Themotivation of using PKI is to facilitate the
use of public key cryptography.

 Three key players in PKI system:

 The certificate owner - who applies for the certificate.
 CA - which issues the certificate that binds the owner’s
identity to the owner’s public key value.
 The relying party - who uses on the certificate.

 Other players:
 Registration Authority (RA) - in some systems the
identification verification is performed by a separate
authority.
 Validation Authority (VA) - end users ask the VA if a
given certificate is still valid and receive a yes or no 72
answer.
 ESTABLISHING A PKI
 When a PKI is established, the following
processes need to take place:
 The key pairs for CAs must be generated.
 The key pairs for users must be
generated.
 Users must request certificates
 Users’ identities must be verified.
 Users’ key pairs must be verified.
 Certificates must be produced.
 Certificates must be checked.
 Certificates must be removed/updated
(when necessary).
 Certificates must be revoked (when 73
necessary).
 KEY MANAGEMENT
A typical requirement specification for a
symmetric key system might include each of
the following:
 Keys must be generated using a random or
pseudorandom process.
 Any key used by a communicating pair must be
unique to them.
 A key must be used for only for a purpose, e.g.
the same key should not be used for both
encryption and authentication.
 Each key must be replaced within the time
deemed necessary to determine it by an
exhaustive search. 74
 KEY MANAGEMENT (CONT.)
 A key must not be used if its compromise is either
known or suspected.

 Compromise of a key which is shared between

two parties must not compromise any key used
by a third party.

 Keys should only appear in clear form within a

highly tamper resistant device. Elsewhere all
keys must be encrypted or in component form.

 Keys must be protected against misuse.

 Unauthorized modification, substitution or replay75

of any key must be prevented or detected.
 THE KEY LIFE CYCLE
Generation

Distribution
Destruction

Change Storage

76
Usage
 RSA
 by Rivest, Shamir & Adleman of MIT in 1977
 best known & widely used public-key scheme

 Ingredients of RSA:

p, q, two primes number (private, chosen)

n = p*q (public, calculated)

e, with gcd (Ø(n),e) =1; (public, chosen)

1<e<Ø(n)

d = e-1 (mod Ø(n)) (private, calculated)

77
 RSA KEY SETUP
 each user generates a public/private key pair by:
 selecting two large primes at random - p, q

 computing their system modulus n=p*q

 note ø(n)=(p-1)(q-1)
 selecting at random the encryption key e

where 1<e<ø(n), gcd(e,ø(n))=1

 solve following equation to find decryption key d

 e*d=1 mod ø(n) and 0≤d≤n

 publish their public encryption key: PU={e,n}

 keep secret private decryption key: PR={d,n} 78

 RSA USE
 to encrypt a message M the sender:
 obtains public key of recipient
PU={e,n}
 computes: C = Me mod n, where 0≤M<n

 to decrypt the ciphertext C the owner:

 uses their private key PR={d,n}
 computes: M = Cd mod n

 note
that the message M must be
smaller than the modulus n (block if
needed) 79
RSA EXAMPLE - KEY SETUP
1. Select primes: p=17 & q=11
2. Compute n = pq =17 x 11=187
3. Compute ø(n)=(p–1)(q-1)=16 x
10=160
4. Select e: gcd(e,160)=1; choose
e=7
5. Determine d: de=1 mod 160 and d
< 160 Value is d=23
6. Publish public key PU={7,187}
7. Keep secret private key 80
PR={23,187}
RSA EXAMPLE - EN/DECRYPTION
sample RSA encryption/decryption is:
 given message M = 88 (number
88<187)

 encryption:
C = Me mod n
C = 887 mod 187 = 11

 decryption:
M = Cd mod n
M = 1123 mod 187 = 88 81
 EXPONENTIATION
 can use the Square and Multiply Algorithm
 a fast, efficient algorithm for exponentiation
 concept is based on repeatedly squaring base
 and multiplying in the ones that are needed
to compute the result
 look at binary representation of exponent
 only takes O(log2 n) multiples for number n
 eg. 75 = 74.71 = 3.7 = 10 mod 11
 eg. 3129 = 3128.31 = 5.3 = 4 mod 11

82
EXPONENTIATION (ALGORITHM FOR
COMPUTING AB MOD N)
c = 0; f = 1
for i = k downto 0
do c = 2 x c
f = (f x f) mod n
if bi == 1 then
c=c+1
f = (f x a) mod n
return f

83
 EFFICIENT ENCRYPTION
 encryption uses exponentiation to power e

 hence if e small, this will be faster

 often choose e=65537 (216-1)
 also see choices of e=3 or e=17

 but if e too small (eg e=3) can attack

 using Chinese remainder theorem & 3 messages
with different moduli

 if e fixed must ensure gcd(e,ø(n))=1 84

 i.e. reject any p or q not relatively prime to e
 EFFICIENT DECRYPTION
 decryption uses exponentiation to power d
 this is likely large, insecure if not

 can use the Chinese Remainder Theorem

(CRT) to compute mod p & q separately.
then combine to get desired answer
 approx 4 times faster than doing directly

 onlyowner of private key who knows values

of p & q can use this technique
85
 RSA KEY GENERATION
 users of RSA must:
 determine two primes at random - p, q
 select either e or d and compute the other

 primes
p,q must not be easily derived from
modulus n=p*q
 means must be sufficiently large
 typically guess and use probabilistic test

 exponentse, d are inverses, so use Inverse

algorithm to compute the other
86
 RSA SECURITY
 possible approaches to attacking RSA are:
 brute force key search (infeasible given size
of numbers)
 mathematical attacks (based on difficulty
of computing ø(n), by factoring modulus n)
 timing attacks (on running of decryption)
 chosen ciphertext attacks (given properties
of RSA)

87
 OTHER STANDARD ENCRYPTION
ALGORITHM
 DES
 The Data Encryption Standard (DES) is a block cipher (a
form of shared secret encryption) that was selected by the
National Bureau of Standards as an official Federal Information
Processing Standard (FIPS) for the United States in 1976
 based on a symmetric-key algorithm that uses a 56-bit key.
 16 complex block of substitution and transposition process
 Breakable as shown by distributed.net and the Electronic
Frontier Foundation back in 1999

 TRIPLE DES
 applies the Data Encryption Standard (DES) cipher algorithm
three times to each data block.
 Triple DES provides a relatively simple method of increasing the88
key size of DES to protect against brute force attacks
OTHER STANDARD ENCRYPTION
ALGORITHM
 AES
 In cryptography, the Advanced Encryption
Standard (AES) is an encryption standard
adopted by the U.S. government.
 The standard comprises three block ciphers,
AES-128, AES-192 and AES-256, adopted from
a larger collection originally published as
Rijndael.
 Each AES cipher has a 128-bit block size, with
key sizes of 128, 192 and 256 bits, respectively.
89
 METHODS OF ATTACK
 Four general attacks can be perform against
encrypted information:
 Ciphertext
- only attack guessing the plaintext or using
frequency analysis

 Known Plaintext
-guess using known plaintext.

 Chosen-plaintext
 Chosen-ciphertext attack 90
 METHODS OF ATTACK (CONT.)
 Thereare also specific attacks that can be
launched against encryption systems.
 Brute-Force attack
 Exhaustive key search - trying every
possible combination.
 Replay attacks
 Taking encrypted information and playing
it back at a later point in time.
 Man-in-the-middle attacks
 Fault in Cryptosytem
91
 SUMMARY
 have considered:
 Authentication concepts and techniques
 Cryptography concept and techniques
 principles of private and public-key
cryptography
 RSA algorithm, implementation, security
 Methods of attack in Digital Signature,
Encryption and RSA

92
 LESSON REVIEW
 Decipherthe following cryptogram. It was
obtained from English text by using a
simple substitution cipher. What is the
enciphering key?

FQJCB RWJWJ VNJAX BNKHJ WHXCQ

NAWJV NFXDU MBVNU UJBBF NNC

93