RSA

蔚落 2023-08-17 16:12 85阅读 0赞

# RSA #

## RSA简介 ##

### RSA定义 ###

相信只要对密码学了解的同学肯定听说过RSA，它是三个发明者名词的缩写(Rivest-Shamir-Adleman)，也是最早的公钥密码学系统之一，也是可能是应用最广泛的公钥密码学系统。\[1\]这里给它两个定义

*  广义的说，RSA密码系统(RSA cryptosystem)是基于RSA问题的公钥密码学系统
 *  狭义的说，RSA假设(RSA assumption)是一个可以构造单向陷门函数(One-way trapdoor functions)的假设。

### RSA原理 ###

我们通过定义可以看出如果一个密码学方案使用了RSA假设，那么这个密码学方案至少可以说使用了RSA密码系统。下面阐述RSA的具体原理。既然是具体的原理，我们采取狭义的定义，即RSA是一个假设，这种假设是一种单向陷门函数。

我们先介绍单向陷门函数，然后给出了RSA基本形式。接着阐述RSA的基本假设，最后通过它构造RSA单向陷门函数(也是单向陷门置换方案)。

> Despite many years of study, RSA is essentially the only known reasonable candidate trapdoor permutation scheme.

#### 单向陷门函数 ####

\[2\]单向函数(One-way function)是一类这样的函数\\(F:x \\rightarrow y\\)正向计算很容易，但是反向计算，即通过\\(y\\)计算\\(x\\)很难的函数。单向陷门函数就一类特殊的单向函数。特殊之处在于存在陷门(trapdoor)，通过陷门可以反向计算单向函数。即如果使用陷门，我们很容易逆向计算单向函数，但是如果没有陷门，我们仍然很难计算单向函数。

另外如果\\(x\\)和\\(y\\)所在域相同，即一一对应，那么就说这个单向陷门函数就一个单向陷门置换。正式的定义请参考\[2\]。

#### RSA是一个单向陷门置换 ####

涉及到RSA的基本形式，我不得不这里写出正式的定义，该定义来自于\[3\]。

RSA主要由三个函数构成\\(RSAGen\\)，\\(F\\)，\\(I\\)。

\\(RSAGen(l,e)\\)生成一个\\(l\\)位的素数\\(p\\)满足\\(gcd(e,p-1) = 1\\)

\\(RSAGen(l,e)\\)生成一个\\(l\\)位的素数\\(q\\)满足\\(gcd(e,q-1) = 1\\)且\\(p \\neq q\\)

\\(n \\leftarrow pq\\)

\\(d \\leftarrow e^\{-1\} \\mod (p-1)(q-1)\\)

输出\\((n,d)\\)

对于给定的公钥\\(pk = (n,e),x \\in Z\_n\\)，我们定义\\(F(pk,x) := x^e \\in Z\_n\\)。

对于给定的私钥\\(sk = (n,d),y \\in Z\_n\\)，我们定义\\(I(sk,y) := y^d \\in Z\_n\\)。

*注意这里要求gcd(e,p-1) = 1且gcd(e,q-1) = 1是在保证可以计算出d否则e不在群\\(Z\_n\\)即\\(Z\_\{pq\}\\)中存在乘法逆*。

#### RSA假设 ####

一句话，RSA假设就是说**假设**上面的RSA方案是一个单向陷门函数。由于RSA本身的数学性质是\\(Z\_n^\*\\)到自身的置换。所以RSA方案是一个单向陷门置换。

#### RSA假设基于什么 ####

保研夏令营的时候老师问我RSA假设基于啥？我其实不知道当时上课的时候说的啥，突然脑子中想起就说是基于大整数分解。老师说不对。如今仔细翻书才明白。**RSA假设啥都不基于，它就是一个假设。** 大整数分解如果能被解决，那么RSA一定能被解决。但是RSA被解决却不一定需要大整数分解。大整数分解是更难的问题，无法规约到RSA。\[4\]

## RSA应用 ##

