rsa算法中快速生成大素数方法改进论文.pdfVIP

2009年6月 重庆文理学院学报 (自然科学版) Jun．，2009 第 28卷 第3期 JournalofChongqingUniversityofArtsandSciences(NaturalScienceEdition) V01．28 No．3 RSA算法 中快速生成大素数方法的改进 王 萍 ，廖芳燕 ，廖芳午 ，张树贵 (1．成都理工大学 信息管理学院，四川 成都 610059；2．成都理工大学 环境与土木工程学院，四川 成都 610059) [摘 要]根据同余理论提出一种快速试除法来更快地判断一个大整数是否能被小素数整除， 从而进一步提高RSA算法 中所需要的大素数的生成速度． [关键词]RSA；大素数；同余 [中图分类号]O156．1 [文献标识码]A [文章编号]1673—8012(2009)03—0009—03 数能否被小素数整除的时间要 比各种概率测试 1 RSA算法简介 法短得多，一般说来，这种筛选可以排除大整数 RSA算法是一种 既能用于加密又能用于数 不是素数 76％的可能性；之后再进行 5次 Miller 字签名的公钥算法 J．其原理是：选取两个大素 — Rabin检测，那么这个大数不是素数的概率就 数P和q，算出n：P·q， (n)=(P一1) ·(q 会降到 1／1000以下，这样就加快了大素数生成 一 1)，再随机选取一个正整数 e，使之满足 1e 的速度． ()，并且 gcd(西(n)，e)=1，然后计算 d， 3 对传统筛选法的改进 满足d·e；1rood西(n)．其中，n和e为公钥，d为 私钥．根据 RSA算法，设要加密的明文为m，C为 以上提到的用小素数试除法是一种有效的 密文．加密过程为 ：C m (modn)．解密过程 排除合数的方法．那么怎样可以更快地判断一个 为 ：m=c(rood )．由此可见 ，RSA算法的安全 随机大整数是否能被 100以内的小素数除尽呢? 性是基于大数 n的分解难度 J．目前，因子分解 根据同余的理论，我们可以将大整数 “分块”相 速 度 最 快 的 方 法，其 时 间 复 杂 度 为： 加再除以小素数 ，若能除尽则该大整数肯定能被 exp(sqrt(In(n)lnln(n)))．随着 n长度 的增加 ， 除尽． 分解因子所需时间成指数增加．现在．129位十进 3．1 快速试除法 制数的模数是能分解 的临界数．因此，n应该大 于这个数．可见，RSA的安全性取决于大整数的 我们知道 ，判定一个整数能否被 3整除，可 长度． 以把每一位上的数字相加再除以3，如果 能 除 尽则该数能被 3整 除，这 比直接用这个数去 2 生成大素数的方法 除3要快得多．其原理是：10—1(rood3)，因 由于素数在正整数序列中分布不规则，无法 此 10 =1(mod3)J．任意一个十进制的整数 用公式直接计算出一个指定长度 的大素数，所 以 (aka …口la0)1o可表示如下 ： 当前采用的方法是随机产生一个大整数 ，再对其 (aka¨…ala0)lo 做素性检测．常见的素性检测法有 Miller—Rabin = a ·10 +a一 l ·10一 + … +al·10 +a0 E a + a 检测 J、So