35.5概率加密 概率加密是由 S Goldwasser和 S Mical提出的。 基本想法是使公钥密码体制的信 息泄露为0 在多项式时间内由密文不能推出 明文或密钥的任何信息
3.5.5 概率加密 概率加密是由 S.Goldwasser 和 S.Micali提出的。 基本想法是使公钥密码体制的信 息泄露为0 在多项式时间内由密文不能推出 明文或密钥的任何信息
对给定的公开密钥,对一个确定的明文 加密总是得到一个相应的密文,因此攻 击者就可采用已知明文进行攻击。 如果对于一个明文,在给定密钥下,加 密结果不是确定的,而是概率的,使 6个明文在同二个密钥下可对应多个密文, 就使得上述攻击变得相当困难 SA EIGam密码体制以及椭圆曲线上的 EIGamal密码体制属于这类
对给定的公开密钥，对一个确定的明文 加密总是得到一个相应的密文，因此攻 击者就可采用已知明文进行攻击。 如果对于一个明文，在给定密钥下，加 密结果不是确定的，而是概率的，使一 个明文在同一个密钥下可对应多个密文， 就使得上述攻击变得相当困难。 ElGamal密码体制以及椭圆曲线上的 ElGamal密码体制属于这类
定义中的条件(1)规定了加解密方法,特别是引进了 随机数ro 条件(2)则保证明文m的所有可能密文分布与m≠m的 所有可能密文分布是不可区分的,这就使得攻击者无 法确认密文是对应什么明文的。 1)对母个k∈K,母个E1∈E,D1∈D,有 p(E(m,r)m(对m∈M,vr∈R),并且当 冷Ymm(m∈M时,有Em,m)≠Em,n) 其中E1:MxR→C,D:C→M A2没是安全参数,对任意keK,任意meM,在C 上定义一个概率分布Pkm 这里PM(l)表示在给定密钥k和明文的条件下c是密 文的概率(概率在所有r∈R上计算) 如果m、m'∈M,有m≠m且keK,则概率分布Pkm ≠PLm不是E可区分的
定义3.4：一个概率公钥密码体制是一个 6元组 (M,C,K,E,D,R)。其中 M 、 C 、 K分别是明文空间、 密文空间和密钥空间， E 和 D分别是公开加密规则 集和秘密解密规则集， R为随机量空间，它们满足 以下要求： (1)对每个 k K，每个 E k E，D k D，有 D k(E k(m,r))=m( 对 m M, r R) ，并且当 m m'(m' M)时，有 E k(m,r) E k(m',r) 其中 E k：M R → C，D k：C → M (2) 设 ε是安全参数，对任意 k K，任意 m M，在 C 上定义一个概率分布 Pk,m 。 这里 Pk,M(c)表示在给定密钥 k和明文的条件下 c是密 文的概率 (概率在所有 r R上计算 ) 。 如果 m 、m' M，有 m m' 且 k K，则概率分布 Pk,m Pk,m’不是 ε可区分的。 定义中的条件(1)规定了加解密方法，特别是引进了 随机数 r 。 条件(2)则保证明文 m的所有可能密文分布与m' m 的 所有可能密文分布是不可区分的，这就使得攻击者无 法确认密文是对应什么明文的
1 Goldwasser-Micali概率公钥密码 体制 Goldwasser-Micali在1984年给出了一个 概率公钥密码方案。 该体制是基于奇合数n平方剩余难解问 题建立的。 奇合数n平方剩余问题对于给定的一个 多人A奇合数n和整数a,决定a是否为模m的平 方剩余,即判定x2= a mod n是否有解 若有解,则是modn的平方剩余,否则 a是模n的非平方剩余
1.Goldwasser-Micali概率公钥密码 体制 Goldwasser-Micali在1984年给出了一个 概率公钥密码方案。 该体制是基于奇合数n平方剩余难解问 题建立的。 奇合数n平方剩余问题:对于给定的一个 奇合数n和整数a，决定a是否为模n的平 方剩余，即判定x2=a mod n是否有解， 若有解，则a是mod n的平方剩余，否则 a是模n的非平方剩余
Euler准则:设p是奇素数,则x是p的平方剩余当且仅 当xP)2= I modp 对于n=pq,x是n的平方剩余当且仅当x|=(x|=1。 p/( Zn=x1sx<n,J(n, x)=1 在Zn上定义谓词Qn x是模n的平方剩余 Q 10x是模n的非平方剩余 当n是素数或n的素因子已知时,Q是容易 计算的, 当n的素因子未知时,Q的计算是难的。 这就是所谓的平方剩余假设
Goldwasser-Micali的方案具体过程： 设 N 表示正整数集， nN 。 令 Zn*={x|1≤x<n,(x,n)=1}， Zn'={x|1≤x<n,J(n,x)=1}。 在Zn'上定义谓词Qn： 是模 的非平方剩余 是模 的平方剩余 x n x n Qn 01 当n是素数或n的素因子已知时，Qn是容易 计算的， 当n的素因子未知时，Qn的计算是难的。 这就是所谓的平方剩余假设。 Euler 准则：设 p 是奇素数，则 x 是 p 的平方剩余当且仅 当 x(p-1)/21modp。 对于 n=pq，x 是 n 的平方剩余当且仅当 1 qx px