0
$\begingroup$

It seems like there are a lot of algorithms in number theory which I would classify as "deterrent" algorithms -- for example the various number field sieves for factoring, Coppersmith's algorithm for discrete logarithm -- which effectively serve as a benchmark for the cost of attacking a cryptographic protocol. They have immense value to society by justifying minimum bit sizes needed to make attacks intractable.

But I wonder: do these algorithms actually get used on a regular basis? After all, if there are systems that can be successfully attacked by these algorithms, then those systems are not properly designed.

$\endgroup$
  • $\begingroup$ Do you suppose that breaking RSA is the only situation where one would want to factor an integer? $\endgroup$ – fkraiem Aug 13 '17 at 4:34
  • $\begingroup$ No... but factoring a large integer -- is there any situation other than attacking a cryptosystem? $\endgroup$ – Jason S Aug 13 '17 at 12:52
  • $\begingroup$ Certainly, for example in the course of their research a number theorist may want to do that to experimentally verify a conjecture or theorem. $\endgroup$ – fkraiem Aug 13 '17 at 12:59
6
$\begingroup$

Technically, yes.

The number field sieve was used to break a 768-bit RSA challenge.

What is probably the current best effort (unclear whether it's still ongoing) to break a 130-bit elliptic curve challenge uses Pollard's rho algorithm.

Wikipedia lists many more references.

I say ‘technically’, of course, because these aren't ‘attacks’ on real systems; they are attacks on challenges to demonstrate the cost of the attack by academics who get to win grant funding in exchange for performing it, which we hope is a good proxy for the cost to real attackers. It is exceedingly unlikely that these academics would intentionally attack real systems, too, because the ethical issues are more obvious than the back door in Dual_EC_DRBG, and nobody else who might carry them out is motivated to disclose their cryptanalytic capabilities.

I would guess that well-funded intelligence agencies such as the NSA devote some resources to NFS, Pollard's rho, etc., for stupidly small parameter choices made by people who don't know any better, or by people who should have known better but were under the influence of the selfsame state intelligence agencies, or in historical systems—such as major internet protocols that were designed when US crypto export controls were in effect.

But mostly they probably spend effort on working around the crypto rather than breaking it, since on a scale from one to ten of sturdiness, modern cryptography rates somewhere around a nine and most modern so-called software ‘engineering’ rates somewhere negative.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.