Digd0g's Blog

RSA加密算法详细解说

发表于 更新于 分类于 ，
本文字数： 783 阅读时长 ≈ 3 分钟
       
-------------已经到底啦！-------------
 

RSA加密算法是一种非对称加密算法,加密由公钥,私钥,明文,密文四部分组成.

取模运算

a mod n ≡ b表示a与b对模n同余(a,b分别除以n)
:::info
举个栗子: 3 mod 2 ≡ 1 <–> 1mod2=1且3mod2=1
:::

欧拉函数

任意给定正整数n，计算在小于等于n的正整数之中，有多少个与n构成互质关系？计算这个值的方法就叫做欧拉函数，以φ(n)表示.

:::info
例如，在1到8之中，与8形成互质关系的是1、3、5、7，所以φ(n)=4
:::

在RSA算法中，欧拉函数对以下定理成立

1.如果n可以分解成两个互质的整数之积，即n=p×q，则有：φ(n)=φ(pq)=φ( p )φ( q );
2.当p为质数，φ( p )=p-1

所以有φ(n)=(p-1)(q-1)

欧拉定理与模反元素

欧拉函数的用处，在于欧拉定理
“欧拉定理”指的是:
如果两个正整数a和n互质，则n的欧拉函数φ(n)可以让下面的等式成立：
a^φ(n)≡1(modn)
也就是说，a的φ(n)次方被n除的余数为1

模反元素的推导过程如下:

根据欧拉定理，有：
a^φ(n) = a × a^(φ(n)−1)≡1(modn)

令b=a^(φ(n)−1)，得：

ab≡1(modn)
:::info
b就是a的模反元素
所以，如果两个正整数a和n互质，那么一定可以找到整数b使得ab-1被n整除，或者说ab被n除的余数是1
:::

[所以求私钥d的公式：d*e≡1mod[(p-1)(q-1)]]{.green}

如何求d

例如我们定义e为17,p=473398607161，q=4511491
为了求出d我们写出如下脚本

1
2
3
4
5
6
7
8
9
# 17x + 2135733082216268400y = 1
def ext_euclid ( a , b ):
    if (b == 0):
        return 1, 0, a
    else:
        x , y , q = ext_euclid( b , a % b )
        x , y = y, ( x - (a // b) * y )
        return x, y, q
print(ext_euclid(17,  2135733082216268400))

由于de≡1mod[(p-1)(q-1)可等价为 de mod (p-1)(q-1)=1
代入e、p、q
所以我们可以把上式看作: 17x+(473398607161-1)(4511491-1)y=1

代入φ(n) = (p-1)(q-1),φ(n) 与e互质，k为正整数
可化为：d= (k*φ(n)+1)/e

1
2
3
4
5
6
公钥    n -->  两素数p、q之积
        e -->  1<e<(p-1)·(q-1)且e与乘积互质
私钥    d -->  d·e ≡ 1 mod[(p-1)·(q-1)]
        n -->  同公钥n
加密    ----->  C ≡ M^e mod(n)   M为明文
解密    ----->  M ≡ C^d mod(n)   C为密文

由p,q,dp,dq,c求明文的算法

1
2
3
4
5
6
7
8
import gmpy2
I = gmpy2.invert(q,p)
mp = pow(c,dp,p)
mq = pow(c,dq,q)               #求幂取模运算

m = (((mp-mq)*I)%p)*q+mq       #求明文公式

print(hex(m))          #转为十六进制

==pow(a,b,c)表示 a^b^ %c 即a^b^ mod c==

数学运算规律

a^b^ %p = ((a%p)^b^)%p
若a≡b(%p),则对任意的c,都有(a+c)≡(b+c)(%p)
若a≡b(%p),则对任意的c,都有(ac)≡(bc)(%p)
若a≡b(%p),对任意的c,都有c≡d(%p),那么(a+c)≡(b+d)(%p),(ac)≡(bd)(%p)

运算推论:参考 https://blog.csdn.net/mikecoke/article/details/105967809?utm_medium=distribute.pc_relevant.none-task-blog-baidujs_title-2&spm=1001.2101.3001.4242