Cryptography
密码学
课件
- Coursera_Dan Boneh_Cryptography_1_Stanford
- 现代密码学_电子科技大学
会议
四大安全会议
- S&P IEEE Symposium on Security and Privacy（CCF-A）
- 每年11月截稿，第二年5月开会，在美国开会
- https://sp2023.ieee-security.org/program-papers.html
- CCS ACM Conference on Computer and Communications Security（CCF-A）
- 每年5月截稿，同年10月开会，在美国开会
- https://www.sigsac.org/ccs/CCS2023/workshops.html
- USENIX Security Usenix Security Symposium （System-oriented）（CCF-A）
- 每年2月截稿，同年8月开会，在美国开会
- https://www.usenix.org/conferences/best-papers
- NDSS ISOC Network and Distributed System Security （CCF-A）
- 每年8月截稿，第二年2月开会，在美国开会
- 大陆迄今录用最少, 引用最好
- https://www.ndss-symposium.org/
三大密码会
- CRYPTO International Cryptology Conference（CCF-A）
- 美密会 每年2月截稿，同年8月开会，在美国开会
- EUROCRYPT Annual International Conference on the Theory and Applications of Cryptographic Techniques（CCF-A）
- 欧密会 每年10月截稿，翌年5月开会，在欧洲开会
- ASIACRYPT Annual Int Conf on Theory and Application of Cryptology and Information Security（CCF-B）
- 亚密会 每年5月截稿，同年12月开会，在亚洲开会
- 录用率比美密、欧密低
中国计算机学会推荐国际学术期刊/学术会议方向大全(https://www.ccf.org.cn/Academic_Evaluation/By_category/ )
- 计算机体系结构/并行与分布计算/存储系统
- 计算机网络
- 网络与信息安全
- 软件工程/系统软件/程序设计语言
- 数据库/数据挖掘/内容检索
- 计算机科学理论
- 计算机图形学与多媒体
- 人工智能
- 人机交互与普适计算
- 交叉/综合/新兴
Coursera_Dan Boneh_Cryptography_1_Stanford_Note
WEEK 1
Course Overview
What is Cryptography
History
- Caser Cipher：Substitution cipher
- Frequency of ( pairs of ) letters
- “e”、”he”
- ciphertext only attack（惟密文攻击 对替换式密码很有效）
- Vigener Cipher
- c = ( nk + m ) mod 26
- get bunch and look at the first letter
- same letter
- Rotor Machines
- A B C D
- D A B C
- C D A B
- Enigma
- Caser Cipher：Substitution cipher
Discrete Probability 1（离散概率）
- Uniform distribution
- Point distribution
- Distribution vector
- event A such as all x in U such that lsb2(x)=11
- union bound （和事件概率 < 事件概率和）
- contain elements
- Random Variables
- a function from the universe of some other sets
- 一个从全局到其他集合的函数
- 定义了概率分布
- Randomized algorithms（Deterministic algorithm）
- algorithm defines a distribution
Discrete Probability 2（离散概率）
- discrete probability is defined over a finite set（有限集）
- Indenpendence
- XOR 异或 是否不同
- 即为 ( a +b ) mod 2
- 能让随机分布变量 与 均匀分布变量 成为 均匀分布的随机变量
- The birthday paradox
- 需要多少人 两人相同生日
- 365 -> 24
Cipher
- Def：a cipher
- a pair of algorithm
- an encryption algorithm E
- often randomized
- an decryption algorithm D
- an encryption algorithm E
- be defined over a triple（三元组）
- 全体密钥的集合K
- 全体明文的集合M
- 全体密文的集合C
- the consistency equation 一致性方程
- D(K,E(K,M))=M
- a pair of algorithm
- The One Time Pad
- C := E(K,M) = K XOR M
- D(K,C) = K XOR C = M
- smae length
- key too long
- safe：密文不揭示明文的任何信息
- perfect secrecy
- P[E(k,M0)=C] = P[E(k,M1)=C]
- where k<-R-K
- 给定特定密文 我并不知道哪里来的
- 无法知道被加密的是M0还是M1
- 需要计算能将特定M映射到C的密钥k数量 只有一个
- 不意味着使用时安全
- key len >= msg len
- 任何完美安全的密码必须拥有足够长的密钥
- P[E(k,M0)=C] = P[E(k,M1)=C]
- no CT only attack
- Def：a cipher
Stream Ciphers
- 对数据流进行连续处理的一类密码算法
- make one-time pad more practical
- replace random key by pseudorandom key
- 长为s的随机种子做为固定的函数G的输入 G：伪随机发生器(PRG)
- C = E(K,M) := M XOR G(K)
- D(K,C) := C XOR G(K)
- PRG must be unpredictable
- 给定前几位 不能计算后面的位数
- Epsilon >= 1/2^30 密钥加密1GB数据时可能发生
Attack on OTP and use of stream ciphers
- 流密钥使用次数只能一次
- very easy to tell where that change occurr
- two time pad
- never use stream cipher key more than once
- dont use stream cipher for disk encryption
- every section would have its own key
- 可以对密文产生特定影响 从而对揭秘后的明文产生影响
- OTP is malleable（可修改的）
- 就可以把特定改变应用到明文上
Example Stream Ciphers
- RC4 Software
- CSS Hardware
- eStream
- PRG need 2 inputs ( k , r ) （unique）
- save us the trouble of moving to a new key every time
- Salsa 20
- designed for both software and hardware implementations
- a very fast stream cipher
PRG Security Defs
- 统计测试方法，判断是否随机
- Random iff |#0(x)-#1(x)| <= 10n^1/2
- Random iff |#00(x)-n/4| <= 10n^1/2
- Random iff max-run-of-0(x) <= 10logn
- 统计测试A相对于发生器G的优势
- 如果优势接近于1，表示当我们输入伪随机数时和输入真随机数时，统计测试A表现得完全不同。这时，这个统计测试就能将这个发生器的输出和真随机区分开来，某种意义上我们说这个统计测试破解了发生器G，因为可以区分输出序列和真随机序列。
- 如果优势接近于0，这意味着统计测试在两种情况下，表现得基本一致，对真随机的输入，我们基本上可以说测试A无法区分发生器输出和真随机。
- Secure PRGs
- 什么是安全的伪随机数发生器，我们说发生器G是安全的，如果不存在有效的统计测试可以区分发生器G的输出和真随机序列 ⭐️
- 发生器G是安全的，不仅特定的统计测试认为它的输出是随机的，事实上对所有有效的的统计测试，都认为输出是随机的。注意：限制为有效的统计测试是必须的
- Unpredictable
- statistic test B：given string x，B在前I位上运行算法A，算法A是否成功预测了第i+1位，如果成功返回1，否则返回0
- Real：1/2
- Fake：1/2+Epsilon
- 如果A是一个好的预测算法，B是一个好的统计测试，可以破解发生器
- 如果发生器G是安全的，没有任何好的统计测试和好的预测算法（这个发生器是不可预测的）
- 姚期智：发生器不可预测，发生器是安全的：如果存在一个位置能通过l位预测l+1，就是不安全的
- 说PRG是安全的，如果给出一个伪随机分布，随机选取密钥k，输出相应的G这个分布与均匀分布是计算上不可区分的
- 统计测试方法，判断是否随机
- Stream ciphers_Semantic security
- Shannon’s idea
- cannot recover secret key
- cannot recover all of plaintext
- reveal no “info” about PT
- cannot predict any letter
- 一个对称加密机制是安全的，“对所有有效攻击者，优势可忽略”（没有有效攻击者可以区分M0和M1的加密）。对这个攻击者能想到的两条明文，攻击者依旧不能区分这两种分布。
- 明文的任一位如果能被学习到，都意味着系统不是语义安全的。
- OTP 语义安全
- Shannon’s idea
WEEK 2
- Block Ciphers（分组密码）
- 信息被分组加密
- maps N bits inputs to exactly N bits of outputs
- 3DES：n=64bits k=168bits 48rounds
- AES： n=128bits k=128(10rounds)、192、256 bits
- built by Iteration （迭代）
- round function
- performance numbers（性能参数）
- Speed
- slower than stream ciphers
- Speed
- PRPs and PRFs
- PRFs：Pseudo Random Function（伪随机函数）
- K x X -> Y
- PRPs：Pseudo Random Permutation（伪随机置换）
- 作为PRFs的特例
- K x X -> X
- Funs[X,Y]：所有从集合X映射到集合Y的函数的集合
- 大小为|Y|^|X|
- 举例2个元素映射3个元素，每个元素都有三种地方可以映射
- 单射：不同射不同
- 满射：对象被射满
- 双射：一一映射（单+满）
- 大小为|Y|^|X|
- 如果攻击者无法区分是在和真随机函数互动还是和伪随机函数互动，PRF是安全的
- PRFs：Pseudo Random Function（伪随机函数）
- 伪随机置换，不是选择一个随机函数，而是选择一个随机置换
- 随机的双射函数
- 同样的输入 输出也必须不同
- 伪随机函数可以创造伪随机数生成器PRG
- 扩张的生成器可以满足并行计算
WEEK 3
WEEK 4
WEEK 5
WEEK 6
WEEK 7
- Post title：Cryptography
- Post author：Picasun
- Create time：2023-07-19 11:20:39
- Post link：https://redefine.ohevan.com/2023/07/19/Cryptography/
- Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.