摘 要

随着嵌入式系统的普及和发展，这种专为某种功能而设计的系统越来越受到人们的亲睐，无论是远程通信，家庭设备，快速计算，都离不开特定的嵌入式系统，但是受众广的同时，该类系统或是软件也面临越来越多的安全威胁，并且嵌入式系统在安全性设计上工作更加复杂，需要考虑的因素更多，面对资源受限的嵌入式环境，如何权衡存储，效率，成本以及功耗是嵌入式保密性设计准则的关键。

目前嵌入式环境下使用的程序存储加密算法还主要是对称加密算法，这类算法非常适合资源受限的嵌入式环境，不过受限于自身机制的局限，对称加密算法密钥泄露风险大，无法实现数字签名的功能，即无法保证信息的完整性和不可否认性，因此本文考虑实现公钥加密算法，并针对公钥加密效率慢这一最大局限，提出相应改进算法。

目前公钥加密中的优化算法有很多，例如，有学者提出从右到左的二进制方法计算标量乘以减少ECC中标量乘占用较多计算开销的情况，随后有学者在二进制的基础上提出了NAF标量表示法，对称三进制的标量表示法等等，也有学者基于ECC算法和AES算法提出了混合加密算法，兼顾了算法的安全性和有效性，具有重大意义。

蒙哥马利乘是一种专门用于简化大数取模运算的算法，主要基于中国剩余定理，欧拉函数等数论中有关取模的数学定理，通过预处理等运算，规避了取模运算中运算开销较大的除法运算，而ECC加密算法和RSA加密算法都用到了大量的大数取模运算，因此，本文通过植入蒙哥马利乘实现了改进的ECC和RSA加密算法。

本文主要通过对比分析得到最优的公钥加密算法设计，对于ECC加密算法而言，植入蒙哥马利乘算法后并没有带来明显的效率提高，反而因为多次预处理过程，致使代码循环结构体更加复杂，移植性更差， 而对于RSA加密算法而言，植入蒙哥马利乘算法后可以将加密时间提升数百倍，主要是由于对于RSA加密算法而言，蒙哥马利乘预处理过程只要执行一次即可，改进后的RSA加密算法加密效率甚至高于ECC算法，不过只是针对加密时间而言，如果考虑到密钥生成时间，RSA算法还是稍有欠缺，因此，改进后的RSA加密算法还是只能适合在存储空间大，加密数据短的场合下使用。

关键词:ECC加密，RSA加密，蒙哥马利乘，嵌入式系统 With the popularity and development of embedded systems, this kind of system designed for a certain function is more and more popular.A specific embedded system is necessacy for remote communication, home equipment, and fast computing. However, while the audience is wide, such systems or software are also facing more and more security threats, and embedded systems are more complex in security design, because more factors need to be considered. In the face of resource-restricted embedding Environment, how to balance storage, efficiency, cost and power consumption is the key to embedded privacy design guidelines.

At present, the program storage encryption algorithms used in the embedded environment are mainly symmetric encryption algorithms. These algorithms are very suitable for resource-constrained embedded environments, but due to the limitations of their own mechanisms, the risk of key leakage of symmetric encryption algorithms is high and cannot realize the function of digital signature, that is, the integrity and non-repudiation of information cannot be guaranteed, so this paper considers the implementation of public key encryption algorithm, and proposes corresponding improvement algorithm for the biggest limitation of slow public key encryption efficiency.

At present, there are many optimization algorithms in public key encryption. For example, some scholars have proposed a right-to-left binary method to calculate scalar multiplications to reduce the ECC scalar multiplications that take up more computing overhead. Later, some scholars proposed on the basis of binary NAF scalar representation, symmetric ternary scalar representation, etc., some scholars have proposed a hybrid encryption algorithm based on ECC algorithm and AES algorithm, taking into account the security and effectiveness of the algorithm.

