• DEPARTMENT OF CSE

COURSE TITLE:
INTRODUCTION TO BLOCKCHAIN & CRYPTO CURRENCIES

COURSE CODE:
23CS3045RB
 AIM OF THE
SESSION
To familiarize students with the basic concepts of Cryptography

INSTRUCTIONAL
OBJECTIVES
This Session is designed to:
Demonstrate Principles of various Cryptographic Technique

LEARNING OUTCOMES

At the end of this session, you should be able to:

1. Define Cryptography
2. Public Key Cryptography
3. RSA Cryptography
4. Digital Signature
 Index
 Public Key Cryptography
 Applications of Public Key Cryptography
 RSA algorithm
 RSA’s Security
 Working examples
 Digital Signature
 Use of RSA and Attacks on RSA
 Hybrid – real-time
 PUBLIC KEY CRYPTOGRAPHY
Clear-text Input Cipher-text Clear-text Output
“The quick brown “Py75c%bn&*)9| “The quick brown fox
fox jumps over the fDe^bDFaq#xzjFr@g5=&n jumps over the lazy
lazy dog” mdFg$5knvMd’rkvegMs” dog”

Decryption
Encryption

Different keys private

public

Recipient’s public key Recipient’s private key

 PUBLIC KEY CRYPTOGRAPHY

• The concept is proposed in Diffie and Hellman (1976) “New

Directions in Cryptography”
• public-key encryption schemes
• public key distribution systems
• Diffie-Hellman key agreement protocol
• digital signature

• Most significant paradigm shift in a few thousand years.

5
PUBLIC KEY CRYPTOGRAPHY EARLY
HISTORY
• Features
• Each user has two keys (a public key and a private key)
• The algorithm is public knowledge.
• Knowledge of the algorithm does not help an attacker.
• Public-key encryption was proposed in 1970 by James Ellis
• in a classified paper made public in 1997 by the British
Governmental Communications Headquarters
• Concept of digital signature is still originally due to Diffie &
Hellman.
 DIFFIE-HELLMAN PROTOCOL
• Alice and Bob never met and share no secrets
• Public info: p and g
• p is a large prime number, g is a generator of Zp*
• Zp*={1, 2 … p-1}; aZp* i such that a=gi mod p

Pick secret, random Pick secret, random Y

X
gx mod p
gy mod p
Compute k=(gy)x=gxy mod p Alice Bob Compute k=(gx)y=gxy mod p
 WHY IS DIFFIE-HELLMAN SECURE?
• Discrete Logarithm (DL) problem:
given gx mod p, it’s hard to extract x
• There is no known efficient algorithm for doing this
• This is not enough for Diffie-Hellman to be secure!

• Computational Diffie-Hellman (CDH) problem:

given gx and gy, it’s hard to compute gxy mod p
• … unless you know x or y, in which case it’s easy

• Decisional Diffie-Hellman (DDH) problem:

given gx and gy, it’s hard to tell the difference between gxy mod p and gr mod p where r is
random
 PROPERTIES OF DIFFIE-HELLMAN
• Assuming DDH problem is hard, Diffie-Hellman protocol is
a secure key establishment protocol against passive
attackers
• Eavesdropper can’t tell the difference between the
established key and a random value
• Can use the new key for symmetric cryptography
• Basic Diffie-Hellman protocol does not provide
authentication
• IPsec combines Diffie-Hellman with signatures, anti-
 REQUIREMENTS FOR PKC
1.Anyone can quickly encrypt messages for A using his public key.
2.Only A can quickly decrypt messages.
3.It must be hard for anyone else to decrypt messages intended for A in a
reasonable amount of time.

• guarantees security.
• Also implies the need for computationally hard problems.
 NUMBER THEORY STUFF
• Prime Numbers
• Integers that have no positive factors except themselves and 1.
• Composite Numbers
• Integers that have at least one non-trivial factor except themselves and 1.
• Co-prime or Relatively Prime
• Two integers a and b are co-prime iff GCD(a, b)=1.

