Symmetric Ciphers对称加密

Classical Cryptography加密Encryption 加密算法解密Decryption 解密算法Modern cryptography加密 加密算法 密钥Secret Key解密 解密算法 密钥对称加密同一套密钥负责加密和解密而且必须满足 解出来的肯定是原来的内容A and B have the same key. andD (k,E (k,m))m加密E密钥明文 密文解密D密钥密文 明文1 Stream Ciphers流密码One-Time PadOTP一次一密c E(k,m) k⊕mm D(k,c) k⊕ck m⊕cSecret key isas long asmessages to be encrytedEach secret key will beused once onlyChoose secretkey randomly有完美的保密性但过于理想每次都用新的且要与信息等长消耗太大无法现实使用。Pr[E(k,m0)c] Pr[E(k,m1)c]即k在密钥空间中均匀分布无法从密文中得到明文的信息异或XOR的重要性质一个随机变量XOR一个独立均匀变量 一个均匀变量PRG伪随机生成器解决密钥太长replace random key by pseudorandom keyPRGmust beunpredictable不可预测把短密钥 “拉长”代替 OTP 里的长钥匙需要不可预测知道前面的几位不能猜出后面的不是完美安全的Stream Ciphers 流密码(由PRG创造)用 PRG 生成的乱码和明文做拼图匹配E(k,m)m⊕G(k) 加密 明文⊕由密钥生成的伪随机序列D(k,c)c⊕G(k) 解密 密文⊕由密钥生成的伪随机序列缺点同一密钥不能用两次没有 “防篡改” 功能不能用于磁盘加密--很容易定位哪里修改了重复使用OTP或流密码是不安全的两次的结果异或可以得到两条明文的异或结果PRG安全希望输出的伪随机与真随机是不可区分的statistical test统计测试A是一个关于{01}^n的统计测试区分器输出1表示是认为是PRG的输出输出0表示认为是真随机数Pr是概率G伪随机数生成器优势AdvantageAdvPRG[A, G] | Pr[A(G(k))1] - Pr[A(U)1] |属于[0,1]核心公式本质上都是 “攻击者通过统计测试区分 PRG 输出与真随机串的概率差的绝对值”优势接近1--A能区分G和随机数优势接近0--A无法区分G和随机数题A(x) LSB(x), Pr[LSB(G(k)0)]1/2 ①(A,G) LSB(G(k1,k2)) LSB(G(k1)^G(k2)) LSB(G(k1))^LSB(G(k2))^is AND function--only just when LSB(G(k1))0 and LSB(G(k2))0, LSB(G(k1))^LSB(G(k2))0 ②because of①②--Pr(LSB(G(k1))^LSB(G(k2))0)1/2*1/2 1/4Adv_PRG[A,G] |Pr[A(G)0]-Pr[A(U)]0| |1/4-1/2| 1/4Semantic security语义安全密文不泄露任何关于明文的 “有用信息”对于任意两个明文m_1, m_2长度相同以及任意攻击者A若A无法区分 “m_1加密后的密文c_1” 和 “m_2加密后的密文c_2”则方案满足语义安全。攻击测试Advadversary攻击者给挑战者发送两条明文m0和m1Chal.挑战者随机选一条消息m0或m1加密得到密文c并将c给Adv优势计算两条明文加密后结果的概率相减看Adv是否能判断出是哪条明文被加密了不能每次加密用的k都是一样的不能直接把k接在m后面加密Negligible and non-negligible可忽略和不可忽略密码学里只要攻击成功的概率是 “可忽略” 的就认为这个加密方法是安全的2 Block ciphers分组加密将固定长度的明文块加密为相同长度的密文块的对称加密算法。对称性加密和解密使用同一个密钥k。固定分组长度如 AES 的分组长度为 128 位16 字节。确定性对于相同的明文块和密钥输出的密文块总是相同的除非结合工作模式引入随机性。例子3DESn 64bits,k 168bitsAES:n 128bits,k 128,192,256bits迭代构建分组加密密钥k作为输入k被扩展为子kiround轮密钥R(k,m)轮函数接收轮密钥和消息m的当前状态结果输出到下一轮经过n轮后输出密文c。PRFs伪随机函数Pseudorandom Function密钥和输入一起 映射到一个输出空间F:{0,1}^κ×{0,1}^n→{0,1}^m其中κ密钥长度n输入长度m输出长度通常 mn 或固定值对每个密钥 kFk​(⋅)F(k,⋅) 是一个从 n 位到 m 位的确定性函数。对于不知道密钥 k 的攻击者来说访问 Fk​(⋅) 就像在访问一个真正随机的函数即每次输入不同输出看起来完全随机且不可预测。PRF安全如果对所有概率多项式时间PPT攻击者 A该优势都是可忽略函数negligible则称 F 是一个安全的 PRF。特点不要求是双射即不要求一一对应多个不同输入可能映射到相同输出允许碰撞常用于 MAC如 HMAC、密钥派生KDF、流密码构造等。PRPs伪随机置换Pseudorandom PermutationE:{0,1}^κ×{0,1}^n→{0,1}^n满足对每个密钥 kEk​(⋅) 是一个双射bijection即一个置换permutation一对一存在高效的逆函数 Dk​Ek−1​使得 Dk​(Ek​(x))x。PRP 是一个可逆的 PRF且其输出空间与输入空间相同并构成一个排列。安全分组密码就是需要成为安全伪随机置换。PRF 生成 PRG数据加密标准DES64bits输入初始置换重新排列--16轮Feistel网络--初始置换逆操作--得到输出Feistel网络将输入分为R0 L0左右两个块初始的R0放到下一轮的L1下一轮的R1是这轮的f(R0) ROX L0S盒Substitution-box替换盒S盒是分组密码中实现非线性替换的基本结构。DES中输入 6 位输出 4 位通过查表实现非线性替换表格如下所示Exhaustive Search穷举搜索攻击尝试所有可能的密钥直到找到能正确解密出有意义明文的那个密钥。DES挑战可以被穷举搜索攻击破解密文3DES 是对 DES 的加强用三次 DES 操作通常是 E-D-E 模式来提升安全性。为什么不用 2DES因为中间相遇攻击meet in the middle attack使其有效安全强度仅为 ~57 位远低于预期的 112 位。攻击步骤正向用所有可能的 k1​ 加密明文 P得到中间值 XEk1​​(P)存入表。反向用所有可能的 k2​ 解密密文 C得到 X′Dk2​​(C)。找到 XX′ 的配对 → 对应的 (k1​,k2​) 就是候选密钥。AES高级加密标准高级加密标准Advanced Encryption Standard是目前最广泛使用的对称分组密码。项目值分组长度固定128 位16 字节密钥长度128、192 或 256 位对应 AES-128、AES-192、AES-256加密轮数10 轮128 位密钥、12 轮192、14 轮256核心结构SPN 网络AES 基于SPNSubstitution-Permutation NetworkS非线性替换通过S盒P线性扩散行移位 列混淆每轮操作包括最后一轮只有2、3AddRoundKey与轮密钥异或XORSubBytes每个字节通过 S盒非线性替换提供混淆ShiftRows状态矩阵的行循环左移增加扩散MixColumns每列进行线性变换进一步扩散基于PRG的分组密码PRF构建GGM 构造PRG将一个长度为n的种子扩展成一个长度为m的输出其中m n。PRF对于不同的输入x输出PRF(k, x)看起来是完全随机且独立的。把输入k当作二叉树路径用 PRG 逐层展开重复多次得到kn非常慢但只要PRG安全PRF就安全Many-time key指同一个密钥被用于加密多个消息。这在现实中非常常见比如你用同一个 Wi-Fi 密码加密每天的上网数据。只要加密方案设计正确如带随机 IVmany-time key 是安全的。如果方案是确定性的如 ECB 或重复使用 nonce就会出问题。选择明文攻击Chosen-Plaintext Attack,CPA一种安全模型用于评估加密方案的安全性。同一明文加密得到的密文相同选择明文加密攻击者给两个一样的信息m0,m0获取他选择的特定消息m0的密文之后再发m0,m1看密文就能知道那个消息被加密了这是不安全的。CPA安全的模型允许many-time keyNonce-based 加密NonceNumber used once仅使用一次的数它不需要保密通常随密文一起传输在同一个密钥下nonce 绝不能重复使用不一定需要随机但常是随机或计数器计数器的范围要够大不能重复只需唯一性。引入 nonce 后每次加密cEnck​(nonce,m)nonce 不保密随密文一起发送。即使 m 相同只要 nonce 不同密文就不同 → 实现CPA 安全。CBC密码块连接CBCCipher Block Chaining密码块链接是一种经典的分组加密工作模式用于将固定长度的分组密码如 AES、DES扩展为可加密任意长度消息的安全方案。引入初始向量IV和链式异或使相同明文块加密后产生不同密文消除 ECB 模式的模式泄露问题。基于nonce的CBCrand ctr-mode随机化计数器模式随机化计数器模式Randomized CTR Mode是CTR 模式Counter Mode的一种标准安全用法核心在于使用随机 nonce来实现CPA 安全的加密。CTR 模式基本思想CTR 将分组密码如 AES转换为流密码不直接加密明文而是用密钥 k 加密一个递增的计数器值生成 keystream明文与 keystream 异或得到密文Ci​Pi​⊕Ek​(counteri​)随机 nonce CTR 安全流式加密3.数据完整性message integrityMACMessage Authentication Code消息认证码保证消息的完整性、真实性。通过MAC签名算法生成一个短标签tag和m一起发送S(k,m)-t对方通过MAC验证算法计算tag是否是’yesV(k,m,t)-0,1同时要共享一个对称密钥k来保证消息不被篡改消息 M需要被认证的原始数据如文本、文件、网络数据包共享密钥 K发送方与接收方预先约定的秘密密钥双方独有第三方未知MAC 算法公开的哈希 / 加密类算法如 HMAC、CMAC用于将 “消息 密钥” 转化为固定长度的 MAC基本流程发送方 1. 持有 消息M 共享密钥K 2. 用 MAC 算法计算Tag MAC(K, M) 3. 发送 消息M 标签Tag 给接收方 接收方 1. 收到 消息M 标签Tag 2. 用自己的共享密钥K和收到的M计算 Tag MAC(K, M) 3. 对比 Tag 与 Tag - 若相等说明M未被篡改且发送方持有合法密钥来源真实 - 若不等说明M被篡改或发送方无合法密钥来源伪造特点完整性任何对消息的篡改都会导致 MAC 值变化接收方可通过对比发现篡改认证性只有持有共享密钥的合法方才能生成正确的 MAC 值可验证消息来源无抗抵赖性MAC 依赖共享密钥双方都持有无法区分是发送方还是接收方生成的标签因此不具备 “抗抵赖” 能力这是与数字签名的核心区别固定长度无论消息长短MAC 输出的标签长度固定如 HMAC-SHA256 输出 256 比特。一个安全的 MAC 必须满足不可伪造性Unforgeability under Chosen-Message Attack,UF-CMA即即使攻击者能获取任意(m,t)【允许发起选择消息攻击】也无法伪造新消息的有效 tag。没有加密的 MAC 内容公开但可信常见的 MAC 算法HMAC哈希消息认证码原理基于哈希函数如 SHA-1、SHA-256和共享密钥是应用最广泛的 MAC 算法特点无需依赖对称加密算法计算高效安全性由哈希函数和密钥强度保证典型应用HTTPS 协议的消息认证、API 接口签名如阿里云 / 腾讯云接口。CMACCipher-based MAC原理基于对称分组密码如 AES将消息分块后用密钥加密计算认证标签特点安全性与底层分组密码绑定适用于已部署对称加密系统的场景典型应用金融领域的交易数据认证、物联网设备的通信校验。GMACGalois/Counter Mode MAC原理基于 AES-GCM 模式的认证组件可同时实现加密和认证AEAD 算法特点支持并行计算效率高常用于高速通信场景典型应用TLS 1.3 协议、5G 通信的数据加密与认证。MAC 与数字签名的核心区别MAC 和数字签名都能实现消息认证但核心差异在于密钥体系和抗抵赖性特性消息认证码MAC数字签名密钥体系共享密钥对称密钥非对称密钥公钥 私钥核心能力完整性 来源认证完整性 来源认证 抗抵赖密钥持有方发送方和接收方都持有发送方持私钥接收方持公钥典型算法HMAC、CMACRSA-SHA256、ECDSA