0
$\begingroup$

It seems to me an exhaustive search would simply try to use all the possible bit combinations of a key, while factorization is some mathematical formula for determining the key? When discussing the NSA's cryptography "breakthroughs" some articles discuss factorization as the contributing factor. However, others go further and mention that they have only found a flaw in how some programs use factorization. I guess I'm not understanding how that term should actually be used as it relates to cryptography.

$\endgroup$
1
$\begingroup$

Your summary of exhaustive search is essentially correct; the attacker just tries every possible key until he finds one that works. This works against almost any cryptosystem (exceptions: OTP, secret sharing, quantuum cryptography). It's not practical against any modern system (mostly because 'has a key too large to be brute forced' is an essential attribute of any modern system).

Factorization is not a generic attack; instead, it is attack on certain public key crypto systems (mainly RSA). With RSA, the public key contains a composite number; if someone where again to derive its factorization, they could reconstruct the private key. That is, if someone could factor, they could break RSA. However, a breakthough in factorization would affect only RSA (and a handful of other systems that are not used much in practice); there is no known way to use factorization to attack (say) AES, SHA-2 or Elliptic Curve Cryptography.

$\endgroup$
1
  • $\begingroup$ @AnotherTest: no, there is no known way to use a factorization blackbox to attack DH (which uses a prime modulus). $\endgroup$
    – poncho
    Nov 2 '13 at 19:10

Your Answer

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