Sunday, May 17. 2015About the supposed factoring of a 4096 bit RSA keyComments
Display comments as
(Linear | Threaded)
Even though your own research didn't end up where you first thought it might, it still clearly paid off by providing the evidence to debunk this latest self-promoting FUD-propagation. So thanks for that; I'll be sure to direct those in a panic on freenode here instead of Mircea's blog.
So in your paper you write "It is unknown to me what the origin of the other two keys is and why they were broken in such a way." Your post seems to imply you are more certain now. What changed?
I don't really know, but I talked to Nadia Heninger about it and she mentioned that they were probably created by some email software only used in Germany. She also mentions something in a talk she gave lately:
https://mvideos.stanford.edu/graduate#/SeminarDetail/Spring/2015/EE/380/9469
The process for hacking a key and finding the factors of a PGP or RSA type key is really no where near as hard as is believed. I will give a few hints
(1) The sum of any two prime numbers can be defined as Sum = Center^2 - Difference^2 where the high prime is Center + Difference and the lower prime is Center - Difference. (2) Center can be guessed approximately as SqrRoot(Sum)+1. (3) Validity checks can validate based on last digits of potential sums (4) A proposed square produces Sum - Center(guess)^2 = Difference(guess)^2. If Difference(guess) square root as integer produces a remainder then the guess is invalid. (5) Using ending digit validation for sums most guesses can be tossed out. (6) Factors are automatically derived as a pair by this means. The number of factors to process is reduced by the following means (a) the process is linear not geometric (b) the math only uses multiplication and shift right (c) The process reduces necessary processor time by a factor of several trillion times compared with the successive factors and such methods. I know people may not realize this but RSA process is easily cracked using this method. Instead of taking years it takes an hour or two and is easily handed to parallel processing. Cryptographic success with any known RSA Sum should be within reasonable times for any modest computer this way. The problem is guys you are shooting at the wrong end of the problem. Any time math problems become geometrically more complex your solution method is wrong.
If the high prime is (Center + Difference) and the lower prime is (Center - Difference), then surely, Center² - Difference² is the product of the two prime numbers and not the sum?
The sum of your two primes, (Center + Difference) + (Center - Difference), is just 2Center.
Also, guessing Center "approximately" as SqrRoot(Sum)+1 is a very bad guess. The two factors of a 4096-bit key are likely both 2048 bits long, meaning that guess is possibly off by up to 2^2047, which is an absolutely huge space to search.
You seem to be describing Fermat's method of factorisation, which is well known and RSA keys are usually chosen to be resistant to factorisation using this method.
> For all we know today factoring is hard enough to make RSA secure (at least as long as there are no large quantum computers)
I find the mention of quantum computers here a bit misleading. In practice the factorisation problem (and the discrete logarithm problem which is also involved in the security of RSA) has proven that it's pretty hard, having hundreds of mathematicians working on it for decades without breaking. But it's not theoretically hard (not NP-complete) and the huge amount of work on it have given significant results (see https://en.wikipedia.org/wiki/General_number_field_sieve for instance) and that's why you need to use huge keys to get a correct security level (2048 bits is the bare minimum if you want to be safe). The work is still in progress (see Antoine Joux's latest work on the discrete logarithm problem http://eprint.iacr.org/2013/400) and I think that RSA is more likely to be abandoned due to this kind of works than by an hypothetical «large quantum computer». My two cents.
While large quantum computers aren't the only thing that could reasonably play a role in deprecating RSA, I think it's unfair not to mention them given that we already have an algorithm ready that would work if we managed to build one. Since the physics around it is unchallenged so far, it's an engineering problem and it's rarely wise betting on the impossibility of solving an engineering problem.
It's not just an engineering problem - the author of one of the most popular quantum factoring algorithms presented it as a interesting find, but not necessary applicable. There are two issues with quantum factoring:
- it starts with a superposition of all the numbers of the n-bit length - we don't know how to do it, is it even possible and given we can do it how to do it efficiently - quantum algorithm works with some probability and while it's ok for optimization problems - you get the best solution or a one really close to it, it's not that good in factoring - a bit off is as bad as 2047/2048 bits off. So while the quantum algo will give you almost perfect answer, still getting the single, correct one can take some time.
I'm no mathematician or cryptographer, but all people I asked think that there is no way the results of Joux can be generalized. They only apply to a very specific variant of the discrete log problem (in finite fields of small characteristics). This is interesting research, but irrelevant for any crypto in use.
I don't know what you mean by theoretically hard. There is no way with current knowledge to produce any proovably secure public key algorithms, even if you could base them on an NP-complete problem. That's a given in today's crypto, we always have to rely on plausible assumptions. But to the best of my knowledge there is nothing that even remotely comes close to endangering RSA with reasonable keys (2048 or bigger) - except quantum computers. |
QuicksearchAbout meInformationen über meine Arbeit als freier Journalist finden Sie hier.
Hanno Böck mail: hanno@hboeck.de jabber: hanno@hboeck.de GPG/OpenPGP key Hanno on Twitter Impressum Tagsaiglx asia asia2013 atomkraft bahn berlin blog bundestag cacert ccc certificate china co2 compiz copyright creativecommons cryptography datenschutz demonstration demoscene encryption english entropia esoterik ffmpeg film firefox freeculture freesoftware games gentechnik gentoo gpg gps hardware https javascript karlsruhe kazakhstan kde kino klima klimaschutz klimawandel kohle kohlekraft laptop linux lug mongolia murrhardt musik nintendo notebook openssl openstreetmap pgp php planet presse privacy religion router rsa russia security sha1 spam ssl strom stuttgart supermario talk tls train travel trip2011 umwelt umweltschutz video visa vorratsdatenspeicherung vulnerability web websecurity wlan xgl xorg xss ökologie überwachung
My pages
Picture gallery |
Tracked: May 18, 06:10
Tracked: May 18, 07:50
Tracked: May 18, 10:40
Tracked: May 18, 15:10
Tracked: May 19, 15:33
Tracked: May 20, 09:31
Tracked: May 20, 09:40