RSA - 原理、特点(加解密及签名验签)及公钥和私钥的生成

IT教程 4年前 (2020) https://www.55wd.com

rsa

Wiki - RSA加密演算法

Wiki - 欧拉函数

Wiki - 模反元素

ASN.1 格式标准

RSA算法原理(二)

注意:

  • RSA 加密或签名后的结果是不可读的二进制,使用时经常会转为 BASE64 码再传输。
  • RSA 加密时,对要加密数据的大小有限制,最大不大于密钥长度。例如在使用 1024 bit 的密钥时(genrsa -out rsa_private_key.pem 1024),最大可以加密 1024/8=128 Bytes 的数据。数据大于 128 Bytes 时,需要对数据进行分组加密(如果数据超限,加解密时会失败,openssl 函数会返回 false),分组加密后的加密串拼接成一个字符串后发送给客户端。
  • 为了保证每次加密的结果都不同,RSA 加密时会在待加密数据后拼接一个随机字符串,再进行加密。不同的填充方式 Padding 表示这个字符串的不同长度,在对超限数据进行分组后,会按照这个 Padding 指定的长度填入随机字符串。例如如果 Padding 填充方式使用默认的 OPENSSL_PKCS1_PADDING(需要占用 11 个字节用于填充),那么明文长度最多只能就是 128-11=117 Bytes
  • 一般默认使用 OPENSSL_PKCS1_PADDING。PHP 支持的 Padding 有 OPENSSL_PKCS1_PADDINGOPENSSL_SSLV23_PADDINGOPENSSL_PKCS1_OAEP_PADDINGOPENSSL_NO_PADDING
  • 接收方解密时也需要分组。将加密后的原始二进制数据(对于经过 BASE64 的数据,需要解码),每 128 Bytes 分为一组,然后再进行解密。解密后,根据 Padding 的长度丢弃随机字符串,把得到的原字符串拼接起来,就得到原始报文。

原理

RSA 算法的可靠性基础:对极大整数做因数分解是很困难的

RSA 是非对称算法,加解密使用不同的密钥。

两个密钥都可以用于加密,解密时需要使用另一个密钥。但是,通常用公钥加密私钥解密,因为公钥是近乎完全公开的,对于私钥加密的数据,有太多的人可以解密了。理论上 A 和 B 之间要通过 RSA 实现保密通信,需要 A 和 B 各自生成一组密钥,同时保管好自己的私钥;用对方的公钥加密要发送的消息,用自己的私钥解密对方发送过来的消息。

在签名的场景下,用私钥签名,公钥验签。

RSA 比 DES 等对称算法慢得多。一般在实际数据传输时,用 RSA 来加密比较短的对称密码,双方交换密码后再使用 DES 等对称算法传输数据。

互质关系

如果两个正整数,除了 1 以外没有其他公因子,就称这两个数是互质关系。比如 3 和 5,13 和 31 等。

欧拉函数

Wiki - 欧拉函数

欧拉函数:求小于 N {\displaystyle N} N 的正整数中与 N {\displaystyle N} N 互质的数的数目。

例如,对应 8,与 8 互质的数有 1,3,5,7,所以 φ ( N ) {\displaystyle \varphi (N)} φ(N) = 4。

RSA 算法使用了欧拉函数的一个特例:如果 N {\displaystyle N} N 可以分解成两个互质的整数之积:

N = p q {\displaystyle N=pq} N=pq

φ ( N ) = φ ( p ) φ ( q ) = ( p − 1 ) ( q − 1 ) {\displaystyle \varphi (N)=\varphi (p)\varphi (q)=(p-1)(q-1)} φ(N)=φ(p)φ(q)=(p−1)(q−1)

比如, φ ( 35947 ) = φ ( 103 ) φ ( 349 ) = ( 102 ) ( 348 ) = 35496 {\displaystyle \varphi (35947)=\varphi (103)\varphi (349)=(102)(348)=35496} φ(35947)=φ(103)φ(349)=(102)(348)=35496。

模反元素

