CS549:

Cryptography and Network

Security
© by Xiang-Yang Li

Department of Computer Science,

IIT
Cryptography and Network Security 1
Notice©
This lecture note (Cryptography and Network Security) is prepared by
Xiang-Yang Li. This lecture note has benefited from numerous
textbooks and online materials. Especially the “Cryptography and
Network Security” 2nd edition by William Stallings and the
“Cryptography: Theory and Practice” by Douglas Stinson.
You may not modify, publish, or sell, reproduce, create derivative
works from, distribute, perform, display, or in any way exploit any
of the content, in whole or in part, except as otherwise expressly
permitted by the author.
The author has used his best efforts in preparing this lecture note.
The author makes no warranty of any kind, expressed or implied,
with regard to the programs, protocols contained in this lecture
note. The author shall not be liable in any event for incidental or
consequential damages in connection with, or arising out of, the
furnishing, performance, or use of these.

Cryptography and Network Security 2

Cryptography and Network
Security

Public key system

Xiang-Yang Li

Cryptography and Network Security 3

Public Key Encryption
 Two difficult problems
 Key distribution under conventional encryption
 Digital signature

 Diffie and Hellman, 1976

 Astonishing breakthrough
 One key for encryption and the other related key for
decryption
 It is computationally infeasible (under some
assumptions) to determine the decryption key using
only the encryption key and the algorithm

Cryptography and Network Security 4

Public Key Cryptosystem
 Essential steps of public key cryptosystem
 Each end generates a pair of keys
 One for encryption and one for decryption
 Each system publishes one key, called public key, and
the companion key is kept secret
 It A wants to send message to B
 Encrypt it using B’s public key
 When B receives the encrypted message
 It decrypt it using its own private key

Cryptography and Network Security 5

Encryption Digital signature
Cryptography and Network Security 6
Key distribution

Cryptography and Network Security 7

Applications of PKC
 Encryption/Decryption
 The sender encrypts the message using the receiver’s
public key
 Q: Why not use the sender’s secret key?
 Digital signature
 The sender signs a message by encrypt the message or a
transformation of the message using its own private key
 Key exchange
 Two sides cooperate to exchange a session key,
typically for conventional encryption

Cryptography and Network Security 8

Conditions of PKC
 Computationally easy
 To generate public and private key pair
 To encrypt the message using encryption key
 To decrypt the message using decryption key

 Computational infeasible
 To compute the private key using public key
 To recover the plaintext using ciphertext and public key

 The encryption and decryption can be

applied in either order

Cryptography and Network Security 9

One Way Function
 PKC boils down to one way function
 Maps a domain into a range with unique inverse
 The calculation of the function is easy
 The calculation of the inverse is infeasible

 Easy
 The problem can be solved in polynomial time
 Infeasible
 The effort to solve it grows faster than polynomial time
 For example: 2n
 It requires infeasible for all inputs, not just worst case

Cryptography and Network Security 10

Trapdoor One-way Function
 Trapdoor one way function
 Maps a domain into a range with unique inverse
 Y=fk(X)
 The calculation of the function is easy
 The calculation of the inverse is infeasible if the key is
not known
 The calculation of the inverse is easy if the key is
known

Cryptography and Network Security 11

Possible Attacks
 Brute force
 Use large keys
 Trade-off: speed (not linearly depend on key size)
 Confined to small data encryption: signature, key
management
 Compute the private key from public key
 Not proven that is not feasible for most protocols!
 Probable message attack
 Encrypt all possible messages using encryption key
 Compare with the ciphertext to find the matched one!
 If data is small, feasible, regardless of key size of PKC

Cryptography and Network Security 12

History
 In 1874, a book by William Stanley Jevons
described the relationship of one-way
[1]

functions to cryptography and went on to

discuss specifically the factorization
problem used to create the trapdoor
function in the RSA system.

Cryptography and Network Security 13

History
 1976, Diffie-Hellman protocol was the first published
practical method for establishing a shared secret-key over
an authenticated (but not private) communications channel
without using a prior shared secret.

 Merkle's public-key-agreement technique became known as

