(1)密钥生成 在给定安全参数k(k是正偶数)后,每个用户随机 选取两个k2bi的互异素数p1q,令nP1q,随 机选取模n的非平方剩余y∈Zn,然后将{py作 为公开密钥,而pq则作为秘密密钥。 (2)加密过程 A向B发送信息m=(m1m2m)∈{0,1},则 6 for i=1 toDo x{随机选取x∈Z*n if m;=l then e x mod nB else ei =xy mod nB) 然后将e1e2发送个B (3)解密过程 用户B在收到密文ee2…e后,计算 for i=l to l do m=Qn(e)可求出所有明文
(1)密钥生成 在给定安全参数k(k是正偶数 )后，每个用户 I随机 选取两个k/2 bit的互异素数 p I,q I，令 n I=p I q I，随 机选取模 n I的非平方剩余 y I Z’ nI，然后将{n I,y I } 作 为公开密钥，而 p I,q I则作为秘密密钥。 (2)加密过程 A 向 B发送信息m=(m 1 m 2 m l ) {0,1} l，则 for i=1 to l do { 随机选取 x Z* n B ， if mi=1 then ei=x 2 mod n B else ei=x 2y mod n B } 然后将 e 1 e 2 e l发送个 B 。 (3)解密过程 用户 B在收到密文 e 1 e 2 e l后，计算 for i=1 to l do mi=Q n B(ei )可求出所有明文
容易证明上述解密过程是正确的。 在 Goldwasser-Miai概率公钥密码体制 中,明文m的密文不是唯一的,而是依 赖于随机量x。 已有分析结论表明该方案有较强的安全 冷以性。但缺陷是密文数据扩展为明文的k 倍,而通常k≈664,故实用价值不大
容易证明上述解密过程是正确的。 在Goldwasser-Micali概率公钥密码体制 中，明文m的密文不是唯一的，而是依 赖于随机量x。 已有分析结论表明该方案有较强的安全 性。但缺陷是密文数据扩展为明文的k 倍，而通常k664，故实用价值不大
2Bum- Goldwasser概率公钥密码体制 Bum- Goldwasser在1984年给出了另一个概率公 钥密码方案。该体制同样基于平方剩余难解问 题建立。其基本思想是利用BBS发生器产生lbit 的伪随机序列作为密钥流对明文进行加密。 所谓BBS发生器定义如下: 设pq为两个满足p=q=3mod4的互异素数 n=pq,QR(n)表示模n的平方剩余集合 g八s∈QR(n称为种子, 对0s计算S1=s2modn,z=Smod2,则 fs0)=(z1,z2,,)即为BBS发生器的输出结果
2.Blum-Goldwasser概率公钥密码体制 Blum-Goldwasser 在1984年给出了另一个概率公 钥密码方案。该体制同样基于平方剩余难解问 题建立。其基本思想是利用BBS发生器产生 l bit 的伪随机序列作为密钥流对明文进行加密。 所谓BBS发生器定义如下： 设p,q为两个满足 p q 3 mod 4的互异素数， n=pq ， QR(n) 表示模 n 的平方剩余集合， s 0 QR(n)称为种子， 对 0 i< l 计 算 si+1=s i 2modn,zi+1=si+1mod 2 ， 则 f(s 0)=(z 1,z 2 , z l )即为BBS发生器的输出结果
◆Blum- Goldwasser的方案具体过程: ◆设pq为两个满足p≡q≡3mod4k2bit 的互异素数,n=pq,公开n,而p和q保 密。对明文m∈{0,1} ◆加密方法: ·在中任取一元素作为BBS发生器的种 子s0,计算出工作密钥z1,z2,…,1,并计 算sH=s2modn;然后计算c=(m+z)mod 2(1≤<。 ◆最后将c1c2…cH+作为密文发送出去
Blum-Goldwasser的方案具体过程： 设p,q为两个满足 p q 3 mod 4 k/2 bit 的互异素数，n=pq，公开 n，而 p 和 q 保 密。对明文 m {0,1} l ， 加密方法： 在 Z n *中任取一元素作为BBS发生器的种 子 s 0，计算出工作密钥 z 1,z 2 , z l，并计 算 s l+1=s l 2mod n；然后计算 c i=(m i+z i)mod 2(1 ≤i< l } 。 最后将 c 1 c 2 c l sl+1作为密文发送出去
解密过程是: 在收到密文c12…CA后,计算 a1=(p+1)/4)mod(p-1), a2=(q+1)/4)4mod(q-1), b 1+1 mod p b2=s1 mod q k入利用中国剩余定理求x,使得满足 x= b,mod p和x=b2modq, 则s= x mod n 利用BBS发生器从S计算出工作密钥 最后计算m1=(c+)mod2(1≤i<得明文
解密过程是： 在收到密文c1c2clsl+1后，计算 a1=((p+1)/4)l+1mod(p-1)， a2=((q+1)/4)l+1mod(q-1)， b s p al mod 1 1 1 b s q al mod 2 2 1 利用中国剩余定理求x，使得满足 x= b1mod p 和x= b2mod q， 则s0 =x mod n 利用BBS发生器从s0计算出工作密钥 z1,z2,zl， 最后计算mi=(ci+zi)mod 2(1≤i<l}得明文