RSA密码系统，或者说所有的公钥密码学系统一般都有两个应用，公钥加密和签名。值得注意的是，相同的密钥对在不同的RSA应用中也不应该被多次使用，这是极其危险的。这部分首先研究下参数选择问题，下面我们分别来说它们的应用。然后尝试几个开源实现。另外这节要参考PKCS \#1 v2.1的标准\[6\] (最新的版本已经到v2.2了)，这也是大多数实现参考的标准。(因为水平有限，省略了素数生成的部分)

### e的选择 ###

选择e = 65537。

理论上任何满足上述条件的e都行，素数方便我们满足gcd(p-1,e)=1。但是处于效率的考虑，我们选择一些费马素数(即形式满足\\(2^n+1\\)的素数)。集合是\{3，5，17，257，65537\}。*更高的费马素数是无法想象的大。*

倾向于选择小的e可以加快速度。但是考虑到兼容性(很多标准都纳入65537，可能源于历史上人们对e的误解)和很多方案没有使用正确的填充，我们通常选择65537作为折中。(并不是说选择小的e不安全。)

一般来讲我们选择e = 65537。

openssl提供了两个选项e = 65537和e = 3来选择。默认是e = 65537。

*我们总听说有什么小指数攻击，那是似乎是因为不正确的填充(padding)或者其它原因导致的。不是说e小导致的，对于正确的使用方案，e=3同样跟e=65537安全。e=65537更近乎行业标准*。

### n的选择 ###

如果你想要保护你的密钥20年，使用RSA2048bit。如果你可以不计开销，那么就使用RSA4096bit。随着计算机越来越快，未来你可能需要使用RSA8196bit。使用一个大RSA是好的，因为可以省去未来更换的麻烦。\[7\]

### RSA padding ###

直接用做加密和签名的RSA都是不安全的！现存的攻击包括小指数攻击，共模攻击，乘法攻击等等更高级的多项式时间攻击。\[5\]所以这里有一个原则：

> it is very bad to have any kind of structure in the  
> numbers that RSA operates on.

例如我们使用2048bitRSA操作256bit的AES密钥时，我们选择e=5，那么\\(2^\{256\*5\} = 2^\{1280\}\\)，我们直接使用开五次方就可以得出结果。所以我们需要打破原来数据的结构。这就是RSApadding，或者说公钥密码系统的padding。

> For example, for encryption you might  
> use RSA-OAEP, and for signatures you might use RSA-PSS.

RSApadding在PKCS \#1 v2.2中有标准。包括RSA-OAEP，RSA-PSS等padding方案。

*  对于RSA加密，标准中给出了pkcs v1.5和OAEP。使用OAEP，pkcsv1.5是不安全的。
 *  对于RSA签名，标准给出了pkcs v1.5和PSS。尽可能使用PSS，虽然签名中的pkcs v1.5没有相应的攻击，但是应该以保守的原则使用PSS。

*PKCS \#1 v2.1说了两遍RSA，一个是带CRT的一个不带，被吐槽了：标准和实现掺在一起*。

### RSA加密 ###

一般来讲，RSA不会直接用于加密。需要使用对称加密方案\\(E\\)来加密消息\\(m\\)，最后传递消息\\(RSAE(key,e),E(m,key)\\)。相应的，使用\\(key = RSAD(RSAE(key,e),d),m = D(E(m,key),key)\\)。进行解密。

### RSA签名 ###

对于签名，首先使用hash函数对签名进行去结构化\\(H(m)\\)。然后通过PRNG来将\\(H(m)\\)来映射到\\(0,...,2^k-1\\)，其中\\(k\\)是满足\\(2^k<n\\)的最大的\\(k\\)。然后再进行朴素的签名即可。

使用填充方案\\(PSS\\)是更好的选择。

### RSA开源实现和使用 ###

#### OpenSSL ####

*  openssl命令

