Transcript Running Time of Euclidean Algorithm

RSA Encryption
Zeph Grunschlag
Copyright © Zeph Grunschlag,
2001-2002.
Agenda
RSA Cryptography

A useful and basically unbreakable method for
encoding messages
Needed for implementing RSA:





L13
Fast Exponentiation
Extended Euler’s Algorithm
Modular inverses
FLT (Fermat’s Little Theorem)
CRT (Chinese Remainder Theorem)
2
RSA Cryptography
Most internet shopping sites offer a “secure
connection” option that allows shoppers
to disclose personal information such as
credit card, address, etc. without fear
that a snoop on the communication will
be able to tell what’s happening:
Mr. Snoop Snoopy Snoop

…#24@ &3240 msP28*…
L13
…Last Name: Smiley…

3
RSA Cryptography
There are several encryption methods. Perhaps
the simplest “unbreakable” system is the RSA
(Rivest, Shamir, Adleman) system.
FrogsRUs.com provides a large number N (e.g.
1024 bit binary number) and an encryption
exponent e. Usually the
N, e
server communicates
these directly to web
browser behind the
scenes.
L13
4
RSA Cryptography
Mr. Smiley’s browser then converts his
message into numbers, as in the modular
encryption that we saw before. The
letters are then put together into number
blocks with each block less than N. Mr.
Smiley’s browser exponentiates each
number block by the exponent e modulo
N and broadcasts these garbled
blocks back to FrogsRUs.com
L13

5
RSA Cryptography
N = 4559, e = 13.
m e mod N
Smiley Transmits: “Last name Smiley”
L13

6
RSA Cryptography
N = 4559, e = 13.
m e mod N

Smiley Transmits: “Last name Smiley”
 L A S T N A M E S M I L E Y
L13
7
RSA Cryptography
N = 4559, e = 13.
m e mod N

Smiley Transmits: “Last name Smiley”
 L A S T N A M E S M I L E Y

L13
1201 1920 0014 0113 0500 1913 0912 0525
8
RSA Cryptography
N = 4559, e = 13.
m e mod N

Smiley Transmits: “Last name Smiley”
 L A S T N A M E S M I L E Y


L13
1201 1920 0014 0113 0500 1913 0912 0525
120113 mod 4559, 192013 mod 4559, …
9
RSA Cryptography
N = 4559, e = 13.
m e mod N

Smiley Transmits: “Last name Smiley”
 L A S T N A M E S M I L E Y



L13
1201 1920 0014 0113 0500 1913 0912 0525
120113 mod 4559, 192013 mod 4559, …
2853 0116 1478 2150 3906 4256 1445 2462
10
RSA Cryptography
FrogsRUs.com receives the encrypted
blocks n = m e mod N. They have a
private decryption exponent d which
when applied to n recovers the original
blocks m : (m e mod N )d mod N = m
For N = 4559, e = 13 the
decryptor d = 3397.
L13
11
RSA Cryptography
N = 4559, d = 3397
 2853 0116 1478 2150
L13
3906 4256 1445 2462
12
RSA Cryptography
N = 4559, d = 3397
 2853 0116 1478 2150 3906 4256 1445
 28533397 mod 4559, 01163397 mod 4559, …
L13
2462
13
RSA Cryptography
N = 4559, d = 3397
 2853 0116 1478 2150 3906 4256 1445
 28533397 mod 4559, 01163397 mod 4559, …
 1201 1920 0014 0113 0500 1913 0912
L13
2462
0525
14
RSA Cryptography
N = 4559, d = 3397
 2853 0116 1478 2150 3906 4256 1445
 28533397 mod 4559, 01163397 mod 4559, …
 1201 1920 0014 0113 0500 1913 0912
L13
2462
0525
15
RSA Cryptography
N = 4559, d = 3397
 2853 0116 1478 2150 3906 4256 1445 2462
 28533397 mod 4559, 01163397 mod 4559, …
 1201 1920 0014 0113 0500 1913 0912 0525
 LA S T N A M E S M I L E Y
