跳至主要内容

有关密码学 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)

密码分析

  • 系统是否安全？
  • 如何破解加密？

密码攻击 (COA)

仅仅获取到密文（ciphertext only attack），如何破解？
LetterFreq.
e12.702%
t9.056%
a8.167%
.............
样本越多，猜测越准确。

密码攻击 (CPA)

二战中，英国人对德国密码系统的种花攻击 (gardening)：
  • 在A地放地雷
  • 截取密文 ...FRQALFFDSFGRE...
  • 在B地放地雷
  • 截取密文 ...FRQALFFDSFUGA...
选择明文攻击 (chosen plaintext attack)：
试探设定的明文的加密结果，获取映射关系。

一致性破坏

不破解明文，仍可以有意地篡改解密结果，欺骗接收方：
  • PT: JOHN 1000; JACK 2000
  • CT: [01] [02]; [03] [04]
  • CT (modified): [01] [04]; [03] [02]
  • PT (modified): JOHN 2000; JACK 1000

极端的安全性


  • 经常更换密码 -> 一次性密码
  • 更大的密码空间 -> 超长的密码
  • 防止字典猜测 -> 密码随机选择

One Time Pad

维吉尼亚密码：使用和明文同样长的随机字母串作为密码
计算机的维吉尼亚密码：加法 -> 按位异或


            U        S        T        C
 plaintext: 01010101 01010011 01010100 01000011
       key: 10110111 11110111 10111110 10011010
ciphertext: 11100010 10100100 11101010 11011001

OTP 为什么安全

非OTP：错误的密码 -> 无效的结果（乱码，无意义文本）
OTP：错误的密码 -> 可能得到看似正确的结果
  • 不可能被COA（密文得到很多看似正确的结果）
  • 不可能被CPA（一次性）


ciphertext: 11100010 10100100 11101010 11011001
 wrong key: 10101010 11110001 10111001 10001101
wrong text: 01001000 01010101 01010011 01010100
            H        U        S        T

一次性

异或运算的性质：(p1 xor k) xor (p2 xor k) = p1 xor p2
如果多次使用OTP，则可以通过密文间异或消去密码。
已知的漏洞：
  • WIFI加密(WEP)
  • MS-PPTP(MSCHAP-v1)

实用性

  • Q: 如何安全地传送一次性密码？
  • A: 加密传输密码？死循环...
现实场景：密码应当便于交换和记录...
（其实可以通过量子密码实现绝对的OTP）

实际的加密方案

密码本模式

electronic code book, ECB

各种加密算法
  • 都可以归于替换式密码和移位式密码的复杂组合
  • 归根结底，就是多"字母"替换
实际的例子：
  • DES: 64位的替换单位
  • AES: 128/192/256 位的替换单位
缺点：同前

密码块链模式

cipher block chaining

为了避免ECB模式中移动块顺序篡改数据的风险：
  • 第i块明文加密之前，和上一块密文异或操作
  • 第1块明文和随机生成的初始向量 (Initial Vector) 做异或
既避免了篡改数据，还可以防止COA、CPA（相同数据两次加密结果不同）

流式密码

stream cipher

块密码中，如果任何一位传输错误，则会影响整个块（甚至下一块）的解密。
基于OTP的思路，设计一种伪OTP：
  • 密钥作为随机数种子
  • 通过伪随机数算法生成伪OTP密钥
  • 按照OTP的流程进行加密
为了避免重用攻击，也可以引入初始向量增加随机性。

其他模式

思考：文件系统加密，上述方法是否实用？

非对称加密


对称加密的矛盾：
  • 密钥必须被安全地保护起来
  • 密钥必须被分发给需要的用户
是否存在一种算法：
  • Decrypt(Encrypt(P, K1), K2) = P
  • 很难从K1推出K2
...以后再讲 (例：RSA)

生日悖论


如果一个房间里有23个或23个以上的人，那么至少有两个人的生日相同的概率要大于50%。


   n(p, d) = sqrt(2d ln(1/(1-p)))
 n(0.5, d) = 1.2 sqrt(d)
n(0.99, d) = 3.0 sqrt(d)
不要低估暴力穷举破解 (brute-force) 的危险性。

最后的话

公开算法

Kerckhoff 原则：密码学算法应当是公开的
  • 保密的是数据和密钥
  • 算法可以得到更多研究者的检验
不要对自己的轮子保有过度的信心。

密码学其他科技

  • 数字签名
  • DRM (蓝光加密算法 AACS)
  • 同态加密 (Homomorphic encryption)
  • ......

the End

谨慎采信本 slides 的内容：
似乎本 slides 没有出现 Alice 和 Bob




Popular posts from 产品随想的博客

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...
阅读全文

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

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

Bob Dylan – Facts. NobelPrize.org

  When I first received this Nobel Prize for Literature, I got to wondering exactly how my songs related to literature. I wanted to reflect on it and see where the connection was. I’m going to try to articulate that to you. And most likely it will go in a roundabout way, but I hope what I say will be worthwhile and purposeful. If I was to go back to the dawning of it all, I guess I’d have to start with Buddy Holly. Buddy died when I was about eighteen and he was twenty-two. From the moment I first heard him, I felt akin. I felt related, like he was an older brother. I even thought I resembled him. Buddy played the music that I loved – the music I grew up on: country western, rock ‘n’ roll, and rhythm and blues. Three separate strands of music that he intertwined and infused into one genre. One brand. And Buddy wrote songs – songs that had beautiful melodies and imaginative verses. And he sang great – sang in more than a few voices. He was the archetype. Everything I w...
