跳至主要内容

深入理解GFW:DNS污染

原文地址是深入理解GFW:DNS污染，帖子写于2009年，对作者表示感谢

翻墙新手们往往遇到这样的问题：我明明已经设置了socks代理为127.0.0.1:xxxx，为什么还是上不去youtube？这时经验丰富的翻墙高手就会告诉你：firefox需要设置network.proxy.socks_remote_dns为true，也就是远程解析域名。这是怎样一回事呢？为什么要远程解析？这就涉及到了GFW的DNS污染技术。
DNS（Domain Name System）污染是GFW的一种让一般用户由于得到虚假目标主机IP而不能与其通信的方法，是一种DNS缓存投毒攻击（DNS cache poisoning）。其工作方式是：对经过GFW的在UDP端口53上的DNS查询进行入侵检测，一经发现与关键词相匹配的请求则立即伪装成目标域名的解析服务器（NS，Name Server）给查询者返回虚假结果。由于通常的DNS查询没有任何认证机制，而且DNS查询通常基于的UDP是无连接不可靠的协议，查询者只能接受最先到达的格式正确结果，并丢弃之后的结果。对于不了解相关知识的网民来说也就是，由于系统默认使用的ISP提供的NS查询国外的权威服务器时被劫持，其缓存受到污染，因而默认情况下查询ISP的服务器就会获得虚假IP；而用户直接查询境外NS（比如OpenDNS）又可能被GFW劫持，从而在没有防范机制的情况下仍然不能获得正确IP。然而对这种攻击有着十分简单有效的应对方法：修改Hosts文件。但是Hosts文件的条目一般不能使用通配符（例如*.blogspot.com），而GFW的DNS污染对域名匹配进行的是部分匹配不是精确匹配，因此Hosts文件也有一定的局限性，网民试图访问这类域名仍会遇到很大麻烦。

观测DNS污染

“知己知彼，百战不殆”。这一节我们需要用到前面提到的报文监听工具，以及参考其DNS劫持诊断一节。在Wireshark的filter一栏输入udp.port eq 53可以方便地过滤掉其他无关报文。为了进一步减少干扰，我们选择一个并没有提供域名解析服务的国外IP作为目标域名解析服务器，例如129.42.17.103。运行命令nslookup -type=A www.youtube.com 129.42.17.103。如果有回答，只能说明这是GFW的伪造回答，也就是我们要观测和研究的对象。

伪包特征

经过一番紧密的查询，我们可以发现GFW返回的IP取自如下列表：
4.36.66.178
203.161.230.171
211.94.66.147
202.181.7.85
202.106.1.2
209.145.54.50
216.234.179.13
64.33.88.161
关于这八个特殊IP，鼓励读者对这样两个问题进行探究：1、为什么是特定的IP而不是随机IP，固定IP和随机IP各自有什么坏处；2、为什么就是这8个IP不是别的IP，这8个IP为什么倒了GFW的霉？关于搜索这类信息，除了www.google.com之外，www.bing.com有专门的搜索IP对应网站的功能，使用方法是输入ip:IP地址搜索。www.robtex.com则是一个专门收集域名解析信息的网站。欢迎读者留下自己的想法和发现:lol:。
从Wireshark收集到的结果分析（实际上更好的办法是，将结果保存为pcap文件，或者直接使用tcpdump，由tcpdump显示成文本再自行提取数据得到统计），我们将GFW发送的DNS污染包在IP头部的指纹特征分为两类：
  • 一型：
    • ip_id == ____（是一个固定的数，具体数值的查找留作习题）。
    • 没有设置“不分片”选项。
    • 没有设置服务类型。
    • 对同一对源IP、目标IP，GFW返回的污染IP在上述8个中按照给出的顺序循环。与源端口无关、与源IP目标IP对相关。
    • TTL返回值比较固定。TTL为IP头部的“Time to Live”值，每经过一层路由器这个值会减1，TTL为1的IP包路由器将不再转发，多数路由器会返回源IP一条“ICMP time to live exceed in transit”消息。
  • 二型：
    • 每个包重复发送3次。
    • 没有设置“不分片”选项。
    • 设置了“保障高流量”服务类型。
    • (ip_id + ? * 13 + 1) % 65536 == 0，其中?为一个有趣的未知数。ip_id在同一个源IP、目标IP对的连续查询之间以13为单位递减、观测到的ip_id的最小值和最大值分别为65525（即-11，溢出了!）和65535。
    • 对同一对源IP、目标IP，GFW返回的污染IP在上述8个中按照给出的顺序循环。与源端口无关、与源IP目标IP对相关。
    • 对同一对源IP、目标IP，TTL返回值时序以1为单位递增。TTL在GFW发送时的取值有64种。注：源IP接收到的包的TTL被路由修改过，所以用户观测到的TTL不一定只有64种取值，这是由于网络拓扑变化的原因导致的。一型中的“比较固定”的“比较”二字也是考虑到网络拓扑偶尔的变化而添加的，也许可以认为GFW发送时的初始值是恒定的。
