Re:Factoring may be easier than we think (2016)
by waynecochran on Sunday June 30, 2019 @10:31AM
(#20318379)
I have always wondered if the NSA has figured out how to factor effeciently.
[ Parent
| on HN ]
Re:Factoring may be easier than we think (2016)
by phicoh on Sunday June 30, 2019 @02:44PM
(#20319727)
One thing to remember here is that RSA can be used in 2 ways: to encrypt and to sign.
If RSA is used to encrypt (for example if you send an encrypted message using PGP) then factoring directly breaks the encryption.
In practice, a lot of encryption on the Internet uses RSA to sign the hash of a key obtained using Diffie-Hellman. In this case breaking RSA would allow the NSA to impersonate but not directly break existing communications. The problem with impersonation is that it is very noticeable.
What I find odd about the linked article is that it only talks about factoring. In practice, the discrete log. problem is just as important and is very much related to factoring.