RSA密码分析中分解大整数的判定算法.pdf

第36卷 第l5期 计 算 机 工 程 2010年 8月 I1oL36 No．15 ComputerEngineering August2010 · 安全拇术 · 文章编号：l000—-3428(2o1o)l5—0l42—03 文献标识码：A 中田分类号：TP309 RSA密码分析中分解大整数的判定算法 孙克泉 (南开社区学院计算机系，天津 300100) 摘 要：RSA的安全性是依据大整数分解的困难性而设计的。在RSA的密码分析中，根据RSA公钥加密体制中的公开密钥n为2个大素 数乘积的特性，针对形如n=pq(其中，P、g为大素数)的大整数 分解，提出一种分解 ”的判定算法，并对n的素因子特征与该算法的有效 性关系进行分析。经过数学证明和相应算法设计证实，该算法的复杂度低于O logn)。 关健词：RSA密码分析；因式分解；公钥加密 ；复杂度 DetermineAlgorithm 0fLargeIntegerDecomposition 0nRSA Cryotanalysis _ 一 oq SUN Ke-quan (ComputerDepartment，NankaiCommunityCollege，Tianjin300100) [Abstract]ThesecurityofRSAisdesignedbasedonthedifficultyoflargeintegerdecomposition．IntheRSAcryptanalysis，accordingtORSA publickeyencryptioncharacteristicsthatthepublickeyHastheproductoftwolargeprimenumbers，contrarytotheformn=pq(inwhichP，qas largeprimenumbers)ofthelrageinteger7／decomposition．AdeterminealgorithmoflargeintegerdecompositiononRSAcryptanalysisisgiven．The decompositionalgorithm isprovedbymathematicalmethod，thecorrespondingalgorithm designisgiven，thecomplexiyt ofthealgorihtm ismade belowO(plogn)，primefactorchraacteristicsandtherelationshipbetweentheeffectivenessofthedecomposition，aswellasRSAsafeytimpactsrae analyzed． [Keywords]RSAcryptanalysis；factorization；public—keyencryption；complexity 1 概述 作为私钥。明文m以分组的方式被加密，其中每个分组是一 RSA算法是一种用数论构造的、被认为理论上相当成熟 个小于 ”的二进数，即分组的长度必须小于或等于lbn；实际 的公钥密码体制，并广泛地应用于密钥管理、数字签名等方 上，分组长度k满足2k ≤2 ，对于明文m和密文c，加 面。基于数论中2个大素数乘积所得整数 和选取满足一定 密和解密具有如下形式： 条件的整数e组成公开密钥(e，7／)，并选取特定私钥d组成私 c=m mod