• GCD(a, b) = Largest integer that completely divides both a and b.

• Euclid’s algorithm can be used to compute GCD.

11
 MORE NUMBER THEORY
• Euler’s Totient function
• ɸ(n) = Count of numbers < n that are co-prime to n

• If n is prime
• ɸ(n) = n-1

• If n is composite (e.g. n=p . q)

• ɸ(n) = ɸ(p . q) = ɸ(p).ɸ(q) = (p-1).(q-1)
• p and q must be co-prime.

• Euler’s Theorem
• Given a number n, ∀a ∈ {1, 2, 3,…., n-1}
• GCD(a, n)=1 => aɸ(n) mod n = 1

12
 SOME NUMBER THEORY FACTS

• Euler totient function (n) where n1 is the number of integers in the
[1,n] interval that are relatively prime to n
• Two numbers are relatively prime if their greatest common divisor (gcd) is 1

• Euler’s theorem:

if aZn*, then a(n)  1 mod n

• Special case: Fermat’s Little Theorem

if p is prime and gcd(a,p)=1, then ap-1  1 mod p
PUBLIC-KEY CRYPTOGRAPHY

public
key
private
public ? key
key

Alice Bob
Given: Everybody knows Bob’s public key

- How is this achieved in practice?

Only Bob knows the corresponding private key
Goals: 1. Alice wants to send a message that only Bob can read
2. Bob wants to send a message that only Bob could
have written
 PUBLIC-KEY ENCRYPTION

• Key generation: computationally easy to generate a pair (public key PK,

private key SK)

• Encryption: given plaintext M and public key PK, easy to compute ciphertext
C=EPK(M)

• Decryption: given ciphertext C=EPK(M) and private key SK, easy to compute
plaintext M
• Infeasible to learn anything about M from C without S K

• Trapdoor function: Decrypt(SK,Encrypt(PK,M))=M

slide 15
 APPLICATIONS OF PUBLIC-KEY CRYPTO
• Encryption for confidentiality
• Anyone can encrypt a message
• With symmetric crypto, must know the secret key to encrypt
• Only someone who knows the private key can decrypt
• Secret keys are only stored in one place

• Digital signatures for authentication

• Only someone who knows the private key can sign

• Session key establishment

• Exchange messages to create a secret session key
 ADVANTAGES OF PUBLIC-KEY CRYPTO
• Confidentiality without shared secrets
• Very useful in open environments
• Can use this for key establishment, avoiding the “chicken-or-egg” problem
• With symmetric crypto, two parties must share a secret before they can
exchange secret messages
• Authentication without shared secrets
• Encryption keys are public, but must be sure that Alice’s public key is really
her public key
• This is a hard problem… Often solved using public-key certificates

slide 20
 DISADVANTAGES OF PUBLIC-KEY CRYPTO
• Calculations are 2-3 orders of magnitude slower
• Modular exponentiation is an expensive computation
• Typical usage: use public-key cryptography to establish a shared secret,
then switch to symmetric crypto
• SSL, IPsec, most other systems based on public crypto
• Keys are longer
• 2048 bits (RSA) rather than 128 bits (AES)
• Relies on unproven number-theoretic assumptions
• Factoring, RSA problem, discrete logarithm problem, decisional Diffie-
Hellman problem…
slide 21
 RSA
• Invented in 1978 by Ron Rivest, Adi Shamir and
Leonard Adleman
• Published as R L Rivest, A Shamir, L Adleman, "On
Digital Signatures and Public Key Cryptosystems",
Communications of the ACM, vol 21 no 2, pp120-
126, Feb 1978

22
 RSA ALGORITHM

• Most popular public key cryptosystem

• Based on the hard problem of “integer factorization”
• Security relies on the difficulty of factoring large composite numbers
• Essentially the same algorithm was discovered in 1973 by Clifford Cocks, who
works for the British intelligence
 MAIN ALGORITHM

As we know a cryptosystem is a 5-tuple (E,D,M,K,C),

