## 03-15 Discrete Log Problem

• 0:00 - 0:02
The hard problem that is closely related
• 0:02 - 0:04
to the Diffie-Hellman security property
• 0:04 - 0:06
is the discrete log problem.
• 0:06 - 0:08
Discrete logs are like continuous logs
• 0:08 - 0:10
but over a discrete group.
• 0:10 - 0:13
So continuous log if we have a to the x equals b,
• 0:13 - 0:16
and we know a and b, we can solve for x.
• 0:16 - 0:19
That's the log base a of b,
• 0:19 - 0:22
and they're well know efficient ways to compute these logarithms.
• 0:22 - 0:24
One of the earliest use of computers
• 0:24 - 0:27
was to compute these tables of logarithms.
• 0:27 - 0:30
With discrete numbers, this gets much more interesting.
• 0:30 - 0:32
So now we have a to the x equals b,
• 0:32 - 0:34
modulo sum value n,
• 0:34 - 0:36
and our goal is to solve for x,
• 0:36 - 0:39
which is the discrete log base a of b,
• 0:39 - 0:42
and this turns out to be, as far as everyone can tell,
• 0:42 - 0:45
a very hard problem when n is a large prime number.
• 0:45 - 0:47
It's not clear that discrete log always exists,
• 0:47 - 0:51
and for certain choices of a, b, and n, it would not exists,
• 0:51 - 0:53
but if we choose n as a large
• 0:53 - 0:55
prime number and a as a generator,
• 0:55 - 0:57
well then by definition, it must exist.
• 0:57 - 0:59
What it means for our number to be a generator
• 0:59 - 1:03
is that if we raise g to each power,
• 1:03 - 1:06
what we get is the permutation of the numbers in the group Zn.
• 1:06 - 1:09
So as a little demonstration, certainly not a proof,
• 1:09 - 1:12
here's a code that produces the permutation
• 1:12 - 1:16
for given some generator and some modulus,
• 1:16 - 1:19
raises the generator to every power
• 1:19 - 1:21
between 1 and the modulus minus 1.
• 1:21 - 1:23
So we can try that with a fairly
• 1:23 - 1:26
small prime number so you can see the results.
• 1:26 - 1:29
We'll use 277 as our prime number
• 1:29 - 1:32
and 5 as a generator for 277.
• 1:32 - 1:34
One could check that in a root force way
• 1:34 - 1:37
just to show that it all produces all the numbers,
• 1:37 - 1:40
and we'll see that in the output for generator permutation.
• 1:40 - 1:42
These are the results and
• 1:42 - 1:45
you can see the first 1 is 5, that's 5 to the 1;
• 1:45 - 1:49
25 is 5 to the 2; 125 is 5 to the 3.
• 1:49 - 1:54
The next one is 71 because 5 to the 4 mod to 77 is 71,
• 1:54 - 1:56
and if we look at all the numbers here,
• 1:56 - 2:00
it would be a permutation on the numbers from 1 to 276.
• 2:00 - 2:02
Other than the early ones,
• 2:02 - 2:04
it would be fairly hard to predict where
• 2:04 - 2:06
a number is in this sequence.
• 2:06 - 2:08
You could certainly compute the whole sequence to find it.
• 2:08 - 2:11
The question the discrete log is asking
• 2:11 - 2:13
is given a number, can you figure out
• 2:13 - 2:15
where it would be in this sequence
• 2:15 - 2:17
or can you figure out the power that you need
• 2:17 - 2:19
to raise the generator to find it,
• 2:19 - 2:21
and the claim is that that's hard to do.
• 2:21 - 2:23
Showing this sequence really is not enough
• 2:23 - 2:25
to convince you that that's hard to do,
• 2:25 - 2:27
and there's no proof that it's hard.
• 2:27 - 2:29
The reason people believe it's hard
• 2:29 - 2:31
is that many smart people have tried to find
• 2:31 - 2:33
good ways of doing this, and none of the
• 2:33 - 2:35
solutions rendered polynomial time
• 2:35 - 2:38
that the fastest known solutions are exponential.
• 2:38 - 2:41
That means essentially that the only way to solve
• 2:41 - 2:44
this is to try all possible powers
• 2:44 - 2:46
until you find the one that works.
• 2:46 - 2:48
You can do a little better than that by trying
• 2:48 - 2:50
powers in a clever way, and you can
• 2:50 - 2:52
exclude some of the powers more quickly,
• 2:52 - 2:55
but you can't do any better than doing this exponential search,
• 2:55 - 2:58
which is exponential in the size of n
• 2:58 - 3:00
so this is something we have to be careful about when we
• 3:00 - 3:02
• 3:02 - 3:05
When we say it's exponential, well it's not exponential in the value of n.
• 3:05 - 3:07
It's linear in the value of n.
• 3:07 - 3:10
We just need to try n operations,
• 3:10 - 3:12
but the magnitude of n
• 3:12 - 3:17
grows as 2 to the number of bits needed to break down n.
• 3:17 - 3:20
So as long as that's the best solution to discrete log,
• 3:20 - 3:22
then for very large n,
• 3:22 - 3:25
it is intractable no matter how many computer resources you have,
• 3:25 - 3:27
you can't do this exponential search.
• 3:27 - 3:29
You can't find the value of x that's the
• 3:29 - 3:32
discrete log of b, base a, mod n.
• 3:32 - 3:34
So as long as no one can find a
• 3:34 - 3:37
fast way to solve the discrete log problem,
• 3:37 - 3:39
as long as n is large and is an
• 3:39 - 3:41
arbitrary instance of this problem,
• 3:41 - 3:43
we think that it should be hard to
• 3:43 - 3:46
compute x given a and b and the modulus.
• 3:46 - 3:48
So for this quiz, we will assume that we have
• 3:48 - 3:50
• 3:50 - 3:53
so all it can do is ease drop on the messages,
• 3:53 - 3:55
• 3:55 - 3:58
they have a procedure dlog that is
• 3:58 - 4:00
a fast procedure for computing discrete
• 4:00 - 4:02
logs that works on any inputs,
• 4:02 - 4:04
and they have modular exponentiation,
• 4:04 - 4:06
a fast procedure that outputs
• 4:06 - 4:08
base to the power mod modules.
• 4:08 - 4:11
And now the question is can they break a Diffie-Hellman key?
• 4:11 - 4:14
So we're assuming that they're passive attackers,
• 4:14 - 4:17
so they've eased dropped on all the
• 4:17 - 4:19
messages between Alice and Bob,
• 4:19 - 4:22
so they have all these values that were sent over the secure channel,
• 4:22 - 4:24
and the possible answers are no
• 4:24 - 4:26
that it's impossible with no
• 4:26 - 4:29
more resources or information,
• 4:29 - 4:31
or yes there is a way to do it,
• 4:31 -
and here's the way that she would compute that.
Title:
03-15 Discrete Log Problem
Team:
Udacity
Project:
CS387 - Applied Cryptography
Duration:
04:34