Merkle's Puzzles, and was invented in 1974 and published in
1978.

 RSA invented in 1977, and published 1978

 ElGamal system 1984
 Elliptic curve cryptography (ECC) , Neal Koblitz[1] and
Victor S. Miller[2] in 1985.
 Digital Signature Algorithm (DSA) 1991-1993
Cryptography and Network Security 14
History
 [Link]
160/ British
 National Security Action Memorandum
160
 Kennedy Nuclear Weapon
 [Link]
 National Security Action Memorandum 160 (from June 6,
1962), entitled "Permissive Links for Nuclear Weapons in
NATO". The claim was that this memo -- signed by
President Kennedy and endorsing a memo from his science
advisor, Jerome Weisner -- was the basis for the invention
of public key cryptography by NSA.

Cryptography and Network Security 15

Cryptography and Network Security 16
Cryptography and Network Security 17
Cryptography and Network Security 18
Cryptography and Network Security 19
Cryptography and Network Security 20
Cryptography and Network Security 21
Cryptography and Network Security 22
RSA Algorithm
 R. Rivest, A. Shamir, L. Adleman (1977)
 James Ellis came up with the idea in 1970, and proved that it was
theoretically possible. In 1973, Clifford Cocks a British
mathematician invented a variant on RSA; a few months later,
Malcom Williamson invented a Diffie-Hellman analog
 Only revealed till 1997

 Patent expired on September 20, 2000.

 Block cipher using integers 0~n-1
 Thus block size k is less than log2n

 Algorithm:
 Encryption: C=Me mod n
 Decryption: M=Cd mod n

 Both sender and the receiver know n

Cryptography and Network Security 23
RSA (public key encryption)
 Alice wants Bob to send her a message. She:
 selects two (large) primes p, q, TOP SECRET,
 computes n = pq and (n) = (p-1)(q-1),
(n) also TOP SECRET,
 selects an integer e, 1 < e < (n), such that
gcd(e, (n)) = 1,
 computes d, such that de  1 (mod (n)),
d also TOP SECRET,
 gives public key (e, n), keeps private key (d, n).

Cryptography and Network Security 24

Requirements
 Possible to find e and d such that
 M=Mde mod n for all message M
 Easy to conduct encryption and decryption
 Infeasible to compute d
 Given n and e

Cryptography and Network Security 25

RSA Example
1. Select primes: p=17 & q=11
2. Compute n = pq =17×11=187
3. Compute ø(n)=(p–1)(q-
1)=16×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 since 23×7=161=
10×160+1
6. Publish public key KU={7,187}
7. Keep secret private key KR={23,17,11}
Cryptography and Network Security 26
RSA Example cont
 sample RSA encryption/decryption is:
 given message M = 88 (nb. 88<187)
 encryption:
C = 887 mod 187 = 11
 decryption:
M = 1123 mod 187 = 88

Cryptography and Network Security 27

Key Generation
 Recall Euler Theorem
 a(n)+1=a mod n for all 0<a<n and gcd(a,n)=1
 Then ed=1 mod (n) is sufficient to make algorithm
correct (need more proofs)
 RSA chooses the following
 Integer n=pq for two primes p and q
 Select e, such that gcd(e, (n))=1
 Compute the inverse of e mod (n)
 The result is set as d

Cryptography and Network Security 28

Key Generation
 The prime numbers p and q must be
sufficiently large
 They are chosen by applying primality testing of
randomly chosen large numbers
 About n/ln n prime numbers less than n
 Implies needs to check about 2ln n random numbers
to find 2 primes numbers around n
 Compute n=pq, keep p and q secret!
 Select random number e
 Test gcd(e, (n))=1, and get d if equation holds

Cryptography and Network Security 29

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

Cryptography and Network Security 30

Exponentiation

Cryptography and Network Security 31

More on Exponention (PGP)
 To compute Cd mod n, we compute
 Cd mod p and
 Cd mod q

 Remember that the receiver could keep p,q

 Then Chinese Remainder Theorem to find
 Cd mod n
 Here we use the fact that the following equation has
