Transcript Advanced Internet Technologies

“‘To be an effective Information Warrior,
individuals need superior computer skills, as
well as an in-depth understanding of
information technology architectures,…
protocols and processes.’
Michael Erbschloe
author of
“Information Warfare: How to Survive Cyber Attacks”
1
AGENDA






MATHEMATICAL BACKGROUND
 Revision (3-7); ORDER of a mod n (8,9); Primitive Root g of
n (10,11); Index of a (12-14); a: quadratic residue mod p
and Legendre Symbol (15 to 32); Square and non-square
elements of Zp (33 to 36); dlogg,p(b) : Discrete Logarithm of
b for base g (mod p) (37 to 39);
Diffie-Hellman Key Exchange (40 to 50);
ElGamal’s PK System (51 to 57);
Digital Signature Systems (58 to 62);
Elliptic Curve Cryptosystem (ECC) (63 to 76);
Identity Based Encryption (IBE) (77 to 93): ISO/IEC 11770-3
Key Agreement Scheme, Shamir’s Method, (Cocks’s quadratic
residues IBE scheme and Pairing-based methods: left out for
self-study)
Modular Arithmetic:
systematized by Carl Friedrich
Gauss in his book Disquisitiones Arithmeticae, published in 1801
Reference: http://programmingpraxis.com/2009/07/07/modular-arithmetic/ as of
Dec 06, 2009


Exponentiation: repeated modular multiplication
Square root: that number which, when multiplied by
itself, equals the target number



normal arithmetic: √4 = +2 or -2.
modular arithmetic: √18 mod 31 = 7 or 24.
Since (24 + 7) mod 31 = 0, 7 and 24 may be considered to
be ‘negative’ of each other.
Consider x2 (mod 13):


x
0
1
2
3
4
5
6
7
8
9
10 11 12
x2
0
1
4
9
3
12
10
10
12
3
9
4
1
x2 (mod 13) acquires the values of 0, 1, 3, 4, 9, 10, 12 ONLY.
x2 (mod 13) is NEVER equal to 2, 5, 6, 7, 8, 11
3
Modular Arithmetic:
Square root of some numbers may not exist.



There is no x such that
x2 mod 13 = 7
 the square root of 7 mod 13 does not exist;
the only numbers that have square roots modulo 13
are 1, 3, 4, 9, 10, and 12, or, equivalently, ±1, ±3, and
±4.
Another restriction: the modular square root is only
defined if the modulus is an odd prime.
Example: COMPOSITE MODULUS: For x2 (mod 15):
Please see the next slide:
4
Composite modulus: No square root exists
Example: COMPOSITE MODULUS: For x2 (mod 15):
x
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
x2
0
1
4
9
1
10
6
4
4
6
10
1
9
4
1


As x is varied from 0 to 14,
2 (mod 15) acquires the values of 0, 1, 4, 6, 9,
 x
10 ONLY.

x2 (mod 15) is NEVER equal to 2, 3, 5, 7, 8, 11,
12, 13, 14.
4 has two sets of conjugate square roots: ±2 and ±7
 non-unique solution
 Hence the modular square root of 4 is said
not to exist when the modulus is composite.
5
Revision Slide-1
Logarithms
Logxy=a => y=xa
 Logx1=0
(x0= 1)
 Logxx=1
(x1= x)
 Logx(y.z)=Logx(y)+Logx(z)
 Logx(yr)=r . Logx(y)

6
Revision Slide-2
Euler’s theorem
Euler’s theorem: Generalization of
Fermat’s theorem:
If a and n are relatively prime,
(n)
a = 1 mod n
where (n) = Euler’s Totient Function
= number of positive integers less than
n and relatively prime to n
7
Order of a mod n
Given: a and n are relatively prime.
Let am=1 mod n.
The smallest positive value of m for which
the above equation is satisfied is called
the ORDER of a mod n.

Examples: Order of a mod 17: (Please see the next slide .)
44=1 mod 17  Order of 4 mod 17 = 4.
Similarly 316=1 mod 17; 516=1 mod 17; 28=1 mod 17; 88=1 mod 17 
Order of 3 mod 17 = 16; Order of 5 mod 17 = 16
Order of 2 mod 17 = 8; Order of 8 mod 17 = 8
8
Example:
p = 17
….1
i
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16
1i
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2i
2
4
8
16 15 13 9
1
2
4
8
16 15 13 9
1
3i
3
9
10 13 5
15 11 16 14 8
7
4
1
4i
4
16 13 1
5i
5
8
7i
7
8i
8
6
4
16 13 1
4
16 13 1
1
1
12 2
6
4
16 13 1
3
15 7
1
8
5
1
16 9
4
15 1
15 12 13 7
9
14 1
16 1
16 1
13 14 2
10 16 12 9
11 4
15 3
4
12 16 10 2
14 13 6
13 2
16 9
.
11 9
4
15 1
8
13 2
.
11i 11 2
5
4
10 8
3
16 6
16 1
16 1
16 1
.
16i 16 1
16 1
16 1
9
m
Example: a modulo 19
For a=2,3,10,13,14 or 15:
Choose any one of the above 6 values for a.
 As m is varied from 1 to 18,

