跳至主要内容

有关密码学 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 产品随想的博客

黑客讲述渗透Hacking Team全过程

原文地址在 Freebuf ，后来已经被删除 Wayback Machine 备份 近期，黑客 Phineas Fisher在pastebin.com上讲述了入侵Hacking Team的过程，以下为其讲述的原文情况，文中附带有相关文档、工具及网站的链接，请在安全环境下进行打开，并合理合法使用。作者部分思想较为激进，也请以辩证的观点看待之。 1、序言 在这里，可能你会注意到相比于前面的一个版本，这个版本的内容及语言有了一些变化，因为这将是最后一个版本了 ［1］ 。对于黑客技术，英语世界中已经有了许多书籍，讲座，指南以及关于黑客攻击的知识。在那个世界，有许多黑客比我优秀，但他们埋没了他们的天赋，而为所谓的“防护”服务商（如Hacking Team之流的），情报机构服务工作。黑客文化作为一项非主流文化诞生于美国，但它现在只保留了它本质的魅力，其他均被同化了。从黑客的本质出发，至少他们可以穿着一件T恤，把头发染成蓝色，用自己的黑客的名字，随意 洒脱 地做着自己喜欢的事件，而当他们为别人（前文所指的 Hacking Team及情报机构 ）工作的时候，会感觉自己像个反抗者。 如果按照传统的方式，你不得不潜入办公室偷偷拿到文件［2］，或者你不得不持枪抢劫银行。但现在你仅仅需要一台笔记本，躺在床上动动手指便可做得这一切［3］［4］。像CNT在入侵伽玛集团（Gamma Group）之后说的，“让我们以一种新的斗争方式向前迈进吧”［5］。 [ 1 ] http: / /pastebin.com/raw .php?i=cRYvK4jb [ 2 ] https: / /en.wikipedia.org/wiki /Citizens%27_Commission_to_Investigate_the_FBI [3] http:/ /www.aljazeera.com/news /2015/ 09/algerian-hacker-hero-hoodlum- 15092108 3914167 .html [ 4 ] https: / /securelist.com/files /2015/ 02 /Carbanak_APT_eng.pdf  [ 5 ] http: / /madrid.cnt.es/noticia /consideraci...
阅读全文

产品爱好者周刊 第26期：PRISM, XKeyscore, Trust No One

  Products Gitea - Git with a cup of tea   https://gitea.io/en-us/ A painless self-hosted Git service. 自建Git服务，避免GitHub隐私侵犯 https://github.com/objective-see/LuLu LuLu is the free macOS firewall 监视Mac的出站流量，且阻断 OverSight   https://github.com/objective-see/OverSight OverSight monitors a mac's mic and webcam, alerting the user when the internal mic is activated, or whenever a process accesses the webcam. 监视是否有应用调用Mac的麦克风、摄像头 Mozilla Hubs   https://github.com/mozilla/hubs The client-side code for Mozilla Hubs, an online 3D collaboration platform that works for desktop, mobile, and VR platforms. 开源的多人虚拟空间，Mozilla打造，企业级VR诉求 数字移民   https://shuziyimin.org 关于内容源、工具的推荐，适合刚接入国际的新人 SimpleLogin   https://simplelogin.io/ 匿名邮箱工具，转发用，Michael Bazzell推荐 Telegram 群组、频道、机器人 - 汇总分享   https://congcong0806.github.io/2018/04/24/Telegram/#机器人-bot https://archive.ph/iJMBj 献给那些将来到Telegram的朋友 Design Patrick Wardle   https://www.instagram.com/patrickwardle/?hl=en 他的IG，摄影也精彩，审美...
阅读全文

360T7 刷机步骤及固件

https://cmi.hanwckf.top/p/360t7-firmware/   360T7的固件支持由immortalwrt-mt798x项目提供支持，请参考： https://cmi.hanwckf.top/p/immortalwrt-mt798x https://github.com/hanwckf/immortalwrt-mt798x 刷机步骤 参考 此处 的办法开启原厂固件的UART和telnet功能 在以下链接下载360T7测试固件（纯净版，无任何插件） https://wwd.lanzout.com/b0bt9idwd 密码:ezex （此固件已过时，请选择其它更新的固件） 接下来将刷入修改版uboot。修改版uboot的优点有： 固件分区可达108MB，原厂uboot只能使用36M 自带一个简单的webui恢复页面 到以下仓库的Release页面下载uboot，目前暂时仅支持360T7，后续将支持更多mt798x路由器。 推荐使用 mt7981_360t7-fip-fixed-parts.bin ， fixed-parts 代表uboot分区表在编译期间固定，不会随着uboot环境变量变化。 https://github.com/hanwckf/bl-mt798x/releases/latest 将 mt7981_360t7-fip-fixed-parts.bin 通过HFS等方式上传到路由器，使用以下命令刷入uboot mtd write mt7981_360t7-fip-fixed-parts.bin fip 确认刷入完毕后，拔掉路由器电源。然后将电脑的IP地址设置为固定的 192.168.1.2 ，接着按住路由器的RESET按钮后通电开机，等待8s后用浏览器进入 192.168.1.1 在uboot恢复页面选择要刷入的固件。immortalwrt-mt798x目前编译两个版本的360T7固件。 建议修改版uboot直接使用 immortalwrt-mediatek-mt7981-mt7981-360-t7-108M-squashfs-factory.bin ，两种固件区别如下： mt7981-360-t7-108M 为108M固件分区，原厂uboot不可启动，需要修改版u...
阅读全文

