在对称密码中,由于加密和解密的密钥是相同的,因此必须向接收者配送密钥。用于解密的密钥必须被配送给接收者,这一问题称为 密钥配送问题 ,如果使用公钥密码,则无需向接收者配送用于解密的密钥,这样就解决了密钥配送问题。可以说公钥密码是密码学历史上最伟大的发明。
解决密钥配送问题的方法
在人数很多的情况下,通信所需要的密钥数量会增大,例如:1000名员工中每一个人都可以和另外999个进行通信,则每个人需要999个通信密钥,整个密钥数量:
1000 x 999 ÷ 2 = 499500
很不现实,因此此方法有一定的局限性
在Diffic-Hellman密钥交换中,进行加密通信的双方需要交换一些信息,而这些信息即便被窃听者窃听到也没有问题(后续文章会进行详解)。
在对称密码中,加密密钥和解密密钥是相同的,但公钥密码中,加密密钥和解密密钥却是不同的。只要拥有加密密钥,任何人都可以加密,但没有解密密钥是无法解密的。
公钥密码中,密钥分为加密密钥(公钥)和解密密钥(私钥)两种。
公钥和私钥是一一对应的,一对公钥和私钥统称为密钥对,由公钥进行加密的密文,必须使用与该公钥配对的私钥才能够解密。密钥对中的两个密钥之间具有非常密切的关系——数学上的关系——因此公钥和私钥是不能分别单独生成的。
发送者:Alice 接收者:Bob 窃听者:Eve
通信过程是由接收者Bob来启动的
公钥密码解决了密钥配送的问题,但依然面临着下面的问题
RSA是目前使用最广泛的公钥密码算法,名字是由它的三位开发者,即Ron Rivest、Adi Shamir和Leonard Adleman的姓氏的首字母组成的(Rivest-Shamir-Adleman)。RSA可以被使用公钥密码和数字签名(此文只针对公钥密码进行探讨,数字签名后续文章敬请期待)1983年在美国取得了专利,但现在该专利已经过期。
在RSA中,明文、密钥和密文都是数字,RSA加密过程可以用下列公式来表达
密文 = 明文 E mod N
简单的来说,RSA的密文是对代表明文的数字的 E 次方求mod N 的结果,换句话说:将明文和自己做 E 次乘法,然后将结果除以 N 求余数,这个余数就是密文。
RSA解密过程可以用下列公式来表达
明文 = 密文 D mod N
对表示密文的数字的 D 次方求mod N 就可以得到明文,换句话说:将密文和自己做 D 次乘法,在对其结果除以 N 求余数,就可以得到明文
此时使用的数字 N 和加密时使用的数字 N 是相同的,数 D 和数 N 组合起来就是RSA的解密密钥,因此 D 和 N 的组合就是私钥 。只要知道 D 和 N 两个数的人才能够完成解密的运算
根据加密和解密的公式可以看出,需要用到三个数—— E 、 D 和 N 求这三个数就是 生成密钥对 ,RSA密钥对的生成步骤如下:
准备两个很大的质数 p 和 q ,将这两个数相乘,结果就是 N
N = p x q
L 是 p-1 和 q-1 的最小公倍数,如果用lcm( X , Y )来表示 “ X 和 Y 的最小公倍数” 则L可以写成下列形式
L = lcm ( p - 1, q - 1)
E 是一个比1大、比 L 小的数。 E 和 L 的最大公约数必须为1,如果用gcd( X , Y )来表示 X 和 Y 的最大公约数,则 E 和 L 之间存在下列关系:
1 E L
gcd( E , L ) = 1 (是为了保证一定存在解密时需要使用的数 D )
1 D L
E x D mod L = 1
p = 17
q = 19
N = p x q = 17 x 19 = 323
L = lcm ( p - 1, q - 1) = lcm (16,18) = 144
gcd( E , L ) = 1
满足条件的 E 有很多:5,7,11,13,17,19,23,25,29,31...
这里选择5来作为 E ,到这里我们已经知道 E = 5 N = 323 这就是公钥
E x D mod L = 1
D = 29 可以满足上面的条件,因此:
公钥: E = 5 N = 323
私钥: D = 29 N = 323
要加密的明文必须是小于 N 的数,这是因为在加密运算中需要求 mod N 假设加密的明文是123
明文 E mod N = 123 5 mod 323 = 225(密文)
对密文225进行解密
密文 D mod N = 225 29 mod 323 = 225 10 x 225 10 x 225 9 mod 323 = (225 10 mod 323) x (225 10 mod 323) x (225 9 mod 323) = 16 x 16 x 191 mod 323 = 48896 mod 323 = 123(明文)
如果没有mod N 的话,即:
明文 = 密文 D mod N
通过密文求明文的难度不大,因为这可以看作是一个求对数的问题。
但是,加上mod N 之后,求明文就变成了求离散对数的问题,这是非常困难的,因为人类还没有发现求离散对数的高效算法。
只要知道 D ,就能够对密文进行解密,逐一尝试 D 来暴力破译RSA,暴力破解的难度会随着D的长度增加而加大,当 D 足够长时,就不能再现实的时间内通过暴力破解找出数 D
目前,RSA中所使用的 p 和 q 的长度都是1024比特以上, N 的长度为2048比特以上,由于 E 和 D 的长度可以和N差不多,因此要找出 D ,就需要进行2048比特以上的暴力破解。这样的长度下暴力破解找出 D 是极其困难的
E x D mod L = 1 L = lcm ( p - 1, q - 1)
由 E 计算 D 需要使用 p 和 q ,但是密码破译者并不知道 p 和 q
对于RSA来说,有一点非常重要,那就是 质数 p 和 q 不能被密码破译这知道 。把 p 和 q 交给密码破译者与把私钥交给密码破译者是等价的。
p 和 q 不能被密码破译者知道,但是 N = p x q 而且 N 是公开的, p 和 q 都是质数,因此由 N 求 p 和 q 只能通过 将 N 进行质因数分解 ,所以说:
一旦发现了对大整数进行质因数分解的高效算法,RSA就能够被破译
这种方法虽然不能破译RSA,但却是一种针对机密性的有效攻击。
所谓中间人攻击,就是主动攻击者Mallory混入发送者和接收者的中间,对发送者伪装成接收者,对接收者伪装成发送者的攻击,在这里,Mallory就是“中间人”
这种攻击不仅针对RSA,而是可以针对任何公钥密码。在这个过程中,公钥密码并没有被破译,所有的密码算法也都正常工作并确保了机密性。然而,所谓的机密性并非在Alice和Bob之间,而是在Alice和Mallory之间,以及Mallory和Bob之间成立的。 仅靠公钥密码本身,是无法防御中间人攻击的。
要防御中间人攻击,还需要一种手段来确认所收到的公钥是否真的属于Bob,这种手段称为认证。在这种情况下,我们可以使用公钥的 证书 (后面会陆续更新文章来进行探讨)
网络上很多服务器在收到格式不正确的数据时都会向通信对象返回错误消息,并提示“这里的数据有问题”,然而,这种看似很贴心的设计却会让攻击者有机可乘。 攻击者可以向服务器反复发送自己生成的伪造密文,然后分析返回的错误消息和响应时间获得一些关于密钥和明文的信息。
为了抵御这种攻击,可以对密文进行“认证”,RSA-OAEP(最优非对称加密填充)正是基于这种思路设计的一种RSA改良算法。
RSA-OAEP在加密时会在明文前面填充一些认证信息,包括明文的散列值以及一定数量的0,然后用RSA进行加密,在解密的过程中,如果解密后的数据的开头没有找到正确的认证信息,则可以判定有问题,并返回固定的错误消息(重点是,不能将具体的错误内容告知开发者)
RSA-OAEP在实际应用中,还会通过随机数使得每次生成的密文呈现不同的排列方式,从而进一步提高安全性。
随着计算机技术的进步等,以前被认为是安全的密码会被破译,这一现象称为 密码劣化 ,针对这一点:
如果需要理解RSA的加密原理,需要理解以下理论:
等同于求一元二次方程 23 * d + 192 * y = 1
可以求得其中一解为(d=167,y=-20)
至此就完成了所有的计算
对于上述例子的到公钥(221,23)和私钥(221,167)
在上述的计算过程中一共用到了
上面用到的数中只有公钥部分是公开的,即(221,23)。那么我们是否可以通过公钥来推到出私钥部分,即已知n和e,推到出d?
(1)ed 1(mod (n)),只有知道 (n)才能解出d
(2) (n)= (p) (q)= (p-1) (q-1),只有知道p和q才能得到 (n)
(3)n=p q,就需要对n进行因式分解
那么如果可以对n因式分解就可以求出d,也就意味着私匙被破解
那么RSA加密的可靠性就在于对n因式分解的难度,而现在对一个整数n做因式分解并没有巧妙的算法,只有通过暴力破解计算。在实际应用中的n取值通常在1024位以上,而公开已知的可因式分解的最大数为768位。所以现阶段来说RSA加密是可靠的。
现在我们就可以进行加密和解密了
我们使用上面生成的公钥(221,23)来加密。如果我们需要加密的信息是m( m必须为整数并且m要小于n ),m取56,可以用以下公式求出加密串c:
c (mod n)
10 (mod 221)
可以求出加密后的结果c为10
密钥为(221,167),加密结果c=10,可以使用以下公式求出被加密的信息
m (mod n) 即加密结果的d次方除以n的余数为m
56 (mod 221)
RSA加密属于块加密算法,总是在一个固定长度的块上进行操作。如果被加密的字符串过长,则需要对字符串进行切割,如果字符串过短则需要进行填充。
以下主介绍一下RSA_PKCS1_PADDING填充模式以及RSA_NO_PADDING模式
此填充模式是最常用的填充模式,在此填充模式下输入的长度受加密钥的长度限制,输入的最大长度为加密钥的位数k-11。如果公钥的长度为1024位即128字节,那么输入的长度最多为128-11=117字节。如果长度小于117就需要填充。如果输入T的长度为55字节,填充后的块为EM,则EM格式如下:
EM= 0x00 || BT || PS || 0x00 || T
在此填充模式下,输入的长度最多和RSA公钥长度一样长,如果小于公钥长度则会在前面填充0x00。如果公钥长度是128字节,输入T的长度为55字节,填充后的块为EM,则EM格式如下:
EM=P || T
参考:
RSA加密是一种非对称加密。可以在不直接传递密钥的情况下,完成解密。这能够确保信息的安全性,避免了直接传递密钥所造成的被破解的风险。是由一对密钥来进行加解密的过程,分别称为公钥和私钥。公钥加密--私钥解密,私钥加密--公钥解密
在 整数 中, 离散对数 是一种基于 同余 运算和 原根 的一种 对数 运算。而在实数中对数的定义 log b a 是指对于给定的 a 和 b ,有一个数 x ,使得 b x = a 。相同地在任何群 G 中可为所有整数 k 定义一个幂数为 b K ,而 离散对数 log b a 是指使得 b K = a 的整数 k 。
当3为17的 原根 时,我们会发现一个规律
对 正整数 n,欧拉函数是小于或等于n的正整数中与n 互质 的数的数目(因此φ(1)=1)。有以下几个特点
服务端根据生成一个随机数15,根据 3 15 mod 17 计算出6,服务端将6传递给客户端,客户端生成一个随机数13,根据 3 13 mod 17 计算出12后,将12再传回给服务端,客户端收到服务端传递的6后,根据 6 13 mod 17 计算出 10 ,服务端收到客户端传递的12后,根据 12 15 mod 17 计算出 10 ,我们会发现我们通过 迪菲赫尔曼密钥交换 将 10 进行了加密传递
说明:
安全性:
除了 公钥 用到 n 和 e ,其余的4个数字是 不公开 的(p1、p2、φ(n)、d)
目前破解RSA得到的方式如下:
缺点
RSA加密 效率不高 ,因为是纯粹的数学算法,大数据不适合RSA加密,所以我们在加密大数据的时候,我们先用 对称加密 算法加密大数据得到 KEY ,然后再用 RSA 加密 KEY ,再把大数据和KEY一起进行传递
因为Mac系统内置了OpenSSL(开源加密库),所以我们开源直接在终端进行RSA加密解密
生成RSA私钥,密钥名为private.pem,密钥长度为1024bit
因为在iOS中是无法使用 .pem 文件进行加密和解密的,需要进行下面几个步骤
生成一个10年期限的crt证书
crt证书格式转换成der证书
RSA加密是非对称加密的算法
A向B发送信息通过RSA用公开密钥对A明文进行加密
之后发送给B
B通过密钥对A发来的信息进行解密
其中这个密钥是不公开的
所以RSA的保密性
完整性都很好
如果用一段已经知道的明文,经过公钥加密,得到密文。现在已知明文密文和n, 是不是就可以通过解密的公式不断的幂运算求出私钥d呢?
前几天看到一句话,“我们中的很多人把一生中最灿烂的笑容大部分都献给了手机和电脑屏幕”。心中一惊,这说明了什么?手机和电脑已经成为了我们生活中的一部分,所以才会有最懂你的不是你,也不是你男朋友,而是大数据。
如此重要的个人数据,怎样才能保证其在互联网上的安全传输呢?当然要靠各种加密算法。说起加密算法,大家都知道有哈希、对称加密和非对称加密了。哈希是一个散列函数,具有不可逆操作;对称加密即加密和解密使用同一个密钥,而非对称加密加密和解密自然就是两个密钥了。稍微深入一些的,还要说出非对称加密算法有DES、3DES、RC4等,非对称加密算法自然就是RSA了。那么当我们聊起RSA时,我们又在聊些什么呢?今天笔者和大家一起探讨一下,有不足的地方,还望各位朋友多多提意见,共同进步。
RSA简介:1976年由麻省理工学院三位数学家共同提出的,为了纪念这一里程碑式的成就,就用他们三个人的名字首字母作为算法的命名。即 罗纳德·李维斯特 (Ron Rivest)、 阿迪·萨莫尔 (Adi Shamir)和 伦纳德·阿德曼 (Leonard Adleman)。
公钥:用于加密,验签。
私钥:解密,加签。
通常知道了公钥和私钥的用途以后,即可满足基本的聊天需求了。但是我们今天的主要任务是来探究一下RSA加解密的原理。
说起加密算法的原理部分,肯定与数学知识脱不了关系。
我们先来回忆几个数学知识:
φn = φ(A*B)=φ(A)*φ(B)=(A-1)*(B-1)。
这个公式主要是用来计算给定一个任意的正整数n,在小于等于n的正整数中,有多少个与n构成互质的关系。
其中n=A*B,A与B互为质数,但A与B本身并不要求为质数,可以继续展开,直至都为质数。
在最终分解完成后,即 φ(N) = φ(p1)*φ(p2)*φ(p3)... 之后,p1,p2,p3都是质数。又用到了欧拉函数的另一个特点,即当p是质数的时候,φp = p - 1。所以有了上面给出的欧拉定理公式。
举例看一下:
计算15的欧拉函数,因为15比较小,我们可以直接看一下,小于15的正整数有 1、2、3、4、5、6、7、8、9、10、11、12、13、14。和15互质的数有1、2、4、7、8、11、13、14一共四个。
对照我们刚才的欧拉定理: 。
其他感兴趣的,大家可以自己验证。
之所以要在这里介绍欧拉函数,我们在计算公钥和私钥时候,会用到。
如果两个正整数m 和 n 互质,那么m 的 φn 次方减1,可以被n整除。
其中 .
其中当n为质数时,那么 上面看到的公式就变成了
mod n 1.
这个公式也就是著名的 费马小定理 了。
如果两个正整数e和x互为质数,那么一定存在一个整数d,不止一个,使得 e*d - 1 可以被x整除,即 e * d mode x 1。则称 d 是 e 相对于 x的模反元素。
了解了上面所讲的欧拉函数、欧拉定理和模反元素后,就要来一些化学反应了,请看图:
上面这幅图的公式变化有没有没看明白的,没看明白的咱们评论区见哈。
最终我们得到了最重要的第5个公式的变形,即红色箭头后面的:
mod n m。
其中有几个关系,需要搞明白,m 与 n 互为质数,φn = x,d 是e相对于x的模反元素。
有没有看到一些加解密的雏形。
从 m 到 m。 这中间涵盖了从加密到解密的整个过程,但是缺少了我们想要的密文整个过程。
OK,下面引入本文的第四个数学公式:
我们来看一下整个交换流程:
1、客户端有一个数字13,服务端有一个数字15;
2、客户端通过计算 3的13次方 对 17 取余,得到数字12; 将12发送给服务端;同时服务端通过计算3的15次方,对17取余,得到数字6,将6发送给客户端。至此,整个交换过程完成。
3、服务端收到数字12以后,继续计算,12的15次方 对 17取余,得到 数字10。
4、客户端收到数字 6以后,继续计算,6的13次方 对 17 取余,得到数字 10。
有没有发现双方,最终得到了相同的内容10。但是这个数字10从来没有在网络过程中出现过。
好,讲到这里,可能有些人已经恍然大悟,这就是加密过程了,但是也有人会产生疑问,为什么要取数字3 和 17 呢,这里还牵涉到另一个数学知识,原根的问题。即3是17的原根。看图
有没有发现规律,3的1~16次方,对17取余,得到的整数是从1~16。这时我们称3为17的原根。也就是说上面的计算过程中有一组原根的关系。这是最早的迪菲赫尔曼秘钥交换算法。
解决了为什么取3和17的问题后,下面继续来看最终的RSA是如何产生的:
还记得我们上面提到的欧拉定理吗,其中 m 与 n 互为质数,n为质数,d 是 e 相对于 φn的模反元素。
当迪菲赫尔曼密钥交换算法碰上欧拉定理会产生什么呢?
我们得到下面的推论:
好,到这里我们是不是已经看到了整个的加密和解密过程了。
其中 m 是明文;c 是密文; n 和 e 为公钥;d 和 n 为私钥 。
其中几组数字的关系一定要明确:
1、d是e 相对于 φn 的模反元素,φn = n-1,即 e * d mod n = 1.
2、m 小于 n,上面在讲迪菲赫尔曼密钥交换算法时,提到原根的问题,在RSA加密算法中,对m和n并没有原根条件的约束。只要满足m与n互为质数,n为质数,且m n就可以了。
OK,上面就是RSA加密算法的原理了,经过上面几个数学公式的狂轰乱炸,是不是有点迷乱了,给大家一些时间理一下,后面会和大家一起来验证RSA算法以及RSA为什么安全。
产品的开发快则一个月,慢则一年,那么如何杜绝市面上各种山寨也成为了我们必须要关注的问题,加密芯片可以做到这点,在保障开发者权益的同时也保护了消费者权益,KEROS加密芯片作为该领域的领头者,一直在尽力贡献一份力。特点如下:接口:标准I2C协议接口;算法: 标准aes256 / KAS算法;特殊接口:Random Stream Cipher for Interface;工作温度:工业级 -40℃ ~+85℃;频率:400Khz;存储:2K字节EEPROM(可选);电压:1.8V~3.6V;封装:SOT23-6,SOP8,TDFN-6。如何用rsa加密的介绍就聊到这里吧,感谢你花时间阅读本站内容,谢谢。
本文标签:如何用rsa加密