one unique solution in the range of [1, pq]
 x  a mod p

 x  b mod q
Cryptography and Network Security 32
Security of RSA
 Brute force: try all possible private keys
 Factoring integer n, then know (n)
 Not proven to be NPC
 Determine (n) directly without factoring
 Equivalent to factoring! (1996)  (n)  ( p  1)(q  1)
 Two variables and two equations  n  pq


 Determine d directly without knowing (n)

 Currently appears as hard as factoring
 But not proven, so it may be easier!

Cryptography and Network Security 33

Practical Considerations
 Testing p, q using probability first, then
deterministic methods
 A good random number generator is needed for p,q
 'random' and 'unpredictable'
 Primes p and q should be in similar scale
 Both p-1 and q-1 should have large prime factor
 The gcd(p-1,q-1) should be small
 The encryption key e = 2 should not be used
 The decryption key d should larger than n1/4
 RSA is much slower than symmetric cryptosystems.
 In practice, typically encrypts a secret message with a symmetric
algorithm, encrypts the (comparatively short) symmetric key with
RSA, and transmits both the RSA-encrypted symmetric key and the
symmetrically-encrypted message to Alice.
Cryptography and Network Security 34
Fixed point of RSA
 How many m such that
 me=m mod n assume that gcd(m, n)=1
 It is same as me-1=1 mod n
 Thus, me-1=1 mod p and me-1=1 mod q
 Solutions gcd(e-1,p-1)*gcd(e-1,q-1)
 Need more proofs.

Cryptography and Network Security 35

continue
 Solving me-1=1 mod p
Each number in [1, p - 1] is written as

g i mod p where i is an integer in [1, p - 1] and g is primitive root
Then m e 1  1 mod p is same as finding i such that
( g i ) e 1  1 mod p
Since g is primitive root, we have
p  1 divides i (e  1)
Let d  gcd( p  1, i (e  1))
p 1 i (e  1)
Then divides
d d
p 1 e 1 p 1
Since gcd( , )  1, we have divides i.
d d d
p 1
Thus, the choices for i is j , where j  1,2,...d .
d Cryptography and Network Security 36
Cyclic Attack
 Continuously re-encrypt the ciphertext
 Compute ce mod n, me2 = (me ) emod n, me3 mod n…till
it reaches same C, then the previous one is m
 Need period large
 Let r be the largest prime of p-1, L be the largest
prime of r-1
 Then period is at least L with high probability
 Implies that we often need find a large prime x
 Based on this, find a large prime of y=kx+1 format (by trying
k=2,3,…)
 Based on y, then find a large prime p=t y+1 format
 Try difference values for t=2,3,4…
Cryptography and Network Security 37
Avoid Cyclic attack
 Strong Primes
 It has been suggested that choosing “Strong Primes” for p
and q increases the number of cycles required to break the
encryption:
 p is a strong prime if p-1 and p+1 both have large factors, t
and w
 t-1 and t+1 have a large factor
 w-1 and w+1 have a large factor
 In analysis with small key size (10-70 bit) we saw no
correlation between key size and cycles required to crack.
 ●Large Primes
 In tests, keys greater than 60 bits were not crackable using a cyclic
attack in 24 hours
 As RSA currently uses keys that are 1024 bits or higher, it would take
many years to crack
 This type of attack is not deemed feasible with current hardware
Cryptography and Network Security 38
How to deal with p, q
 Delete them securely
 Or used for speed-up calculation from CRT
 Compute Me mod p and Me mod q
 Then find using Me mod n based on CRT

Cryptography and Network Security 39

Timing Attacks
 Keep track of how long a computer takes to
decrypt a message!
 Paul Kocher, 1995, Dec-7
 Stunning attack strategy and cipher only attack!
 Guessing the key bit by bit

 Countermeasures (Rivest 11 Dec 1995)

 Constant exponentiation time
 Random delay
 Blinding (add a random number for encryption and
decryption)

Cryptography and Network Security 40

Attack when same keys for
Encryption and Signature
 Collect ciphertext c (send to Alice), want to find m=cd
