信息安全技术

从杂碎开始笔记在概念性的地方的笔记会更简单一些

课程主要内容：
对称加密 公钥加密
消息认证码 数字签名

The joy of cryptography

参考 Dan Boneh

考试：70%考试 30%平时成绩

目的：

  1. 基本的密码算法及其应用
  2. 密码算法可证明安全思路
  3. 学习密码思维方式
  4. 工程实践中正确运用

GF(P)的生成元；GF(2^m)

二进制加法：进行异或操作即可
乘法：乘上之后模一个不可约多项式

两个困难问题【现代公钥密码技术的安全保障】：大数因数分解(两个很大的素数相乘，很难分解乘法的结果)和离散对数问题

考试

概念性

流密码

  1. 完美保密性(完美安全性)：
    任意 m0,m1,∣m0∣=∣m1∣m_0,m_1,|m_0|=|m_1| 任意密文c， Pr[E(k,m0)=c]=Pr[E(k,m1)=c]Pr[E(k,m_0)=c]=Pr[E(k,m_1)=c]

    同一明文，消息加密后为c的概率相等。

  2. PRG

    • PRG安全性：定义统计测试算法A(输出0 伪随机，输出1 真随机)，一个PRG G，一个真随机r；定义A对G的优势：AdvPRG[A,G]=∣Pr[A(G(k))=1]−Pr[A(r)=1]∣Adv_{PRG}[A,G]=|Pr[A(G(k))=1]-Pr[A(r)=1]| 如果该优势 AdvPRGAdv_{PRG} 是接近1，表明A可以将G与真随机区分，反之接近0 表示不可区分
    • PRG性质：
      • 安全的PRG是不可预测的；
      • 可预测的PRG一定是不安全的；
      • PRG G的每一个bit都是不可预测的，则G是一个安全的PRG

  3. 不可区分：p1和p2不可区分可以说，对于任意有效的统计检测A，有p1，p2两种在{0,1}^n上的分布

  4. 语义安全性(one-time key)(完美保密性的减弱)

    定义了两个实验，优势为在两个实验中输出1的概率的差，如果对所有有效的A语义安全优势 Advss[A,E]Adv_{ss}[A,E] 是可忽略的，则称之为语义安全的

    • 注意：语义安全性，A只能给挑战者发送一次明文，只能询问一次密文，挑战者的密钥只使用了一次
    • 语义安全性例子：可推断LSB的算法A安全性(从输出的角度)、OTP的安全性(从分布的角度)
    • 流密码的语义安全性：如果G是一个安全的PRG，则基于G的流密码E是语义安全的。因为：对任意语义安全的对手A，总是存在一个PRG对手B，使得 Advss[A,E]≤2⋅AdvPRG[B,G]Adv_{ss}[A,E] \le 2 \cdot Adv_{PRG}[B,G]
      • 详细证明看笔记

分组密码

  1. 分组密码性能与流密码性能对比（分组比流密码块）：

    • 3DES:分组大小64bit 密钥168bit（56*3） K3×M→MK^3 \times M{\rightarrow}M
      • 3DES轮数：48(3*16)
      • 3E((k1,k2,k3),m)=E(k1,D(k2,E(k3,m)))
      • k1=k2=k3 3DES会变成single的DES
    • AES：分组大小128bit 密钥128,192,256bit
      • AES轮数：10

  2. 伪随机函数PRF：F:K*X->Y

  3. 伪随机置换PRP：E:K*X->X

    • 存在确定、有效的算法E(k,x)
    • E(k,*)是一对一的
    • 存在有效的逆算法 D(k,y)
    • PRP是一个输入空间=输出空间的PRF且它可以有效求逆
    • AES是PRP(K*X->X;K=X={0,1}128);3DES也是PRP(K*X->X;X={0,1}64,K={0,1}^168)

  4. 安全的PRF、PRP：

    • 安全的PRF：从所有X到Y的函数（Funs[X,Y]）中选取一个函数F，和使用任意k生成的 PRF=F(k,⋅)PRF=F(k,\cdot) 是不可区分的(不存在A使得 AdvPRP[A,F]Adv_{PRP}[A,F] 是可区分的)
      • Funs[X,Y]中的元素是Y的X次方；所有k对应的PRF集合的大小是K的大小
    • 安全的PRP：从所有的由X到Y的一对一函数中选取一个函数F（Perm[x]），和使用任意k生成的 PRP=E(k,⋅)PRP=E(k,\cdot) 是不可区分的(不存在A使得 AdvPRP[A,E]Adv_{PRP}[A,E] 是可区分的)
      • 3DES,AES都可以视作安全的PRP
    • 重点：注意PRP是一对一的，不可能存在不同的输入x1，x2使得PRP的输出相等

  5. 从PRF构建PRP：如果F是一个安全的PRF，则将PRF按照不同输入拼接(F(k,1)||F(k,2)…)成为一个PRP，则该PRP是一个安全的PRP

  6. DES：key长度：56bits 分组大小：64bit

    • 核心Feistel网络（看笔记）；如果f是一个安全的PRF,则使用该f构造的3轮Feistel网络是一个安全的PRP(K3×0,12n→0,12nK^3 \times {0,1}^{2n} {\rightarrow} {0,1}^{2n} )
    • DES是16轮的Feistel网络
      • 输入64bits明文，首先进行初始置换
      • 进行16轮Feistel网络(将密钥k扩展成16个k，k长度为48bit)；其中有 fi(x)=F(ki,x)f_i(x)=F(k_i,x)
        • 64bit名为拆开称为两个32bit，对第一个32bit输入 fif_i
          • fif_i 首先将32bit扩展为48bit，与 kik_i 异或
          • 异或得到的结果分成8组，分别输入到S盒中查表，从6位置换为4位
          • 4*8=32 将8组输出合并
          • 将32bit移位到低位
            前半段计算f函数的结果，移位到后半段
      • 进行逆置换
      • 输出64位明文
    • S盒的选取需要注意：不能有线性函数的输出能以较大比例与S盒的输出重合
      • 如果是线性，则很容易通过多个DES推出一个DES

        DES(k,m1)⊕DES(k,m2)⊕DES(k,m3)=DES(k,m1⊕m2⊕m3)DES(k,m_1) \oplus DES(k,m_2) \oplus DES(k,m_3) = DES(k,m_1\oplus m_2 \oplus m_3)

  7. AES：密钥长度：128bit/192bit/256bit 分组长度：128bit

    • AES使用代换置换网络(而非Feistel)，该网络中每回合所有的位都会变
    • AES步骤
      • 先构造16字节4*4矩阵(将一个分组变成矩阵)
      • 然后将矩阵和密钥异或
      • 异或结果输入到轮函数
      • 最后一个分组只进行字节代换和行变换，不进行列混淆，最后与密钥异或后输出结果

  8. 通过PRG构建PRF

    • 如果G：K→K2K{\rightarrow}K^2 是一个安全的PRG，则可以通过如下方法构造一个1bit的PRF:将PRG输出一分为二，如果0，就输出PRG输出的第一个分片，如果是1就输出PRG的第二个分片
    • 安全性证明：(看笔记，通过不断使用针对及替换即可)
    • GGM PRF:令G：K→K2K{\rightarrow}K^2 是一个安全的PRG，则可定义F:K×0,1n→KK \times {0,1}^n {\rightarrow} K

  9. 通过PRF构建PRP?

    • 通过GGMPRF 构建一个安全的PRF，然后通过Luby-Rackoff theorem(使用该f构造的3轮Feistel网络)构造出的PRP是一个安全的PRP

  10. PRF转换引理：

    • 安全的PRP也是安全的PRF，在== |X| 足够大时==
    • 引理：对于q次询问的敌手A， A对PRP E的优势与A对PRF E的优势的差的绝对值小于 q2/2∣X∣q^2/{2|X|}
      • 推论：如果 |X|足够大，那么 q2/2∣X∣q^2/{2|X|} 是可忽略的，则，如果PRP是安全的，即A对PRP E的优势可忽略，可以推出A对PRF E的优势可忽略，因此PRP也是一个安全的 PRF
    • 如果X不够大会怎么样？看4.1章节的例题：1bit PRP->PRF