where
M —a set of plaintexts (some use P as symbol);
K —the set of keys;
C —the set of ciphertexts;
E: M x K  C —the set of enciphering functions;
D: C x K  M —the set of deciphering functions;
 RSA: CHOOSING –EXAMPLE-1
• Choose 2 large prime numbers p, q (e.g., 1024 bits each)
For our example, we’ll choose p = 5 and q = 7
• Compute n = pq, z = (p - 1)(q - 1)
So n = 35 and z = 24
• Choose e (with e < n) that has no common factors with z. (e, z are “relatively prime”)
Let’s choose e = 5
• Choose d such that ed-1 is exactly divisible by z (in other words: ed mod z = 1 )
Let’s choose d = 29
• Public key is (n, e) and Private key is (n, d)
+ -
K = (35, 5) K = (35, 29)
B B
RSA: EXAMPLE -1
Bob chooses p = 5, q = 7. Then n = 35, z = 2
Choose, e = 5 (so e, z relatively prime).
d = 29 (so ed -1 exactly divisible by
e e
letter m m c = m mod n
encrypt:
l 12 1524832 17

d d
c c m = c mod n letter
decrypt:
17 481968572106750915091411825223071697 12 l
 RSA: EN/DECRYPTION
• Given (n,e) and (n,d) as computed above
• To encrypt bit pattern, m, compute
c = me mod n (0 < m < n)
• To decrypt received bit pattern, c, compute
m = cd mod n
e d
m = (m mod n) mod n

c
 RSA: WHY IS e d
mod n
m = (m mod n)

Useful number theory result:

If p, q are prime and n = pq,
y then y mod (p-1)(q-1)
x mod n = x mod n

e d ed
(m mod mod n = m
n) mod (p-1)(q-1)
ed mod n 1
= m mod n = m mod n
(since we chose ed to be divisible b
using number theory result above)
(p-1)(q-1) with remainder 1 )
= m
 WHY RSA DECRYPTION WORKS

• ed  1 mod (n)

• Thus ed = 1+k(n) = 1+k(p-1)(q-1) for some k
• If gcd(m,p)=1, then by Fermat’s Little Theorem, mp-1  1 mod p
• Raise both sides to the power k(q-1) and multiply by m, obtaining m 1+k(p-1)(q-1)
 m mod p
• Thus med  m mod p
• By the same argument, med  m mod q
• Since p and q are distinct primes and pq=n,
med  m mod n
 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 modulii
 if e fixed must ensure gcd(e,ø(n))=1

ie 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
 RSA Example 2- Key Setup
1. Select primes: p=17 & q=11
2. Calculate n = pq =17 x 11=187
3. Calculate ø(n)=(p–1)(q-1)=16x10=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 since
23x7=161= 10x160+1
6. Publish public key PK={7,187}
7. Keep secret private key PS={23,187}
 RSA Example - En/Decryption
 sample RSA encryption/decryption is:
 given message M = 88 (nb. 88<187)
 encryption:
C = 887 mod 187 = 11
 decryption:
M = 1123 mod 187 = 88
 SQUARE AND MULTIPLY ALGORITHM FOR
EXPONENTIATION
• Computing (x)c mod n
• Example: suppose that c=53=110101
• x53=((x13)2)2·x=(((x3)2)2·x)2)2·x =(((x2·x)2)2·x)2)2·x mod n

Alg: Square-and-multiply (x, n, c = ck-1 ck-2 … c1 c0)

z=1
for i  k-1 downto 0 {
z  z2 mod n
if ci = 1 then z  (z × x) mod n
}
return z
 Why RSA Works
 because of Euler's Theorem:

aø(n)mod n = 1 where gcd(a,n)=1
 in RSA have:

n=p.q

ø(n)=(p-1)(q-1)

carefully chose e & d to be inverses mod ø(n)

hence e.d=1+k.ø(n) for some k
 hence :
Cd = Me.d = M1+k.ø(n) = M1.(Mø(n))k
= M1.(1)k = M1 = M mod n
 WHY DOES RSA WORK?
