Transcript Why Pierre de Fermat Would be a Billionaire Today

Why Pierre de
Fermat Would
be a Billionaire
Today
Lecture Notes 6
SYCS 653 – Fall 2009
1
Or, How
Cryptology Will
Affect Us All
-- Asymmetric Crypto
• Wayne Patterson
• Senior Fellow,
• The Graduate School
• Howard University
• SYCS 653, Howard University
• Fall 2009
2
Public-Key Cryptology
• Despite the pluses
or minuses of DES,
one problem DES
can never solve is
the “key
management
problem.”
• 6 users, (6  5)/2
= 15 keys
• 1000 users (1000 
999)/2 = 499,500
keys
3
The PKC Model
• For each user, choose a key ki = (kpi , ksi
), i=1, ..., 1000. In a system-wide public
directory, list all of the “public” keys kpi,
i=1, ..., 1000. Then, to send a message m
to user j, select the public key, kpi, and
apply the encryption transformation
• c = T(kpi , m).
• Send the ciphertext, c.
• Only user j has the rest of the key
necessary to compute:
• T( (kpi, ksi) , c ) = m.
4
The PKC Solution to Key
Management
• Thus, rather than having to manage
the secret distribution of O(n2) keys
in a network of n users, only n keys
are required, and they need not be
distributed secretly.
• Furthermore, the public-key concept
could also be used for the
authentication of messages in a way
that a “secret-key” system could not
address.
5
Authentication
• Consider a cryptosystem based on the traditional
“secret-key” approach. Consider also that it is used
for funds transfer in a banking network. One day the
system manager receives a message from X. The
manager decrypts the message using the secret key
agreed upon by X and the manager. The message
reads, “transfer $1,000,000 from my account to the
system manager’s account.” The manager dutifully
does so.
• X complains to the authorities, saying that the
message was a forgery, sent by the manager
himself(herself). The system manager, when reached
for comment by long distance telephone from Tahiti,
says that the message was authentic and that X had
recanted his desire to make the transfer.
6
Authentication
• Since both X and the manager had to
know the secret key, there is no way,
using the cryptosystem, to resolve the
dispute.
• However, a public-key cryptosystem could
have resolved the issue. Suppose that, in
addition to the message, every
transmission in the network is required to
be “signed,” that is, to contain a trailer
encrypted using X’s public key. Then, this
requirement would carry with it the ability
to authenticate X’s message, since only X,
knowing the rest of the key, would be able7
to decrypt the trailer.
Can We Devise a PKC?
• Therefore, if we could devise a PKC,
it would certainly have most
desirable features. But many
questions remain to be asked. First
of all, can we devise a PKC? What
should we look for? Second, if we
can find one, will it be secure? Will it
be efficient?
• For now, we will consider only the
general parameters of finding PKCs.
8
Factoring
• From the earlier description, we need to
find functions that are “one-way,” that is,
that enable an efficient computation
sufficient for encryption, but whose
inverses are cryptanalytically very difficult
to find.
• The example we will study involves the
ease of multiplying numbers together
combined with the difficulty of finding the
original factors, given a product.
9
Who is Pierre de Fermat?
• French mathematician
of the 17th century
(1601-1665)
• purchased the offices
of councillor at the
parliament in
Toulouse
• This allowed him to
change his name from
“Pierre Fermat” to
“Pierre de Fermat” (!)
• Pioneer in geometry
and number theory
10
Fermat’s Last Theorem
– (9 + 16 = 25)
• 52 + 122 = 132
– (25 + 144 = 169)
• 72 + 242 + 252
– (49 + 576 = 625)
• Is there an
example for n > 2
where
• xn + yn = zn ???
I have discovered a truly remarkable proof which this
margin is too small to contain.
• 32 + 42 = 52
xn + yn = zn
n>2
11
The 323-Year Marginalia
• Fermat’s marginal
comments led to many,
many futile efforts to
solve his “Last Theorem”
• Finally solved in 1993 by
Andrew Wiles =>
• Saudi Arabia awarded
Wiles a $500,000 prize
• Who says math doesn’t
pay?
• I could prove it now --in text, it takes 1,000
pages to provide the
complete proof
12
The Little Fermat Theorem
• Prime numbers are • The “Little Fermat”
those with no proper theorem says that
if I take any
divisors, e.g. 2, 3,
number, raise it to
5, …, 13, 17,..., 23,
a power (n), and
29, ..
divide the result by
n … I will get a
• For the product of
remainder of 1.
two prime numbers, • In mathematical
p, q, there is a
notation,
function (n) = (p- • a(n) (mod n) = 1.
1)  (q-1)
13
The RSA Cryptosystem
• About twenty years ago, three computer
scientists, Ron Rivest, Adi Shamir, and
Len Adleman, developed a “public-key”
cryptosystem that they called the RSA
cryptosystem (wonder why ???)
• It is based entirely on the Little Fermat
theorem
• If Pierre de Fermat only could’ve gotten
royalties, he could have bought all of
Toulouse.
14
What is the RSA
Cryptosystem?
• Short enough that RSA
Security has put it on a TShirt =>
• Take two prime numbers
(of 200 digits), multiply n
= pq
• Find e and d such that
their product gives a
remainder of 1 when
divided by (p-1)(q-1)
• To encrypt, raise the
message m to the power e
(mod n)
• To decrypt, raise the
cipher c to the power d
(mod n)
15
Why You Should Be Skeptical …
• 1. Can we find prime numbers p, q of
200 digits?
• 2. Can we multiply them together?
• 3. Can we find an e such that GCD(e,
φ(n)) = 1?
• 4. If we can find such an e, can we
find d such that e × d  1
(modφ(n))?
• 5. Can we realistically compute
16
either me (mod n) or cd (mod n)?
Modular
Arithmetic
SYCS 653 Fall 2009
17
Consider First Z6
• Addition
•
+ 0 1 2
•
0 0 1 2
•
1 1 2 3
•
2 2 3 4
•
3 3 4 5
•
4 4 5 0
•
5 5 0 1
3
3
4
5
0
1
2
4
4
5
0
1
2
3
5
5
0
1
2
3
4
• Multiplication
•
 0 1 2 3 4 5