mod n
 Attacker chooses random r
 Compute x= re mod n; y=xc mod n; and t= r-1 mod n
 Attacker gets Alice to sign y with private key using
RSA: yd mod n
 That is why not use the same key for encryption and digital signature
 Alice sends u= yd mod n to Attacker
 Attacker then computes tu mod nm

Cryptography and Network Security 41

Other attacks on RSA
 Comprised decryption key
 If the private key d (for decryption of received
ciphertext) of a user is comprised, then the user has to
reselect n and e and d
 It cannot use the old number n to produce the key-pairs!
 Otherwise attacker already can factor n almost surely!
 The number n can only be used by one
person
 If two user uses the same n, even they do not know the
factoring of n, they still could figure out the factoring of
n with probability almost one.
 Similar as above

Cryptography and Network Security 42

Factoring algorithm given the
decryption key d
Algorithm Factor(n,e ,d) // given n, e, and d, find a factor of n

Choose a random w in [1, n - 1]

compute x  gcd (w,n)
if 1  x  n then output x as a factor, and quit
write ed-1  2 s r , where r is odd
compute v  wr mod n
If v  1 mod n, then quit and failed
while v  1 mod n do
v0  v;
v  v 2 mod n
If v0  -1 mod n then quit and faild
else compute x  gcd (v0  1,n) as one factor of n
Cryptography and Network Security 43
Bit security of RSA
 Given ciphertext C,
 We may want to find the last bit of M, denoted by
parity(C)
 We may want to find if M>n/2, denoted by half(C)
 We may want to find all bits of M

 The above three attacks are the same!

 If we can solve one, we can solve the other two!

Cryptography and Network Security 44

 Bit security of RSA
1. The following two are equivalent
C  M mod n
e

1. Find the last bit of M, denoted by

Then the encrytion of 2M is (2M ) e mod n  2e M e mod n  2e C mod n
If M  n / 2, then 2 M  n and (2 M mod n) is an even number
parity(C)
If M  n / 2, then 2 M  n and (2 M mod n  2 M  n) is an odd number 2. Find if M>n/2, denoted by half(C)
Thus, when M  n / 2, the last bit of the message returned by parity(2e C ) will be 0;
when M  n / 2, the last bit of the message returned by parity(2e C ) will be 1.

Thus, if we can solve parity(C),then we can use parity(2e C ) to answer whether M  n / 2 or not.

Then, consider t he other direction. Assume that we can solve half(C).

Then we use the following property
M
1)If M is an even number, then it is easy toshow that  M * 2 1 mod n
2
1
In other words, M * 2 mod n is an integer  n/ 2 when M is even.

2) When M is an odd number, assume that M * 2 1  x mod n.

Then we have 2 * M * 2 1  2 x mod n ,  M  2 x mod n
Since M is an odd number, obviously, x  n / 2.
Thus, M * 2 1 mod n is an integer  n/ 2 when M is odd
Notice that the encrytion of M * 2 1 mod n is C*( 2-1 mod n) mod n
Thus, half(C*( 2-1 mod n) mod n) returns " message is  n/2"  M is odd
half(C*( 2-1 mod n) mod n) returns " message is  n/2"  M is even
Cryptography and Network Security 45
 Bit security of RSA
1. The following two are equivalent
1. Find the last bit of M, denoted by
parity(C)
2. Find all bits of M

C  M e mod n
Then the encrytion of 2M is (2M ) e mod n  2e M e mod n  2e C mod n
If M  n / 2, then 2M  n and (2M mod n) is an even number
If M  n / 2, then 2M  n and (2 M mod n  2M  n) is an odd number
Thus, when M  n / 2, the last bit of the message returned by parity(2e C ) will be 0;
when M  n / 2, the last bit of the message returned by parity(2e C ) will be 1.

Thus, if we can solve parity(C),then we can use parity(2e C ) to answer whether M  n / 2 or not.
We continute this by checking parity(2 2 e C )  tells whether 2 M mod n  n/ 2 or not
We continute this by checking parity(2ie C )  tells whether 2i 1 M mod n  n/ 2 or not

