针对离散私钥比特泄漏的RSA格攻击方法

第４０卷　第３期　Ｖ＿０１．４０　ＮＯ．３　计算机工程　２０１４年３月　Ｍａｒｃｈ　２０１４　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　・安全技术・　文章鳙号：１０００—３４２８（２０１４）０３—０１６３．０４　文献标识码：Ａ　中田分类号：ＴＮ９１８　针对离散私钥比特泄漏的ＲＳＡ格攻击方法　刘向辉　，韩文报　，王政　，权建校　（１．解放军信息工程大学四院，郑州４５０００２；２．数学工程与先进计算国家重点实验室，郑州４５０００２；　３．江南计算技术研究所，江苏无锡２１４０８３）　摘要：ＲＳＡ算法是目前应用最广泛的公钥密码体制之一，而格攻击是针对ＲＳＡ体制的一类重要攻击方法。为此，将ＲＳＡ算法　的部分私钥泄漏问题转化为多变元线性同余方程的求解问题，基于同余方程构造出特定的格，利用ＬＬＬ格基约化算法进行约化，　从而以一定的概率求得同余方程的小根。以上述多变元线性同余方程的小根求解技术为基础，提出一种针对离散私钥比特泄漏的　ＲＳＡ格攻击方法。在该方法下，如果ＲＳＡ算法的公钥参数Ｐ＝　≤Ｎ１　，并且私钥ｄ的未知部分Ｎ￣＜Ｎ１　，则能以高概率恢复出　ＲＳＡ算法的私钥ｄ。通过ＮＴＬ包对长度为１　０２４　ｂｉｔ的大整数进行实验，结果验证了该攻击方法的有效性。　关健词：ＲＳＡ算法；格攻击；离散私钥比特泄漏；线性同余方程；小根；格基约化算法　ＲＳＡ　Ｌａｔｔｉｃｅ　Ａｔｔａｃｋ　Ｍｅｔｈｏｄ　ｆｏｒ　Ｄｉｓｃｒｅｔｅ　Ｐｒｉｖａｔｅ　Ｋｅｙ　Ｂｉｔ　Ｌｅａｋａｇｅ　ＬＩＵ　Ｘｉａｎｇ．ｈｕｉｌ＇２，ＨＡＮ、ｖｅｎ．ｂａｏ　，．，ｗＡＮＧ　Ｚｈｅｎｇ　’－，ＱＵＡＮ　Ｊｉａｎ－ｘｉａｏ　（１．Ｔｈｅ　Ｆｏｕ￣ｈ　Ｉｎｓｔｉｔｕｔｅ，ＰＬＡ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｚｈｅｎｇｚｈｏｕ　４５０００２，Ｃｈｉｎａ；　２．Ｓｔａｔｅ　Ｋｅｙ　Ｌａｂｏｒａｔｏｒｙ　ｏｆ　Ｍａｔｈｅｍａｔｉｃａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｄｖａｎｃｅｄ　Ｃｏｍｐｕｔｉｎｇ，Ｚｈｅｎｇｚｈｏｕ　４５０００２，Ｃｈｉｎａ；　３．Ｊｉａｎｇｎａｎ　Ｉｎｓｔｉｔｕｔｅ　ｏｆＣｏｍｐｕｔｉｎｇ　Ｔｅｃｈｎｏｌｏｇｙ，Ｗｕｘｉ　２１４０８３，Ｃｈｉｎａ）　［Ａｂｓｔｒａｃｔｌ　ＲＳＡ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｏｎｅ　ｏｆｔｈｅ　ｍｏｓｔ　ｗｉｄｅｌｙ　ｕｓｅｄ　ｐｕｂｌｉｃ　ｋｅｙ　ｃｙｐｔｒｏｓｙｓｔｅｍｓ　ａｔ　ｐｒｅｓｅｎｔ　ａｎｄ　ｌａｔｔｉｃｅ　ａｔａｃｋｓ　ｐｌａｙ　ａｎ　ｉｍｐｏｒｔａｎｔ　ｒｏｌｅ　ｆｏｒ　ｔｈｅ　ａｎａｌｙｓｉｓ　ｏｆ　ＲＳＡ　ｓｙｓｔｅｍ．Ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆ　ｐａｒｔｉａｌ　ｄｉｓｃｒｅｔｅ　ｐｒｉｖａｔｅ　ｋｅｙ　ｂｉｔ　ｌｅａｋａｇｅ　ｉｓ　ｔｒａｎｓｆｏｒｍｅｄ　ｉｎｔｏ　ｔｈｅ　ｓｏｌｕｔｉｏｎ　ｏｆ　ｍｕｌｔｉｖａｒｉａｔｅ　ｌｉｎｅａｒ　ｃｏｎｇｒｕｅｎｃｅ　ｅｑｕａｔｉｏｎｓ　ａｎｄ　ａ　ｓｐｅｃｉａｌ　ｌａｔｔｉｃｅ　ｉｓ　ｃｏｎｓｔｒｕｃｔｅｄ．Ａｎｄ　ｔｈｅｎ　ｂｙ　ｔｈｅ　ｌａｔｔｉｃｅ　ｒｅｄｕｃｔｉｏｎ　ａｌｇｏｒｉｔｈｍｓ　ｓｕｃｈ　ａｓ　ＬＬＬ　ａｌｇｏｒｉｔｈｍ，ｔｈｅ　ｓｍａｌｌ　ｒｏｏｔｓ　ｏｆ　ｍｕｌｔｉｖａｒｉａｔｅ　ｌｉｎｅａｒ　ｃｏｎｇｒｕｅｎｃｅ　ｅｑｕａｔｉｏｎｓ　ｃａｎ　ｂｅ　ｏｂｔａｉｎｅｄ　ｗｉｔｈ　ａ　ｈｉｇｈ　ｐｒｏｂａｂｉｌｉｔｙ．Ｂａｓｅｄ　ｏｎ　ｔｈｅ　ａｂｏｖｅ　ｔｅｃｈｎｏｌｏｇｙ，ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｓ　ａ　ｌａｔｔｉｃｅ　ａｔｔａｃｋ　ｍｅｔｈｏｄ　ｏｎ　ＲＳＡ　ｆｏｒ　ｄｉｓｃｒｅｔｅ　ｐｒｉｖａｔｅ　ｋｅｙ　ｂｉｔ　ｌｅａｋａｇｅ．Ｗｉｔｈ　ｔｈｉｓ　ｍｅｔｈｏｄ．ｉｆ　ｔｈｅ　ｐｕｂｌｉｃ　ｐａｒａｍｅｔｅｒ　ｓａｔｉｓｆｉｅｓ　ｅ＝　’≤　Ｎ、　ａｎｄ　ｔｈｅ　ｕｎｋｎｏｗｎ　ｐａｒｔ　ｏｆｐｒｉｖａｔｅ　ｋｅｙ　ｄ　ｓａｔｉｓｆｉｅｓ／Ｗ￣＜Ｎ１　～．ｉｔ　ｃａｎ　ｒｅｃｏｖｅｒ　ｔｈｅ　ｐｒｉｖａｔｅ　ｋｅｙ　ｄｗｉｔｈ　ａ　ｈｉｇｈ　ｐｒｏｂａｂｉｌｉｔｙ．Ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔ　ｏｎ　１　０２４　ｂｉｔ　ｎｕｍｂｅｒ　ｉｓ　ｇｉｖｅｎ　ｗｉｔｈ　ＮＴＬ　ｐａｃｋａｇｅ　ａｎｄ　ｔｈｅ　ｒｅｓｕｌｔｓ　ｖｅｒｉｆｙ　ｔｈｅ　ａｖａｉｌａｂｉｌｉｔｙ　ｏｆｔｈｅ　ａｔｔａｃｋ　ｍｅｔｈｏｄ．　［Ｋｅｙ　ｗｏｒｄｓｉ　ＲＳＡ　ａｌｇｏｒｉｔｈｍ；ｌａｔｔｉｃｅ　ａｔｔａｃｋ；ｄｉｓｃｒｅｔｅ　ｐｒｉｖａｔｅ　ｋｅｙ　ｂｉｔ　ｌｅａｋａｇｅ；ｌｉｎｅａｒ　ｃｏｎｇｒｕｅｎｃｅ　ｅｑｕａｔｉｏｎ；ｓｍａｌｌ　ｒｏｏｔ；ｌａｔｔｉｃｅ　ｂａｓｅ　ｒｅｄｕｃｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ＤｏＩ：１０．３９６９￣．ｉｓｓｎ．１０００．３４２８．２０１４．０３．０３３　１概述　自１　９７６年公钥密码的思想提出以来，各种公钥密码体　制不断涌现，但公认安全的且应用广泛的却并不多，其中　筛法，它是一个亚指数时间算法，在当前的计算能力下无　法对实际使用的ＲＳＡ模数进行分解。也就是说，在不借助　其他条件下直接通过大数分解对ＲＳＡ体制进行攻击是困　难的。　较著名的是ＲＳＡ公钥密码体制、Ｅ１Ｇａｍａｌ公钥密码体制和　椭圆曲线公钥密码体制。而ＲＳＡ公钥密码体制由于具有简　单易用、明密文长度相同等优点，在各种秘密通信中得到　广泛应用，一直是公钥密码学研究的热点ｕ　Ｊ。一般来讲，公　钥密码体制往往利用数学中已经得到证明的难题或公认的　难题来设计方案，ＲＳＡ算法就是建立在大数分解问题上的。　目前，针对大数分解问题最好的通用攻击算法是一般数域　然而，在实际使用过程中可能会泄漏ＲＳＡ体制的部分　信息，例如泄漏私钥Ｐ或者ｄ的若干比特信息。同时，由　于旁道攻击等手段的发展，攻击者往往能够获得部分密钥　信息。如何利用这些已知信息对ＲＳＡ体制进行攻击成为密　码学的一个重要研究课题。文献［２－３】提出利用ＬＬＬ算法求　解整系数同余方程及多项式方程小根的方法，此后该方法　被广泛应用于ＲＳＡ算法的私钥泄漏攻击中，例如，在泄漏　基金项目：国家自然科学基金资助项目（６１００３２９１）；数学工程与先进计算国家重点实验室开放基金资助项目（２０１３Ａ０３）。　作者简介：刘向辉（１９８４一），男，博士研究生，主研方向：密码学，信息安全；韩文报，教授、博士、博士生导师；王政，副教授、　博士；权建校，助理研究员、硕士。　收稿日期：２０１３—０３—０７　修回日期：２０１３・０４－０７　Ｅ—ｍａｉｌ：ｌｘｈｋｚ２００２＠１６３．ｔｏｍ　１６４　计算机工程　２０１４年３月１５日　私钥ｄ的低ｎ／４比特，同时加密指数较小的条件下ＲＳＡ的　私钥恢复　；在加密指数较大情况下的ＲＳＡ部分私钥泄漏　攻击等　；私钥指数Ｐ的连续比特泄漏攻击等【６ｊ。　早期的ＲＳＡ私钥泄漏攻击都建立在文献【２—３】求解多变　元模方程或者求解多变元多项式方程小根的基础上，主要　集中在私钥ｄ的高位连续比特或者低位连续比特泄漏的情　形。在实际环境中，攻击者获得的部分私钥信息通常是不　连续的，特别是旁道攻击　的存在使得ＲＳＡ体制离散比特　私钥泄露攻击也显得更有意义。文献［８］通过构造多变元线　性模方程并利用格基约化算法进行求解，提出针对泄漏私　钥Ｐ部分离散比特的攻击方法，在泄漏私钥Ｐ的７０％比特　信息的条件下该方法能够有效分解ＲＳＡ的模数。文献［９】　利用变换多项式的格构造方法给出针对私钥指数ｄ的离散　比特泄漏攻击，但该方法要求格的维数较高。　本文通过构造多变元线性模方程，并利用典型的格构　造方法，针对ＲＳＡ算法私钥ｄ部分离散比特泄漏的情况进　行分析。在公钥指数较小的条件下，如果泄漏私钥ｄ的部　分离散比特，则可以有效恢复出ＲＳＡ算法的私钥参数ｄ。　２准备知识　本节给出ＲＳＡ格攻击所用到的基础知识，包括格的基　本概念、Ｍｉｎｋｏｗｓｋｉ定理等格的基本理论以及ＬＬＬ算法等　格基约化算法，具体细节可参考文献［１　０］。　定义１设　，　，…，ｂｍ∈　为一组线性无关的向量，其　中，　为实数域上的，２维向量空间；Ｉ．（ｂｌ，　，…，６　）＝　ｍ　｛Ｚ＝∑　　ｌ∈Ｚ）称为以（　，ｂ２，…，ｂｍ）为基的格，ｍ称　ｉ＝１　为格的维数。若ｍ＝ｎ，则格上称为满秩。如果Ｒ＝Ｚ，也　即格中元素取自整数环，则称其为整格。　定义２令　，　，一　为　，　，…，　进行Ｇｒａｍ－Ｓｃｈｍｉｄｔ　正交化后所得的向量，则对以（ｂｔ，ｂ２，…，６　）为基的ｍ维格　，称其行列式ｄｅｔ（Ｌ）＝１－ＩｌＩ西　为格的范数。其中，ｌ　ｌ６　Ｉｌ表　ｉ＝１　示向量６的欧氏范数，又称为向量的长度，也即若　６＝（ｂｌ，ｂ２，…，　），则ｌｌ　６ｌｌ＝（　＋　＋…＋　）”　。　显然，一个格有多组基，在解决格上相关问题时，希　望能找到一组特定的基有利于问题的解决，寻找这组基的　过程就称为格基约化，这组基就称为约化基。拥有长度较　短向量的基往往具有一些良好的性质，如何寻找具有短向　量的基一直受到人们的关注。定理１给出了格中最短向量　长度的上界。　定理１设格三　是一个满秩格，那么必然存在非零　向量＇，满足ｌ　ｌ忙√　ａｅｔ（Ｌ）“”。　Ｍｉｎｋｏｗｓｋｉ定理说明格中最短向量的长度　ｌｌ＜√　ａｅｔ（Ｌ）“”，但如何寻找格中范数最小非零向量的最短向量　问题（ｔｈｅ　Ｓｈｏｒｔｅｓｔ　Ｖｅｃｔｏｒ　Ｐｒｏｂｌｅｍ，ＳＶＰ）是格上的著名难题，　格理论研究表明它是ＮＰ问题。１９８２年，著名的ＬＬＬ算法　由Ｌｅｎｓｔｒａ等人提出　，可以在多项式时间求取格中长度为　ｌｌ＜２（　）　ｄｅｔ（Ｌ）　的近似最短向量。实际上，ＬＬＬ算　法所求得的向量长度比理论结果要好，往往能够求得需要　的短向量。　３一种离散私钥比特泄漏的ＲＳＡ格攻击方法　本节根据ＲＳＡ算法的已知信息建立多变元线性同余方　程，并利用格基约化算法对方程进行求解，从而给出离散　私钥比特泄漏的ＲＳＡ格攻击方法。　设ＲＳＡ算法的模数为Ｎ＝Ｐｑ，公钥为ｃｏ，私钥为ｄ，　则满足ｅｄ＝１ｒｏｏｄ　（Ⅳ），其中，　（Ⅳ）＝（Ｐ—１）（ｑ一　１）为　欧拉函数。假设私钥ｄ有　个比特块未知，设其值分别为　，Ｘ２，…，Ｘ　，于是得：　ｄ＝ａ１ｘ１＋Ｏ２Ｘ２＋…＋ａｎＸ＂＋ａ　＋１　其中，ａｋ＝２　表示第ｋ个未知块　在第　比特的位置。　对于ｅｄ＝１ｒｏｏｄ（ｐ（Ｎ），显然存在正整数ｋ使得Ｐ　一　１＝尼　（Ⅳ）。将ｄ代入可得：　ｅ（ａｌｘＩ＋ａ２ｘ２＋…＋ａ　ｘ　）＋ｃａ＂＋１一Ｉ＝：　ｋ（Ｎ一（ｐ＋ｑ）＋１）　将上述方程模Ⅳ可得　＋１变元的线性同余方程如下：　ｅａ１ｘ１＋ｃａ２ｘ２＋…＋ｅａｎｘｎ＋　ｋ（ｐ＋ｑ一１）＋ｅａ　＋ｌ一１＝０ｒｏｏｄＮ　将同余方程乘以ｅ　ｒｏｏｄＮ可得：　１　＋ａ２ｘ２＋…＋ａ　ｘｎ＋　ｃ－ｌｋ（ｐ＋ｑ—１）＋（　＋１一ｅ一　）＝０ｒｏｏｄＮ　方程的解为：　（Ｙ１，　２，…，　，Ｙ　＋１）＝（Ｘ１，Ｘ２，…，Ｘｎ，ｋ（ｐ＋ｑ一１））　下面对上述方程进行求解。为描述方便，令ｂｌ＝ａ　一，　：ａｎ，　＋１＝Ｃ－１　＋２＝ａｎ＋１一ｅ－　，同时，　＋１＝Ｊｉ｝（ｐ＋ｇ一１），　那么方程具有以下形式：　（Ｘｌ，Ｘ２，…，Ｘ　＋１）＝　＋ｂ２ｘ２＋。・‘＋ｂｎ＋１Ｘ　＋１＋　＋２＝０ｍｏｄＮ　对于一般的多变元线性同余方程，解的个数以及解的　结构是一个较困难的问题，但是在某些限定条件下，能够　得到上述同余方程的唯一解。定理２给出了一种求解情况，　能够在一些限定条件下完成对ＲＳＡ算法私钥ｄ的恢复。　定理２令Ⅳ是ＲＳＡ模数，私钥ｄ满足ｉＮ（Ｘｌ，　２，…，　Ｘｎ＋１）＝ｂｌｘ１＋　２＋…＋　＋１　＋ｌ＋　＋２＝０ｍｏｄＮ是线性　同余方程，其中，方程的解Ｙｌ＜Ｎ　＝　，…，　＜Ｎ　＝　，　＋　＋…＋　＝　为私钥ｄ未知的　个比特块，同时假　设８＝Ｎｐ。如果　＋　≤１／２，那么可以恢复ＲＳＡ算法的　私钥ｄ的未知部分。　证明：对于方程厂Ⅳ（　，　，…，Ｘｎ＋１）＝６ｌ　＋ｂｚｘ２＋…＋　＋１　＋１＋　＋２＝０ｍｏｄＮ，首先假设ｂｉ和Ⅳ互素，也即　第４０卷第３期　刘向辉，韩文报，王政，等：针对离散私钥比特泄漏的ＲＳＡ格攻击方法　１６５　ｇｃｄ（ｂ／，Ｎ）＝１，ｉ＝１，２，…，ｎ＋２，否则可以直接分解Ⅳ，从　而求出私钥ｄ。　由已知条件Ｙｌ＜Ⅳ　：Ｘｌ，…，　＜Ｎ　＝　，ｋ＝（ｅｄ一１）／　Ⅳ）＜Ｐ＝Ⅳ　，Ｊｔｐ＋ｑ一１￣＜３Ｎ１　可得，Ｙｎ＋１＜３　＋１。注释３定理２描述的攻击方法是一个概率算法。也就　是说，如果满足已知条件，该方法并不能保证一定可以恢　复出私钥ｄ。但实际结果表明，该方法往往能够得到方程的　解并恢复出私钥。　０　０　０　＝　对系数　＋２，引入变元　＋２满足Ｙｎ＋２≤　＋２＝１，　根据上述描述及定理２的证明，给出如下针对离散私　０　０　０　也即将ｎ＋１变元的线性同余方程当作　＋２变元方程：　（Ｘｌ，Ｘ２，…，Ｘｎ＋２）＝　ｂｌｘ１＋　２＋…＋　＋２Ｘｎ＋２：０ｍｏｄＮ　方程的解（　，　，…，　＋２）满足Ｙ／＜Ｎｚ＝　，ｉ＝１，２，…，　，Ｙｎ＋ｌ＜３Ｎ　＝Ｘｎ＋１，Ｙｎ＋２＝１。　将方程两边同乘以一　得新的线性同余方程Ｘ】＋　ｃ２ｘ２＋ｃ３ｘ￣＋…＋　２　＋２＝ＯｒｍｄＮ，对方程的解（Ｙｌ，Ｙ２，…，　＋２），必存在正整数Ｙ满足ｃ２ｙ２＋ｃ３Ｙ３＋…＋ｃ　＋２Ｙ　＋２＝　Ｙ】一ｙＮ。令　＝Ｎ／　，考虑如下矩阵生成的格三：　ＪＶ　・０　０　ｃ２　・０　０　Ｌ＝　：　：　：　●　●　●　・　＋１　０　Ｙ１Ｃｎ＋２　・０　＋２　显然，它是一个　＋２维的格，ｌ，＝（Ｙ，Ｙ２，…，　＋２）、　Ｂ＝（　１，ｒ２ｙ２，…，　＋２　＋２）是格三中的向量。由于　ｆ＝　Ｎ≤Ｎ，从而可得ｌｌ＇，ｌｌ＜４ｎ＋２Ｎ。如果向量　是格三中的短向量，那么可以通过格基约化算法将其求出，　从而得到方程的解，下面利用Ｍｉｎｋｏｗｓｋｉ定理说明Ｖ是格三　中的短向量。　易求格三的范数为：　ｄｅｔ（Ｌ　Ｎ　）：）＝ｎ兀兀　＝＋２　Ｎ　ｎｎ＋２　Ｎ：ｎ了＝　：ＮＮ棚肿ＦＩ　÷　ｉ＝１　ｉ＝１＾ｆ　ｉ＝１以ｆ　ｎ＋２，—．．———．一　．．．．．．．一　如果兀Ｘｉ≤Ｎ，那么向量ｌｌ＿ｌ，ｌ１４√　＋２Ｎ≤√，ｚ＋２　ｉ＝１　ｄｅｔ（Ｌ）“　＋２），根据Ｍｉｎｋｏｗｓｋｉ定理可知向量　是格　中的　一个短向量，利用格基约化算法可以求出。由已知条件，　≤Ⅳ　＋。　斗　＝Ⅳ　、Ｘｎ＋１＝３Ｎｆｌ“　、　＋２＝１，　ｉ＝１　＋２　省略小常数３，那么当　＋　≤１／２，可得兀Ｘｉ≤Ｎ。结　ｉ＝１　论得证。　注释１在证明过程中，省略小常数３，这是因为常数３　相对于Ⅳ非常微小。如果Ⅳ是一个１　０２４　ｂｉｔ的大整数，小　常数影响Ⅳ的指数为０．００　１　５５，而且它并不随着攻击算法　参数的改变而改变。于是为了计算方便，通常忽略这些小　常数，并且它基本不影响攻击算法的结果。　注释２格基约化算法通常采用ＬＬＬ算法，它是一个多　项式时间算法，这样能够在多项式时间内完成攻击，而且　ＬＬＬ算法往往能够得到需要的短向量。　钥比特泄漏的ＲＳＡ格攻击算法。　算法离散私钥比特泄漏的ＲＳＡ格攻击算法　输入ＲＳＡ算法的模数为Ⅳ，公钥ｅ＝Ｎ　，私钥ｄ未　＂　知比特块的界满足Ｙｌ＜　，Ｙ２＜　，…，Ｙｎ＜　，兀Ｘｉ≤　ｉ＝１　Ｎ。　ｏＩ七８≤１｜２　输出私钥ｄＥ知比特块的值Ｙｌ，Ｙ２，…，Ｙ　（１）根据式ｅｄ＝１ｍｏｄ　（Ⅳ）列出，２＋１元线性同余方程　厂Ⅳ（　，　，…，Ｘｎ＋１）：　（２）根据定理２的证明对方程进行变换并构造格三；　（３）利用ＬＬＬ算法求取格工中的短向量；　（４）对短向量进行代入计算出原始方程的解；　（５）输出私钥ｄ未知比特块的值。　假设ＲＳＡ算法的模数Ⅳ的长度为ｍ，公钥参数为　ｅ＝Ⅳ∥，根据上述算法，如果私钥ｄ的长度为（１／２一ｆ１）ｍ　比特块未知，那么可以将私钥ｄ恢复出来。在实际使用中，　通常选取Ⅳ为１　０２４　ｂｉｔ的数，ｅ＝６５　５３７，也就是说，　＝０．０１５　６　此时，如果私钥ｄ长度为０．４８３ｍ的比特块　未知，那么可以将ｄ恢复出来。相对于单块连续比特泄漏　的情形，攻击算法需要泄漏更多的信息。例如，Ｂｏｎｅｈ等人　只需要泄漏私钥ｄ的低ｍ／４比特，也即０．７５ｍ的比特块未　知，那么可以恢复出私钥ｄ。但是，本文攻击算法是基于离　散比特的私钥泄漏攻击，未知的比特信息可以在任意位置，　在实际环境中具有更强的适应性。　４实验结果与分析　本文算法能够有效恢复出离散私钥比特泄漏情形的私　钥ｄ，本节对攻击方法进行实现，给出了部分实验结果。　实验采用Ｉｎｔｅｌ　Ｃｏｒｅ２　Ｄｕｏ　ＣＰＵ　Ｅ７５００　２．９３　ＧＨｚ、２　ＧＢ　内存、Ｗｉｎｄｏｗｓ　ＸＰ操作系统、ｃ＋＋编程语言、Ｖｉｓｕａｌ　Ｓｔｕｄｉｏ　２００５编程环境。实验基本数据类型以及部分函数使用ＮＴＬ　包５．５．２版本　。　随机产生１　０２４　ｂｉｔ的大整数如下：　Ⅳ＝８９８８４６５６７４３１１５７９５３８６４６５２５９５３９４５１２３６６８０８９８８４８９４７１１５　３２８６３６７ｌ５０４０５７８８６６３３７９０２７５０４８１５６６３５４２３８６６１２０３７６８０１　０５６００５６９３９９３５６９６６７８８２９３９４８８４４０７２０８４４５３２４５０３０１４７４５７　０９２９８ｌ５１３６７４４８４６１１２５７２８０２９１２１６４９７６５３２３６１６１３６６７９３８３　４９０Ｏ７０２４３０４９３２２３８７６２３０８６９９４９１２８６６５８７６２８９６ｌ５７５９２２００　９２４５１２０８２８００３５ｌ８５４５３７７０５９５３９８９００２４０５１８４７７２３２７７３４５１　７４８５１６１３　选择公钥参数ｅ＝６５　５３７，并计算其私钥参数：　１６６　计算机工程　２０１４年３月１５日　ｄ＝－７４６７５９８ｌ３５９３７２０９２５ｌ５７１２６５７７５６７４８７２１１０１０８ｌ５３４５１４４３５　１３４５５９２８４９９２１３３２６９９７５２２２０７２３８９９５２６１９９７９３４９４５４８５３９０　９０７３８６６３６９６１７４４９８７９７４５８３６５９１０２８０２５１６７９３６１０５４０８３４７５　６５１７３４２４２２０９０６９６１５５７３３８９５８４４８６０Ｏ５３０３Ｏ３１１６２２３１２８２１４　ｌ８１９９４７９１４６３００２５０４３８１６ｌ５４０５５７０１２１１７２３７３７５８６７３８１６５３　４５１６８６８９２２３０６６９３４８７１８９５９９９２１２７８２８５７３５９０７９５５６８７２５９２　３４５６０８３３　为描述方便，以下运算选择１６进制表示。私钥参数ｄ　的１６进制表示为：　６ａ５７９５ａ８６ａ５７９５ａ８６ａ５７９５ａ８６ａ５７９５ａ８６ａ５７９５ａ８６ａ５７９５ａ８６ａ５　７９５ａ８６ａ５７９５ａ８６ａ５７９５ａ８６ａ５７９５ａ８６ａ５７９５ａ８６ａ５７９５ａ８６ａ５７９５　ａ８６ａ５７９５ａ８ｄｄａ３７４４４６１０ｅ８ｅｂｄ０ｂｄ２ｆ４２ｄ０ｂｄ２ｆ４２ｄ０ｂｄ２ｆ４２ｄ０　ｂｄ２ｆ４２ｄ０ｂｄ２ｆ４２ｄ０ｂｄ２ｆ４２ｄ０ｂｄ２ｆ４２ｄ０ｂｄ２ｆ４２ｄ０ｂｄ２ｆ４２ｄ０ｂｄ２　ｆ４２ｄＯｂｄ２ｆ４２ｄ０ｂｄ２ｆ４２ｄＯｂｄ２ｆ４２ｄ０ｂｄ２ｆ４４ｅ５ｆｃ１４ｄ４２５ｃｂ６ｅｂ４１　显然ｄ是一个１　０２４ｂｉｔ的大整数。根据定理２，如果私　钥ｄ的未知比特数小于４９０　ｂｉｔ，那么可以恢复私钥ｄ。下文　分２种情况进行实验验证。　情况１私钥ｄ单未知比特块未知。假设ｄ的第１０１比　特～第５８０比特未知，也即：　６ａ５７９５ａ８６ａ５７９５ａ８６ａ５７９５ａ８６ａ５７９５ａ８６ａ５７９５ａ８６ａ５７９５ａ８６ａ５　７９５ａ８６ａ５７９５ａ８６ａ５７９５ａ８６ａ５７９５ａ８６ａ５７９５ａ８６ａ５７９５ａ８６ａ５７９５　ａ８６ａ５７９５ａ半术　牛水冰术木木木冰木木木　丰丰木木木半半木木半半水术母水　术木木木木术水术半术　木木木木木术木木木术木卡枣木　半年木木　木木木木木木木木木　木枣半木半半　丰年　木木水木木木木丰　｝｝　料料料｝　｝　｝　ｄ０ｂｄ２ｆ４４ｅ５ｆｃ１４ｄ４２５ｃｂ６ｅ　ｂ４１　其中，　表示未知部分。那么可以建立一个双变元的方程，　然后构造３变元的格对其进行求解，运行ＬＬＬ算法恢复出　私钥ｄ的未知比特。　情况２私钥ｄ多比特块未知。选取５个比特块未知，　假设ｄ的第１０１比特～第１８０比特，第２５７比特～第３５６比　特，第４５７比特～第５５６比特，第６５７比特～第７５６比特，　第８５７比特～第９５６比特共４８０个比特信息未知，也即此时：　６ａ５７９５ａ８６ａ５７９５ａ８６　￥　料　｝　｝　５７９５ａ８６ａ５７　９５ａ８６ａ５７９５ａ８６ａ５木　木木木木木卑木丰　枣木　士　卡｝幸　幸木９５ａ８６ａ５７９５ａ　８６ａ５７９５ａ８ｄｄａ３７　｝｝｝　｝｝　｛　｝｝　｛　２ｄ０ｂｄ２ｆ４２ｄ０ｂ　ｄ２ｆ４２ｄ０ｂｄ２ｆ４２｝｝　｝　｛　｝　｝　０ｂｄ２ｆ４２ｄＯｂｄ２ｆ　４２ｄ０ｂｄ　｝｝｝￥　十料¨｝　｝｝　ｄ０ｂｄ２ｆ４４ｅ５ｆｃ１４ｄ４２５ｃｂ６ｅｂ４１　其中，　表示未知部分。那么可以建立一个６变元的方程，　然后构造７变元的格对其进行求解，运行ＬＬＬ算法恢复出　私钥ｄ的未知比特。　通过上述２个实验，本文算法能够有效恢复出ＲＳＡ算　法的私钥ｄ，并且由于算法使用的格非常小，整个攻击过程　在普通ＰＣ机上即可完成。　５结束语　随着旁道攻击等物理攻击手段的不断发展，ＲＳＡ算法　的私钥泄漏攻击越来越受到人们的重视。但是，由于离散　比特的私钥泄漏攻击列方程及解方程的困难性，目前研究　大多集中于泄漏私钥的连续比特。本文对离散私钥比特泄　漏情形的ＲＳＡ安全性进行了初步分析，利用多变元线性同　余方程的典型求解算法，给出一种针对离散私钥比特泄漏　的ＲＳＡ格攻击方法。利用该方法攻击者可以有效恢复ＲＳＡ　算法的私钥参数ｄ。另一方面，本文分析结果还可以指导　ＲＳＡ算法在使用时选取安全的参数。然而，本文结果要求　已知ＲＳＡ算法有较多的私钥比特，同时利用基本的格构造　方法，虽然构造格的维数比较低，格基约化运算部分用时　较少，但是该方法是概率性的，可能会有不成功的情形存　在。因此，如何对本文方法进行改进是下一步研究的重点。　参考文献　［１１　Ｒｉｖｅｓｔ　Ｒ，Ｓｈａｍｉｒ　Ａ，Ａｄｌｅｍａｎ　Ｌ．Ａ　Ｍｅｔｈｏｄ　ｆｏｒ　Ｏｂｔａｉｎｉｎｇ　Ｄｉｇｉｔａｌ　Ｓｉｇｎａｔｕｒｅｓ　ａｎｄ　Ｐｕｂｌｉｃ　Ｋｅｙ　Ｃｒｙｐｔｏｓｙｓｔｅｍｓ［Ｊ］，　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　ｏｆｔｈｅ　ＡＣＭ，１９７８，２１（２）：１２０—１２６．　［２］Ｃｏｐｐｅｒｓｍｉｔｈ　Ｄ．Ｆｉｎｄｉｎｇ　ａ　Ｓｍａｌｌ　Ｒｏｏｔ　ｏｆ　ａ　Ｕｎｉｖａｒｉａｔｅ　Ｍｏｄｕｌａｒ　Ｅｑｕａｔｉｏｎ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ＥＵＲＯＣＲＹＰＴ’９６．　Ｂｅｒｌｉｎ，　Ｇｅｒｍａｎｙ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，１９９６：１５５—１６５．　［３］Ｃｏｐｐｅｒｓｍｉｔｈ　Ｄ．Ｆｉｎｄｉｎｇ　ａ　Ｓｍａｌｌ　Ｒｏｏｔ　ｏｆ　ａ　Ｂｉｖａｒｉａｔｅ　Ｉｎｔｅｇｅｒ　Ｅｑｕａｔｉｏｎ　Ｆａｃｔｏｒｉｎｇ　ｗｉｔｈ　Ｈｉｇｈ　Ｂｉｔｓ　Ｋｎｏｗｎ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ＥＵＲＯＣＲＹＰＴ’９６．Ｂｅｒｌｉｎ，Ｇｅｒｍａｎｙ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，１９９６：　１７８—１８９．　［４］　Ｂｌｏｍｅｒ　Ｊ，Ｍａｙ　Ａ．Ｎｅｗ　Ｐａｒｔｉａｌ　Ｋｅｙ　Ｅｘｐｏｓｕｒｅ　ＡＲａｃｋｓ　ｏｎ　ＲＳＡ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ＣＲＹＰＴＯ’０３．Ｂｅｒｌｉｎ，Ｇｅｒｍａｎｙ：　Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，２００３：２７—４３．　［５］Ｅｒｎｓｔ　Ｍ，Ｊｏｃｈｅｍｓｚ　Ｅ，Ｍａｙ　Ａ．Ｐａｒｔｉａｌ　Ｋｅｙ　Ｅｘｐｏｓｕｒｅ　Ａｔｔａｃｋｓ　ｏｎ　ＲＳＡ　ｕｐ　ｔｏ　Ｆｕｌｌ　Ｓｉｚｅ　Ｅｘｐｏｎｅｎｔｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ＥＵＲＯＣＲＹＰＴ’０５．Ｂｅｒｌｉｎ，Ｇｅｒｍａｎｙ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，２００５：　３７１．３８６．　［６］Ｓａｎｔａｎｕ　Ｓ．Ｓｏｍｅ　Ｒｅｓｕｌｔｓ　ｏｎ　Ｃｒｙｐｔａｎａｌｙｓｉｓ　ｏｆ　ＲＳＡ　ａｎｄ　Ｆａｃ—　ｔｏｒｉｚａｔｉｏｎ［Ｄ］．Ｋｏｌｋａｔａ，Ｉｎｄｉａｎ：Ｉｎｄｉａｎ　Ｓｔａｔｉｓｔｉｃａｌ　Ｉｎｓｔｉｔｕｔｅ，　２０１１．　［７］陈财森，王韬，郑嫒媛，等．ＲＳＡ公钥密码算法的计时攻　击与防御【ＪＪ．计算机工程，２００９，３５（２）：１２３—１２５．　［８］Ｈｅｒｒｍａｎ　Ｍ．Ｓｏｌｖｉｎｇ　Ｌｉｎｅａｒ　Ｅｑｕａｔｉｏｎｓ　Ｍｏｄｕｌｏ　Ｄｉｖｉｓｏｒｓ：Ｏｎ　Ｆａｃｔｏｒｉｎｇ　Ｇｉｖｅｎ　Ａｎｙ　Ｂｉｔｓ【Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆＡＳＩＡＣＲＹＰＴ’０８　Ｂｅｒｌｉｎ，Ｇｅｒｍａｎｙ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，２００８：４０６—４２４．　［９］刘向辉，韩文报，孙杰．基于离散比特的ＲＳＡ私钥泄漏　攻击［ＪＪ．信息工程大学学报，２０１２，１３（４）：３８５—３８８．　［１　０］Ｎｇｕｙｅｎ　Ｐ　Ｑ，Ｖａｌｌｅ　Ｂ．Ｔｈｅ　ＬＬＬ　Ａｌｇｏｒｉｔｈｍ：Ｓｕｒｖｅｙ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ［Ｍ］．Ｂｅｒｌｉｎ，Ｇｅｒｍａｎｙ：Ｓｐｒｉｎｇｅｒ　Ｐｕｂｌｉｓｈｉｎｇ　Ｃｏｍｐａｎｙ，２００９．　［１１］Ｌｅｎｓｔｒａ　Ａ　Ｋ，Ｌｅｎｓｔｒａ　Ｈ　ｗｊ　Ｌｏｖａｓｚ　Ｌ．Ｆａｃｔｏｒｉｎｇ　Ｐｏｌｙｎｏｍｉａｌｓ　ｗｉｔｈ　Ｒａｔｉｏｎａｌ　Ｃｏｅｉｆｃｉｅｎｔｓ［Ｊ］．Ｍａｔｈｅｍａｔｉｃｈｅ　Ａｎｎａｌｅｎ，１９８２，　２６１（４）：５１５—５３４．　［１２］Ｓｈｏｕｐ　Ｖ　Ｎｕｍｂｅｒ　Ｔｈｅｏｒｙ　Ｌｉｂｒａｒｙ（ＮＴＬ）ｆｏｒ　Ｃ＋＋［ＥＢ／ＯＬ］．　（２０１０—０５—１６）．ｈｔｔｐ：／／ｗｗｗ．ｓｈｏｕｐ．ｎｅｔ／ｎｔｌ／．　编辑陆燕菲