•
0 0 0 0 0 0 0
•
1 0 1 2 3 4 5
•
2 0 2 4 0 2 4
•
3 0 3 0 3 0 3
•
4 0 4 2 0 4 2
•
5 0 5 4 3 2 1
18
Now Consider Z7
• Addition
•
+ 0 1 2
•
0 0 1 2
•
1 1 2 3
•
2 2 3 4
•
3 3 4 5
•
4 4 5 6
•
5 5 6 0
•
6 6 0 1
3
3
4
5
6
0
1
2
4
4
5
6
0
1
2
3
5
5
6
0
1
2
3
4
6
6
0
1
2
3
4
5
• Multiplication
•
 0 1 2 3 4 5 6
•
0 0 0 0 0 0 0 0
•
1 0 1 2 3 4 5 6
•
2 0 2 4 6 1 3 5
•
3 0 3 6 2 5 1 4
•
4 0 4 1 5 2 6 3
•
5 0 5 3 1 6 4 2
•
6 0 6 5 4 3 2 1
19
What Are the Differences in
the Tables?
• An element (in any multiplication
table) has a multiplicative inverse 
there is a “1” in the row
corresponding to that element
• Which elements have inverses in Z6?
• Which elements have inverses in Z7?
20
What is the Essential
Difference Between 6 and
7?
• One is prime (all non-zero elements have
inverses)
• The other is composite (certain non-zero
elements do not have inverses)
– indeed, the elements that do not have inverses
are exactly those which have a common factor
21
with the composite number
Computing the
GCD and the
Modular
Inverse
SYCS 653 Fall 2009
22
The “3x2” Algorithm for
GCD
• Suppose we want to compute GCD(36583,
17286).
• First construct a 32 matrix whose first
row consists of the two numbers whose
GCD we wish to compute
• Next write for the second row: 1 0
• And for the third row: 0 1, i.e.
• 36583 17286
•
1
0
•
0
1
23
The algorithm
• Multiply the right-most column by
the largest integer so the product of
the element in the first row is less
than its left-hand neighbor, in this
case 2.
• Create a new column to the right,
which is [left column] – multiplier 
[right column]
• 36583
17286
2011
•
1
0
1
24
•
0
1
-2
Finally, repeat until the first
row has a “0.”
2
8
1
1
385
8
43
1
3658
3
1728
6
2011
1198
1
0
1
-8
9
-17
43
-361
0
1
-2
17
-19
36
-91
764
GCD
813
2
Inverse (if it exists)
41
20
2
2
1
0
404
8441
1728
6
-855
1786
4
3658
3
25
Another Example
2
8
1
1
2
2
1
2
1
1
2
2
365
85
172
86
201
3
118
2
831
351
129
93
36
21
15
6
3
0
1
0
1
-8
9
-17
43
103
146
395
541
936
241
3
576
2
0
1
-2
17
-19
36
-91
218
309
836
114
5
198
1
510
7
121
95
GCD
26
Primality
Testing
SYCS 653 Fall 2009
27
If We Can’t Factor Big
Numbers …
• How can we tell if they are prime?
• The answer is, we can’t …
– But we can choose a number p, which, if
it passes a set of tests “primality tests,”
we will be willing to accept as a prime,
with a probability of 1/(2100) of guessing
wrong.
28
Either the Solovay-Strassen or
the Lehman-Peralta Primality
Test
• To test p for primality, first choose 100
numbers at random < p, e1, …, e100.
• Compute GCD[ei, p] for i = 1,…,100
• If any GCD is > 1, throw out p and start over!
• For each ei and p, compute a number called
the Jacobi symbol. It is either 1 or –1. If the
Jacobi symbol is 1, there is only a 50% chance
that p is not prime and the Jacobi symbol is 1.
• Thus, if all 100 Jacobi symbols are 1, there is
only a 1/(2100) chance that p is not prime.
29
The Fast
Exponentiation
Algorithm
SYCS 653 Fall 2009
30
How Not to Compute
x16374927
• Compute x × x × x × x × x × x × x × x
×x×x×x×x×x×x×x×x×x×x
×x×x×x×x×x×x×x×x×x×x
×x×x×x×x×x×x×x×x×x×x
×x×x×x×x×x×x×x×x×x×x
×x×x×x×x×x×x×x×x×x×x
×x×x×x×x×x×x×x×x×x×x
×x×x×x …×x
• 16,374,927 times
31
Maybe for 16 million …
• But of course, the former method will
never complete if we’re trying to
compute
• x1728347619348723048762093847612471087462083
47631208
• For example.
32
Fast Exponentiation for
x14374
• First, convert
14374 to binary:
• 14374
• - 8192 ( = 213 )
•
6182
• - 4096 ( = 212 )
•
2086
• - 2048 ( = 211 )
•
38
• 38
• - 32 ( = 25 )
•
6
• - 4 ( = 22 )
•
2
• - 2 ( = 21 )
•
0
• Therefore the
binary is
11100000100110
33
Now, 14374 =
111000001001102
•
•
•
•
•
•
•
•
Call the bits b13b12b11…b2b1b0.
Ignore the high bit
To compute x14374, set m = x
Do i = 12 downto 0
m := m * m
if bi = 1 then m = m * x
End do
m is the desired exponent.
34
Specifically:
• m=x
• i = 12: x  x2,
– x2  x = x3
• i = 11: x3  x6,
– x6  x = x7
•
•
•
•
i
i
i
i
=
=
=
=
10: x7  x14
9: x14  x28
8: x28  x56
7: x56  x112
• i = 6: x112  x224
• i = 5: x224  x448
–
x448  x = x449
• i = 4: x449  x898
• i = 3: x898  x1796
• i = 2: x1796  x3592
–
x3592  x = x3593
• i = 1: x3593  x7186
–
x7186  x = x7187
• i = 0: x7187  x14374
35
Checking the Results
• Go to Mathematica
36
If Your Skepticism is Cured
… Why Does It Work?
•
•
•
•
•
•
Aha! Little Fermat Theorem:
cd = (me)d (definition of decryption)
 med 
