RSA加解密算法以及密钥格式

时间:2024-07-10 12:35:20

RSA算法:

有个文章关于RSA原理讲的不错:

https://blog.****.net/dbs1215/article/details/48953589

http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html

RSA 相关名词

RSA代表的是一种算法

PKCS 代表的这种算法的一系列标准

原始算法定义:

RSA的算法涉及三个参数,n、e1、e2。其中,n是两个大质数p、q的积,n的二进制表示时所占用的位数,就是所谓的密钥长度。e1和e2是一对相关的值,e1可以任意取,

要求e1与(p-1)*(q-1)互质

再选择e2,要求(e2*e1)mod((p-1)*(q-1))=1。

(n,e1),(n,e2)就是密钥对。其中(n,e1)为公钥,(n,e2)为私钥。

RSA加解密的算法完全相同,设A为明文,B为密文,则:

A=B^e2 mod n;

B=A^e1 mod n;

公钥加密*中,一般用公钥加密,私钥解密

e1和e2可以互换使用,即:

A=B^e1 mod n;

B=A^e2 mod n;

具体实用产生密文过程:

对于非数学,或者不需要做加密解密等工作的人,我觉得了解下面这些就够了:

公钥     (E,N)
私钥     (D,N)
密钥对     (E,D,N)
加密     密文=明文EmodN
解密     明文=密文DmodN

计算过程:

求N     N= p * q ;p,q为质数
求L     L=lcm(p-1,q-1) ;L为p-1、q-1的最小公倍数
求E     1 < E < L,gcd(E,L)=1;E,L最大公约数为1(E和L互质)
求D     1 < D < L,E*D mod L = 1

具体名词:

1. 密钥长度:

n的二进制表示时所占用的位数,就是所谓的密钥长度。

RSA 算法中的密钥长度是非常长的,介于 512 - 65536 之间(JDK 中默认长度是1024),但是必须是64 的倍数。

密钥:

密钥的存储结构:

密钥的存储结构有很多,现在先用pem的PKCS#1为例说明:

在PKCS#1 RSA算法标准中定义RSA私钥语法为:

RSAPrivateKey ::= SEQUENCE {

version Version,

modulus INTEGER, -- n

publicExponent INTEGER, -- e

privateExponent INTEGER, -- d

prime1 INTEGER, -- p

prime2 INTEGER, -- q

exponent1 INTEGER, -- d mod (p-1)

exponent2 INTEGER, -- d mod (q-1)

coefficient INTEGER, -- (inverse of q) mod p

otherPrimeInfos OtherPrimeInfos OPTIONAL

}

类型RSAPrivateKey 的各域具有以下意义:

• version 是版本号,为了与本文档的今后版本兼容。本篇文档的这个版本号应该是0,如果使用了多素数,则版本号应该是1。

Version ::= INTEGER { two-prime(0), multi(1) }

(CONSTRAINED BY {-- version must be multi if otherPrimeInfos present --})

• modulus 是RSA合数模n。

• publicExponent 是RSA的公开幂e。

• privateExponent 是RSA的私有幂d。

• prime1 是n的素数因子p。

• prime2 i是n的素数因子q。

• exponent1 等于d mod (p − 1)。

• exponent2 等于d mod (q − 1)。

• coefficient 是CRT系数 q–1 mod p。

• otherPrimeInfos 按顺序包含了其它素数r3, …, ru的信息。如果version是0 ,它应该被忽略;而如果version是1,它应该至少包含OtherPrimeInfo的一个实例。

OtherPrimeInfos ::= SEQUENCE SIZE(1..MAX) OF OtherPrimeInfo

OtherPrimeInfo ::= SEQUENCE {

prime INTEGER, -- ri

exponent INTEGER, -- di

coefficient INTEGER -- ti

}

OtherPrimeInfo的各域具有以下意义:

• prime 是n的一个素数因子ri ,其中i ≥ 3。

• exponent 是di = d mod (ri − 1)。

• coefficient 是CRT系数 ti = (r1 · r2 · … · ri–1)–1 mod ri。

公钥语法为:

RSAPublicKey ::= SEQUENCE {

modulus INTEGER, -- n

publicExponent INTEGER -- e

}

类型RSAPublicKey的域具有以下意义:

• modulus 是RSA的合数模n。

• publicExponent 是RSA公开幂e。

pem 就是将以上数据结构用TLV格式组装成文件,存储起来。

公用文件实例:

1. 假设文件内容如下:

