全球定位系统（GPS）军码协议有多复杂，为什么没法破解？

这个问题要从GPS的定位原理说起

首先，我们都知道GPS最基本的原理是测量信号从卫星发射到用户接收之间的延迟 $t$ 乘以光速 $c$ ，得到此时刻卫星到用户的距离 $l=ct$ ，当知道3颗星的位置和与用户的距离之后，我们就可以列三个方程求解用户的三维位置。实际上由于接收机的时钟不可能百分百精确，钟差 $\delta t$ 也要列入方程。所以GPS定位至少需要4颗星，列4个方程。

但是，由于GPS是无源系统，用户机只能接收信号，不能发射信号，所以我们习惯的测量反射时间的方式就明显不能用了，我们需要一种接收机只靠接收信号就能测量信号飞行时间的方式。GPS卫星广播的信号包括三种信号分量：载波、测距码和数据码。测距码又分为P码（精码）和C/A码，关系为

通常也会把C/A码叫做民码，

载波就是卫星信号的基础频率，然后在载波上调制测距码和数据码

随着GPS的技术更新，还有一些新的测距码加入，但是在本问题中只考虑P码和C/A码就足以说明问题，所以其他新的测距码姑且不提。

GPS测量距离的方式主要有两种：伪距法和载波相位法

伪距法就是利用上述的P码或C/A码进行定位，载波相位法通过测量载波在传输过程中延迟的相位来测定信号传输延迟的时间，从而进行定位。

对于伪距法

GPS的两种测距码都属于伪随机噪声码（Pseudo Random Noise，PRN ，伪随机码或伪码），在这一步，我们可以将其简单理解成短时间内不会重复的一组序列

然后GPS是怎么通过PRN定位呢？卫星通过一定算法 $f(t,s)$ (其中t为绝对时间，s为卫星编号)生成并广播PRN，接收机也按照相同算法生成PRN，那么就有两组相同的PRN，但是由于卫星发出的信号在传输过程需要时间，所以当卫星的PRN测距码到达接收机时必然落后于接收机产生的信号，如下图

第一行蓝色的信号就是卫星发出的测距码，第二行绿色的信号是接收机按照相同算法产生的信号，很显然卫星的信号由于传输的时间延迟，在到达接收机时比接收机产生的信号落后。这时接收机会尝试将自身产生的信号与接收到的卫星信号进行比对，然后发现往后移动 $\Delta t$ 时自己产生的信号和接收到的卫星信号对上了（第三行绿色信号）！那么接收机就可以确定这些信号在路上用的时间是 $\Delta t$ ，那么自己与这颗卫星的距离就是 $c\Delta t$ 。

通过上述描述，我们可以看出，伪随机码的周期 $T$ 不能太短，如果太短的话（例如正弦波），接收机往后移动 $T$ 也能把信号对上，往后移动 $2T$ 也能对上， $nT$ 也能对上，那么就乱套了，所以要用伪随机码，这样在一段比较长的时间里都不会重复。另外这种方式对接收机和卫星上的时钟精度要求也很高，因为要保证在相同的时刻产生相同的信号，而我们自己设定时钟的精度确实太低，所以要将接收机钟差也列入求解，也是因此GPS有了授时功能。并且传说中相对论在GPS的应用也是为了校准星载原子钟。

说了伪随机码的应用原理，下一步我们就要来说伪随机码是怎么产生的。伪随机码的产生是通过一个称为“多极反馈移位寄存器”的装置产生的。如下图是一个简单的4位的“多极反馈移位寄存器”。

如同大部分数字电路，“多极反馈移位寄存器”的工作也由时钟控制，按照时钟周期进行动作。在工作初始时刻，多极反馈移位寄存器的每一位都在置1脉冲作用下置为1，在下一时刻，选取第三位和第四位内的数字进行模二相加（其实就是XOR异或），将得到的数字放在第一位，然后剩余数字依次后移，将4内的数字输出，连续工作时，我们就得到了下表：

将最后一列输出的二进制数连起来，我们就得到了上面提到的伪随机码PRN，不同的卫星进行异或的寄存器位不一样，比如上面是34，另一颗星可能是23，再有一颗星就可能是14等等，这样不同卫星得到的测距码序列也就不一样了。

于是，我们日常说的GPS的定位码就是这么产生的，我们说的“破解”，也是得到正确的多极反馈移位寄存器组合，以便在接收机上产生正确的PRN用来进行定位。但实际上，GPS的C/A码是公开的，生产C/A码接收机不需要破解，只需要下载官方公开的文档就可以。

GPS的C/A码由两个10级反馈移位寄存器组合而产生。码长 $N_{u} =2^{10}-1=1023 bit$ ，而C/A码的时钟频率为 $f_{1}=1.023MHz$ ，所以每一位宽度为 $t_{u}=\frac{1}{f_{1} } =0.97752\mu s$ ，所以每一位的距离是 $t_{u}c= 293.1m$ ，重复周期为 $T_{u}=N_{u} t_{u} =1ms$ （记住这个重复周期！很重要！），数据传输速率为 $1.023Mbit/s$ 。两个移位寄存器在每周日0时全部重置为1状态。

所以，C/A码的码长短，共1023个码元，若以每秒50码元的速度搜索，只需20.5s，易于捕获，称捕获码。P码等精码的捕获也要先捕获C/A码。

好了，现在说破解。

对于卫星导航信号的破解，最著名的参考文献莫过于高杏欣的Compass-M1 Broadcast Codes and Their Application to Acquisition and Tracking（http://gps.stanford.edu/papers/Gao_IONNTM_2008.pdf）。