AES应用

  1. ECB模式(电码本模式)
    • 加密不同的m，ECB方法总是使用同一个key；导致m1=m2.c1=c2
    • ECB不是语义安全的【如果明文分组超过1个分组】，证明：
      Adv=1的攻击方法：
  2. 确定的CTR模式
    • 是一个由PRF构造的流密码
    • 如果F是一个安全的PRF，则E_CTR 是一个语义安全的加密方法，对任何有效的CTR敌手A，存在有效的对于PRF的敌手B，使得 AdvSS=[A,EDETCTR]=2⋅AdvPRF[B,F]Adv_{SS}=[A,E_{DETCTR}]=2 \cdot Adv_{PRF}[B,F]
  3. 多次使用的密钥(Many time Key)下的语义安全性【CPA安全】
    • 区别：敌手可以看到多个由同一个key加密得到的消息(此前，一次密钥是只能看到一条用一个密钥加密的消息)；选择明文安全：因为敌手可以询问多个明文
    • 定义：敌手可以询问q组明文的加密，每次都要猜测挑战者加密的是第一个还是第二个明文
    • CPA攻击下，如果相同的m总输出相同的加密结果，那么可以通过询问两个一样的消息来获得正确明文。因此一定要保证相同的明文加密两次，产生的密文是不同的。
      • 方案1：随机化加密（明文中加一个随机值，但是需要注意，随机值选取空间一定要足够大，保证r不重复）
      • 方案2：基于新鲜值加密（1.计数器作为新鲜值，可以在密文中隐藏新鲜值；2.随机选取新鲜值，需要附加在密文中）新鲜值空间也要足够大
        • 基于新鲜值加密的CPA安全：
  4. CBC模式：
    • 加密：
    • 解密：
    • CBC的CPA分析（安全性）： 对一个可以询问q次的E_CBC攻击者A，存在一个PRP的敌手B，使得： AdvCPA[A,ECBC≤2⋅AdvPRP[B,E]+2q2L2/∣X∣]Adv_{CPA}[A,E_{CBC} \le 2 \cdot Adv_{PRP}[B,E]+2q^2L^2/|X|]
      • 只有当 q2L2<<∣X∣q^2L^2 << |X| 时，CBC才是安全的
      • 可以根据 ε\varepsilon 反推出 qL的大小
    • 基于新鲜值的CBC:注意，需要有两个key(一个用来生成IV，一个用来AES加密)，不然会导致攻击！！
    • CBC模式需要padding
  5. CTR模式
    • 顺序计数器模式：PRF的输入是IV,IV+1…，IV是随机选取的
      • 计数器模式安全性引理：如果F是一个安全的PRF E是一个CPA语义安全的CTR

        AdvCPA[A,ECTR]≤2⋅AdvPRF[B,F]+q2L/∣X∣Adv_{CPA}[A,E_{CTR}] \le 2 \cdot Adv_{PRF}[B,F]+ q^2L/|X|

        只需要 q2L<<∣X∣q^2L<<|X| 即可满足安全性【比CBC好】
    • 新鲜值模式：新鲜值不重复，IV=【高位，nonce；低位：计数器】

消息认证码MAC

目的：完整性

  1. MAC组成：两个算法：S；输出认证tag；V：验证完整性：0/1
  2. MAC的安全性：
    • 攻击者目的：存在性伪造，创造新的合法消息；因此攻击者无法对新消息产生合法key，给定一个正确认证的消息，无法产生该消息的新的合法认证码/无法产生新消息的合法认证码
    • 安全的MAC：
    • 注意标签空间T不能太短，如果太短，攻击者可以有 1/|T| 的优势猜中正确的MAC;至少需要1/2^96位
  3. 基于PRF的MAC：
    • 安全性计算：如果F是安全的PRF,且F的输出空间 |Y| 足够大，则由此PRF构造的MAC是安全的MAC
      • 存在一个对于MAC的敌手A，且存在一个PRF敌手B，使得

        AdvMAC≤AdvPRF+1/∣Y∣Adv_{MAC} \le Adv_{PRF}+1/|Y|

      • 证明（看笔记）
    • 截断基于PRF的MAC：如果有一个安全的PRF构成的MAC是安全的，输出n位，那么截断的MAC，输出w位也是安全的【当且仅当 1/2^w是可忽略的】
    • PRF的输入对于一个长消息来说还是太短了，需要CBC-MAC和NMAC
  4. ECBC-MAC
    • 需要两个key
    • 通过PRP定义一个新的PRF：
    • 如果没有最后一步…也会被选择明文攻击攻破，选一个分组大小n的消息， 获得认证消息，然后接长原来的消息，可以通过t，pt构造出合法的MAC
    • AdvPRF[A,FECBC]≤AdvPRP[B,F]+2q2/∣X∣Adv_{PRF}[A,F_{ECBC}] \le Adv_{PRP}[B,F]+2q^2/|X| 当 q<<∣X∣1/2q<< |X|^{1/2} 时，CBC-MAC安全
  5. NMAC
    • 也需要两个key 通过级联函数实现
    • 如果没有最后一步…会被选择明文攻击攻破【攻击者选一个消息为分组大小n的消息，获取其tag，再将这个消息变成n+1，那么可知最后一个分组与输入F的t，可以成功伪造t；具体看笔记】
    • AdvPRF[A,FNMAC]≤q⋅L⋅AdvPRF[B,F]+q2/2∣K∣Adv_{PRF}[A,F_{NMAC}] \le q \cdot L \cdot Adv_{PRF}[B,F] + q^2/2|K| 当 q<<∣K∣1/2q<< |K|^{1/2} 时，CBC-MAC安全
  6. 随机化的RCBC
    • 安全性：AdvMAC[A,IRCBC≤AdvB,F⋅(1+2q2/∣X∣)]Adv_{MAC}[A,I_{RCBC} \le Adv_{B,F} \cdot (1+2q^2/|X|)]
  7. CBC MAC的填充：
    1. ISO标准：padding：末尾为0，填充开始的地方以1分割，避免歧义需要假填充
    2. NIST标准 CMAC：key=(k,k1,k2)，如果正好不需要填充，需要异或上一个k2，如果需要填充，正常填充即可，且使用k1异或
  8. PMAC:
    • 最后一个分组不加密，需要两个 key
    • AdvPRF[A,FPMAC]=AdvPRF[B,F]+2q2L2/∣X∣Adv_{PRF}[A,F_{PMAC}]=Adv_{PRF}[B,F]+2q^2L^2/|X|
  9. 一次性MAC
    • 定义：
    • one time mac举例，使用L+1次多项式用于生成消息(不像举例，ppt里自己看吧)
  10. 一次性MAC->many-time MAC
    • 使用one time MAC构造可快速求得的many-time MAC
    • Carter-Wegman MAC： CW((K1,K2),m)=(r,F(k1,r)⊕S(k2,m))CW((K_1,K_2),m)=(r,F(k_1,r)\oplus S(k_2,m));其中，F是一个安全的PRF,S是一个oneTime MAC，r是一个随机值
  11. 总结

哈希函数

  1. 生日悖论：
  2. 哈希函数
    • H：M->T 是一个哈希函数(|M|>>|T|，大空间到小空间)
    • 碰撞：m0!=m1,H(m0)=H(m1)
    • 哈希函数的抗碰撞：对任意有效算法A， AdvCR[A,H]=Pr[AoutputscollisionforH]Adv_{CR}[A,H]=Pr[A outputs collision for H] 是可忽略的
  3. 通过抗碰撞构造MAC
    • 如果有一个对于短消息生成认证的MAC，以及一个哈希函数（从大空间到小空间）,可以构造一个新的MAC I。如果MAC安全，且H是康朋子的，那么这个MAC是安全的。长消息通过Hash变成短消息，再通过S输出消息认证码。
    • 注意，H一定是抗碰撞的
  4. Merkle-Damgard
    • 构造：h压缩函数 得到哈希函数H，需要填充(具体看笔记)
    • MD抗碰撞定理：如果压缩函数h是抗碰撞的，由MD构造方法构造的H也是抗碰撞的
      （证明看笔记，证明逆否命题）
  5. 构建安全的压缩函数
    1. 从分组密码制造压缩函数
      • Davies-Meyer压缩函数：h(H,m)=E(m,H)⊕Hh(H,m)=E(m,H) \oplus H
    2. 从分组密码构造压缩函数
      • Miyaguchi-Preneel：h(H,m)=E(m,H)⊕H⊕mh(H,m)=E(m,H) \oplus H \oplus m 以及 h(H,m)=E(H⊕m,m)⊕mh(H,m)=E(H\oplus m,m)\oplus m
      • 不安全的： h(H,m)=E(m,H)⊕mh(H,m)=E(m,H)\oplus m
  6. 从难解问题构造压缩函数：利用离散对数问题，但是很慢
  7. HMAC(从SHA-256)
    • 注意：直接将k，m输入hash函数构造MAC是不安全的【攻破方法：】
    • HMAC: S(k,m)=H(k⊕opad∣∣H(k⊕ipad∣∣m))S(k,m)=H(k \oplus opad || H(k\oplus ipad ||m));ipad和opad分别是外部密码本，内部密码本
    • HMAC是一个安全的PRF:1. HMAC压缩函数是PRF下可证明安全的；2.安全边界和NMAC一致

