加密使用算法4.ppt

第8次RSA和rabbin算法(以下简称RSA加密安全性(接下来简称RSA加密)实践rabbin加密算法执行rabbin加密安全公钥加密总结，3.8回合攻击，3.8回合攻击，3 对3.9消息隐藏问题、3.9消息隐藏问题(续)、3.10前因搜索攻击3.11RSA-OAEP、3.11RSA-OAEP (续)、3.11RSA-OAEP和3.12定时攻击RSA算法的攻击不仅仅是算法本身，还可能导致不适当的执行攻击者可能会利用这些执行的弱点来威胁整个RSA系统的安全性。 密码系统的攻击受到安全工程师和用户的关注。 执行攻击包括定时攻击、功耗分析攻击、错误攻击、电磁辐射攻击等。 我们时常把这些攻击称为边信道攻击(side-channelattacks )。 侧信道一词用于描述目标设备，例如智能卡，无意中泄露的信息。 3.12定时攻击(继续)定时攻击中的边信道是指设备操纵机密密钥所需的时间。 攻击者可以精心测量目标系统的运行时间，以发现存储在设备上的私钥，最终崩溃整个安全系统。 许多现实系统可能受到这次攻击的威胁，例如各种密码令牌、基于网络的密码系统、其他攻击者能够准确地测量运行时间的应用系统等。 3.12定时攻击(续)假设环境。攻击者允许系统观察密文消息g的解密。 他还知道加密算法的执行细节，并且可应用这些信息来确定算法的计算期间可发生的不同步骤的执行时间。 并且，假定使用上述算法4计算gd(modn )。 3.12定时攻击(继续)、3.12定时攻击(继续)、3.12定时攻击(继续)、3.12定时攻击(继续)、4RSA加密实践、4.1模式大小由于分解整数算法的进展，尤其是数域过滤方法，在RSA中模式n应该至少是1024比特从长期安全的观点来看，应该使用2048比特以上的模型。 4.2素数的选择(1)素数p和q的选择原则是使分解整数n=pq无法计算。 主要的p和q的限制是，必须具有与足够长度近似相等的比特长度。 例如，如果使用1024比特的模拟n，则p和q应该都是512比特。 (2)对素数p和q的另一限制是p-q不应过小。 随机选择p和q时，p-q以压倒性概率增大。 4.2素数的选择(续) (3)许多地方建议使用强素数p和q。 一个素数p是强素数，必须满足以下三个条件： *p-1有一个大的素数因子叫做*p 1也有一个大的素数因子*r-1还有一个大的素数因子。 而且，第一个条件的原因是存在Pollard的p-1分解算法，该算法仅在模式n中存在一个素性因子p满足p-1平滑时有效的第二个条件是存在p 1分解算法，该算法仅在模式n中存在一个素性因子p满足p 1平滑时才进行此外，如果随机选择素数p且它足够大，则p-1和p 1很可能具有大的素数系数。 另外，如果随机选择p和q，则可以忽略循环攻击成功的可能性。 因此，强素数不比随机选择的素数提供更多的保护。 在现有的分解算法知识中，没有理由使用强质数。 另一方面，生成强素数只是相对于随机生成的素数增加了很小的计算时间，因此使用强素数并不经常开销。 此外，如果随机选择了4.3指数(1)加密指数e，则要在RSA加密中使用算法4，需要k阶模均方根k/2阶模乘法。 这里，k是模式n的位长。 加密速率可以选择较小的加密指数e，或者尽可能减少加密指数e的二进制表示中的第一数字。 4.3指数(续) (2)实际上，加密指数通常选择e=3。 在这种情况下，p-1和q-1必须不能被3整除。 这个优点是加密速度非常快，只需要主模式乘法和主模式平方。 另一个最常用的加密指数是e=216 1=65537。由于该数字的二进制表示仅有两个1，因此为了使用算法4进行加密，仅需要16次模式平方和1次模式平方。 一般认为加密指数e=216 1优于e=3。 这是因为应用程序通常不太可能向216个收件人发送相同的消息。 4.3指数(续) (3)由于小指数攻击，有必要解码指数dn0.292。 Boneh和Durfee认为他们的攻击算法不能成为理论。 因为他们也不能证明攻击算法一定会成功。 但实验证明攻击算法是有效的，没有发现攻击算法失败的例子。5Rabin加密算法、5.1算法描述符、5.1算法描述符(续)、5.1算法描述符(续)、5.1算法描述符(续)、6Rabin加密执行、6.1计算平方根、6.2效率Rabin加密过程的效率非常高的是初级模式平方计算相比之下，如果RSA加密使用加密，则e=3需要平方和平方计算。 Rabin解码比加密慢，但是在与RSA解码相同的级别。 6.3冗馀问题Rabin公钥加密方案的一个缺点在于接收者必须从四种可能的情形中选择正确的经解密的明文消息。 解码中的不确定性问题可以通过增加预定义明文消息的冗馀来解决。 (例如，必须复制明文消息的最后64比特。 以这种方式，用非常高的概率解码的四条可能的明文消息中只有一条适合冗馀的规则。 如果四个平方根中没有一个符合冗馀规则，则接收方确定错误并拒绝密文消息。 (1)Rabin公钥密码方式中有RSA密码那样的小指数密码和前项的检索问题。 前项检索问题可以通过在明文信息中加盐来解决。 (2)作为被动攻击者的任务是从密文信息c中恢复明文信息m。 这就是平方根SQROOT问题。 分解n和计算型n的平方根问题是计算等价的。 因此，Rabin公钥加密方案可证明能够抵抗被动攻击者的攻击，假定分解n在计算上是不可能的。 7Rabin加密的安全性，并且假定多项式时间算法r能够解决SQROOT问题。 该算法可以用来解决数n的分解问题。 随机选择整数x以满足(x，n)=1，并计算ax2(modn )。 然后，当输入是a和n时，算法r被执行并返回模式n的平方根y。 在yx(modn )的情况下，分解尝试失败，随机选择另一个整数x，然后重复上述步骤。 否则，可以获得(x-y，n)n的不寻常的因子，p或q。 由于a有4个模式n的平方根，因此每次成功的可能性是1/2。 (3)对于主动攻击者，Rabin公钥密码存在选择密文攻击的问题。 这种攻击可以按照以下步骤进行。 攻击者选择随机的整数m，计算cm2(modn )。 攻击者把c提交给a的解密机，把c解密后返回明文信息y。 因为a不知道明文的消息m，并且m是随机选择的，所以明文的消息y不一定是相同的。 随机返回可以是1/2，其中y不等于m(modn )。 在此情况下，(m-y，n )为n的素数系数。 否则，攻击者可以交换m重复上述过程。 (4)在上述情况下使用冗馀规则时，Rabin公钥加密方式没有选择密文攻击的问题。 如果攻击者选择了消息m并具有规定的冗馀，并且将cm2(modn )提供给a密码机，则密码机将消息m本身以非常高的概率返回给攻击者(因为另一种三种c模式的平方根中不包含规定冗馀的概率很大)，并且也不会给攻击者任何信息。 另一方面，如果攻击者选择不包含冗馀的信息m，则4个模式的平方根不具有必要的冗馀形式的可能性非常高。 在此情况下，解密机认为c的解密失败，不回复攻击者。 因此，Rabin公钥密码通过增加适当的冗馀规则来提高实用价值。 8.1公钥加密的总体要求是一个公钥系统，其中针对任何消息mm，消息集合m、密钥集合k和相加/解密函数E/D要求满足dk(ek(m，m )=m。(2)容易为消息mm和密钥kk计算值Ek(m )和Dk(m )。 8.1对公钥加密的请求(续)，(3)给出的密钥kk容易找到函数Ek和Dk。 (4)如果对于大部分密钥kk仅知道函数Ek，则该算法不能有效地计算函数Dk。 (1)对于8.1