Diffie Hellman -the Mathematics bit- Computerphile 

could you please link an explanation to this? i've been trying to understand how g^a and g^b were made public when in actuality it was those numbers _mod n_ that were made public. also don't understand how you can calculate (g^a)b mod n without first having g^a, which again, wasn't made public because of the modulo term

@@znefas I never saw an explanation myself, but consider the following: imagine we are working in base N, and not binary or decimal. Then, modN just keeps the last digit. So, since we know that it's possible to start by calculating the last digit when doing long addition/multiplication, as the carry only travels left, we can discard the left digits at any intermediate steps and still have the same result as if we only did it at the end. Signed addition and negative powers (division) break this, but wrapping subtraction of unsigned integers actually survives afaik. This is the same reason why we can know the last digit of 7^44444 will be 1, without having to calculate the whole number.

@@qm3ster the only thing i understood is how the carry only traveling left may be useful when trying to calculate a number smaller than the entire expression; i don't understand how the whole mod N thing works i also hate modular arithmetic notation because "13 = 5 mod 8" is so much more annoying than "13 % 8 = 5" for me as a programmer

​@@znefas for all unsigned integers a, b, c, n: (a + b)%n == (a%n + b%n)%n (a * b)%n == ((a%n)*(b%n))%n ((a ^ b) ^c)%n == (((a%n)^b)%n)^c)%n As long as at the end you were dropping the stuff left of n, the result won't be changed by dropping it earlier, as it cannot affect what is on the right. The intermediate values will in fact be different, which is what makes this a computational saving. But outside cryptography and adjacent subjects like checksumming you usually want the most significant bits, not the least significant, they're called that for a reason, so this doesn't get used *too* often.

@@znefas g^a and g^b wasn't made public, only g^a%n and g^b%n - Mike got a bit sloppy when presenting (just as we do when we write down the maths). If we knew g^a, and since we know g, it would be trivial to work out a (and similarly for b).

A Parker clock, one might say!

It should not, as they used the colour analogy there.

The clock is not strictly an analogy, it's a common learning technique for modular arithmetic

It explains why n needs to be a big value.

The clock analogy I think is one of the best ways to explain modulo arithmetic...

There is quite some math behind it about rings, fields and other group theory. But the plain formulas in crypto are pretty nice and easy. The computation is quite a mess as numbers get pretty big, often even bigger than your memory and power and multiply are not the chips best friend.

I find there are a lot of these types of algorithms; Radix Sort comes to mind... It seems like voodoo, then you look at the algorithm, and probably at first think 'that can't possibly work...?' but viola...

​@@MrHaggyythat's still somewhat elegant, square-multiply-modulo is a genius and simple solution to easily calculate such an otherwise gargantuant number. I find the truly hard (and amazing) part is the theory behind which numbers are safe to use, even more fascinatingly and terrifyingly genius are the ways people find to crack it

@@justalonelypoteto square-multiply is a genius algorithm as it has view operations,. Lattice and Russian Peasant are awesome too. A lot more operations but most of them are cheap additions that can be done in parallel. My interest is hard-realtime systems. We want algorithms with fixed calculation times. Square-multiply can vary depending on the numbers. And on cheap and small hardware you might be able to eavedrop with an oscilloscope.

@@MrHaggyy Montgomery's ladder might be up your alley, it performs both operations each time with the only distinguishable difference being a possible timing variation because the needed operation affects which memory address is read, apparently this is fixed by scattering the data around to ensure cache misses

If you watched Attack on Titan ,one of the character used. Only his words and hacked the entire cosmos to make it seem real at that moment

Yup.

Thanks for this, felt like a logical leap without this proof.

At the beginning there, did you put a g, where you meant a b?

@@nelsblair2667 He did, yes.

Interesting proof. But a few corrections: First what you are trying to prove is that (g^a)^b mod n == (g^a mod n)^b You made a mistake, in (((g^a) mod n) ^ g)) mod n . You put an extra "g", it's a "b" Also to simplify...or clarify your proof, and make it more understandable, organized: 1) supposing: g^a = n*k+x ( *WHERE "x" IS NOT A MULTIPLE OF "n"* , in other words "x" is the "remainder" of the division by "n" ) This is an important purposeful "setting up" so that: n*k mod n == 0 and x mod n == x 2) mod n of any number which is a multiple of n will equal zero --> n*k mod n == 0 3) Proof that: (g^a mod n)^b == x^b a) Which would mean --> (g^a mod n) == x a) substitute "n*k+x" for "g^a", from step "1" (n*k + x) mod n == x --> given that: n*k mod n == 0 (any multiple of "n" will be zero) b) If (n*k + x) mod n == x, then (g^a mod n) == x, c) meaning --> (g^a mod n)^b == x^b 4) (g^a)^b mod n a) substitute (n*k+x) for g^a, given in step "1" --> (n*k+x)^b mod n b) Expanding (n*k+x)^b, using binomial theorem, *IMPORTANT MAGIC* : *all terms will be multiples of "n"* except the last term which is x^b c) Mod n of all terms that are multiples of "n" will be zero, leaving only the last term: x^b d) Thus (g^a)^b mod n = x^b 5) (g^a)^b mod n == (g^a mod n)^b , as both equal to x^b .

