The existence of that K9 clique shows that public-key cryptosystems have gone to the dogs (sorry, bad pun!).

There is no reason to make a distinction between "really bad" (two identical keys) and "really, really bad" (two keys with a prime gcd). Both cases should be considered as completely insecure.

The latter is more insecure, since *anyone* could easily use Euclid's algorithm (which takes at most O(n²) time for n-digit keys) to obtain the common factor, then deduce the other factor by division (also O(n²), using the naive method). If a key is merely really bad, then only people sharing the key could factorise.

The title suggests that the solution is to switch from RSA to a single-secret system, whereas the actual solution is to make sure your random generator is in working order.

Agreed. An amenable solution is to seed a PRNG with an online source of pure random information (there is a quantum random bit generator, where the CAPTCHA is an advanced calculus problem, apparently). Once the random integer has been generated, it is fairly trivial to count upwards until a probable-prime is obtained (and, at those magnitudes, Fermat pseudoprimes are sufficiently sparse to ignore them completely). Sincerely, Adam P. Goucher

Better yet would be a website that verifies the suitability of your random number generator.  But once the Intel Ivy Bridge CPUs are released later this year, we will have a built-in random number generator based on physical noise, and all this pseudorandom number garbage will become obsolete.   --  Gene

________________________________ From: Mike Speciner <ms@alum.mit.edu> To: math-fun <math-fun@mailman.xmission.com> Sent: Thursday, February 16, 2012 7:44 AM Subject: Re: [math-fun] We don't need no stinking factorizer to break RSA... duh!!!!!!!!!

So, given that there's no limit on human stupidity, has someone put up a website (commercial, or public service) where you attempt to register your public RSA key and it tells you if it matches someone else's, or if it shares a factor with someone else's (in which case it informs the someone else[s] if they've registered), or if it is a weak key for some other reason (e.g., easily factored, easily guessed private exponent), or it says it's OK and registers it? I could imagine such a service provided by such entities as NIST [but would you trust the government?], some university, some industry organization such as IEEE or ACM, or some security software provider such as Norton or EMC/RSA.

--ms

On 2/14/2012 7:44 PM, Warren Smith wrote:

...

front page of NY Times just featured this paper

http://eprint.iacr.org/2012/064.pdf

which is hilarious! Just when you thought you'd seen the ultimate in human stupidity...

* Marc LeBrun <mlb@well.com> [Feb 17. 2012 16:55]:

...

="Eugene Salamin" <gene_salamin@yahoo.com> all this pseudorandom number garbage will become obsolete.

Perhaps not entirely; there could remain some utility in being able to, say, rerun simulations exactly.

Reproducibility is very often an absolute must (e.g. for physical simulations whose results get published). I do not think an on-chip random number generator is needed for crytographic purposes, we just need a decent entropy source (crank up input gain on the sound card and cycle-and-XOR 1024-bit chunks over 60 sec, this should be good enough, I speculate. Also some not-too-silly circuitry for <= 1 Dollar should do the job very well). Btw. /dev/random and /dev/urandom (under Linux) should do the trick already. In cases of paranoia: take a one minute stretch of images from your web-cam while moved around, feed into something like md5 or SHA. _Quality_ entropy.

* Mike Stay <metaweta@gmail.com> [Feb 17. 2012 19:25]:

[...]

Boxen running in a data center with only a solid-state hard drive (perfectly predictable seek times) and a network card where traffic is carefully distributed and very predictable have real troubles getting enough randomness.

Oh, I see. Get an FPGA board, implement a (deterministic) random number generator (with _very_ long period), and XOR in entropy from several independent noise sources (on that FPGA board, say 5 such at $3 each ("enterprise solution")). Should at the _very_ least give you, one 1024 (super-OMG!-)random bitstring per second. Given the (enormous) possible parallelism that an FPGA offers we may just run many deterministic generators (all of different periods, but the exact instance and state of the generator not accessible), XOR (an (entropy-) random choice of) them to get as much random bits per sec as the bus can transfer. Problem solved? No, people will not use it because they do not realize how bloody important the "random" part is.

...

Btw. /dev/random and /dev/urandom (under Linux) should do the trick already.

In situations like the one above, the server would either block on dev/random or be vulnerable because all the entropy has been depleted.

Yes, the "real" one of those two (can never remember which) does block if no usable entropy is available.

-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com

Does anyone know how much RSA enforces the two primes to be of similar size? I always thought that one should rather use a supersize key (say, 16k bits) and allow the primes to be of vastly different size (say, requiring the smaller one just being >=3000 bits). No collisions then! (Oh, wait, I assumed the "random" part non-ignored...)

* Eugene Salamin <gene_salamin@yahoo.com> [Feb 18. 2012 18:35]:

[...]

Buy FPGA board.  Buy FPGA programming software.  Program and debug FPGA.  Write software drivers.  Test and certify algorithm.  Enjoy your nice new pseudo RNG.

Alternatively, buy Ivy Bridge computer.  Enjoy Intel's nice new true RNG.

An RNG on (or at least near) CPU is a good thing[TM], no doubt. fxtbook citation (sect.1.30 "CPU instructions often missed", p.82-83): \item A random number generator, LHCAs (see section \jjvref{sect:lhca}) may be candidates. At the very least: a decent entropy source. The message I was replying to indicated a setting where "true" randomness would be exceedingly important. Also there are people who do FPGA designs as fast as a good programmer implements an algorithm within his/her core interest (i.e., in essentially no time). But after I see a good documentation of what the "nice new true" RNG exactly does I may well concede that that my idea is overkill. Note there once was (several years ago) an on-chipset RNG (by intel(?)) but that one was discontinued pretty much immediately (dunno why). best regards, jj

  --  Gene _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun