临沧永德网站建设电子商务公司,腾讯云服务器app,网站推广平台,最新的电商资讯有哪些【现代密码学】笔记9-10.3-- 公钥#xff08;非对称加密#xff09;、混合加密理论《introduction to modern cryphtography》 写在最前面8.1 公钥加密理论随机预言机模型#xff08;Random Oracle Model#xff0c;ROM#xff09; 写在最前面
主要在 哈工大密码学课程 张… 【现代密码学】笔记9-10.3-- 公钥非对称加密、混合加密理论《introduction to modern cryphtography》 写在最前面8.1 公钥加密理论随机预言机模型Random Oracle ModelROM 写在最前面
主要在 哈工大密码学课程 张宇老师课件 的基础上学习记录笔记。
内容补充骆婷老师的PPT 《introduction to modern cryphtography》–Jonathan Katz, Yehuda Lindell现代密码学——原理与协议中相关章节 密码学复习笔记 这个博主好有意思
初步笔记如有错误请指正
快速补充一些密码相关的背景知识 8.1 公钥加密理论 本节学习用于保护信息的完整性和真实性的消息认证码MAC和抗碰撞的哈希函数CRHF。 目录公钥加密的定义和安全陷门排列选择密文攻击安全在随机预言机模型中从陷门排列到公钥加密。 私钥密码学局限性 密钥分发需要通信各方在物理上会面 U U U个用户的密钥的数量 Θ ( U 2 ) \Theta(U^2) Θ(U2)开放系统的安全通信基于私钥密码学的解决方案无法充分处理开放系统中的安全通信问题在开放系统中通信各方不能物理上会面或只能暂时交互注私钥密码学中的一个核心问题就是密钥分发与管理问题。 Needham-Schroeder 协议 Needham–Schroeder Symmetric Key Protocol在开放网络中双方通过一个可信的第三方建立一个会话密钥session key密钥分发中心Key Distribution CenterKDC作为可信的第三方Trusted Third PartyTTP与通信双方Alice和Bob在事前分别建立了对称密钥KDC根据Alice的请求生成一个新的 k k k 会话密钥session key分别用与Alice和Bob分别共享的密钥来加密并发送给Alice E B o b ( k ) E_{Bob}(k) EBob(k) 作为一个来访问Bob所需的凭证ticket用于MIT’s Kerberos 协议 (in Windows)优点每一方只需要存储一个密钥不需要更新通信双方密钥因为采用新的会话密钥弱点单点失效一旦KDC被破坏则整个系统都不安全。 Merkle难题无需可信第三方的密钥交换 Alice准备 2 32 2^{32} 232 个难题 P u z z l e i \mathsf{Puzzle}_i Puzzlei并且发送给Bob难题如下 P u z z l e i ← E n c ( 0 96 ∥ p i ) ( “Puzzle #” x i ∥ k i ) , \mathsf{Puzzle}_i \gets \mathsf{Enc}_{(0^{96}\|p_i)}(\text{Puzzle \#} x_i \| k_i), Puzzlei←Enc(096∥pi)(“Puzzle #”xi∥ki),其中 E n c \mathsf{Enc} Enc 是 128位加密 p i ← { 0 , 1 } 32 p_i \gets \{0,1\}^{32} pi←{0,1}32 并且 x i , k i ← { 0 , 1 } 128 x_i,k_i \gets \{0,1\}^{128} xi,ki←{0,1}128。 注每个难题中明文包括一个随机数和一个密钥用一个密钥加密 Bob随机选择一个难题 P u z z l e j \mathsf{Puzzle}_j Puzzlej并且在 2 32 2^{32} 232 时间内猜测 p j p_j pj 获得 x j , k j x_j,k_j xj,kj 并将 x j x_j xj 发送给 Alice。 Alice 按照 x j x_j xj查询谜题并且使用 k j k_j kj 作为密钥。 敌手需要 2 32 32 2^{3232} 23232 时间是诚实方所需时间复杂性的二次方。 在诚实方和敌手之间存在更好的差距吗如果将加密方法看作是一个黑盒预言机那么二次差距是最好的。 Merkle难题的缺点是谜题数量太大获得密钥的代价太大 注Merkle当时是UC的一名本科生这是他的一门课程设计申请。 公钥革命 在1976年Whitfield Diffie 和 Martin Hellman 发表了 “New Directions in Cryptography” 密码学的新方向。在这篇论文中提出公钥加密方案、陷门Trap door和数字签名等概念。论文原文链接非对称Asymmetric或公钥public-key加密方案: 公钥Public key作为加密密钥注接收方产生发送方持有私钥Private key作为解密密钥 注接收方产生接收方持有 公钥原语Public-key primitives: 公钥加密Public-key encryption数字签名Digital signatures (不可抵赖性non-repudiation)交互式密钥交换Interactive key exchange 优点 在公开信道上密钥分发减少保存大量密钥的需求使得在开放系统的安全成为可能 缺点慢两到三个数量级针对公钥分发的主动攻击 注如何保证Alice得到的公钥真的是Bob的公钥 公钥加密定义 密钥生成Key-generation算法: ( p k , s k ) ← G e n (pk,sk) \gets \mathsf{Gen} (pk,sk)←Gen, 密钥长度 ≥ n \ge n ≥n明文空间 M \mathcal{M} M 与 p k pk pk 相关注公钥加密方案通常以数学难题为基础明文与公钥之间并不完全独立加密Encryption算法: c ← E n c p k ( m ) c \gets \mathsf{Enc}_{pk}(m) c←Encpk(m).解密Decryption算法 m : D e c s k ( c ) m: \mathsf{Dec}_{sk}(c) m:Decsk(c), 或者输出 ⊥ \perp ⊥.需求 Pr [ D e c s k ( E n c p k ( m ) ) m ] ≥ 1 − n e g l ( n ) \Pr[\mathsf{Dec}_{sk}(\mathsf{Enc}_{pk}(m)) m] \ge 1 - \mathsf{negl}(n) Pr[Decsk(Encpk(m))m]≥1−negl(n). 注公钥加密方案通常以数学难题为基础存在解密不成功的可能。 对窃听者的安全 CPA 由于公钥是公开的敌手不仅能窃听而且能够加密任意明文。在敌手和挑战者间窃听不可区分实验 P u b K A , Π e a v ( n ) \mathsf{PubK}^{\mathsf{eav}}_{\mathcal{A},\Pi}(n) PubKA,Πeav(n): 挑战者生成密钥 ( p k , s k ) ← G e n ( 1 n ) (pk,sk) \gets \mathsf{Gen}(1^n) (pk,sk)←Gen(1n)。敌手 A \mathcal{A} A 被给予 p k \mathbf{pk} pk 以及 E n c p k ( ⋅ ) \mathbf{\mathsf{Enc}_{pk}(\cdot)} Encpk(⋅) 预言机的访问输出相同长度的 m 0 , m 1 m_0, m_1 m0,m1 。挑战者随机生成 b ← { 0 , 1 } b \gets \{0,1\} b←{0,1}。将挑战密文 c ← E n c p k ( m b ) c \gets \mathsf{Enc}_{pk}(m_b) c←Encpk(mb) 发送给敌手 A \mathcal{A} A。 A \mathcal{A} A 继续访问预言机 E n c p k ( ⋅ ) \mathbf{\mathsf{Enc}_{pk}(\cdot)} Encpk(⋅) 并且输出 b ′ b b′。如果 b ′ b b b b′b A \mathcal{A} A 成功 P u b K A , Π e a v 1 \mathsf{PubK}^{\mathsf{eav}}_{\mathcal{A},\Pi}1 PubKA,Πeav1否则 0。 定义 Π \Pi Π 是 CPA-secure 如果 ∀ \forall ∀ ppt A \mathcal{A} A, ∃ \exists ∃ n e g l \mathsf{negl} negl 使得 Pr [ P u b K A , Π c p a ( n ) 1 ] ≤ 1 2 n e g l ( n ) \Pr\left[\mathsf{PubK}^{\mathsf{cpa}}_{\mathcal{A},\Pi}(n)1\right] \le \frac{1}{2} \mathsf{negl}(n) Pr[PubKA,Πcpa(n)1]≤21negl(n)。 公钥加密的安全属性 对称加密可以加密32比特消息产生32比特密文例如使用一次一密。在公钥系统中能够做到同样的吗一个确定性的公钥加密方案在窃听者出现时是安全的如果 Π \Pi Π 在窃听者出现时是安全的那么 Π \Pi Π 也是CPA安全的? 是否是多重加密安全的完美保密的公钥加密是可能的吗注不可能 密钥长度比较 NIST美国国家标准技术研究所推荐可比较的密钥长度 (按比特) 。NIST 认为一个112比特的有效密钥长度直到2030年是可接受的但是推荐 128 比特或更长的密钥。 对称密钥AESRSA/DHECC5651211280102416011220482241283072256192768038425615360512 混合加密Hybrid Encryption构造 为了加速加密采用私钥加密方案 Π ′ \Pi Π′ (数据封装机制data-encapsulation mechanism, DEM) 与公钥加密方案 Π \Pi Π (密钥封装机制, key-encapsulation mechanism, KEM) 一起。 Π h y ( G e n h y , E n c h y , D e c h y ) \Pi^{\mathsf{hy}} (\mathsf{Gen}^{\mathsf{hy}}, \mathsf{Enc}^{\mathsf{hy}}, \mathsf{Dec}^{\mathsf{hy}}) Πhy(Genhy,Enchy,Dechy): G e n h y \mathsf{Gen}^{\mathsf{hy}} Genhy: ( p k , s k ) ← G e n ( 1 n ) (pk,sk) \gets \mathsf{Gen}(1^n) (pk,sk)←Gen(1n). 注只需提前生成公钥加密方案所需密钥 E n c h y \mathsf{Enc}^{\mathsf{hy}} Enchy: p k pk pk and m m m. k ← { 0 , 1 } n k \gets \{0,1\}^n k←{0,1}n. 注生成私钥加密密钥 c 1 ← E n c p k ( k ) c_1 \gets \mathsf{Enc}_{pk}(k) c1←Encpk(k), c 2 ← E n c k ′ ( m ) c_2 \gets \mathsf{Enc}_{k}(m) c2←Enck′(m). 注用公钥加密的公钥加密私钥加密密钥用私钥加密密钥加密消息。 D e c h y \mathsf{Dec}^{\mathsf{hy}} Dechy: s k sk sk and ⟨ c 1 , c 2 ⟩ \langle c_1,c_2\rangle ⟨c1,c2⟩. k : D e c s k ( c 1 ) k : \mathsf{Dec}_{sk}(c_1) k:Decsk(c1). 注用公钥加密中私钥解密获得私钥加密密钥 m : D e c k ′ ( c 2 ) m : \mathsf{Dec}_k(c_2) m:Deck′(c2). 注用私钥加密密钥获得明文 问题混合加密方案是公钥加密还是私钥加密 混合加密安全 定理如果 Π \Pi Π 是一个CPA安全的公钥加密方案并且 Π ′ \Pi Π′ 是窃听者不可区分的私钥加密方案那么 Π h y \Pi^{\mathsf{hy}} Πhy 是CPA安全的公钥加密方案。这里对于私钥加密方案的安全性要求只是窃听者不可区分的不要求是CPA安全的因为私钥加密密钥是每次加密时随机产生的新密钥私钥加密的加密预言机提供的结果无法被利用。整个方案安全证明的思路是利用各方案之间不可区分性以及不可区分性所具有的传递性transitiviy。目标是证明 1 ⟨ p k , E n c p k ( k ) , E n c k ′ ( m 0 ) ⟩ \langle pk,\mathsf{Enc}_{pk}(k),\mathsf{Enc}_{k}(m_0)\rangle ⟨pk,Encpk(k),Enck′(m0)⟩ 与2 ⟨ p k , E n c p k ( k ) , E n c k ′ ( m 1 ) ⟩ \langle pk,\mathsf{Enc}_{pk}(k),\mathsf{Enc}_{k}(m_1)\rangle ⟨pk,Encpk(k),Enck′(m1)⟩ 之间对于不同明文的不可区分性。为此先观察1 ⟨ p k , E n c p k ( k ) , E n c k ′ ( m 0 ) ⟩ \langle pk,\mathsf{Enc}_{pk}(k),\mathsf{Enc}_{k}(m_0)\rangle ⟨pk,Encpk(k),Enck′(m0)⟩ 与3 ⟨ p k , E n c p k ( 0 n ) , E n c k ′ ( m 0 ) ⟩ \langle pk,\mathsf{Enc}_{pk}(0^n),\mathsf{Enc}_{k}(m_0)\rangle ⟨pk,Encpk(0n),Enck′(m0)⟩ 之间对于不同公钥加密明文私钥加密密钥之间由于公钥加密方案不可区分性也是不可区分的同理2 ⟨ p k , E n c p k ( k ) , E n c k ′ ( m 1 ) ⟩ \langle pk,\mathsf{Enc}_{pk}(k),\mathsf{Enc}_{k}(m_1)\rangle ⟨pk,Encpk(k),Enck′(m1)⟩ 与4 ⟨ p k , E n c p k ( 0 n ) , E n c k ′ ( m 1 ) ⟩ \langle pk,\mathsf{Enc}_{pk}(0^n),\mathsf{Enc}_{k}(m_1)\rangle ⟨pk,Encpk(0n),Enck′(m1)⟩ 之间也是不可区分的。3 ⟨ p k , E n c p k ( 0 n ) , E n c k ′ ( m 0 ) ⟩ \langle pk,\mathsf{Enc}_{pk}(0^n),\mathsf{Enc}_{k}(m_0)\rangle ⟨pk,Encpk(0n),Enck′(m0)⟩ 与4 ⟨ p k , E n c p k ( 0 n ) , E n c k ′ ( m 1 ) ⟩ \langle pk,\mathsf{Enc}_{pk}(0^n),\mathsf{Enc}_{k}(m_1)\rangle ⟨pk,Encpk(0n),Enck′(m1)⟩ 之间由于私钥加密方案不可区分性也是不可区分的。最后根据不可区分性所具有的传递性证明混合加密方案的不可区分性。 混合加密范式应用 共享文件访问Alice用自己的对称密钥加密文件Bob的公钥加密对称密钥密钥托管Alice用托管服务器的公钥加密对称密钥领导从托管服务器获得私钥来解锁 陷门函数Trapdoor Function 陷门函数Trapdoor function: 易于计算在缺乏特定信息陷门时难以求逆即带有陷门的单向函数。1982年姚期智在论文《Theory and Applications of Trapdoor Functions》中提出从任意陷门函数中可构造一个公钥加密方案。 函数族Families of Functions Π ( G e n , S a m p , f ) \Pi (\mathsf{Gen}, \mathsf{Samp}, f) Π(Gen,Samp,f) 是一个函数组如果 参数生成Parameter-generation算法: I ← G e n ( 1 n ) I \gets \mathsf{Gen}(1^n) I←Gen(1n)。参数 I I I定义了定义域domain D I \mathcal{D}_I DI和值域range D R \mathcal{D}_R DR。注这里产生了一个具体的函数参数。采样sampling算法: x ← S a m p ( I ) x \gets \mathsf{Samp}(I) x←Samp(I)均匀随机地产生一个 x x x。确定性赋值evaluation算法: y : f I ( x ) y : f_I(x) y:fI(x)。 这里强调采样算法是因为后面要学习的数论难题的输入是要满足某些条件的。 陷门排列族 一组多项式时间算法 Π ( G e n , S a m p , f , I n v ) \Pi (\mathsf{Gen}, \mathsf{Samp}, f, \mathsf{Inv}) Π(Gen,Samp,f,Inv) 是一个陷门排列族family of trapdoor permutationsTDP如果 参数生成parameter generation算法 G e n \mathsf{Gen} Gen, 输入 1 n 1^n 1n输出 ( I , t d ) (I,\mathsf{td}) (I,td) 有 ∣ I ∣ ≥ n |I| \ge n ∣I∣≥n。其中 ( I , t d ) (I, \mathsf{td}) (I,td) 定义了集合 D I D t d \mathcal{D}_I \mathcal{D}_{\mathsf{td}} DIDtd。注陷门排列族是一个函数集合参数生成算法产生一个具体陷门排列所需的参数。 G e n I \mathsf{Gen}_I GenI 只输出 I I I。 ( G e n I , S a m p , f ) (\mathsf{Gen}_I, \mathsf{Samp}, f) (GenI,Samp,f) 是 OWP。其中的 S a m p \mathsf{Samp} Samp是采样函数用于获得函数的输入 x ← D I x \gets \mathcal{D}_I x←DI。一个确定性求逆算法 I n v \mathsf{Inv} Inv对于 ∀ ( I , t d ) \forall (I,\mathsf{td}) ∀(I,td) 并且 ∀ x ∈ D I \forall x \in \mathcal{D}_{I} ∀x∈DI $ \mathsf{Inv}_{\mathsf{td}}(f_I(x))x$。注可求逆 核心断言确定性多项式时间算法 h c \mathsf{hc} hc 是 Π \Pi Π 的一个核心断言hard-core predicate如果 ∀ \forall ∀ ppt A \mathcal{A} A ∃ \exists ∃ n e g l \mathsf{negl} negl 使得 $ \Pr[\mathcal{A}(I,f_I(x)) \mathsf{hc}_I(x)] \le \frac{1}{2} \mathsf{negl}(n)$。定理给定一个陷门排列族 Π ( G e n , S a m p , f , I n v ) \Pi (\mathsf{Gen}, \mathsf{Samp}, f, \mathsf{Inv}) Π(Gen,Samp,f,Inv)则存在一个带有核心断言的陷门排列族 Π ^ ( G e n ^ , S a m p , f , I n v ) \widehat{\Pi} (\widehat{\mathsf{Gen}}, \mathsf{Samp}, f, \mathsf{Inv}) Π (Gen ,Samp,f,Inv)。注证明与单向函数部分关于核心断言的定理类似。 TDP例题 如果答案是肯定的则需要反证法证明 f ′ f f′若不是TDP那么 f f f也不是如果答案是否定的则需要给出一个有效的求逆方法。 从TDP到公钥加密方案 从一个带有核心断言 h c \mathsf{hc} hc的陷门排列族 Π ^ ( G e n ^ , S a m p , f , I n v ) \widehat{\Pi} (\widehat{\mathsf{Gen}}, \mathsf{Samp}, f, \mathsf{Inv}) Π (Gen ,Samp,f,Inv)来构造一个公钥加密方案 G e n \mathsf{Gen} Gen: ( I , t d ) ← G e n ^ (I, \mathsf{td}) \gets \widehat{Gen} (I,td)←Gen 输出公钥 I I I 和私钥 t d \mathsf{td} td。 E n c \mathsf{Enc} Enc: 输入 I I I 和 m ∈ { 0 , 1 } m \in \{0,1\} m∈{0,1}选择一个 x ← D I x\gets \mathcal{D}_I x←DI 并且输出 ⟨ f I ( x ) , h c I ( x ) ⊕ m ⟩ \langle f_I(x), \mathsf{hc}_I(x)\oplus m \rangle ⟨fI(x),hcI(x)⊕m⟩。 D e c \mathsf{Dec} Dec: 输入 t d \mathsf{td} td 和 ⟨ y , m ′ ⟩ \langle y, m\rangle ⟨y,m′⟩计算 x : f I − 1 ( y ) x: f^{-1}_I(y) x:fI−1(y) 并且输出 h c I ( x ) ⊕ m ′ \mathsf{hc}_I(x)\oplus m hcI(x)⊕m′。 定理如果 Π ^ ( G e n ^ , f ) \widehat{\Pi}(\widehat{Gen},f) Π (Gen ,f) 是 TDP并且 h c \mathsf{hc} hc 是 Π ^ \widehat{\Pi} Π 的 HCP 那么构造 Π \Pi Π 是 CPA安全的。问题这个方案是安全的吗 E n c I ( m ) f I ( m ) \mathsf{Enc}_{I}(m) f_I(m) EncI(m)fI(m) D e c t d ( c ) f I − 1 ( c ) \mathsf{Dec}_{\mathsf{td}}(c) f^{-1}_I(c) Dectd(c)fI−1(c)。 证明 h c I ( x ) \mathsf{hc}_I(x) hcI(x) 是伪随机的。将 A h c \mathcal{A}_{\mathsf{hc}} Ahc for h c \mathsf{hc} hc 规约到 A \mathcal{A} A for Π \Pi Π。 Pr [ A h c ( I , f I ( x ) ) h c I ( x ) ] \Pr[\mathcal{A}_{\mathsf{hc}}(I,f_I(x))\mathsf{hc}_I(x)] Pr[Ahc(I,fI(x))hcI(x)] 1 2 ⋅ ( Pr [ b ′ b ∣ z h c I ( x ) ] Pr [ b ′ ≠ b ∣ z ≠ h c I ( x ) ] ) . \frac{1}{2}\cdot (\Pr[bb|z\mathsf{hc}_I(x)]\Pr[b\neq b|z\neq \mathsf{hc}_I(x)]). 21⋅(Pr[b′b∣zhcI(x)]Pr[b′b∣zhcI(x)]).上面的公式的含义是 A h c \mathcal{A}_{\mathsf{hc}} Ahc成功得到核心断言包含两种情况 当 z z z是核心断言则 A \mathcal{A} A面对的是方案 Π \Pi Π A \mathcal{A} A成功 b ′ b bb b′b输出的 z z z就是核心断言当 z z z不是核心断言则 A \mathcal{A} A面对的挑战密文与 Π \Pi Π中是相反的 A \mathcal{A} A失败 b ′ ≠ b b\neq b b′b输出的 z ‾ \overline{z} z就是核心断言 证明续 Pr [ b ′ b ∣ z h c I ( x ) ] Pr [ P u b K A , Π e a v ( n ) 1 ] ε ( n ) \Pr[bb|z\mathsf{hc}_I(x)] \Pr[\mathsf{PubK}^{\mathsf{eav}}_{\mathcal{A},\Pi}(n)1]\varepsilon(n) Pr[b′b∣zhcI(x)]Pr[PubKA,Πeav(n)1]ε(n)。 注 A \mathcal{A} A实验成功。如果 z ≠ h c I ( x ) z \neq \mathsf{hc}_I(x) zhcI(x), m ′ m b ⊕ h c ‾ I ( x ) m b ‾ ⊕ h c I ( x ) m m_b\oplus \overline{\mathsf{hc}}_I(x) m_{\overline{b}}\oplus \mathsf{hc}_I(x) m′mb⊕hcI(x)mb⊕hcI(x)这意味着 m b ‾ m_{\overline{b}} mb 被加密了。 Pr [ b ′ b ∣ z ≠ h c I ( x ) ] Pr [ P u b K A , Π e a v ( n ) 0 ] 1 − ε ( n ) \Pr[bb|z\neq \mathsf{hc}_I(x)] \Pr[\mathsf{PubK}^{\mathsf{eav}}_{\mathcal{A},\Pi}(n)0]1-\varepsilon(n) Pr[b′b∣zhcI(x)]Pr[PubKA,Πeav(n)0]1−ε(n)。 注 A \mathcal{A} A实验失败了。 Pr [ b ′ ≠ b ∣ z ≠ h c I ( x ) ] ε ( n ) \Pr[b\neq b|z\neq \mathsf{hc}_I(x)] \varepsilon(n) Pr[b′b∣zhcI(x)]ε(n)。 Pr [ A h c ( I , f I ( x ) ) h c I ( x ) ] 1 2 ⋅ ( ε ( n ) ε ( n ) ) ε ( n ) \Pr[\mathcal{A}_{\mathsf{hc}}(I,f_I(x))\mathsf{hc}_I(x)] \frac{1}{2}\cdot (\varepsilon(n)\varepsilon(n)) \varepsilon(n) Pr[Ahc(I,fI(x))hcI(x)]21⋅(ε(n)ε(n))ε(n)。 注根据上一页的公式。至此我们学习了基于陷门排列的公钥加密方案但只能加密一个比特如何加密一个更长的明文后面学习随机预言机模型设定下的公钥加密方案。 在公钥设定中CCA情景 CCA 敌手 A \mathcal{A} A 观察由 S \mathcal{S} S 发送给 R \mathcal{R} R 的密文 c c c 。 A \mathcal{A} A 以 S \mathcal{S} S 或自己的名义发送 c ′ c c′ 给 R \mathcal{R} R 。 A \mathcal{A} A 根据从 c ′ c c′ 中解密出的 m ′ m m′ 来推断 m m m。 情景 用口令来登陆在线银行试错从银行反馈中获得信息。邮件回复中包含解密出的文本的引用。密文的可锻造性例如在拍卖中将其他人的出价翻倍。 对CCA/CCA2的安全定义 CCA/CCA2 不可区分实验 P u b K A , Π c c a ( n ) \mathsf{PubK}^{\mathsf{cca}}_{\mathcal{A},\Pi}(n) PubKA,Πcca(n) ( p k , s k ) ← G e n ( 1 n ) (pk,sk) \gets \mathsf{Gen}(1^n) (pk,sk)←Gen(1n). A \mathcal{A} A 给定输入 p k pk pk 和预言机访问 D e c s k ( ⋅ ) \mathsf{Dec}_{sk}(\cdot) Decsk(⋅)输出相同长度的 m 0 , m 1 m_0, m_1 m0,m1 。 b ← { 0 , 1 } b \gets \{0,1\} b←{0,1}。挑战密文 c ← E n c p k ( m b ) c \gets \mathsf{Enc}_{pk}(m_b) c←Encpk(mb) 给 A \mathcal{A} A。在CCA2中 A \mathcal{A} A 除了 c c c 之外还可以访问 D e c s k ( ⋅ ) \mathsf{Dec}_{sk}(\cdot) Decsk(⋅)并输出 b ′ b b′ 。注CCA 也被称作午餐攻击。CCA2 也被称为适应性的 CCA。如果 b ′ b b b b′b那么 A \mathcal{A} A 成功 P r i v K A , Π c c a 1 \mathsf{PrivK}^{\mathsf{cca}}_{\mathcal{A},\Pi}1 PrivKA,Πcca1否则 0。 Π \Pi Π 是 CCA/CCA2安全的如果 ∀ \forall ∀ ppt A \mathcal{A} A, ∃ \exists ∃ n e g l \mathsf{negl} negl 使得 Pr [ P u b K A , Π c c a ( n ) 1 ] ≤ 1 2 n e g l ( n ) \Pr\left[\mathsf{PubK}^{\mathsf{cca}}_{\mathcal{A},\Pi}(n)1\right] \le \frac{1}{2} \mathsf{negl}(n) Pr[PubKA,Πcca(n)1]≤21negl(n). 例题 略 CCA2安全加密技术进展 零知识证明Zero-Knowledge Proof复杂并不可实践。(例如Dolev-Dwork-Naor)随机预言机模型Random Oracle model有效但并不踏实 (将 CRHF 当作 RO)。 (例如RSA-OAEP 和 Fujisaki-Okamoto)DDH决策性Diffie-Hellman假设和UOWHF全域单向哈希函数大小扩展2倍但可以在没有RO和ZKP场景下证明安全 (例如Cramer-Shoup system)。CCA2安全意味着明文感知Plaintext-aware敌手在不知道明文的情况下不能产生有效的密文。开放问题如何构造一个与“书本上RSA”一样有效的基于RSA问题的CCA2安全的方案。
随机预言机模型Random Oracle ModelROM 随机预言机模型Random Oracle ModelROM 为了在实践中实现CPA安全和CCA安全的公钥加密方案引入了一个更强大的随机对象称为随机预言机Random Oracle Model。随机预言机RO一个真随机函数 H H H对每个可能的查询回答一个随机应答。 一致性如果 H H H曾经在运行中为一个输入 x x x 输出 y y y那么它一直对相同的输入输出相同的答案。无人“知道”整个函数 H H H。 随机预言机模型ROM存在一个公开的RO。与此相对的不存在RO的情况称作标准模型。方法论在ROM中构造可证明的安全。 在ROM中一个方案被设计并被证明是安全的。将 H H H 用一个哈希函数 H ^ \hat{H} H^例如 SHA256。 无人严格地声明随机预言机存在。存在某些方案在ROM中被证明是安全的但无论如何将随机预言机实例化都不是安全的。使用ROM很容易实现可证明安全同时通过正确的实例化来保持高效。 ROM的简单例子 由于RO “强大的随机性”其可以充当或构造之前学习过得密码学原语包括为单向函数、抗碰撞哈希函数、伪随机函数等。 一个 RO 将 n 1 n_1 n1 比特输入映射为 n 2 n_2 n2 比特输出。 RO 作为 OWF进行如下实验 选择一个RO H H H 选择一个随机的 x ∈ { 0 , 1 } n 1 x \in \{0,1\}^{n_1} x∈{0,1}n1 并且赋值 y : H ( x ) y : H(x) y:H(x) 敌手 A \mathcal{A} A 被给予 y y y如果输出 x ′ x x′: H ( x ′ ) y H(x)y H(x′)y则成功 解释如果敌手成功求逆则意味着敌手“事先”询问过RO RO 作为 CRHF进行如下实验 选择一个RO H H H 敌手 A \mathcal{A} A 成功如果其输出 x , x ′ x, x x,x′ 满足 H ( x ) H ( x ′ ) H(x)H(x) H(x)H(x′) 但是 x ≠ x ′ x\neq x xx′ 解释如果敌手找到碰撞则意味着 H H H不是随机的因为两个随机输出不可能相同。 从一个RO构造PRF n 1 2 n n_12n n12n, n 2 n n_2n n2n. F k ( x ) def H ( k ∥ x ) , F_k(x) \overset{\text{def}}{} H(k\| x), Fk(x)defH(k∥x), ∣ k ∣ ∣ x ∣ n . |k||x|n. ∣k∣∣x∣n. 解释如果 F F F不是伪随机的则 H H H也可以与真随机相区分。 CPA安全 思路PubK CPA PrivK (Secret Key TDP RO)实现CPA安全的公钥加密方案可以基于一个安全的私钥加密方案其中私钥加密的密钥由RO得到通过TDP传递生成密钥所用的随机量构造 G e n \mathsf{Gen} Gen: p k I pk I pkI, s k t d sk \mathsf{td} sktd. E n c \mathsf{Enc} Enc: r ← { 0 , 1 } ∗ r \gets \{0,1\}^* r←{0,1}∗, 输出 ⟨ c 1 f I ( r ) , c 2 H ( r ) ⊕ m ⟩ \langle c_1 f_I(r), c_2 \mathsf{H}(r)\oplus m\rangle ⟨c1fI(r),c2H(r)⊕m⟩. D e c \mathsf{Dec} Dec: r : f t d − 1 ( c 1 ) r : f^{-1}_{\mathsf{td}}(c_1) r:ftd−1(c1), 输出 H ( r ) ⊕ c 2 \mathsf{H}(r)\oplus c_2 H(r)⊕c2. 定理如果 f f f 是 TDP 并且 H H H 是 RO则构造是 CPA 安全的。解释私钥加密方案只需要是窃听下安全因为每次加密都是概率性的每次私钥加密密钥都是重新生成的。该方案不是CCA安全的因为篡改密文可以直接影响明文。用RO的必要性由于 r r r的部分信息可能通过TPD泄漏如果以一个PRG来替换掉RO则由于种子的部分信息已知PRG的输出也不在是伪随机的加密方案也不再安全。 基于私钥加密的CCA安全 思路PubK CCA PrivK CCA (Secret Key TPD RO)实现CCA安全的公钥加密方案可以基于一个CCA安全的私钥加密方案其中私钥加密密钥由RO得到通过TDP传递生成密钥所用的随机量构造 Π ′ \Pi Π′ 是一个安全私钥加密方案。 G e n \mathsf{Gen} Gen: p k I pk I pkI, s k t d sk \mathsf{td} sktd. E n c \mathsf{Enc} Enc: k : H ( r ) , r ← D I k : H(r), r \gets D_I k:H(r),r←DI, 输出 ⟨ c 1 f I ( r ) , c 2 E n c k ′ ( m ) ⟩ \langle c_1 f_I(r), c_2 \mathsf{Enc}_k(m)\rangle ⟨c1fI(r),c2Enck′(m)⟩. D e c \mathsf{Dec} Dec: r : f t d − 1 ( c 1 ) r : f^{-1}_{\mathsf{td}}(c_1) r:ftd−1(c1), k : H ( r ) k:H(r) k:H(r), 输出 D e c k ′ ( c 2 ) \mathsf{Dec}_k(c_2) Deck′(c2). 定理如果 f f f 是 TDP Π ′ \Pi Π′ 是 CCA 安全的并且 H H H 是 RO那么构造是 CCA 安全的。解释公钥加密方案的CCA安全性来自私钥加密方案的CCA安全性。 在ROM中基于TPD的CCA安全 思路PubK CCA TDP 2 RO (一个用于加密一个用于MAC)实现CCA安全的公钥加密方案可以通过RO来构造一个CPA安全的公钥加密方案以明文和密文一起作为输入来生成MAC标签。构造 G e n \mathsf{Gen} Gen: p k I pk I pkI, s k t d sk \mathsf{td} sktd E n c \mathsf{Enc} Enc: r ← D I r \gets D_I r←DI输出 ⟨ c 1 f I ( r ) , c 2 H ( r ) ⊕ m , c 3 G ( c 2 ∥ m ) ⟩ \langle c_1f_I(r), c_2 H(r)\oplus m, c_3G(c_2\|m)\rangle ⟨c1fI(r),c2H(r)⊕m,c3G(c2∥m)⟩ D e c \mathsf{Dec} Dec: r : f t d − 1 ( c 1 ) r : f^{-1}_{\mathsf{td}}(c_1) r:ftd−1(c1), m : H ( r ) ⊕ c 2 m : H(r)\oplus c_2 m:H(r)⊕c2。如果 G ( c 2 ∥ m ) c 3 G(c_2\|m) c_3 G(c2∥m)c3 输出 m m m否则 ⊥ \perp ⊥。 定理如果 f f f 是 TDP G , H G,H G,H 是 RO那么构造是 CCA 安全的。解释其CCA安全性在于对密文的任何篡改都无法通过MAC验证。 私钥加密 vs. 公钥加密 私钥加密公钥加密密钥双方接收者最弱攻击窃听者CPA概率性CPA/CCA一直对CPA的假设OWFTDP对CCA的假设OWFTDPRO效率快慢
