一、大家初看密码方案的时候,一定迷惑于为什么论文用大篇幅进行安全性证明。为什么需要证明安全性呢?
比如一个加密方案,若定义安全性为敌手得不到完整密文,那么敌手就很有可能有能力得到部分密文。而安全的加密方案应该使得敌手得不到任何有用的消息。利用安全性规约,我们能够很优雅、规范、严谨地证明我们方案能够达到的安全性。
二、通常是将我们的方案归约到某一个公认的困难性问题上(如离散对数等).证明思路是如果存在算法攻破我们的方案,那么就可以构造算法攻破公认的困难性问题。(后面详细举例)
严谨来说:首先确定密码算法的安全目标,如加密的CCA安全等,然后构造形式化的敌手模型和实验,把密码算法归约到对已知困难性问题的攻击,这就是可证明安全。
下面给出以下常见的困难性问题例子:
例如:离散对数问题:给定 g , c = g a ( m o d p ) g,c=g^a(mod ~p) g,c=ga(mod p),求解参数 a a a是困难的。
有同学可能想的是对 c c c求个对数不就出来了吗。但是需要注意的是这里是做了模 p p p运算,在不模的情况下 g a = c + k p g^a=c+kp ga=c+kp,而 p p p又是一个很大的数,比如128bit(是 p p p的比特长度,而不是数值是128!!, p p p范围在 2 128 2^{128} 2128)。
CDH问题:给定 g , g a , g b g,g^a,g^b g,ga,gb,求解 g a b g^{ab} gab是困难的。
结论:如果存在敌手A能攻破(求解)离散对数问题,那么就可以求解CDH问题
证明思路:假设小明收到CDH问题实例 g , g a , g b g,g^a,g^b g,ga,gb,他想利用攻击者来求出 g a b g^{ab} gab。那么他把 g a g^a ga或 g b g^b gb发送给攻击者。因为攻击者有能力求解离散对数问题,敌手把求解的结果 a a a或 b b b返回给小明,那么小明就可以计算出 ( g a ) b (g^a)^b (ga)b或者 ( g b ) a (g^b)^a (gb)a。小明成功利用攻击者的能力求解出了CDH问题的解。
所以说如果敌手攻破了离散对数,那么小明利用这个攻击者构造了上述算法求解了CDH问题。
**DDH问题:**给定 g , g a , g b , T g,g^a,g^b,T g,ga,gb,T,判定 T = g a b T=g^{ab} T=gab或者 T = g c T=g^c T=gc是困难的。(判定T是计算出来的还是随机选的)
双线性映射:群 G , H , G T G,H,G_T G,H,GT是三个循环群,且群的阶均为素数 p p p,
g g g是群 G G G的生成元, h h h是群 H H H的生成元, e ( g , h ) e(g,h) e(g,h)是群 G T G_T GT的生成元。
定义双线性映射 e : G × H → G T e:G\times H \rightarrow G_T e:G×H→GT满足以下性质:
1.对任意的 a , b ∈ Z p ∗ a,b \in \mathbb{Z}_p^* a,b∈Zp∗, e ( g a , h b ) = e ( g , h ) a b e(g^a,h^b)=e(g,h)^{ab} e(ga,hb)=e(g,h)ab
2. e ( g , h ) ≠ 1 e(g,h)\ne 1 e(g,h)=1且 e ( g a , h b ) = 1 e(g^a,h^b)= 1 e(ga,hb)=1当且仅当 a = 0 , b = 0 a=0,b=0 a=0,b=0
思考为什么需要第二点成立:
提示:如果 e ( g , h ) = 1 e(g,h)=1 e(g,h)=1,那么群 G T G_T GT中素由生成元表示任意元 e ( g , h ) a e(g,h)^a e(g,h)a等于多少?
非对称双线性映射: G = H , e : G × G → G T G=H,e:G\times G \rightarrow G_T G=H,e:G×G→GT
对称双线性映射: G ≠ H , e : G × H → G T G\ne H,e:G\times H \rightarrow G_T G=H,e:G×H→GT
注意:为什么双线性成立,底层原理是什么?这些问题不需要了解!方案构造时只需要知道双线性的性质(除非你要去做优化)。底层已经被封装好了!!
思考:非对称双线性上CDH,DDH成立,但是对称DDH不成立。为什么不成立?
对称:给定 g , g a , g b , T g,g^a,g^b,T g,ga,gb,T,判定 e ( g a , g b ) e(g^a,g^b) e(ga,gb)是否等于 e ( g , T ) e(g,T) e(g,T)
非对称:给定 g , g a , g b , T g,g^a,g^b,T g,ga,gb,T,无法计算 e ( g a , g b ) e(g^a,g^b) e(ga,gb),因为 g b g^b gb不在群 H H H上。
同理给出BCDH问题:给定 g , g a , g b , g c g,g^a,g^b,g^c g,ga,gb,gc,求解 e ( g , g ) a b c e(g,g)^{abc} e(g,g)abc是困难的。