Cryptography and Network Security 46

Other Public Key Systems
 Rabin Cryptosystem
 Decryption is not unique
 Elgamal Cryptosystem
 Expansion of the plaintext (double)
 Knapsack System
 Already broken
 Elliptic Curve System
 If directly implement Elgamal on elliptic curve
 Expansion of plaintext by 4; Restricted plaintext
 Menezes-Vanston system is more efficient
Cryptography and Network Security 47
Rabin Cryptosystem
 Procedure
 Let n=pq and p=3 mod 4, q=3 mod 4
 Publish n, and a number b<n
 For message m
 C=m(m+b) mod n
 The receiver decrypts ciphertext C
 (b2/4+C)1/2-b/2

Cryptography and Network Security 48

Analysis
 For receiver, need solve equation
 x2+xb=C mod n
 Let x1=x+b/2, c=b2/4+C, then need
 Solve x12 =c mod n
 Chinese Remainder Theorem implies that
 x12 =c mod p
 x12 =c mod q
 When p=3 and q=3 mod 4
 Solution x1=c(p+1)/4 mod p and x1=c(q+1)/4 mod q
 Then Chinese Remainder Theorem again to combine
solution

Cryptography and Network Security 49

Security
 Breaking it < factoring n
 Secure against
 Chosen plaintext attack

 Not secure against

 Chosen ciphertext attack

 Decoding produces three false results in addition to the correct

one, so that the correct result must be guessed. This is the major
disadvantage of the Rabin cryptosystem and one of the factors
which have prevented it from finding widespread practical use.
 It has been proven that decoding the Rabin cryptosystem is
equivalent to the integer factorization problem, which is rather
different than for RSA.

Cryptography and Network Security 50

Dealing with 4 solutions
 By adding redundancies, for example, the
repetition of the last 64 bits, the system
can be made to produce a single root.
 If this technique is applied, the proof of
the equivalence with the factorization
problem fails.

Cryptography and Network Security 51

Breaking Rabin System Same as
Factoring
 If we can do factorization of n, we clearly
can solve the equation x2=a mod n
 Assume that we can solve the equation x2=a
mod n and get all 4 solutions
x1,x2,x3,x4,where x1=n-x2, and x3=n-x4.
 Then x12= x32 mod n; thus,
 (pq) | (x1 - x3)(x1 + x3)
 It is easy to show that (pq) does not divide
(x1 - x3) or (x1 + x3)
 Thus, gcd(n, x1 - x3) is one factor of n, and
gcd(n, x1 + x3) is another Cryptography and Network Security 52
ElGamal Cryptosystem
 Based on Discrete Logarithm
 Find unique integer x such that gx=y mod p
 Here g is a primitive element in Zp, p is prime
 Procedure
 Make p, g, y public, keep x secret
 Encryption:
 Ek(m)=(gk mod p, m y k mod p)
 Decryption
 Dk(y1,y2)=y2(y1x)-1 mod p

Cryptography and Network Security 53

Efficiency
 ElGamal encryption is probabilistic, meaning that a
single plaintext can be encrypted to many possible
ciphertexts, with the consequence that a general
ElGamal encryption produces a 2:1 expansion in
size from plaintext to ciphertext.
 Encryption under ElGamal requires two
exponentiations;
 however, these exponentiations are independent of the message
and can be computed ahead of time if need be.
 Decryption only requires one exponentiation (instead of division,
exponentiate y1 to p-1 − x).
 Unlike in the RSA and Rabin systems, ElGamal decryption cannot
be sped up via the Chinese remainder theorem.

Cryptography and Network Security 54

Security of ElGamal
 ElGamal is a simple example of a semantically
secure asymmetric key encryption algorithm
(under reasonable assumptions).
 ElGamal's security rests, in part, on the difficulty
of solving the discrete logarithm problem in G.
 Specifically, if the discrete logarithm problem could be solved
