增强的自然蒙哥马利指数掩蔽

发明领域

本发明涉及密码学领域，具体涉及目的是对于物理攻击安全的密码算法和设备，例如使用公钥密码系统的智能卡。

技术背景

在CRC出版社1995年出版的Douglas Stinson的《Cryptography，Theory and Practice》(以下称为Stinson)中描述了密码掩蔽方法。Shamir的5,991,415号美国专利(以下称为Shamir)讨论了非侵入式攻击技术和秘密模数的掩蔽技术。Kocher等的6,298,442号美国专利(以下称为Kocher)和Joye等的WO 03014916号PCT出版物(以下称为Joye)也公开了掩蔽方法。

最初在《Mathematics of Computation》44(1985)比得·蒙哥马利(Peter Montgomery)的“Modular Multiplication Without TrialDivision”一文中描述了蒙哥马利算法。6,185,596号美国专利(以下称为596)公开了一种蒙哥马利算法和装置。

将本说明书所提及和引用的所有出版物的公开内容引入作为参考。

发明内容

许多公钥密码系统都利用模指数运算(modulo exponentiation)，这种密码系统中的一项共同操作是计算信息的一个幂。例如，加密可能涉及计算明文信息的公开指数次幂，解密可能涉及计算密文信息的私有(秘密)指数次幂。“信息”一词在这里指密码算法的任何输入，这些密码算法的目的包括但不限于：加密、解密、数字签名、验证和鉴别。这里的“私有”和“秘密”指的是和公钥密码系统的私有密钥相关的信息。

一个众所周知的指数运算方法涉及用对应于指数中多个“1”那些比特的选择性乘法运算反复进行平方运算。使用这种方法或类似方法进行指数运算的设备可能不安全，这是因为在指数运算过程中，能够从外部监视这一设备(非侵入式)，用各种物理手段，例如功耗监视，来读取秘密指数。在指数运算期间进行乘法运算时，把信息选为某个特定值会例如迫使设备消耗可以检测其差别的功率，这种可检测的差别会暴露秘密指数中“1”那些比特的位置(“选定信息攻击”)。有许多众所周知的功率分析技术能够被用来从密码设备提取密钥。因此，设备易于受到建立在功率分析基础之上的选定信息攻击是一个安全危险。除了功率分析以外，还有其它非侵入式的方法能够攻击希望安全的设备，包括检测从设备发出的辐射。这些方法可以依赖于能够从外部检测的可测量的，会泄露能够从中推测出密钥的信息的任意物理现象。

已经将各种技术用于伪装或模糊这种设备的内部操作。一种众所周知的技术是进行哑操作，这种操作(例如在功耗方面或者辐射方面)会产生相似的物理效果，但其结果只是被丢弃，不影响输出。然而，尽管使用了哑操作，通过分析这种选定信息攻击，从计算的角度仍然能够识别插入的哑操作，并由此确定密钥信息。

为了挫败选定信息攻击，设备最好不直接对信息本身进行重要计算，而是针对从这一信息得到的中间值进行运算，优选通过也接收随机输入的信息的掩蔽函数。当然，这样做要求能够从结果中去掉这一掩蔽函数的影响。

上面引用的ElGamal系统可以按照以下方式加以采用：

给定：a，只有加密信息的接收方知道的密钥；x，系统的发送方要加密并且要发送的信息；以及公知元素：p，模数；a，指数函数的底；以及接收方的公钥β＝α^amodp。

发送方秘密地准备并发送y₁和y₂，其中：

y₁＝α^kmodp；其中k为随机掩蔽指数，由发送方产生。

y₂＝xβ^k modp＝xα^ak，信息x乘以接收方的公钥。

随后，接收方利用发送的信息y₁和y₂进行如下运算：