L13
16
RSA Cryptography
The key to security of RSA cryptosystem:
The public key (N,e) must be such that
it is very difficult for Snoop Snoopy
Snoop to figure out what d is, yet very
simple for FrogsRUs.com to come up
with.
L13
17
Fast Modular Exponentiation
In order to implement RSA exponentiation
relative some modulo needs to be done
a lot. So this operation better be
doable, and fast.
Q: How is it even possible to compute
28533397 mod 4559 ? After all, 28533397
has approximately 3397·4 digits!
L13
18
Fast Modular Exponentiation
A: By taking the mod after each
multiplication.
EG, a more lucid example:
233 mod 30 
L13
19
Fast Modular Exponentiation
A: By taking the mod after each
multiplication.
EG, a more lucid example:
233 mod 30  -73 (mod 30)
L13
20
Fast Modular Exponentiation
A: By taking the mod after each
multiplication.
EG, a more lucid example:
233 mod 30  -73 (mod 30)
 (-7)2 ·(-7) (mod 30)
L13
21
Fast Modular Exponentiation
A: By taking the mod after each
multiplication.
EG, a more lucid example:
233 mod 30  -73 (mod 30)
 (-7)2 ·(-7) (mod 30) 49 · (-7) (mod 30)
L13
22
Fast Modular Exponentiation
A: By taking the mod after each
multiplication.
EG, a more lucid example:
233 mod 30  -73 (mod 30)
 (-7)2 ·(-7) (mod 30) 49 · (-7) (mod 30)
 19·(-7) (mod 30)
L13
23
Fast Modular Exponentiation
A: By taking the mod after each
multiplication.
EG, a more lucid example:
233 mod 30  -73 (mod 30)
 (-7)2 ·(-7) (mod 30) 49 · (-7) (mod 30)
 19·(-7) (mod 30)  -133 (mod 30)
L13
24
Fast Modular Exponentiation
A: By taking the mod after each
multiplication.
EG, a more lucid example:
233 mod 30  -73 (mod 30)
 (-7)2 ·(-7) (mod 30)  49 · (-7) (mod 30)
 19·(-7) (mod 30)  -133 (mod 30)
 17 (mod 30)
L13
25
Fast Modular Exponentiation
Therefore, 233 mod 30 = 17.
Q: What if had to figure out 2316 mod 30.
Same way tedious: need to multiply 15
times. Is there a better way?
L13
26
Fast Modular Exponentiation
A: Better way. Notice that 16 = 2·2·2·2 so that
2316 = 232·2·2·2 = (((232)2)2)2
Therefore:
2316 mod 30
L13
27
Fast Modular Exponentiation
A: Better way. Notice that 16 = 2·2·2·2 so that
2316 = 232·2·2·2 = (((232)2)2)2
Therefore:
2316 mod 30  (((-72)2)2)2 (mod 30)
L13
28
Fast Modular Exponentiation
A: Better way. Notice that 16 = 2·2·2·2 so that
2316 = 232·2·2·2 = (((232)2)2)2
Therefore:
2316 mod 30  (((-72)2)2)2 (mod 30)
 (((49)2)2)2 (mod 30)
L13
29
Fast Modular Exponentiation
A: Better way. Notice that 16 = 2·2·2·2 so that
2316 = 232·2·2·2 = (((232)2)2)2
Therefore:
2316 mod 30  (((-72)2)2)2 (mod 30)
 (((49)2)2)2 (mod 30)  (((-11)2)2)2 (mod 30)
L13
30
Fast Modular Exponentiation
A: Better way. Notice that 16 = 2·2·2·2 so that
2316 = 232·2·2·2 = (((232)2)2)2
Therefore:
2316 mod 30  (((-72)2)2)2 (mod 30)
 (((49)2)2)2 (mod 30)  (((-11)2)2)2 (mod 30)
 ((121)2)2 (mod 30)
L13
31
Fast Modular Exponentiation
A: Better way. Notice that 16 = 2·2·2·2 so that
2316 = 232·2·2·2 = (((232)2)2)2
Therefore:
2316 mod 30  (((-72)2)2)2 (mod 30)
 (((49)2)2)2 (mod 30)  (((-11)2)2)2 (mod 30)
 ((121)2)2 (mod 30)  ((1)2 )2 (mod 30)
L13
32
Fast Modular Exponentiation
A: Better way. Notice that 16 = 2·2·2·2 so that
2316 = 232·2·2·2 = (((232)2)2)2
Therefore:
2316 mod 30  (((-72)2)2)2 (mod 30)
 (((49)2)2)2 (mod 30)  (((-11)2)2)2 (mod 30)
 ((121)2)2 (mod 30)  ((1)2 )2 (mod 30)
 (1)2 (mod 30)