（以上结果仅保证真实性，不保证时效性，GFW的特征随时有可能改变，尤其是时序特征与传输层特征相关性方面。最近半年GFW的特征在很多方面的变化越来越频繁，在将来介绍TCP阻断时我们会提到。）
还可以进行的实验有：由于当前二型的TTL变化范围是IP个数的整数倍，通过控制DNS查询的TTL使得恰好有GFW的返回（避免动态路由造成的接收者观察到的TTL不规律变化），观察IP和TTL除以8的余数是否有对应关系，在更改源IP、目标IP对之后这个关系是否仍然成立。这关系到的GFW负载平衡算法及响应计数器（hit counter）的独立性和一致性。事实上对GFW进行穷举给出所有关于GFW的结果也缺乏意义，这里只是提出这样的研究方法，如果读者感兴趣可以继续探究。
每次查询通常会得到一个一型包和三个完全相同的二型包。更换查询命令中type=A为type=MX或者type=AAAA或者其它类型，可以看到nslookup提示收到了损坏的回复包。这是因为GFW的DNS污染模块做得十分粗制滥造。GFW伪造的DNS应答的ANSWER部分通常只有一个RR组成（即一条记录），这个记录的RDATA部分为那8个污染IP之一。对于二型，RR记录的TYPE值是从用户查询之中直接复制的。于是用户就收到了如此奇特的损坏包。DNS响应包的UDP荷载内容特征：
  • 一型
    • DNS应答包的ANSWER部分的RR记录中的域名部分由0xc00c指代被查询域名。
    • RR记录中的TTL设置为5分钟。
    • 无论用户查询的TYPE是什么，应答包的TYPE总是设置为A（IPv4地址的意思）、CLASS总是设置为IN。
  • 二型
    • DNS应答包的ANSWER部分的RR记录中的域名部分是被查询域名的全文。
    • RR记录中的TTL设置为1天。
    • RR记录中的TYPE和CLASS值是从源IP发送的查询复制的。
其中的术语解释：RR = Resource Record：dns数据包中的一条记录；RDATA = Resource Data：一条记录的数据部分；TYPE：查询的类型，有A、AAAA、MX、NS等；CLASS：一般为IN[ternet]。

触发条件

实际上DNS还有TCP协议部分，实验发现，GFW还没有对TCP协议上的DNS查询进行劫持和污染。匹配规则方面，GFW进行的是子串匹配而不是精确匹配，并且GFW实际上是先将域名转换为字符串进行匹配的。这一点值得特殊说明的原因是，DNS中域名是这样表示的：一个整数n1代表以“.”作分割最前面的部分的长度，之后n1个字母，之后又是一个数字，若干字母，直到某次的数字为0结束。例如www.youtube.com则是"\x03www\x07youtube\x03com\x00"。因此，事实上就可以观察到，对www.youtube.coma的查询也被劫持了。