am(modulo19) generates the entire set of non-zero
integers from 1 to 18. (The example of a=15 is given below.)
i
15i

1
2
15 16
3
4 5
6
7
8
9
10 11 12 13 14 15 16 17 18
12
9 2
11
13
5
18
4
3
7
10
17
8
6
14
1
For each of the ( above) 6 values of a
18
 a =1 mod 19.
Hence Order of a mod 19 for the above values of a is 18.
10
Primitive root:




Definition: If, for some integer value of ‘a’, the ‘order
of a mod n’ is equal to Φ(n), the integer value of ‘a’
is called the ‘Primitive Root of n’.
 Primitive roots of a prime number p will be
denoted by g.
Property: For a primitive root and for every value of
0<m≤Φ(n), am generates a distinct number (mod
n) and every such number is co-prime with n.
An integer may - or may not have – a primitive root.
Integer of type pα, 2pα , where p: an odd prime
number; α: a positive integer, have one or more
primitive roots.
11
Examples of primitive roots
n
2 3 4 5
6 7
9
10
Primitive 1 2 3 2,3 5 3, 5 2, 5 3, 7
roots of n
n
11
Primitive 2,6,
roots of n 7,8
13
14 17 18 19 22
2,6, 3, 3, 5, 2,
7,11 … … .. …
7,.
.
gs(n): The smallest primitive root of an integer n
Reference: http://mathworld.wolfram.com/PrimitiveRoot.html as
of Dec 06, 2009
Index of a number a
Let modulus: n
Primitive root of n: g
An integer, co-prime to n: a
x
If g = a mod n,
then x = v(a) is called the Index of a.
Examples: modulus = 11, primitive root = 6,
i
1 2 3 4 5 6 7 8 9 10
6i 6 3 7 9 10 5 8 4 2 1
For a = 5, 66 = 5 mod 11; Therefore v(5) = 6;
For b = 7, 63 = 7 mod 11; Therefore v(7) = 3.
Similarities between Log and Index
(v(a))
Given: a mod n = g
mod n
(v(b))
b mod n = g
mod n


Log(a.b) = Log a + Log b
axb mod n = g(v(a) + v(b)) mod n
 v(axb) = v(a) + v(b)


Example: 5x7 mod 11 = 6(6 + 3) mod 11
Log(ab) = b Log a
ab mod n = g(b. v(a)) mod n
b
 v(a ) = b. v(a)
7
(7x 6)
Examples: 5 mod 11 = 6
mod 11 =3
Similarly ba mod n = g(a. v(b)) mod n
Example: 75 mod 11 = 6(5x 3) mod 11 =10
References:
1. For the smallest primitive roots for the first few integers:
http://mathworld.wolfram.com/PrimitiveRoot.html as of Dec 06,
2009
2. For a list of first 1000 prime numbers:
http://primes.utm.edu/lists/small/1000.txt as of Dec 06, 2009
3. Primes by primitive roots:
http://www.research.att.com/~njas/sequences/Sindx_Pri.html as
of Dec 06, 2009
4. G.A.Miller, “ Methods to Determine the Primitive Roots of a
Number”,
http://www.jstor.org/view/00029327/di994161/99p0203o/0?frame=noframe&userID=89cf8ca8@uwindsor.
ca/01c0a8346600501ceadb5&dpi=3&config=jstor as of Dec 1, 2007
http://www.jstor.org/stable/2370177?&Search=yes&term=Number&term=Methods&term=Roots&term=Determ
ine&term=Primitive&list=hide&searchUri=%2Faction%2FdoAdvancedSearch%3Fq0%3DMethods%2Bto%2
BDetermine%2Bthe%2BPrimitive%2BRoots%2Bof%2Ba%2BNumber%26f0%3Dall%26c0%3DAND%26q1
%3D%26f1%3Dall%26c1%3DAND%26q2%3D%26f2%3Dall%26c2%3DAND%26q3%3D%26f3%3Dall%2
6wc%3Don%26Search%3DSearch%26sd%3D%26ed%3D%26la%3D%26jo%3D&item=11&ttl=7332&retu
rnArticleService=showArticle
as of Dec 06, 2009
15
2
Solution for x = a mod p
2
PROBLEM: Given values of ‘a’ and ‘p’: x = a mod p
where p: odd prime and a: an integer
To solve for x:
There are three possibilities:
(i) No solution:
‘a’ is said to be a “quadratic non-residue mod p”.
(ii) One solution if a = 0 mod p
(iii) Two solutions
‘a’ is said to be a “quadratic residue mod p”.
Reference: Henri Cohen,”A Course in Computational Algebraic
Number Theory”, Springer 1996, pp27
16
Example:
Existence of a solution
Consider modulus = 11.
Squares: 1,3,4,5,9
Non-squares: 2,6,7,8,10
2
For non-squares, a solution for x = a mod p does not
exist.
2
Thus there is no value of x, which satisfies x = 6 mod
11.
x
2
x mod 11
1 2 3 4 5 6 7 8 9 10
1 4 9 5 3 3 5 9 4 1
Definition:
Legendre-Jacobi-Kronecker Symbol
Legendre Symbol (a/p):
(i)
(a/p) = -1 if a is quadratic non-residue mod p
(ii)
(a/p) = 0 if a = 0
(iii)
(a/p) = 1 if a is quadratic residue mod p.
2
The number of solutions of x = a mod p will be
(1 + (a/p)).
18
Solutions,
if a is a quadratic residue mod p
If (a/p) = 1. there exists an x such that
2
x = a mod p
 An easy solution for half of the primes, which obey