• Need to show that (Me)d (mod n) = M, n = pq
• We know that when MZpq*, i.e., when gcd(M, n) = 1, then
Med  M (mod n)
• What if gcd(M, n)  1?
• Assume, wlog, that gcd(M, n) = p
• ed  1 (mod (n)), so ed = k(n) + 1, for some integer k.
• Med mod p = (M mod p)ed mod p = 0, so Med  M mod p
• Med mod q = (Mk*(n) mod q) (M mod q) = M mod q, so
Med  M mod q
• As p and q are distinct primes, it follows from the
Chinese Remainder Theorem that Med  M mod pq
EFFICIENCY OF COMPUTATION MODULO N
• Suppose that n is a k-bit number, and 0 x,y  n
• computing (x+y) mod n takes time O(k)
• computing (x-y) mod n takes time O(k)
• computing (xy) mod n takes time O(k2)
• computing (x-1) mod n takes time O(k3)
• computing (x)c mod n takes time O((log c) k2)
 RSA IMPLEMENTATION

• Select p and q prime numbers

• In general, select numbers, then test for primality
• Many implementations use the Rabin-Miller test,
(probabilistic test)
 WHY RABIN-MILLER TEST WORK
Claim: If the algorithm returns “n is composite”, then n is
not a prime.

Proof: if we choose a and returns composite on n, then

• am1, am-1, a2m  -1, a4m  -1, …, a2^{k-1}m  -1 (mod n)
• suppose, for the sake of contradiction, that n is prime,
• then an-1=a2^{k}m=1 (mod n)
• then there are two square roots modulo n, 1 and -1
• then a2^{k-1}m = a2^{k-2}m = a2m = am = 1 (contradiction!)
• so if n is prime, the algorithm will not return “composite”
RSA IMPLEMENTATION

e
• e is usually chosen to be 3 or 216 + 1 = 65537
• In order to speed up the encryption
• the smaller the number of 1 bits, the better
 RSA SECURITY

• RSA security depends on hardness of factoring n=pq

• Knowing (n) enables factoring n
• Knowing (e,d) such that ed mod (n)=1 enables factoring n
 WHY IS RSA SECURE?

• RSA problem: given c, n=pq, and e such that gcd(e,(p-1)(q-1))=1,

find m such that me=c mod n
• In other words, recover m from ciphertext c and public key (n,e) by taking eth
root of c modulo n
• There is no known efficient algorithm for doing this

• Factoring problem: given positive integer n, find primes p1, …, pk such that
n=p1e1p2e2…pkek

• If factoring is easy, then RSA problem is easy, but may be possible to

break RSA without factoring n
 THE RSA PROBLEM

• The RSA Problem: Given a positive integer n that is a product of two

distinct large primes p and q, a positive integer e such that gcd(e, (p-1)
(q-1))=1, and an integer c, find an integer m such that mec (mod n)
• widely believed that the RSA problem is computationally equivalent to
integer factorization; however, no proof is known

• The security of RSA encryption’s scheme depends on the hardness of

the RSA problem.
 (N) IMPLIES FACTORIZATION
• Knowing both n and (n), one knows
n = pq
(n) = (p-1)(q-1) = pq – p – q + 1
= n – p – n/p + 1
p(n) = np – p2 – n + p
p2 – np + (n)p – p + n = 0
p2 – (n – (n) + 1) p + n = 0
• There are two solutions of p in the above equation.
• Both p and q are solutions.
 “TEXTBOOK” RSA IS BAD
ENCRYPTION
• Deterministic
• Attacker can guess plaintext, compute ciphertext, and compare for equality
• If messages are from a small set (for example, yes/no), can build a table of
corresponding ciphertexts

• Can tamper with encrypted messages

• Take an encrypted auction bid c and submit
c(101/100)e mod n instead

• Does not provide semantic security (security against chosen-plaintext

attacks)
 INTEGRITY IN RSA ENCRYPTION

• “Textbook” RSA does not provide integrity