认证加密

  • 认证加密是为了防止篡改攻击【提供保密性和完整性】，实现了选择密文攻击的安全性，认证加密可以推出CCA安全
  1. 认证加密：认证加密系统 (E,D)
    • 为了安全性，必须提供：CPA攻击下的语义安全；密文完整性(攻击者不能构造一个可被正确解密的密文)
  2. 密文完整性 CI 的定义与认证加密的定义
    • 多次询问之后发送一个密文c，且c解密之后没有报密文无效的错误(不会输出错误符号)
    • (E,D)提供认证加密，当它是CPA攻击下语义安全的，同时它具有密文完整性CI
  3. 选择密文攻击安全 CCA安全
    • 定义：【CPA+可无限询问明文】CPA询问(询问两个m，获得任意一个的加密)；CCA询问(进行多次密文询问，并获得密文的解密值)；输出CPA询问结果，是被加密了m0还是m1 E是CCA安全的，对所有有效算法A， AdvCCA[A,E]=∣Pr[EXP(0)=1]−Pr[EXP(1)=1]∣Adv_{CCA}[A,E]=|Pr[EXP(0)=1]-Pr[EXP(1)=1]| 是可忽略的
    • 分析：随机IV的CBC的CCA安全（看笔记）
    • 如果(E,D)提供认证加密(AE)，那么(E,D)是CCA安全的[证明看笔记]

      AdvCCA[A,E]≤2q⋅AdvCI[B1,E]+AdvCPA[B2,E]Adv_{CCA}[A,E] \le 2q \cdot Adv_{CI}[B_1,E]+Adv_{CPA}[B_2,E]

    • 认证加密不能防止重放攻击和测信道攻击(如，计时攻击)
  4. 认证加密定理：如果(E,D)是CPA安全的加密，(S,V)是安全的MAC，则先E后M总是安全的；先M后E可能对CCA不安全，但是如果加密算法是随机CTR(一次MAC)或者随机CBC，那么先M后C是安全的
    • 注意，MAC必须要是安全的，不然攻击者会找到碰撞，导致获得一个密文后，总是能构造出正确解出的明文(例子看笔记)
    • OCB：直接从PRP构造的认证加密；高效可并行【有省略】

杂项

  1. 密钥获取：一般来说会通过一个SK(从硬件随机数发生器或密钥交换协议生成)去通过密钥生成函数(KDF)获取多个密钥
  2. 密钥推到函数KDF：
    • SK服从均匀分布
      • 如果源密钥SK在K空间是均匀分布的，则可以通过一个PRF来输出一组key；通过CTX来区分不同的进程
    • SK不服从均匀分布
      • SK不服从均匀分布，那么PRF输出不能与随机函数不可区分(只有输入是均匀的，输出才会均匀，如果输入不均匀，输出也不均匀)
      • 一般来叔输出是不均匀的(比如，密钥交换协议输出的K的子集可能是不均匀的，硬件生成的随机数可能是不均匀的)
      • 解决方法1：先提取再扩展机制
        • 先提取在扩展：HKDF(使用HMAC构造KDF)
      • 基于密码的KDF
        • 密码熵值太小，不能用在HKDF中，会被字典攻击攻破
        • 需要使用盐值以及一个慢哈希函数 PKCS#5
  3. 确定性加密：概念
    • 确定性加密：总是将指定明文映射到同一密文
    • 确定性加密不是CPA安全的：(相同CT映射到相同PT；明文空间小，可以构成一个字典，可以根据部分不变的密文来获得额外信息)
    • 证明CPA安全：由于相同明文会加密成相同密文，因此会泄露信息(确定性加密对一般的CPA安全是不安全的)
    • 证明确定性CPA安全：
      • 确定性安全：增加条件：加密者永远不会加密相同的明文两次，即(k,m)对永远不会重复
        • 可以每次从很大的空间中选取消息；或者使用某种消息结构使消息具有唯一性
      • 证明：确定性CPA安全【要素：多次使用同一个k加密，所有的消息是不同的，询问多次之后最后猜测ci是左侧消息还是右侧消息】
    • 有确定IV的CBC没有确定性安全
    • 确定IV的计数器模式吧不是确定性CPA安全【攻击：通过异或后的值来判断】
  4. 构造确定性加密
    • 方法1：合成IV
      • 该方法构造的E是确定CPA安全的，因为msg是唯一的，因此所有的r是与随机数不可区分的，对一个以上的CPA分组较为适合
    • 合成IV构造了密文的完整性(确定认证加密)
      • 以SIV-CTR为例，即中间的加密算法换成CTR模式
      • 如果F是安全PRF 从CTR得出的F_{CTR}是CPA安全的，由F和F_{CTR}构造的SIV-CTR提供确定性认证安全

密钥交换

  1. key的管理：每个人各自存一个密钥，每个人需要O(n)个密钥；使用信任的第三方(TTP)，每个人只需要一个key
  2. 密钥生成的玩具协议:抵抗窃听攻击但是不抵抗篡改攻击
  3. Merkle Puzzle
    • 通过难解谜题让对方猜测
    • 使用例子：
      • Alice准备2^32个谜题，每个谜题都包含一个随机的p和 (xi,kj)(x_i,k_j)，逐一发给bob；Bob选取一个随机的puzzle去解，(解法，应该是遍历整个p，看看哪个能解出正确的值)得到 (xi,kj)(x_i,k_j) ,然后把 $x_i $ 发给Alice;Alice把k_j作为密钥
      • 时间差别：Alice和Bob都只需要O(n)的时间来准备/解决puzzle，但是窃听者需要O(n^2)来首先猜测Bob选中的puzzle，再解密puzzle
      • 两者的gap: n2n^2 2402^40 和 2802^80
  4. Diffie-Hellman 协议
    • 协议描述
      • 首先选择一个大素数p(如，600位)，g(比p小的整数)
    • 安全性：攻击者可见p,g,A和B，但是攻击者难以计算 gab(mod  p)g^{ab}(\mod p)
      • DH函数： DHg(aa,gb)=gab(mod  p)DH_{g}(a^a,g^b) = g^{ab} (\mod p)
      • 求解时间复杂度：最好的算法 exp⁡O~(n3){\exp \widetilde{O}}({\sqrt[3]{n}})
      • 比较椭圆曲线和模大小
    • 中间人主动攻击
    • 关于DH的开放问题(看笔记去吧)
  5. 建立共享私钥
    • 公钥加密定义：需要三个函数G,E,D(D可以输出解密结果或错误)
    • 公钥加密的语义安全性(IND-CPA)
    • 共享私钥的建立：收方用私钥解密
      • 该方式是语义安全的：攻击者能看到pk，E(pk,x) 想获得x；但是由于x是随机值，因此攻击者无法区分x和真随机，因此不能获得x
      • 但是这种方式对于中间人攻击是脆弱的

公钥加密RSA

上课透了：：：：注意公钥加密的CPA安全性的定义

mark：我想思考，公钥加密的CPA安全和普通CPA安全的区别？几个典型的攻击？
对称加密：有one-time 安全和 many-time安全(CPA);一次密钥安全和CPA安全之间是不同的，一次密钥安全不能推出CPA安全
公钥加密：一次安全可以推出CPA安全，这是因为攻击者知道pk之后就可以自己随意加密msg，这和CPA安全是一样的
公钥加密来说，G一定是随机的

  1. 公钥加密的CPA安全（看上一章节的最后一节）
  2. 公钥加密的CCA安全
    • 定义：发起挑战之前/之后，可以多次解密自己想要的密文的明文，但是不能解密挑战密文。
    • 一个攻击举例：
  3. 陷门函数
    • 陷门函数定义：西安门函数包括三个函数
    • 陷门函数的安全性：如果F是一个单向的函数，即计算容易但求逆难，那么陷门函数 (G,F,F−1)(G,F,F^{-1}) 就是安全的
    • 使用TDF进行公钥加密 (G,E,D)
      • 安全性定理：如果(G,F,F^{-1})是安全TDF,(E_S,D_S)提供认证加密，H:X->K是一个随机寓言机，那么(G,E,D)是CCA安全的
      • 不能直接使用TDF加密：
  4. RSA陷门置换函数
    • 之前的是理论，现在套上实际的一个TDF：RSA
    • RSA陷门置换：加密：消息求e次方，解密：消息求d次方
      • RSA假设：RSA是一个单向置换(对于不知道sk的人来说，求出e的逆元很困难)
    • RSA公钥加密：
      • 先用G生成e和d，然后随机选一个x，算它RSA的值y，y作为公钥一部分；然后对x值hash，hash之后的值放入对称加密作为加密的key-
      • RSA"加密"x，自己再用这个x生成k，然后解密
    • 直接使用RSA进行加密是不安全的；示例一个攻击：
      • 攻击者可以进行类似中间相遇攻击的办法对教科书RSA进行攻击
  5. RSA是单向函数:
    RSA问题：已知e^x(mod N) 求x；该问题的求解只能将N进行因子分解，但是因子分解是一个难解问题，因此RSA是一个单向函数
    • RSA最小的指数为3，即最小的e为3
    • 错误提高RSA性能：不能使用小私钥来加快解密，使得指数计算缩短来让==>这样会导致私钥可以通过(N,e)计算
  6. RSA的应用
    • 可以使用较小的e加速RSA解密，e最小是3，一般推荐2^16+1
    • 针对RSA的攻击(见后面)