efficiently, then ElGamal would be broken. However, the security
of ElGamal actually relies on the so-called Decisional Diffie-
Hellman (DDH) assumption. This assumption is often stronger
than the discrete log assumption, but is still believed to be true for
many classes of groups.

Cryptography and Network Security 55

Semantic Security
 Semantic security is a widely-used definition for security
in an PKS.
 For a cryptosystem to be semantically secure, it must be infeasible
for a computationally-bounded adversary to derive significant
information about a message (plaintext) when given only its
ciphertext and the corresponding public encryption key.
 Semantic security considers only the case of a "passive"
attacker, i.e., one who observes ciphertexts and generates
chosen ciphertexts using the public key
 Indistinguishability definition is used more
commonly than the original definition of semantic
security.

Cryptography and Network Security 56

Indistinguishability: semantic
security.
 Indistinguishability under Chosen Plaintext Attack
(IND-CPA) is commonly defined by the following
game:
 A probabilistic polynomial time-bounded adversary is given a
public key, which it may use to generate any number of ciphertexts
(within polynomial bounds).
 The adversary generates two equal-length messages m0 and m1,
and transmits them to a challenge oracle along with the public key.
 The challenge oracle selects one of the messages by flipping a
uniformly-weighted coin, encrypts the message under the public
key, and returns the resulting ciphertext c to the adversary.

Cryptography and Network Security 57

Cont.
 The underlying cryptosystem is IND-CPA (and
thus semantically secure under chosen plaintext
attack) if
 the adversary cannot determine which of the two messages was
chosen by the oracle, with probability significantly greater than 1/2
(the success rate of random guessing).
 Prob(correct guess)-1/2 < 1/p(k) for a polynomial p, and k is the
message size
 a semantically secure encryption scheme must by
definition be probabilistic, possessing a component
of randomness; if this were not the case, the
adversary could simply compute the deterministic
encryption of m0 and m1 and compare these
encryptions with the returned ciphertext c to
successfully guess the oracle's choice.
Cryptography and Network Security 58
Deal with deterministic PKS
 RSA, can be made semantically secure
(under stronger assumptions) through the
use of random encryption padding schemes
such as Optimal Asymmetric Encryption
Padding (OAEP).

 ElGamal scheme is semantically secure

Cryptography and Network Security 59

Security of ElGamal Encryption
 If the computational Diffie-Hellman (CDH)
assumption holds the underlying cyclic
group G of order q, then the encryption
function is one-way
 The CDH assumption states that, given
 (g,ga, gb)
 for a randomly-chosen generator g and random
 Numbers a, b,
 it is computationally intractable to compute the value
 gab .


Cryptography and Network Security 60

Cont.
 If the decisional Diffie-Hellman assumption (DDH)
holds in G, then ElGamal achieves semantic
security. Semantic security is not implied by the
computational Diffie-Hellman assumption alone
 Consider a (multiplicative) cyclic group G of order q, and with
generator g. The DDH assumption states that, given ga and gb for
randomly-chosen 0<a,b <q, the value gab "looks like" a random
element in G.
 This intuitive notion is formally stated by saying that the following
two probability distributions are computationally indistinguishable
(in the security parameter q):
 (ga, gb, gab), where a and b are randomly and independently
chosen from [1,q-1].
 (ga, gb, gc), where a,b,c are randomly and independently
chosen from [1,q-1].

Cryptography and Network Security 61

Cont.
 ElGamal encryption is not secure under
chosen ciphertext attack.
 For example, given an encryption (c1,c2) of some
(possibly unknown) message m, one can easily
construct a valid encryption (c1,2c2) of the message 2m.

 Other schemes related to ElGamal which

achieve security against chosen ciphertext
attacks have also been proposed.
 The Cramer-Shoup system

Cryptography and Network Security 62

Malleability
 An encryption algorithm is malleable
 if it is possible for an adversary to transform a
ciphertext into another ciphertext which decrypts to a
related plaintext.
 That is, given an encryption of a plaintext m, it is
possible to generate another ciphertext which decrypts
to f(m), for a known function f, without necessarily
knowing or learning m.
 Malleability is often an undesirable