现状分析

  • 4.36.66.178，关键词。whois：Level 3 Communications, Inc. 位于Broomfield, CO, U.S.
  • 203.161.230.171，关键词。whois：POWERBASE-HK位于Hong Kong, HK.
  • 211.94.66.147，whois：China United Network Communications Corporation Limited位于Beijing, P.R. China.
  • 202.181.7.85，关键词。whois：First Link Internet Services Pty Ltd.位于North Rocks, AU.
  • 202.106.1.2,whois：China Unicom Beijing province network位于Beijing, CN.
  • 209.145.54.50，反向解析为dns1.gapp.gov.cn，新闻出版总署的域名解析服务器？目前dns1.gapp.gov.cn现在是219.141.187.13在bjtelecom。whois：World Internet Services位于San Marcos, CA, US.
  • 216.234.179.13，关键词。反向解析为IP-216-234-179-13.tera-byte.com。whois：Tera-byte Dot Com Inc.位于Edmonton, AB, CA.
  • 64.33.88.161，反向解析为tonycastro.org.ez-site.net, tonycastro.com, tonycastro.net, thepetclubfl.net。whois：OLM,LLC位于Lisle, IL, U.S.
可见上面的IP大多数并不是中国的。如果有网站架设到了这个IP上，全中国的Twitter、Facebook请求都会被定向到这里——好在GFW还有HTTP URL关键词的TCP阻断——HTTPS的请求才构成对目标IP的实际压力，相当于中国网民对这个IP发起DDoS攻击，不知道受害网站、ISP是否有索赔的打算？
我们尝试用bing.com的ip反向搜索功能搜索上面那些DNS污染专用IP，发现了一些有趣的域名。显然，这些域名都是DNS污染的受害域名。
  • 例如倒霉的edoors.cn.china.cn，宁波中国门业网，其实是因为edoors.cn被dns污染。一起受害的还有chasedoors.cn.china.cn，美国蔡斯门业（深圳）有限公司。
  • 还有*.sf520.com，似乎是一个国内的游戏私服网站。www.sf520.com也是一个私服网站。可见国内行政体系官商勾结之严重，一个“国家信息安全基础设施”竟然还会用来保护一些网游公司的利益。
  • 此外还有一些个人blog。www.99tw.net也是一个游戏网站。
  • 还有www.why.com.cn，名字起得好。
  • 还有www.999sw.com 广东上九生物降解塑料有限公司生物降解树脂|增粘母料|高效保水济|防洪 邮编:523128……这又是怎么一回事呢？不像是被什么反动网站连坐的。还有人问怎么回事怎么会有那么多IP结果。
  • www.facebook.comwww.xiaonei.com，怎么回事呢？其实是因为有人不小心把两个地址连起来了，搜索引擎以为这是一个链接，其实这个域名不存在，但是解析的时候遭到了污染，就以为存在这个域名了。
  • 倒霉的www.xinsheng.net.cn——武汉市新胜电脑有限公司，因为www.xinsheng.net被连坐。

DNS劫持的防范和利用