p = 3 mod 4:
(p+1)/4
x=a
mod p
 For half of the remaining primes, which obey
p = 5 mod 8, there are two possibilities:



a
a
(p-1)/4
(p-1)/4
(p+3)/8
= +1  The solution is x = a
mod p.
(p-5)/8
= -1  The solution is x = 2a.(4a)
mod p.
For the remaining primes, which obey
p = 1 mod 8, it is difficult to come to
similar solutions.
19
Example:
2
Solutions for x: x = a mod p
For p =11: It obeys p = 3 mod 4.
 Hence if (a/p) = 1, its solutions can be
found by using
(p+1)/4
x=a
mod p
For p =11,

Given: a 1
3
4
5
9
To Find: x 1
5
9
4
3
Algorithm for finding out the value of (a/p)
(slides 22-34)
21
Algorithm for evaluating
Kronecker(a/b) where a, b ε Z


Step 1: If b = 0, output = 0 if lal≠ 1
= 1 if lal= 1 END
Step 2: (for removing 2’s from b)
Set v = 0
While b is even {
set v  (v + 1)
b  (b/2)}
If v is even, set k  1.
(a**2 – 1)/8
Otherwise k  (-1)
If b < 0, set b  (-b), AND if in addition
a < 0, set k  (-k).
22
Algorithm for evaluating
Kronecker(a/b) where a, b ε Z



Step 3 (for reducing size once)
Note: At this stage b is odd and b > 0.
Set a  a mod b
Step 4: If a = 0, output = 0 if b > 1
= k if b = 1
Step 5 (for removing powers of 2)
Set v = 0
While a is even {
set v  (v + 1)
a  (a/2)}
If v is odd, set k  (-1) (b**2 – 1)/8.k
contd. 2
END
23
Algorithm for evaluating
Kronecker(a/b) where a, b ε Z contd. 3
 Step 6: Subtract and apply reciprocity.
Note: At this stage a and b are odd.
Set r  (b – a).
(a-1).(b-1)/4
If r > 0, set k = (-1)
.k
ba
a  r;
Else set a  (-r).
Go to Step 4.
24
Legendre (a/b),
where a, b ε Z and b is an odd prime
Step 1: not required.
 Step 2: (required only for initializing k)
K is set to 1.
 Step 3 (for reducing size once)
Note: At this stage b is odd and b > 0.
Set a  a mod b
 Step 4: If a = 0,
output = 0 if b > 1
= k if b = 1

END
25
Legendre (a/b),
where a, b ε Z and b is an odd prime ….2

Step 5 (for removing powers of 2 from a)
Set v = 0
While a is even {
set v  (v + 1)
a  (a/2)}
If v is odd, set k  (-1) (b**2 – 1)/8.k
26
Legendre (a/b),
where a, b ε Z and b is an odd prime ….3








Step 6: Subtract and apply reciprocity.
Note: At this stage a and b are odd.
Set r  (b – a).
(a-1).(b-1)/4
If r > 0, set k = (-1)
.k
ba
a  r;
Else set a  (-r).
Go to Step 4.
27
Example 1
for Legendre Symbol
For modulus p = 11, we found

Squares: 1,3,4,5,9

Non-squares: 2,6,7,8,10
(i)
By using the algorithm (of the last three slides), it
can be seen that for each of the square values,
(a/p) = 1
(ii)
By using the algorithm (of the last three slides), it
can be seen that for each of the non-square
values, (a/p) = -1.
Note: Try the algorithm for one of the square values and one of
the non-square values and confirm the above two
statements.
Example 2
for Legendre Symbol
25 mod 11
Iteration 1:
 Step2: k = 1
 Step 3: a = 25 mod 11 = 3
 Step 4: a ≠ 0
 Step 5: v =0; Since v ≠ odd, no change in the value
of k.
 Step 6: r = 11- 3 = 8
(a-1).(b-1)/4
2.(10)/4
k = (-1)
.k = (-1)
.k = -1
b=3
a = 8.

29
Example 2
…2
for Legendre Symbol
Iteration 2: (begins at step 4)
 Step 4: a ≠ 0
 Step 5: v =0;
{ v = 1, a = 4}; {v = 2, a = 2}; {v = 3, a = 1}
(b**2 – 1)/8
Since v is odd, k = (-1)
.k = 1
 Step 6: r = 3- 1 = 2
k = (-1) (a-1).(b-1)/4.k = (-1) 0.(2)/4.k = 1
b=1
a = 2.
30
Example 2
for Legendre Symbol … 3
Iteration 3: (begins at step 4)

Step 4: a ≠ 0

Step 5: v =0;
{ v = 1, a = 1};
Since v is odd, k = (-1) (b**2 – 1)/8.k = 1