openssl命令行关于rsa的有三个命令模块`genrsa`，`rsa`，`rsautl`。其中genrsa主要用于生成rsa密钥。rsa主要用于转换rsa密钥格式。rsautl用于对数据的加密或者解密。具体使用方法可以参考openssl的手册。

值得注意的是，对于rsa模块的命令有两组选项分别是`-pubin`,`-pubout`和`-RSAPublickey_in`,`-RSAPublicKey_out`。这是两种不同的格式，我在网上搜索到了满意的[答案][Link 1]。(为啥没有privatekey的格式，因为PKCS\#8只规定了公钥的格式，私钥因为不用分发所以不需要格式。)

*  openssl接口

生成RSA密钥的函数

`RSA * RSA_generate_key(int bits, unsigned long e, void (*callback) (int,int,void *),void *cb_arg);`

从文件中读取RSA函数

`EVP_PKEY *PEM_read_bio_PrivateKey(BIO *bp, EVP_PKEY **x, pem_password_cb *cb, void *u);`

RSA加密解密函数

`int RSA_public_encrypt(int flen, const unsigned char *from,unsigned char *to, RSA *rsa,int padding);`

`int RSA_private_decrypt(int flen, const unsigned char *from,unsigned char *to, RSA *rsa,int padding);`

RSA签名验证函数

`int RSA_sign(int type, const unsigned char *m, unsigned int m_length, unsigned char *sigret, unsigned int *siglen, RSA *rsa);`

`int RSA_verify(int type, const unsigned char *m, unsigned int m_length, unsigned char *sigbuf, unsigned int siglen, RSA *rsa);`

## RSA性能 ##

提升RSA性能主要考虑两个方面，一个是CRT，一个时模n乘法。对于CRT，PKCS \#1中专门给出了相应的CRT标准。对于模n乘法也是选择e的因素。

### CRT ###

待更新。。。

### 模n乘法 ###

## RSA攻击\[5\] ##

### 数学攻击 ###

### 实现攻击（侧信道） ###

## 相关的名词 ##

OAEP PSS DSA ECC PKCS

## 总结 ##

RSA是如今使用最广泛的公钥密码学系统，相关选择要么是纸上的标准，要么是行业默认的标准。希望能用此文阐述RSA相关的内容，供他人和自己参考。文中有错误或者不详尽之处，请发[邮件][Link 2]给我或者在下方评论。

## 参考 ##

\[1\] [https://en.wikipedia.org/wiki/RSA\_(cryptosystem)][https_en.wikipedia.org_wiki_RSA_cryptosystem].

\[2\] A Graduate Course in Applied Cryptography by Dan Boneh and Victor Shoup, Version 0.4, September 2017, Chapter 10.2, P395-398.

\[3\] A Graduate Course in Applied Cryptography by Dan Boneh and Victor Shoup, Version 0.4, September 2017, Chapter 10.3, P398-401.

\[4\] Introduction to modern cryptography by Jonathan Katz and Yehuda Lindell, Second edition, Chaper 8.2.5, P314-316.

\[5\] [https://crypto.stanford.edu/~dabo/pubs/papers/RSA-survey.pdf][https_crypto.stanford.edu_dabo_pubs_papers_RSA-survey.pdf]

\[6\] [https://tools.ietf.org/html/rfc8017][https_tools.ietf.org_html_rfc8017]

\[7\] Cryptography Engineering by Niels Ferguson, Bruce Schneier and Tadayoshi kohno, the 1st Edition, Chapter 12.4.4, P203.

转载于:https://www.cnblogs.com/zhuowangy2k/p/11517610.html

[Link 1]: https://stackoverflow.com/a/29707204
[Link 2]: mailto:zhuowangy2k@outlook.com
[https_en.wikipedia.org_wiki_RSA_cryptosystem]: https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29
[https_crypto.stanford.edu_dabo_pubs_papers_RSA-survey.pdf]: https://crypto.stanford.edu/~dabo/pubs/papers/RSA-survey.pdf
[https_tools.ietf.org_html_rfc8017]: https://tools.ietf.org/html/rfc8017