非对称加密RSA算法原理及实际应用场景
引言应用场景RSA 算法原理数学基础质数欧拉定理模指数运算小白理解为什么需要足够大的质数引言
我数学差的离谱,所以我朋友去学AI,我还在这搞这些。虽然数学差也能学那些,但是毕竟不想当调包侠,没走那条路。所以本文如果在数学方面有问题,请留言给我,避免误人子弟
。
写这个文章还一个原因就是,最早SMB漏洞
导致恶意利用出来很多勒索病毒
,虽然实际上是通过SMB漏洞
执行的,但是外行并不懂,他们认为勒索病毒=漏洞
,甚至有人让我帮忙解密
,我解个憨憨哟,RSA加密
我拿什么给你解,这篇文章算是科普。
应用场景
对称加密算法有
AES
,DES
,3DES
,RC4
等,加密解密方共用1个密钥
,这就导致了很容易被破解,因为密钥
在客户端中
也存在,无论你如何加密这个字符串,程序跑起来的时候这密钥总会在内存里
。一般情况下,我们会使用
RSA加密
,RSA
使用一个公钥
和一个私钥
,公钥加密
的数据由私钥解密
,私钥加密
的数据由公钥解密
,但是性能会比对称加密算法
要差很多。对于数据量大
的情况,我们可以不加密信息整体
。
我的解决方案
是这样:创建
RSA密钥对
。(服务端保留私钥,客户端保留公钥)创建AES密钥
(服务端客户端共有)动态创建AES IV初始向量
,即每次信息AES
都用不同的IV
加密。使用RSA私钥
加密IV
。使用AES密钥
使用CTR
或OFB
模式加密信息整体
。传递给客户端被加密的AES初始向量IV
和AES加密过的信息整体
。客户端利用RSA公钥
先解密出AES的IV
,再用AES密钥解密信息整体
。这样做的结果就是无论如何你都无法进行
重放
(伪造服务端),因为无法自己造出来AES的IV
,AES的IV
由服务器中的RSA私钥进行加密
且AES的IV
每次随机生成,想要伪造服务端重放唯一的办法是爆破RSA私钥
或hook掉解密AES密钥的地方
或修改公钥
使用自己的密钥,针对hook点
我们做检查
就很容易了,无论是通过线程上下文(int 3)
还是jmp法
或者dr寄存器
,我们只要确保函数首部没被篡改即可,然后再针对公钥那段内存地址做检测。这里说一下为什么动态生成的是
AES的IV
而不是动态生成AES密钥
,因为IV
只需要16字节(128位加密)
,而我们要做的只是为了随机性
。
RSA 算法原理
RSA
建议使用1024bits或以上的长度生成公钥和私钥
,RSA-768 (768 bits, 232 digits) 在被成功分解
,虽然没到1024bits
,我自己建议2048bits
,这个长度每增加1bit难度都会上升2的n+1
次方,至于为什么需要长度这么长的大数呢,看完原理你就知道了。
数学基础
质数
质数
有时被称为素数
,是指在大于1的自然数中
,除了1和它本身
以外不再有其他因数
的自然数。
互质数性质
两个不相同质数
一定是互质
数。相邻
的两个自然数是互质
数。p是大于1
的整数
,则p和p-1
构成互质
关系。相邻
的两个奇数
是互质
数。p是大于1
的奇数
,则p和p-2
构成互质
关系。两个相差4
的奇数
是互质
数。任意两个自然数,大数
是质数
的两个数是互质
数。一个数是质数
,另一个数只要不是前者的倍数
,两者就构成互质
关系。
欧拉定理
计算从1到n
有多少个数与其互质
的方法叫做欧拉函数
,以φ(n)
表示。
欧拉定理
,是一个关于同余的性质
。欧拉定理
表明,若n,a
为正整数
,且n,a互质
,则a^φ(n)≡1(mod n)
。
如果n
是质数
,则φ(n)=n-1
。如果p
为质数
,n
是p
的k 次方
,即φ(n)=φ(p ^ k) = p ^ k - p ^ (k-1)=(p ^ k)( 1 - 1/p )
,比如φ(8) = φ(2 ^ 3) = 2 ^ 3 - 2 ^ 2 = (2 ^ 3)(1 - 1 / 2) = 8 * 0.5 = 4
。如果n
为两个互质的积
.
n = p × q
φ( n ) = φ( pq ) = φ( p )φ( q )
模指数运算
指数运算很简单,取模也很简单,模指数是个啥玩意?
就是先进行指数运算,然后再取模,就叫模指数。
比如 (2^5) mod 4,先进行2的5次方运算,再取模,编程语言中为 pow(2,5)%4,这下看懂了吗。
小白理解
注意:下面的
^
符号是指数运算
,并不是异或运算
,虽然异或运算
也算是简单的加密解密
,但是这里是指数运算
,指数运算
,指数运算
!!!
密文=(明文^e) mod n
。
明文=(密文^d) mod n
。
实际上公钥私钥
就是在算(e,n)
和(d,n)
,其中n是固定的
,只需要求出e
和d
的值。白话就是算出3个值e,d,n
。
我们现在要做的就是算出公钥和私钥对应的指数
与固定模数
。
先找2个足够大
的质数
,p
与q
。计算n = p * q
。计算p-1
和q-1
的最小公倍数(也就是乘积)
,记作l(L不是1)
.计算e
,e
必须满足两个条件
:1 < e < l,e和l互质
。计算d
,d
必须满足两个条件
:e * d mod l = 1
。
为什么需要足够大的质数
从上面我们知道私钥的d
计算就是通过公钥的e
得到的,如果知道公钥(e,n)
,那么就可以进行爆破计算私钥(爆破出p
和q
的值)。
当p
和q
是一个足够大的质数
的时候,从它们的积(p * q)
也就是n
,去分解因子p
和q
,这是一个公认的数学难题。当p
和q
大到1024bits
时,你无法通过n
分解因子得到p
和q
的值。如果爆破不出p
和q
的值,也就无法计算私钥
了。