Iran GPS Spoofing and the RSA Cipher

[Ian Mason]

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.