公钥加密ElGamal

  1. Elgamal：将DH协议转换为公钥加密

    • 密钥交换：
      • gag^a 作为公钥； 通过 gabg^{ab} 计算出k然后解密
    • ElGamal加密系统：(Gen,E,D) Gen生成一个有限群G中的生成元g，以及一个随机的a，a是sk，pk=(g,h=g^a)
      • 人话分析加密过程：ElGamal:一个循环群，阶为n，然后选一个g
        • 加密：加密者随便选一个b，然后计算gb；然后计算u=hb(g{ab});把gb和g^{ab}一起输入hash函数生成k(hash的输入长度是G，因为g是生成元，生成元的幂都在G里)，然后用一个E加密，发送(u,c)
        • 解密：
          • k怎么恢复？先恢复h^b
    • ElGamal 的时间消耗：加密需要2 exp (一种提速方法：提前计算好g的各种次方；但是只能一对一)；解密需要1 exp

  2. ElGamal安全性假设 CPA CCA安全

    • CDH假设：可计算DH假设
      • 如果 g,ga,gbg,g^a,g^b 已知，计算 gabg^{ab} 是困难的
    • HDH假设：Hash DH假设
      • 假设H是一个可以将G^2上的分布转为在K上的均匀分布的Hash函数(即，Hash的输出可以看作是真随机)
    • HDH下，ElGamal的语义安全性证明
      • 由于公钥加密，语义安全=CPA安全，证明如下：
    • ElGamal的CCA安全：通过交互DH(IDH)证明：
      • 依赖于IDH的安全定理：

  3. 更高安全性的ElGamal变种：twin ElGamal

    • 安全性证明：
    • 如何回避随机寓言机假设？
      1. 使用双线性群
      2. 使用特定群

  4. 更一般的原理

    1. 基本的单向函数：从PRG构建的单向函数【没有特殊性质，难以密钥交换】
      • 如果f是一个安全的PRG，那么f就是一个单向函数
    2. 离散对数单向函数：
    3. RSA单向函数

  5. 公钥密码体制需要：

    • 构造具有特殊性质的单向函数
    • 同态特性(f(x),f(y)=>f(x+y)=f(xy)f(x),f(y)=>f(x+y)=f(xy))和陷门

数字签名

签名和MAC的最大差别：
签名只有发送发可以加密，任何人都可以验证;MAC只有收方可以验证(可以同时确认来源以及防止篡改)
公钥加密和对称加密的区别
公钥加密使用公钥加密私钥解密，任何人都可以加密；对称加密的加、解密使用同一个key

  1. 数字签名
  2. 数字签名的安全性
    • 攻击者可以进行选择消息攻击，目标是进行存在性伪造，伪造一个新的合法的msg/sig 对，其中，m不能是此前询问过的m【注意与MAC安全性证明的区别】
    • 攻击者不能对新消息产生任何合法签名
  3. 数字签名应用
    1. 代码签名
    2. 一次性验证通道=>多次验证通道
    3. 重要应用：证书
      • 服务器使用可信第三方对公钥签名
      • CA生成自己的私钥，用于签名
      • 服务器使用证书的时间是有范围的
    4. EMV payments Credit-card payments
    5. 对email签名：DKIM
      • 邮箱会对每个发出的邮件签名，接收者会从DNS获得pk，在收到邮件之后验证签名的合法性。
      • 假设收件人可以为每封收到的电子邮件从DNS中检索新数据，那么Gmail可以在没有签名的情况下实现DKIM吗？可以，Gmail会将每封发送的电子邮件的抗碰撞哈希写入DNS。收件人从DNS中检索哈希并将其与传入消息的哈希进行比较。
    6. 使用签名和MAC的时间比较
      • 如果一个组织签名，一个组织认证：使用MAC
        • MAC需要交互去生成共享的私钥
        • 接收者可以修改数据或者子集重新签名，在将信息发送给第三方组织之前
      • 如果一个组织签名，多个组织认证：使用签名
        • 接收者不能更改收到的消息
    7. 防止数据篡改的三种方式
      • 抗碰撞的hash，需要一个只读空间
      • 数字签名：需要一个长期的sk
      • MAC：提供方需要对每个用户生成以恶新的MAC，同时需要保存一个长期存储的sk生成每个client的MAC KEY
  4. 数字签名构造
    • 使用抗碰撞的hash函数构造
      • 如果Sig是针对短消息的签名，那么在签名时使用长消息到短消息的hash函数就可以将对短消息的签名改为对长消息的签名
      • 如果Hash函数是一个抗碰撞的函数，那么由它构造的 SigBIGSig^{BIG} 是一个安全的对于长消息的签名模式
    • 使用单向函数构造签名(如使用AES)：签名太长，不实用
    • 使用陷门函数构造签名：(RSA)
    • 使用DLOG离散对数构造签名：
  5. 使用陷门置换构造签名
    • 全域hash签名 FDH Signature：
      • 形式：
      • 安全性证明：
      • 如果不使用全域哈希，则会导致存在性伪造
        • 为什么
    • RSA-FDH
      • 形式：
      • 例子 PKCS1 v1.5:

现实加密协议

OTP类

  1. RC4 【不安全】
    1. 初始输入不均匀，比如存在 Pr[2ndbyte=0]=2/256Pr[2^{nd}byte=0]=2/256
    2. 出现连续两个0的概率是 1/2562+1/25631/{256^2}+1/{256^3}
    3. 密钥之间存在关联
  2. CSS 【已经被破解】
    • CSS基于LFSR：线性反馈移位寄存器
      • LFSR的种子是指初始LFSR状态；每次右移一次，末尾舍弃，将异或的结果放在第一位；异或的结果：反馈函数选取固定位置，将这些位置的值进行异或之后再放到第一位
      • LSFR的级数指的是LSFR中的寄存器个数
      • 作业中出现的LSFR的示例：密钥使用3级线性反馈移位寄存器生成流密码的m和c
        1. 先通过c和m异或得到k
        2. k即为LSFR结果，构造f，未知数c0，c1，cn
        3. 构造矩阵，解方程
        4. 解得方程与c，根据f推导出k的推导关系
    • CSS的加密和解密：CSSseed由5字节组成，前两个字节放在17bit的LFSR 后3字节放在25bit的LFSR
    • CSS在2^17时间可破解【如果已知道CSS的前缀，猜测CSS的前17bitLSFR初始状态获得20字节输出，后25bit根据CSS前缀结果反推，验证后25bit是否符合LSFR的输出】
  3. eStream【比较好】
    PRG+新鲜值nonce：PRG: {0,1}s×R→{0,1}n\{0,1\}^s \times R {\rightarrow} \{0,1\}^n 其中，n>>s
    R只使用一次，(k,r)永远不会重复==>k可以重复使用

    E(k,m;r)=m⊕PRG(k;r)E(k,m;r)=m \oplus PRG(k;r)

  4. estream:Salsa 20【安全的】安全性：2^128

MAC

  1. 使用MAC保护系统文件：每个文件都有一个MAC tag，如果病毒非法篡改了文件中的信息，那么会导致计算出的MACtag完全不同

Hash

  1. SHA-256
    • 构造方法：Merkle-Damgard函数
    • 压缩函数：Davies-Mayer压缩函数
    • 分组加密算法：SHACAL-2
  2. TLS协议：使用HAMC-SHA1-96

