Transcript first set

Prelude to Public-Key
Cryptography
Rocky K. C. Chang, February 2014
1
The next 2 sets of slides address
Secret key
functions
Secrecy
service
2
Public key
functions
Authentication
service
Hash
functions
Message
integrity service
Nonrepudiation
service
Outline
Motivations for public-key cryptography
Affine Cipher
Generalizing Affine Cipher to multiplicative groups.




Computing the multiplicative inverses using Euclidean
algorithms
The Chinese Remainder Theorem
Other useful Group Theory results




3
Multiplication modulo prime
Primitive elements
Public-key cryptography
Drawbacks of the symmetric key cryptosystems:



Require a secret key established before sending ciphertext.
Cannot be used for digital signatures.
Main ideas behind the public-key cryptosystems:



4
It is computationally infeasible to determine DK() given EK().
Therefore, EK() can be public and DK() must be private.
Public-key cryptography
Key people behind the public-key cryptography:



Diffie and Hellman
Rivest, Shamir, and Adleman
The RSA algorithm is based on the difficulty of factoring
large integers.
ElGamal, Elliptic Curve, and Diffie-Hellman are based on
the difficulty of solving the discrete logarithm problem.


5
The Affine Cipher
6
Recall that the Affine Cipher is:
Let M = C = Z26 = {0, 1, 2, …, 25}
K = (a, b), where a, b {0, 1, 2, …, 25}.
Encryption and decryption functions:





EK(m) = am + b mod 26
DK(c) = a-1(c  b) mod 26
EK(m) is not an one-to-one function for all a.



7
When a = 1, Affine Cipher is the same as a Shift Cipher.
Affine Cipher is still a special case of the Substitution Cipher.
EK(m) is not an one-to-one function for
all a.
Not all (a, b) can be used as keys.



E.g., a = 2 and b = 1: E(m) = 2m + 1 mod 26.
But E(0) = E(13) = 1.
For any c  Z26, the decryption is possible iff the congruence
am  c (mod 26) has a unique solution for m.




8
Decryption is possible iff there is a unique solution m in am + b  c
(mod 26) or am  c  b (mod 26).
Note that  b just shifts c to the left hand side by b, which gives the
same set of values for c.
Thus, decryption is possible iff there is a unique solution m in am  c
(mod 26).
The values of a: gcd(a,26) = 1.
The congruence am  c (mod 26) has a unique solution for
any c  Z26 iff gcd(a,26) = 1 (i.e., a and 26 are relative prime).


Assume that gcd(a,26) = d > 1.




Assume that gcd(a,26) = 1.





9
Without loss of generality, take c = 0.
Then am  0 (mod 26) has two solutions: m = 0 and m = 26/d.
The congruence does not have a unique solution.
Consider some m1 and m2 for which am1  am2 (mod 26) or a(m1m2) 
0 (mod 26).
That is, 26 | a(m1m2) (i.e., 26 divides a(m1m2)).
Since gcd(a,26) = 1, we have 26 | (m1m2).
By definition, m1  m2 (mod 26).
Therefore, a unique solution m  Z26.
What is the size of the key space?

How many a  Z26 for which gcd(a,26) = 1?



All odd numbers except for 13 (i.e., 12 of them).
Thus, the size of the key space = 1226 = 312.
Define a-1 to be the multiplicative inverse of a for which
aa-1  a-1a  1 (mod 26).
10
Inverses of a  Z26

Multiplicative inverses for the set of a for which gcd(a,26) = 1:








a
1
3
5
7
9
11
a-1
1
9
21
15
3
19







a
15
17
19
21
23
25
a-1
7
23
11
5
17
25
Multiplicative inverses do not exist for the set of a
for which gcd(a,26) ≠ 1.
11
Decryption function





c  am + b (mod 26)
am  c  b (mod 26)
Assuming that the a-1 exists, we have a-1(am)  a-1(c  b)
(mod 26)
The left side is a-1(am)  (a-1a)m  1m  m (mod 26).
Therefore, m = a-1(c  b) mod 26.
12
Multiplicative group
13
Abelian Group or Commutative Group

A group G is a set of numbers together with an
operation  that satisfies the following requirements:





