## 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
• 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
• 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