Wiki - 模反元素

如果两个正整数 a a a 和 n n n 互质,那么一定可以找到整数 b b b,使得 a b − 1 ab-1 ab−1 被 n n n 整除:

a b ≡ 1 ( m o d n ) ab\equiv 1{\pmod {n}} ab≡1(modn)

这时, b b b 就叫做 a a a 的"模反元素"。

欧拉定理证明当 a , n {\displaystyle a,n} a,n 为两个互素的正整数时,则有 a φ ( n ) ≡ 1 ( m o d n ) {\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}} aφ(n)≡1(modn),其中 φ ( n ) {\displaystyle \varphi (n)} φ(n) 为欧拉函数(小于等于 n {\displaystyle n} n 且与 n {\displaystyle n} n 互素的正整数个数)。

上述结果可分解为 a φ ( n ) = a ⋅ a φ ( n ) − 1 ≡ 1 ( m o d n ) {\displaystyle a^{\varphi (n)}=a\cdot a^{\varphi (n)-1}\equiv 1{\pmod {n}}} aφ(n)=a⋅aφ(n)−1≡1(modn),其中 a φ ( n ) − 1 {\displaystyle a^{\varphi (n)-1}} aφ(n)−1 即为 a {\displaystyle a} a 关于模 n {\displaystyle n} n 之模反元素。

举例

求整数 3 对同余 11 的模逆元素 x,

x ≡ 3 − 1 ( m o d 11 ) {\displaystyle x\equiv 3^{-1}{\pmod {11}}} x≡3−1(mod11)

上述方程可变换为

3 x ≡ 1 ( m o d 11 ) {\displaystyle 3x\equiv 1{\pmod {11}}} 3x≡1(mod11)

在整数范围 Z 11 {\displaystyle \mathbb {Z} _{11}} Z11​ 内,可以找到满足该同余等式的 x x x 值为4,如下式所示

3 ( 4 ) = 12 ≡ 1 ( m o d 11 ) {\displaystyle 3(4)=12\equiv 1{\pmod {11}}} 3(4)=12≡1(mod11)

并且,在整数范围 Z 11 {\displaystyle \mathbb {Z} _{11}} Z11​ 内不存在其他满足此同余等式的值。

故,整数3对同余11的模逆元素为4。

生成公钥和私钥

  • 随意选择两个大的质数 p {\displaystyle p} p 和 q {\displaystyle q} q, p {\displaystyle p} p 不等于 q {\displaystyle q} q,计算 N = p q {\displaystyle N=pq} N=pq。
  • 根据欧拉函数,求得 r = φ ( N ) = φ ( p ) φ ( q ) = ( p − 1 ) ( q − 1 ) {\displaystyle r=\varphi (N)=\varphi (p)\varphi (q)=(p-1)(q-1)} r=φ(N)=φ(p)φ(q)=(p−1)(q−1)
  • 选择一个小于 r {\displaystyle r} r 的整数 e {\displaystyle e} e,使 e {\displaystyle e} e 与 r {\displaystyle r} r 互质。并求得 e {\displaystyle e} e 关于 r {\displaystyle r} r 的模反元素,命名为 d {\displaystyle d} d(求 d {\displaystyle d} d 令 e d ≡ 1 ( m o d r ) e d ≡ 1 ( m o d r ) {\displaystyle ed\equiv 1{\pmod {r}}} {\displaystyle ed\equiv 1{\pmod {r}}} ed≡1(modr)ed≡1(modr))。(模反元素存在,当且仅当 e {\displaystyle e} e 与 r {\displaystyle r} r 互质)
  • 将 p {\displaystyle p} p 和 q {\displaystyle q} q 的记录销毁。

( N , e ) {\displaystyle (N,e)} (N,e) 是公钥, ( N , d ) {\displaystyle (N,d)} (N,d) 是私钥。公钥发送给所有的通信对象(对服务器来说就是所有的客户端),私钥则必须保管好,防止泄露。

加密消息