L13
33
Fast Modular Exponentiation
A: Better way. Notice that 16 = 2·2·2·2 so that
2316 = 232·2·2·2 = (((232)2)2)2
Therefore:
2316 mod 30  (((-72)2)2)2 (mod 30)
 (((49)2)2)2 (mod 30)  (((-11)2)2)2 (mod 30)
 ((121)2)2 (mod 30)  ((1)2 )2 (mod 30)
 (1)2 (mod 30)  1(mod 30)
Which implies that 2316 mod 30 = 1.
Q: How ‘bout 2325 mod 30 ?
L13
34
Fast Modular Exponentiation
A: The previous method of repeated squaring
works for any exponent that’s a power of 2.
25 isn’t. However, we can break 25 down as a
sum of such powers: 25 = 16 + 8 + 1. Apply
repeated squaring to each part, and multiply
the results together. Previous calculation:
238 mod 30 = 2316 mod 30 = 1
Thus: 2325 mod 30  2316+8+1 (mod 30) 
L13
35
Fast Modular Exponentiation
A: The previous method of repeated squaring
works for any exponent that’s a power of 2.
25 isn’t. However, we can break 25 down as a
sum of such powers: 25 = 16 + 8 + 1. Apply
repeated squaring to each part, and multiply
the results together. Previous calculation:
238 mod 30 = 2316 mod 30 = 1
Thus: 2325 mod 30  2316+8+1 (mod 30) 
2316·238·231 (mod 30)
L13
36
Fast Modular Exponentiation
A: The previous method of repeated squaring
works for any exponent that’s a power of 2.
25 isn’t. However, we can break 25 down as a
sum of such powers: 25 = 16 + 8 + 1. Apply
repeated squaring to each part, and multiply
the results together. Previous calculation:
238 mod 30 = 2316 mod 30 = 1
Thus: 2325 mod 30  2316+8+1 (mod 30) 
2316·238·231 (mod 30)  1·1·23 (mod 30)
Final answer: 2325 mod 30 = 23
L13
37
Fast Modular Exponentiation
Q: How could we have figured out the
decomposition 25 = 16 + 8 + 1 from
the binary (unsigned) representation of
25?
L13
38
Fast Modular Exponentiation
A: 25 = (11001)2 This means that
25 = 1·16+1·8+0·4+0·2+1·1 = 16+8+1
Can tell which powers of 2 appear by
where the 1’s are. This follows from
the definition of binary representation.
L13
39
Fast Modular Exponentiation
Pseudocode
fastExponentiation(integer m, pos. integers e, N)
unun-1 un-2 … u2 u1 u0 = representInBinary(e)
squarePower0= m mod N
for( i = 0 to n-1)
squarePoweri+1 = squarePoweri 2 mod N
power = 1
for(i = 0 to n)
if (ui == 1 )
power = power · squarePoweri mod N
return power
L13
40
Modular Inverses
Recall the simple encryption function
f (a) = (3a + 9) mod 26
We made the claim that an inverse function is
given by:
g (a) = (9a – 3) mod 26
Check this: g (f (a ))  g(3a+9) (mod 26)
 9(3a+9)-3 (mod 26)  27a+81-3 (mod 26)
 27a+78 (mod 26)  a (mod 26). So for a in
the range [0,25] we have g (f (a )) = a and
so g and f are inverses of each other.
L13
41
Modular Inverses
How could one have inverted f methodically?
Do simpler example: f (a ) = 3a mod 26
Look for constant x and an inverse of the form:
g(a ) = xa
Then condition g(f (a ))  a (mod 26) gives:
g(f (a ))  x·3a (mod 26)  a (mod 26)
If we can solve this for a=1, it will work for all
other x as well. So plug in a=1 to get:
3x  1 (mod 26)
I.e. we wish to find an inverse of 3 modulo 26.
L13
42
Modular Inverses
DEF: The inverse of e modulo N is the
number d between 1 and N-1 such that
de  1 (mod N)
if such a number exists.
Q: What is the inverse of 3 modulo 26?
L13
43
Modular Inverses
A: 9 because 9·3 = 27  1 (mod 26).
Q: What is the inverse of 4 modulo 8?
L13
44
Modular Inverses
A: Trick Question! No inverse can exist
because 4x is always 0 or 4 modulo 8!
THM1: e has an inverse modulo N if and only
if e and N are relatively prime.
This will follow from the following useful fact.
THM2: If a and b are positive integers, the gcd
of a and b can be expressed as an integer
combination of a and b. I.e., there are
integers s,t for which
gcd(a,b) = sa + tb
L13
45
Modular Inverses
Example
5·14 - 3·23 =1 implies:
gcd(14,23) = 1