Step 6: r = 1- 1 = 0; a = 0
Iteration 4: (begins at step 4)
a =0  Since b = 1, output = k = 1
 By slide 18, a solution exists.
By slide 19, a solution for the primes, which obey p = 3 mod 4:
(p+1)/4
x=a
mod p.
2
Since 11 = 3 mod 4, the solution for x = 25 mod 11 is:
x = 253 mod 11 = 33 mod 11 =5
31
Example 3
for Legendre Symbol
17 mod 11
Iteration 1:
 Step2: k = 1
 Step 3: a = 17 mod 11 = 6
 Step 4: a ≠ 0
 Step 5: v =0;
{ v = 1, a = 3}
Since v is odd, k = (-1) (b**2 – 1)/8.k = - 1
 Step 6: r = 11- 3 = 8
k = (-1) (a-1).(b-1)/4.k = (-1) 2.(10)/4.k = 1
b = 3, a = 8.

32
Example 3
…2
for Legendre Symbol
Iteration 2: (begins at step 4)
 Step 4: a ≠ 0
 Step 5: v =0;
{ v = 1, a = 4}; {v = 2, a = 2}; {v = 3, a = 1}
(b**2 – 1)/8
Since v is odd, k = (-1)
.k = -1
 Step 6: r = 3- 1 = 2
k = (-1) (a-1).(b-1)/4.k = (-1) 0.(2)/4.k = -1
b=1
a = 2.
33
Example 3
…3
for Legendre Symbol
Iteration 3: (begins at step 4)
 Step 4: a ≠ 0
 Step 5: v =0;
{ v = 1, a = 1};
(b**2 – 1)/8
Since v is odd, k = (-1)
.k = -1
 Step 6: r = 1- 1 = 0; a = 0
Iteration 4: (begins at step 4)
a =0  Since b = 1, output = k = -1.
2
 By slide 18, no solution exists for x = 17 mod 11
34
Square and Non-square Elements
(next 4 slides)
35
Example:
p = 17
….1
i
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16
1i
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2i
2
4
8
16 15 13 9
1
2
4
8
16 15 13 9
1
3i
3
9
10 13 5
15 11 16 14 8
7
4
1
4i
4
16 13 1
5i
5
8
7i
7
8i
8
6
4
16 13 1
4
16 13 1
1
1
12 2
6
4
16 13 1
3
15 7
1
8
5
1
16 9
4
15 1
15 12 13 7
9
14 1
16 1
16 1
13 14 2
10 16 12 9
11 4
15 3
4
12 16 10 2
14 13 6
13 2
16 9
.
11 9
4
15 1
8
13 2
.
11i 11 2
5
4
10 8
3
16 6
16 1
16 1
16 1
.
16i 16 1
16 1
16 1
36
Example:
p = 17 ….2
Squares
Elements of Zp = {1,2 3,…(p-1)} can be either
Squares (as) or Non-squares (an).
Squares: 1, 2, 4, 8, 9, 13, 15, 16
1 = 162 mod 17; 2 = 62 mod 17 = 112 mod 17
4 = 152 mod 17; 8 = 52 mod 17 = 122 mod 17
9 = 142 mod 17; 13 = 82 mod 17 = 92 mod 17
15 = 72 mod 17 = 102 mod 17; 16 =132 mod 17

For all i, asi mod p = a square element only. 
A square element cannot be a primitive root.

Non-squares: 3, 5, 6, 7, 10, 11, 12, 14
No. of as elements = No. of an elements = (p-1)/2
37
Example:
p = 17 ….3
Sub-groups


Testing whether or not an element is square:
an efficient algorithm called Legendre Symbol
Examples of groups, formed by
 a=3, 5
: primitive roots;




Example: for p = 17, primitive roots: 3, 5, 7, 11
Finding primitive roots of a large prime
number: computationally tough
a= 2, 8 : two blocks of q = (p-1)/2 each
a= 4
: four blocks of (p-1)/4 each
38
Example:
p = 17 ….4
Sub-groups

Depending upon the generator elements, size
of Sub-groups of Zp:
 Full group: (p-1) members, if the generator
element is a primitive root
 Size of sub-groups: (p-1)/m
 Sub-group of size 1: g =1
 Sub-group of size 2: Members are 1 and
(p-1)
Example: Use a of 1, 16, 4, 2 or 8, 3 or 5 to get groups
of size 1, 2, 4, 8 and 16 respectively. (See slide 36.)
39
Logarithmic for Modular Arithmetic
Consider a prime number ‘p’ and its primitive
root g.
(There is at least one primitive root for every Zp.)
For any integer b, we can find the exponent ‘i’
such that
b=gi(mod p).
Both g and i are members of Zp i.e.
0≤ i ≤ (p-1)
i: Discrete Logarithm of b for base g (mod p)
: dlogg,p(b)

40
Discrete Logarithm Theorems




dloga,p(1) = 0
dloga,p(a) = 1
dloga,p(bc)= (dloga,pb + dloga,pc) mod Φ(p)
dlog (yr)= [r . dlog (y)] mod Φ(p)
a,p
a,p
Compare: Logx1=0
(x0= 1)
Logxx=1
(x1= x)
Logx(y.z)=Logx(y)+Logx(z)
Logx(yr)=r . Logx(y)
41
Calculation of Discrete Logarithm
Consider p: a prime number.
Its primitive root : generator element=g.
y = gx mod p



