跳至主要内容

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

BG投资十问（Baillie Gifford）

  1，公司是否能正面推动经济、社会或者文化发 展？ 如果做不到，BG可能就不会再往下看了。比如军火、赌博类公司再便宜，BG不会去看。 2，公司销售额在5年之内能否翻倍？ 为什么要讨论销售额？因为BG关注公司成长，销售额是比较简单直观的指标，而利润可有一些方法调节。所以，BG主要先关注销售额，再看现金流。 3，公司5年之后会怎么样？ 这是未来5到10年或者5到15年的中间维度，一是看公司的成长空间究竟还有多大，二是考虑5年之后，公司的短期估值会不会下降，会不会变得成熟。 4，公司的竞争优势到底是什么？随着时间会变 强还是变弱？ BG认为，如果公司的竞争优势是不断变弱的，将来在更远期挣回现金流的可能性就更低了。 5，公司是否有非常独特的文化？文化是否能够进化？ 毕竟要投资这么长时间，对创始人和公司管理文化是非常关注的。特别喜欢创始人领导的公司，而不是说创始人什么都不干，创始人在做房地产，找了一些人在做新公司，要尽量避免这样的公司。 谈到进化在BG看来，大部分公司都会有大公司病，需要看它怎么能维持比较灵活的管理，变大之后还能够保持非常快速的成长，比如亚马逊的day one文化（注：就是始终处在 创业启动状态，充满迷茫和压力，但是充满创造力和颠覆思想 ）。 6，公司过去的回报率怎么样？ 一方面是考虑到公司的ROE（净资产收益率），二是考虑公司的Margins（利润），看它的过去是不是值得投资，如果每年ROE都不到10个点，可能长期来看也没什么意思。 7，ROE能不能随着时间增长？ 有些公司一开始没有盈利，一直在烧钱，5年之后说不定ROE会到20%或者更高，它是一个动态过程。这样的公司BG也会投资，包括一些早期项目，很多公司都是没有盈利的。 8，公司怎么分配资本？ 资本现金流无非就是5种方法：再投资、收购、还债、分红、回购股份，要看公司在某个阶段的资本分配是不是最优的。 如果公司明明可以发展更多，结果乱分红了；或者是明明到了特别成熟的时候，还不愿意分红，都是错误的分配资本。 9，公司怎样才能长成5倍？ BG关注的是怎样，而不是能不能。这会强迫BG每个人去设想一些未来的可能性，包括公司现在的底层架构能不能够延伸到更多的业务。 比如，早期的亚马逊或者是阿里，连一个概念都没有，BG会考虑这个公司有没有这种机遇，以后去扩展到可触及的市场。 10，市场对公司有哪些误解，哪些事...
阅读全文

产品随想 | 周刊 第126期：Think of your life as a rainbow arcing across the horizon of this world

FolderPaint   https://github.com/MichaelTr7/FolderPaint Folder colour changing application for macOS. 乔布斯说：“对于我和苹果公司的许多人来说，索尼的盛田昭夫是最大的灵感来源之一。我希望我们今天的所想所为能让他会心一笑。” 乔布斯甚至从索尼挖走了一位顶级设计师。哈特穆特·艾斯林格被苹果挖走前，已在 100 多种索尼产品的创造中发挥了重要作用。 供职于索尼时，艾斯林格所在的设计工作室与管理办公室和工厂车间享有同等地位。他说，这样有助于促进公司生产和设计团队之间在一定程度上达成团结，这正是乔布斯试图重建的团结。 艾斯林格指出：“乔布斯有能力洞察事物的好坏，却不知道如何实现以及如何通过组织去构建。因此，我们向苹果提出的第一个建议是，赋予设计师一定的话语权。” 斯卡利表示，乔布斯和盛田之间的深厚友谊和相互敬重可以归结为对于设计的共同热忱。 “他们以非常积极的方式产生了共鸣”，斯卡利说，“两位来自不同文化背景的创始人共聚一堂，这是非常难能可贵的。他们讨论设计原则，却从不谈及商业模式。” “Think of your life as a rainbow arcing across the horizon of this world. You appear, have a chance to blaze in the sky, then you disappear.” City Lights Bookstore   https://en.wikipedia.org/wiki/City_Lights_Bookstore?useskin=vector 旧金山的城市之光独立书店 Vesuvio Cafe   https://en.wikipedia.org/wiki/Vesuvio_Cafe?useskin=vector 好奇怪，这家Cafe居然没有太多的介绍 “One of the things that I was fortunate of was to see and understand the context of San Francisco through the eyes of Steve Jobs,” Mr. Ive said. “He kn...
阅读全文

产品随想 | 周刊 第68期：Glory to Z-Library

