Hi All , so in a previous article i tried to explain how D-H works , and i hope I did a good job of it and hopefully there’s no questions , but how hard would it be for the person eavesdropping to reverse the “secret exponents” and guess the key? Remember that image ? let’s recap: Jerry and Simon agreed a and a number , while they were chatting about this there’s a third person “Random” that is listening to everything. prime base Next step Simon and Jerry will calculate a number and tell it each other, for example jerry will tell Simon: BASE to the SECRET EXPONENT modulo PRIME which translates to: 3667 ** 6531 % 2833 = 2642 So Jerry will tell Simon my Computed number is 2642. So how hard is it for “Random” to obtain the “secret exponent” with all the values that she had right now? to clarify “Random” equation should be something like: 3667 ** % 2833 = 2642 X is the value we want to know , if “Random” knows , then she will be able to know the secret exponent. X X This is called discrete logarithms , so to examplify this i will use smaller numbers: BASE=5 , PRIME=7 , RESULT=2 , SECRET = 10 5 ** 7 % 17 = 10 So far there’s no easy way to solve this backwards , it’s easy with small numbers , for example we could make a list of all numbers smaller than prime: So that would work in a way … but as you can tell it is sort of brute forcing , the catch is when you use a large prime number , something in the range of: (+100 digits) 2074722246773485207821695222107608587480996474721117292752992589912196684750549658310084416732550077 you can see the complexity drastically , the other catch is once you build this table , and build it in ! , how do you search over it ? as you see not impossible but very very slow. increases time efficiently So long prime numbers would add a lot of complexity to the reversing this modulo. One question that in a forum was how complex is to generate these numbers , and how fast is it ? specially of something. power Well what i found is that if the a compute want’s to know: 3 ** 17 OR 3 power of 17 The computer won’t do this: (it’s too slow) 3x3x3x3x3x3x3x3x3.... Instead there’s an operation called which simplifies this greatly , the idea is the following: repeated squaring , This is way faster than multiplying , times :) 3 17 So to wrap up , Some arithmetic operations are very easy/doable one way but very complex the other way around , hence D-H popularity .