UNstudio实习经验分享

再过一周，我就将离开UNstudio阿姆斯特丹总部，到其上海分部了，鉴于上海分部目前还不承担设计任务，因此可以视为我UNstudio参与设计的体验即将告一段落。这个实习，原定3个月，后来被要求延长到了6个月，后来又延长到9个月，现在看来最终大概有11个月——那天一问，发现我的合同已经到了9月份了，赶紧声明不能这么长，我8月得回学校了。
阅读全文

文明、现代化、价值投资与中国 By 李录

 价值投资的概念/框架： 1）股票是对公司的所有权，而不仅仅是一张纸； 2）安全边际；（预测未来，但要留好安全边际） 3）市场先生；（让市场来服务你，而不是被指导） 4）能力圈；（建立属于自己的能力圈） 公司的来源： 欧洲扩张，从国王到贵族，到有钱人，到平民 《价值线》-几千家公司过去10年的财务情况
阅读全文

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

巴菲特致股东信-1980年

 笔记： 会计中对于下属股权公司的记账方式有3种： 持股50%以上，全部并入 持续20%--50%，则按持股比例并入 持股20%以下，则以实际收到的利润返还，计入报表 这种会计方式，会导致伯克希尔旗下，不少的企业，未能暴露实际的收益情况 对伯克希尔而言，对盈余的认定并非取决于持股比例是100%，50%，20%，5%或是1%，盈余的真正价值在于其将来再投资所能产生的效益 我们宁愿将所赚的盈余继续交由不受我们控制的人好好发挥，也不希望转由我们自己来浪费 高通货膨胀等于是对投入的资本额外课了一次税 翻译： https://xueqiu.com/6217262310/131837878 https://archive.ph/XMX5n  原文： Buffett’s Letters To Berkshire Shareholders 1980 巴菲特致股东的信 1980 年 Operating earnings improved to $41.9 million in 1980 from $36.0 million in 1979, but return on beginning equity capital (with securities valued at cost) fell to 17.8% from 18.6%. We believe the latter yardstick to be the most appropriate measure of single-year managerial economic performance. Informed use of that yardstick, however, requires an understanding of many factors, including accounting policies, historical ca...
阅读全文

产品爱好者周刊 第10期：乔布斯逝世10年

  产品爱好者周刊 第10期： 2021.10.14 Products 经济学人、卫报、Wired等电子周刊： https://github.com/hehonghui/the-economist-ebooks 每周均更新 Immersed： https://immersed.com/ 桌面端软件，可以虚拟出5个VR桌面，能模拟出在海滩、宇宙等地方，工作 它的员工写了篇自己工作流，非常酷 Working From Orbit： https://blog.immersed.team/working-from-orbit-39bf95a6d385 bilibili视频下载工具（开源） 哔哩下载姬 downkyi： https://github.com/leiurayer/downkyi Windows Only BilibiliVideoDownload: https://github.com/blogwy/BilibiliVideoDownload 多平台 BiliDuang:  https://github.com/kengwang/BiliDuang Versus： https://versus.com/cn 万物皆可比较 官网的范例，基本都是数码产品，可能是标准化产品有具体参数，容易比较些？ News Jony Ive on What He Misses Most About Steve Jobs:  https://www.wsj.com/articles/jony-ive-steve-jobs-memories-10th-anniversary-11633354769 中文译本： https://archive.ph/EZihd Ideas Weather Spark:  https://weatherspark.com 全球城市的全年气候，用于去陌生城市、旅行规划了解城市天气，会有帮助 Long Now Foundation：  https://twitter.com/longnow 以10000年的跨度，去思考未来的可能性，真是一件很浪漫的事情 Outside interests Notion会私自查看用户的内容
阅读全文

A Sister’s Eulogy for Steve Jobs

I grew up as an only child, with a single mother. Because we were poor and because I knew my father had emigrated from Syria, I imagined he looked like Omar Sharif. I hoped he would be rich and kind and would come into our lives (and our not yet furnished apartment) and help us. Later, after I’d met my father, I tried to believe he’d changed his number and left no forwarding address because he was an idealistic revolutionary, plotting a new world for the Arab people. Even as a feminist, my whole life I’d been waiting for a man to love, who could love me. For decades, I’d thought that man would be my father. When I was 25, I met that man and he was my brother. By then, I lived in New York, where I was trying to write my first novel. I had a job at a small magazine in an office the size of a closet, with three other aspiring writers. When one day a lawyer called me — me, the middle-class girl from California who hassled the boss to buy us health insurance — and said his cl...
阅读全文