跳至主要内容

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

Foobar2000 组件安装教程

 原作者 博客地址   汉化作者 Asion博客   关于foobar 2000的一些资源 前言 foobar2000 由于其软件架构特点以及开放的姿态，使得第三方很容易开发组件（component）来拓展它的功能。由于在官网下载的默认安装文件只带了少量几个默认的组件，满足不了使用的需求，例如：默认不带 ape，tta，tak 等音频文件格式的解码器，很多无损压缩格式音乐没法播放。所以自己下载安装组件是必备的基本技能。 foobar2000 的中文汉化版（Asion 汉化）为了方便使用，集成了无损压缩文件解码器以及一些其它有用的插件，安装时选上即可，不喜欢折腾的建议使用汉化版。 这里组件指的是 foobar2000 标准组件（*.dll 文件），而非 vst 插件等其它插件，姑且把组件分为两类： 官方组件： 英文版安装包自带，安装时可选择； 第三方组件：非官方自带的组件 除了 foo_input_std.dll 和 foo_ui_std.dll 这两个组件是必须的外，其它的所有组件都 非必需 的，可以随需要增删。第三方组件可以去 官网 、 官方论坛 或者 官方 wiki 去找，也可以去贴吧等地逛逛。 下载 还是要强调一下，这里说的是 foobar2000 component ，不是中文网上通常说的 vst 插件。 下载好的组件包一般是 xxx.zip 或 xxx.fb2k-component 格式的文件，也有用 7z 打包的。前两种都是 zip 压缩（只要把 fb2k-component 改成 zip 文件就变成了 zip： 包）。标准状况下压缩包里的内容结构应该是 xxx.zip yyy.dll README.txt (可能没有) LICENCE.txt (可能没有) (其它杂七杂八） 除少数外一般只有一个 xxx.dll 文件.一定要注意压缩包结构不能是: xxx.zip yy folder (文件夹） zzz.dll … 否则要解压缩，提取那个 dll 文件。 安装 方法一（推荐） 打开 foobar2000 的菜单 文件 > 首选项(file >preferences) 的 组件(components...
阅读全文

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

《沸腾新十年》2007-2012

2007-2009 大幕拉启 早期玩iPhone的人觉得：它不支持复制粘贴、拍摄视频，也不能更改铃声、壁纸，还不能换电池、插存储卡，手机里的照片和备忘录等也没法复制到电脑中。（但它有Killing Feature是沉浸式的屏幕、上网功能） 在网龙的路演过程中，网龙创始人刘德建发现，在当时极为“高大上”的投资人群中，用iPhone已经蔚然成风 ──论有钱人带领的风潮 苹果早期是不支持第三方输入法的，这一问题要等到2014年iOS 8的推出才正式解决。 ──居然也封闭了整整七年 对于航班管家来说，好用户就是高频乘坐飞机出行的群体。以前，这个群体在哪里、如何捕捉，都是问题。但是iPhone的出现，天然筛选出了那些消费能力强劲的群体。 苹果公司和联通也在为没有好应用来推广iPhone而发愁，所以它们精选了6款应用。王江的航班管家和搜吃搜玩都得以入选，吃到了iPhone大推广时代的官方预装红利。 王江认为：“其实有了智能手机，才能说有了场景。你不拿着手机亲临其境，怎么叫场景呢？ 触宝输入法，深合安卓早期创业的三大奥义：“高频、刚需、工具化”。 参赛是一个名利双收的大好机会，能帮助免费推广产品 魅族黄章对之前毫无保留地和雷军交流有些后悔：“我连M9的UI交互文档都发给过他，请他一起探讨。” 安卓早期的最大刚需之一是系统优化。 CyanogenMod因此成为当时全球最大的ROM开发和优化团队。 中国早期安卓生态的很大一部分是建立在CM的基础上的。最着名的有小米的MIUI团队、创新工场的点心团队、占据国内千元机市场的乐蛙OS团队等。 当时的盛大创新院群星璀璨，除了潘爱民和许式伟，还有樊一鹏“樊大师”，也有郝培强和霍炬，有极客余晟，有陆坚博士，有黄伟和吴义坚，有庄表伟，还有白宁等诸多牛人。 2012年夏天，华为的任正非在一个讲话中提到两个“备胎”计划，一个是关于芯片的，另一个就是关于操作系统的。 ──布局早在10年前 2009年，张一鸣决意离开饭否，转而去房产网站九九房，这是26岁的张一鸣从南开大学毕业后的4年里准备开启的第4段工作经历，每份工作平均也就一年多一点的时间。此时的张一鸣与大部分同龄人相比略显著急，稍显无措，全然没有日后那种长期思考的定力和耐性。 2009年12月底，王兴确定做美团。 ──原来也已经10年+ 2009年的“双11”购物节只是给淘宝商城团队找点事情的自我安慰...
阅读全文

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

UNstudio实习经验分享

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

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

巴菲特致股东信-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...
阅读全文

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

巴菲特致股东信-1974年

 笔记： 价格战企业的逻辑：需要降价获取销量--->需要降低成本--->怎么降？扩大规模以摊低成本--->提高固定资产投入--->净资产回报率会降低 翻译： 雪球：https://xueqiu.com/6217262310/131257947 备份：https://archive.ph/5CEP6 原文： To the Stockholders of Berkshire Hathaway Inc.: Operating results for 1974 overall were unsatisfactory due to the poor performance of our insurance business. In last year's annual report some decline in profitability was predicted but the extent of this decline, which accelerated during the year, was a surprise. Operating earnings for 1974 were $8,383,576, or $8.56 per share, for a return on beginning shareholders' equity of 10.3%. This is the lowest return on equity realized since 1970. Our textile division and our bank both performed very well, turning in improved results against the already good figures of 1973. However, insurance underwriting, which has been mentioned in the last several annual reports as running at levels of unsustainable profitability, turned dramatically worse...
阅读全文

巴菲特致股东信-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'...
阅读全文