之前我们已经谈到，GFW是一套入侵检测系统，仅对流量进行监控，暂没有能力切断网络传输，其“阻断”也只是利用网络协议容易被会话劫持（Session hijacking）的弱点来进行的。使用无连接UDP的DNS查询只是被GFW抢答了，真正的答案就跟在后面。于是应对GFW这种攻击很自然的想法就是：
根据时序特性判断真伪，忽略过早的回复。
通常情况对于分别处于GFW两端的IP，其RTT（Round-trip time，往返延迟）要大于源IP到GFW的RTT，可以设法统计出这两个RTT的合适的均值作为判断真伪的标准。另外由于GFW对基于TCP的DNS请求没有作处理，于是可以指定使用TCP而不是UDP解析域名。也可以通过没有部署GFW的线路到没有被DNS污染的NS进行查询，例如文章一开始提到的“远程解析”。但黑体字标出的两个条件缺一不可，例如网上广为流传的OpenDNS可以反DNS劫持的说法是以讹传讹，因为到OpenDNS服务器的线路上是经由GFW的。
本质的解决办法是给DNS协议增加验证机制，例如DNSSEC（Domain Name System Security Extensions），客户端进行递归查询（Recursive Query）而不查询已经被污染了的递归解析服务器（Recursive/caching name server）。然而缺点是目前并非所有的权威域名解析服务器（Authoritative name server）都支持了DNSSEC。Unbound提供了一个这样的带DNSSEC验证机制的递归解析程序。
另外GFW的DNS劫持还可能被黑客利用、带来对国际国内互联网的严重破坏。一方面，GFW可能在一些紧急时刻按照“国家安全”的需要对所有DNS查询都进行污染，且可能指定污染后的IP为某个特定IP，使得全球网络流量的一部分直接转移到目标网络，使得目标网络立刻瘫痪。当然我们伟大的祖国郑重承诺“不率先使用核武器”…另一方面，GFW将伪造的DNS返回包要发送给源IP地址的源端口，如果攻击者伪造源IP，会怎样呢？将会导致著名的增幅攻击：十倍于攻击者发送DNS查询的流量将会返回给伪源IP，如果伪源IP的端口上没有开启任何服务，很多安全配置不严的系统就需要返回一条ICMP Port Unreachable消息，并且将收到的信息附加到这条ICMP信息之后；如果伪源IP的端口上开启了服务，大量的非法UDP数据涌入将使得伪源IP该端口提供的服务瘫痪。如果攻击者以1Gbps的速度进行查询，一个小型IDC（DNSpod被攻击事件）甚至一个地域的ISP也会因此瘫痪（暴风影音事件）。攻击者还可能设置TTL使得这些流量恰好通过GFW产生劫持响应，并在到达实际目标之前被路由丢弃，实现流量“空对空不落地”。攻击者还可能将攻击流量的目标IP设置伪造成与伪源IP有正常通信或者其他关联的IP，更难以识别。这样实际上就将一个国家级防火墙变成了一个国家级反射放大式拒绝服务攻击跳板。
最为严重的是，这种攻击入门难度极低，任何一个会使用C语言编程的人只要稍微阅读libnet或者libpcap的文档，就可能在几天之内写出这样的程序。而GFW作为一套入侵防御系统，注定缺乏专门防范这种攻击的能力，因为如果GFW选择性忽略一些DNS查询不进行劫持，网民就有机可乘利用流量掩护来保证真正的DNS通信不被GFW污染。尤其是UDP这样一种无连接的协议，GFW更加难以分析应对。“反者道之动，弱者道之用。”

参考文献

  1. 闫伯儒, 方滨兴, 李斌, 王垚. "DNS欺骗攻击的检测和防范". 计算机工程, 32(21):130-132,135. 2006-11.
  2. Graham Lowe, Patrick Winters, Michael L. Marcus. The Great DNS Wall of China. 注：这篇文章虽然试图通过统计特性了解GFW，但由于实验条件控制不佳、实验结果观察不细致，加上缺乏对GFW的整体观，故没有提供什么有意义的结论。然而美国同学的这种科学态度与实验精神值得我们学习和思考。事实上，这篇文章仍然提供了珍贵的历史资料，读者不妨按照本文逻辑来分析这篇参考文献。阅读过这篇文献的敏感的读者还将在我们后续的文章中看到熟悉的数字。
  3. KLZ毕业. 入侵防御系统的评测和问题. 注：本文对DNS污染包的分类就是从这篇文章的分类继承而来。

Popular posts from 产品随想的博客

《逢いたくていま》──仁医主题曲