property in a general-purpose
cryptosystem, since it allows an attacker to
modify the contents of a message.
 But it does allow searchable encryption (Symmetric
Searchable Encryption) Cryptography and Network Security 63
ElGamal is malleable.
 In the ElGamal cryptosystem, a plaintext m
is encrypted as E(m) = (gk,mYk), where (g,Y)
is the public key.
 Given such a ciphertext (c1,c2), an
adversary can compute (c1,tc2), which is a
valid encryption of tm, for any t.

Cryptography and Network Security 64

Bit security of Discrete Log
 Given gx=y mod p
 We may want to find the value of x
 Find some bits of x

 Assume that p-1 = 2st

 We can find the last s bits of x for sure
 But to find the other bits of x is same as to find all bits
of x!
 Example, the last bit of x is
0  y is QR iff y(p-1)/2=1 mod p
 1 y is NQR iff y(p-1)/2=-1 mod p

Cryptography and Network Security 65

DH Assumption
 Consider a cyclic group G of order q. The DDH
assumption states that,
 given (g,ga,gb) for a randomly-chosen generator g and random ,
the value gab "looks like" a perfectly random element of G.
 This intuitive notion is formally stated by saying
that the following two ensembles are
computationally indistinguishable:
 (g,ga,gb,gab), where g,a,b are chosen at random as
described above (this input is called a "DDH tuple");
 (g,ga,gb,gc), where g,a,b are chosen at random and c is
chosen at random.
 Diffie-Hellman problem
 computing gab from (g,ga,gb)

Cryptography and Network Security 66

Knapsack Cryptosystem
 Based on subset sum problem
 Given a set, find a subset with half summation value
 It is NPC problem generally

 Superincreasing set if si>j<isj

 The subset problem over superincreasing
set can be solved in polynomial time!
 Been broken by Shamir, 1984
 Using integer programming tech by Lenstra

Cryptography and Network Security 67

Solve Subset Problem
 Let T be the half summation, t=T;
 For i=n downto 1 do
 If tsi then
 t=t-si
 Set xi=1
 Else xi=0
 If xisi=T then (x1, x2,… xn) is the solution
 Else, there is no solution

Cryptography and Network Security 68

Knapsack System
 Procedure
 Select a superincreasing set s
 Let p be prime larger than set summation of s,
 Select integer a, keep s, a, p secret
 Make vector t=(as1, as2,…asn) mod p public
 Encryption
 Ciphertext C = E(x1,x2,…xn)=xiti mod p
 Decryption
 Solve the subset summation problem (s, a-1C mod p)

Cryptography and Network Security 69

Break of this system
 Adi Shamir, A Polynomial Time Algorithm
for Breaking the Basic Merkle-Hellman
Cryptosystem. CRYPTO 1982, pp279–288.
 [Link]
to/HTML/PDF/C82/[Link]

Cryptography and Network Security 70

Elliptic Curve Cryptography
 majority of public-key crypto (RSA, D-H)
use either integer or polynomial arithmetic
with very large numbers/polynomials
 imposes a significant load in storing and
processing keys and messages
 an alternative is to use elliptic curves
 offerssame security with smaller bit sizes
 was suggested independently by Neal Koblitz[1] and
Victor S. Miller[2] in 1985.
 Paper
 [Link]
1987-0866109-5/[Link]
Cryptography and Network Security 71
USE of ECC
 At the RSA Conference 2005, the National Security Agency
(NSA) announced Suite B which exclusively uses ECC for
digital signature generation and key exchange. The suite is
intended to protect both classified and unclassified national
security systems and information.[5]
 Recently, a large number of cryptographic primitives based
on bilinear mappings on various elliptic curve groups, such as
the Weil and Tate pairings, have been introduced. Schemes
based on these primitives provide efficient identity-based
encryption as well as pairing-based signatures, signcryption,
key agreement, and proxy re-encryption.

Cryptography and Network Security 72

Real Elliptic Curves
 an elliptic curve is defined by an equation in