• Given encryptions of m1 and m2, attacker can create encryption of m1m2
• (m1e)  (m2e) mod n  (m1m2)e mod n
• Attacker can convert m into mk without decrypting
• (me)k mod n  (mk)e mod n
 INTEGRITY IN RSA ENCRYPTION
• In practice, often needs padding, e.g., Optimal Asymmetric Encryption
Padding (OAEP)
• Roughly, to encrypt M, chooses random r, encode M as M’ =
[X = M  H1(r) , Y= r  H2(X) ], where H1 and H2 are cryptographic hash
functions, then encrypt it as (M’) e
mod n
• Note that given M’=[X,Y], r = Y  H2(X), and M = X  H1(r)
• r is random and fresh
• Resulting encryption is plaintext-aware: infeasible to compute a valid
encryption without knowing plaintext
• … if hash functions are “good” and RSA problem is hard
 • An example of the RSA algorithm.
Here p=3, q=11, n=33, z=(p-1)*(q-
WORKING 1)=20, choose d=7, which is
EXAMPLE 3 OF RSA relative prime of z. choose e=3
where e*d mod 20 = 1.
• Here (3, 20) is public key. (7,20) is
private key.
• C=Pe mod n; P=Cd mod n;
Example 4
 DIGITAL SIGNATURES: THE PROBLEM
• Consider the real-life example - a person pays by credit card and signs
a bill; the seller verifies that the signature on the bill is the same with
the signature on the card
• Contracts, they are valid if they are signed.
• Signatures provide non-repudiation.
• ensuring that a party in a dispute cannot repudiate, or refute the
validity of a statement or contract.
• Can we have a similar service in the electronic world?
• Does Message Authentication Code provide non-repudiation? Why?
 DIGITAL SIGNATURES
• Message Authentication Code (MAC): One party
generates MAC, one party verifies integrity.
• Digital signatures: One party generates
signature, many parties can verify.
• Digital Signature: a data string which associates
a message with some originating entity.
 DIGITAL SIGNATURES
• Digital Signature Scheme:
• a signing algorithm: takes a message and a
(private) signing key, outputs a signature
• a verification algorithm: takes a (public) key
verification key, a message, and a signature
• Provides:
• Authentication, Data integrity, Non-Repudiation
 RSA SIGNATURES
Key generation (as in RSA encryption):
• Select 2 large prime numbers of about the same size, p and q
• Compute n = pq, and  = (q - 1)(p - 1)
• Select a random integer e, 1 < e < , s.t. gcd(e, ) = 1
• Compute d, 1 < d <  s.t. ed  1 mod 

Public key: (e, n) used for verification

Secret key: d used for generation
 RSA SIGNATURES

Signing message M
• Verify 0 < M < n
• Compute S = Md mod n
Verifying signature S
• Use public key (e, n)
• Compute Se mod n = (Md mod n)e mod n = M
Note: in practice, a hash of the message is signed and not the
message itself.
PRACTICAL SCENARIOS

Secret Key Public Key

Setting Setting

Secrecy / Stream ciphers Public key

Confidentiality Block ciphers + encryption: RSA, El
encryption modes Gamal, etc.

Authenticity / Message Digital Signatures:

Integrity Authentication Code RSA, DSA, etc.
 PRESENT USE OF RSA

Called as the “work horse” of Internet

security:
• Most Public Key Infrastructure (PKI)
products.
• SSL/TLS: Certificates and key-exchange.
• Secure e-mail: PGP, Outlook, …
 Attacks on RSA
 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
 Factoring Problem
 mathematical approach takes 3 forms:

factor n=p.q, hence compute ø(n) and then d

determine ø(n) directly and compute d

find d directly
 currently believe all equivalent to factoring

have seen slow improvements over the years
• as of May-05 best is 200 decimal digits (663) bit with LS

biggest improvement comes from improved algorithm
• cf QS to GHFS to LS

currently assume 1024-2048 bit RSA is secure
• ensure p, q of similar size and matching other constraints
 SUMMARY OF MATH-BASED ATTACKS ON RSA