假设客户端要向服务器发送消息 m {\displaystyle m} m,服务器的公钥是 N {\displaystyle N} N 和 e {\displaystyle e} e。客户端将消息 m {\displaystyle m} m 转换为一个小于 N {\displaystyle N} N 的非负整数 n {\displaystyle n} n,比如可以将每一个字转换为这个字的 Unicode 码,然后将这些数字连在一起组成一个数字。假如信息非常长的话,可以将这个信息分为几段,然后将每一段转换为 n {\displaystyle n} n。用下面这个公式他可以将 n {\displaystyle n} n 加密为 c {\displaystyle c} c:

c ≡ n e ( m o d N ) {\displaystyle c\equiv n^{e}{\pmod {N}}} c≡ne(modN)

计算 c {\displaystyle c} c 并不复杂。客户端算出 c {\displaystyle c} c 后就可以将它传递给服务器。

解密消息

得到消息 c {\displaystyle c} c 后,可以利用密钥 d {\displaystyle d} d 来解码。可以用以下这个公式来将 c {\displaystyle c} c 转换为 n {\displaystyle n} n:

c d ≡ n ( m o d N ) {\displaystyle c^{d}\equiv n\ (\mathrm {mod} \ N)} cd≡n(modN)

得到 n {\displaystyle n} n 后,可以将原来的信息 m {\displaystyle m} m 重新复原。

解码的原理是:

c d ≡ n e ⋅ d ( m o d N ) {\displaystyle c^{d}\equiv n^{e\cdot d}\ (\mathrm {mod} \ N)} cd≡ne⋅d(modN)

已知 e d ≡ 1 ( m o d r ) {\displaystyle ed\equiv 1{\pmod {r}}} ed≡1(modr),即 e d = 1 + h φ ( N ) {\displaystyle ed=1+h\varphi (N)} ed=1+hφ(N)。由欧拉定理得:

n e d = n 1 + h φ ( N ) = n ( n φ ( N ) ) h ≡ n ( 1 ) h ( m o d N ) ≡ n ( m o d N ) {\displaystyle n^{ed}=n^{1+h\varphi (N)}=n\left(n^{\varphi (N)}\right)^{h}\equiv n(1)^{h}{\pmod {N}}\equiv n{\pmod {N}}} ned=n1+hφ(N)=n(nφ(N))h≡n(1)h(modN)≡n(modN)

签名消息

RSA 也可以用来为一个消息签名。

对消息字符串的散列值(Message digest,用 MD5、SHA256 等算法求得的长度较短且固定的字符串)使用 RSA 的私钥计算签名(实际上仍然是加密消息)后,得到一个签名字符串,将其附加在消息字符串的合适位置后,一并发送。接收方使用对应的公钥可以从签名字符串中解密出原来的散列值,同时对原始消息再计算一次散列值。二者相比较,假如两者相符的话,则认为发信人持有正确的私钥,并且这个消息在传播路径上没有被篡改过。

密钥长度

用户应使用 1024 位密钥,证书认证机构应用 2048 位或以上。

特点

RSA 之所以叫非对称算法,是因为加密和解密的密钥不一样。任何一个密钥都可以用来加密。

公钥和私钥