two variables x & y, with coefficients
 consider a cubic elliptic curve of form
 y2 = x3 + ax + b
 where x,y,a,b are all real numbers
 also define zero point O

 have addition operation for elliptic curve

 geometrically sum of Q+P is reflection of intersection
R

Cryptography and Network Security 73

Real Elliptic Curve Example

Cryptography and Network Security 74

More ECC example

Cryptography and Network Security 75

Finite Elliptic Curves
 Elliptic curve cryptography uses curves
whose variables & coefficients are finite
 have two families commonly used:
 prime curves Ep(a,b) defined over Zp
 use integers modulo a prime p
 best in software
 binary curves E2m(a,b) defined over GF(2n)
 use polynomials with binary coefficients
 best in hardware

Cryptography and Network Security 76

ECC using Fp
 An elliptic curve is the locus of points in
the affine plane whose coordinates satisfy
a certain cubic equation together with a
point at infinity O
 the point at which the locus in the projective plane
intersects the line at infinity. In the case of
characteristic p > 3 the defining equation of can be
written:
 where and are constants such that

Cryptography and Network Security 77

Operations
 We define the negative of a point P = (x,y)
to be − P = (x, − y) for
 P + Q = Q + P (commutativity)
 (P + Q) + R = P + (Q + R) (associativity)
 P + 0 = 0 + P = P (existence of an identity element)
 there exists ( − P) such that − P + P = P + ( − P) = 0
(existence of inverses)

 Here 0 is a point at infinity

Cryptography and Network Security 78

Elliptic Curve Cryptography
 ECC addition is analog of modulo multiply
 ECC repeated addition is analog of modulo
exponentiation
 need “hard” problem equiv to discrete log
 Q=kP, where Q,P belong to a prime curve
 is “easy” to compute Q given k,P
 but “hard” to find k given Q,P
 known as the elliptic curve logarithm problem

 Certicom example: E23(9,17)

Cryptography and Network Security 79

ECC Diffie-Hellman
 can do key exchange analogous to D-H
 users select a suitable curve Ep(a,b)
 select base point G=(x1,y1) with large order
n s.t. n*G=O
 Typically n is required to be prime
and close to size of all points
 A & B select private keys nA<n, nB<n
 compute public keys: PA=nA×G, PB=nB×G
 compute shared key: K=nA×PB, K=nB×PA
 same since K=nA×nB×G
Cryptography and Network Security 80
ECC Encryption/Decryption
 several alternatives, will consider simplest
 must first encode any message M as a point
on the elliptic curve Pm
 select suitable curve & point G as in D-H
 Order of G is a large prime, close to number of points
 each user chooses private key nA<n
 and computes public key PA=nA×G
 to encrypt Pm : Cm={kG, Pm+k PA}, k
random
 decrypt Cm compute:
Pm+kPA–nA(kG) = Pm+k(nAG)–nA(kG) = Pm
Cryptography and Network Security 81
Choosing of parameters
 Several classes of curves are weak and should be avoided:
 curves over F(2^m) with non-prime m are vulnerable to Weil descent attacks.[7][8]
 curves such that n divides pB − 1 (where p is the characteristic of the field – q for a
prime field, or 2 for a binary field) for sufficiently small B are vulnerable to MOV
attack[9][10] which applies usual DLP in a small degree extension field of to solve
ECDLP. The bound B should be chosen so that discrete logarithms in the field are
at least as difficult to compute as discrete logs on the elliptic curve .[11]
 curves such that |F_q| =q are vulnerable to the attack that maps the points on the
curve to the additive group of F_q [12][13][14]

Cryptography and Network Security 82

ECC Security
 relies on elliptic curve logarithm problem
 fastest method is “Pollard rho method”
 compared to factoring, can use much
smaller key sizes than with RSA etc
 for equivalent key lengths computations
are roughly equivalent
 hence for similar security ECC offers
significant computational advantages

Cryptography and Network Security 83

security
 Since all the fastest known algorithms that
allow to solve the ECDLP (baby-step giant-
step, Pollard's rho, etc.), need steps,
it follows that the size of the underlying
field shall be roughly twice the security
parameter.

Cryptography and Network Security 84