原始链接： 听歌学日语 | 唱哭很多人的《逢いたくていま》 あ いたくていま - MISIA 现在好想见你- MISIA 初 はじ めて 出会 であ った 日 ひ のこと  覚 おぼ えてますか 第一次相遇的那天 你是不是还记得呢?   過 す ぎ 行 ゆ く 日 ひ の 思 おも い 出 で を  忘 わす れずにいて 那些过去日子的回忆 我一直没有有忘记   あなたが 見 み つめた  全 すべ てを  感 かん じていたくて 凝视着你 这一切的全部 我都想要感觉   空 そら を 見上 みあ げた 抬头仰望天空   今 いま はそこで  私 わたし を  見守 みまも っているの? 你到现在是否还在那里守护着我？   教 おし えて… 请你告诉我 今 いま   逢 あ いたいあなたに 现在好想见你 伝 つた えたい 事 こと がたくさんある 有好多想要告訴你的事情   ねえ  逢 あ いたい  逢 あ いたい 呐 好想见你 好想见你   気 き づけば  面影 おもかげ   探 さが して  悲 かな しくて 如果能注意到的话 你的面容 是在寻找着 还是悲伤着 どこにいるの?  抱 だ きしめてよ 到底在哪里呢? 好想抱紧你 私 わたし はここにいるよ ずっと 我 会一直在这里 一直等你 もう 二度 にど と 逢 あ えないことを  知 し っていたなら 如果能早点知道 已经再也无法相见   繋 つな いだ 手 て をいつまでも  離 はな さずにいた 我会牵在一起的手 永远都不会放开   『ここにいて』と そう 素直 すなお に  泣 な いていたなら 如果当初诚实哭泣地告诉你『留在我身边』的话   今 いま もあなたは  変 か わらぬまま 现在的你是否也依然不变地   私 わたし の 隣 とな りで ...
阅读全文

Interview with Steve Jobs, WGBH, 1990

Interviewer: what is it about this machine? Why is this machine so interesting? Why has it been so influential? Jobs: Ah ahm, I'll give you my point of view on it. I remember reading a magazine article a long time ago ah when I was ah twelve years ago maybe, in I think it was Scientific American . I'm not sure. And the article ahm proposed to measure the efficiency of locomotion for ah lots of species on planet earth to see which species was the most efficient at getting from point A to point B. Ah and they measured the kilocalories that each one expended. So ah they ranked them all and I remember that ahm...ah the Condor, Condor was the most efficient at [CLEARS THROAT] getting from point A to point B. And humankind, the crown of creation came in with a rather unimpressive showing about a third of the way down...
阅读全文

犀流研习班第十期001-2讲听课笔记

一. 杂谈   1. Max  逼真的效果图和视频   2. SU  显示模式，费力可以作出好看的效果图   3. Maya  支持Nurbs,但不快捷，对CAD导出也不方便
阅读全文

产品随想 | 周刊 第69期：Do not go gentle into that good night

Products Windows Apps That Amaze Us   https://amazing-apps.gitbook.io/windows-apps-that-amaze-us/ 令人精细的Windows App 文物出版社   https://book.douban.com/press/2456/ 这是一个宝藏出版社，出品书籍质量非常高，大开眼界 blind   https://www.teamblind.com/ 老外的匿名职场社交工具，挺有意思，看看硅谷的meme 中国科学技术大学测速网站   https://test.ustc.edu.cn/ 看着还不错，挺靠谱的 底层代码是LibreSpeed   https://github.com/librespeed/speedtest 能不能好好说话？   https://github.com/itorr/nbnhhsh 也是我的一个痛点 Tree Style Tab (aka TST)   https://github.com/piroor/treestyletab 一个超强的浏览器扩展插件，树状呈现浏览器标签 Failory Pitch Decks   https://www.failory.com/pitch-deck 超级多的融资计划投资板，Pitch Book AutoCut   https://github.com/mli/autocut 用文本编辑器剪视频 全网漫游指南   https://tagly.notion.site/tagly/a333efd8c3e54e12b123acd541e8d3e6 数字时代的指引，希望他们成功 IT eBooks   https://it-ebooks.info/ IT书籍下载 ToastFish   https://github.com/Uahh/ToastFish 一个利用摸鱼时间背单词的软件。 利用Win10通知栏，出现、背单词 Ideas 沈向洋：IDEA 如何找到创新的「甜区」   https://mp.weixin.qq.com/s/OlI5VUxQKU_ijWZClQCG0Q AIGC How Did Nor...
阅读全文