Any number dividing both 14 and 23 must divide 1
The inverse of 14 modulo 23 is 5


5·14 =1+ 3·23
5·14  1 (mod 23)
“An” inverse of 23 modulo 14 is -3




L13
-3·23 =1- 5·14
-3·23  1 (mod 14)
11·23  1 (mod 14)
“The” inverse is 11
46
Modular Inverses
Proof of THM1 using THM2:
If an inverse d exists for e modulo N, we
have de  1 (mod N) so that for some k,
de = 1 +kN, so 1 = de – kN. This
equation implies that any number
dividing both e and N must divide 1, so
must be 1, so e,N are relatively prime.
L13
47
Modular Inverses
On the other hand, suppose that e,N are
relatively prime. Using THM2, write
1 = se + tN. Rewrite this as se = 1-tN.
Evaluating both sides mod N gives
se  1 (mod N) .
Therefore s is seemingly the inverse e
except that it may be in the wrong
range so set d = s mod N.
•
L13
48
Extended Euclidean Algorithm
A constructive version of THM2 which gives s
and t will give explicit inverses. This is what
the extended Euclidean algorithm does.
The extended Euclidean algorithm works the
same as the regular Euclidean algorithm
except that we keep track of more details –
namely the quotient q = x/y in addition to the
remainder r = x mod y. This allows us to
backtrack and write the gcd(a,b) as a linear
combination of a and b.
L13
49
Extended Euclidean Algorithm
Examples
gcd(33,77)
Step
x = qy + r
0
-
L13
x
y
gcd = ax+by
33 77
50
Extended Euclidean Algorithm
Examples
gcd(33,77)
Step
x = qy + r
0
-
1
L13
x
y
gcd = ax+by
33 77
33=0·77+33 77 33
51
Extended Euclidean Algorithm
Examples
gcd(33,77)
Step
x = qy + r
0
-
x
y
33 77
1
33=0·77+33 77 33
2
77=2·33+11 33 11
L13
gcd = ax+by
52
Extended Euclidean Algorithm
Examples
gcd(33,77)
Step
x = qy + r
0
-
x
y
33 77
1
33=0·77+33 77 33
2
77=2·33+11 33 11
3
33=3·11+0 11 0
L13
gcd = ax+by
53
Extended Euclidean Algorithm
Examples
gcd(33,77)
Step
x = qy + r
0
-
x
y
33 77
1
33=0·77+33 77 33
2
77=2·33+11 33 11
3
33=3·11+0 11 0
L13
gcd = ax+by
Solve for r. Plug it in.
54
Extended Euclidean Algorithm
Examples
gcd(33,77)
Step
x = qy + r
0
-
x
y
gcd = ax+by
33 77
1
33=0·77+33 77 33
2
77=2·33+11 33 11
11 = 77 - 2·33
3
33=3·11+0 11 0
Solve for r. Plug it in.
L13
55
Extended Euclidean Algorithm
Examples
gcd(33,77)
Step
x = qy + r
0
-
x
y
gcd = ax+by
33 77
11= 77 - 2·(33-0·77)
1
33=0·77+33 77 33
2
77=2·33+11 33 11
11 = 77 - 2·33
3
33=3·11+0 11 0
Solve for r. Plug it in.
=
Therefore
s = -2 and t = 1
L13
-2·33 + 1·77
56
Extended Euclidean Algorithm
Examples
gcd(244,117):
Step
x = qy + r
0
-
L13
x
y
gcd = ax+by
244 117
57
Extended Euclidean Algorithm
Examples
gcd(244,117):
Step
0
1
L13
x = qy + r
x
y
gcd = ax+by
244 117
244=2·117+10 117 10
-
58
Extended Euclidean Algorithm
Examples
gcd(244,117):
Step
0
1
2
L13
x = qy + r
x
y
gcd = ax+by
244 117
244=2·117+10 117 10
117=11·10+7 10
7
-
59
Extended Euclidean Algorithm
Examples
gcd(244,117):
Step
0
1
2
3
L13
x = qy + r
x
y
gcd = ax+by
244 117
244=2·117+10 117 10
117=11·10+7 10
7
10=7+3
7
3
-
60
Extended Euclidean Algorithm
Examples
gcd(244,117):
Step
0
1
2
3
4
L13
x = qy + r
x
y
gcd = ax+by
244 117
244=2·117+10 117 10
117=11·10+7 10
7
10=7+3
7
3
7=2·3+1
3
1
-
61
Extended Euclidean Algorithm
Examples
gcd(244,117):
Step
0
1
2
3
4
5
L13
x = qy + r
x
y
gcd = ax+by
244 117
244=2·117+10 117 10
117=11·10+7 10
7
10=7+3
7
3
7=2·3+1
3
1
3=3·1+0
1
0
-
62
Extended Euclidean Algorithm
Examples
gcd(244,117):
Step
0
1
2
3
4
5
L13
x = qy + r
x
y
gcd = ax+by
244 117
244=2·117+10 117 10
117=11·10+7 10
7
10=7+3
7
3
1=7-2·3
7=2·3+1
3
1
3=3·1+0
1
0 Solve for r. Plug it in.
-
63
Extended Euclidean Algorithm
Examples
gcd(244,117):
Step
0
1
2
x = qy + r
x
y
gcd = ax+by
244 117
244=2·117+10 117 10
117=11·10+7 10
7
-
3
10=7+3
7
3
1=7-2·(10-7)
= -2·10+3·7
4
5
7=2·3+1
3
1
1
0
1=7-2·3
L13
3=3·1+0
Solve for r. Plug it in.
64
Extended Euclidean Algorithm
Examples
gcd(244,117):
Step
0
1
2
x = qy + r
x
y
gcd = ax+by
244 117
244=2·117+10 117 10
-
117=11·10+7
10
7
1=-2·10+3·(117-11·10)
= 3·117-35·10
3
10=7+3
7
3
1=7-2·(10-7)
= -2·10+3·7
4
5
7=2·3+1
3
1
1
0
1=7-2·3
L13
3=3·1+0
Solve for r. Plug it in.
65
Extended Euclidean Algorithm
Examples
gcd(244,117):
Step
x = qy + r
0
-
1
2
x
gcd = ax+by
244 117
244=2·117+10 117
117=11·10+7
y
10
10
1= 3·117-35·(244- 2·117)
=
-35·244+73·117
7
1=-2·10+3·(117-11·10)
= 3·117-35·10
3
10=7+3
7
3
1=7-2·(10-7)
= -2·10+3·7
4
5
7=2·3+1
3
1
1
0
1=7-2·3
L13
3=3·1+0
Solve for r. Plug it in.
66
Extended Euclidean Algorithm
Examples inverse of 244
modulo 117
gcd(244,117):
Step
x = qy + r
0
-
1
2
x
gcd = ax+by
244 117
244=2·117+10 117
117=11·10+7
y
10
10
1= 3·117-35·(244- 2·117)
=
-35·244+73·117
7
1=-2·10+3·(117-11·10)
= 3·117-35·10
3
10=7+3
7
3
1=7-2·(10-7)
= -2·10+3·7
4
5
7=2·3+1
3
1
1
0
1=7-2·3
L13
3=3·1+0
Solve for r. Plug it in.
67
Extended Euclidean Algorithm
Summary: Extended Euclidean algorithm
works by keeping track of how remainder
r results from dividing x by y. Last such
equation gives gcd in terms of last x and
y. By repeatedly inserting r into the last
equation, one can get the gcd in terms of
bigger and bigger values of x,y until at
the very top is reached, which gives the
gcd in terms of the inputs a,b.
L13
68
Exponential Inverses
Finding modular inverses is good enough
for decoding simple modular
cryptography. However, in RSA
encryption consists of exponentiating
modulo N, i.e. m e mod N. We want to
find a different exponent d based on e
and N which will give us back m, i.e. we
want m de mod N =m. In other words,
we want an exponential inverse for e
modulo N.
L13
69
Exponential Inverses.
Prime Modulii
To tackle the general problem, start first with
the case of N a prime number.
Exponentiation modulo a prime number is
well understood.
EG: Consider exponentiating 3 modulo 7:
1.
2.
3.
4.
5.
6.
L13
31 mod
32 mod
33 mod
34 mod
35 mod
36 mod
7
7
7
7
7
7
=
=
=
=
=
=
3
2
6
4
5
1
7. 37 mod 7 = 3
8. 38 mod 7 = 2
9. 39 mod 7 = 6
10.310 mod 7 = 4
11.311 mod 7 = 5
12.312 mod 7 = 1
70
Exponential Inverses.
Prime Modulii
Exponentiating to the p -1 power results in 1.
Therefore, any further exponentiation
results in a cycling, with repetitions
occurring every 6 exponentiations.
Fermat’s Little Theorem says that this effect
happens for all rel-prime numbers under
prime modulus:
1.
2.
3.
4.
5.
6.
L13
31 mod 7
32 mod 7
33 mod 7
34 mod 7
35 mod 7
36 mod 7
=
=
=
=
=
=
3
2
6
4
5
1
7. 37 mod 7 = 3
8. 38 mod 7 = 2
9. 39 mod 7 = 6
10.310 mod 7 = 4
11.311 mod 7 = 5
12.312 mod 7 = 1
71
Fermat’s
Little
Theorem
THM (FLT): Suppose that p is a prime number.
If a is not divisible by p then
a p-1  1 (mod p) .
Furthermore, all numbers satisfy
a p  a (mod p) .
EG: Compute 9100 mod 17:
p =17, so p-1 = 16. 100 = 6·16+4. Therefore,
9100=96·16+4=(916)6(9)4 . So mod 17 we have
9100  (916)6(9)4 (mod 17)  (1)6(9)4 (mod 17)
 (81)2 (mod 17)  (-4)2 (mod 17)  16
