鸿蒙源码分析（二十）

叁歲伎倆 2022-09-04 00:46 199阅读 0赞

# 鸿蒙安全模块当中的RSA加密算法 #

## 一、算法简介 ##

RSA公开密钥密码体制是一种使用不同的加密密钥与解密密钥，“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制 。  
在公开密钥密码体制中，加密密钥（即公开密钥）PK是公开信息，而解密密钥（即秘密密钥）SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然解密密钥SK是由公开密钥PK决定的，但却不能根据PK计算出SK 。  
正是基于这种理论，1978年出现了著名的RSA算法，它通常是先生成一对RSA密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。这就使加密的计算量很大。为减少计算量，在传送信息时，常采用传统加密方法与公开密钥加密方法相结合的方式，即信息采用改进的DES或IDEA对话密钥加密，然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息后，用不同的密钥解密并可核对信息摘要 。

## 二、算法原理 ##

RSA加密是现代安全算法当中常用的加密算法，RSA公开密钥密码体制的原理是：根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。

## 三、算法描述 ##

RSA算法主要流程如下：  
**1. 选取两个大素数，p和q，计算二者乘积n=p\*q，计算ф(n)=(p-1)(q-1)**  
**2. 选取e和互素，即gcd(e,ф(n))==1,同时要求e>max(p,q)，即e要大于p和q的最大值**  
**3.解密钥d满足d*e mod ф(n)==1，即d*e = k\*ф(n)+1,k是大于等于1的整数，这里找到一组k和d的整数解就可以进行下一步的计算**  
**4.公开n和e，对整数d进行秘密保存**  
**5.将明文m加密为密文c**  
 C = E ( m ) = m e   m o d   n C = E(m) = m^e\\ mod\\ n C=E(m)=me mod n  
**6.将密文c解密为明文m**  
 m = D ( c ) = c d   m o d   n m = D(c) = c^d\\ mod\\ n m=D(c)=cd mod n

## 实例演示 ##

`1. 选取素数p=47,q=61，则n = 2867，ф(n) = 2760`  
`2. 选取e=67和ф(n)=2760互素`  
`3. 根据d*e = k*ф(n)+1公式，枚举k。得到第一组整数解k=505,d=20803。(这里很感谢文静同学对数据的贡献)`  
`4. 对m=7加密，得到密文c = 4.1837784725909e+56`  
`5. 解密m = 7`  
至此将RSA算法流程完整的走了一遍

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2OTc2MjUy_size_16_color_FFFFFF_t_70]

## 四、实现技术点 ##

主要设计的非对称加密的实现，即密钥的不对称性。其次算法中涉及到幂运算，但是c语言的限制会导致数据的溢出，所以要学会相关的快速幂运算和大数幂运算。其次函数的离线准备环节需要设计到素数的判断和公约数的计算，这里一般常用数论方法来判断素数，因为大数判素会很久，数论方法中的各种筛法较快。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2OTc2MjUy_size_16_color_FFFFFF_t_70]: /images/20220829/9b44806066764fe5bacf568839bbbf3e.png