0
$\begingroup$

Nowadays, private key systems like AES have replaced RSA. Even for digital signatures, people mostly use ECC, so even if an efficient integer factorization algorithm is made, would it be a threat to digital security anymore? Or is this danger just an idea in the past?

$\endgroup$
0
3
$\begingroup$

AES is a secret-key cryptosystem, and as such can't replace a public-key cryptosystem like RSA, or an ECC-based one.

Examine how the certificate of a web server is signed and you'll see RSA is far from dead, and actually remains king when it comes to static signature of certificates, for excellent reasons. If you look at the present server, not only the certificate is RSA-signed, but the key signed is actually RSA.

Thus yes, an integer factorization algorithm faster than GNFS for balanced biprimes would be a big deal. If it makes factoring a 1984-bit (or even 1536-bit) RSA modulus borderline feasible for well-funded adversaries, or factoring a 1024-bit RSA modulus feasible for more casual hackers, it could be a threat to the current IT infrastructure. 2048-bit RSA is extensively used, or 1984-bit when 255 bytes is a sound barrier, 1536-bit on occasions, and 1024-bit in legacy systems including some door locks (but it's easy to kick these open or sneak in).

I'm far from ruling out we'll see the RSA-1024 (former) challenge openly factored in the next 5 years, or that this size is already factored covertly. I'm ready to bet we'll get there unless a global disaster strikes, and that it won't first be with a quantum computer.


Addition: when RSA is used for encryption, factorization of the public key remains a threat as long as the encrypted data remains of interest and did not leak. Thus even if Post-Quantum Crypto had a fast adoption rate (contrary to human nature of not changing what works unless that's indispensable within a defined time frame), factoring RSA moduli will remain of practical interest decades after.

$\endgroup$
5
  • $\begingroup$ Thanks alot man it was all the motivation i needed $\endgroup$ – Muhammad Usman Qureshi Dec 7 '20 at 9:53
  • 1
    $\begingroup$ My two pence: payment cards. Billions of them are in circulation, their security is based on RSA and the EMV Standard sets the max key length to 1984 bits. $\endgroup$ – tum_ Dec 7 '20 at 12:07
  • 1
    $\begingroup$ @tum_: Yes. And the EMV standard in turn does this because the length of the data field in a card APDU is coded on a byte, and can't exceed 255 bytes (or 256 depending on direction, but that's not universally supported) in the ISO/IEC 7816-3:1989 standard, reaffirmed 1997 from that standpoint. This limitation was worked around in the 2006 edition (the dreaded cases 2E, 3E, 4E, and subcases), but we're far from universal adoption of that workaround, and I can name at least two other incompatible workarounds. Plus bugs in the implementations of some workarounds. $\endgroup$ – fgrieu Dec 7 '20 at 12:41
  • 1
    $\begingroup$ @fgrieu I'm sure you remember this case back in Feb. 2000. The guy factored a key and forged an SDA card. I happened to work in Paris at that time, remember this being on TV. $\endgroup$ – tum_ Dec 7 '20 at 16:35
  • 1
    $\begingroup$ @tum_ Oh yes I do. That was damage control time. I talk about it in this answer, second bullet. I added your link. $\endgroup$ – fgrieu Dec 7 '20 at 16:55
2
$\begingroup$

Efficient factorization algorithm will not matter in the future not because of AES or ECC - AES is data encryption, RSA and ECC both can be used for key encapsulation and digital signature. Factorization will cease to matter in the future when "post-quantum" schemes are deployed, because they rely on completely different hard problems to achieve security.

$\endgroup$
1
  • 2
    $\begingroup$ Interesting, but (A) Where RSA is used for encryption, factorization of the public key remains a threat as long as the encrypted data remains of interest and did not leak. This makes factorization of RSA moduli interesting for many decades. (B) if IPv6 is an indication, the adoption of PKC will be slow. And then lack of IPv4s is a thing, and the when was predictable, when Quantum Computers usable for cryptanalysis won't be for a long time (an Apple ][ trounces any existing QC on a crypto workload), perhaps several decades, if not ever. $\endgroup$ – fgrieu Dec 7 '20 at 11:46

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.