5.3.Rabin&ElGamal PPT课件.ppt

文档介绍：第5章公钥密码
Rabin算法描述
Rabin算法既可看成是RSA算法的一个特例,也可看成对RSA算法的一个修正。
Rabin算法是一个被证明其破解难度正好等价于大整数分解的公钥密码算法,它是第一个可证明安全的公钥密码算法。
Rabin算法的安全性基于求解合数模下的平方根的困难性。
Rabin算法描述
Rabin算法描述(续)
加密变换:
明文消息m,通过计算得到密文c。
解密变换:
为了解出密文c ,需求解二次同余方程:
Rabin算法描述(续)
令,则上面方程可改写为:

再令,则方程进一步改写为:

因此,解密问题归结为求C模n的平方根。
Rabin算法描述(续)
方程有四个解,当时:
方程的两个解为:
方程的两个解为:
Rabin算法描述(续)
组合得到四个一次同余方程组:
解这四个同于方程组,其解是C模n的四个平方根,要寻找的明文就是四个解的其中之一。
Rabin算法描述(续)
Rabin算法的加密函数不是单射,解密具有不确定性,合法用户不能确切地知道到底哪一个解是真正的明文。
如果加密之前在明文消息中插入一些冗余信息,可以帮助收信者准确的识别解密后的明文。
Rabin算法描述(续)
Rabin算法的解密过程是寻找 C 模 n 的平方根,这个问题的难度等价于n 的因子分解。
尽管计算模为素数的平方根是多项式时间可解的,但其过程仍然很复杂。
要求p与q是模4同余3的限制条件是为了使解密的计算和分析变的更容易
Rabin算法的特例
取b=0时:可看成加密指数e=2的RSA算法。
加密变换:
解密变换: