Iran GPS Spoofing and the RSA Cipher
Ian Mason
ukcrypto at sourcetagged.ian.co.uk
Fri Dec 23 13:08:59 GMT 2011
On 23 Dec 2011, at 09:28, Ben Liddicott wrote:
> That's true of any block cypher in CTR mode.
Indeed.
>
> Ben
> -----Original Message----- From: Brian Gladman Sent: Friday,
> December 23, 2011 8:03 AM
> I am NOT going to argue that this is the reason for using an RSA
> based keystream generator in this particular application but one
> potential advantage of such generators (see, for example, the Blum-
> Blum-Shub (BBS) generator) is that the n'th bit in the keystream can
> be calculated without having to run the generator up to this point.
The actual PRNG used by GPS for the M-code is classified. What is
known is that it generates a bitstream at 5.115 MHz that is used as a
DSSS spreading code. thus it has to be fast, and the time between
successive chunks of the bitstream being available has to be
deterministic (you can't hold up the modulation process waiting for
your next bit of keystream). The period of this code is likely to be
long, for example the older P-code is 6.1871 × 10^12 bits long.
It's a requirement of codes used with DSSS to be able to hop around in
the keystream to achieve correlation with the transmitted signal to
demodulate it. Thus you need a PRNG that has the properties Brian has
highlighted - the ability to get bit N from the keystream without
first generating bits 0..N-1. The older P-code takes a week to repeat,
you can't wait a week to try and get a lock on the transmitted signal!
Yes, you can in theory construct a PRNG from RSA. You'd however have
to be insane to try. RSA is highly computationally intensive, the time
of each RSA calculation is variable and it has properties that will
trip you up every time unless you are careful (e.g. if your message
has few enough significant bits it will pass through RSA encryption
essentially unencrypted). Using it this way is of a similar order of
foolishness as constructing a cartwheel from toothpicks glued together
when you've got a store full of well-seasoned timber waiting to be cut
to shape.
When one thinks of PRNGs one thinks of LFSRs and block ciphers in CTR
mode or one of the feedback modes. I have NEVER seen anyone in the
literature propose using RSA to construct a PRNG.
More information about the ukcrypto
mailing list