Return to Video

03-16 Discrete Log Problem Solution

  • 0:00 - 0:02
    The answer is the second choice.
  • 0:02 - 0:06
    If it were possible to compute discrete logs quickly,
  • 0:06 - 0:08
    and our adversary had a way to do that,
  • 0:08 - 0:10
    well then, they could compute the discrete log of the
  • 0:10 - 0:13
    intercepted value y-A, the g, and the q values,
  • 0:13 - 0:15
    which were also intercepted.
  • 0:15 - 0:17
    Those ones were public,
  • 0:17 - 0:19
    and the result of this would be the
  • 0:19 - 0:21
    x-A value that was Alice's secret,
  • 0:21 - 0:23
    and then the adversary can
  • 0:23 - 0:25
    compute the key the same way that Alice would.
  • 0:25 - 0:27
    This was the only secret value,
  • 0:27 - 0:29
    and if you had the discrete log function,
  • 0:29 - 0:31
    you could compute that secret value.
  • 0:31 - 0:33
    The second answer doesn't compute the right thing.
  • 0:33 - 0:35
    It's computing the straight log of y-B,
  • 0:35 - 0:37
    which would be the y-A value.
  • 0:37 - 0:41
    That's not the value that is necessary to compute the key.
  • 0:41 - 0:43
    The third value doesn't use discrete log.
  • 0:43 - 0:45
    If we could actually compute the key this way,
  • 0:45 - 0:47
    well then the protocol would be completely
  • 0:47 - 0:49
    unsecure because it turns out that
  • 0:49 - 0:51
    modular exponentiation is a function
  • 0:51 - 0:53
    that we can compute efficiently,
  • 0:53 - 0:56
    and it's necessary that we can compute modular exponentiation efficiently
  • 0:56 - 0:59
    because otherwise, the legitimate participates
  • 0:59 - 1:02
    in the protocol wouldn't be able to determine their keys.
  • 1:02 - 1:04
    So we will look at that soon.
  • 1:04 - 1:07
    Before doing that, I want to emphasize that this is not a proof
  • 1:07 -
    that breaking discrete log is hard.
Title:
03-16 Discrete Log Problem Solution
Team:
Udacity
Project:
CS387 - Applied Cryptography
Duration:
01:10
Amara Bot added a translation

English subtitles

Revisions