(multiplication of exponents)
 mkφ(n)+1 (since ed  1 mod φ(n))
 mkφ(n) × m1 (addition of exponents)
 1 × m = m (by the Little Fermat
Theorem)
• All computations mod n.
37
Digital Signatures
• Conceivably a more important challenge in
security than encryption is
authentication
• How can I prove that a given document
was really produced by the purported
author?
• Technique is often called “digital
signatures” in comparison with ordinary
written signatures
• Current methodology also uses “Little
Fermat” and the same underlying theory
38
Digital Signatures: the
Model
• Also a “public-key”
approach
• Every user has a public
key for signing
• To “sign” a message M,
append to the message
a few bytes requiring
private key S. Send
M+S.
• Anyone can verify that
M+S came from
legitimate source by
doing a computation on
M+S using legitimate
sender’s public key.
M
S
M+S
39
Digital Signature Standard
• Conceivably a more important challenge in
security than encryption is authentication
• How can I prove that a given document was
really produced by the purported author?
• Technique is often called “digital signatures” in
comparison with ordinary written signatures
• Current methodology also uses “Little Fermat”
and the same underlying theory
• The definition of the standard can be found at:
– http://www.itl.nist.gov/fipspubs/fip186.
htm
40
Digital Signature Standard
The DSA makes use of the following parameters:
• 1. p = a prime modulus, where 2L-1 < p < 2L for 512 =
< L = <1024 and L a multiple of 64
• 2. q = a prime divisor of p - 1, where 2159 < q < 2160
• 3. g = h(p-1)/q mod p, where h is any integer with 1 < h
< p - 1 such that h(p-1)/q mod p > 1
(g has order q mod p)
• 4. x = a randomly or pseudorandomly generated integer
with 0 < x < q
• 5. y = gx mod p
• 6. k = a randomly or pseudorandomly generated integer
with 0 < k < q
41
Digital Signature Standard
• The integers p, q, and g can be public and can be
common to a group of users. A user's private and
public keys are x and y, respectively. They are
normally fixed for a period of time. Parameters x
and k are used for signature generation only, and
must be kept secret. Parameter k must be
regenerated for each signature.
Parameters p and q shall be generated as
specified in Appendix 2, or using other
FIPS approved security methods.
Parameters x and k shall be generated as
specified in Appendix 3, or using other
42
FIPS approved security methods.
Signature Generation
The signature of a message M is the pair
of numbers r and s computed according to
the equations below:
• r = (gk mod p) mod q and
• s = (k-1(SHA(M) + xr)) mod q.
• In the above, k-1 is the multiplicative
inverse of k, mod q; i.e., (k-1 k) mod q =
1 and 0 < k-1 < q. The value of SHA(M) is
a 160-bit string output by the Secure
Hash Algorithm specified in FIPS 180. For
use in computing s, this string must be
converted to an integer.
43
Signature Generation
• As an option, one may wish to check
if r = 0 or s = 0. If either r = 0 or s
= 0, a new value of k should be
generated and the signature should
be recalculated (it is extremely
unlikely that r = 0 or s = 0 if
signatures are generated properly).
The signature is transmitted along
with the message to the verifier.
44
Signature Verification
• Prior to verifying the signature in a signed
message, p, q and g plus the sender's public key
and identity are made available to the verifier in
an authenticated manner.
Let M', r' and s' be the received versions of M, r,
and s, respectively, and let y be the public key of
the signatory. To verifier first checks to see that
0 < r' < q and 0 < s' < q; if either condition is
violated the signature shall be rejected. If these
two conditions are satisfied, the verifier computes
• w = (s')-1 mod q
u1 = ((SHA(M')w) mod q
u2 = ((r')w) mod q
v = (((g)ul (y)u2) mod p) mod q.
45
Signature Verification
• If v = r', then the signature is verified and
the verifier can have high confidence that
the received message was sent by the
party holding the secret key x
corresponding to y. For a proof that v = r'
when M' = M, r' = r, and s' = s, see
Appendix1.
If v does not equal r', then the message
may have been modified, the message
may have been incorrectly signed by the
signatory, or the message may have been
signed by an impostor. The message
46
should be considered invalid.
The Dilemma
• “Lucifer” or DESType Methods
– Very suspicious
definitions
– Don’t solve key
management
problem
– Very fast, efficient
• Number Theoretic
Methods
– Very clear methods
– Public-key methods
solve key
management
– Inherently slow
This is the ultimate
dilemma!
47
References
• General Scientific Reference:
– Mathematical Cryptology, Wayne Patterson, Rowman
and Littlefield, 1987.
• Mathematical infrastructure:
– Number Theory, Wayne Patterson, in the Wiley
Encyclopedia of Electrical and Electronics Engineering,
Wiley, 1999.
• Website for current technology (and some
history):
– http://www.rsasecurity.com/experience/esecurity/index.
html#
• WW II History:
– The Hut Six Story, Gordon Welchman, Classical Crypto
Books, 1997.
• Current Security Issues:
– Secrets and Lies, Bruce Schneier, Wiley, 2000.
48