rsa算法 RSA算法原理详解

一些相关的数学概念

在理解RSA算法之前，必须先了解一些相关的数学概念。

素数和互素数

素数，也称素数，是指除了1和数本身以外，不能被其他自然数整除的数。大于1的自然数，如果不是素数，就叫做合数。

如果两个或两个以上整数的最大公约数为1，则称为互质。两个整数a和b互为素数，表示为⊥ b

两个互素数具有以下性质

整数a和b互为素数当且仅当存在整数x和y，使得xa+yb=1。

也就是说，如果a和b互为素数，那么xa+yb=1一定有解。如果xa+yb=1有解，那么A和B一定是互素数；如果xa+yb=1无解，那么A和B一定不是互素。

这个性质涉及到扩展的欧氏算法，我们后面会提到。

相互质量的判别方法主要包括:

两个不同的质数一定互质。例如，2与7、13与19。较大的数是质数，则两数互质。如33与51一个素数，另一个不为它的倍数，这两个数互质。例如，3与10、5与 26。相邻两个自然数互质。即，如果p是大于1整数，则p与p-1、p+1互质。如15与16、14互质相邻两个奇数互质。如19与21、17互质扩展欧几里得算法

扩展的欧氏算法可以用来计算反模元素，并证明一些性质。

欧几里德算法

欧几里得算法，又叫捻转和捻转除法，是求最大公约数的算法。

假设

a= q*b + r

其中a、b、q和r是整数，gcd是计算公约数的函数，那么

gcd(a，b) = gcd(b，r)

也就是，

gcd(a，b) = gcd(b，a%b)

这样就可以用log(n)的时间复杂度求解A和B的最大公约数。由swift实施为:

func gcd(a:Int，b:Int)->Int{

returnb == 0？a : gcd(a:b，b:a%b)

}

扩展欧几里德算法

扩展欧氏算法的基本过程如下:

对于不完全为0的非负整数A，B，gcd(a，B)来表示A和B的最大公约数，必须有整数对X，Y，这样

a*x + b*y = gcd(a，b)

如果x0和y0是上述二元线性不定方程的解，那么方程的通解为:

x= x0 + (b/gcd)*t

y = y0 –( a/gcd)* t

扩展欧氏算法的计算过程

如果已知任意整数a和b，求未知数x和y，这样:

a*x + b*y = gcd(a，b)

由swift实施为:

静态函数gcdEx(a:Int，b:Int，x:inout Int，y:inout Int)->；Int{

Ifb == 0{ //递归直到b == 0

x = 1

y = 0

返回

}else{

设r = gcdEx(a:b，b:a % b，x:& amp；x，y:& amp；y)

让t = x

x = y

y = t - a/b * y

返回者

}

}

计算过程大致如下:

每次取a=b，b=a%b，进行相同欧几里得扩展算法，然后压栈。此时不知道x、y，所以x、y还是初始值当碰到一个特例b=0时，因为0与任何数的公约数是该数本身。即，当b=0时，a * 1 + 0 * 0 = a，也就是说x=1，y=0。得到x=1、y=0之后，依次出栈。如果栈顶的解为x1、y1，栈下面的一个解（前一个解）为x0、y0，那么两组解有如下关系：

x0= y1

y0= x1 - (a0/b0) * y1

最后栈低出栈，得到原始的a、b的解：x、y

两个解的关系简单证明如下:

对于整数a0，b0，x0，y0的存在使得:

A0 * x0+b0 *y0 = gcd(a0，b0)(公式1)

我们点了

A1= b0(等式2)

B1= a0%b0(等式3)

对于整数a1和b1，x1和y1的存在使得:

A1 * x1+b1 *y1 = gcd(a1，b1)(等式4)

在计算机中，有

A0% b0 = a0-(a0/b0) * b0(等式5)

欧几里得算法是:

Gcd(a0，b0) = gcd(b0，a0%b0)(公式6)

结合以上六个等式:

x0= y1

y0= x1 - (a0/b0) * y1

欧拉函数的定义

欧拉全能函数:用φ(n)表示，是小于等于n的正整数中n为素数的个数。

例如，在小于8的数字中，有4 (1，3，5，7)是8的素数，所以φ(8)=4。

欧拉函数的一些定理

当n为1时，φ(1)=1。当n为质数时，φ(n)=n-1。因为，两个数中较大一个数是质数，则两个数互质。那么质数n与所有小于自己的数互质。而小于n的正整数有n-1个如果整数m、n互质，则 φ(mn)=φ(m)φ(n);也就是说欧拉函数是积性函数当n为奇数时，φ(2n)=φ(n)如果n是质数p的k次幂，则φ(n)=φ(p^k)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。欧拉函数的计算