产品随想 | 周刊 第115期：2024.5.16 Great libraries build communities

Loop   https://github.com/MrKai77/Loop Loop is a macOS app that simplifies window management for you! 我的电视 my-tv   https://github.com/lizongying/my-tv 我的电视 电视直播软件，安装即可使用 When we think about this technology, we need to put human dignity, human well-being—human jobs—in the center of consideration. ————Fei-Fei Li Author Talks: Dr. Fei-Fei Li sees ‘worlds’ of possibilities in a multidisciplinary approach to AI   https://www.mckinsey.com/featured-insights/mckinsey-on-books/author-talks-dr-fei-fei-li-sees-worlds-of-possibilities-in-a-multidisciplinary-approach-to-ai Randy Ubillos   https://apple.fandom.com/wiki/Randy_Ubillos Randall Hayes "Randy" Ubillos is the original software engineer behind Adobe Premiere and Final Cut Pro. 影响全球视频制作的男人， Reminders MenuBar   https://github.com/DamascenoRafael/reminders-menubar Simple macOS menu bar application to view and interact with reminders. Developed with SwiftUI and using Apple Reminders as a source. Bad libraries build colle...
阅读全文

产品爱好者周刊 第36期：走进Linux

Products OpenShot   https://github.com/OpenShot/openshot-qt OpenShot Video Editor is an award-winning free and open-source video editor for Linux, Mac, and Windows 开源的视频剪辑工具，跨平台 Run   https://github.com/The-Run-Philosophy-Organization/run 润学全球官方指定GITHUB，整理润学宗旨、纲领、理论和各类润之实例 Dozer   https://github.com/Mortennn/Dozer Hide menu bar icons on macOS ThisIsWin11   https://github.com/builtbybel/ThisIsWin11 Win11的隐私保护 RoundedTB   https://github.com/torchgm/RoundedTB Add margins, rounded corners and segments to your taskbars! Droptop Four   https://github.com/Droptop-Four/Basic-Version Droptop Four is the fourth iteration of the popular dropdown app launcher for Windows & Rainmeter. LibreTube   https://github.com/Libre-tube/LibreTube An alternative frontend for YouTube, for Android. nheko   https://github.com/Nheko-Reborn/nheko Quaternion   https://github.com/quotient-im/Quaternion 多平台的Matrix客户端 FluffyChat   https://fluffychat.im/ Phone端的Matrix...
阅读全文

Apple's One-Dollar-a-Year Man, By Steve Jobs, 2000

(FORTUNE Magazine) – Now that Steve Jobs has showed his hand on Apple's Internet and system software strategies and dropped the "interim" from his title, other questions loom. He's always denied it, but isn't it true that his old company, Next, did wind up taking over Apple? Will there ever be an encore to the 15-year-old Macintosh? Short of that, does Apple have any plans to jump into the "Internet appliance" fray? Will Apple ever build computers for business people again? And what, pray tell, does Steve think of all these young Internet zillionaires? Let's ask. Practically every technology that your old company, Next, possessed when Apple acquired it in 1997 is now being used by Apple in some strategic way. This must seem like sweet vindication.  The thing about Next was that we produced something that was truly brilliant for an audience that our heart really wasn't into selling to--namely, the enterprise. I suppose if you were wr...
阅读全文

产品随想 | 周刊 第43期：历史上的今天

