0


【密码学】高级密码学-1

文章目录

0 一些前置内容

0.1 对称加密

  通信双方使用同一个密钥,通过使用加密算法配合上密钥来加密,解密过程采用加密过程的逆过程配合密钥即可。
  常见的对称加密算法有DES、AES等。
  对称加密的缺点:不能在不安全的网络上传输密钥,一旦密钥泄露则加密通信失败。

0.2 非对称加密(公钥加密)

  非对称加密使用了一对密钥——公钥(public key)和私钥(private key)。私钥只能由一方安全保管,不能外泄,而公钥可以发送给任何请求它的人。非对称加密使用公钥对数据进行加密得到密文,使用私钥对数据进行解密得到原数据。
  比如,你向银行请求发送数据,银行将一个公钥发给你,自己保留与之对应的公钥。你使用公钥对数据进行加密后发给银行,那么只有私钥的持有者——银行才能对你的消息解密。
  与对称加密不同的是,银行不需要将私钥通过网络发送过去,因此安全性大大提高。
  常见的非对称加密算法有RSA、ECC。

0.3 RSA

密钥准备
  假设Alice和Bob要在网上进行加密通信,则他们使用RSA来加密解密信息的过程如下:

  1. 随机选择两个不相同的素数 p , q p,q p,q。
  2. 将 p , q p,q p,q相乘,记 n = p × q n=p×q n=p×q。
  3. 计算 n n n的欧拉函数 φ ( n ) \varphi(n) φ(n),欧拉函数证明,当 p , q p,q p,q为不相同的素数时, φ ( n ) = ( p − 1 ) ( q − 1 ) \varphi(n)=(p-1)(q-1) φ(n)=(p−1)(q−1)。
  4. 随机选择一个整数 e e e,满足两个条件: φ ( n ) \varphi(n) φ(n)与 e e e互质,且 1 < e < φ ( n ) 1<e<\varphi(n) 1<e<φ(n)。
  5. 计算 e e e对于 φ ( n ) \varphi(n) φ(n)的模逆元素 d d d,即找到一个元素 d d d满足 e d = 1 m o d    φ ( n ) ed=1\mod\varphi(n) ed=1modφ(n)。
  6. 最终把 ( e , n ) (e,n) (e,n)封装成公钥, ( d , n ) (d,n) (d,n)封装成私钥。

加密
  利用公钥

     ( 
    
   
     e 
    
   
     , 
    
   
     n 
    
   
     ) 
    
   
  
    (e,n) 
   
  
(e,n)计算 
 
  
   
   
     C 
    
   
     = 
    
    
    
      M 
     
    
      e 
     
    
    
    
    
    
      m 
     
    
      o 
     
    
      d 
     
      
   
     n 
    
   
  
    C=M^e\mod n 
   
  
C=Memodn。其中, 
 
  
   
   
     C 
    
   
  
    C 
   
  
C为密文, 
 
  
   
   
     M 
    
   
  
    M 
   
  
M为明文。

解密
  RSA证明,

      C 
     
    
      d 
     
    
   
     = 
    
    
    
      M 
     
    
      e 
     
    
    
    
    
    
      m 
     
    
      o 
     
    
      d 
     
      
   
     n 
    
   
  
    C^d=M^e\mod n 
   
  
Cd=Memodn,所以 
 
  
   
   
     M 
    
   
     = 
    
    
    
      C 
     
    
      d 
     
    
    
    
    
    
      m 
     
    
      o 
     
    
      d 
     
      
   
     n 
    
   
  
    M=C^d \mod n 
   
  
M=Cdmodn,利用私钥 
 
  
   
   
     ( 
    
   
     d 
    
   
     , 
    
   
     n 
    
   
     ) 
    
   
  
    (d,n) 
   
  
(d,n)即可解密。

0.4 数字签名

  数字签名是只有发送者才能产生的别人无法伪造的一段数字串,这段数字串同时也是对信息发送者发送信息真实性的一个有效证明。它类似于写在纸上的普通的物理签名,只不过使用了公钥加密技术来实现。

签名过程
  发送报文时,发送方用一个哈希函数从报文文本中生成报文摘要,然后用发送方的私钥对这个摘要进行加密,这个加密后的摘要作为数字签名和报文一起发送给接收方。接收方首先用与发送方一样的哈希函数从接收到的原始报文中计算出报文摘要,接着再用公钥来对报文附加的数字签名进行解密,如果这两个摘要相同,那么接收方就能确认该报文是发送方的。
签名

0.5 数字证书

背景
  Alice对Bob使用数字签名技术发送信息,看似天衣无缝,但是仍忽略了一个问题,在验证身份时,Bob需要用到Alice的公钥,公钥在发布的时候是公开的,攻击者如果在Alice发布公钥时,拦截下来,将自己的公钥发布出去,Bob拿到了攻击者的公钥,反而会将攻击者发来的信息当场Alice的信息,而把Alice发来的信息当成攻击者的信息。
  数字证书的作用就是防止Alice的公钥被伪造。

数字证书
  Alice需要找到一个CA机构(负责签发证书、认证证书、管理已颁发证书的机关),CA将证书的颁布机构、有效期、Alice的公钥、持有者等信息用CA的私钥进行签名,将签名值和这些信息打包起来(即数字证书)颁发给Alice。如果需要通信,Alice将自己的证书交给Bob,Bob拿出数字证书中的签名值,用CA中心的公钥进行解签(CA中心的公钥是无法篡改的)得到摘要A ,再对证书中的信息作摘要,得到摘要B。如果二者相等,说明证书未被篡改过,因此就可以确认公钥确实是Alice的。
数字签名

1 可证明安全性

1.1 语义安全性

什么是安全
  安全是基于信任构建的标准“可满足性”;简单来说,你相信“它”是安全的,“它就是安全的”。
  安全基于信任而不是基于试验的原因是试验往往需要很高的代价。

信任源
  信任源具有动态性,受外部因素的影响,信任可能成立也可能不成立。一旦不成立,基于该信任构建的安全也就不成立。
  信任源具有稳健性。其稳健性越高,代价越高。
  现代密码学的信任基础是对数学难题的信任。若某个数学难题是难解的,那么基于该难题构建的密码算法是可证明安全的。

