RSA

一、RSA的使用

RSA属于非对称加密，采用一对密钥进行加密（公钥和私钥），一个用来加密、另一个用来解密，非对称加密运算速率慢（需要采用大量的数学运算，一般用于少量信息加密）

1.RSA三要素

RSA加密需要三个值：n，e1， e2。

n是两个质数的乘积，n的值越大，加密越安全，一般处于公开状态。

e1是公钥中的e（指数），与n形成公钥，用于加密，一般处于公开状态。

e2是私钥中的e（指数），与n形成私钥，用于解密，处于保密状态（不公开）。

2.Python使用rsa包加密

首先导入rsa包，把n和e转化为10进制。通过rsa.PublicKey(e=e, n=n)生成公钥。

然后使用rsa.encrypt("8helkyme0ludtdw0".encode(), pub_key=key)进行加密，其中8helkyme0ludtdw0为加密的明文，由于rsa是对字节流进行加密，所以enode()。

加密后的内容感觉乱七八糟的，一般在这时候使用hex()，把每个字节转化为两位16进制数（字节转变字符串），因此加密结果长度增加一倍。如图1所示。

图1

二、RSA原理

假设a为明文，b为密文。

加密：b=pow(a, e1, n)

解密：a=pow(b, e2, n)

1.n的来源

n是通过两个质数相乘得到的，n的二进制长度就是密钥长度。RSA的密钥一般是1024位，少数是2048位。如图1中的modulus就是1024位。

例：x和y是两个不同的质数：11和13，则n=11*13=143（加密内容不能超过143）。143的二进制是：10001111，为8位。则密钥为8位。

2.e1的来源

获取e1需要使用欧拉函数，再选取与φ(n)互质的一个数。

φ(n)=(x-1)*(y-1)=10*12=120

则：1<e1<120，且e1与120互质，如：e1=13，一般来说e1为65537。

例：2与3只有公因数1，则2和3互质。

3.e2的来源

e2泄露则代表加密被破解，在rsa加密中的6个数字中，x,y,n,φ(n),e1,e2，n=x*y，φ(n)=(x-1)*(y-1)，也就是说x,y一定不能泄露，否则6个数字已知晓了4个数字，再加上e1是公开的，所以e2就能被推算出来了。

e1*e2 mod φ(n) = 1 即：e1*e2 = k * φ(n) + 1 —>  13*e2 = k*120 +1，这个使用“扩展欧几里得算法”求解。python实现方式如图2所示。

图2

由于“扩展欧几里得算法”中的方程式是13*e2 + k*120= 1，因此k是负数，最后得出：e2=37, k=-4。

4.尝试加密解密

从上文叙述已知：e1=13, e2=37, n=143，即公钥是（13,143），私钥是（37， 143）

这里用数字9进行测试，即明文a=9，加密：b=pow(a, e1, n)=9^13%143=113

明文9加密后得到密文b：113，解密：a=pow(b, e2, n) = 113^37%143=9

三、RSA加密源码

从图1中已知，使用rsa包就两步，首先传入e，n生成公钥，key=rsa.PublicKey(e=e, n=n)

然后传入明文和公钥key，输出加密结果，h=rsa.encrypt("8helkyme0ludtdw0".encode(), pub_key=key)

在encrypt()中就几步，首先看源码：

def encrypt(message, pub_key):

keylength = common.byte_size(pub_key.n)

padded = _pad_for_encryption(message, keylength)

payload = transform.bytes2int(padded)

encrypted = core.encrypt_int(payload, pub_key.e, pub_key.n)

block = transform.int2bytes(encrypted, keylength)

return block

从源码中可以看到需要两个参数，message是明文，pub_key是公钥。

第一步：common.byte_size(pub_key.n)目的是计算n的二进制长度（位），然后除以8（字节），得到支持的最大加密长度。

第二步：_pad_for_encryption(message, keylength)目的是对明文进行填充，右侧补全，填充值是使用os.urandom()随机生成的，因此每次填充结果不一样。

第三步：transform.bytes2int(padded)目的是把每个字节转化为两位16进制来表示，再转化为10进制。

第四步：core.encrypt_int(payload, pub_key.e, pub_key.n)，对明文进行加密。

第五步：transform.int2bytes(encrypted, keylength)目的是舍弃左侧的0，在右侧进行0补全，最后每64位进行一次封装。

四、自己实现RSA加密

import os

import math

import copy

from structimport pack

k ="8helkyme0ludtdw1".encode()

modulus ="00A2FD668D79120D41EFFA26B0F5A5A43D6139D46893F7559CC2BA0C704BDA19A9420F97D113E32EF4E462C49F95B9DC487E2963F0FBE9C9C79DBD128D26C244D062BA69F9E7961D646193B8EF36814C7BB17053AB2418E1C8671781827D4BF3C6AA3D8B581FDF4F60210900EBD4AF34C5B51B77C73FB707448C527A56541B142B"

e =int("010001", 16)

n =int(modulus, 16)

# 计算n的二进制长度,获取证书位数（1024和2048）

key_length = math.ceil(n.bit_length() /8)

# 预留11个字节,获取加密时支持的最大字节数

max_msglength = key_length -11

msg_length =len(k)

if msg_length > max_msglength:

raise OverflowError("超出可支持的最大加密长度,支持:[{}]字节,目前:[{}]字节".format(max_msglength, msg_length))

padding_length = key_length - msg_length -3

new_padding = os.urandom(int(padding_length) +5).replace(b'\x00', b'')

padding = new_padding[:padding_length]

padded =b''.join([b'\x00\x02', padding, b'\x00', k])

# 原方法使用hexlify(),目的:每个字节的数据转换成相应的 2 位十六进制表示。因此产生的字符串是原数据的两倍长度

# padded.hex()在python3.5以前的实现：''.join(['%02x' % b for b in a_bytes])

# padded.hex()在python3.5以后的实现：a_bytes.hex()

payload =int(padded.hex(), 16)

# RSA加密

encrypted =pow(payload, e, n)

raw_bytes =b''

num = copy.deepcopy(encrypted)

# 加密内容进行包装

while num >0:

raw_bytes = pack(">Q", num &0xffffffffffffffff) + raw_bytes

num >>=64

# 获取左侧为0的长度

leading =0

for xin raw_bytes:

if x ==0:

leading +=1

    else:

break

# 舍弃左侧为0的数据，进行右侧补全

if leading:

raw_bytes = raw_bytes[leading:]

raw_bytes = raw_bytes.rjust(int(key_length), b'\x00')

result = raw_bytes.hex()

这是对1024位密钥加密的实现，存在部分局限性。

号外：

RSA解密：

解密原理与加密原理相同，不过多赘述，在使用python中的RSA包的时候，有一个坑，生成私钥需要传5个参数e,d,n,p,q。我们知道解密不需要e，p，q。从生成私钥源码中发现存在对p，q的检查，但是只是检查p，q是否互质。也就是说p，q传值2,3也可以。