认证加密

  1. 现实世界的AE系统以及其构造方式
    • SSL：先MAC,生成tag后再将m和tag一起加密
    • IPsec：先加密，加密后结果计算tag【永远对的】
    • SSH：先加密，然后对明文计算tag，将tag附在密文后面【不安全，泄露明文】
  2. NIST的认证加密标准：(基于nonce，都是认证加密)
  3. TLS1.2 (TLS记录协议)【先计算MAC再加密】
    • 有两个单向密钥k_{b to s} 和 k_{s to b} ;每个方向维护一个计数器ctr
    • 加密 CBC-AES 128 HMAC-SHA1;E(k,data,ctr)
      • 先算tag，再pad，再CBC加密，再接到header后
    • 解密
      • 先CBC解密，pad失败则发送失败；检查tag，检查失败则发送失败
    • TLS 1.1漏洞
      1. CBC的IV是可预测的；下一个IV是本次记录的最后一个密文分块，不是CPA安全的
      2. 有padding oracle攻击：根据服务器返回的错误消息，可以得知密文的padding是否有效，（对不同的错误会返回不同的响应）
    • 长度泄露：TLS头会泄露TLS记录的长度(也可以通过监听网络流量获取)
  4. 对802.11b WEP的主动攻击
    • 注意，CRC是线性的，这表示 ∀m,p:CRC(m⊕p)=CRC(m)⊕F(p){\forall}m,p: CRC(m \oplus p) = CRC(m) \oplus F(p)

公钥加密

  1. PKCS1 v1.5
    • 将消息扩展成如下格式之后，使用RSA加密
    • 攻击：利用解密漏洞：server会先查看传来的密文的明文开头是不是’02’，则攻击者可以测试明文的首部是不是02
      • 一个简化版的实际攻击例子(N取2的幂)，每次通过将密文乘以2来使密文左移，逐渐左移，得到铭文的最高位，2th最高位，。。。。是不是02
    • HTTP对此的解决方法：使用随机字符串r作为首部
  2. PKCS1 v2.0 OAEP 优化非对称加密补齐
    • OAEP+(普通陷门函数替代RSA,但padding改成用随机寓言机计算得)与SAEP+(让RSA e=3，去掉一个G)
    • OPEP实际执行困难要注意计时攻击
  3. 公钥加密应用：不同的pk加密， 保证不同人都可以解密

攻击方法汇总

对OTP和流密码的攻击

  1. two time pad 一次一密，密钥使用两次的情况

    C1<−m1⊕PRG(k)C2<−m2⊕PRG(k)C_1<- m_1 \oplus PRG(k) C_2<- m_2 \oplus PRG(k)

    C1⊕C2→m1⊕m2C_1 \oplus C_2 {\rightarrow} m_1 \oplus m_2

    攻击者可以根据m1m2异或的结果得到明文信息
  2. two time pad示例：MS-PPTP
    发送方和接收方的key都是G(k)，正确方法应该是双方共享一对密钥
  3. 802.11b WEP
    k不变，IV变，IV24bit，k104bit（不变），在2^24之后，IV会出现重复，且有些802.11会在重复后重置为0===>出现two time pad
    • 解决方法：k作为PRG输入，输出的结果分段，每个分段作为一个key==>每个包有一个伪随机生成的key
  4. 硬盘加密
    使用相同密钥加密文件，可以根据文件相同的部分破解k
  5. OTP无完整性、可修改性：修改密文攻击 解密后，得到 m⊕pm \oplus p 密文已经被改变但是接收者无法察觉
    攻击举例：

对分组密码的攻击

DES

  1. 穷尽搜索攻击
    • 给定一个key，存在另外一个key，使得DES(k,m)=DES(k’,m)的概率是：256*1/(264)=1/256【即有很小的概率找到key】
    • 对于两个DES明文，密文对，他们的唯一性是1-1/(2^71)
    • 对于AES 两个输入输出对，唯一性是 1-1/(2^128)
    • 对于3DES 穷尽攻击的时间是2^118
  2. 2DES的穷尽搜索攻击(中间相遇攻击) 考过
    • 一条消息就可以实现穷尽搜索攻击
    • 2E((k1,k2),m)=E(k1,E(k2,m))；key长度：112bits 密文长度64bits
    • 寻找(k1,k2),使得E(k2,M)=D(k1,c)
    • Step1：构建表格：列出所有k2以及对应的E(k2,M)，并且按照第二列的值排列(方便第二步寻找)
    • Step2：尝试相遇：列出所有的k，尝试D(k,C)是否在刚刚的表格中的第二列中，如果找到，则输出对应的(k1,k2)
    • 时间复杂度：2个 2∗256log⁡256<263<<21122* 2^56 \log{}{2^56} < 2^63 << 2^112
  3. DESX的穷尽搜索攻击(中间相遇攻击)
    • EX((k1,k2,k3),m)= k1 xor E(k2,m x or k3 )
    • 一条消息不能实现穷尽搜索攻击（因为始终不能确定k1或者k3），应该使用两条明文，密文对进行相遇
    • Step1：穷举k1，计算k1 xor c1 以及 k1 xor c2
    • Step2：穷举k2，计算 D(k2,k1 xor c1) 和 D(k2,k1 xor c2)
    • Step3：计算D(k2,k1 xor c1) xor m1 以及 D(k2,k1 xor c2) xor m2，如果相等则相遇，计算结果为k3
  4. 测量时间攻击，测量功率攻击；错误攻击：检测错误
  5. 线性密码分析：DES的S盒设计缺陷导致
    • 如果c是DES(k,m)，对于随机的k，m，有
      • 对于DES， ε=1/221{\varepsilon}=1/2^{21}
    • 因此对于 1/ε21/{\varepsilon}^2 个随机明文、密文对，通过异或明文与密文，可以获得key的子集的概率大于等于97.7%
    • 对于DES, ε=1/221{\varepsilon}=1/2^{21} ，则可以在 2^42时间内获得key的子集(14bit)
  6. 量子攻击
    • 对于搜索问题，普通计算机需要O(|X|)的时间，而量子计算机只需要O(|X^1/2|)的时间搜索

AES

  1. 针对AES-256，存在相关密钥攻击，该攻击可以在给定 2^99个输入输出对（它们是由4个相关密钥加密而成），可以在 2^99时间内恢复密钥
  2. 对可预测IV的CBC的攻击
    • 构造一个全零的，可以判断异或的值
  3. 针对带随机IV的CBC进行篡改攻击【作业里有】【随机IV的CBC不提供认证加密】
    • 笔记7.1节 篡改攻击,CBC可以通过修改IV实现
  4. CTR模式的选择密文攻击

对MAC的攻击

  1. MAC的安全边界
    • ECBC模式边界计算：通过使用的PRP大小来计算边界[AES,|X|=2^128;3DES, |X|=2^64]
    • (如果ECBC-MAC NMAC都是PRP实现)存在如下性质：如果找到一个认证消息的碰撞，那么认证消息接长也会碰撞
  2. CBC MAC填充攻击：如果是应用全0填充，那么攻击者可以通过构造消息末尾为全0的消息，并且提前询问攻击者消息的加密，pad(m)=pad(m||0)
  3. 对MAC认证的计时攻击
    • 产生原因：HMAC(key, msg) == sig_bytes 该代码在验证tag的时候，由于是逐个字节比对，可以根据时间来确定哪些位数是对的
    • 解决1：让比较总是花费相同时间
    • 解决2：不让攻击者知道哪个值被比较了

对Hash的攻击

  1. 通用生日攻击
    • 通用抗碰撞函数攻击：
      O(2n/2)O(2^{n/2}) 每次选2{n/2}个随机消息，暴力破解，如果不行，再选2{n/2}个，大概只需要2轮查询即可
  2. SHA
    • SHA1 不安全，输入160bits 通用攻击2^80
    • SHA256 安全 输入256bits 通用攻击2^128
    • SHA512 安全，输入512bits 通用攻击2^256
    • 量子计算机优化

对认证加密的攻击

对padding的攻击

  • Padding Oracle可以通过先加密再MAC避免
  • 先MAC再加密虽然提供认证加密，但是只有在不透露解密失败原因的时候
  1. 计时攻击：根据返回错的时间判断错误类型
  2. 针对CBC的padding oracle攻击
    • 根据CBC特性，更改前一个分组的密文就可以更改解密后的CBC的值，将其用padding 01 覆盖
    • 然后每次都提交，查看解密后返回的信息【是填充错误，还是其它】接下来，继续猜测，这次用02 02 覆盖
    • 使用CTR模式可以避免攻击：先MAC再CTR 因为不需要padding，自然也不存在padding oracle
  3. 对TLS实现IMAP的padding oracle攻击
    • 问题：TLS会在每次获取不合法消息之后重新协商key
    • 每五分钟客户端会向server发一个登录密钥
    • 攻击者还是可以通过padding oracle恢复出用户明文

