从高杏欣破解“北斗”编码说起-高杏欣
&&&&【提要】本篇《从高杏欣破解“北斗”编码说起_》由66test小编特别为需要综合文库的朋友收集整理，仅供参考。
&&&&从高杏欣破解“北斗”编码说起(旅美随感之六)&&&&&&&&日，国务院新闻办公室举行新闻发布会。会上宣布，北斗导航系统27日正式提供试运行，即开始向中国及周边地区提供连续的导航定位和授时服务。虽然北斗卫星导航系统目前仍处在卫星组网的关键阶段，但该系统已成功应用于测绘、电信、交通运输、森林防火、减灾救灾等诸多领域，其未来的军事利用前景也值得期待。&&&&美国十分关注北斗卫星导航系统的进展，美国智世界安全研究所中国项目主任孔哲文说：“2010年是“北斗”系统至关重要的一年，该系统将为中国提供独立的定位／导航能力，这不仅会冲击商用导航领域，还会因为中国减少了对美国GPS的依赖，而产生更大的战略冲击。”&&&&在这次新闻发布会之后，在我国网上盛传一则消息：清华大学毕业的女学生高杏欣，在斯坦福大学攻读博士学位期间，破解了我国北斗导航卫星的编码规则，随之发表了多篇高水平的论文，并获得了美国航空无线电委员会的表彰（见图）。一石引起千层浪，在网上招来骂声一片。有人称她在美国的研究是吃里扒外的汉奸卖国行为。&&&&高杏欣，哈尔滨人。清华大学2001年本科毕，2003年硕士毕业。2008年于美国斯坦福大学获得博士学位。毕业留校担任斯坦福大学GPS实验室助理研究员。后来她嫁给了在美的印度人。其父高德林，曾任黑龙江省公安厅常务副厅长，已在2010年免职。父母著有：《跨进美国斯坦福大学:追寻女儿成长的足迹》一书。她的研究项目专注于新型全球导航卫星系统所使用的信号及其接收机。&&&&2005年10月，她破解了伽利略系统的首颗试验卫星（GIOVE-A）用于生成编码的底层算法，并对其三个波段上所使用的频率进行了解码。在了她的成果公布后，许多接收机公司都使用她的编码，来制造接收机以获取和跟踪伽利略系统的信号。&&&&2007年4月，我国发射了北斗系统的首颗地球中轨道卫星。她解调了这颗卫星上所有民用的三个波段频率，并将这些伪随机数码，应用于一个接收机中获取并跟踪这个卫星。2008年4月，欧洲发射了GIOVE-B，她又破解了其底层编码生成器。&&&&由此可见，在中美两国复杂关系的背景下，由中国在美留学生，来破解自己国家研制的导航系统编码，的确很易引起网民的反感。因此，要提醒在美留学生，你们的研究项目，最好避开像“北斗”这样军民两用的十分敏感的项目。至于高杏欣的破解对于“北斗”发展的影响，实际上是微乎其微的。高杏欣破解的只是“北斗”的民用编码。美国GPS的民用编码，很早就被人破解了，否则，市面上的GPS终端，也就不会那么便宜了。“北斗”的频率是不能随便更换的，但其中的编码和算法等，却都是可以任意重设的。可以相信，别人一般是无法破解“北斗”未来的军用编码的。&&&&现代国与国之间的竞争，归根结底是科技创新能力的竞争，实质上也就是人才的竞争。中美两个世界最大的经济体之间，无疑正在展开一场激烈的“人才战”。目前，中国在这场人才争夺战中，明显处于劣势。截至2009年，中国送出留学人员约162万，世界最多，但归国者只有49万，不归者半数以上在美国。近年来，出国留学人员还在增加，每年到美国留学的学生已超过10万人。据美国《科学》杂志报道，2006年，美国博士生第一大来源就是清华，第二大来源是北大。因此美国《科学》杂志把清华、北大称作“最肥沃的美国博士培养基地”。中国继成为美国最大的博士生来源之后，也已成为博士毕业生留在美国最多的国家。中国留美博士已成为美国著名大学和高科技公司中的主要技术骨干。现在中国虽然在中美贸易上有很大的顺差，但在人才交易中，却产生了相反的巨大逆差。通过这个“官二代”高杏欣的实例，我们试问：假若我们未来无法在这场中美人才战中取胜，那么，我们怎能在综合国力的竞争中取胜呢？&&&&……
特别声明：当前位置：&>&&>&
清华女毕业生高星星高杏欣帮美帝破解“北斗”究竟意味着什么?
清华大学精仪系本科毕业的女学生高杏欣，在斯坦佛大学攻读博士学位期间破解了我国北斗二代定位导航卫星的信道编码规则，随之发表了多篇高水平的论文，并获得了美国航空无线电委员会的表彰。消息传到国内，一石引起千层浪，招来骂声一片。有人称她在清华大学就读时就参与过北斗项目，她在美国的研究是吃里扒外的汉奸卖国行为。图1 高杏欣获得美国航空无线电委员会的表彰除了网上的传言，她在清华是否参加过北斗项目不得而知，但想必让其掌握核心机密的可能性很小。而且，若她在美国的研究真的破解了我国军事机密，美国想必会对此严格保密，在未来的军事对抗中拿将出来，一定可以搞我们个措手不及，不太会像现在这样高调公开，从而让我们提前防范。那她的研究究竟是怎么回事呢？这得从卫星通信的编码流程说起。卫星要对信号按信源编码+加密编码+信道编码的次序进行处理，其中信源编码的作用是使用更精炼的符号来携带更多的信息，加密编码的作用当然就是加密了，信道编码的作用是将前面已经生成的码处理成更适应信道传输的码。卫星使用电池工作，发射功率不可能很大，加上其距离地面成千上万公里，信号传到地面时功率会衰减到很小，甚至会被淹没在背景噪声之中。那该如何保证接收端能正确接受呢？关键就在于信道编码，导航卫星普遍采用了扩频技术，即用一个扩频码序列代表原码中的“1”，用它的反码代表原码中的“0”，这个扩频码序列被称为码片（chip），原来的10序列就变成了由码片组成的新序列。举个例子，如果由码片“-1 -1 -1 +1 +1 -1 +1 +1”代表原码中的“1”，由“+1 +1 +1 -1 -1 +1 -1 -1”代表原码中的“0”，则原码序列“101”就变成“-1 -1 -1 +1 +1 -1 +1 +1 +1 +1 +1 -1 -1 +1 -1 -1 -1 -1 -1 +1 +1 -1 +1 +1”这样的码片序列了，为了便于您区分这三段，中间加了两处空格，而实际序列中是没有空格的。地面的接收站收到信号后，要按上述的编码次序的反序进行解码，这就好比下床时按先内衣后外衣的次序穿衣服，上床时就要按先外衣后内衣的次序脱。在进行信道解码时，将接收到的序列按每8位分成一段，然后用已知的码片序列“-1 -1 -1 +1 +1 -1 +1 +1”去跟每段逐位相乘，然后再相加，以上述的“101”为例，其三段的第一段“-1 -1 -1 +1 +1 -1 +1 +1”，跟“-1 -1 -1 +1 +1 -1 +1 +1”逐位相乘，第一位是-1乘-1得+1……，相加的结果是+8，第二段结果是-8，第三段是+8。由于信道中有很大干扰，在码片序列中的每一位上都会迭加上不同的干扰值，这些干扰值跟“-1 -1 -1 +1 +1 -1 +1 +1”逐位相乘再相加，会因为正负相抵而削弱。显然，若码片长度是100，则上述结果就会是“+100 -100 +100”，而随着码片长度的增加，信号增强噪声抵消的效果就越发明显，实际中的码片长度会成千上万。这段话不好理解，不妨打个比方，我在纸条上写100个+1和-1的总数相等的序列，例如-1 -1 -1 +1 +1 -1 +1 +1......，你也在纸条上写100个段话，分别是 赢78 输23 输39 赢42 输8......你写的序列中输赢次数及总量是均匀的。都写好后双方都把纸条亮出来，你的第1条赢78对应的是我的-1，此条算你输我78元，你的第4条赢42对应我的+1，此条算你赢我42元。由于我写的正负次序你是不知道的，最终的输赢应该接近打个平手，按术语说就是数学期望为0。如果只写几条，你都碰对的可能性还不小，但随着序列越长，就越倾向于打平手。而高杏欣出现了，她偷看了我写的+1和-1序列，她写的序列是 输23 输39 输8 赢78 赢42......这个序列的输赢次数及总量也是均匀的，在外人看来跟你写的没啥两样。但她的次序是号着我的脉搞出来的，每条都是她赢，结果就是连赢100把，序列越长，累加的钱数就越多。从时间次序来看，空中的干扰就好比是你写出的正正负负大大小小很乱但很均衡的序列，而我写的+1和-1序列就是前面说的码片序列，两个序列所对应的正负是不相关的，对应相乘再累加就把噪声抵消了。而把所传输的信号有意搞成高杏欣那个序列的样子，那在接收端与码片序列（即我写的+1和-1序列）进行相乘再累加运算，那信号自然就会大大增强了。由此可以看出，序列越长，接收效果就越好，但是，由一大长串正负1来表示原始的一个“1”或“0”，效率会随着序列的增加而降低，这就有个效率与可靠性的平衡问题了，一般说来，几千位的序列是比较常见的。言归正转回到北斗，北斗一代是由几颗对地静止同步轨道卫星组成的，位于我国上空，提供区域级的定位导航服务。日，我国发射了M-1卫星，这是北斗二代的第一颗卫星，北斗二代跟一代有很大不同，预计发射35颗星，其中非静止轨道30颗，静止轨道5颗。与美国GPS和俄罗斯GLONASS一样，北斗二代是全球定位导航系统，我国有望抢在欧洲的伽利略系统之前成为第三个GNSS（Global Navigation Satellites System）俱乐部成员。国外常用的北斗英文名是Beidou或Compass。按照国际法，卫星轨道和卫星频率信道先占先得，欧洲的伽利略系统跟北斗二代的频率有重合部分，但伽利略系统的第一颗实验卫星于05年打上去后很长时间没有动静，而北斗二代07年后却是连续地打，与伽利略形成了竞争关系。虽说频率信道先占先得，但总是要先备案的，我们在国际电信联盟备案了四个频率，分别是1590MHz、1561MHz、1269MHz、1207MHz。M-1打上去后引起了广泛关注，法国的国家空间研究中心就盯着研究了一个月，并公布了1589.74 MHz（E1）、1561.1 MHz（E2）、1268.52 MHz（E6）、1207.14 MHz（E5b）四个实测频率。北斗二代并不是高杏欣的第一个破解目标，伽利略系统的首颗试验卫星于2006年1月被激活后，在几个小时之内，她就与实验室里工作人员一道捕捉到了三个波段上的信号，并在接下来的几周里破解了信道编码，对北斗二代M-1卫星的破解，更多的是上述工作的重复。她和她的团队使用了斯坦佛大学的GNSS监控站，图2为1.8米的监控站碟形天线，图3为监控站的便携式地面设备。地面设备的核心是安捷伦89600矢量信号分析系统，配合其专用的VXI总线的测试设备，可对射频信号进行非常深入的分析，这套组合非常高端，可对三种国际3G标准设备进行测试分析，包括我国提出的TD-SCDMA标准的设备，甚至下一代的LTE设备。卫星信号经过长徒跋涉后衰减很大，到天线那里的功率就只剩下区区10-16 瓦特了，虽然斯坦佛GNSS监控站很先进，可以把信号放大300多倍，但信号还是会弱到无法识别。有人可能会问，这么高端的设备都识别不了，那丁点大小的用户机是咋识别的呢？原因就在于合法的用户机里有前面说的码片序列，与带扰信号进行逐位相乘再相加后，可以大幅度的放大信号和抵消干扰。作为破解者，高杏欣并不知道这个码片序列（事实上这个码片序列正是她想要知道的），那她会怎么办呢？她采用的是相同码片累加法，从很长的接收序列中找出相同的段落，然后对齐累加，原码片部分正正加得更大的正，负负加得更小的负，而不同时段的干扰部分因互不相关，会趋向于正负抵消，对齐累加的段落数越多，则干扰被抑制得越多，码片幅度被放大得越大。为说明这个方法，不妨设计一个游戏，我和其他10个人都写个8位数，+1和-1各4个，然后把这11个序列诸位相加，形成一个新序列，假如7个人的第1个数是+1，4个人的第1个数是-1，则新序列的第1个数是+3，以此类推。把这个新序列交给高杏欣，让她来猜我写的序列是什么。她还知道两个情况，即我永远写“-1 -1 -1 +1 +1 -1 +1 +1”这个序列，而其他10个人的正负次序每次都变，互相也不沟通。那她如何猜呢？她会要求玩很多把这个游戏，等手上攒了一大把新序列的纸条后，就把这些纸条对齐，逐位都累加起来再得到一个更新的序列，例如-78，-82，-69，+89，+58，-56，+66，+77。她知道只玩一把并靠一张新序列的纸条是猜不出来的，因为我的数据被其它10个人的乱数据给淹没了。但她同时知道那10个人的数据每次都是随机变的，而且又是互不相关，搞的次数多了，这10个人的每一位的数值和就会趋向于0，而我的次序是固定的，在第1236位永远贡献-1，在4578位永远贡献+1，随着游戏次数的增多，我的固定次序就脱颖而出，从“-78，-82，-69，+89，+58，-56，+66，+77”中就可以读出，我的次序就是“-1 -1 -1 +1 +1 -1 +1 +1”。说着容易做着难，特别是如何找到相同的段落？如何对齐？这涉及到多普勒频偏消除、相位调整等很复杂的技术问题，但她的文章并没有详细地介绍。好了，某个码片被她找到了。很明显，设计者不会把几千位的码片数据存在卫星上的闪存里，这种调用式的编码方式效率太低而成本太高，通常都是用移位寄存器来编码的。由找到的码片特例来倒推出移位寄存器的结构，跟从“0，2，4，6，8……”倒推出f(x)=2x公式一样，需要破解者的经验和数学技巧，当然也少不了计算机的仿真运算，她们用MATLAB软件把这个移位寄存器的结构给分析出来了，这个结构直接对应着生成多项式，而生成多项式相当于f(x)=2x这样的公式，知道输入，经这个生成多项式一计算，码片就编出来了。至此，高杏欣在没有得到授权的情况下，就可以跟踪利用北斗二代了，但她所获知的东西，在北斗二代将来民用化后都是会提供给用户的，现在所使用的短码是民用的，而且也并未有意做防破解处理。北斗二代的频率是不能随便换的，但其中的编码和算法等都是可以任意重设的，在将来实际应用时，完全可以做到与GPS的P码一样，重复一次需要267天，那这种靠对齐累加来提取码片的方法就不灵光了。北斗一代除了定位导航外，还有一个与众不同的功能，即可以进行数据通信，报道称北斗二代继承了一代的优点，想必这个优点也继承了，而数据通信的安全取决于加密编码体制，这是不同于信道编码的另一个层面的问题，她的研究与此无关。高杏欣的研究也并不是没有意义，北斗在一些波段上覆盖了GPS和伽利略系统，研究北斗卫星信号的编码调制方式可以帮助搞清楚系统之间是否会产生冲突。高杏欣将现行的民用短码的信道编码生成多项式公开，想必并不是北斗设计者所乐见的，但对北斗二代的安全，特别是军事应用的安全，并不会产生实质性的危害。参考文献：【1】Grace Xingxin Gao, Compass-M1 Broadcast Codes in E2,E5b, and E6 Frequency Bands, IEEE Journal of Selected Topics in Signal Processing, Vol3,No.4,August 2009【2】Grace Xingxin Gao, GNSS over China-The compass MEO Satellite Codes, InsideGNSS, July/August 2007