RSA加解密原理以及三种填充模式

一.理论

如果需要理解RSA的加密原理，需要理解以下理论：

（1）如果两个正整数除了1以外没有其他公因子，则这两个数称为互质关系。(比如5和9)

（2）给定一个正整数n，在小于等于n的正整数中，与n形成互质关系的数的个数计为 $\phi$ (n)， $\phi$ (n)称为欧拉函数。(比如在1到8之间与8形成互斥关系的数为1、3、5、7，则 $\phi$ (8)=4)

（3）对于一个质数n来说， $\phi$ (n)=n-1

（4）如果n可以分解为两个互质的整数之积，即n=p1 $\times$ p2，p1与p2互质，则满足公式： $\phi$ (n) = $\phi$ (p1 $\times$ p2) = $\phi$ (p1) $\times$ $\phi$ (p2) = (p1-1) $\times$ (p2-1)

（5）如果a与b互质，则满足公式： $a^{\phi(b)}$ $\equiv$ 1( mod b)，即a的 $\phi$ (b)次方除以b的余数为1

（6）如果a与b互质，则存在n使得a $\times$ n $\equiv$ 1(mod b)，n称为a的模反元素

二.如何生成一对公私钥

（1）选择两个不相等的质数p，q。如（p=13，q=17）

（2）将p与q相乘的到n。n=13 $\times$ 17=221

（3）计算n的欧拉函数，即 $\phi$ (n)= $\phi$ (221)=(p-1) $\times$ (q-1)=192

（4）在1到 $\phi$ (221)之间选择一个与 $\phi$ (221)互质的数e，如选择e=23

（5）我们可以求得e对于 $\phi$ (n)的模反元素d，即 ed $\equiv$ 1(mod $\phi$ (n))

等同于求一元二次方程 23 * d + 192 * y = 1

可以求得其中一解为（d=167，y=-20）

至此就完成了所有的计算

（6）将计算出来的值封装为公钥（n，e）和私钥（n，d）

对于上述例子的到公钥（221，23）和私钥（221，167）

三.RSA的可靠性

在上述的计算过程中一共用到了

两个质数p，q
p与q的乘积n
欧拉函数 $\phi$ (n)
一个小于 $\phi$ (n)并与之互质的数e
e对于 $\phi$ (n)的模反元素d

上面用到的数中只有公钥部分是公开的，即（221，23）。那么我们是否可以通过公钥来推到出私钥部分，即已知n和e，推到出d？

（1）ed $\equiv$ 1(mod $\phi$ (n))，只有知道 $\phi$ (n)才能解出d

（2） $\phi$ (n)= $\phi$ (p) $\times$ $\phi$ (q)= (p-1) $\times$ (q-1)，只有知道p和q才能得到 $\phi$ (n)

（3）n=p $\times$ q，就需要对n进行因式分解

那么如果可以对n因式分解就可以求出d，也就意味着私匙被破解

那么RSA加密的可靠性就在于对n因式分解的难度，而现在对一个整数n做因式分解并没有巧妙的算法，只有通过暴力破解计算。在实际应用中的n取值通常在1024位以上，而公开已知的可因式分解的最大数为768位。所以现阶段来说RSA加密是可靠的。

四.加解密过程

现在我们就可以进行加密和解密了

（1）使用公钥（n，e）加密

我们使用上面生成的公钥（221，23）来加密。如果我们需要加密的信息是m（m必须为整数并且m要小于n），m取56，可以用以下公式求出加密串c：

$m^e$ $\equiv$ c (mod n)

$56^{23}$ $\equiv$ 10 (mod 221)

可以求出加密后的结果c为10

（2）使用密钥（n，d）解密

密钥为（221，167），加密结果c=10，可以使用以下公式求出被加密的信息

$c^d$ $\equiv$ m (mod n) 即加密结果的d次方除以n的余数为m

$10^{167}$ $\equiv$ 56 (mod 221)

五.RSA加密的三种填充模式

RSA加密属于块加密算法，总是在一个固定长度的块上进行操作。如果被加密的字符串过长，则需要对字符串进行切割，如果字符串过短则需要进行填充。

填充方式	输入	输出
RSA_PKCS1_PADDING	必须比RSA钥模长至少短11位以上	与RSA钥模长一样长
RSA_PKCS1_OAEP_PADDING	必须比RSA钥模长至少短41位以上	与RSA钥模长一样长
RSA_NO_PADDING	可以和RSA钥模长一样长	与RSA钥模长一样长

以下主介绍一下RSA_PKCS1_PADDING填充模式以及RSA_NO_PADDING模式

（1）RSA_PKCS1_PADDING填充模式

此填充模式是最常用的填充模式，在此填充模式下输入的长度受加密钥的长度限制，输入的最大长度为加密钥的位数k-11。如果公钥的长度为1024位即128字节，那么输入的长度最多为128-11=117字节。如果长度小于117就需要填充。如果输入T的长度为55字节，填充后的块为EM，则EM格式如下：

EM= 0x00 || BT || PS || 0x00 || T

首字节填充0x00，确保加密块的大小小于加密钥（可见第四部分加密要求）
BT仅一个字节，并只有三种选项0x00，0x01，0x02。其中0x02表示公钥加密，0x00，0x01表示私钥加密
PS表示填充字段，根据BT类型有不同的情况。1.对于公钥加密的情况（即BT=0x02），PS为随机生成的且不含0的数。2.BT=0x00，PS填充的值为0x00（只有输入T不以0x00开头时，BT才为0x00，否则会有歧义）。3.BT=0x01，PS填充0xFF。PS的长度为128-3-len(T)=70字节，所以PS随机数长度至少为8个字节
而后填充0x00用于区分填充字段和输入信息
T为实际的输入

以上内容可在RFC 2313 第8.1章节找到

（2）RSA_NO_PADDING填充模式

在此填充模式下，输入的长度最多和RSA公钥长度一样长，如果小于公钥长度则会在前面填充0x00。如果公钥长度是128字节，输入T的长度为55字节，填充后的块为EM，则EM格式如下：

EM=P || T

如果T长度为55字节，则P为73字节0x00
T为实际输入

参考：
http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html
http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html
https://my.oschina.net/3pgp/blog/749195

最后编辑于：2020.04.12 21:13:36

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 201,552评论 5赞 474
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 84,666评论 2赞 377
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 148,519评论 0赞 334
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,180评论 1赞 272
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,205评论 5赞 363
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,344评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,781评论 3赞 393
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,449评论 0赞 256
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,635评论 1赞 295
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,467评论 2赞 317
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,515评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,217评论 3赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,775评论 3赞 303
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,851评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,084评论 1赞 258
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,637评论 2赞 348
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,204评论 2赞 341

RSA加解密原理以及三种填充模式

一.理论

（1）如果两个正整数除了1以外没有其他公因子，则这两个数称为互质关系。(比如5和9)

（2）给定一个正整数n，在小于等于n的正整数中，与n形成互质关系的数的个数计为(n)，(n)称为欧拉函数。(比如在1到8之间与8形成互斥关系的数为1、3、5、7，则(8)=4)

（3）对于一个质数n来说，(n)=n-1

（4）如果n可以分解为两个互质的整数之积，即n=p1p2，p1与p2互质，则满足公式：(n) = (p1p2) = (p1) (p2) = (p1-1) (p2-1)

（5）如果a与b互质，则满足公式： 1( mod b)，即a的(b)次方除以b的余数为1

（6）如果a与b互质，则存在n使得an 1(mod b)，n称为a的模反元素