Given x, y can be calculated easily
using CLRS
algorithm. (as studied in RSA PK method)
For large prime numbers –
Given y, for calculation of x: no method
with a complexity lower than that for factorizing
prime numbers exists. This is known as the
Discrete Logarithm Problem (DLP).
42
Diffie-Hellman Key Exchange
(agreement) ……..1

Diffie-Hellman Key Exchange: based on DLP
 Alice selects a prime p and generator g of Gallois Field Zp
 select a random number a < p,
a
 computes y =g mod p and
 sends y , p and g to Bob
 Bob
 selects a random number b< p,
b
 computes z =g mod p and
 sends z to Alice
Reference: Whitfield Diffie and Martin E. Hellman,”New Directions in
Cryptography”, IEEE Transactions on Information Theory, IT22(6):644-654, November 1976
43
Diffie-Hellman Key Exchange
(agreement)……………..2
then Alice computes k = za mod p (= gab
mod p)
 And Bob computes
k = yb mod p (=gab
mod p).




Therefore Alice and Bob are able to get the same key
securely without meeting together by sending
messages on an insecure line.
A Hacker knows p, g, y and z. But without knowing a
or b, k cannot be determined.
a = dlogg,p(y) and b = dlogg,p(x) cannot be found,
since discrete log is difficult to evaluate for large
numbers.
44
Diffie-Hellman Key Exchange
Example








…1
Choose p = 11.
Primitive roots of 11 are 2, 6, 7, 8
Alice and Bob choose g = 2 for p =11 for key
exchange.
She chooses a private key of a = 5.
25 mod 11 = 10.
Alice sends y = 10 to Bob.
Bob chooses a private key of b = 7.
27 mod 11 = 7. Bob sends z = 7 to Alice.
45
Diffie-Hellman Key Exchange
Example
…2
SECRET KEY
 He calculates the secret key k = 107 mod 11
= 10
5
 Alice calculates the secret key k = 7 mod 11
= 10
EVE:
Knows about p = 11 and g = 2
Can sniff y =10 and z = 7. But does not know
about the private keys.
Reference: Example 5.2 from Man Young Rhee, “Internet Security:
Cryptographic principles. algorithms and protocols”. Wiley 2003 46
Diffie-Hellman Key Exchange:
To Find the private keys
To find the private keys:
For a:
Solve the equation 2a mod 11 = 10.
i.e. a = dlog2,11(10)
For b:
Solve the equation 2b mod 11 = 7
i.e. b = dlog2,11(7)
Calculation of discrete logarithms for
large prime numbers is very hard.
47
Diffie-Hellman Key Exchange:
The Protocol
Every user should publish her/his public key (p, g and
y) in a directory. Then all users, whose keys are in
the directory, can communicate with one another
securely by calculating the secret key.
Question: How authentic will the directory be?
 Authenticate using the Diffie-Hellman key: If Alice
and Bob recognize each other’s voice, voice samples
may be encrypted by using the secret key and
exchanged to confirm that there is no MITM.
Problem: Will work till voice synthesis technology is able

to reproduce the exactly similar voice samples.
48
Diffie-Hellman Key Exchange
Man-in-the-Middle attack…1





Alice sends y =ga mod p to Bob
Eve intercepts it and sends w =gc mod p to Bob.
Bob (believing that the message is from Alice)
b
 responds with z =g mod p; and
b
cb
 creates the key k1 = w = g
Eve intercepts Bob’s message and
c
bc
 is able to create the key k1 = z = g
d
 sends v =g mod p to Alice.
d
ad
 is able to create the key k2= y = g
Alice receives v and creates the key k2= va = gda
49
Diffie-Hellman Key Exchange
Man-in-the-Middle attack…2
All future communication:


Alice sends messages to Bob encrypted with k2
Eve




intercept the message and
decrypts it using the key k2
encrypts it/modified message using the key k1
Sends the encrypted message to Bob
Bob receives the message and is able to decrypt it
by using the key k1
-- similar scenario for the messages from Bob to Alice
 Thus Alice and Bob can be under the mistaken
impression that they are talking to each other.

50
MITM attack and smaller Sub-groups
For a prime number p,
Zp = {1,2 3,…(p-1)},
a primitive root g can generate all the members.
During a MITM attack, Eve may send a non-primitive
Root as g, leading to a small sub-group of Zp. This
may compromise the security.
 If g is a non-square:
y = ga mod p



is a square if a is even and
it is non-square if a is odd.
Thus Eve can check y and find out the last bit of
a ( ie whether a is even or odd)  Use only squares?
51
Safe Prime


If p = 2q +1, where p and q are both prime
numbers, p is called a safe prime.
Choose a group



with modulo p, where p = 2q + 1;
which has q elements;
for which g is a square. (Use Legendre Symbol
function to verify.)
52
Safe Primes:
How to choose g for such a group?

g should be a square;