yeah, modular arithmetics is easy. :D ...

And theeeeres the party pooper.

Didn't work for me a=11 b=13 g=7 n=199

The math is easier to understand, because it's more technical.

Jyoti Das lol.

Correct that was an error on their part since of course if a divides by n exactly the remainder is 0 not n.

Technically you could have n on the clock but you'd have to omit 0. You can have n or you can have 0, but not both. Having n on the clock would actually be more like counting units of 1 up to n and then starting back at 1 again for the next unit until you run out of units. Same result (specifically in this case because the number itself doesn't matter), but a different perspective on it.

Having a 0 instead of the n is very useful when you work with such a construct though. This clock face is what mathematicians call a cyclic group, and its "neutral element" is 0 (or n, they are the same in the cyclical group). That means that (a+0)mod n=a mod n, so the 0 doesn't change an element by being added. That is very obvious if you actually write it as a 0 instead of an n.

And multiply by zero also give nice properties. :-)

But clocks are 1-based.

☞ nope.avi

they need to feel smart

If you're not familiar with what he's explaining, this is enough to confuse you and this is not the only thing he says that can create confusion.

he kinda of implicitly stopped at n-1 when he mentioned there is the element 0 in mod operations

😂

Fabian Neundorf (g^a mod n)^b mod n is the same as (g^a)^b mod n, I believe he also mentioned it briefly in the video.

The simple answer as to why they're the same is that Modulo arithmetic=Finite fields, and Finite fields are consistent. Proving that finite fields are consistent would probably be another couple videos...

Short answer: It's because the product in modulo/clock arithmetic is defined that way. If you wanna know more I'll explain it in more detail: Maybe it's easier if you think of g^a mod n just as a number between 0 and n-1 (actually if we use this notation we should start from 1 and go up to n-1, but it's not extremely important so let's forget about it). Think of the multiplication between two such numbers as a standard multiplication, but if the result is bigger than n-1 we take the remainder. So basically the product is just: (a mod n)*(b mod n) = a*b mod n (THIS IS THE DEFINITION OF PRODUCT IN MODULO ARITHMETIC) Elevating g to the power a is just repeated multiplication, so what you do is apply the definition of product: (g mod n)^a = (g mod n)*(g mod n)*...*(g mod n) = g*g*g*...*g mod n You can easly see that we get a similar thing if we elevate g^a to the power b: (g^a mod n)*(g^a mod n)*...*(g^a mod n) = (g^a)*(g^a)*...*(g^a) mod n = (g^a)^b mod n So yeah, (g^a mod n)^b = (g^a)^b mod n Hope it's clear now ;)

The "mod n" isn't an operation in this case. Appending "mod n" to a term just signals that you're calculating in clock arithmetic, meaning you always stay between 0 and n-1. If you do 2+3 in "mod 4", the answer is 5, or 1, or even 9, because in "mod 4" 1 is equal to 5 by definition. Calculating a modulo is not an operation that needs to be performed if you define yourself to be working in clock arithmetic

Actually g^(ab) mod n = (g^a mod n)^ b mod n, but yes, it is the same. The proof is just long and kinda gross which is why he didn't get into it. Here it is if you want to see it though. Proof: Any number m mod n is defined as the remainder left after dividing m by n, so we have m=q*n+r where q is the whole number of times n goes into m, and m mod n=r, which is the remainder. So g^a=q_a*n+r_a, and g^a mod n=r_a. (I'm using the underscore to denote a subscript.) (g^a mod n)^b=r_a^b=q_1*n+r_1, and (g^a mod n)^b mod n=r_1. g^(a*b)=q_(ab)*n+r_(ab), and g^(a*b) mod n =r_(ab). But we also know g^(a*b)=(g^a)^b, and g^a=q_a*n+r_a, so g^(a*b)=(q_a*n+r_a)^b. Expanding that out into a sum we get (q_a*n+r_a)^b=sum((q_a*n)^(b-j)*r_a^j,j=0..b) The last term in this sum is r_a^b and every other term has at least one factor of n, so we can rewrite it as (q_a*n+r_a)^b=n*sum(q_a^(b-j)*n^(b-j-1)*r_a^j , j=0..b-1)+r_a^b. Now let q_2=sum(q_a^(b-j)*n^(b-j-1)*r_a^j , j=0..b-1), so we have (q_a*n+r_a)^b=q_2*n+r_a^b. Remember that this is equal to g^(a*b). So we have g^(a*b)=q_2*n+r_a^b. We already have r_a^b=q_1*n+r_1, so we have g^(a*b)=(q_1+q_2)*n+r_1 and g^(a*b) mod n = r_1. We already had that (g^a mod n)^b mod n = r_1 so we have now proved that g^(a*b) mod n = (g^a mod n)^b mod n.