非原子操作的解密攻击

  1. SSH二元包协议攻击
    • 协议：先解密长度；再读取对应长度的包，然后解密密文分组，最后检查MAC是否合法
    • 攻击：通过发送的“MAC error”判断消息m的长度，发送一个大小只有1的m，server先解密得到len，之后试图从收到的信息后获得len长度的消息，此时攻击者一个字节一个字节地发送消息，并且等待server发送“MAC error”（表示消息长度是对了，但是没有通过MAC的校验）====>攻击者获得明文中len的信息
    • 非原子操作的解密，以及在正确认证之前就使用解密内容是不安全的。
    • 如何更改SSH？
      • 直接使用明文的长度域(可以防止CCA)
      • 单独对长度(seq-num,length)进行MAC验证，加在len明文后
      • 将先加密+MAC改成先加密后MAC没有用，因为还是会泄露长度域
      • 可以更改长度域名，通过每次收取一个字节信息就用MAC来识别包的边界，可以但是要花费大量时间

对公钥加密的攻击

对RSA的攻击

  1. 计时攻击：计算c^d(mod N)的时间可能会暴露私钥d
  2. 功耗分析
  3. 解密错误攻击(比如，检查解密错误，可能会重新计算一下解密后的密文和收到的密文是否一样，这个耗时会暴露d)
    • 举例：CRT-RSA中国剩余定理RSA(如果计算xq发生错误但是xp没有，那么就可以计算出p)
    • 举例：RSA密钥生成问题：如果使用同样的p生成RSA密钥，那么则会导致不同设备的N有相同的因数p

第八周随便提一点

考试形式：闭卷考试，题型：填空题（20分）选择题（20分）大题4道，每道题15分左右，选择填空一般是零散的知识点，如OTP的密文如何得到对应明文，如何解密；

算法安全性：如作业中的，哪些哈希算法是安全的，，3des安全吗，AES安全吗，md5安全吗，sha1安全吗 sha256安全吗；认证加密，如果随机初始向量CBC模式，先加密后认证安不安全；公钥；；；

答题：会有简答题：概念性的东西，公钥加密和对称加密的区别和概念，有对称加密为什么还要有公钥加密；如果用纯对称的做密钥交换，代价很大，gap最多是n^2 如果有公钥加密，gap会达到指数

从定义上来说，对称:直接加密消息；公钥加密，用于传输

简答题，提一些协议的漏洞，TLS的漏洞，padding oraacle攻击，什么pp协议，WAP协议的漏洞讲一下上课讲过的漏洞

大题可能和作业有些类似，内容更多，成体系的东西比较多；建议看确定性加密

TLS协议一定要考 讲了很多TLS

考试：考过Dlog原理的hash抗碰撞

上课透了：：：：注意公钥加密的CPA安全性的定义

补充了：群签名的例子：给所有的用户相同的私钥

第十周：回顾

  1. 秘密共享;Shamir秘密共享是怎么做的。(不会考证明，但是会考公钥加密CPA安全性)门限秘密共享怎么利用拉格朗日插值；(n,t)，给定t-1个点可以重构，t个点不能
  2. 流密码：
    • OTP的定义；根据消息和密文恢复密钥
    • 流密码将OTP变为实际可用的(伪随机生成器：安全性要求【不可预测性】)
    • 攻击：PPTP协议的问题；WEP的问题(至少三次的问题，到底有哪些脆弱性，理出来);OTP完整性攻击(篡改密文 from bob from eve )；
    • RC4的缺陷(WEP);Salsa20的构造(很无聊，知道他是安全的；要知道哪些流密码是安全的哪些是不安全的；标准化的东西记住也没有用)
    • 语义安全性：不会考太多，没有太多有关语义安全性的证明题；更多是分析以及找到一些攻击
    • 证明的部分不用花太多时间，要理清楚他们之间的关系：（异或）；攻击比较容易考(11:39)
    • 攻击多看
  • 第十周应该要提一点了吧

Dan Boneh Problem Set

答案1
答案2

Week1

  1. 判断安全的PRG
    • 选项1：A：区分首位是不是1，Adv=1/2
    • 选项2：如果G’可以由A区分，则G也可以由G区分(异或1，分布不变)，与题干矛盾
    • 选项3：k是随机选取的，异或1，分布不变
    • 选项4：判断LSB是不是等于0，Adv=1/2
    • 选项5：去除最后一个bit，不影响G的安全性
    • 选项6：判断第一个bit和第n+1个bit是否一样即可
  2. 判断一次性的语义安全
    • 选项1：询问 0n0^n 和 0n−110^{n-1}1 可以区分EXP(0)和EXP(1)【全0，和全0接一个1，如果全0，那么输出结果最后一位肯定是0，另一个m，输出结果最后一位肯定是1，Adv=1】
    • 选项2：如果E’不安全，则E也一定不安全，与题干矛盾。(我也不知道为什么，但是感觉就是对的)
    • 选项3：不能上当了，虽然这个很随机，但是直接把key接在E后面，攻击者直接可以用k解密
    • 选项4：输出两次密文：攻击者无法获取任何信息，如果要破解E’，必然要先破解E。(不能把他和真随机比，因为这是语义安全性，不是在判断PRG)
    • 选项5：加不加0对攻击者都没有影响，因为加0这个行为其实没有暴露可以区分m0和m1的方法
    • 选项6：破解攻击很简单，构造 0n0^n 和 1n1^n 全0输出还是全0，全1输出是全1 Adv=1

Week2

  1. 判断安全PRF
    注意看，正确的选项都是直接用了安全的PRF，直接输出，都可以将他们转换为真随机，转换后的结果仍然是真随机
  2. 两轮Feistel网络
    根据提示，攻击方法如下：
  3. 基于Nonce的CBC，但是Nonce用和加密一样的key k作为PRP的输入
    因为有点简单，就是列举一下，不写过程了
  4. CBC加密长度为l个分组的密文，如果第l/2个分组出现问题，会影响2个密文的解密；CTR模式，同样长度为l但是第l/2个密文出问题，只会影响一个密文的解密

Week3

  1. 这题，不太理解，感觉都不对，难道选第一个选项是对的？只有更改了文件内容才会认证失败，难道更改名字不会失败吗
  1. MAC的安全性
  2. ECBC-MACB使用固定IV的攻击：
    • 使用r作为初始向量，通过对IV异或可以做到更改m的目的
  3. 这题说的是把消息m的最后一个bit进行更改，加解密需要使用AES的次数，记住CBCMAC需要加密两次；这题要先把原消息m的最后一个分组解密，然后再更改成m’，再加密
  4. 抗碰撞
    • 32次方太短了，可以在 2^16时间内攻破
  5. 碰撞需要的样本数量计算
    • 2次碰撞：T的大小是tag空间，如果两次碰撞，只需要尝试 O(∣T∣1/2)O(|T|^{1/2}) 个消息即可
    • 3次碰撞：假设需要n个样本，n个样本的三层碰撞的组合有 n3n^3 种，由于两个H函数的碰撞概率(H(x)=H(y))为 1/∣T∣1/|T| ，构造三层碰撞需要 H(X)=H(y);H(x)=H(z)同时成立，同时成立的概率是 1/∣T∣21/|T|^{2} 则三次碰撞的概率是 O(n3/∣T∣2)O(n^3/|T|^2) 由于需要概率趋于1，这里不妨直接令 n3/∣T∣2=1n^3/|T|^2=1 则可以计算出，需要 O(∣T∣2/3)O(|T|^{2/3})

Week4

  1. 经典针对CBC的完整性攻击
  1. 判断认证加密
    • 认证加密：密文完整性CI+选择密文攻击安全性CCA安全
    • 2不是认证安全，原因可以看3，2没有保证两个明文都是正确的
    • 4不是认证安全，因为4是encrypt-and-MAC是不安全的
  2. 认证加密提供CCA安全，同时也满足many time key的安全
  3. 如何通过对称加密构造一个MAC?==需要对称加密满足认证加密的要求(MAC安全，则MAC需要不能被存在性伪造，由于认证加密不存在存在性伪造，因此MAC也不会存在存在性伪造，就是安全的MAC了)
  4. KDF，奇怪的题目，让你挑一个在k均匀分布的时候安全但是在k不是均匀分布的时候不安全的PRF
  5. 什么情况下可以使用DAE(确定性认证加密)
  6. CBC攻击的次数
    • 每个bit攻击2^8=256次*48个字节=12288次

Week5

  1. 利用DH问题难解的性质
    • 如果DH难解，那么由DH组成的f也一定是难解的
  2. 别搞反了：只要记住A只知道a，B只知道b就可以
  3. 玩具协议加MAC可以防止中间人攻击吗？
    • 加MAC并不能阻止中间人攻击，因为攻击者还是可以生成称自己的pk’，发给A和B，照样执行中间人攻击
  4. 欧拉定理和费马定理计算阶乘应用
  5. 解得方程

