一种强素数生成算法.pdfVIP

维普资讯 一 ■塑 竺堕竺 aNew Meth0dofStrong PrimeNumbersGenerator 杨淑群 ’ Yang Shuqun (1．东华理工学院计算机通信系．抚州 344000；2．福建师范大学软件学院，福州 350007) (1．Facultyof~athematicsandInformationScience，EastChina InstituteofTechnology．Fuzhou 344000 2．Software Institue．FujianNormalUniversity，Fuzhou 350007) 摘 要：RSA岱钥加密体制由美国麻省理工学院干 1978年提出，它是第一个成熟的、最为成功曲公开密码体制．它的 原理和安全性是基于数论中曲Euler定理和计算复杂性理论中的论断：求两个大素数的乘积是容品计算的．但要把两个大素 数的乘积分解成素因子则是非常困难的。随着密码体系分析的发展．RSA需要具有更强性质的素数(强素数) 本文提出了一种 简单的强素数生成算法．同时夼绍了一种伪随机微生成嚣和 Rabin—Miller概卓素性检测算法。 关键词：R ‘强素数：概率索性检测：伪随机数生成嚣 中圈分类号：TP3l1．1 文献标识码 ：A 文章鳙号：l671—4792一(2006)1l一0094-02 abstract：．TheRSA cryptoRnalysisWaSadvancedbyRivest。ShamirandAdleman ITjin 1978．Atpresent，jt iSthe most testing and successful0peniT1g cryptoanalysis．Its princLple and securit?are based on the ~0nclusion 0f the Euler theory andcomputing c~ plexity theory．It is easy to getthe product of twobig primes．but extremely difficu1t to get the prime factors of the product of two big primes．Sinee the developlng of the RSA cryptoanalysis．we nOW need strongerprime numbers thanevet．In this paper，we have presented a simplemethod for thegenerationof stronRprimenumbers．Wealso introduceakindofpseudorandom n【IlIlber generatorcPP~＼GJ andaprobabillsticprimalitytestalgorithm (Rabin-)lillertest)． Zevwo~ ：Rs^：StrongPrimeNumber：ProbabilisticPrimalityTest；PseudoRandomxmberGenerator 0 引售 。@ l也必须有一个很大的素数因子； RSA密码体系的流程如下： 回rl也必须有一个大的素数园子。 sl：找出两个大素数：p和q： 本文将给出一种简单的随机强素数 (pseudo strong s2：计算n--p’q．z=巾n()：(p-1)’(q-1)； primenumber)生成算法。 s3：选取e，使得 (e，z)=】。q，n #为公开密钥： 1 算法步骤 ． s4：计算d．使得de；1ro(odz)，d，n)作为私有密钥。 算祛步骤如下： 对于明文块P和密文块C，加解密的过程如