n表示为几个素数的乘积

n= p1^k1 * p2^k2 * p3^k3...* pn^kn

其中p1、p2、P3...pn都是质数

欧拉函数的一般公式是:

φ(n)= n *(1-1/P1)*(1-1/p2)*(1-1/P3)...*(1-1/pn)

从上面的公式，我们可以实现一种求欧拉函数的方法:

静态函数欧拉(n:Int)->；Int{

varn = n

vari = 2

varresult = Double(n)

whilei * i & lt= n

Ifn% i == 0{ //如果I是N的因子，

结果=结果* (1.0- 1.0/ Double(i))

whien % I = = 0 {//去掉n的所有I因子。

n /= i

}

print(" I =(I)n =(n)reu SLT =(result)")

}

i += 1

}

//处理最后一个定性因素

结果=结果* (1- 1/ Double(n))

returnInt(结果)

}

这个函数的时间复杂度为O(sqrt(n))

应该指出的是:

计算欧拉函数的核心是求N的所有定性因子，即因子分解N。

因为任何复合数，只有一个定性因子大于sqrt(n)。我们已经处理了函数末尾的最后一个定性因素。因此，您只需要遍历sqrt(n)。

模逆元素模运算

模运算又称取模和模除，用mod表示，即求余数运算。在程序中通常表示为% operator。

例如:

17mod5= 17% 5= 2

单元

单位元的定义是任何一个元素和单位元做一些二进制运算后，结果等于原元素。

比如加法的单位元素是0，任意数N加0后，结果还是N。

由此可知，乘法的单位元是1，矩阵乘法的单位元是单位方阵

反元素

如果一个元素x和另一个元素y做一些运算f，结果是运算f的单位元素，那么在这种情况下y是x的反元素。

例如，3的额外元素是-3，因为3+(-3)= 0

3的乘法倒数是1/3，因为3 * 1/3 = 1

模逆元素

模逆元也叫模逆元。

按照我们上面说的反元素，应该是模块化操作下的反元素。模运算的单位元是1，即任意数n有n% 1 = n，那么如果整数a的模逆元是b，那么就有:

a % b = 1 <。= >;a ≡ 1 (mod b)

其实模逆元素在模运算之后有乘法运算，描述的是三个数之前的关系。

，或者可以说是模运算下的乘法逆元

如果整数A到模(同余)N的模逆元是B，那么有

a* b = 1(mod n)

也就是说，如果a和b的乘积，模n的余数是1，即。

(a * b) % n = 1

那么，b是整数a到同余n的模逆元。

例如，当同余为n=5时，整数a=3的反模元素为b=2，因为(3*2)%5=1

必须有一个系数k，这样:

a * b - k*n + 1

这相当于一个二元线性方程:

a * x + n *y = 1

模块化反元素的性质

整数A到模N的模逆元存在的充要条件是A和N是互质的

也就是说，如果a和n互为素数，那么整数a到模n的模逆元必然存在。反之，如果A和N的最大公约数不是1，那么反模元素一定不存在。

简单证明一下:

如果A到模N的模逆元是X，根据我们在前面一节推导的二元线性方程，有

A * x+n *y = 1(等式1)

根据欧几里得展开算法有:

A * x+n *y = gcd(a，n)(公式2)

如果A和N互为素数，那么gcd(a，n)=1，那么我们之前得到的二元线性方程一定有解，反模元素D存在。

If gcd(a，n)！= 1，方程1和2矛盾，方程1无解。

模逆元素的计算

根据以上，我们可以得到一个二元线性方程:

a * d + (-k) *n = 1

对于这个二元线性方程，我们可以用扩展的欧氏算法来求解。

func gcdEx(a:Int，b:Int，x:inout Int，y:inout Int)->Int{

ifb == 0{

x = 1

y = 0

返回

}else{

// r = GCD(a，b) = GCD(b，a%b)

//递归直到a% b == 0

设r = gcdEx(a:b，b:a % b，x:& amp；x，y:& amp；y)

让t = x

x = y

y = t - a/b * y

返回者

}

}

然后，求整数A到模N的反模元素D的解，即ad+(-k)n = 1，有

static func modularInverse(a:Int，n:Int，d:inout Int，k:inout Int){

varx : Int= 0

变化:整数= 0

_ = gcdEx(a: Int(a)，b:Int(n)，x:& amp；x，y:& amp；y)

d = x

k = -y

}