Week6

  1. 公钥加密可以像对称加密一样，加密后的结果是32bit吗？
    • 显然不能，因为2^32长度对的密文太短了，会导致字典攻击来解密
  2. 公钥加密(Gen,E,D)使用的加密算法E可以是确定性加密吗？
    • 不能，因为E中一定要有随机元素，不然就没有CPA安全了
  3. 判断安全的公钥加密系统
    • 1不是安全的，不能保证传输过程中，密文被篡改
    • 2不是CCA安全的，因为攻击者可以询问m0=0128和m1=1128的两个消息，获得一个挑战密文(c1,c2)，然后攻击者构造一个新的明文m0，并且将其加密为c3，然后请求challenger对(c1,c3)进行解密，如果解密结果是m0或者错误输出；如果结果是m0，表示c1是m0,则表示c1=c3，均为m0的加密，即在exp0，如果输出错误，则表示在exp1
    • 3是安全的，因为1的第二个密文没啥用，相当于一个公钥加密
  4. 使用y分解N？？？？【很迷惑的一道题】
    • 找到一个偶次方根不为1的
  5. N分解三个素因数
  6. N由三个相同的相近素数产生，那么d的边界是？？？【没搞懂这道题】
    • 边界是1/6，是因为N-fai(N)现在是N^{2/3}的秩

Week7

  1. 一个均匀分布s和一个随机数异或是0，那么概率就是1/2^{n}

  2. 各种安全性的梳理

    • 完美安全：密钥长度一定要大于等于消息长度
    • 语义安全性(一次密钥的语义安全性质)：只能询问一次m0，m1
    • CPA安全：many time key 可以进行多次询问，每次询问的结果用一个key加密而成，随机获得0，1里的一个值的加密。确定性加密一定没有CPA安全
    • 确定性CPA安全：cpa安全的基础上，限制加密者不会加密相同的明文两次
    • CCA安全：可以无限询问密文的解密，但是只能询问一次m0，m1的加密内容，目的是要猜出是m0还是m1的加密

  3. CBC用PRP,CTR用PRF

  4. 不懂但是做对了：对使用一个key去加密2^32个消息的对称加密，如果需要使其具有CPA安全，那么需要应用新鲜值，新鲜值的长度？

    • 原因是用了生日攻击？？
    • 不太懂啊啊啊

  5. 不懂但是做对了；为什么计数器模式可以只用32bit长度的nonce，但是不用计数器的需要2^128

  6. 安全的MAC的定义

    • 为什么是给定一个k，后半句可以理解

  7. 碰撞检测的定义

  8. 语义安全的定义

  9. DH密钥交换协议

密码学透透🤣

开源精神互相帮助捏

====秘密共享

  • Shamir秘密共享是怎么做的。(不会考证明，但是会考公钥加密CPA安全性)门限秘密共享怎么利用拉格朗日插值；(n,t)，给定t个点可以重构，t-1个点不能

====流密码

  1. OTP的定义；

    • 定义：M=C=0,1nM=C={0,1}^n K=0,1nK={0,1}^n K是一串随机选取的和消息长度一样的bit
      • OTP定义
    • 根据消息和密文恢复密钥
      恢复密钥

  2. 流密码将OTP变为实际可用的(伪随机生成器：安全性要求【不可预测性】)

    • 流密码的组成：使用PRG构成流密码
      流密码
    • 伪随机生成器的安全要求
      • PRG安全性：定义统计测试算法A(输出0 伪随机，输出1 真随机)，一个PRG G，一个真随机r；定义A对G的优势：AdvPRG[A,G]=∣Pr[A(G(k))=1]−Pr[A(r)=1]∣Adv_{PRG}[A,G]=|Pr[A(G(k))=1]-Pr[A(r)=1]| 如果该优势 AdvPRGAdv_{PRG} 是接近1，表明A可以将G与真随机区分，反之接近0 表示不可区分

  3. 攻击：PPTP协议的问题；WEP的问题(至少三次的问题，到底有哪些脆弱性，理出来);OTP完整性攻击(篡改密文 from bob from eve )；

    • two time pad示例：MS-PPTP
      发送方和接收方的key都是G(k)，正确方法应该是双方共享一对密钥
    • WEP的问题
      1. 对802.11b WEP的主动攻击【完整性攻击】
        • 注意，CRC是线性的，这表示 ∀m,p:CRC(m⊕p)=CRC(m)⊕F(p){\forall}m,p: CRC(m \oplus p) = CRC(m) \oplus F(p)
      2. 802.11b WEP
        k不变，IV变，IV24bit，k104bit（不变），在2^24之后，IV会出现重复，且有些802.11会在重复后重置为0===>出现two time pad
        • 解决方法：k作为PRG输入，输出的结果分段，每个分段作为一个key==>每个包有一个伪随机生成的key
      3. RC4使用WEP
    • OTP完整性攻击
      • OTP无完整性、可修改性：修改密文攻击 解密后，得到 m⊕pm \oplus p 密文已经被改变但是接收者无法察觉
        攻击举例：

  4. RC4的缺陷(WEP);Salsa20的构造(很无聊，知道他是安全的；要知道哪些流密码是安全的哪些是不安全的；标准化的东西记住也没有用)

    • RC4
      1. 初始输入不均匀，比如存在 Pr[2ndbyte=0]=2/256Pr[2^{nd}byte=0]=2/256
      2. 出现连续两个0的概率是 1/2562+1/25631/{256^2}+1/{256^3}
      3. 密钥之间存在关联
    • 安全的流密码和不安全的流密码：
      1. RC4 不安全
      2. CSS 基于LFSR 已经被破解(2^17时间)
      3. estream:Salsa 20【安全的】
  • 语义安全性：不会考太多，没有太多有关语义安全性的证明题；更多是分析以及找到一些攻击
    • 语义安全性： 定义了两个实验，优势为在两个实验中输出1的概率的差，如果对所有有效的A语义安全优势 Advss[A,E]Adv_{ss}[A,E] 是可忽略的，则称之为语义安全的
      • 注意：语义安全性，A只能给挑战者发送一次明文，只能询问一次密文，挑战者的密钥只使用了一次
      • 语义安全性例子：可推断LSB的算法A安全性(从输出的角度)、OTP的安全性(从分布的角度)
  • 证明的部分不用花太多时间，要理清楚他们之间的关系(比如流密码：随机生成器和消息异或，会出现什么样的攻击)；攻击比较容易考(11:39)
    • 太抽象了，不知道在说什么，感觉是要把各个密码的理论构造看懂
  • 攻击多看
    • 攻击比证明重要，哈哈

====分组密码

  1. DES为什么不安全？因为S盒有线性关系；DES使用feistel网络；AES没有用Feistel网络；
    • 密钥搜索只需要2^24时间
      • 线性密码分析：DES的S盒设计缺陷导致
      • 如果c是DES(k,m)，对于随机的k，m，有
        • 对于DES， ε=1/221{\varepsilon}=1/2^{21}
      • 因此对于 1/ε21/{\varepsilon}^2 个随机明文、密文对，通过异或明文与密文，可以获得key的子集的概率大于等于97.7%
      • 对于DES, ε=1/221{\varepsilon}=1/2^{21} ，则可以在 2^42时间内获得key的子集(14bit)
    • 中间相遇攻击2DES(知道就可以)
  2. 实现中出现的问题：侧信道，时间攻击，错误攻击
    • 测信道攻击：包括计时攻击，针对功率的攻击，
    • 错误攻击：对解密者返回的错误进行分析
  3. 线性分析不考，知道对对称密码来说，线性分析很简单，就可以对其进行破解
  4. 只要知道AES是安全的就好；AES和3DES相同的安全等级下，谁的效率更高：AES效率更高；3DES：加密一次解密一次再加密一次；效果不好

====分组密码的使用

【着重看CBC模式的加密，怎么做的】

  • CBC模式：
    • 加密：
    • 解密：
  1. 使用模式的安全，哪些安全哪些不安全。

    • DESX的穷尽搜索攻击(中间相遇攻击)

    • ECB模式不是语义安全的

      • 加密不同的m，ECB方法总是使用同一个key；导致m1=m2.c1=c2
      • ECB不是语义安全的【如果明文分组超过1个分组】，证明：
        Adv=1的攻击方法：

    • CBC模式

      1. 对可预测IV的CBC的攻击 不是CPA安全的
        • 构造一个全零的，可以判断异或的值
        • 可以使用基于新鲜值的CBC解决，需要两个k
          基于新鲜值的CBC
      2. 针对带随机IV的CBC进行篡改攻击【作业里有】【随机IV的CBC不提供认证加密】
        • 7.1节 篡改攻击,CBC可以通过修改IV实现
      3. 针对CBC的padding oracle攻击
        • 根据CBC特性，更改前一个分组的密文就可以更改解密后的CBC的值，将其用padding 01 覆盖
        • 然后每次都提交，查看解密后返回的信息【是填充错误，还是其它】接下来，继续猜测，这次用02 02 覆盖
        • 使用CTR模式可以避免攻击：先MAC再CTR 因为不需要padding，自然也不存在padding oracle
      4. 随机IV的CBC不是CCA安全的

    • CTR模式

      • 确定CTR模式，由PRF构成，是一次密钥语义安全的
      • 有选择密文攻击：
  2. CBC模式的加密：需要使用随机IV，如果IV不随机，会导致什么安全性后果，如果IV可预测会出现什么问题,TLS1.0版本的bug
    • 可预测CBC，看上一个