For anyone who got confused with this, we start with the left-hand side of the equation: (g^a mod p)^b mod p = (g^ab mod p) mod p [by the property of modular exponentiation] Now, we move on to the right-hand side of the equation: (g^b mod p)^a mod p = (g^ba mod p) mod p [by the property of modular exponentiation] Since (g^ab mod p) mod p = (g^ba mod p) mod p, we can say that: (g^a mod p)^b mod p = (g^b mod p)^a mod p Hope this helps.

...yeah you should really log off

You didn’t get the video.... tbh he actually did explain it well

@@ivanarabome4172 and you didn't get the joke

@Jesse Duncan yup, been watching on instaflixxer for since november myself =)

Nice

Same. With the color one I was like "what do you mean I can't figure out what the other color was? We just subtract the public color from it!"

The actual process is more difficult as instead of adding, it's multiplication to the power of another colour. Imagine Yellow^red x blue.

Me too. It's so easy to understand math when it doesn't have weird symbols that I have no idea what the heck they mean.

Yes, the thing with math is that it is a language which you need to learn. Once you do, the concepts behind the maths become not that complicated, when you know them. Implementation could still be complicated though. Devils in the details...

Thomas Wigele Yeah I came down to point it out as well :)

not only that, but the primality of g is completely irrelevant - the n needs to be prime if you want the n in the 2 to 4k range (and DH to remain secure), best if n is actually a safe prime (then g can be any number but 0, 1 and n-1) - a prime for which (n-1)/2 is also prime

666Tomato666 I don't get why n would have to be prime at all?

+Π. Καράπας This way you are 100% sure that the remainder is in [0, n-1].

Александър Савев but doesn't modulo always return something in the range of [0,n-1]?

In the previous video regarding this topic, with the color mixing, he mentions that n is a prime number.

I really was hoping he would explain why n has to be prime. I'm thinking the reason is that the search space of [numbers] mod n would be much smaller than n if it weren't a prime number, but that's just my intuition and I'm not sure if I'm right.

@@tissuepaper9962 The goal is to have the denominator and numerator being coprime i.e. their greatest common divisor is 1 as otherwise, you'd end up getting 0 as the result. The only way to guarantee that is with a prime number which is naturally coprime to any number.

This is the most important fact that makes this explanation work.

I'm not the only one who is botherd by this ^^

This is very true. Easy mistake to make, though.

same thought here - was about to write a comment.

There are 3 hard things in programming: 1 off by one errors and 2 naming things

I was about to write the same xd

Really? I've never seen it explained without this clock representation.

Yes, you can do that pretty efficiently. It's called modular exponentiation. Basically, ga^b is calculated (ga is (g^a)mod n) the way it normally would, but after every little step of that calculation, the mod n of the current result so far is calculated.

I'm glad I'm not the only one I thought this, I literally couldn't go on watching the video, this bothered me so much. At 3:47 He says Bob sends Alice g^b, well now everyone knows b. If he meant to say Bob sends Alice g^b mod n, then he doesn't explains how Alice is able to extract g^b from that (why can't people listening in do this then??) in order to raise it to a. Very frustrating.

Yeah, I wanted to hear that too, but considering the technique wouldn't work otherwise, it probably is. It also kind of makes intuitive sense in the terms of significant bits. Modulo tosses away all most-significant bits, and only keeps the least significant bits. Multiplication will push the least significant bits into the most significant bits (two 32 bit numbers multiplied for example, gives a 64 bit number). So tossing away those most significant bits (which would've been moved to even higher significant bits) shouldn't matter.

The modulo just takes the remainder of the division: being the multiplication commutative, g^(ab) = g^(ba), you'll get the same number. You can then do modulo n, but the number will be the same anyways.

Let's say g^{a} = X + Y, where X is divisible by n and Y < n (therefore g^{a} mod n = Y). Then g^{ab} is (X^b + c1*X{b-1}Y + c2*X{b-2}Y^{2} + ... + Y^b). Since X is a multiple of n, all but the last term will be zero mod n, so we are left with Y^b mod n = ( g^{a} mod n)^b mod n after we take the modulo. Therefore g^{ab} mod n = g^{a} mod n)^b mod n. I hope that's clear enough.

This is why he put this in the Maths video and not the colour video. As you should know this basic thing to know the theory. And he mentioned it in the video, very short.

Is that true? After thinking about this (admittedly only for a few minutes), it is obvious to me that for a given size of n, selecting g to be a primitive root is the most secure because you'll get the maximal cycle length of n-1. But choosing a non-(primitive root) doesn't seem to actually break the algorithm.

@@trogdorstrngbd yes is doesn't break the algorithm but you will need to exhaust fewer values