1.modulus:
AB602562101207D05A6C413E24CE42699210388F5D31D28151E0FA9141D9C8F8
AC716C0C4F449616AA2270F1007CF3BA46F05131E402266B2A628F4B70142429
93F5BC06E3C0609F9E52BE8D5D0CFACF53C2EE98533A9818828EC5CB8120A688
ADC603DBE65DF9059AD8039644897896943912D81C76856AB7E380C1530C6DE0
E155D4C9FB943967C52EB147CDBF2464AC2B631055DBE3109491A067567AE515
FD36428930FABCAC7C0FEB906C11815B6F00462E588DEB81C4364E2B62540E92
69F49487CC4F8724DDC481C5134B86108C9FACD5D7187706ACA2D3425BFE4F11
9C254273FA5C91EEA5EB06154936D27EE62266CDCAE9E34D20229360559325C7

2.publicExponent:
00000003

2。

组装PEM文件

1.按照以上数据域顺序依次组装成TLV。
①modulus组装
0282010100
AB602562101207D05A6C413E24CE42699210388F5D31D28151E0FA9141D9C8F8
AC716C0C4F449616AA2270F1007CF3BA46F05131E402266B2A628F4B70142429
93F5BC06E3C0609F9E52BE8D5D0CFACF53C2EE98533A9818828EC5CB8120A688
ADC603DBE65DF9059AD8039644897896943912D81C76856AB7E380C1530C6DE0
E155D4C9FB943967C52EB147CDBF2464AC2B631055DBE3109491A067567AE515
FD36428930FABCAC7C0FEB906C11815B6F00462E588DEB81C4364E2B62540E92
69F49487CC4F8724DDC481C5134B86108C9FACD5D7187706ACA2D3425BFE4F11
9C254273FA5C91EEA5EB06154936D27EE62266CDCAE9E34D20229360559325C7

说明:
02 - tag  1byte 固定长度 T
82 - 81代表长度用1byte表示,82代表长度用2byte表示 L
0101 - length 2bytes表示 L 跟上面部分共同组成L 长度不固定 见注释
00 - 在modulus数据前添加00。 见注释

modules 正常应该是base64存储

②publicExponent组装:
020103

说明:
02 - tag T
01 - length L
03 - 00000003 在公钥组装中,舍弃0x00;私钥组装中,保留0x00 V

2.输出PEM文件
①公钥PEM文件头,嵌套多层TLV,本实例文件头为:
30820120 300d06092a864886f70d0101010500 0382010d 0030820108

说明:
30820120 文件总的说明 标签头
30 - tag
82 - 代表length由2bytes表示
0120 - length (2bytes) 代表本文件有288个byte

30 0d 06092a864886f70d0101010500 这13个字节代表的含义,后续再研究
30 - tag
0d - length
06092a864886f70d0101010500 - value

03 82 010d 00。269个字节,组装的整体的实际内容:module和publicExponent
03 - tag
82 - 代表length由2bytes表示
010d - value (2bytes),代表长度

00 - 补0x00,

3082 0108  组装的整体的实际内容:module和publicExponent
30 - tag
82 - 代表length由2bytes表示
0108 - value(2bytes),代表长度。

②依次输出以上组装后的数据到PEM文件。

至此,PEM文件已生成。

注:

长度确定方式 ,也就是L的编码:

编码长度,一种是只用一个字节表示长度,其最高位为0,后7位表示长度值,显然这样只能表示0-127。另一种是第一个字节的最高位为1,其他位表示后面还有多少个字节属于Length octets(>=0x80)。后面的那些字节组成的就是长度值。长度值表示的是Contents octets所占的字节数。DER要求如果长度为0-127则要使用第一种方式,如果大于127则使用后一种方式。

1)上述TLV结构中:

V值长度<0x80,L表示数据的长度;

V值长度>=0x80的时候,L为0x8X,X表示的L长度要占用的字节数,X个字节用来表示V的长度。

2)RSA公钥N的第一个字节如果大于0x80,则需要在公钥值前面补00,这是因为modulus 为一个大整数,最高位为符号位,其为1时,就是负数,所以要在最高位填充0x00以保证不为负。所以公钥TLV应该是:02 81 81 00 [128字节个公钥值]。

3)RSA私钥的N,d,p,q,Dp,Dq,Mp也需要考虑(2)中的第一个字节如果大于0x80的情况。

4)

TLV一种可变格式,TLV的意思就是:Type类型, Lenght长度,Value值;

Type和Length的长度固定,一般那是2、4个字节;

Value的长度有Length指定;