在这篇文章中，得出了北斗M1星的民码生成算法。既然题主问到了必要的技术，那么首先需要有个接收机来接收卫星信号

上图就是文章中使用的1.8m碟形天线和相应的地面移动工作站，这套设备在当时相比国内堪称豪华，但是对于文章中的工作来说还是有点捉襟见肘，所以这篇文章也体现出了高深厚的信号处理功底。

在收到信号之后，大致流程是先对信号做自相关分析，得到信号的重复周期 $T_{u}$ ，然后去除多普勒效应对信号峰值造成的影响。

自相关分析并去除多普勒效应之后的信号，竖线之间为一个信号周期 $T_{u}$

然后确定初始相位（paper上这块因为自己不是通信专业的……没看懂……），这样可以在收到多个周期的信号之后从哪里将信号切成几个独立的周期。

将信号周期区分开之后，为了提高信噪比，将多个周期的信号堆栈（叠加），就可以得出PRN的波形，下图显示了文章中得到的前50微秒的PRN序列，如上文所述，整个周期为1毫秒，图中是完整周期的一部分。文章还特别指出了此时尚不能确定信号的符号，但在后面猜测移位寄存器的步骤中可以一并得到结果。

由此可见，要想破解卫星定位信号，或者更具体些，PRN的产生算法，我们至少要多次得到完整的信号周期，以便进行叠加并提炼移位寄存器配置。

好了，现在我们回到正题，看看破解军（P）码到底有多难

而对于P码（precision code，精定位码），美国人当然不笨啦，为了提高精度并防止你破解，发生电路采用的是两组各由12级反馈移位寄存器构成。。码长 $N_{u} \approx 2.35\times 10^{14} bit$ ，而P码的时钟频率为 $f_{1}=10.23MHz$

，所以每一位宽度为 $t_{u}=\frac{1}{f_{0} } =0.097752\mu s$ ，所以每一位的距离是 $t_{u}c= 29.31m$ ，重复周期为 $T_{u}=N_{u} t_{u} \approx 267d$ （天啦，重复周期从一毫秒涨到了二百多天！！），数据传输速率为 $10.23Mbit/s$ 。

你看，要破解的话至少要观察267天才能得到一个完整周期，比起民码一毫秒周期随随便便一观察就能得到成千上万个周期来简直是让人丧失信心。这还不算完，实际应用时P码的周期被分成38部分（每一部分为7天，码长约 $6.18\times 10^{12} bit$ ），其中1部分闲置，5部分给地面监控站使用，32部分分配给不同卫星，每颗卫星使用P码的不同部分，都具有相同的码长和周期，但结构不同。参照C/A码的每周重置，P码会有更复杂的重置和交换策略。

你看，这么一折腾，你连得到267天的完整周期都是一件几乎不可能的事了，所以，GPS军码的破解，大概就是这么难了

以上说到的还是P码明码，美国在运行GPS的过程中对P码应用了Anti-Spoofing政策，将P码与加密用的W码混合，生成Y码。W码的具体细节公开资料不多，只知道码率大概在500kHz。而P码本身生成规则不保密。但为了还原W码，仍需要对P（Y）码做足够多的观测，也就是上面讲的码长与观测时间的矛盾。

以上的P码是旧的军码，后来在新一代GPS上老美又提出了专门的M（Military）码，具体细节仍处于高度保密中，只知道速率为5.115 MHz，码长未知，并且不需要提前捕获C/A码。有小道消息认为M码结构类似P码，对捕获P（Y）码的研究可能对捕获M码也会有帮助。

PS，既然说到，就免不了插一嘴高杏欣，正如参考文献中列出来的，她工作的内容实际上就是抢在官方发布前猜出了《北斗卫星导航系统空间信号接口控制文件》中对北斗民码的部分描述，而现在她猜出来的东西在北斗官网提供公开下载（虽然按照国内gov网站的一贯尿性，链接不好找）。所以大家大可以对这件事坐下并放宽。

而对于北斗的军码部分，参照GPS的P码，北斗的军码在破解难度上至少会持平，很有可能更难，所以前一阵中科院的那个姐姐才会说，与其破解北斗军码还不如去造时间机器。

就酱

欢迎大家批评指正。

参考资料：

吴才聪《导航与通信导论》

《北斗卫星导航系统空间信号接口控制文件2.0》 beidou.gov.cn 的页面

Dunn M J. Global Positioning System Directorate Systems Engineering & Integration Interface Specification IS-GPS-200[J]. 2012.

Gao G X, Chen A, Lo S, et al. Compass-M1 broadcast codes and their application to acquisition and tracking[J]. Proceedings of the Institute of Navigation (ION NTM 2008), 2008: 133-141.

Barker B C, Betz J W, Clark J E, et al. Overview of the GPS M code signal[R]. MITRE CORP BEDFORD MA, 2006.

-------------厚脸皮的分割线-----------------

厚着脸皮链几个我的其他回答：

2016 年你在哪些地方留下了足迹？ - xelmiraaaaaaaage的回答 - 知乎

客机的引擎为什么不能像战机一样装在尾部，而要装在机翼两侧？ - xelmiraaaaaaaage的回答 - 知乎

「烧水汽车」是否可行？如果可行是否有实用价值？ - xelmiraaaaaaaage的回答 - 知乎

为什么中国军人如此重视军姿训练，而感觉美国这种不断打仗的军队却不那么强调军容军姿的整齐划一? - xelmiraaaaaaaage的回答 - 知乎

你去过的那些地方让你由衷地感叹人类的渺小（游客少的地方）？ - xelmiraaaaaaaage的回答 - 知乎

编辑于 2017-01-01 21:11