嵌入式系统中RSA密钥生成的高效实现

Efficient implementation of RSA key generation in embedded system

为了在嵌入式系统中高效实现RSA密钥生成,对密钥生成中涉及的算法做了详细分析。在素性测试之前引入改进的试除法,将大部分奇合数去掉,减少了调用素性测试程序的次数,提高了素数生成的速度。为了更有效地实现最大公约数算法,对Euclid算法和Binary算法进行了时间和空间上的分析比较,最终采用了Euclid算法。最后,根据嵌入式系统的特点对算法进行了优化,有效提高了RSA密钥生成的效率。

In order to efficiently implement RSA key generation algorithm in embedded system, algorithms involved in key generation are analyzed in detail. Improved trial division algorithm, which detects most of odd composite numbers, is used before primality tests, highly decreasing the frequency of using primality test program and increasing the speed of prime number generation. To implement greatest common divisor algorithm more efficiently, Euclid algorithm and Binary algorithm are analyzed and compared regarding space and speed, with Euclid algorithm finally adopted. At last, algorithms are optimized based on characteristics of embedded system, which effectively improved the efficiency of RSA key generation.