L13
72
Exponential Inverses.
Prime Modulii
COR: If e is relatively prime to p –1, where p is
prime, then its exponential inverse modulo p
exists and is the inverse of d modulo p-1.
Proof. Supposing de  1 (mod p-1). Then for
some k, de = 1+k (p-1). So if a is any
number not divisible by p, FLT implies:
ade  a1+k(p-1) (mod p)  a (mod p)
In other words, exponentiating by de doesn’t
change numbers, modulo p, so by definition,
d and e are exponential inverses.
•
L13
73
Exponential Inverses.
Prime Modulii
EG: Find the exponential inverse of 3
modulo 11.
p =11, so p-1 = 10. The inverse of 3
modulo 10 is 7, which is the answer.
L13
74
Exponential Inverses.
Next Step
Q: Why don’t we just use a prime
number as our base N since it’s so easy
to find the decryptor d ?
L13
75
Exponential Inverses.
Next Step
A: Because it’s so easy to find the decryptor d!
Recall, this is a public cryptosystem. The key
(N,e) is available to all customers. There is
no way of restricting customers to the
benevolent non-hackers. If a prime N were
used, Mr. Snoop could simple shop once,
analyze the communication stream to find out
what N and e were, and decrypt other
customer’s communications by finding the
inverse of e modulo N-1.
RSA uses next simplest case: N = pq –a
product of two (different) primes.
L13
76
Exponential Inverses.
Next Step
If we know what p and q are, then we’ll
be able to find the exponential inverse.
if
But that’s a big
. Factoring large
numbers is a surprisingly difficult
problem. No-one knows how to do this
in polynomial time, except on
theoretical Quantum Computers.
L13
77
Exponential Inverses.
Product of Two Primes
However, FrogsRUs.com is the one
coming up with N, so it knows what p
and q are. FrogsRUs would like to
make sure that it knows how to
decrypt. So let’s see how to do this.
We need one more important number
theory fact:
L13
78
Chinese Remainder Theorem
Old Folk Tale: Chinese Emperor used to count
his army by giving a series of tasks.
1. All troops should form groups of 3. Report
back the number of soldiers that were not
able to do this.
2. Now form groups of 5. Report back.
3. Now form groups of 7. Report back.
4. Etc.
At the end, if product of all group numbers is
sufficiently large, can ingeniously figure out
how many troops.
L13
79
Chinese Remainder Theorem
L13
80
Chinese Remainder Theorem
mod 3:
N mod 3 = 1
L13
81
Chinese Remainder Theorem
mod 5:
N mod 5 = 2
L13
82
Chinese Remainder Theorem
mod 7:
N mod 7 = 2
L13
83
Chinese Remainder Theorem
Secret inversion formula (for N < 105 = 3·5·7):
N  a (mod 3)
N  b (mod 5)
N  c (mod 7)
Implies that N = (-35a + 21b + 15c) mod 105.
So in our case a = 1, b = 2, c = 2 gives:
N = (-35·1 + 21·2 + 15·2) mod 105
= (-35 + 42 + 30) mod 105
= 37 mod 105
= 37
L13
84
Chinese Remainder Theorem
How did I come up with the secret formula?
For any x, a, b, and c satisfying
x  a (mod 3)
x  b (mod 5)
x  c (mod 7)
Chinese Remainder Theorem says that this is
enough information to uniquely determine
x modulo 3·5·7. Proof, gives an algorithm for
finding x –i.e. the secret formula.
L13
85
Chinese Remainder Theorem
Example
1. Find three numbers l,m,n with following
properties



