3 ms·
Multiplying 1024 bits by 1024 bits the naive way on a 32 bit processor involves 1024 multiply operations. Even in 2003, they were typically pipelined with a th
by londons_explore 6y ago
Multiplying 1024 bits by 1024 bits the naive way on a 32 bit processor involves 1024 multiply operations. Even in 2003, they were typically pipelined with a throughput of one multiply per cycle[1], so you should be able to do that in ~1040 clock cycles. Which is 750 nanoseconds on a 1999 era Pentium 3.
Since DH key exchange isn't done on all the data, only to exchange keys, and no machine then or now was setting up 1 million encrypted connections per second, I don't see this as a performance bottleneck at all.
What am I missing?
[1]: https://books.google.co.uk/books?id=V5oACAAAQBAJ&pg=PA208 https://books.google.co.uk/books?id=V5oACAAAQBAJ&pg=PA208
- jcranmer 6y ago> Multiplying 1024 bits by 1024 bits the naive way on a 32 bit processor involves 1024 multiply operations. That's 1024 32-to-64-bit wide multiply operations. On x86, where regular mul is wide (it sets both edx and eax), that's the same as a regular operation. Some architectures that have just a MUL and a MULH instruction would make it two instructions. If you have neither, that would require 3 multiply instructions plus a few shifts. > Even in 2003, they were typically pipelined with a throughput of one multiply per cycle[1], so you should be able to do that in ~1040 clock cycles. The inner loop is much more than a wide multiply. You have to load the two words you're multiplying (although one of them should already be loaded in the outer loop). Then you need to two adds-with-carry, store the results back. Next you need to handle the extra carry bit, which in the most naïve case is another load, add-with-carry, store. And finally, you need the regular loop management instructions. That's 4 loads, 3 stores, 3 adds, and 1 multiply, repeated 1024 times. I don't know the exact port availability and timing of Pentium 3 processors, but if there's only one load /store port, and it's a 4-cycle latency operation, you're looking at probably 25-ish cycles per inner loop iteration, or about 25,000 clock cycles.
- labawi 6y agoI think RSA and DH call for exponentiation (modulo prime), not just multiplication. So multiply by 1024 and some significant efficiency derating as per sibling comment, and you should get close to 20ms.
- bostik 6y agoYeah, my bad. Meant to say "exponentiation". And if we're talking about precise terms, that should be prefixed by "modular". On the bright side, the brainfart triggered a lot of interesting discussion. :)