跳至主要内容

有关密码学 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 at the All Things Digital D5 Conference, Steve and Bill Gates spoke with journalists Kara Swisher and Walt Mossberg onstage in May 2007.

Kara Swisher: The first question I was interested in asking is what you think each has contributed to the computer and technology industry— starting with you, Steve, for Bill, and vice versa. Steve Jobs: Well, Bill built the first software company in the industry. And I think he built the first software company before anybody really in our industry knew what a software company was, except for these guys. And that was huge. That was really huge. And the business model that they ended up pursuing turned out to be the one that worked really well for the industry. I think the biggest thing was, Bill was really focused on software before almost anybody else had a clue that it was really the software that— KS: Was important? SJ: That’s what I see. I mean, a lot of other things you could say, but that’s the high-order bit. And I think building a company’s really hard, and it requires your greatest persuasive abilities to hire the best ...
阅读全文

产品随想 | 周刊 第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...
阅读全文

巴菲特致股东信-1976年

 笔记： 为什么选择轻资产行业：当竞争疯狂时，不会强迫加入降价大战 最终选择了费雪的思想，选择能理解的优秀企业，以合理的价格买入并长期拥有 翻译： 雪球：https://xueqiu.com/6217262310/131440258 备份：https://archive.ph/XLK0S 原文： To the Stockholders of Berkshire Hathaway Inc, After two dismal years, operating results in 1976 improved significantly. Last year we said the degree of progress in insurance underwriting would determine whether our gain in earnings would be "moderate" or "major." As it turned out, earnings exceeded even the high end of our expectations. In large part, this was due to the outstanding efforts of Phil Liesche's managerial group at National Indemnity Company. In dollar terms, operating earnings came to $16,073,000, or $16.47 per share. While this is a record figure, we consider return on shareholders' equity to be a much more significant yardstick of economic performance. Here our result was 17.3%, moderately above our long-term average and even further above the average o...
阅读全文

Commencement Address at Stanford University--“Stay hungry. Stay foolish.”

I am honored to be with you today for your commencement from one of the finest universities in the world. Truth be told— I never graduated from college. This is the closest I’ve ever gotten to a college graduation. Today I want to tell you three stories from my life. That’s it. No big deal. Just three stories. The first story is about connecting the dots. I dropped out of Reed College after the first six months but then stayed around as a drop-in for another eighteen months or so before I really quit. So why did I drop out? It started before I was born. My biological mother was a young, unwed graduate student, and she decided to put me up for adoption. She felt very strongly that I should be adopted by college graduates, so everything was all set for me to be adopted at birth by a lawyer and his wife. Except that when I popped out they decided at the last minute that they really wanted a girl. So my parents, who were on a waiting...
阅读全文

巴菲特致股东信-1975年

 笔记： 华盛顿邮报已成为伯克希尔第一重仓股 翻译： 雪球：https://xueqiu.com/6217262310/131409324 备份：https://archive.ph/4hgK3 原文： To the Stockholders of Berkshire Hathaway Inc.: Last year, when discussing the prospects for 1975, we stated “the outlook for 1975 is not encouraging.” This forecast proved to be distressingly accurate. Our operating earnings for 1975 were $6,713,592, or $6.85 per share, producing a return on beginning shareholders ’ equity of 7.6%. This is the lowest return on equity experienced since 1967. Furthermore, as explained later in this letter, a large segment of these earnings resulted from Federal income tax refunds which will not be available to assist performance in 1976. On balance, however, current trends indicate a somewhat brighter 1976. Operations and prospects will be discussed in greater detail below, under specific industry titles. Our expectation is that significantly better results in textiles, earnings added from recent acquisitio...
阅读全文

产品随想 | 周刊 第90期：史家之绝唱，无韵之离骚

Why AI Will Save the World   https://a16z.com/2023/06/06/ai-will-save-the-world/ Marc Andreessen的雄文，十分有說服力，邏輯清晰 辯證了現今AI監管拋出的5個可能的AI問題 讀的過程中，腦海裏浮現的都是編程隨想那篇文章 为什么马克思是错的？——全面批判马列主义的知名著作导读   https://program-think.blogspot.com/2018/09/Book-Review-The-Errors-of-Marxism-Leninism.html 兩者的思維鏈條、敘事方式，非常相似 人民聖殿教   https://zh.wikipedia.org/zh-hk/人民圣殿教?useskin=vector 瓊斯自稱是神的化身，幾千年前轉世為釋迦牟尼，創建了佛教；後來又轉世為耶穌基督，創建了基督教；之後短期化身轉世為巴孛，建立巴哈伊信仰；最後轉世為列寧，將社會主義發揚光大。 邪教徒聲稱自己轉世成了列寧，這說明了什麼？ Apple Vision   https://stratechery.com/2023/apple-vision Omnivore   https://github.com/omnivore-app/omnivore Omnivore is a complete, open source read-it-later solution for people who like reading. How the YouTube Algorithm Works in 2023: The Complete Guide   https://blog.hootsuite.com/how-the-youtube-algorithm-works/#A_brief_history_of_the_YouTube_algorithm 外人眼中的YouTube推薦算法變遷 Histography   https://histography.io/ “Histography" is interactive timeline that spans across 14 billion years of history, f...
阅读全文

巴菲特致股东信-1973年

 笔记： 在上一年度预测的今年竞争加剧导致利润下滑，真的发生了 翻译Link： 雪球：https://xueqiu.com/6217262310/131257618 备份：https://archive.ph/KIfdT 原文： To the Stockholders of Berkshire Hathaway Inc.: Our financial results for 1973 were satisfactory, with operating earnings of $11,930,592, producing a return of 17.4% on beginning stockholders' equity. Although operating earnings improved from $11.43 to $12.18 per share, earnings on equity decreased from the 19.8% of 1972. This decline occurred because the gain in earnings was not commensurate with the increase in shareholders' investment. We had forecast in last year's report that such a decline was likely. Unfortunately, our forecast proved to be correct. Our textile, banking, and most insurance operations had good years, but certain segments of the insurance business turned in poor results. Overall, our insurance business continues to be a most attractive area in which to employ capital. Management'...
阅读全文

Steve Jobs introduced the iPhone on January 9, 2007.

This is a day I’ve been looking forward to for two and a half years. Link Every once in a while, a revolutionary product comes along that changes everything. And Apple has been— well, first of all, one’s very fortunate if you get to work on just one of these in your career. Apple’s been very fortunate. It’s been able to introduce a few of these into the world. In 1984, we introduced the Macintosh. It didn’t just change Apple, it changed the whole computer industry. In 2001, we introduced the first iPod, and it didn’t just change the way we all listen to music, it changed the entire music industry. Well, today, we’re introducing three revolutionary products of this class. The first one is a widescreen iPod with touch controls. The second is a revolutionary mobile phone. And the third is a breakthrough internet communications device. So, three things: a widescreen iPod with touch controls; a revolutionary mobile phone; and a breakthrough internet communicat...
阅读全文

犀流研习班第十期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...
阅读全文