可证明安全性起源
  1982年Goldwasser和Micali等学者提出了语义安全性定义,将可证明安全的思想首次带入安全协议的形式化分析中,他们也因此获得2012年图灵奖。

何为语义安全
  语义安全是密码学中的术语。如果已知某段未知文段的密文不会泄露任何该文段的其余信息,则称该密文是语义安全的。
  该概念相似于香农的完善保密性定义。完善保密性意味密文不会泄露任何明文的信息,而语义安全侧重表示被揭露的信息不会被实际窃取。

语义安全的主要成分

  • 攻击者 - 计算能力:通常为多项式级,即计算能力可以用一个多项式表达- 先验知识:攻击者已知的信息,及由这些信息推导出的知识,如公钥、密文、算法等
  • 攻击目标 - 直观目标:破解密钥、明文- 实际目标:破解明文语义

  在语义安全中,假设攻击者能够获得最强的信息获取能力,获得所有的公开信息(例如算法的公开参数和算法等),计算能力的最大上限(一般考虑能够具有解决多项式的问题和能力)。攻击目标限定于只需能够获得1比特的信息。

以上述两者为基础,如何定义安全?
  攻击者破解密文并获得其明文任意1比特语义的“优势”可忽略,这里的“优势”是攻击者成功概率减去1/2的部分,则该公钥加密的算法是语义安全的(具体地说是选择明文攻击下语义安全的)。

语义安全性最大的精髓
  将攻击者的攻击能力最大化,攻击目标最小化,不限制攻击者的具体攻击方式。这样的好处是既不会陷于某种攻击方式而丧失普遍性,又构造了最有利于攻击者的情况,若仍能够说明密码算法的安全,则密码算法是真的安全。

1.2 攻击者/挑战者模型

攻击者/挑战者模型
过程:

  1. 攻击者自己任意选择两个消息 M 0 M_0 M0​和 M 1 M_1 M1​。(注意,这两个是攻击者自己选的)
  2. 攻击者把这两个消息发送给挑战者。
  3. 挑战者运行加密算法,加密 M b M_b Mb​(b=0或1),把加密结果发送给攻击者。
  4. 攻击者看到加密结果后,猜测这个加密结果是由 M 0 M_0 M0​加密来的,还是由 M 1 M_1 M1​加密来的。

1.3 攻击者/挑战者模型的应用:ElGamal与数学难题

ElGamal加密算法思想

  •                                     S                            e                            t                            u                            p                            (                            k                            )                                  Setup(k)                     Setup(k):输入安全参数                                        k                                  k                     k,选择阶为大素数                                        q                                  q                     q的乘法群                                        G                                  \mathbb{G}                     G,选择群                                        G                                  \mathbb{G}                     G的一个生成元                                        g                                  g                     g,选择一个随机数                                        s                            ∈                                       Z                               q                               ∗                                            s\in Z_q^*                     s∈Zq∗​,计算                                        P                            =                                       g                               s                                            P=g^s                     P=gs,输出公钥                                        P                            K                            =                            (                            q                            ,                            G                            ,                            g                            ,                            p                            )                                  PK=(q,\mathbb{G},g,p)                     PK=(q,G,g,p),私钥                                        S                            K                            =                            s                                  SK=s                     SK=s。
    
  •                                     E                            n                            c                            (                            P                            K                            ,                            M                            )                                  Enc(PK,M)                     Enc(PK,M):输入公钥                                        P                            K                                  PK                     PK和明文                                        M                                  M                     M,选择随机数                                        r                            ∈                                       Z                               q                               ∗                                            r\in Z^*_q                     r∈Zq∗​,计算并输出密文                                        C                            =                            (                                       g                               r                                      ,                                       P                               r                                      ⋅                            M                            )                                  C=(g^r,P^r·M)                     C=(gr,Pr⋅M)。
    
  •                                     D                            e                            c                            (                            S                            K                            ,                            C                            )                                  Dec(SK,C)                     Dec(SK,C):输入私钥                                        S                            K                                  SK                     SK和密文                                        C                                  C                     C,分解                                        C                            =                            (                                       C                               1                                      ,                                       C                               2                                      )                                  C=(C_1,C_2)                     C=(C1​,C2​),计算并输出                                                   M                               ′                                      =                                       C                               2                                      /                                       C                               1                                           S                                  K                                                       M'=C_2/C_1^{SK}                     M′=C2​/C1SK​。
    

依赖的数学难题——Decisional Diffie-Hellman(DDH)
  给定两个元组

     ( 
    
    
    
      g 
     
    
      a 
     
    
   
     , 
    
    
    
      g 
     
    
      b 
     
    
   
     , 
    
    
    
      g 
     
     
     
       a 
      
     
       b 
      
     
    
   
     ) 
    
   
  
    (g^a,g^b,g^{ab}) 
   
  
(ga,gb,gab)和 
 
  
   
   
     ( 
    
    
    
      g 
     
    
      a 
     
    
   
     , 
    
    
    
      g 
     
    
      b 
     
    
   
     , 
    
   
     R 
    
   
     ) 
    
   
  
    (g^a,g^b,R) 
   
  
(ga,gb,R),其中 
 
  
   
   
     g 
    
   
  
    g 
   
  
g是阶为大素数 
 
  
   
   
     q 
    
   
  
    q 
   
  
q的乘法群 
 
  
   
   
     G 
    
   
  
    \mathbb{G} 
   
  
G的生成元, 
 
  
   
   
     a 
    
   
     , 
    
   
     b 
    
   
     ∈ 
    
    
    
      Z 
     
    
      q 
     
    
      ∗ 
     
    
   
  
    a,b\in Z_q^* 
   
  
a,b∈Zq∗​, 
 
  
   
   
     R 
    
   
     ∈ 
    
   
     G 
    
   
  
    R\in\mathbb{G} 
   
  
R∈G均为随机数,如何判断哪个元组是*Diffie-Hellman*元组。

Diffie-Hellman元组:形如

     ( 
    
    
    
      g 
     
    
      a 
     
    
   
     , 
    
    
    
      g 
     
    
      b 
     
    
   
     , 
    
    
    
      g 
     
     
     
       a 
      
     
       b 
      
     
    
   
     ) 
    
   
  
    (g^a,g^b,g^{ab}) 
   
  