=====MAC

  1. 消息认证码，有些上课提到过：消息认证码和数字签名的关系；
    • 签名只有发送发可以加密，任何人都可以验证;MAC只有收方可以验证(可以同时确认来源以及防止篡改)
  2. MAC的定义，以及安全MAC的定义；存在性伪造的定义，CPA下的存在性伪造的定义;所有的伪造的方法以及伪造后怎么修复；存在性伪造会有一个简单的让你伪造的题目
    • MAC的定义：
      MAC定义
    • 存在性伪造(针对MAC CPA安全的存在性伪造)：
      存在性伪造
    • 安全MAC的定义：多次询问挑战者tag，最后伪造一个可以通过检验的新MAC
      定义
      安全MAC
    • 所有的伪造的方法以及伪造后怎么修复(MAC这块好像没找到)
      • 基于PRF的MAC(针对短消息的)[这个修复只能想到换一个key]
        • 安全性计算：如果F是安全的PRF,且F的输出空间 |Y| 足够大，则由此PRF构造的MAC是安全的MAC
        • 存在一个对于MAC的敌手A，且存在一个PRF敌手B，使得

          AdvMAC≤AdvPRF+1/∣Y∣Adv_{MAC} \le Adv_{PRF}+1/|Y|

      • NMAC与CBC-MAC确实有伪造；
        1. ECBE-MAC没有最后一步加密：使用一次选择消息攻击就可以轻松伪造(放在下一节)
        2. NMAC没有最后一步加密：使用一次选择消息攻击就可以轻松伪造:先询问m的tag1，再询问tag1 xor w的tag(cascade(k,m||w))，然后 cascade(k,m)=>cascade(k,m||w)
        3. 安全边界
          • ECBC模式边界计算：通过使用的PRP大小来计算边界[AES,|X|=2^128;3DES, |X|=2^64]
          • (如果ECBC-MAC NMAC都是PRP实现)存在如下性质：如果找到一个认证消息的碰撞，那么认证消息接长也会碰撞
            alt text
          • 解决方法：使用随机构造
            随机构造
  3. 着重看一下ECBC-MAC(encrypted CBC-MAC = CBC-MAC)会有什么问题
    • 需要两个key
    • 通过PRP定义一个新的PRF：
    • 如果没有最后一步…也会被选择明文攻击攻破，选一个分组大小n的消息， 获得认证消息，然后接长原来的消息，可以通过t，pt构造出合法的MAC
    • AdvPRF[A,FECBC]≤AdvPRP[B,F]+2q2/∣X∣Adv_{PRF}[A,F_{ECBC}] \le Adv_{PRP}[B,F]+2q^2/|X| 当 q<<∣X∣1/2q<< |X|^{1/2} 时，CBC-MAC安全

===hash

  1. hash和数字签名结合在一起考
  2. 生日攻击；以根号t的时间找到，hash至少要160以上；要了解一下这个(阈值？？)
    • 通用生日攻击：通用抗碰撞函数攻击：
      O(2n/2)O(2^{n/2}) 每次选2{n/2}个随机消息，暴力破解，如果不行，再选2{n/2}个，大概只需要2轮查询即可
      • 原理：生日悖论
    • 通用攻击时间
      alt text
  3. 哪些hash安全哪些不安全
    alt text
    • SHA1 不安全，输入160bits 通用攻击2^80
    • SHA256 安全 输入256bits 通用攻击2^128
    • SHA512 安全，输入512bits 通用攻击2^256
    • 量子计算机优化

===认证加密

  1. padding oracle的攻击实验；以及它的原理

    • Padding Oracle可以通过先加密再MAC避免
    • 实验：针对CBC的padding oracle攻击
      • 根据CBC特性，更改前一个分组的密文就可以更改解密后的CBC的值，将其用padding 01 覆盖
      • 然后每次都提交，查看解密后返回的信息【是填充错误，还是其它】接下来，继续猜测，这次用02 02 覆盖
      • 使用CTR模式可以避免攻击：先MAC再CTR 因为不需要padding，自然也不存在padding oracle

  2. 对于WEP不考(不考大题)，要把TLS的注意一下，TLS要考大题；以及它的缺陷怎么修复

    • TLS协议哈希函数：使用HAMC-SHA1-96
    • TLS1.2 (TLS记录协议)【先计算MAC再加密】
      • 有两个单向密钥k_{b to s} 和 k_{s to b} ;每个方向维护一个计数器ctr
      • 加密 CBC-AES 128 HMAC-SHA1;E(k,data,ctr)
        • 先算tag，再pad，再CBC加密，再接到header后
      • 解密
        • 先CBC解密，pad失败则发送失败；检查tag，检查失败则发送失败
      • TLS 1.1漏洞
        1. CBC的IV是可预测的；下一个IV是本次记录的最后一个密文分块，不是CPA安全的
        2. 有padding oracle攻击：根据服务器返回的错误消息，可以得知密文的padding是否有效，（对不同的错误会返回不同的响应）
      • 长度泄露：TLS头会泄露TLS记录的长度(也可以通过监听网络流量获取)
    • 对TLS实现IMAP的padding oracle攻击
      • 问题：TLS会在每次获取不合法消息之后重新协商key
      • 每五分钟客户端会向server发一个登录密钥
      • 攻击者还是可以通过padding oracle恢复出用户明文
        TLS的padding oracle

===密钥交换

  1. 要知道密钥交换怎么做的，怎么实现的
    • 密钥交换DH协议
      DH协议

===数论

  1. 计算 \fai(N)，N=pq的时候
  2. 对于比较大的指数，要会求 m^e mod n 的结果，会用欧拉定理；指数值很大怎么计算，比如5^1000怎么计算；
    计算

===RSA

  1. RSA公钥加密怎么做
    • RSA陷门置换：加密：消息求e次方，解密：消息求d次方

      - RSA假设：RSA是一个单向置换(对于不知道sk的人来说，求出e的逆元很困难)
    • RSA公钥加密：
  2. textbook RSA是怎么做的；对教科书RSA的攻击(有点像中间相遇)
    • 直接使用RSA进行加密是不安全的；示例一个攻击：
      • 攻击者可以进行类似中间相遇攻击的办法对教科书RSA进行攻击
  3. 要会写RSA陷门(基本功)
  4. 要知道CPA安全性的定义(公钥安全的)
    • 公钥加密的语义安全性(IND-CPA)
  5. 假如给你一个方案，你要会证明CPA安全性，可能需要规约；课本上会归约到困难问题，有时候也会归约到两个算法的问题；归约到陷门函数。
    • 例如，从陷门函数构造公钥加密，归约到陷门函数的安全
      alt text
    • 感觉可以参考ElGamal的语义安全证明，用到两次规约
    • HDH下，ElGamal的语义安全性证明
      • 由于公钥加密，语义安全=CPA安全，证明如下：

===Elgamal(自己加的 )

  • 有一道大题有关ELGAMAL，和DH密钥协商类似；基于椭圆曲线
    • 这是在说谜语吗，ELGAMAL到底要啥？只能把ppt 12-pubkey-dh-annotated全看一遍了

===数字签名

  • 数字签名考的不是很多，概念知道就可以了，数字签名和hash结合会有一道小题；会少一些数字签名
    1. 抗碰撞Hash函数扩展签名输入的大小
      alt text
      • 题目答案是3，因为如果H不是抗碰撞的，那么一定可以找到m0和m1.导致可以伪造签名
    2. 全域哈希签名
      • 在全域哈希中，哈希函数的选择不是固定的，而是从一个哈希函数的集合中随机选择的。
      • 构造alt text
        • 形式：
      • 安全性证明：
      • 如果不使用全域哈希，则会导致存在性伪造
        • 为什么
    3. RSA-FDH
      • RSA-FDH
      • 形式：
      • 例子 PKCS1 v1.5:
信息安全技术
https://mapllle.site/2024/03/11/StudySHUSHU/Crypto/
作者
MAple
发布于
2024年3月11日
许可协议