据加密算法与大素数的运算

【摘 要】大素数的生成运算是数据加密算法的关键。文章从加密算法的原理以及素数的生成和证明出发，对加密算法与大素数的数据结构和实现进行了阐述，并为解决大素数的运算问题提供了几种方法。

【关键词】加密算法；大素数；运算

前言：在现代信息社会中，数据加密的技术是防止信息被假冒、伪造和修改的重要手段，能够保证信息的完整、准确和安全。随着信息技术的深入发展，越来越多的数据加密算法应运而生，例如其中的RSA密码算法作为一种公认的安全加密算法，广泛的流行应用到诸多领域，其安全性来源于对数论中的大素数的运算和分解，同时大素数的运算研究对加密算法的发展有着重要的作用。

一、加密算法与大素数的关系

在众多的加密算法中，RSA公钥密码算法是目前最为流行的一种算法，广泛应用于各种信息领域，1977年由罗纳德·李维斯特、阿迪·萨莫尔和伦纳德·阿德曼一起提出了RSA加密算法，RSA就是以他们名字的开头字母命名的[1]。

选取两个大素数p和q，需要算出m=pq，φ（m）=（p-1）（q-1），选取一个正整数e，满足（e，φ（m））=1，1

针对大数的因子分解，密钥长度与分解次数紧密相关，分解所需要的时间随密钥长度的增加而增加，加密强度会更高，密码破解也就越来越难，如果m的长度是50位（十进制），尝试的次数大约是1.4×1010次，如果m的长度为100位的话，则需要尝试的次数是2.3×1015次。目前，如果m的长度为200位的话，需要尝试的次数则为2.3×1025次，如果使用一台1秒钟能进行1亿次因子分解的高速计算机来做这些工作的话，需要的时间分别是2.3分钟、270天、3800000年，由此可见，为了使RSA加密算法中得出安全可靠的数据，要解决的首要问题就是要生成满足长度要求的两个大素数——p和q。

二、大素数的生成与证明

正整数序列中素数的分布不规则，所以一个指定长度的大素数是无法用公式直接计算出来的，随机选择的大整数是否是素数也同样无法用公式直接证明出来。如果想通过计算并存储一个全面的素数表，以备日后所需的话，是不现实的，而且耗费也十分巨大，且p和q的安全也无法得到保障。

当前采用的方法为：任意选择一个大整数，然后对其做素数性的检测，要检查一个正整数N是否是素数的话，可以“试除法”，用小等于的所有素数去试除N，如果无法整除，N就是素数，在目前计算机运算水平的基础上，这种方法的运算是无法大素数进行正确判断的。当前对一个大整数进行素数检验的方法法有两种，分别是确定性素数法和概率测试法。

一个数n可以通过确定性素数法的检验方法能够准确地验证出是否为素数，且准确验证一个大整数是否素数，目前已有很多方法能够得出结论，比如， Demytko提出的定理，通过16bit的素数，导出的32bit的素数为，通过又能够导出64bit的素数，以此类推，但是由于构成素数容易产生一定的规律性，怎样能够得到适于加密体系用的素数还没有得到解决。

一般来说判定一个大整数是否为素数有一定的困难，但是否定其是素数则比较容易，这里有一个简便的运算方法能够淘汰大量的合数，它是通过利用数论理论产生的一种算法，针对一个给定的大整数n，每次完成一次检测，就给出一个yes，n是素数的概率是1/2甚至更高，或是no：n，则一定不是素数。当n通过了t次检测，则n为非素数的概率为，n是素数的概率为1-，如果t足够大，比如：t为100，那么此时n是素数几乎可以认定出来。如果概率验证法得出的素数是合数（尽管概率很小），也不会产生太大的问题，当这种情况出现时，加密体制将会显示异常，可以马上发现问题。这里针对基于加密算法下大素数的运算方法可采用如下几种方法：

（一）Lehman计算方法

Lehman是一种简单的检测大素数的方法，对一个小于x大于1的任意整数a，如果和1或者-1模x同余的话，那么可以确定x不是素数，否则x不是素数的概率则要大于或等于1/2，运算步骤为：选择一个小于x的随机整数a，计算modx，如果（modx）不等于1或者-1（modx），那么x一定不是素数；如果（modx）等于1或者-1（modx），那么x为非素数的可能性会超过50%。当x通过了t次测验，那么x为非素数的概率依然是。

（二）Miller-Rabin计算方法

令x=2bm+1，b，m是奇数，任选一个正整数，检测：

当a满足以上两个条件，则x一定是合数，通过理论证明得出：如果x通过检测，那么x为非素数的概率一定1/4，当x通过了t次检验，则x是非素数的概率依然是。

结论：

综上所述，文章从加密算法的原理以及素数的生成和证明出发，对加密算法与大素数的数据结构和实现进行了阐述，并为解决大素数的运算问题提供了几种方法。为了方便用户使用和操作，可将大素数的基本运算整理成相应的模块，这种方法对于信息安全、完整有着重要的意义。

参考文献：

[1]吴明航.DES和RSA混合加密算法的研究[D].哈尔滨：哈尔滨工业大学，2013.

[2]谭祖刚.改进的基于有限域Chebyshev多项式和RSA的公钥密码算法[D].长沙：中南大学，2013.

[3]杨博.RSA加密算法的ASIC实现[D].济南：山东大学，2012.

[4]魏瑞良.计算机网络通信安全中数据加密技术的研究与应用[D].北京：中国地质大学（北京），2013.