• Three possible approaches:
1. Factor n = pq
2. Determine (n)
3. Find the private key d directly
• All are equivalent
• finding out d implies factoring n
• if factoring is hard, so is finding out d
• Should never have different users share one common
modulus
 Timing Attacks
Timing Attacks on Implementations of Diffie-Hellman, RSA,
DSS, and Other Systems (1996), Paul C. Kocher
 developed by Paul Kocher in mid-1990’s
 exploit timing variations in operations

eg. multiplying by small vs large number

or IF's varying which instructions executed
 infer operand size based on time taken
 RSA exploits time taken in exponentiation
 Timing Attacks

 countermeasures

use constant exponentiation
time

add random delays

blind values used in
calculations
 TIMING ATTACKS

• Is it possible in practice? YES.

OpenSSL Security Advisory [17 March 2003]

Timing-based attacks on RSA keys
================================
OpenSSL v0.9.7a and 0.9.6i vulnerability
----------------------------------------
Researchers have discovered a timing attack on RSA keys, to which
OpenSSL is generally vulnerable, unless RSA blinding has been turned on.
Progress in Factoring
 IMPLEMENTATION ATTACKS
• Attack the implementation of RSA.

• Timing attack: (Kocher 97)

The time it takes to compute Cd (mod N) can
expose d.

• Power attack: (Kocher 99)

The power consumption of a smartcard while it is
computing Cd (mod N) can expose d.

• Faults attack: (BDL 97)

A computer error during Cd (mod N) can expose
d. OpenSSL defense: check output. 5% slowdown.
 Chosen Ciphertext Attacks

• RSA is vulnerable to a Chosen Ciphertext Attack (CCA)

• attackers chooses ciphertexts & gets decrypted plaintext back
• choose ciphertext to exploit properties of RSA to provide info to help
cryptanalysis
• can counter with random pad of plaintext
• or use Optimal Asymmetric Encryption Padding (OAEP)
Adaptive Chosen Ciphertext Attack

• An interactive chosen-ciphertext
attack
• the attacker sends many ciphertexts
to be decrypted by an end-system
• may result in the gradual revelation
of the secret key.
 OTHER DECRYPTION ATTACKS ON RSA

Small encryption exponent e

• When e=3, Alice sends the encryption of message m to three people (public keys
(e, n1), (e, n2), (e,n3))
• C1 = M3 mod n1, C2 = M3 mod n2, C3 = M3 mod n3,
• An attacker can compute a solution
x to the nfollowing
c1 mod 1
system
x c2 mod n2
x c3 mod n3

• The solution x modulo n1n2n3 must be M3

• (No modulus!), one can compute integer cubit root
• Countermeasure: padding required
 Optimal
Asymmetric
Encryption
Padding (OAEP)
is the SOLUTION
 OTHER ATTACKS ON RSA

Forward Search Attack

• If the message space is small, the attacker
can create a dictionary of encrypted messages
(public key known, encrypt all possible
messages and store them)
• When the attacker ‘sees’ a message on the
network, compares the encrypted messages,
so he finds out what particular message
was encrypted
HYBRID ENCRYPTION (REAL WORLD)
Launch key Symmetric *#$fjda^j
for nuclear encryption u539!3t
missile (e.g. DES) t389E *&\@
“RedHeat” 5e%32\^kd
is...
Symmetric key
encrypted asymmetrically
Digital
User’s (e.g., RSA) Envelope
public key
As above, repeated Digital
(in certificate) for other recipients
or recovery agents Envelope
Randomly-
Generated Other recipient’s or
symmetric agent’s public key
“session” key (in certificate)
RNG in recovery policy
HYBRID DECRYPTION

*#$fjda^j Symmetric Launch key

u539!3t decryption for nuclear
(e.g. DES) missile
t389E *&\@ “RedHeat”
5e%32\^kd is...

Recipient’s Symmetric
private key “session” key
Asymmetric
decryption of Session key
“session” key (e.g. RSA)
Digital envelope must be
contains “session” decrypted using
key encrypted the recipient’s
using recipient’s Digital private key
public key Envelope
Thanks