Products Anna’s Archive   https://annas-archive.org/ Search engine of shadow libraries: books, papers, comics, magazines. Z-Library不会消失，只会激励更多 ReVanced Manager   https://github.com/revanced/revanced-manager The official ReVanced Manager based on Flutter. YouTube免广告 Gopeed   https://github.com/monkeyWie/gopeed High speed downloader that supports all platforms. All Platforms，非常霸气，除了iOS，确实都支持了 The Twitter archive   https://github.com/timhutton/twitter-archive-parser Python code to parse a Twitter archive and output in various ways 逃离Twitter Ideas 吴晓波｜“我们这是怎么了？”   https://chinadigitaltimes.net/chinese/680826.html 我辈需保持那股企业家的精气神 Worth Moving to Sweden as Engineers?   https://hongchao.me/living-and-working-in-sweden-as-engineers/ 瑞典工作10年的华人工程师，分享自己的看法 Murray Newton Rothbard 默里·罗思巴德   https://zh.wikipedia.org/wiki/穆瑞·羅斯巴德 米塞斯学生，也是推崇自由主义、开放社会 个人工具箱（2022 年 11 月 16 日更新）   https://github.com/pseudoyu/yu-tools 我的个人工具箱 (设备, macOS 软件, iOS Apps...) Design 2022台北...
阅读全文

产品随想 | 周刊 第127期：晨光只开一刻钟，但比千年松，并无甚不同

Cherry Studio   https://github.com/CherryHQ/cherry-studio Cherry Studio is a desktop client that supports for multiple LLM providers. Support deepseek-r1 Aalto Repository beta   https://repo.aalto.fi/ Images, sounds and videos from Aalto University 这个系列，价值极高 Nokia Design Archive   https://nokiadesignarchive.aalto.fi/ 芬兰这个国家很了不起 对话影石刘靖康：两代未出现划时代的产品，就会沦为平庸的品牌   https://www.geekpark.net/news/308996 还挺喜欢这个创始人的，有一种海盗的内涵 从哈佛、明星创业者到酷家乐副总裁，苏奇的传奇   https://app.modaiyun.com/mdy/article/3FO4K4W0M259 WHO关于猫狗咬伤、抓伤的处理建议 动物咬伤： https://www.who.int/zh/news-room/fact-sheets/detail/animal-bites 狂犬病： https://www.who.int/zh/news-room/fact-sheets/detail/rabies 关于狂犬病的10个事实： https://www.who.int/zh/news-room/facts-in-pictures/detail/rabies INDIGO 新年直播（2025）   https://www.youtube.com/live/ZIgPvSDGAfY 对2024年AI发展的回顾部分特别好 Artab   https://github.com/get-artab/artab Get Inspired by the World's Greatest Artworks Every Time You Open a New Tab. Extension Available for Chrome, Edge, and...
阅读全文

产品随想 | 周刊 第39期：《自由秩序原理》

Products Exodus   https://github.com/Exodus-Privacy/exodus-android-app Exodus is an Android application that let you know what trackers are embedded in apps installed on your smartphone using the εxodus plateform. It let you also know the permissions required by any apps on your smartphone. 检测你Android机子获取权限、嵌入追踪SDK的 simplewall   https://github.com/henrypp/simplewall Simple tool to configure Windows Filtering Platform (WFP) which can configure network activity on your computer. Mem Reduct Lightweight real-time memory management application to monitor and clean system memory on your computer. 内存清理工具，Windows上挺多这类小工具，很有意思 Squad303   https://1920.in/ 提供大家一个方式，告诉俄罗斯人，乌克兰在发生什么 Chameleon   https://github.com/sereneblue/chameleon WebExtension port of Random Agent Spoofer 帮助隐匿浏览器信息 CanvasBlocker   https://github.com/kkapsner/CanvasBlocker 浏览器指纹识别是丧心病狂 Alpine Linux   https://zh.wikipedia.org/zh-hans/Alpine_Linux 以安全为理念的Linux分支 Wirecutter   https://www.nytimes.com...
阅读全文

产品随想 | 张鸣论中国传统政治