14
(Closure) For all a, b  G, a  b  G.
(Associative) For all a, b, c  G, a  (b  c) = (a  b)  c.
(Identity) Exists some unique e  G such that for all a  G, a 
e = e  a = a. (e is the identity element)
(Inverse) For all a  G, there exists an a-1  G, such that a  a-1
= a-1  a = e. (a-1 is the inverse of a).
(Commutative) For all a, b  G, a  b = b  a.
For example,

The set of real numbers under addition is a (additive)
group.


The set of non-zero real numbers under multiplication is
a (multiplicative) group.



e = 0 and a-1 = -a.
e = 1 and a-1 = 1/a.
The set of integers under addition is a group, but the set
of integers under multiplication is not a group.
Zn = {0, 1, 2, …, n–1} under addition modulo n is a group.
15
Multiplicative group

Let Z*26 = {1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25} under
multiplication modulo 26 forms a group.


Z*26 is the set of residues modulo 26 that are relatively prime
to 26.
We can generalize the modulo 26 to any modulo p.


am  c (mod p) has a unique solution m  Zp for every c 
Zp iff gcd(a,p) = 1.
The number of integers in Zp that are relatively prime to p is
denoted by (p).


16
(26) = ?
There is a formula to compute (p).
Multiplicative group

Suppose a  Zp, a-1 exists iff gcd(a,p) = 1.



If a-1 exists, it is unique.
It is not difficult to prove that Z*p forms a group under
multiplication modulo p.
As a special case, if p is prime, then every nonzero
element of Zp has a multiplicative inverse.


17
Therefore, (p) = p – 1.
Z*p = Zp \ {0}.
How to compute the multiplicative
inverse?

Use the Euclidean algorithm to compute gcd(a,b).



E.g., gcd(108,42) = gcd(42,24) = gcd(24,18) = gcd(18,6) = 6.
E.g., gcd(75,28) = gcd(28,19) = gcd(19,9) = gcd(9,1) = 1.
Can determine whether a positive integer a < p has a multiplicative
inverse modulo p.
public static int gcd(int a, int b) {
int c;
while (a % b != 0) {
c = b;
//
b = a % b;
//
a = c;
//
}
return b;
//
} // end gcd
18
temporarily store b
update b, the second argument
update a, the first argument
note that b is the gcd value.
The Extended Euclidean algorithm


Use the Extended Euclidean algorithm to compute r, s, t,
such that sa + tb = r = gcd(a,b).
For example, a = 108, b = 42 (i.e., gcd(a,b) > 1),





19
108 = 242+24 (24 = a–2b)
42 = 124+18 (b=1(a–2b)+18 or -a+3b=18)
24 = 118+6 (a–2b=1(-a+3b)+6 or 2a–5b=6)
18 = 36+0
Therefore, 2a–5b=6 (s = 2, t = -5, and r = 6).
The Extended Euclidean algorithm

For example, a = 75, b = 28 (i.e., gcd(a,b) = 1),





20
75 = 228+19 (19 = a–2b)
28 = 119+9 (b=1(a–2b)+9 or -a+3b=9)
19 = 29+1 (a–2b=2(-a+3b)+1 or 3a–8b=1)
9 = 91+0
Therefore, 3a–8b=1 (s = 3, t = -8, and r = 1).
Compute the multiplicative inverse


Consider a  Zp and gcd(p,a) = 1.
From the Extended Euclid. Algorithm, we have sp + ta
= 1.



Reducing the above modulo p, we have ta  1 (mod p).
In other words, t is the multiplicative inverse of a. Note that it
is also unique.
E.g., for a =28 and Z75, a-1 = -8 mod 75 = 67.

21
Check aa-1 mod 75 = 1876 mod 75 = 1!
The Chinese Remainder Theorem
22
The Chinese Remainder Theorem

The CRT is a method of solving the followings for x,
where gcd(pi, pj) = 1 for i  j.






x  a1 (mod p1)
x  a2 (mod p2)
…
x  ar (mod pr),
The CRT asserts that there is a unique solution in {0, 1,
…, p1 … pr – 1}.
To see why, consider mapping x to x mod pi (called X).
23
For example,

Consider p1 = 5 p2 = 3, P = p1p2 = 15, and x  {0, 1, 2,
…, 14}.