需要注意的是，以这种方式计算的反模元素d可能是负数，但是我们期望取整数范围内的值。也就是说，我们期望d和k都大于0。X = d = >: 0、y =-k & lt；=0

虽然二元线性不定方程有多个解，但我们可以使用一般解:

x= x0 + (b/gcd)*t

y = y0 –( a/gcd)* t

如果我们找到满足我们期望的最小解集，那么对于相同的余数n，我们就会找到A的模逆元。

静态函数modularInverse(a:UInt，n:UInt)->；UInt{

varx : Int= 0

变化:整数= 0

_ = gcdEx(a: Int(a)，b:Int(n)，x:& amp；x，y:& amp；y)

ifx <。0|| y >。0{

设t0 = ceil((0- Float(x)) / Float(n))

设t1 = ceil((0- Float(y)) / Float(a))

让t = Int(max(t0，t1))

x = x + Int(n) * t

y = y - Int(a) * t

}

让d = UInt(x)

让k = UInt(-y)

print(" modular inverse a =(a)n =(n)d =(d)k =(k)")

返回d

}

欧拉定理

欧拉定理，又称费马-欧拉定理，是同余的一个性质。

欧拉定理表明，如果n和a是正整数，n和a互为素数，那么:

a^φ(n) = 1(mod n)

即:

a^φ(n) % n = 1

也就是说，如果A是φ(n)的幂，那么模n得到的余数就是1。

根据欧拉定理:

a* a^(φ(n) - 1) = 1

也就是说，如果整数A和N互为素数，那么对于模N必然存在A的反模元素D。

d= a ^ (φ(n) - 1)

费马理论

费马小定理是欧拉定理的特例。也就是说，当模数n为素数时，此时:

φ(n) = n - 1

然后

a^(n-1) = 1(mod n)

密钥的生成

1.随机选择两个不相等的素数p和q。假设我们

p=61，q=53

2.计算P和Q的乘积n；n的二进制长度为密钥长度，一般为1024位，重要场合为2048位

n= p * q = 61* 53= 3233

3.计算n的欧拉函数φ(n)。

欧拉函数φ(n)是小于或等于n的正整数中n为素数的个数。

一个数的欧拉函数等于它的各种因子的欧拉函数的乘积，即

φ(n) = φ(p*q) = φ(p) *φ(q)

因为一个素数和每一个小于它的数构成一个互素数关系。因此

φ(p) = p - 1

φ(q) = q - 1

然后:

φ(n)=φ(p * q)=φ(p)*φ(q)=(p-1)(q-1)= 60 * 52 = 3120

4.随机选择一个整数e，前提是1

假设我们选择17，即e=17。(实际应用中经常选择65537。)

5.求φ(n)E的模逆元d。

ed≡ 1(mod φ(n))

也就是，

17 * d≡1(mod 3120)lt；= >;17 * d - k * 3120 = 1

用“扩展欧氏算法”解决问题，用我们上面的函数modularInverse(a:n:)计算，最后得到d=2753，k=15

6.将(e，n)封装为公钥，将(d，n)封装为私钥，即公钥(17，3233)和私钥(2753，3233)

编码算法

用公钥(e，n)加密明文m，得到密文c。

C= M^e模n

如果我们假设M=65，我们之前得到的公钥是(17，3233)，那么:

C= 65^17% 3233= 2790

应该指出的是:

1、明文M必须是整数。而使用中M经常是字符串，我们需要转化为相应的ascii值或unicode值，即转化为Data类型进行运算。2、M必须小于n。如果M大于n，我们需要分块进行运算。即如果n是1024位，如果M大于1024位，需要切分成若干小于1024位的块。而后面我们会说到Padding，每块还需要减去Padding的大小。解密算法

用私钥解密密文C，得到明文m。

M= C^d模n

即:

M= 2790^ 2753% 3233= 65

签名算法

用私钥(d，n)对信息M签名，得到签名s。

S= M^d模n

这相当于用私钥加密信息

验证签名算法

验证算法:首先用公钥(e，n)对签名S进行运算，得到M’

S^d mod n

这相当于用公钥解密签名

然后比较m和m’，如果它们相等，则验证成功

算法的简单证明

那么，如何保证用私钥解密的数字是原始明文呢？

根据加密规则

C ≡ m e mod n(等式1)

即:

M^e % n = C

可以写成:

M^e-kn = C(等式2)

将上述公式带入解密算法:

M ≡ c d mod n(公式3)

是

M1^e - kn)^d mod n