Products Huberman Lab   https://hubermanlab.com/ 一款聚焦于健康的播客 今日热榜   https://tophub.today/ 聚合展示，国内各热门榜单，对跟进热点非常有帮助，热点运营的好帮手 SketchyBar   https://github.com/FelixKratz/SketchyBar A highly customizable macOS status bar replacement Mac菜单栏定制 自定义程度很高，看作者展示的案例，暂时没想出这样的好处（不过应用本身的编辑，确实也没啥意义）生命在于折腾吧！ Thanks-Mirror   https://github.com/eryajf/Thanks-Mirror 整理记录各个包管理器，系统镜像，以及常用软件的好用镜像，Thanks Mirror。 Musicn   https://github.com/zonemeen/musicn 一个下载高品质音乐的命令行工具，音乐来源: 咪咕 Planet Minecraft A creative Minecraft community fansite sharing maps, minecraft skins, resource packs, servers, mods, and more. 里面有很多动人的故事 可能是世界上最大的Minecraft社区，从2010年至今 The Uncensored Library   https://www.uncensoredlibrary.com/en blockworks   https://www.blockworks.uk/ "Distinctive maps for Minecraft that have educated players and risen to the level of art" 游戏也可以让人有更高的实现，而不仅仅是沉迷其中，国外游戏厂商比我们做的好太多 Minecraft_Memory_Bypass_GUI   https://github.com/xingchuanzhen/Minecraft_Memory_Bypass_GUI 绕过Minecraft...
阅读全文

Steve Jobs: `There's Sanity Returning', 1998

Nobody can doubt the charisma of Steven P. Jobs. The interim CEO of Apple Computer Inc., who returned to the company last July after his ignominious 1985 ouster, has brought back his legendary vision, impatience, and infectious passion for the Macintosh. Jobs spoke to Business Week Correspondent Andy Reinhardt in Apple's stark, fourth-floor boardroom, just after the company rolled out its new software strategy on May 11. Note: This is an extended, online-only version of the Q&A that appears in the May 25, 1998, issue of Business Week. Q: Now that you've introduced the new, bold-looking iMac, are you going to do some radically different products? A: There's a lot of talk about such things -- about handhelds, set-top boxes. A lot of computer companies have been searching for a consumer product. My view is that the personal computer has been the most successful consumer product of the last 10 years. What we have to do, what the industry stopp...
阅读全文

有关密码学 Cryptography

% Crypto 101 % CUI Hao 密码学 Cryptography 加密 ：军事、商业保密、身份认证、日记... 计算机出现前：加密 人类语言文字 。 计算机出现后：加密比特流（ASCII文本、网络协议） 古典替换式密码 凯撒密码 文本中每个字母在字母表上后移 k 个位置。 ATTACK -> DWWDFN (k=3) IBM -> HAL (k=-1) 改进 重新排列 字母表（单字母替换）： alphabet: ABCDEFGHIJKLMNOPQRSTUVWXYZ map to: RCPWUXNQBZFMYTLIEGVDJOAKHS example: ATTACK -> RDDRPF "密码组合"有 26! 种之多。 维吉尼亚密码 每k个字母一组，与长度k的密码做 加法 ： ATTACKATDAWN (plaintext) + LEMONLEMONLE (key: LEMON) = LXFOPVEFRNHR (ciphertext) 多个字母的凯撒密码。 替换式密码 substitution cipher 单字母替换/多字母替换/密码本... 加密算法：映射 密码：描述映射关系 解密算法：反过来映射 另一种设计方案 也许是中国人发明的吧： 群书万卷常暗诵， 主人顾盼千金重。 药物楚老渔商市， 丸剑跳踯霜雪浮。 移位式密码 ( transposition cipher ) 列移位密码 按密码重新排列文本各列，然后竖着读出来： KEY: 6 3 2 4 1 5 TEXT: W E A R E D     CT:     I S C O V E ==> EVLNEACDTKESEAQROFOJDEECUWIREE     R E D F L E     E A T O N C     E Q K J E U     (WE ARE DISCOVERED. FLEE AT ONCE) ...
阅读全文