X(0) = (0,0), X(1) = (1,1), X(2) = (2,2),
X(3) = (3,0), X(4) = (4,1), X(5) = (0,2),
X(6) = (1,0), X(7) = (2,1), X(8) = (3,2),
X(9) = (4,0), X(10) = (0,1), X(11) = (1,2),
X(12) = (2,0), X(13) = (3,1), X(14) = (4,2)
The mapping X(x) is bijective => a unique solution to


24
x  a1 (mod p1)
x  a2 (mod p2).
The Chinese Remainder Theorem

Suppose p1, …, pr are pairwise relatively prime, and a1, …, ar are
integers. Then the system of r congruences x  ai (mod pi) has a
unique solution modulo P = p1… pr, which is given by



x = a1P1y1 mod P + … + arPryr mod P,
where Pi = P/pi and yi = Pi-1 mod pi, i=1, …, r.
For example, (p1,p2,p3) = (7,11,13) and (a1,a2,a3)=(5,3,10).



25
P = 1001.
From the Extended Euclid. Algorithm, y1 = 5, y2 = 4, and y3 = 12.
From the CRT, x = ( 5(1113)5 + 3(713)4 + 10(711)12 ) mod
1001 = 894.
Multiplicative group modulo prime
26
Lagrange’s theorem

For a finite multiplicative group G under modulo p, define



E.g., for Z*26 = {1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25}, recall that
(p) = 12.





The order of G is (p) (i.e., the number of elements in G)
The order of an element g  G to be the smallest +ve integer n such that
gn mod p = 1.
The order of 1 is 1.
The order of 3 is 3, because 33 mod 26 = 1.
The order of 5 is 4, because 54 mod 26 = 1.
…
(Lagrange) Suppose G is a multiplicative group of order n, and
g  G. Then the order of g divides n.
27
Multiplicative group modulo prime

From the Lagrange’s theorem, we immediately have



If b  Z*p, then b(p)  1 (mod p).
If p is a prime and b  Z*p, then bp  b (mod p).
If p is prime, then Z*p is a cyclic group.



28
There exists at least an element g  Z*p having order equal to
(p) = p – 1.
Such element is called the primitive element modulo p.
E.g., for Z*7, 3 is a primitive, because 3i mod 7  1, i=1,…,5, and
37-1 mod 7 = 1.
Properties of the primitive elements

An element g is a primitive element modulo p iff gi, i = 0, 1, …,
p–2, generate Z*p. E.g., for p = 7







30 mod 7 = 1,
31 mod 7 = 3,
32 mod 7 = 2,
33 mod 7 = 6,
34 mod 7 = 4,
35 mod 7 = 5.
The order of an element a = gi is given by (p–1)/gcd(p–1,i).


29
Thus, a = gi is a primitive element iff gcd(p–1,i) = 1.
In other words, the number of primitive elements is (p–1).
For example,


For p = 7, p–1 = 6 = 23. Therefore, (6) = (21–21-1)(31–
31-1) = 2.
Test for primitive elements:






30
gcd(6,0) = 6
gcd(6,1) = 1  31 is a primitive element.
gcd(6,2) = 2
gcd(6,3) = 3
gcd(6,4) = 2
gcd(6,5) = 1  35 mod 7 = 5 is another primitive element.
A quicker method for testing for primitive
elements


Suppose that p is prime and a  Z*p. Then a is a primitive
element modulo p iff a(p–1)/q  1 (mod p) for all primes q such
that q | (p–1).
Back to p = 7, all primes, for which q | (p–1), are 2 and 3.

1 is clearly not a primitive element.

26/2  1 (mod 7).

36/2  6 (mod 7) and 36/3  2 (mod 7)  3 is a primitive element.

46/2  1 (mod 7).

56/2  6 (mod 7) and 56/3  4 (mod 7)  5 is a primitive element.
31
Conclusions

We have laid down some foundations for understanding
the public-key cryptography.




32
Affine Cipher
Multiplicative groups (Diffie-Hellman)
The Chinese Remainder Theorem (RSA)
Multiplicative groups modulo prime (Diffie-Hellman)
Acknowledgments

The notes are prepared mostly based on

33
D. Stinson, Cryptography:Theory and Practice, Chapman &
Hall/CRC, Second Edition, 2002.