Iran GPS Spoofing and the RSA Cipher

[Florian Weimer]

* 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
| exponent!)