然后:

M^(ed) -k^dn^d - k2*n = M

简化

M^(ed) - (k^dn^(d-1) - k2)*n = M

等于

M^(ed) - k3*n = M

也就是问:

M (ed) ≡ m (modn)(公式4)

密钥生成包括:

Ed≡ 1(mod φ(n))(等式5)

然后

Ed= hφ(n)+1(等式6)

把上面的公式带入方程四，有

M (hφ (n)+1) = m (modn)(等式7)

简化

M h φ (n) = 1 (modn)(等式8)

接下来，在两种情况下证明了上述公式。

#####(1)m和n互为素数。

因为m和n互为素数，根据欧拉定理:

M φ (n) ≡ 1 (modn)(等式9)

联立方程8和方程9，有

hφ(n) = φ(n)

当h=1时，方程成立，证明了原公式。

# # # # # #(2)m和N不是素数关系。

因为M和N不是素数，所以M和N必须有大于1的公约数。而n是素数p和q的乘积，所以n的因子只有p和q，那么M和n的p和q中的一个必然是M和n的公约数，那么M=kp，M=kq，必然有一个成立。

如果m是p和q的倍数，那么m = ln >: =n，符合RSA加密对明文m的要求

假设m是p的倍数，并且与q互质，则存在

M= kp(公式10)

因为M和Q是相互定性的，所以属于欧拉定理

M (φ (q) = 1 (modq)(公式11)

然后:

M^(φ(q) = 1 + l*q

双方同时被提升到h的力量，包括

(m (φ (q)) h = (1+l * q) h(公式12)

因为拆分(1+l * q) h后，只有第一项1不包含n，所以

(1 + l*q)^h % q = 1

也就是，

(1+l * q) h = 1 (modq)(公式13)

联立方程12和13，有

(m (φ (q)) h = 1 (modq)(公式14)

设h=j(p-1)，并将M=kp和(φ(q)=q-1带入(等式14)，有

((KP) (q-1)) (j (p-1)) ≡ 1 mod q(公式15)

将φ(n)=(p-1)(q-1)带入上述公式，有

kp^jφ(n) ≡ 1modq = >;kp^(jφ(n)+1)KP(modq)

上面有方程6，有jφ(n)+1 = ed，带入上面的公式，得到

kp^ed = kp (modq)

然后

Kp^ed = tq+kp(公式16)

两侧同时成型p、

kp^ed % p = tq % p + kp % p

必须

tq% p = 0

因为p和q互为素数，所以t必须是p的倍数，即。

t= rq

引入等式16

kp^ed = rpq + kp

因为M=kp，n=pq，所以:

m^ed = rn+m = & gt；M^ed ≡ M(现代n)

当密钥生成时

ed ≡ 1(modφ(n)) = >ed=hφ(n)+1

然后

M^(hφ(n)+1)

然后

m^hφ(n)1(modn)

最后证明了方程8成立，证明了原公式。

算法的安全性

(n，e)作为公钥，可以通过网络公开传播。最重要的是保证私钥(n，d)的安全性。而n同时存在于公钥和私钥中，那么d是最关键的。

算法的安全性取决于从(n，e)计算d的难度。而e我们已经知道，如果找到(n)，就可以得到d。

前面我们给出了一个求φ(n)的算法，属于蛮力破解，时间复杂度为O(sqr(n))。看似简单快速，但当n增加一位时，时间复杂度呈指数级增加。想象一下，当n达到1024位时，计算能力是多么可怕。

但是用素数因子分解最大数还是世界级的问题。

即使是超级计算机也很难对两个素数相乘得到的复合数进行有效的素因子分解，所以这个原理可以用于加密算法中。

当复合数的所有因子都很大时，很难通过强手段获得具体因子，这是RSA系统理论的核心。

到2000年，RSA模分解的最大位数是768位。

到目前为止，分解1024位以上的RSA数仍然是一个代价高昂的工程问题，分解大整数仍然被认为是困难的。

所以目前一般场景使用1024位还是比较安全的，一些比较机密的场景需要2048位。

我们可以在苹果的钥匙扣上看到，大部分的RSA整数基本都是2018。通常我们用的时候1024位就够了。位数越多，加密和解密消耗的性能越高。

参考材料

RSA算法原理（一）RSA算法原理（二）數學上的模逆元模逆元扩展欧几里德算法详解互素-维基百科大数因子分解算法综述RSA算法原理——（3）RSA加解密过程及公式论证

链接:https://juejin.im/post/5d172e916fb9a07ef81a11f1