Return to Video

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
    talk about hard problems.
  • 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
    and advisory that's passive
  • 3:50 - 3:53
    so all it can do is ease drop on the messages,
  • 3:53 - 3:55
    but they also have access to a powerful computer resource,
  • 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
Amara Bot added a translation

English subtitles

Revisions