Since it is a square, it cannot contain all the 2q
elements.
The number of elements must be a factor of (p-1).
However since p-1 = 2q, it can have only subgroups of 1, 2 and q.
Choose a random number r in the range
2 ……………. (p-2).
Select g = r2, except that it should not be
either 1 or (p-1)
53
ElGamal’s PK System - keys
ElGamal proposed two systems for use in PK system
and for encryption of plaintext messages.
PK System:
 Choose a prime number p and two random
numbers g and d such that





g is the primitive root modulo p.
1 ≤ d ≤ (p-2)
Calculate e =gd mod p
Private key: d
Public key: e, g and p
54
ElGamal’s PK System - Security
Example: Choose p =11, g = 6 and d = 8
e = 68 mod 11 = 4
Private key = 8; Public key: 4, 6 and 11
SECURITY: To find d from public key, one has
to solve the equation 6d mod 11 = 4 or d =
dlog6,11(4).
This is the Discrete Logarithm Problem.
It is computationally infeasible for large values
of p.
55
ElGamal Encryption
of plaintext message 0 ≤ m ≤ p-1
Bob wants to send a message securely to Alice.
He knows Alice’s public key: e, g and p.
Encryption Process by Bob:
 Choose a random number k <p;
k is to be kept
secret by Bob
k
 Message Key: K = e mod p
 The Cipher consists of two numbers: (C1, C2)
k
 C1= g mod p
C2 = K.m mod p
K masks the message by using the public key of Alice.
Bob sends the masked message C2 along with C1.
C1 helps Alice calculate the mask K for decryption.
56
Inverse of K helps calculation of m.

ElGamal’s PK System
- Encryption Example
Given: Alice’s public key: e = 4, g = 6 and p = 11
Bob chooses a random number k = 7.
Bob wants to send the message m = 5 to Alice.
m
ElGamal Encrypter
Public key
(C1, C2)
e, g, p
Message Key: K = ek mod p = 47 mod 11 = 5
C1 = gk mod p = 67 mod 11 = 8;
C2 = K.m mod p = 5x5 mod 11 = 3
Bob sends the Cipher (8, 3) to Alice.
57
ElGamal’s PK System –
Decryption
Alice receives (C1 and C2). She has her
private key d. To decrypt:
K = ek mod p = gdk mod p = C1d mod p
C2 = K.m mod p
or m = K-1 .C2 mod p
(C1, C2)
ElGamal Decrypter
m
d
58
ElGamal’s PK System –
Comments
Alice keeps d as a secret.
 Bob keeps k as his secret.
 Bob can compute the mask
K = ek mod p.
Bob does not know d. But he knows e,
where e =gd mod p.
Therefore K = gdk mod p
k
 Bob sends C2 along with C1 where C1= g mod p .
 Alice can compute K, without knowing k, since K =

C1d mod p.
59
ElGamal’s PK System –
Decryption Example
Given:
 Cipher = (C1, C2) = (8, 3)
 Alice’s Private Key = d = 8
To Find: m
K = C1d mod p = 88 mod 11 = 5
K-1 .5 mod 11 = 1; K-1 = 9
m = K-1 .C2 mod p = 9 .3 mod 11 = 5
Reference: Example 5.8 from Man Young Rhee,
“Internet Security: Cryptographic principles.
algorithms and protocols”. Wiley 2003
60
Digital Signature

Association with the entity, which signs
it:



The receiver can associate with the signing
entity.
The signer cannot repudiate it.
Association with the message:

The message, which is authenticated,
cannot be changed.
61
Attacks on RSA Systems …… 1

Low Exponent Attack: e is sometimes chosen to be
small ( eg 3) to make encryption faster.
Coppersmith Theorem: In a modulo n
polynomial f(x) of degree e, one can use an
algorithm of complexity log n to find the roots
if one of the roots is smaller than n1/e.
On applying the theorem to c = me mod n, for e=3, if
only two-third of the bits in m are known, the
algorithm, can find all the bits.
Recommendation: e may not be smaller than
216 + 1 = 65537.
62
Attacks on RSA Systems …… 2

Broadcast Attacks: If the same message is
sent to many recipients with the same public
key.
Example: e = 3:
a1 = m3 mod n1
a2 = m3 mod n2
a3 = m3 mod n3
CRT can be used to find
A = m3 mod n1. n2.n3
m can then be found by using ordinary
arithmetic.
63
Attacks on RSA Systems …… 3

Short Pad Attack: Bob wants to send a message m to Alice He pads it
with x and encrypts m ll x to get C1. The message is intercepted and
dropped by Eve.
Alice tells Bob that she has not received the message.
Bob again pads m with y and encrypts m ll y to get C2. The message is
intercepted by Eve.
If x and y are small, Coppersmith proved that Eve can find m.
Use Optimal Asymmetric Encryption Padding (OAEP) with
G: a function for converting k bits to m bits, and,
H: a function for converting m bits to k bits
Reference: 1. M. Bellare, P. Rogaway. Optimal Asymmetric Encryption -- How to encrypt
with RSA. Extended abstract in Advances in Cryptology - Eurocrypt '94 Proceedings,
Lecture Notes in Computer Science Vol. 950, A. De Santis ed, Springer-Verlag, 1995
http://cseweb.ucsd.edu/users/mihir/papers/oae.pdf as on 6th Dec 2009
2. http://en.wikipedia.org/wiki/Optimal_Asymmetric_Encryption_Padding as on 6th Dec
64
2009
Comparison

