Diffie-Hellman key exchange <\/h1>\n\n\n\n
The Diffie-Hellman key exchange protocol<\/a> was published in 1976. Long story shorts it was designed to establish a secret key between two parties over a public communication channel (public means that it could be eavesdropped – I don’t cover the exact details of the algorithm as there are many many well written explanation over the Internet). The protocol more or less looks like the following:<\/p>\n\n\n\n To sum up, private component of the Diffie-Hellman protocol are: a, b, K, whereas public components are: P, G, A, B.<\/p>\n\n\n\n To find out what is the secret key K (remember, K = Ga*b<\/sup> mod P) we must find private values a and b. The a and b were used to generate publicly available A and B so maybe it would be a good idea to break them. To extract a from A and b from B we must win through a discrete logarithm problem<\/a>. It basically states that if you know a, m and c it is hard to find b such that:<\/p>\n\n\n\n ab<\/sup>=c mod m<\/strong><\/p>\n\n\n\n If you look closer that is exactly what we want to get: a and b from A and B, i.e. Ga<\/sup> = A mod P and Gb<\/sup> = B mod P assuming we know G, B, A and P (which are publicly available).<\/p>\n\n\n\n Once we have the background of the problem the question is, how we can solve discrete logarithm problem? The most obvious idea is to brute force by checking a and b values starting from 1 up to the P-1. This method, however, is not feasible if we are talking about hundreds digit numbers. One way to ease the problem is to use baby step giant step algorithm<\/a>.<\/p>\n\n\n\n The baby step giant step algorithm could be used to reduce the time complexity of the DLP from the linear complexity (O(N)) to the square root complexity (O(\u221aN)) hence the time decreases dramatically. However, the algorithm is based on a space-time trade-off (there’s no such thing as a free lunch). You can find quite good explanation in the wiki page among others: baby step giant step algorithm<\/a> so I don’t put it here. Instead, I present the implementation in C# and show some interesting benchmark. <\/p>\n\n\n\n You can find the implementation of baby step giant step algorithm alongside the brute force implementation and benchmark of both on my GitHub: <\/p>\n\n\n\n One thing that is unusual in my implementation is the If you run the If you run the In this post I presented the BigInteger<\/a> API for dealing with really large numbers and the practical usage of the API – breaking the discrete logarithm problem. One thing I missed in the BigInteger API is a method for computing modulo inverse. I had to implement the extended Euclidean algorithm ( Have a nice day, bye!<\/p>\n","protected":false},"excerpt":{"rendered":" Introduction C# is a great and mature programming language. In general, the whole .NET environment which I work with on a daily basis is extremely…<\/p>\n\n
![\"\"](\"https:\/\/baldsolutions.com\/wp-content\/uploads\/2024\/06\/image-1.png\")
<\/figure>\n<\/div>\n\n\nBaby step giant step algorithm<\/h1>\n\n\n\n
Breaking DLP in C#<\/h1>\n\n\n\n
\n
limit<\/code> argument in the Compute<\/code> methods. This is a simplification of the algorithm because of my laptop limitation. For the sake of the blog post I limited the solution space by the limit<\/code> argument so that is computationally feasible (the value of limit<\/code> was chosen randomly, just to be greater than the solution of the DLP).<\/p>\n\n\n\nbaby-step-giant-step<\/code> (dotnet run, it takes ~30 sec) you can see that both algorithms (baby step giant step and brute force) find a solution.<\/p>\n\n\n\nbaby-step-giant-step-benchmark<\/code> (dotnet run -c Release, it takes ~20 mins) you can see the following results:<\/p>\n\n\n![\"\"](\"https:\/\/baldsolutions.com\/wp-content\/uploads\/2024\/06\/image-3.png\")
<\/figure>\n<\/div>\n\n\nSummary<\/h1>\n\n\n\n
BigIntegerExtensions<\/code> class) to get such a modulo inverse (I followed this wiki page<\/a>). Nevertheless, I am more than happy that there is such an API so that I can play with large number stuff in the language I am most familiar with. As always I encourage all of you to try it on your own!<\/p>\n\n\n\n