原始文章目录 张鸣：皇权不确定性下的统治术——传统中国官场机会主义溯源   https://www.aisixiang.com/data/68897.html 张鸣：从科举制到市场经济转型——官本位的源流及滥觞   https://www.aisixiang.com/data/59273.html 张鸣：权力边界何在，实话空间几许？——论中国政治传统中的权力与真理关系   https://www.aisixiang.com/data/67054.html Insight： 中国自秦汉以来一直是官僚化的帝制结构，虽然皇帝最终要凭借官僚这个中介才能统治国家，但官员的权力来源和合法性依据都是皇权。官僚机器只是帝制的“车轮”。所以，皇帝要怎么样，官员只要迎合，就能获利。只有在皇帝明显违反常识道理、造成重大灾祸之时，官员才可能凭借儒家伦理对皇帝提出批评。理性选择的结果使得官员更多地趋向于顺从皇帝。 ——符合历史以来的感知 中国尽管有两千多年官僚制的传统，但守规矩、遵法制、走程序的现代理性官僚制度却一直都没有建立起来。考试取官的确是理性官僚制的一个重要因素，但中国古代官僚制只是万里长征走完了第一步，然后就再也不走了。隋唐科举制建立的初衷也并非建设官僚体系，而是防止贵族垄断官职，强化君权。科举制度越来越严密，选拔出来的人才也愈发精英化。但是，官僚的行为却没有程式化和规法化。官员的个人行为偏好往往直接影响一地的发展。 ——如何再往前走一步，可以看看新加坡 官员的行为模式往往以皇帝的喜好为风向标。一般来说，皇帝喜欢什么，一个朝代就兴什么。汉初皇帝喜欢黄老，臣子们就清静无为；东汉皇帝喜欢儒生，则臣子们多为经学家；唐初皇帝喜人上书言事，则多诤谏之徒；到晚唐，皇帝喜欢佛教了，则多礼佛之士；清代嘉庆之后，皇帝提倡节俭，带头穿补丁衣服，则满朝文武衣服上都打了补丁，有的补丁比衣服本身还贵。 ——Interesting 皇帝行为的不确定性，势必导致官员行为无法程序化、规范化，而皇帝行为的不确定往往是由统治术决定的，属刻意为之。多数王朝都外儒内法，崇尚权术，甚至迷信权术。秦始皇和丞相李斯之间，有过一个小故事。李斯随从车马过盛，很是招摇，皇帝看了不高兴。随行的宦官就把这事告诉了李斯，李斯于是轻车简从，低调起来。秦始皇马上知道身边有人泄密，又审不出来，于是把当时在身边的人都杀...
阅读全文

信息流的初衷是节省用户时间

https://mp.weixin.qq.com/s/nMZzLkEe7Cfk6Wu5560m9w 讲述信息流前世今生，讽刺的是信息流发展之初是为了让用户在短时间内找到最需要自己关注的内容，现在却成为消磨时间、捕捉用户兴趣的一个作用。
阅读全文

A Tribute to a Great Artist: Steve Jobs

  Steve Jobs, who died October 5 after resigning in August as CEO of Apple, the company he co-founded, had many talents. But what set him apart from other computer wizards was his artistic sense. He continually used the word “taste” in explaining what was ready to be manufactured at Apple, and what wasn’t ready yet—what he had to reject. The Apple computer, the iPhone, the iPad and the iPod are all strikingly beautiful objects; the clarity of their visual design matches the way they function. It’s clear that Steve Jobs was an artist and that his artistry worked at many levels: it was a visual sensitivity that extended outward to a way of thinking about how things worked and how different variables could interact with each other in a pleasing harmony. Where did this ability come from? Jobs gave some credit for his success to a seemingly unlikely source—a course on calligraphy that he took as an undergraduate at Reed College, a course established by a maverick profes...
阅读全文

巴菲特致股东信-1969年

 编者笔记： 巴菲特正式清算合伙人企业。 我把它们视为实业，而非股票，如果长期而言实业的业绩良好，那么股票也会有着同样的表现。 我不想解散一个雇佣了1100人的生意，尤其在管理层已经在努力改善公司相对整体行业的表现，而且也取得了合理结果的时候，同时该业务目前尚不需要额外的资本投入。 但是如果未来我们面临需要投入大量资本，或者该业务遭受相当程度的损失时，我将做出不同的决定。 原文： 1969 年 5 月 29 日 致合伙人: 大概在 18 个月以前，我曾经给你们致信，认为投资环境和我个人情况的变化将导致我对我 们未来业绩预期做出调整。 我当时所讨论的投资环境 ，已经变得更加的恶劣且令人沮丧 。也许我仅仅是缺乏从精神层面 进行调整的能力。(正如一位评论家对超过 40 岁的证券分析师所评价的那样:“他们知道太 多如今已不再适用的东西 。”) 虽然如此，就我看来: (1) 在过去的二十年中，对于数量(定量)分析方法所能把握的机会 之水已经逐渐干涸 ，到今天可以说是已经完全枯竭了 ;( 2 )我们的资金基数已经达到一个亿 ， 也就是说不超过三百万的投资量对于我们净资产的影响几乎可以忽略不计 ，实际上我们的投 资标的的市值已经不能低于一亿美元 ;( 3 )大量地对于投资的专注已经导致市场的交易行为 变得极度追求短期的利润，市场的投机性大大增加。 在 1967 年 10 月的信中我亦提到个人境遇的变化是我调整我们未来收益预期的最重要的原 因。我表达了自己不想再在合伙公司上注入我 100% 的精力的愿望。然而在过去的 18 个月 中我完全没有做到这一点。我曾经写到 :“希望随着预期的降低，我的对此投入的个人努力 也可以随之降低 。”然而实际上完全不是这样，我发现只要我一天还在管理合伙企业，我就 完全无法让自己投入到其它与之无关的东西上去。我不想让自己成为一个永远管理着资金 ， 追逐着投资收益的疯狂的兔子，而唯一让我放缓脚步的办法，就是将其停止。 所以，在年底之前，我希望所有的有限合伙人都能正式地得知我的退休愿望。 1969 年 10 月 9 日 致合伙人: 以下是接下来我认为对于我的退休将要涉及的事情: ( 1 )向你们介绍一下 Bill...
阅读全文