通过私钥可以轻松计算出公钥,反之不行。

  1. 随机选择两个不相等的质数 p {\displaystyle p} p 和 q {\displaystyle q} q, p {\displaystyle p} p 不等于 q {\displaystyle q} q,计算 N = p q {\displaystyle N=pq} N=pq。

    这里选择 103 和 349。 N = p q {\displaystyle N=pq} N=pq = 35947。 N {\displaystyle N} N 的长度就是密钥长度。35947 对应的二进制是 ‭1000110001101011‬,一共有 16 位,所以这个密钥就是 16 位。实际应用中 RSA 密钥一般是1024位。

  2. 计算 N {\displaystyle N} N 的欧拉函数 φ ( N ) {\displaystyle \varphi (N)} φ(N)。 r = φ ( 35947 ) = φ ( 103 ) φ ( 349 ) = ( 102 ) ( 348 ) = 35496 {\displaystyle r=\varphi (35947)=\varphi (103)\varphi (349)=(102)(348)=35496} r=φ(35947)=φ(103)φ(349)=(102)(348)=35496。
  3. 选择一个小于 r {\displaystyle r} r 的整数 e {\displaystyle e} e,使 e {\displaystyle e} e 与 r {\displaystyle r} r 互质,这里取 e = 773 {\displaystyle e=773} e=773。
  4. 求 e {\displaystyle e} e 关于 r {\displaystyle r} r 的模反元素,命名为 d {\displaystyle d} d(求 d {\displaystyle d} d 令 e d ≡ 1 ( m o d r ) e d ≡ 1 ( m o d r ) {\displaystyle ed\equiv 1{\pmod {r}}} {\displaystyle ed\equiv 1{\pmod {r}}} ed≡1(modr)ed≡1(modr))。最终转为 773d-1=35496k 这个二元一次方程,求得一组解(d,k)=(45,1)。
  5. 将 ( N , e ) {\displaystyle (N,e)} (N,e) 封装成公钥, ( N , d ) {\displaystyle (N,d)} (N,d) 封装成私钥。所以公钥就是 (35496 ,773),私钥就是(35496 , 45)。

加密和解密

用公钥加密时,私钥可以解密。反之亦然,私钥加密后的信息用公钥可以解密。

签名和验签

操作

如果是对接其他平台提供的标准接口,如果这个接口用到了 RSA 加密,则需要这个平台提供对应的公钥。

Linux 下通过 OpenSSL 生成 RSA 公钥和私钥

需要提前在 Linux 上安装 OpenSSL,默认生成在当前用户家目录下:

[root@VM_120_242_centos ~]# openssl 
OpenSSL> genrsa -out app_private_key.pem   1024  # 生成私钥
Generating RSA private key, 1024 bit long modulus
.++++++
........++++++
e is 65537 (0x10001)

OpenSSL> rsa -in app_private_key.pem -pubout -out app_public_key.pem  # 生成公钥
writing RSA key
OpenSSL> exit

对于 PHP 可以直接使用上面生成的原始私钥。但是 Java 需要将私钥转换成 PKCS8 格式,然后将生成的 PKCS8 格式的私钥去除头尾、换行和空格,作为私钥字符串填入代码中:

OpenSSL> pkcs8 -topk8 -inform PEM -in app_private_key.pem -outform PEM -nocrypt -out app_private_key_pkcs8.pem # 私钥转成 PKCS8 格式

查看生成的文件:

[root@VM_120_242_centos ~]# ll
总用量 1064
-rw-r--r-- 1 root root    887 6月  14 11:25 app_private_key.pem
-rw-r--r-- 1 root root    272 6月  14 11:25 app_public_key.pem

查看公钥:

-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQC3//sR2tXw0wrC2DySx8vNGlqt
3Y7ldU9+LBLI6e1KS5lfc5jlTGF7KBTSkCHBM3ouEHWqp1ZJ85iJe59aF5gIB2kl
Bd6h4wrbbHA2XE1sq21ykja/Gqx7/IRia3zQfxGv/qEkyGOx+XALVoOlZqDwh76o
2n1vP1D+tD3amHsK7QIDAQAB
-----END PUBLIC KEY-----

转成 PKCS8 格式的公钥字符串为:

MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQC3//sR2tXw0wrC2DySx8vNGlqt3Y7ldU9+LBLI6e1KS5lfc5jlTGF7KBTSkCHBM3ouEHWqp1ZJ85iJe59aF5gIB2klBd6h4wrbbHA2XE1sq21ykja/Gqx7/IRia3zQfxGv/qEkyGOx+XALVoOlZqDwh76o2n1vP1D+tD3amHsK7QIDAQAB

查看私钥:

-----BEGIN RSA PRIVATE KEY-----
MIICXQIBAAKBgQC3//sR2tXw0wrC2DySx8vNGlqt3Y7ldU9+LBLI6e1KS5lfc5jl
TGF7KBTSkCHBM3ouEHWqp1ZJ85iJe59aF5gIB2klBd6h4wrbbHA2XE1sq21ykja/
Gqx7/IRia3zQfxGv/qEkyGOx+XALVoOlZqDwh76o2n1vP1D+tD3amHsK7QIDAQAB
AoGBAKH14bMitESqD4PYwODWmy7rrrvyFPEnJJTECLjvKB7IkrVxVDkp1XiJnGKH
2h5syHQ5qslPSGYJ1M/XkDnGINwaLVHVD3BoKKgKg1bZn7ao5pXT+herqxaVwWs6
ga63yVSIC8jcODxiuvxJnUMQRLaqoF6aUb/2VWc2T5MDmxLhAkEA3pwGpvXgLiWL
3h7QLYZLrLrbFRuRN4CYl4UYaAKokkAvZly04Glle8ycgOc2DzL4eiL4l/+x/gaq
deJU/cHLRQJBANOZY0mEoVkwhU4bScSdnfM6usQowYBEwHYYh/OTv1a3SqcCE1f+
qbAclCqeNiHajCcDmgYJ53LfIgyv0wCS54kCQAXaPkaHclRkQlAdqUV5IWYyJ25f
oiq+Y8SgCCs73qixrU1YpJy9yKA/meG9smsl4Oh9IOIGI+zUygh9YdSmEq0CQQC2
4G3IP2G3lNDRdZIm5NZ7PfnmyRabxk/UgVUWdk47IwTZHFkdhxKfC8QepUhBsAHL
QjifGXY4eJKUBm3FpDGJAkAFwUxYssiJjvrHwnHFbg0rFkvvY63OSmnRxiL4X6EY
yI9lblCsyfpl25l7l5zmJrAHn45zAiOoBrWqpM5edu7c
-----END RSA PRIVATE KEY-----

视频加速器哪个好?

随着互联网的快速发展和电脑的普及,越来越多的小伙伴都喜欢在网上观看电影视频。相信很多人在网上播放视频时,都遇到过有些视频不需

2-生理周期

上一篇中讲解了什么是枚举,并通过一个例子说明了枚举的过程,枚举的确是一个个的尝试答案,但是很多尝试我们就知道它一定不满足要求,所

excel2007表格如何加密的教程

Excel的加密功能如何运用到表格上呢?接下来是豌豆资源网小编为大家带来的excel2007表格如何加密的教程,供大家参考。excel2007表格

build-essential 软件包

build-essential 软件包 build-essential 软件包的作用是提供编译程序必须的软件包列表信息。1. apt-cache depends build-essent

TIM怎么添加多个邮箱并管理?

想要让TIM同时来管理多个邮箱,该怎么添加邮箱并管理邮箱呢?下面我们就来看看详细的教程。1、首先我们在手机上打开并登录TIM后,我们

文章回顾

大家看了本文RSA - 原理、特点(加解密及签名验签)及公钥和私钥的生成的精彩教程资源内容,是不是对RSA - 原理、特点(加解密及签名验签)及公钥和私钥的生成了解更多,真心希望RSA - 原理、特点(加解密及签名验签)及公钥和私钥的生成能帮助到你, 小编会一直给你带来更多教程资源文章信息。

版权声明: 发表于 2020-07-02 1:48:29。

本文由第三方用户分享仅代表作者观点,不代表本网站立场,秉承互联网开放分享的精神,目的在于传递更多信息,加强各行业互通交流,但对内容不作任何保证或承诺,请读者自行参考斟酌。网站发布的信息(包含但不限于版式、图片、字体、文章等素材)由第三方用户分享,版权归原作者所有,本站不承担任何相关的版权纠纷等相关责任。如您认为本篇内容侵犯了您的权益,请与我们联系,我们会及时处理。

豌豆资源网专注分享全网综合资源网站大全,致力于超实用的内容资源搜索。

转载请注明:
本文标题:RSA - 原理、特点(加解密及签名验签)及公钥和私钥的生成
本文地址:https://55wd.com/s87934/