Diffie Hellman -the Mathematics bit- Computerphile

แชร์
ฝัง
  • เผยแพร่เมื่อ 1 ต.ค. 2024
  • Correction : as oodles of commenters have pointed out, the clock face should go from 0 to n-1. Also, worth reminding people that Mike has simplified the notation in this video (as he mentions).
    Mike explains the mathematics behind one of the most important pieces of computer security. (Simplified version with colour mixing analogy linked below)
    Secret key Exchange (Colour Mixing) Video: • Secret Key Exchange (D...
    / computerphile
    / computer_phile
    This video was filmed and edited by Sean Riley.
    Computer Science at the University of Nottingham: bit.ly/nottsco...
    Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com

ความคิดเห็น • 807

  • @qm3ster
    @qm3ster 2 ปีที่แล้ว +345

    I think the fact that addition, multiplication, and exponentiation maintain their properties under modulo arithmetics was worth mentioning.

    • @znefas
      @znefas 2 ปีที่แล้ว +18

      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

    • @qm3ster
      @qm3ster 2 ปีที่แล้ว +21

      @@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.

    • @znefas
      @znefas 2 ปีที่แล้ว +4

      @@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

    • @qm3ster
      @qm3ster 2 ปีที่แล้ว +46

      ​@@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.

    • @wybird666
      @wybird666 ปีที่แล้ว +15

      @@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).

  • @peter62709
    @peter62709 6 ปีที่แล้ว +94

    I just took a crypto class in university and my professor got so wrapped up in the specifics of group theory that I didn't even understand how Diffie-Hellman worked, but this made everything so clear without really being any less mathematical.

  • @babel_
    @babel_ 6 ปีที่แล้ว +309

    Alice and Bob only communicate in Pub. Alice and Bob are probably undergrads.

  • @xcvsdxvsx
    @xcvsdxvsx 6 ปีที่แล้ว +968

    I actually understood the math for once!

    • @peppybocan
      @peppybocan 6 ปีที่แล้ว +10

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

    • @jasonpatowsky6929
      @jasonpatowsky6929 6 ปีที่แล้ว +62

      And theeeeres the party pooper.

    • @BryanLeeWilliams
      @BryanLeeWilliams 6 ปีที่แล้ว

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

    • @grrr1351
      @grrr1351 6 ปีที่แล้ว +2

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

    • @musashi939
      @musashi939 6 ปีที่แล้ว

      Jyoti Das lol.

  • @emilmartens123
    @emilmartens123 6 ปีที่แล้ว +221

    awesome video, I see some comments point out its actually (((g^a) mod n) ^ g)) mod n, so here is why its the same as (g^a)^b mod n:
    lets say:
    g^a = k*n+x
    where x is an unknown number
    because: (u + v) mod n =(u mod n + v mod n) mod n
    and because: k*n mod n = 0
    we get:
    (g^a) mod n = (k*n+x) mod n = x
    ((g^a) mod n)^b mod n = x^b mod n
    i used the binomial theorem nCr to get:
    (g^a)^b = (k*n+x)^b = (k*n)^b + (nC1)*(k*n)^(b-1)*x + ... + (nC(b-1))*( (k*n)^(1)*x^(b-1) + x^b
    since n appears in every part except in x^b every other part is set to 0 when we take the modulo:
    (g^a)^b mod n = x^b mod n
    so therefore (g^a)^b mod n = ((g^a) mod n)^b mod n

    • @AhsimNreiziev
      @AhsimNreiziev 6 ปีที่แล้ว +1

      Yup.

    • @theguyoo1
      @theguyoo1 6 ปีที่แล้ว +39

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

    • @nelsblair2667
      @nelsblair2667 3 ปีที่แล้ว +11

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

    • @AhsimNreiziev
      @AhsimNreiziev 3 ปีที่แล้ว +7

      @@nelsblair2667
      He did, yes.

    • @deckard5pegasus673
      @deckard5pegasus673 3 ปีที่แล้ว +9

      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
      .

  • @fsmoura
    @fsmoura 5 ปีที่แล้ว +79

    5:02 THIS! IS! CRYPTOGRAPHY! *_*kicks you down a 4096-bit deep well*_*

  • @davidsanders9426
    @davidsanders9426 6 ปีที่แล้ว +200

    I thought "solving the discrete log problem" was what happens when you clog the toilet at your in-laws' house?
    ...Sorry, I'll show myself out.

    • @Ping727
      @Ping727 3 ปีที่แล้ว +18

      ...yeah you should really log off

    • @ivanarabome4172
      @ivanarabome4172 3 ปีที่แล้ว

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

    • @jamhamtime1878
      @jamhamtime1878 3 ปีที่แล้ว +13

      @@ivanarabome4172 and you didn't get the joke

    • @jadielrhys3156
      @jadielrhys3156 3 ปีที่แล้ว

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

    • @RussTeeTrombone
      @RussTeeTrombone 3 ปีที่แล้ว

      Nice

  • @kusharora1435
    @kusharora1435 3 ปีที่แล้ว +81

    love the way this guy explains.. never imagined i could binge watch cryptography videos

  • @KraylusGames
    @KraylusGames 6 ปีที่แล้ว +225

    Lmao everyone calling him out for not stopping at n-1. Give the dude a break!

    • @tohopes
      @tohopes 6 ปีที่แล้ว +8

      ☞ nope.avi

    • @tedbaltz2164
      @tedbaltz2164 4 ปีที่แล้ว +17

      they need to feel smart

    • @martinkunev9911
      @martinkunev9911 3 ปีที่แล้ว +13

      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.

    • @realcryptc
      @realcryptc 3 ปีที่แล้ว +1

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

    • @skeetabomb
      @skeetabomb 2 ปีที่แล้ว

      😂

  • @agrawalyogesh
    @agrawalyogesh 2 ปีที่แล้ว +7

    Hi Mike, Alice or Bob never shared "g to the power of a or b" but they shared "g to the power of a (b) mod n". But as we continued the example we said they shared the power of a or b. Can you please help explain that?

    • @cliftonfestusmalvea9777
      @cliftonfestusmalvea9777 ปีที่แล้ว +2

      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.

  • @CJBurkey
    @CJBurkey 6 ปีที่แล้ว +485

    Wouldn't a mod n only return values from 0 to _n_-1? You wrote _n_ on the clock.

    • @seraphina985
      @seraphina985 6 ปีที่แล้ว +80

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

    • @VoilaTadaOfficial
      @VoilaTadaOfficial 6 ปีที่แล้ว +47

      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.

    • @Friek555
      @Friek555 6 ปีที่แล้ว +23

      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.

    • @AndersJackson
      @AndersJackson 6 ปีที่แล้ว +3

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

    • @tohopes
      @tohopes 6 ปีที่แล้ว

      But clocks are 1-based.

  • @outofahat9363
    @outofahat9363 2 ปีที่แล้ว +22

    Came in expecting some incomprehensible esoteric math but this was very easy to understand. Reminds me of that Doctor Strange quote "It's a simple spell but quite unbreakable"

    • @mackmenezes4912
      @mackmenezes4912 ปีที่แล้ว +1

      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

  • @rabreu08
    @rabreu08 6 ปีที่แล้ว +189

    Great clock analogy. This should be the main video

    • @F1ghteR41
      @F1ghteR41 6 ปีที่แล้ว +7

      A Parker clock, one might say!

    • @AndersJackson
      @AndersJackson 6 ปีที่แล้ว +3

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

    • @mungflesh199
      @mungflesh199 5 ปีที่แล้ว +3

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

    • @Cysecsg
      @Cysecsg 4 ปีที่แล้ว +2

      It explains why n needs to be a big value.

    • @skeetabomb
      @skeetabomb 2 ปีที่แล้ว

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

  • @YouTubist666
    @YouTubist666 6 ปีที่แล้ว +79

    Wow. I've always thought D-H was some esoteric math magic. It is extremely clever and elegant.

    • @MrHaggyy
      @MrHaggyy 2 ปีที่แล้ว +2

      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.

    • @Tasarran
      @Tasarran ปีที่แล้ว

      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...

    • @justalonelypoteto
      @justalonelypoteto 11 หลายเดือนก่อน +1

      ​@@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

    • @MrHaggyy
      @MrHaggyy 11 หลายเดือนก่อน +1

      @@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.

    • @justalonelypoteto
      @justalonelypoteto 11 หลายเดือนก่อน +1

      @@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

  • @Ry____
    @Ry____ 5 ปีที่แล้ว +150

    It’s amazing how beautifully elegant and simple cryptography really is.

  • @xdyps
    @xdyps 6 ปีที่แล้ว +24

    Please do a video on Elliptic-curve cryptography and Elliptic-curve Diffie-Hellman , pretty please :D

  • @xZise
    @xZise 6 ปีที่แล้ว +268

    It looks really simple, but it unfortunately doesn't explain whether "(g^a mod n)^b" and "(g^a)^b mod n" are the same. I mean obviously it must be the same for it to work.

    • @bgroks1
      @bgroks1 6 ปีที่แล้ว +48

      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.

    • @jonathanseamon9864
      @jonathanseamon9864 6 ปีที่แล้ว +63

      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...

    • @TheUnclepecos
      @TheUnclepecos 6 ปีที่แล้ว +174

      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 ;)

    • @FelkCraft
      @FelkCraft 6 ปีที่แล้ว +25

      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

    • @danieljensen2626
      @danieljensen2626 6 ปีที่แล้ว +43

      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.

  • @Kolop315
    @Kolop315 6 ปีที่แล้ว +75

    Wow, that is way more simple than I was expecting.

  • @wildwest1832
    @wildwest1832 3 ปีที่แล้ว +13

    The idea of diffie hellman is actually really clever. Its actually pretty hard to come up with a way to do that, and not have anyone be able to reverse how they did it or needing to share something that can be reversed. I can see why we still use this today it would be very difficult to replace it, and its very ingenious how it works and its not incredibly complicated either.

  • @kegelsknight
    @kegelsknight 6 ปีที่แล้ว +208

    It shouldn't be 'n' on the clock but 'n-1' because 'n'==0 in modolo

    • @sebastianheinrich8683
      @sebastianheinrich8683 6 ปีที่แล้ว +22

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

    • @AhsimNreiziev
      @AhsimNreiziev 6 ปีที่แล้ว +5

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

    • @Majenga
      @Majenga 6 ปีที่แล้ว +3

      same thought here - was about to write a comment.

    • @remuladgryta
      @remuladgryta 6 ปีที่แล้ว +41

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

    • @breadnoodle
      @breadnoodle 6 ปีที่แล้ว

      I was about to write the same xd

  • @sponsoredmessage201
    @sponsoredmessage201 2 ปีที่แล้ว +3

    I don't understand why (g^a mod n)^b mod n = (g^a)^b mod n

  • @AdamMPick
    @AdamMPick 6 ปีที่แล้ว +42

    The whole time I am thinking about the clock-drawing test, after seeing those clockface numbers beeing squished together.
    PS. I find this video even simpler to understand than the original "simple" version with the food colouring.

    • @kayinnasaki
      @kayinnasaki 6 ปีที่แล้ว +6

      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!"

    • @lambertbrother1628
      @lambertbrother1628 6 ปีที่แล้ว +1

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

    • @xcvsdxvsx
      @xcvsdxvsx 6 ปีที่แล้ว +3

      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.

    • @AndersJackson
      @AndersJackson 6 ปีที่แล้ว +3

      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...

  • @kennethcarvalho3684
    @kennethcarvalho3684 2 ปีที่แล้ว +5

    For some reason I understand all his videos but not many of the other tutors on Comphile.. Quite a teacher

  • @elultimopujilense
    @elultimopujilense 4 ปีที่แล้ว +2

    At 4:00 that exponentiation is flawed, because you need to calculate (g^a mod n)^b, not (g^a)^b. Those are not the same, and the explanation he gave is not correct. He should have said that because of the modulus exponentiation property (g^a mod n)^b mod n is the same as (g^b mod n)^a mod n. He omitted a really important step when he jumped to (g^a)^b is equal to (g^b)^a. That is something that you arrive at when you apply the modulus exponentiaion property.

  • @sammonger4002
    @sammonger4002 6 ปีที่แล้ว +10

    It's interesting that he doesn't mention that n should be prime in addition of being large. That is an aspect equally as important as its size which could easily break the encryption (if n isn't prime). There was even a defcon panel (2016 I think) that discussed this very problem and how it is often ignored.

    • @Legendarior
      @Legendarior 5 ปีที่แล้ว +1

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

    • @tissuepaper9962
      @tissuepaper9962 4 ปีที่แล้ว

      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.

    • @MarioFanGamer659
      @MarioFanGamer659 2 ปีที่แล้ว

      @@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.

  • @AbhishekSharma0318
    @AbhishekSharma0318 6 ปีที่แล้ว +27

    This was not that difficult!

  • @Starfuchs
    @Starfuchs 6 ปีที่แล้ว +144

    The clockface only goes up to n-1, (n mod n = 0). He forgot to change that too when he added the zero afterwards

    • @kpan
      @kpan 6 ปีที่แล้ว +5

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

    • @666Tomato666
      @666Tomato666 6 ปีที่แล้ว +1

      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

    • @kpan
      @kpan 6 ปีที่แล้ว

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

    • @aleksandarsavev
      @aleksandarsavev 6 ปีที่แล้ว +2

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

    • @kpan
      @kpan 6 ปีที่แล้ว +4

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

  • @YousifNael
    @YousifNael 5 ปีที่แล้ว +11

    g needs to be a primitive root of n for this to work.

    • @trogdorstrngbd
      @trogdorstrngbd 4 ปีที่แล้ว +4

      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.

    • @drewkavi6327
      @drewkavi6327 3 ปีที่แล้ว +2

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

  • @drewad0
    @drewad0 11 หลายเดือนก่อน +3

    All these years of hearing how "diffie helman is extremely complex" yet such a simple and easily understandable algorithm. Thank you so much for this!

  • @vibhavsharma9093
    @vibhavsharma9093 ปีที่แล้ว +2

    great video, just to clarify modulo math, ((g^a)^b) mod n = ( ( (g^a) mod n )^b )mod n,
    by using this we can generate same value from both side

    • @HarishNarayanan
      @HarishNarayanan ปีที่แล้ว

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

  • @VoilaTadaOfficial
    @VoilaTadaOfficial 6 ปีที่แล้ว +7

    I love these math versions. They help me understand it so much better than just the computer science bits. Please do more of these!

  • @Syldar
    @Syldar ปีที่แล้ว +4

    This is the most interesting channel about computer science. I’ll never be as much grateful as I would like to be. Thanks a lot for sharing these.

  • @jasper265
    @jasper265 6 ปีที่แล้ว +3

    It's annoying how he simplifies his notation and then just forgets to explain a part because it wasn't in his simplified explanation.
    In particular, I know that (a^b)^c = a^(a*b) and that's what he used to explain it. However, we need (a^b mod n)^c mod n = a^(b*c) mod n. It seems the latter is also true, but because of his simplified notation, he forgets to explain it...

    • @aszxdcfv0509
      @aszxdcfv0509 2 ปีที่แล้ว

      Yeah! I had to do a bit of googling to find out what’s happening. At least to me, the exponent part is quite familiar high school level of math but the modular calculation is what I’m not familiar with.

  • @DicoTheRedstoner
    @DicoTheRedstoner 6 ปีที่แล้ว +1

    The video claims that Alice knows g^b and Bob knows g^a once they're sent, but they only know the remainders of these values. He didn't mention this or explain how they still get the same shared secret. Disappointing

    • @BRUHItsABunny
      @BRUHItsABunny 5 ปีที่แล้ว

      (g^a mod n)^b mod n = g^(a*b) mod n
      He simplified his notation... and with it his explanation

  • @supdawg7811
    @supdawg7811 6 ปีที่แล้ว +8

    Yeah but you never talked about if (g^{a} mod n)^{b} is the same as (g^{b} mod n)^{a}. As in, does g^{a^{b}} = g^{b^{a}} hold in the modulo field.

    • @Aidiakapi
      @Aidiakapi 6 ปีที่แล้ว +4

      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.

    • @Dsiefus
      @Dsiefus 6 ปีที่แล้ว +2

      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.

    • @yondaime500
      @yondaime500 6 ปีที่แล้ว +2

      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.

    • @AndersJackson
      @AndersJackson 6 ปีที่แล้ว +1

      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.

  • @vorniy
    @vorniy 6 ปีที่แล้ว +43

    But isn't the public value "g^a mod n" instead of "g^a" or is that irrelevant, because "(g^a mod n)^b mod n" is the same as "(g^b mod n)^a mod n"?

    • @evge
      @evge 6 ปีที่แล้ว +9

      was wondering the same thing, can someone answer

    • @ChenfengBao
      @ChenfengBao 6 ปีที่แล้ว +8

      You can put "mod n" anywhere or nowhere. It doesn't make any difference as long as the end result is mod n.

    • @johnmiller8884
      @johnmiller8884 6 ปีที่แล้ว +32

      That "mod n" is important for keeping things secret. Remember that it is the *discrete* logarithm problem that is hard. If I give you `g` and `g^a` you can find `a` you could find `a` by log_g (g^a). That is what a logarithm is: the inverse of exponentiation. The 'mod n' piece is what make the problem hard because you don't know how many times you have looped back to 0 again. For any given g and n there actually might be a lot of values for a that would work, *but* if g and n are relatively prime (they have no common factors) then there is exactly one value a less than n that will result in g^ mod n. That is why the subtle mention that g and n are large *prime* numbers. The math still works if they are not, but it makes the problem of finding a much easier.

    • @efeyzee
      @efeyzee 6 ปีที่แล้ว +13

      Tested with a couple values, (g^a mod n)^b mod n seems to equal (g^b mod n)^a mod n .

    • @philippetrov4881
      @philippetrov4881 6 ปีที่แล้ว +9

      Yes, it is.
      And yes, "(g^a mod n)^b mod n" is the same as "(g^b mod n)^a mod n"

  • @RineezAhmed
    @RineezAhmed 2 ปีที่แล้ว +1

    In previous video Mike said the math is very complex so separated out to another video. Now by the end of this video Mike says the math is not very complex it's simple. 🙃
    Actually it was hard for me to understand how (g^a mod n)^b became (g^ab mod n) . It felt so counter intuitive to me that I had to test the math with several sample values before I could convince my brain it is true.

  • @Caelum1337
    @Caelum1337 6 ปีที่แล้ว +1

    Alice sends her key (g^a mod n), but you assume that (g^a mod n)^b = (g^ab mod n) is that correct? I wished you proved your assumptation

  • @spuddo123
    @spuddo123 2 ปีที่แล้ว +4

    I love how this all works on the fact that (((a^b)%x)^c)%x=(((a^c)%x)^b)%x

  • @sondoanvan5161
    @sondoanvan5161 ปีที่แล้ว +1

    thanks your video is very helpful, but i have a question let's say in signal or realtime chat webapp WhatsApp using Diffie Hellman, on server side only public key is saved. So I have a question where is the private key stored for each user when they log in so that they can be retrieved and every time you log in on another device, how do you get that user's private key? thanks and hope you can help me answer my question

  • @kamism770
    @kamism770 2 ปีที่แล้ว +1

    Does Alice and Bob gonna share the exponent values with the modulo operation or without it at the first exchange ? Cuz he first said said that both of them gonna use the modulo operation but he completed the analogy with only the exponents values (g^a and g^b)

  • @trevordobbertin6469
    @trevordobbertin6469 6 ปีที่แล้ว +4

    It would be awesome if you guys did some podcasts. I learn so much from you guys and it would be great to listen while in the car or at school. Thanks guys.

  • @AustrianAlrounder
    @AustrianAlrounder 2 ปีที่แล้ว +1

    Amazing video, but how do we know that (x^a mod n)^b is the same as (x^a)^b mod n? 🙂

  • @DavidPsurny
    @DavidPsurny หลายเดือนก่อน +1

    3:32 How can Alice perform (g^b)^a when she receives ((g^b) mod n) from Bob? Alice does not know the value of (g^b).

    • @danielf.7151
      @danielf.7151 12 วันที่ผ่านมา

      it's not mentioned, but (((g^b) mod n)^a) mod n is the same as ((g^b)^a) mod n. this applies zo adfition and multiplication as well

  • @garydunken7934
    @garydunken7934 7 หลายเดือนก่อน +1

    Bad camera positioning. Keep it steady on the page, most of the time his head was in the way.. damn.

  • @regdenied3306
    @regdenied3306 6 ปีที่แล้ว +10

    It is quite misleading that after they exchange (g^a)mod n and (g^b)mod n Mike goes on as if alice knew the value of g^b and bob g^a and even saying that those values would now be public, which is simply wrong.

    • @ChrisStavros
      @ChrisStavros 3 ปีที่แล้ว

      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.

  • @jlamothe2
    @jlamothe2 4 ปีที่แล้ว +1

    X mod n will be in the range of 0 to n-1, not 0 to n.
    I'm also a little unclear as to how we get g^(a*b) mod n. Bob, for instance would have g, n, b, and g^a mod n. I think it might be the same as (g^a mod n)^b mod n, which Bob could compute, but I'm not sure if that's correct, or if so, why.

    • @xiezhenhaoa
      @xiezhenhaoa ปีที่แล้ว

      According to Congruence modulo, (a mod n) * (b mod n) = a*b mod n, so (g^a mod n)^b mod n = (g^a)^b mod n

  • @MaxDiscere
    @MaxDiscere 6 ปีที่แล้ว +12

    why do it have to be prime numbers?

    • @evankivolowitz4788
      @evankivolowitz4788 6 ปีที่แล้ว +5

      Because if you can easily factor g^a or g^b, then you can find a or b in polynomial time (easy to do on technology we have today).

    • @kamoroso94
      @kamoroso94 6 ปีที่แล้ว +7

      It also makes the number modulo n more uniformly distributed.

    • @Dsiefus
      @Dsiefus 6 ปีที่แล้ว +4

      Because otherwise it wouldn't be a field.

    • @jackflash9123
      @jackflash9123 3 ปีที่แล้ว

      @@evankivolowitz4788 This is not true. What you are thinking of is prime factorization (getting the product in primes of a number) but that does not come into play here. Also you never send g^a or g^b but the remainder of that number after mod n. The reason for prime numbers is, that you distribute possible secrets on the whole range 0, ..., n-1.

  • @MSA_THE_DEV
    @MSA_THE_DEV 3 ปีที่แล้ว +1

    As a backend developer, I have to say keeping secrets from the server is a bit offensive to me.

  • @jaytimbadia2191
    @jaytimbadia2191 4 ปีที่แล้ว +1

    Nice video Computerphile. Q: What if Alice and Bob gets their private number a & b same? Can we find the chance of that scenario?

    • @parveenakhtar486
      @parveenakhtar486 3 ปีที่แล้ว

      They both are still going to get the same answer

  • @sieevansetiawan4792
    @sieevansetiawan4792 4 ปีที่แล้ว +1

    Technical question. Does the value of a, b, g, n are permanent, or they get changed periodically.

  • @programmercouple
    @programmercouple 3 ปีที่แล้ว +1

    There is no better explanation of the "Diffie-Hellman key exchange".

  • @SkylerGhostly
    @SkylerGhostly 4 ปีที่แล้ว +1

    G TO THE A TO THE B TO THE C, COMPUTERPHILE IS THE BEST YOU SEE

  • @pranit_7D
    @pranit_7D ปีที่แล้ว +1

    This somehow made more sense than the color version lol

  • @dannyniu4268
    @dannyniu4268 6 ปีที่แล้ว +5

    What about Elliptic Curve Diffie Hellman??!

    • @americanswan
      @americanswan 6 ปีที่แล้ว +2

      Danny Niu
      I wish them luck in finding someone who can explain this in a simple manner.

    • @666Tomato666
      @666Tomato666 6 ปีที่แล้ว

      the problem is defining what "adding points on an elliptic curve" means, after that is simple, you just add points instead of exponentiate and the algorithm still works - both alice and bob select a random number a and b, exchange g · a and g · b, add to it their own secret part to get g · a · b and g · b · a, respectively, which will be the same value - mission accomplished

    • @americanswan
      @americanswan 6 ปีที่แล้ว

      666Tomato666
      I'd like to see it explained as easily as this video.

    • @shumymikaball
      @shumymikaball 5 ปีที่แล้ว

      Once the aritmetic is defined, is the same - a.b×G = b.a×G

  • @DimMyPrp
    @DimMyPrp 6 ปีที่แล้ว +2

    Yeah! Best explanation on key exchange ever. Thanks to both videos I understood it instantaneously. A test on paper and mental arithmetic worked like a charm.
    Thanks :-)

  • @aanesijr
    @aanesijr 6 ปีที่แล้ว +1

    Is it weird that I found this easier to understand than the one with the colors?

  • @andreafeletto
    @andreafeletto 6 ปีที่แล้ว +1

    How can Alice do [g^(ab) mod n] if she gets [n^b mod n] from Bob? Shouldn't she do [(g^b mod n)^a mod n]?

  • @salerio61
    @salerio61 6 ปีที่แล้ว +34

    The clock-face numbers should go from 0 to (n-1)

    • @OXXOI77777
      @OXXOI77777 6 ปีที่แล้ว +3

      You are technically correct, the best kind of correct

    • @almightyhydra
      @almightyhydra 6 ปีที่แล้ว +1

      Martin O'Donnell Or even 1..n-1, as this is a multiplicative group.

    • @CJBurkey
      @CJBurkey 6 ปีที่แล้ว

      I'm glad a lot of people saw it.

    • @potatopassingby
      @potatopassingby 6 ปีที่แล้ว

      thank you. i kept thinking about it and it was so hard to concentrate on the video haha

    • @xXThePr0Xx
      @xXThePr0Xx 4 ปีที่แล้ว

      And it should start at 1 because 0 isn't an element of the multiplicative group Z*_n

  • @lynx-titan
    @lynx-titan 6 ปีที่แล้ว +1

    g must be the generator of cyclic group of n (the set 0..n-1) by repeatedly applying the group operation (exponent, modulo)

  • @SouravTechLabs
    @SouravTechLabs 6 ปีที่แล้ว +1

    Can you (Dr. Mike Pound) please do a video on Linux security, and its flaws for being open-source?

  • @deckard5pegasus673
    @deckard5pegasus673 3 ปีที่แล้ว

    Video for the mathematically inclined...then starts to explain exponent multiplication, which supposedly any highschool graduate "should" know.... but doesn't
    Great video BTW.

  • @giusepperana6354
    @giusepperana6354 8 วันที่ผ่านมา

    Your explanation seems to be skipping a part though. You're not doing (g^a)^b, you're doing (g^a%n)^b, so why does that still work?

  • @johnpugh24
    @johnpugh24 6 ปีที่แล้ว +2

    Thanks for explaining, you do such a great job. Always my favourite computerphile presenter.

  • @necorvartem6803
    @necorvartem6803 2 ปีที่แล้ว +3

    He left the most interesting part out.
    (g^b % n)^a % n === g^a^b % n

  • @benjaminshropshire2900
    @benjaminshropshire2900 6 หลายเดือนก่อน

    The missing part is why (g^a mod n) is fast to compute even though the reverse is not.
    Tl;dr; g^a can be computed by starting with x_0=1 and and defining x_1=a_0^2 or x_1=x_0^2 * g and then doing the same for x_2 and so on. Making the right choices at each step (which is basically reading out the bits of a) you get g^a in at most log2(a)+1 steps.

  • @fv6
    @fv6 3 ปีที่แล้ว +1

    2:12 0 to n-1 not n

  • @xiezhenhaoa
    @xiezhenhaoa ปีที่แล้ว

    I don't really get it why it's difficult to crack the a or b. Assume calculating big 'A' takes 1ms, a=1000,000, a brute force to crack little 'a' will take 1000,000 rounds, which takes 1000,000ms=1000s.
    Is it the bigger the number, the slower the calculate process? Then it will be gradually slower and slower from 1 to 1000,000?

  • @fsxelw
    @fsxelw 6 ปีที่แล้ว +1

    After a 2 hour lecture at school I still didn't understand it. But after 7 minutes watching this vid I finally understand everything LOL

  • @sabriath
    @sabriath 6 ปีที่แล้ว

    a^b mod p = v
    a,p,v are known, looking to solve for b:
    a^b = v + p*n
    b = ln(v+p*n)/ln(a) where b must be an integer, solve cyclical 'n' where this is the case
    to do so quickly, start 'n' at 1, and solve the above equation, then repeat the following until you reach an integer: increase 'n' by 1 until it overlaps the next integer overflow, reduce by 1 and multiply by 'a'.
    The only downside....you need a computer that can hold a googol-digit number for calculation.

  • @FusionDeveloper
    @FusionDeveloper 5 ปีที่แล้ว

    So using addition for a key exchange won't work, since you could subtract to get the keys. Okay well that's step 1 I understand with numbers I can do in my head. I wish there were small number examples.

  • @nonserviam24
    @nonserviam24 ปีที่แล้ว

    I need someone smart to help me please. I cant figure out how to get to: g^ab mod(p)
    After exchanging values bob is left with (g^a mod p)^b mod p and Alice with (g^b mod p)^a mod p
    now substitute X = g^a mod p we get => X^b mod p
    NOW why is X^b = g^ab ?? Where does the mod go I dont get it

  • @233kosta
    @233kosta 5 ปีที่แล้ว +2

    They're... they're indices. And remainders. I fail to see what's so complicated about them.
    This overstatement of difficulty seems to be a major contributor in putting people off from learning about any of this.

    • @baatar
      @baatar 5 ปีที่แล้ว

      Have you seen the hordes of nerds raging not at his understanding of the problem but what's essentially a typo? And this guy is a highly qualified mathematician. Forget about regular people giving it a crack.

    • @trogdorstrngbd
      @trogdorstrngbd 4 ปีที่แล้ว +1

      The basic idea is actually quite simple -- just high school mathematics, really. The legitimately hard part is figuring out the appropriate restrictions on the parameters and proving that there isn't a shortcut to calculate a from g^a (mod n).

  • @Benepstein97
    @Benepstein97 6 ปีที่แล้ว +1

    If you know g^a and g^b publically, why can't you just do logbase_g(g^a) to get a?
    Also, if you are just taking ((g^a)^b)% n and ((g^b)^a)%n why are you calculating (g^b)%n or (g^a)%n? Just for an explanation of modulus?
    Thanks!

    • @HalfgildWynac
      @HalfgildWynac 6 ปีที่แล้ว +2

      The thing is, an observer does not know g^a and g^b. If you steal the information Alice and Bob exchange you will only know their remainders when divided by a large prime number. Calculating a logaritm on an integer ring is computationally difficult for large numbers.
      Try solving these:
      • which power of 2 gives a remainder of 3 when divided by 5?
      • which power of 6 gives you a remainder of 5 when divided by 11
      • which power of 2 gives a remainder of 12 when divided by 19?
      • which power of 2 gives a remainder of 20 divided by 37?
      • 2^x % 20323 = 55 (for some x < 20322). What is x?
      If I told you that 2^d = 8589934592 you would easily calculate my d.
      However if you only know that 2^d % 53 = 31 or 2^d % 20323 = 8877 it is fairly hard to tell 2^d exactly.
      Of course, the function is in principle reversible. Only it may take you QUITE some time to reverse it for primes much, much bigger than 53, 20323, 55001, or 567877.
      This is the reason discrete exponentiation is used here. Calculating a^b (mod p) is reasonably fast even for a large p. Figuring out an X such that a^x = C (mod p) may be very time consuming for the same p (unless you are extremely lucky).

    • @HalfgildWynac
      @HalfgildWynac 6 ปีที่แล้ว

      Here is an example with the fairly small n=6997 as a prime and 2 as our g.
      Let Alice choose a=161 and Bob choose b=1630. These values remain secret.
      Alice calculates 2^161 (mod 6997) = 283
      Bob calculates 2^1630 (mod 6997) = 2001
      They can send each other these two values-theoretically, through a channel they KNOW someone is actively listening to.
      Now Alice can calculate (2^b)^a (mod 6997) = 2001^161 (mod 6997) = 5296
      And Bob can calculate (2^a)^b (mod 6997) = 283^1630 (mod 6997) = 5296
      However, if you only knew that N=6997 and also that 2^a → 283 and 2^b→2001 you'd have to find a or b first. Only then you would be able to deduce where 2^ab lands at.

  • @ianpatrick23
    @ianpatrick23 2 ปีที่แล้ว +1

    Fantastic explanation of the mathematics behind this encryption!

  • @flockenlp1
    @flockenlp1 4 หลายเดือนก่อน

    You are why I am confident I won't fail my Safety and Security module. Mike is exceptional at communicating these concepts!

  • @Makker_1
    @Makker_1 3 ปีที่แล้ว

    If alice can take g^b then it is public right and that would mean you could find out b right and then just put (g^a)^b) mod n and you got the key??? But also you can't get ((g^a)^b) if the only number you get from alice is (g^a) mod n...

  • @herminencreve246
    @herminencreve246 4 ปีที่แล้ว +2

    When we start to go inside the cryptography's math we always face the formula : a^b mod n.
    But if a and b are huge number, how in the world can we compute a^b ?
    To work out a^b mod n ?

    • @maybelbdidit
      @maybelbdidit 4 ปีที่แล้ว

      Thats where floating point and mantissa stuff comes in iirc

    • @ChrisStavros
      @ChrisStavros 3 ปีที่แล้ว

      @@maybelbdidit You don't recall correctly. a^b for large a and b is arbitrary precision integer arithmetic, not floating point.

  • @jackflash9123
    @jackflash9123 3 ปีที่แล้ว

    3:44 Bob is sending (g^b mod n) and not g^b without modulo n. Else it would be simple to extract b. But the result of "(g^b)^a mod n" is the same as "(g^b mod n)^a mod n".
    Was that him saying "I change notation to save space"?

  • @hovhadovah
    @hovhadovah 2 ปีที่แล้ว

    I'm confused. At the start, you said that Alice calculates g^a mod n and sends that to Bob, and Bob calculates g^b mod n and sends that to Alice. But then you said that Alice is going to take Bob's result and do: (g^b)^a mod n. But shouldn't this actually be (g^b mod n)^a mod n? Because Bob didn't calculate just g^b-he calculated g^b mod n.

  • @gerardligonde4083
    @gerardligonde4083 3 ปีที่แล้ว

    The agonizing forgery maternally joke because xylophone neurochemically stop into a colossal keyboard. skinny, changeable scissors

  • @fabriziodutto7508
    @fabriziodutto7508 5 ปีที่แล้ว

    Why the mod n disappears when Alice (or Bob for his part) get (g^b mod n), how managed Alice to get (g^b) from (g^b mod n), to perform (g^b^a) mod n ?

  • @Robbebeest
    @Robbebeest 6 ปีที่แล้ว

    Shouldn't g^b mod(n) be in the public domain instead of g^b? Because with g and g^b in the public domain one can calculate b.

  • @TheGameFreak013
    @TheGameFreak013 6 ปีที่แล้ว

    is alice sending [(g^a)mod n] over to bob or just [g^a]? if its the former, then how does bob figure out what [g^a] is? if its the later then shouldnt it be pretty easy to figure out a and whats the point of mod n then?

  • @MalevolentProphecies
    @MalevolentProphecies 2 ปีที่แล้ว

    Is it important for the encryption key how many times we go around the clock to get to the answer? Otherwise surely you would only have to brute force numbers zero to n?¿

  • @SanctumZero
    @SanctumZero 6 ปีที่แล้ว

    If you actually knew g, n, g^a, and g^b like the drawing would lead you to believe towards the end of the video, you could just go a = Log(g^a)/Log(g)

  • @SH-vz8ef
    @SH-vz8ef 2 ปีที่แล้ว

    At 4:47 it’s been said that we know g^a and g^b, but shouldn’t it say we know g^a mod n and g^b mod n?
    If g is public and g^a would be public too, we could calculate the value of a using the logarithm of g for g^a, couldn’t we?

  • @lherfel
    @lherfel ปีที่แล้ว

    4:45 when he writes g^a and g^b as being made public, he should have said and written g^a mod N, and g^b mod N, were made public. thanks for explanation.

  • @DerKommentator98756
    @DerKommentator98756 4 ปีที่แล้ว

    Everywhere are for example purpose this little numbers. But what number range do
    a
    b
    g
    n
    actual need to be in a real life use case? What would be a small prime number 'g' be?
    Are 2000-4000 some legit values in a real implementation or are there some more standardized values?

  • @CFPANDRADE
    @CFPANDRADE 5 ปีที่แล้ว

    I don't understand how they know g^a or g^a publicly, if you know G and also G^A its easy to calculate A, the public key sent should be g^a mod n to make it unsolvable , or i'm wrong?

  • @NoobLord98
    @NoobLord98 6 ปีที่แล้ว

    But if g^a mod n and g^b mod n are the values sent through public space, then how does A figure out what g^b is from g^b mod n without knowing b? And of course vice versa, B figuring out what g^a is only knowing what g^a mod n is?

  • @tareqazzouni6240
    @tareqazzouni6240 11 หลายเดือนก่อน

    Thank you for the amazing explaination! One thing confused me about the circle... it should go from 0 to n-1 and not n right?

  • @grandfiore5573
    @grandfiore5573 ปีที่แล้ว

    Please, a remake without Mike's head blocking our view of him writing! Haha

  • @_ashout
    @_ashout 2 ปีที่แล้ว

    How can the computer calculate "g^a"? Wouldn't it be a infeasibly large number? I know that it doesn't have to store all of it since its "g^a mod n" but still how does the computer even calculate it?

  • @thomascreel6522
    @thomascreel6522 5 ปีที่แล้ว

    @3:55 this doesnt make sense, g^a isnt public, g^a mod n is public. for instance, bob would be doing this: g^(g^a mod n)^b mod n?

  • @davidpanic
    @davidpanic 5 ปีที่แล้ว

    Couldnt you man in the middle this exchange???? You exchange keys with bob and allice and then decrypt and reencrypt in the middle...

  • @Musk_Melon_Fruit
    @Musk_Melon_Fruit 11 หลายเดือนก่อน

    If u know g and g^a then it shouldn’t be that hard to calculate a
    This makes me wonder that g^a (likewise g^b) should not be available publicly and that then raises the question of how the eventual key between alice and bob is established i.e. g^a*b mod n

  • @logangaastra4679
    @logangaastra4679 3 ปีที่แล้ว

    Small knitpicking, but you shouldn't have put both the 0 and the n on your circle. You would be implying there are n+1 elements.

  • @bm-ub6zc
    @bm-ub6zc 2 ปีที่แล้ว

    2:43 Watch his face after the question is asked. Like he's thinking "Gosh ... that simpleton again ..." 😂😂

  • @39dz
    @39dz 5 ปีที่แล้ว

    It would be nice to fix this video with misleading "g^b is public now" and not explaining at all that (g^ab mod n ) is the same as (g^a mod n)^b
    . If someone really wants to understand it, this part is ruining it.