(ga,gb,gab)的元组。

ElGamal加密算法的可证明安全性
  如果存在某个攻击者A能够以不可忽略的优势攻破ElGamal加密算法,则存在一个算法B能利用该攻击者来求解DDH问题,即将攻击者A的攻击能力归约到求解DDH问题上。但是求解DDH问题的算法并不存在,因此也就不存在这样的攻击者可以攻破ElGamal算法,因此ElGamal算法是安全的。

归约过程
ElGamal算法规约过程

  • 已知 ( g a , g b , Z ) (g^a,g^b,Z) (ga,gb,Z)为DDH元组的概率为 1 2 \frac{1}{2} 21​。
  • 若 Z = g a b Z=g^{ab} Z=gab,攻击者猜对的概率为 P r [ d = d ′ ∣ Z = g a b ] = ε Pr[d=d'|Z=g^{ab}]=\varepsilon Pr[d=d′∣Z=gab]=ε。
  • 若 Z = R Z=R Z=R,攻击者猜对的概率为 P r [ d = d ′ ∣ Z = R ] = 1 2 Pr[d=d'|Z=R]=\frac{1}{2} Pr[d=d′∣Z=R]=21​。
  • 假设攻击者能攻破ElGamal算法,则 ε > 1 2 \varepsilon>\frac{1}{2} ε>21​。利用该特性,算法B可以求解DDH问题。

1.4 其他问题

什么是安全参数
  因子分解问题的求解复杂度约为

     O 
    
   
     ( 
    
    
    
      2 
     
     
      
      
        ln 
       
      
        ⁡ 
       
      
        ( 
       
      
        n 
       
      
        ) 
       
      
        ln 
       
      
        ⁡ 
       
      
        ( 
       
      
        ln 
       
      
        ⁡ 
       
      
        ( 
       
      
        n 
       
      
        ) 
       
      
        ) 
       
      
     
    
   
     ) 
    
   
  
    O(2^{\sqrt{\ln(n)\ln(\ln(n))}}) 
   
  
O(2ln(n)ln(ln(n))​)。

  在RSA加密算法中,当密钥长度n为1024bits时,RSA算法的破解复杂度约为

      2 
     
    
      84 
     
    
   
  
    2^{84} 
   
  
284,当n为2048bits时,RSA算法的破解复杂度为 
 
  
   
    
    
      2 
     
    
      125 
     
    
   
  
    2^{125} 
   
  
2125。

  从之前的课程中我们了解到,

      2 
     
    
      80 
     
    
   
  
    2^{80} 
   
  
280破解复杂度是密码算法安全性的一个分水岭,超过这个复杂度的算法才具有实用的安全性。密钥长度直接能影响破解的复杂度,越长的加密密钥会有越高的破解复杂度,但同时也会带来更大的计算开销。

安全参数是量化安全性的重要依据。因为非对称密码加密需要一个统一的量化标准来衡量它的安全性,于是就引入了安全参数。所有可证明安全的密码算法都有量化安全性。安全参数与攻击者优势一般成倒数关系,安全参数越大,破解方案的复杂度会成指数级升高。

为什么随机数堆加密算法的安全性至关重要
  从信息论的角度来说,熵代表不确定性,对于任何一个函数,函数的输入熵一定大于等于输出熵,加密算法也不例外。确定性算法无法增加输出的熵,但密码算法要做到安全性,必须要使输出满足一定的随机性,即熵足够大。随机数则作为一个桥梁,引入随机数可以增加输入熵,理论上符合信息论的观点。

为什么完善保密性中没有引入随机数
  因为完善保密性要求明文尽可能满足均匀分布(输入满足高熵),要求密钥也是随机的(采用一次一密的方式)。从这两点我们也可以看出完善保密性在现实中并不具有实用性。

可证明安全
  可证明安全:基本思想基于数学中的反证法,通过“规约”的方式将密码算法安全性规约到某个公认的数学难题, 比如大数分解,素数域离散对数分解问题.。若存在攻破密码算法的攻击方式,,则可以利用该方式构造出攻破数学难题的方法。

2 基于身份加密(IBE)

Boneh D

Boneh D, Franklin M. Identity-based encryption from the Weil pairing[J]. SIAM journal on computing, 2003, 32(3): 586-615.

2.1 公钥基础设施(PKI)

PKI
传统公钥加密体制的局限性
  公钥加密体制虽然很好,但是也有很多潜在的问题。一个最大的问题就是,每个人的公钥都是无意义的一串类似随机数的东西,在加密的时候,加密者怎么知道一个公钥就是接受者的公钥呢?如果加密过程中公钥使用错误,密文就不能被正确的接收者所解密。同时,这很可能就将信息透露给了错误的用户,甚至透露给恶意用户。实际上,现实生活中确实存在这样的攻击方法:恶意用户欺骗加密者,将接收者的公钥替换为自己的公钥并告知加密者,同时加密者无法得知收到的公钥是否为接收者的。

PKI的核心功能
  在网络上因为彼此不能见面,因此伪造身份是十分容易的。基于这个原因,用户是不能直接把自己的公钥发到网上的,因为他不能证明这个公钥是他自己的,即使是加数字签名也没用,就像身份证不能自己来造一样,自己的数字签名没有可信度,也容易伪造。这时需要一个可信第三方来管理这些密钥。PKI提供了这个可信的第三方,即CA(证书中心)。
  简单来说,向发送方证明接收方的公钥是“哪一个”或者说将接收方与某个公钥绑定。当接收方公钥不再有效时,告知发送方,接收方的公钥已被撤销。

CA在PKI中的作用

  1. Alice想要和Bob进行通信,她会首先向CA询问Bob的公钥。
  2. CA用自己的私钥签发Bob的公钥,即生成证书发给Alice。
  3. Alice使用CA的公钥验证后即可使用Bob的公钥。

CA的其他功能
  CA也有撤销用户公钥的能力,即不再签发相应用户的公钥。

PKI存在的实际问题
  在实际应用中,发送方的数量是非常多的。每次发送方加密数据之前,都要询问CA接收方的公钥是什么(即获得接收方公钥的证书),或是询问CA接收方的公钥是否依然有效。于是CA成为了PKI的性能瓶颈。

PKI存在问题的本质原因
  公钥是随机生成的,与用户没有天然绑定关系。CA的存在就是通过一种外力人为地将公钥和用户身份进行绑定。

2.2 IBE简介

核心要求——让用户及其公钥有天然的绑定关系
  为了使这个公钥与用户形成天然的绑定,这个公钥直接或间接的是用户的某些自然属性,且因为公钥具有唯一性,所以自然属性需要有唯一性。

属性=身份=公钥
  有没有一种可能,可以让公钥就是用户的身份呢?所谓身份,就是指一串跟用户相关的有意义的数字,比如身份证号、姓名、邮箱等。加密者在加密过程中,不再需要使用一堆无意义的数字作为公钥了,而是直接使用接收者的身份进行加密。这样一来,加密者就不需要向可信第三方询问接收者的公钥了。

IBE的发展

  • 1984年,Shamir提出了基于身份体制的概念(IBC),但并没有找到实现方法。
  • 20世纪90年代,实现了基于身份签名方案(IBS)。
  • 2000年或2001年,实现了首个基于身份加密方案(IBE)。

IBE的定义

  •                                     S                            e                            t                            u                            p                                  Setup                     Setup算法   - 输入:安全参数- 输出:系统公开参数和系统秘密参数
    
  •                                     E                            x                            t                            r                            a                            c                            t                                  Extract                     Extract算法   - 输入:系统秘密参数,用户的身份信息(公钥)- 输出:用户私钥
    
  •                                     E                            n                            c                                  Enc                     Enc算法   - 输入:系统公开参数,接收方的身份信息(公钥),明文- 输出:密文
    
  •                                     D                            e                            c                                  Dec                     Dec算法   - 输入:接收方私钥,密文- 输出:明文
    

2.3 IBE的应用——基于BF-IBE的邮件系统

IBE邮件系统

  • 初始化阶段 - 密钥生成中心(KGC)运行 S e t u p Setup Setup算法(输入:安全参数),生成系统公开参数和系统秘密参数
  • 用户加入阶段 - 令新加入用户的邮箱地址为ID,KGC运行 E x t r a c t Extract Extract算法(输入:系统秘密参数,ID),生成并授予该用户私钥
  • 邮件安全传输阶段 - 令接收方的邮件地址为ID,发送方运行 E n c Enc Enc算法加密邮件(输入:系统公开参数,ID,邮件内容),生成密文C并发送给接收方- 接收方用私钥解密出邮件内容

2.4 双线性映射

定义
  令

      G 
     
    
      1 
     
    
   
  
    \mathbb{G}_1 
   
  
G1​和 
 
  
   
    
    
      G 
     
    
      2 
     
    
   
  
    \mathbb{G}_2 
   
  
G2​分别为两个阶为大素数 
 
  
   
   
     q 
    
   
  
    q 
   
  
q的加法循环群和乘法循环群,我们称满足以下条件的映射 
 
  
   
    
    
      e 
     
    
      ^ 
     
    
   
     : 
    
    
    
      G 
     
    
      1 
     
    
   
     × 
    
    
    
      G 
     
    
      1 
     
    
   
     → 
    
    
    
      G 
     
    
      2 
     
    
   
  
    \hat{e}:\mathbb{G}_1×\mathbb{G}_1\rightarrow\mathbb{G}_2 
   
  
e^:G1​×G1​→G2​为双线性映射:
  1. 双线性性:对 ∀ P , Q ∈ G 1 \forall P,Q\in\mathbb{G}_1 ∀P,Q∈G1​与 a , b ∈ Z q a,b\in Z_q a,b∈Zq​,都有 e ^ ( a P , b Q ) = e ^ ( P , Q ) a b \hat{e}(aP,bQ)=\hat{e}(P,Q)^{ab} e^(aP,bQ)=e^(P,Q)ab成立。
  2. 非退化性:若 P P P为群 G 1 \mathbb{G}_1 G1​的生成元,则 e ^ ( P , P ) \hat{e}(P,P) e^(P,P)是群 G 2 \mathbb{G}_2 G2​的生成元。
  3. 可计算性:对 ∀ P , Q ∈ G 1 \forall P,Q\in\mathbb{G}_1 ∀P,Q∈G1​,映射 e ^ ( P , Q ) \hat{e}(P,Q) e^(P,Q)在有效时间内可计算。

密码学中还给出了另一种形式的双线性映射形式:
双线性映射的另一种形式

IBE的实现

  •                                     S                            e                            t                            u                            p                            (                            k                            )                                  Setup(k)                     Setup(k):输入安全参数                                        k                                  k                     k,分别构造大素数                                        q                                  q                     q阶加法群与乘法群                                                   G                               1                                            \mathbb{G}_1                     G1​与                                                   G                               2                                            \mathbb{G}_2                     G2​与双线性映射                                                   e                               ^                                      :                                       G                               1                                      ×                                       G                               1                                      →                                       G                               2                                            \hat{e}:\mathbb{G}_1×\mathbb{G_1}\rightarrow\mathbb{G}_2                     e^:G1​×G1​→G2​,设                                        P                                  P                     P是                                                   G                               1                                            \mathbb{G}_1                     G1​的一个生成元(原根),设置明文的二进制长度为                                        n                                  n                     n,定义两个密码学哈希函数                                                   H                               1                                      :                            {                            0                            ,                            1                                       }                               ∗                                      →                                       G                               1                                            H_1:\{ 0,1\}^*\rightarrow\mathbb{G}_1                     H1​:{0,1}∗→G1​和                                                   H                               2                                      :                                       G                               2                                      →                            {                            0                            ,                            1                                       }                               n                                            H_2:\mathbb{G}_2\rightarrow\{ 0,1\}^n                     H2​:G2​→{0,1}n,随机选择                                        s                            ∈                                       Z                               q                                            s\in Z_q                     s∈Zq​,计算                                                   P                               s                                      ←                            s                            P                                  P_s\leftarrow sP                     Ps​←sP,输出系统公开参数                                        p                            a                            r                            a                            m                            s                            =                            <                            q                            ,                                       G                               1                                      ,                                       G                               2                                      ,                                       e                               ^                                      ,                            n                            ,                            P                            ,                                       P                               s                                      ,                                       H                               1                                      ,                                       H                               2                                      >                                  params=<q,\mathbb{G}_1,\mathbb{G}_2,\hat{e},n,P,P_s,H_1,H_2>                     params=<q,G1​,G2​,e^,n,P,Ps​,H1​,H2​>以及系统秘密参数                                        s                                  s                     s。
    
  •                                     E                            x                            t                            r                            a                            c                            t                            (                            s                            ,                            I                            D                            )                                  Extract(s,ID)                     Extract(s,ID):输入系统秘密参数                                        s                                  s                     s和用户                                        I                            D                            ∈                            {                            0                            ,                            1                                       }                               ∗                                            ID\in\{ 0,1\}^*                     ID∈{0,1}∗,输出私钥为                                                   d                                           I                                  D                                                 =                            s                                       H                               1                                      (                            I                            D                            )                                  d_{ID}=sH_1(ID)                     dID​=sH1​(ID)。
    
  •                                     E                            n                            c                            (                            I                            D                            ,                            m                            )                                  Enc(ID,m)                     Enc(ID,m):用户                                        I                            D                            ∈                            {                            0                            ,                            1                                       }                               ∗                                            ID\in\{ 0,1\}^*                     ID∈{0,1}∗和明文                                        m                                  m                     m,选择随机数                                        r                            ∈                                       Z                               q                                            r\in Z_q                     r∈Zq​,输出密文                                        C                            =                            <                            r                            P                            ,                                       H                               2                                      (                                       e                               ^                                      (                                       H                               1                                      (                            I                            D                            )                            ,                                       P                               s                                                 )                               r                                      )                            ⊕                            m                            >                                  C=<rP,H_2(\hat{e}(H_1(ID),P_s)^r)\oplus m>                     C=<rP,H2​(e^(H1​(ID),Ps​)r)⊕m>。
    
  •                                     D                            e                            c                            (                            C                            ,                                       d                                           I                                  D                                                 )                                  Dec(C,d_{ID})                     Dec(C,dID​):令                                        C                            =                            <                            U                            ,                            V                            >                                  C=<U,V>                     C=<U,V>,用户                                        I                            D                                  ID                     ID的私钥为                                                   d                                           I                                  D                                                       d_{ID}                     dID​,则解密                                        C                                  C                     C,输出明文                                        m                            =                            V                            ⊕                                       H                               2                                      (                                       e                               ^                                      (                                       d                                           I                                  D                                                 ,                            U                            )                            )                                  m=V\oplus H_2(\hat{e}(d_{ID},U))                     m=V⊕H2​(e^(dID​,U))。
    

依赖的数学难题——Computational Bilinear Diffie-Hellman(CBDH)
  令

      G 
     
    
      1 
     
    
   
  
    \mathbb{G}_1 
   
  
G1​和 
 
  
   
    
    
      G 
     
    
      2 
     
    
   
  
    \mathbb{G}_2 
   
  
G2​分别为两个阶为大素数 
 
  
   
   
     q 
    
   
  
    q 
   
  
q的加法循环群和乘法循环群, 
 
  
   
    
    
      e 
     
    
      ^ 
     
    
   
     : 
    
    
    
      G 
     
    
      1 
     
    
   
     × 
    
    
    
      G 
     
    
      1 
     
    
   
     → 
    
    
    
      G 
     
    
      2 
     
    
   
  
    \hat{e}:\mathbb{G}_1×\mathbb{G}_1\rightarrow\mathbb{G}_2 
   
  
e^:G1​×G1​→G2​为双线性映射, 
 
  
   
   
     P 
    
   
  
    P 
   
  
P是 
 
  
   
    
    
      G 
     
    
      1 
     
    
   
  
    \mathbb{G}_1 
   
  
G1​的一个生成元,任意给定 
 
  
   
   
     a 
    
   
     P 
    
   
     , 
    
   
     b 
    
   
     P 
    
   
     , 
    
   
     c 
    
   
     P 
    
   
     ∈ 
    
    
    
      G 
     
    
      1 
     
    
   
  
    aP,bP,cP\in\mathbb{G}_1 
   
  
aP,bP,cP∈G1​,其中 
 
  
   
   
     a 
    
   
     , 
    
   
     b 
    
   
     , 
    
   
     c 
    
   
     ∈ 
    
    
    
      Z 
     
    
      q 
     
    
   
  
    a,b,c\in Z_q 
   
  
a,b,c∈Zq​,则不存在一个有效的算法计算 
 
  
   
    
    
      e 
     
    
      ^ 
     
    
   
     ( 
    
   
     P 
    
   
     , 
    
   
     P 
    
    
    
      ) 
     
     
     
       a 
      
     
       b 
      
     
       c 
      
     
    
   
  
    \hat{e}(P,P)^{abc} 
   
  
e^(P,P)abc。

IBE的安全性证明
IBE的安全性证明
证明双线性映射的结合律

       e 
      
     
       ^ 
      
     
    
      ( 
     
    
      a 
     
    
      , 
     
    
      b 
     
    
      + 
     
    
      c 
     
    
      ) 
     
    
      = 
     
     
     
       e 
      
     
       ^ 
      
     
    
      ( 
     
    
      a 
     
    
      , 
     
    
      b 
     
    
      ) 
     
    
      ∗ 
     
     
     
       e 
      
     
       ^ 
      
     
    
      ( 
     
    
      a 
     
    
      , 
     
    
      c 
     
    
      ) 
     
    
   
     \hat{e}(a,b+c)=\hat{e}(a,b)*\hat{e}(a,c) 
    
   
 e^(a,b+c)=e^(a,b)∗e^(a,c)

证明:
已知

     b 
    
   
     , 
    
   
     c 
    
   
  
    b,c 
   
  
b,c属于加法群,不妨设 
 
  
   
   
     g 
    
   
  
    g 
   
  
g为生成元, 
 
  
   
   
     b 
    
   
     = 
    
   
     r 
    
   
     g 
    
   
     , 
    
   
     c 
    
   
     = 
    
   
     s 
    
   
     g 
    
   
  
    b=rg,c=sg 
   
  
b=rg,c=sg;

  
   
    
     
     
       e 
      
     
       ^ 
      
     
    
      ( 
     
    
      a 
     
    
      , 
     
    
      b 
     
    
      + 
     
    
      c 
     
    
      ) 
     
     
    
      = 
     
     
     
       e 
      
     
       ^ 
      
     
    
      ( 
     
    
      a 
     
    
      , 
     
    
      ( 
     
    
      r 
     
    
      + 
     
    
      s 
     
    
      ) 
     
    
      g 
     
    
      ) 
     
     
    
      = 
     
     
     
       e 
      
     
       ^ 
      
     
    
      ( 
     
    
      a 
     
    
      , 
     
    
      g 
     
     
     
       ) 
      
      
      
        ( 
       
      
        r 
       
      
        + 
       
      
        s 
       
      
        ) 
       
      
     
    
            
     
     
    
            
     
    
      = 
     
     
     
       e 
      
     
       ^ 
      
     
    
      ( 
     
    
      a 
     
    
      , 
     
    
      g 
     
     
     
       ) 
      
     
       r 
      
     
    
      ∗ 
     
     
     
       e 
      
     
       ^ 
      
     
    
      ( 
     
    
      a 
     
    
      , 
     
    
      g 
     
     
     
       ) 
      
     
       s 
      
     
     
    
            
     
    
      = 
     
     
     
       e 
      
     
       ^ 
      
     
    
      ( 
     
    
      a 
     
    
      , 
     
    
      r 
     
    
      g 
     
    
      ) 
     
    
      ∗ 
     
     
     
       e 
      
     
       ^ 
      
     
    
      ( 
     
    
      a 
     
    
      , 
     
    
      s 
     
    
      g 
     
    
      ) 
     
     
    
      = 
     
     
     
       e 
      
     
       ^ 
      
     
    
      ( 
     
    
      a 
     
    
      , 
     
    
      b 
     
    
      ) 
     
    
      ∗ 
     
     
     
       e 
      
     
       ^ 
      
     
    
      ( 
     
    
      a 
     
    
      , 
     
    
      c 
     
    
      ) 
     
    
   
     \hat{e}(a,b+c)\\ =\hat{e}(a,(r+s)g)\\ =\hat{e}(a,g)^{(r+s)}\ \ \ \ \ \\ \ \ \ \ \ =\hat{e}(a,g)^r*\hat{e}(a,g)^s\\ \ \ \ \ \ =\hat{e}(a,rg)*\hat{e}(a,sg)\\ =\hat{e}(a,b)*\hat{e}(a,c) 
    
   
 e^(a,b+c)=e^(a,(r+s)g)=e^(a,g)(r+s)          =e^(a,g)r∗e^(a,g)s     =e^(a,rg)∗e^(a,sg)=e^(a,b)∗e^(a,c)

运用双线性映射证明密文的可解密性

       H 
      
     
       2 
      
     
    
      ( 
     
     
     
       e 
      
     
       ^ 
      
     
    
      ( 
     
     
     
       d 
      
      
      
        I 
       
      
        D 
       
      
     
    
      , 
     
    
      U 
     
    
      ) 
     
    
      ) 
     
    
      = 
     
     
     
       H 
      
     
       2 
      
     
    
      ( 
     
     
     
       e 
      
     
       ^ 
      
     
    
      ( 
     
     
     
       H 
      
     
       1 
      
     
    
      ( 
     
    
      I 
     
    
      D 
     
    
      ) 
     
    
      , 
     
     
     
       P 
      
     
       s 
      
     
     
     
       ) 
      
     
       r 
      
     
    
      ) 
     
    
   
     H_2(\hat{e}(d_{ID},U))=H_2(\hat{e}(H_1(ID),P_s)^r) 
    
   
 H2​(e^(dID​,U))=H2​(e^(H1​(ID),Ps​)r)

证明:

       H 
      
     
       2 
      
     
    
      ( 
     
     
     
       e 
      
     
       ^ 
      
     
    
      ( 
     
     
     
       d 
      
      
      
        I 
       
      
        D 
       
      
     
    
      , 
     
    
      U 
     
    
      ) 
     
    
      ) 
     
     
    
      = 
     
     
     
       H 
      
     
       2 
      
     
    
      ( 
     
     
     
       e 
      
     
       ^ 
      
     
    
      ( 
     
    
      s 
     
     
     
       H 
      
     
       1 
      
     
    
      ( 
     
    
      I 
     
    
      D 
     
    
      ) 
     
    
      , 
     
    
      r 
     
    
      P 
     
    
      ) 
     
    
      ) 
     
     
    
      = 
     
     
     
       H 
      
     
       2 
      
     
    
      ( 
     
     
     
       e 
      
     
       ^ 
      
     
    
      ( 
     
     
     
       H 
      
     
       1 
      
     
    
      ( 
     
    
      I 
     
    
      D 
     
    
      ) 
     
    
      , 
     
    
      s 
     
    
      P 
     
     
     
       ) 
      
     
       r 
      
     
    
      ) 
     
     
    
      = 
     
     
     
       H 
      
     
       2 
      
     
    
      ( 
     
     
     
       e 
      
     
       ^ 
      
     
    
      ( 
     
     
     
       H 
      
     
       1 
      
     
    
      ( 
     
    
      I 
     
    
      D 
     
    
      ) 
     
    
      , 
     
     
     
       P 
      
     
       s 
      
     
     
     
       ) 
      
     
       r 
      
     
    
      ) 
     
    
   
     H_2(\hat{e}(d_{ID},U))\\ =H_2(\hat{e}(sH_1(ID),rP))\\ =H_2(\hat{e}(H_1(ID),sP)^r)\\ =H_2(\hat{e}(H_1(ID),P_s)^r) 
    
   
 H2​(e^(dID​,U))=H2​(e^(sH1​(ID),rP))=H2​(e^(H1​(ID),sP)r)=H2​(e^(H1​(ID),Ps​)r)

2.5 IBE总结

IBE与传统公钥加密的不同
  IBE的公钥可以是具有唯一标识用户作用的自然信息或者自然属性。

密钥托管问题
  用户的私钥由密钥生成中心KGC生成,因此KGC知道所有用户的私钥,存在“诈骗”和“泄露”的风险。

用户黑名单管理和密钥吊销问题
  一旦用户私钥泄露,无法通过更新公钥的方式撤销泄露的私钥。

密钥托管问题的解决方案

  • IBE+传统公钥加密:加密时需要同时使用接ID和传统公钥,但无需PKI。
  • “不经意”的IBE私钥生成技术:一个用户对应多个私钥,使密钥生成中心无法知道用户选的是哪个私钥,基于私钥的取证技术,使得若攻击者使用了非用户选定的私钥来解密,可以被发现。

3 基于属性加密(ABE)

Water
Sahai A, Waters B. Fuzzy identity-based encryption[C]//Annual international conference on the theory and applications of cryptographic techniques. Springer, Berlin, Heidelberg, 2005: 457-473.

3.1 传统访问控制

  假设Alice询问某数据库,有以下三种传统的控制方法:

自主访问控制 (DAC)
  用户有权对自身所创建的访问对象进行访问,并可将这些对象的访问权授予其他用户和从授予权限的用户收回其访问权限。
  特点:由数据库所有者自行设置数据的访问权限。
DAC
强行访问控制(MAC)
  由系统(通常为专门设置的系统安全员)对用户所创建的对象进行统一的强制性控制,按照规定的规则决定哪些用户可以对那些对象进行什么样的操作,即使是创建者,在创建一个对象后,也可能无权访问该对象。
  特点:由系统管理员统一设置文件与数据使用者的秘密等级,每个数据库使用者只能访问密级小于等于他的文件。
MAC
基于角色的访问控制(RBAC)
  对系统操作的各种权限不是直接授予具体的用户,而是在用户集合与权限集合之间建立一个角色集合。每一种角色对应一组相应的权限。一旦用户被分配了适当的角色后,该用户就拥有了此角色的所有操作权限。
  通过定义角色的权限,并对用户授予某个角色从而来控制用户的权限。这样使得不必每次在创建用户时都进行分配权限的操作,只要分配用户相应的角色即可。用户和权限逻辑分离,方便权限管理,减少系统的开销。
ABE
传统访问控制存在的问题

  • 数据库以明文形式存放,通过验证用户权限实现数据访问,其安全性完全依赖用户对服务器安全性的信任。
  • 若数据库服务器存在漏洞,导致攻击者获得管理员权限,则该攻击者可以绕开访问控制策略获得数据。
  • 若数据库管理员本身与攻击者合谋,同样可以导致访问控制策略失效。
  • 传统的访问控制方法无法保证云计算环境下的数据安全性。 - 数据集中的云平台更容易成为攻击目标。- 云平台缺乏可信性。

  传统的访问控制存在问题的本质是:数据库管理员拥有最高级别的权限,这将成为攻击者的重点攻击目标。

3.2 ABE简介

起源
  模糊的基于身份加密,即不同的基于身份公钥被同一个私钥解密。

定义
  简而言之,ABE就是看属性集合与策略是否相匹配的一个公钥加密游戏。
  与传统方法不同的是,设计者将属性集合与策略嵌入到了用户私钥与密文中,这样一来,私钥与密文输入解密算法尝试解密的过程,实际也就是属性集合与策略相匹配的过程,倘若能够匹配成功,则算法顺利完成解密操作,用户可成功恢复出明文数据。倘若匹配失败,则用户无法恢复明文,解密失败。

分类

  • KP-ABE:以明文的属性做公钥,以访问控制策略生成对应的私钥。KP-ABE
  • CP-ABE:以访问控制策略做公钥加密明文,以用户的属性生成对应的私钥。CP-ABE

KP-ABE(基于密钥策略的属性加密,Key-Policy ABE,KP-ABE)是将策略嵌入到用户密钥中,属性嵌入到密文中。密钥对应于一个访问结构而密文对应于一个属性集合,解密当且仅当属性集合中的属性能够满足此访问策略。这种设计比较接近静态场景,此时密文用与其相关的属性加密存放在服务器上,当允许用户得到某些消息时,就分配一个特定的访问策略给用户,其应用场景则更加偏向于付费视频网站、日志加密管理等等。如果用户想解密多个文件,那么他必须拥有多个可以满足匹配的秘钥,否则不能解密多个文件。

CP-ABE(基于密文策略的属性加密,Ciphertext-Policy ABE,CP-ABE)是将策略嵌入到密文中,属性嵌入到用户密钥中。密文对应于一个访问结构而密钥对应于一个属性集合,解密当且仅当属性集合中的属性能够满足此访问结构。
CP-ABE基于属性的加密运用密码机制保护数据,由数据拥有者规定访问密文的策略,将属性集合与访问资源相关联,数据使用者可以根据自己的授权属性的访问密文信息,该技术适合隐私数据共享等访问类应用。
CP-ABE由于策略嵌入密文中,这就意味着数据拥有者可以通过设定策略去决定拥有哪些属性的人能够访问这份密文,也就相当于对这份数据做了一个粒度可以细化到属性级别的加密访问控制,CP-ABE的应用场景一般是公有云上的数据加密存储与细粒度共享。

KP-ABE与CP-ABE的应用差异

  • KP-ABE适合于加密方与访问控制方分离的场景,能够实现用户对特定数据的访问。如数据安全采集与共享。KP-ABE应用

  上图中的传感器,可以采集声音、温度、震感三种信息,我们可以将其视为单一属性1、2、3。由于单一属性天然不具备访问策略,所以采用以明文属性做公钥的KP-ABE加密方式。数据中心负责存储加密的三种信息。用户如果需要访问某些信息的话,需要向密钥生成中心获取相应的访问控制策略。
  这种访问控制方式,便于用户的增减,而不需要改变传感器的设置。用户拿到相应的私钥后可以向数据中心获取数据。

  • CP-ABE适合于加密方与访问控制方一体的场景,能够实现数据对特定用户开放。如企业数据安全存储与共享。

CP-ABE由于策略嵌入密文中,这就意味着,数据拥有者可以通过设定策略去决定拥有哪些属性的人能够访问这份密文,也就相当于对这份数据做了一个粒度可以细化到属性级别的加密访问控制。

CP-ABE应用

  管理员选择访问控制策略作为公钥加密文件并上传,当经理、职员等信息检索方具备的属性满足访问策略的时候,就能够用私钥解密密文。
  在CP-ABE方案中,文件的上传方并没有数据管理员那么高的权限,它只能上传数据,并通过访问策略规定数据查看人。文件上传方除了掌握自己上传的文件之外,并不能知道其他文件上传方的文件。

ABE定义

  •                                     S                            e                            t                            u                            p                                  Setup                     Setup算法   - 输入:安全参数- 输出:系统公开参数和系统秘密参数
    
  •                                     E                            x                            t                            r                            a                            c                            t                                  Extract                     Extract算法   - 输入:系统秘密参数,用户的访问控制策略(KP-ABE)或若干属性(CP-ABE)- 输出:私钥
    
  •                                     E                            n                            c                                  Enc                     Enc算法   - 输入:系统公开参数,明文的若干属性(KP-ABE)或访问控制策略(CP-ABE),明文- 密文
    
  •                                     D                            e                            c                                  Dec                     Dec算法   - 输入:私钥,密文- 输出:明文
    

3.3 CP-ABE的实例

CP-ABE的实例1
在这里插入图片描述

3.4 ABE总结

  ABE是密码学与传统访问控制的“有机结合”。在实际应用中,ABE与传统访问控制最大的不同是,ABE不需要信任服务器,即使服务器是恶意的或者被攻破,也不会导致数据泄露。


🤖 第④部分由L3H_CoLin编写,有一些修改。🤖

4 代理重加密(PRE)

4.1 ABE的缺陷

  针对公司数据管理的CP-ABE需要管理员(加密方、访问控制方)对任一企业文件选择访问控制策略,并以该策略为公钥,使用Enc算法加密文件,最后将生成的文件上传至云端。这个访问控制方是必不可少的。
  另外如果数据拥有者仅为普通个人用户,则难以制定专业的、合理的访问控制策略,难以为数据共享者提供在线的私钥生成和分法服务。因为用户的数量一多起来,对访问控制策略的计算效率是一个很大的挑战,包括密钥的生成和分发也需要在线进行,也很难保证密钥在传输过程中的安全性。
  这就需要引出代理重加密(PRE)的概念了。

4.2 PRE简介


  如上图所示,两人要想通过云存储交换文件,使用对称密钥加密存储。Bob想要获得Alice的文件并成功解密,总不能要求Alice发送对称加密的密钥给Bob,这是绝对不安全的,而且文件密钥传输需要两人同时在线,也产生了不便。

  如果采用公钥加密呢?Bob想解密Alice的文件,同样不能要求Alice发送私钥。但Alice可以将Bob所需的文件下载解密后再使用Bob的公钥加密上传。这样虽然可以能够在两人不同时上线的情况下完成文件传输,但增加了Alice的加解密成本。
  由此,2003年Ivan等人正式提出PRE作为这个问题的一个解决方案:

  在PRE体系下,Alice只需要生成一个神奇的重加密密钥,将其发送给云端后云端可以使用重加密密钥将文件变成Bob可以解密的文件,这样Alice就无需自己进行加解密操作。

PRE优点

  • Alice和Bob无需同时在线
  • Alice生成重加密密钥的开销较少

PRE定义

  •                                     Setup                            ⁡                                  \operatorname{Setup}                     Setup算法:   - 输入:安全参数- 输出:系统公开参数和系统秘密参数
    
  •                                     Extract                            ⁡                                  \operatorname{Extract}                     Extract算法(仅在基于身份类的PRE中才存在):   - 输入:系统秘密参数,用户的身份- 输出:私钥
    
  •                                     Enc                            ⁡                                  \operatorname{Enc}                     Enc算法:   - 输入:系统公开参数、Alice公钥、明文- 输出:原始密文
    
  •                                     Dec-1                            ⁡                                  \operatorname{Dec-1}                     Dec-1算法:   - 输入:Alice私钥,初始密文- 输出:明文
    
  •                                     RK                            ⁡                                  \operatorname{RK}                     RK算法:   - 输入:Alice私钥、Bob公钥- 输出:重加密密钥
    
  •                                     ReEnc                            ⁡                                  \operatorname{ReEnc}                     ReEnc算法:   - 输入:重加密密钥,初始密文- 输出:重加密密文
    
  •                                     Dec-2                            ⁡                                  \operatorname{Dec-2}                     Dec-2算法:、   - 输入:重加密密文,Bob私钥- 输出:明文
    

基于IB-PRE的安全云数据存储与共享

4.3 PRE的实例

4.4 PRE的其它问题

  • 细粒度控制问题:打破“全或无”的共享模式。当云端拿到重加密密钥之后,可以对所有Alice的文件进行转换,从而让Bob获取,这显然是不合理的。
  • 多次重加密的问题:打破一个密文只能以重加密共享一次的问题,就是说一个被Alice私钥加密的文件经过重加密密钥转换后变成Bob的私钥可以解密的文件,这个文件是否可以继续被其他的重加密密钥转换为其他用户可以解密的文件?
  • 双向重加密的问题:打破一次重加密过程只能实现Alice→Bob或Bob→Alice的单向共享
  • 复杂多特性PRE方案的设计问题:使得一个PRE具有上面所描述的多个特性

4.5 总结

  • 什么是安全,现代密码为什么安全 - 基于信任构建的标注可满足性- 现代密码的安全性基于对数学难题的信任构建
  • 如何构建 - 可证明安全性- 科学定义安全标准(安全性定义),特别是对攻击者的定义- 基于数学难题严格证明安全性- 利用数学难题的求解复杂度量化现代密码算法的安全性
  • 基于身份加密 - 是公钥体制的一种,但不同于传统公钥加密- 以身份信息作为公钥,取消了对可信第三方的需求- 基于双线性映射构建,实用性有保障- IBE启发了多功能公钥密码的发展
  • 密文数据安全存储与共享 - 简单的对称加密和公钥加密可以实现安全存储,但是不便于安全共享- 对称密码:需要发送方和接受方同时在线- 公钥密码:增加了发送方的通信和计算开销- 常规对称密码和公钥密码主要解决安全通信与存储问题,并不考虑安全共享

本文转载自: https://blog.csdn.net/qq_53334657/article/details/127449253
版权归原作者 叫我半勺小芋圆. 所有, 如有侵权,请联系我们删除。

“【密码学】高级密码学-1”的评论:

还没有评论