4 ms·

At a guess, it was likely a tradeoff between security and computational cost. I used to do freelancing for an ICT magazine and in early-to-mid 00s ran some num

by bostik 6y ago

At a guess, it was likely a tradeoff between security and computational cost. I used to do freelancing for an ICT magazine and in early-to-mid 00s ran some numbers, as part of an article I did on limitations of applied cryptography. You can't do 1024-bit math on 32-bit or even 64-bit integers. Not without bignum libraries, which in turn make use of applied number theory. Under the hood the multiplication of two large numbers is an O(n^2) operation. Performing an RSA or DH calculation with decent desktop computer in ~2003 took about 20ms with a 1024-bit number, and 80ms with a 2048-bit number. IIRC the first was expected to be theoretically breakable in a decade or so, assuming Moore's Law held true. The second was thought to be computationally infeasible for at least 100 years. These days the professionally paranoid use 4096-bit keys. (Or more recently, the nice 25519 curve which is more compact.) So raising the security margin from "reasonable" to "paranoid", back in the day, would have required 4x the hardware investment to serve the same amount of traffic, and it would have imposed severe latency issues for everyone. We also have to consider the fact that most commercial secrets have a shelf life of years to a couple of decades. So before "E2E for everyone" became a thing, there simply wasn't widespread interest for crypto that could protect personal secrets for a lifetime. With regards to using cryptography for personal privacy, cypherpunks were well ahead of their time. It's only become a mainstream issue in the last 5 years or so.

MaximumYComb 6y ago
Isn't multiplication of two integers with length n O(nlog(n)) with the Harvey-Hoevan algorithm? Is the limitation our 64-bit computers?
- wbhart 6y ago
  Harvey-van der Hoeven. And yes it is. But this is an asymptotic cost meaning you have to have absolutely enormous integers before the cost will be lower than the old algorithm. In fact, the crossover is so large it is quite possibly out of the range of anything we'll practically ever compute. In particular, crypto typically works with integers zillions of times smaller, so you certainly don't want the Harvey-van der Hoeven algorithm for that.
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 ago
  I 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 ago

by bostik 6y ago

MaximumYComb 6y ago

Isn't multiplication of two integers with length n O(nlog(n)) with the Harvey-Hoevan algorithm? Is the limitation our 64-bit computers?

wbhart 6y ago
Harvey-van der Hoeven. And yes it is. But this is an asymptotic cost meaning you have to have absolutely enormous integers before the cost will be lower than the old algorithm. In fact, the crossover is so large it is quite possibly out of the range of anything we'll practically ever compute. In particular, crypto typically works with integers zillions of times smaller, so you certainly don't want the Harvey-van der Hoeven algorithm for that.

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 ago
I 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 ago