How secure is RSA and Diffie-Hellman
or ElGamal?



RSA: based on factorization
Diffie-Hellman and ElGamal: based on DLP
Have proved:


Factoring a large prime is equivalent to solving
DLP problem.
Exist algorithms with a sub-exponential but
super-polynomial complexity
65
Elliptic Curve Cryptosystem (ECC)

For ECC, the sub-exponential algorithm
of breaking it has not been found.


So ECC is more secure than RSA or
ElGamal
Or to say, using much smaller key size can
achieve the same security as RSA or
ElGamal with a larger key size, so more
efficient.
66
Elliptic curve group over real number



y2 = x3 + ax + b, where x, y, a
and b are real numbers.
All (x,y) points, satisfying above
equation, along with infinite point
O and addition operation, form a
group
Suppose P=(x,y) then define
–P=(x,-y).
67
Definition of a Group
[A1] closure under addition:
[A2] Associativity of addition:
[A3] Additive identity:
Group
Abelian Group
[A4] Additive inverse:
[A5] Commutativity of addition:
68
Elliptic curve example
69
Addition operation

If P and Q are distinct, and if P  -Q, define
P+Q as follows:




(A Geometric Approach)
Draw a line through P and Q, then the line will
intersect with the curve, the intersected point is
denoted as –R, and define P+Q=R.
Define P + (-P) = O
If P=(x,0), then P+P = O , (in fact, a vertical
line)
Otherwise, draw a tangent line through P,
the intersected point is defined as –R,
then P+P =2P =R.
70
Definition of P+Q = R
71
Definition of P+(-P)
72
Definition of P+P (where
y!=0)
73
Definition of P+P (where y=0)
74




Adding distinct points P and Q
When P = (xP,yP) and Q = (xQ,yQ) and P Q, P  -Q,
P + Q = R where s = (yP - yQ) / (xP - xQ)
xR = s2 - xP - xQ and yR = -yP + s(xP - xR)
Note that s is the slope of the line through P and Q.
Doubling the point P
When yP is not 0,
2P = R where
s = (3xP2 + a) / (2yP )
xR = s2 - 2xP and yR = -yP + s(xP - xR)
P + (-P) =O,
If P = (xP,yP) and yP =0, then P + P = 2P = O.
75
Elliptic Curve Groups over Zp


Zp = {0,1,…,p-1}
y2 mod p = (x3 + ax + b) mod p




Where a and b are in Zp, and x, y are also in Zp.
Addition with modular p.
Example p=23, Zp=Z23 ,y2 = x3 + x
Points lying on y2 = x3 + x:
(0,0) (1,5) (1,18) (9,5) (9,18) (11,10) (11,13) (13,5) (13,18)
(15,3) (15,20) (16,8) (16,15) (17,10) (17,13) (18,10) (18,13)
(19,1) (19,22) (20,4) (20,19) (21,6) (21,17)
Point (1, 5): X=1RHS=2, y2 = 2 mod 23  y = 5
Point (21, 6): X=21RHS=x3+x=213+21=(15 + 21)mod 23 = 13,
y2 = 13 mod 23  y = 6
76
y2 mod 23 = (x3 + x) mod 23
77




Points on Elliptic curve along with addition
operation form a group.
Given a point P (P  (x, 0)), consider
2P=P+P, 3P=2P+P, …., nP=(n-1)P+P,…
Given any n, it is easy to compute R=nP.
However given R, it is very difficult to find n,
such that nP=R.
This is called The Elliptic Curve Discrete
Logarithm Problem (ECDLP).
78
Many cryptosystems can be formed
based on Elliptic Curve

Example: Diffie-Hellman key exchange




Given elliptic curve E and a point P (public)
Alice selects an a, computes A=aP, sends A
to Bob
Bob selects a b, computes B=bP, sends B
to Bob
Then Alice can compute the key
K=aB=abP, similarly, Bob computes the
key K=bA=abP
79
“It is tough to make predictions, especially
about the future.”
-- Yogi Berra
80
X.509v3
1.Distinguished Name:
Root CA: single point of failure
2. Validity period
3. Public Key
Example: National CA/Univ of Windsor/CS/End User like
Chris Smith 2075
Policy of CA
Access Control through the certificate
Certificate revocation lists (CRLs)
Cross-certification is the black hole of PKI
81
CRL Problems





Not issued frequently enough to be effective
against an attacker
Expensive to distribute
Vulnerable to simple DOS attacks
Attacker can prevent revocation by blocking
CRL delivery
If a user caches a CRL, he may deal
with an outdated CRL.
82
CRL Problems


……2
Back-dated CRL can appear at any point in the future
Destroys the entire concept of nonrepudiation
Revoking self-signed certificates is hairy
when a Cert revokes itself, Applications may
– Accept the CRL as valid and revoke the certificate
– Reject the CRL as invalid since it was signed with a revoked certificate
– Crash
to provide timely revocation exacerbates the
problem
Example: 10M clients download a 1MB CRL issued once
a minute  ~150GB/s traffic