阅读全文

产品随想 | 周刊 第101期：木叶飞舞之处，火亦生生不息

How to Install Fonts on Linux: A Comprehensive Guide   https://linuxiac.com/how-to-install-fonts-on-linux/ 在伊丽莎白一世的时代的英国，如果人们想要盗版剧本，就会派一个速写很快的人去看剧，那个人就会偷偷用速写把剧中所有的台词都记录下来。然后根据这些台词，几个看过这部戏剧会一起把这部戏剧中发生的一切都誊写下来。这种盗版剧本是很多戏剧现今存下来的唯一记录。 看到一个大爷总结普通人的一生：盛世之牛马，乱世之炮灰。 在现代晚期之前，总人口有九成以上都是农民，日出而作、胼手胝足。他们生产出来的多余食粮养活了一小撮的精英分子：国王、官员、战士、牧师、艺术家和思想家，但历史写的几乎全是这些人的故事。于是，历史只告诉了我们极少数的人在做些什么，而其他绝大多数人的生活就是不停挑水耕田。 模拟时代的黑胶与磁带   https://sspai.com/post/81162 黑胶与磁带来承载声音，手机照片来承载画面，视频来承载动态影像 一家店需要怎样的 BGM   https://mp.weixin.qq.com/s/F_CluKDRSswDeSMIxKWRFA 我们喜爱音乐，是因为音乐里，能体现出心意 ONE REVOLUTION PER MINUTE - a short film by Erik Wernquist   https://www.youtube.com/watch?v=iiPmgW21rwY 他有人生最可宝贵的一个德性：一种永久新鲜的好奇心，不会给时间冲淡而是与日俱增的。他没有相当的才具来利用这天赋，但多少有才具的人会羡慕他这种天赋！大半的人在二十岁或三十岁上就死了：一过这个年龄，他们只变了自己的影子；以后的生命不过是用来模仿自己，把以前真正有人味儿的时代所说的，所做的，所想的，所喜欢的，一天天的重复，而且重复的方式越来越机械，越来越脱腔走板。 ——《约翰.克里斯多朵夫》 【张一鸣】：《活法》、《少有人做的路》、《高效人士的七个习惯》、《基础生物学》对我影响比较大。 Consumer Electronics Hall of Fame   https://spectrum.ieee.org/special-reports/...
阅读全文

SU小技巧——秒出90°轴测图

 原文首发于角落工作室公众号，转载于 建筑学院 ，在此表示感谢 轴测图在分析图的使用中非常有用，尤其是90°的轴测图，可以和旋转过的平面图完美契合，非常适合用于分析图的制作。 那么如何设置才能导出90°的轴测图呢？ 先来看看最终效果图 我们都知道SU中可以通过设置“相机”—“平行投影”来取消透视，但是无法设置轴测角度，通过下面教程的设置，可以交给大家如何设置90°轴测图。 模型原图， ↑画一个正方形 ↑把这个正方形做成群组 ↑旋转45°，在平面模式 ↑然后给这个正方形一个厚度，厚度多少随意。 ↑然后以侧面的下脚点为轴，向上旋转45°。听起来很复杂，看图很明白 然后在“相机”里选“平行投影” ↑进入我们制作的长方体里，右键单击最上面的面，选择对齐视图。 ↑我们就得到了这个45-90-45的轴测图，删掉之前做的辅助立方体，我们还有一步工作要做。 ↑拖进PS，选择“图像”—“图像大小” 解锁掉宽度和高度中间的小拉锁，然后把高度乘以1.41 比如我这张图是669，就改成964，为什么要乘以1.41，因为是1：根号2的关系。呃，具体关系大家自行脑补。 ↑这样就OK了。 利用轴测图，我们可以进行分析图及复古风格图的PS，这就是下次的教程内容了，先贴一个预告图片
阅读全文

子网掩码和网关

零碎知识点 网关地址是具有路由功能的设备的IP地址 CIDR=IP + mask  是CIDR另一种表现形式 mask在计算中表示按位与的操作数，用来表示从目标中取出特定的二进制位 ARP表 路由表 理解子网掩码 59.78.40.110 59.78.40.126 255.255.255.128 59.78.39.162 59.78.39.254 255.255.255.0 59.78.42.41 59.78.42.254 255.255.255.0 协议作用 TCP/IP检测作用在2，3，4，7层 作用在1，2层：以太网，无线LAN，PPP...... 作用在3层：ARP, IPv4, IPv6, ICMP, IPsec 作用在4层：TCP,UDP,UDP-Lite,SCTP,DCCP 作用在5，6，7层：TELNET,SSH,HTTP,SMTP,POP,SSL/TLS,FTP,MIME,HTML,SNMP,MIB,SIP,RTP......
阅读全文