Montgomery multiplication is an algorithm specially used to simplify the modulus operation of large numbers. It is mainly based on the mathematical theorem about modulus in the number theory such as Chinese residual theorem, Euler function, etc. Through preprocessing and other operations, the operation overhead in modulus operation is avoided.The ECC encryption algorithm and RSA encryption algorithm use a large number of modulus modulo operations, therefore, this paper improved ECC and RSA encryption algorithms by implanting Montgomery multiplication.

This article mainly obtains the optimal public key encryption algorithm design criteria through comparative analysis. For the ECC encryption algorithm, the Montgomery multiplication algorithm does not bring significant efficiency improvement. Instead, because of multiple preprocessing processes, the code loop structure is more complex and the portability is worse. For the RSA encryption algorithm, the Montgomery multiplication algorithm can increase the encryption time by hundreds of times, mainly because for the RSA encryption algorithm, the Montgomery multiplication preprocessing process only needs to be performed once That is, the improved RSA encryption algorithm is even more efficient than the ECC algorithm, but only for the encryption time. If the key generation time is considered, the RSA algorithm is still slightly lacking. Therefore, the improved RSA encryption algorithm is still only can be used in the occasions with large storage space and short encrypted data.

Keywords: ECC encryption, RSA encryption, Montgomery multiplication, embedded system

目 录

中文摘要 Ⅰ

Abstract Ⅱ

第1章 绪论 1

1.1 课题背景及来源 1

1.2 研究现状 2

1.3 课题研究目的 2

1.4 研究内容与思路 2

第2章 加密算法在嵌入式系统中的应用 4

2.1 加密算法的应用 4

2.2 嵌入式软件保密程序中加密算法的缺陷 5

2.2.1 对称密钥体制优劣 5

2.2.2 嵌入式保密程序中ECC加密算法缺陷 5

2.2.3 嵌入式保密程序中RSA加密算法缺陷 7

2.3 公钥加密算法改进方法 7

2.4 本章小结 9

第3章 软件实现 10

3.1 大数库 10

3.2 ECC加密算法实现 10

3.2.1 曲线实现 10

3.2.2 加密算法实现 11

3.2.3 文件存取与编码 11

3.3 RSA加密算法实现 12

3.4 蒙哥马利乘算法实现 13

3.5 本章小结 15

第4章 加密测试及评估 16

4.1 加密算法性能预估 16

4.2 加密算法流程测试 16

4.3 加密算法性能对比测试 18

4.3.1 ECC加密算法及其改进算法对比分析 18

4.3.2 RSA加密算法及其改进算法对比分析 20

4.3.3 综合比较 21

4.4 本章小结 25

第5章 总结 23

致 谢 24

参考文献 25

1. 绪论

1.1 课题研究背景及目的

随着嵌入式系统的普及和发展，这种专为某种功能而设计的系统越来越受到人们的亲睐，但是受众广的同时，该类系统或是软件也面临越来越多的安全威胁。过去，人们往往采用加密算法来确保互联网领域的信息安全，而在嵌入式环境下，安全问题更加复杂，嵌入式设备的开放性和资源受限性，要求在考虑安全性的前提下，兼顾存储，加密效率，成本等问题。

一般认为，安全的数据传输应该要满足以下3个基本的特性：(1)数据机密性:指信息保密，只有授权者有权接收信息。(2)完整性：指信息的一致性，即传输的信息无法非法更改的特性，还要保证信息处理方法的正确性。(3)数据不可否认性:指能保证用户无法事后否认曾经对信息进行的生成、签发、接受等行为。为了保护嵌入式信息安全传输，人们开始对密码学这一学科越来越重视，如何有效的运用密码学知识解决数据加解密问题，也开始成为信息安全研究的重点。

加密技术主要分为两类：一类是对称密码体制又称单密钥体制；一类是非对称密码体制也称公钥密码体制。目前，在嵌入式环境下主要使用的还都是对称密钥体制，这类密钥体制原理简单，加密时间短，占用存储少，算法成熟度高，可移植性强，但是这类算法受限于自身机制局限，密钥管理风险大，无法实现数字签名等功能，即只能保证数据机密性而无法确保完整性和不可否认性。