83
Online Certificate Status Protocol, OCSP
Reply is created on the spot in response
to the request
Ephemeral pseudo-CRL avoids CRL
validity period
 Problems:



Requires a signing operation for every query
CAs charge fees to issue a certificate (Most
expensive collection of bits in the world)
Revocation checks may also cost.
84
Identity-based PK Systems
85
Differences between
Identity-based System

and
a standard PK system
Different Methods of
Constructing a key
 Distributing a key
 Authenticating a key
 Using a key

Reference: 1. Liqun Chen,”Identity-based Cryptography”, HP
Laboratories, 2006,
http://www.sti.uniurb.it/events/fosad06/papers/Chenfosad06.pdf
2. A. Shamir. Identity-based cryptosystems and signature schemes.
In Advances in Cryptology - Crypto '84, Springer-Verlag LNCS
196, 47-53, 1984.
86
Public Key Infrastructure (PKI) System






Sender (Alice) requests the CA for the public key of
the Receiver (Bob).
Through an authenticated channel, CA sends the
public key (of Bob) certificate, signed by the private
key of CA.
Alice decrypts the certificate using the public key of
CA.
Alice encrypts her message using the public key of
Bob.
Alice sends the message to Bob through Internet
Bob gets his private key from CA through an
authenticated channel and decrypts the message.
87
Identity Based Encryption (IBE)





Alice uses the identity of Bob to create his
public key.
Alice encrypts her message using the public
key of Bob.
Alice sends the message to Bob through
Internet
Bob gets his private key from the Master Key
Generator by supplying to it his identity.
Bob decrypts the message by using his
private key.
88
Key Generator in IBE
Private Key
Identity
Private Key Generator
Master Key
89
IBE Schemes


Shamir’s paper 1984
Three IBE schemes in 2001






Sakai, Ohgishi and Kasahara
Boneh and Franklin
Cocks
Sakai and Kasahara in 2003
.
.
90
Identity





E-mail address
Photo
Phone number
Postal address
Role-based access based upon the role
of a person in his organization
91
Shamir’s Method:
IB Private key for Bob


Identity may be the digest of any data string
associated with Bob:
Thus ID = H([email protected])
Let the Master private and public keys be (d, n) and
(e,n) respectively.
Private key = SID = IDd mod n
For signing a message:
Choose r: a random number
Compute t = re mod n
Find f = H(t,m) where m = message
92
Shamir’s Method:
Verification of Signatures
s = SID.rf mod n
where SID = IDd mod n
Output Signatures: (s,t) and f is the signed message.
Verification of Signatures
Compute LHS = se
Compute RHS = ID. tH(t,m) mod n,
where f = H(t,m) and t = re mod n
 If LHS = RHS, the signature is acceptable.
PROOF:
LHS = se = IDd.e.rf.e mod n =ID. rf.e mod n
RHS = ID. re.f mod n
93
ISO/IEC 11770-3 Key Agreement Scheme






Developed by Guillou and Quisquater, based on
Shamir’s scheme
IDA and IDB :identities of Alice and Bob respectively.
Master Key Generator:
 private key: (d, n)
public key: (e, n)
e
 Two elements g and h such that g = h mod n
Master Key Generator: creates private keys for Alice
and Bob as follows:
d
SA = (1/IDA) mod n
SB = (1/IDB)d mod n
94
94
ISO/IEC 14888-2 Signature Scheme
Key Exchange
Alice selects a random number a and computes
tA = SA. ha mod n
and sends it to Bob.
 Bob selects a random number b and computes
tB = SB. hb mod n
and sends it to Alice.
 Both Alice and Bob are able to compute the common
key KAB as follows:
KAB =((tB)e. IDB)a = gab and KAB =((tA)e. IDA)b = gab

The common symmetric key can be used by Alice and
Bob to exchange messages.
95
Cock’s IBE Scheme
96
Cocks’s quadratic residues IBE scheme
 based on the hardness of the quadratic
residues problem, i.e.
2
 y : x = y mod n
 n = pq where p and q are two large
primes, like in RSA
 does not use pairing
Reference: C. Cocks. An identity-based encryption scheme based
on quadratic residues. In Proceedings of Cryptography and
Coding, LNCS 2260, pp. 360-363, Springer-Verlag, 2001
97
Cocks’s quadratic residues IBE scheme ...2


is quite fast
encrypts a message bit by bit, and it
requires log n bits of ciphertext per bit
of plaintext
Reference: C. Cocks. An identity-based encryption scheme based
on quadratic residues. In Proceedings of Cryptography and
Coding, LNCS 2260, pp. 360-363, Springer-Verlag, 2001.
98
Pairings in IBE

pairings, which have been used in
identity-based cryptography: the Weil
pairing and the Tate pairing and their
variants.
References: 1. P. Barreto, H. Kim, B. Lynn, and M. Scott, Efficient
algorithms for pairing-based cryptosystems, Proceedings of
CRYPTO 2002, LNCS 2442, pages 354–369, Springer-Verlag,
2002.
2. D. Boneh and M. Franklin. Identity based encryption from the
Weil pairing. In Advances in Cryptology - Crypto 2001, SpringerVerlag LNCS 2139, 213-229, 2001.
THANKS
100