Iran GPS Spoofing and the RSA Cipher
fw at deneb.enyo.de
Fri Dec 23 20:32:49 GMT 2011
* Ian Mason:
> Yes, you can in theory construct a PRNG from RSA. You'd however have
> to be insane to try.
In the literature, RSA is frequently used to construct other
primitives, followed by a proof that if those primitives lack certain
properties (which allegedly make them secure), then you can break RSA.
Blum-Blum-Shub (already mentioned) is a generator with such a proof.
There is a hilarious paper by Koblitz and Menezes, "Another look at
provable security II", <http://eprint.iacr.org/2006/229.pdf>, which
covers Blum-Blum-Shub in section 6.1. Choice quote:
| According to inequality (2), the BBS generator is secure against an
| adversary whose time is bounded by −2¹⁹². (Yes, that's a negative
| sign!) In this case we get a "better" result from inequality (3),
| which bounds the adversary’s time by 2⁻²⁶⁴. (Yes, that's a negative
More information about the ukcrypto