Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
A breakthrough in factorization would have a major impact on cryptography as a whole. You could use the chinese remainder theorem to solve the DLP in a multiplicative group of integers modulo n. Protocols like Diffie-Hellman (in this group, which is widely adapted) would be broken as a consequence. This would be a cryptographic apocalypse. –  AnotherTest Nov 2 '13 at 19:05
    
@AnotherTest: no, there is no known way to use a factorization blackbox to attack DH (which uses a prime modulus). –  poncho Nov 2 '13 at 19:10
    
Yes, that's true. My mistake. It is possible that the DHP could be solved by solving the DLP though. Still, this doesn't take away the huge impact. –  AnotherTest Nov 2 '13 at 19:36
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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