It seems to me an exhaustive search would simply try to use all the possible bit

Question

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.

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.