l  1(mod 3), l  0(mod 5), l  0(mod 7)
m0(mod 3), m 1(mod 5), m 0(mod 7)
n 0(mod 3), n  0(mod 5), n  1(mod 7)
2. Then y = al+bm +cn [secret formula] satisfies



y  al+bm +cn (mod 3)
a·1+0 + 0 (mod 3)  a (mod 3)
Similarly, y  b (mod 5)
Similarly, y  c (mod 7)
3. This will imply x  y (mod 3·5·7)
L13
86
Chinese Remainder Theorem
Example
Find three numbers l,m,n: Standard trick.
EG, to find l :
a) Multiply together all modulii different from 3.
Result: 5·7 = 35
b) Find an inverse of this number mod 3: In
this case it’s easy. 35  2(mod 3) so find an
inverse of 2 [2 or anything congruent to
2(mod 3)]. Practice shows that should
choose inverse of smallest magnitude: –1.
c) l is the product of (a) and (b): l = -35
l is 0 mod 5 and 7 since it’s divisible by 5·7. But
(c) guarantees that it’s 1 modulo 3!
L13
87
Chinese Remainder Theorem
Example
Similarly, m = 21 and n = 15. So our
solution to all three congruences is:
x = -35a + 21b + 15c
If we want to guarantee a solution
between 0 and 104, just compute
x mod 105 .
The same tricks can be generalized to
prove:
L13
88
Chinese Remainder Theorem
THM (CRT): Let m1, m2, … , mn be pairwise
relatively prime positive integers. Then there
is a unique solution x in [0,m1·m2···mn-1] to
the system of congruences:
x  a1 (mod m1 )
x  a2 (mod m2 )
x  an (mod mn )
L13
89
RSA Cryptosystem
Final Piece
Now we can define how to find the
exponential inverse modulo N=pq and
use CRT to prove the method correct.
THM: Given e and distinct prime numbers
p,q. Suppose that e is relatively prime
to (p-1)(q-1). Then the exponential
inverse of e is the inverse of e modulo
(p-1)(q-1).
L13
90
RSA Cryptosystem
Final Piece
EG: e=5,p=5, q=7. Find the inverse of 5
modulo (5-1)(7-1) = 24. 5 is its own
inverse since 5·5=25 is 1 mod 24. So the
theorem states that any number m should
satisfy m 25  m (mod 35).
Try for example m = 3, using the fact that
25 is 11001 in binary:
1. 31 mod 35 = 3
6. 325 mod 35
= 316+8+1 mod 35
2. 32 mod 35 = 9
= 11·16·3 mod 35
3. 34 mod 35 = 11
= 176·3 mod 35
4. 38 mod 35 = 16
= 1·3 mod 35 91
=3
L13
5. 316 mod 35 = 11
RSA Cryptosystem
Proof of Decryption
Proof that d is inverse of e mod (p-1)(q-1):
We can therefore find k such that
de = 1+k (p-1)(q-1).
Does mde equal itself modulo N = pq ?
mde  m 1+k(p-1)(q-1) (mod pq).
 m 1·m k(p-1)(q-1) (mod pq)
 m ·m k(p-1)(q-1) (mod pq)
L13
92
RSA Cryptosystem
Proof of Decryption
mde  m ·m k(p-1)(q-1) (mod pq)
So mod p:
mde  m·(m p-1) k(q-1)(mod p)
If m relatively prime to p apply FLT:
mde  m·(1) k(q-1)(mod p)  m (mod p)
Otherwise, m  0 (mod p) so that
mde  0de  0  m (mod p)
Either case  mde  m (mod p).
Similar argument: mde  m (mod q).
L13
93
RSA Cryptosystem
Proof of Decryption
So we have the system of congruences:
mde  m (mod p)
mde  m (mod q)
Setting x = mde . CRT states that
x  m (mod p)
x  m (mod q)
has a unique solution (mod pq). But another
apparent solution is x = m. Therefore:
mde  m (mod pq) •
L13
94