内容简介:如果两个或两个以上的整数的最大公约数是 1,则称它们为互质的两个数,有如下性质
质数
(Prime number)又称 素数
,指在大于1的自然数中,除了1和该数自身外,无法被其他自然数整除的数。大于1的自然数若不是素数,则称之为 合数
。
如果两个或两个以上的整数的最大公约数是 1,则称它们为 互质
(也叫互素)。两个整数 a 与 b 互质,记为 a ⊥ 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{ return b == 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实现为:
static func gcdEx(a:Int,b:Int,x:inout Int,y:inout Int)->Int{ if b == 0 { // 递归直到 b == 0 x = 1 y = 0 return a }else{ let r = gcdEx(a:b, b:a % b, x: &x, y: &y) let t = x x = y y = t - a/b * y return r } } 复制代码
计算过程,大致如下:
-
每次取
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) (等式一) 复制代码
我们令
a1 = b0 (等式二) b1 = a0%b0 (等式三) 复制代码
对整数a1、b1,存在x1、y1使得:
a1 * x1 + b1 * y1 = gcd(a1,b1) (等式四) 复制代码
在计算机中,有
a0 % b0 = a0 - (a0/b0) * b0 (等式五) 复制代码
由欧几里得算法有:
gcd(a0,b0) = gcd(b0,a0%b0) (等式六) 复制代码
联立上面六个等式得:
x0 = y1 y0 = x1 - (a0/b0) * y1 复制代码
欧拉函数
欧拉函数的定义
欧拉函数
(Euler' totient function ):用 φ(n)
表示,是小于或等于n的正整数中与n互质的数的数目。
例如小于8的数中,与8互质的有1、3、5、7,一共4个,那么φ(8)=4。
欧拉函数的一些定理
-
当n为1时,
φ(1)=1
。 -
当n为质数时,
φ(n)=n-1
。因为,两个数中较大一个数是质数,则两个数互质。那么质数n与所有小于自己的数互质。而小于n的正整数有n-1个 -
如果整数m、n互质,则
φ(m*n)=φ(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) 复制代码
由上式,我们可以实现一个求欧拉函数的方法:
static func euler(n:Int)->Int{ var n = n var i = 2 var result = Double(n) while i*i <= n { if n % i == 0 { // 如果i是n的因子 result = result * (1.0 - 1.0 / Double(i)) while n % i == 0 { // 除去n所有i因子 n /= i } print("i=\(i) n=\(n) reuslt=\(result)") } i += 1 } // 处理最后一个质因子 result = result * (1 - 1 / Double(n)) return Int(result) } 复制代码
该函数的时间复杂度为 O(sqrt(n))
需要注意的是:
- 计算欧拉函数的核心是找到n所有的质因子,也就是对n进行因数分解
- 由于任何一个合数,它大于sqrt(n)的质因素最多只有一个。我们在函数末尾已经处理了最后一个质因子。所以只需遍历到sqrt(n)即可。
模反元素
模运算
模运算,又称取模、模除,它用 mod
表示,也就是求余数运算。在程序里通常表示为 %
运算符。譬如:
17 mod 5 = 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 (等式一) 复制代码
根据欧几里得扩展算法有:
a * x + n * y = gcd(a,n) (等式二) 复制代码
如果a、n互质,则 gcd(a,n)=1
,那么我们前面的到的二元一次方程必然是有解的,模反元素d存在。
如果 gcd(a,n) != 1
,等式一和二是矛盾的,等式一无解。
模反元素的计算
根据上面的推倒,我们可以得到一个二元一次方程:
a * d + (-k) * n = 1 复制代码
对于这个二元一次方程,我们可以用扩展欧几里得算法求解。
func gcdEx(a:Int,b:Int,x:inout Int,y:inout Int)->Int{ if b == 0 { x = 1 y = 0 return a }else{ // r = GCD(a,b) = GCD(b,a%b) // 递归直到a % b == 0 let r = gcdEx(a:b, b:a % b, x: &x, y: &y) let t = x x = y y = t - a/b * y return r } } 复制代码
则,求整数a对于模数n的模反元素d,即 a*d + (-k)*n = 1
的解,有
static func modularInverse(a:Int,n:Int,d:inout Int,k:inout Int){ var x : Int = 0 var y : Int = 0 _ = gcdEx(a: Int(a), b:Int(n), x: &x, y: &y) d = x k = -y } 复制代码
需要注意的是,这样计算的到的模反元素d有可能是负数,而我们期望的是在整数范围取值。也就是说,我们期望d和k都是大于0的。即 x=d=>0
、 y=-k<=0
而二元一次不定方程的解,不止一个,我们可以根据通解:
x = x0 + (b/gcd)*t y = y0 – (a/gcd)*t 复制代码
找到满足我们预期的最小的一组解,则求a对于同余数n的模反元素
static func modularInverse(a:UInt,n:UInt)->UInt{ var x : Int = 0 var y : Int = 0 _ = gcdEx(a: Int(a), b:Int(n), x: &x, y: &y) if x < 0 || y > 0{ let t0 = ceil((0 - Float(x)) / Float(n)) let t1 = ceil((0 - Float(y)) / Float(a)) let t = Int(max(t0, t1)) x = x + Int(n) * t y = y - Int(a) * t } let d = UInt(x) let k = UInt(-y) print("modular inverse a=\(a) n=\(n) d=\(d) k=\(k)") return 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互质,那么必然存在a对于模数n的模反元素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< e < φ(n),且e与φ(n) 互质。 假设我们选择了17,即
e=17
。(实际应用中,常常选择65537。) -
5、计算e对于φ(n)的模反元素d。
ed ≡ 1 (mod φ(n)) 复制代码
即
17 * d ≡ 1 (mod 3120) <=> 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 mod 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 mod n 复制代码
即:
M = 2790 ^ 2753 % 3233 = 65 复制代码
签名算法
用私钥(d,n)对信息M进行签名,得到签名S
S = M^d mod n 复制代码
相当于用私钥对信息进行加密
验证签名算法
验证算法,先用公钥(e,n)对签名S进行下列运算得到M'
M' = S^d mod n 复制代码
相当于用公钥对签名进行解密
然后对比M和M',如果相等则验证成功
算法的简单证明
那么,如何保证用用私钥解密出来的数就是原来的明文呢。
根据加密规则
C ≡ M^e mod n (等式一) 复制代码
即:
M^e % n = C 复制代码
可以写成:
M^e - kn = C (等式二) 复制代码
将上式带入解密算法:
M ≡ C^d mod n (等式三) 复制代码
有
M ≡ (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 (mod n) (等式四) 复制代码
密钥生成时有:
ed ≡ 1 (mod φ(n)) (等式五) 复制代码
则
ed = hφ(n) + 1 (等式六) 复制代码
将上式带入等式四,有
M^(hφ(n) + 1) = M (mod n) (等式七) 复制代码
化简得
M^hφ(n) = 1 (mod n) (等式八) 复制代码
接下来,分成两种情况证明上面这个式子。
######(1)m与n互质。
因为m与n互质,根据欧拉定理有:
M^φ(n) ≡ 1 (mod n) (等式九) 复制代码
联立等式八、等式九,有
hφ(n) = φ(n) 复制代码
当 h=1
时,等式成立,原式得到证明。
######(2)m与n不是互质关系。
因为M与n不是互质关系,所以M与n必然有大于一得公约数。而n的是质数p与q的乘积,所以n因数只有p、q。那么M与n的p、q之一必然是M与n的公约数。则 M=kp
和 M=kq
,必然有一个成立。
如果M同时是p、q的倍数,那么 M=ln>=n
,与RSA加密对明文的要求 M<n
互斥。所以M对于p、q,肯定是一个的倍数,与另一个互质。
假设M是p的倍数,与q互质,则有
M = kp (等式十) 复制代码
因为M、q互质,由欧拉定理有
M^(φ(q) = 1 (mod q) (等式十一) 复制代码
则:
M^(φ(q) = 1 + l*q 复制代码
两边同时取h次幂,有
(M^(φ(q))^h = (1 + l*q)^h (等式十二) 复制代码
因为对 (1 + l*q)^h
拆分之后,只有第一项 1
不含n,所以
(1 + l*q)^h % q = 1 复制代码
即
(1 + l*q)^h = 1 (mod q) (等式十三) 复制代码
联立等式十二、十三,有
(M^(φ(q))^h = 1 (mod q) (等式十四) 复制代码
令 h=j(p-1)
,并将 M=kp
、 (φ(q)=q-1
带入(等式十四),有
((kp)^(q-1))^(j(p-1)) ≡ 1 mod q (等式十五) 复制代码
将 φ(n)=(p-1)(q-1)
带入上式,有
kp^jφ(n) ≡ 1 mod q => kp^(jφ(n) + 1) ≡ kp (mod q) 复制代码
有上面的等式六,有 jφ(n) + 1 = ed
,带入上式,得
kp^ed = kp (mod q) 复制代码
则
kp^ed = tq + kp (等式十六) 复制代码
两边同时对p取模,
kp^ed % p = tq % p + kp % p 复制代码
得
tq % p = 0 复制代码
因为p、q互质,所以t必然是p的倍数,即
t = rq 复制代码
带入等式十六
kp^ed = rpq + kp 复制代码
因为 M=kp
、 n=pq
,所以:
M^ed = rn + M => M^ed ≡ M (mod n) 复制代码
在生成密钥时
ed ≡ 1(modφ(n)) => ed=hφ(n)+1 复制代码
则
M^(hφ(n)+1) ≡ M (mod n) 复制代码
则
M^hφ(n) ≡ 1 (mod n) 复制代码
最后证明等式八成立,原式得以证明。
算法的安全性
(n,e)作为公钥,是可以通过网络公开传播的。最主要是保证私钥(n,d)的安全性。而n是在公钥和私钥中都存在的,那么d就最为关键了。
算法的安全性取决于由(n,e)计算出d的难度。而e我们已经知道,只要求出(n),就能得到d。
前面我们给出了求φ(n)的一种算法,属于暴力破解,它的时间复杂度为 O(sqr(n))
。看似很简单,也很快,但是n每增加一位时间复杂度会指数增长,想象一下当n达到1024位时,需要的算力是多么恐怖。
而对极大数进行质因数分解,至今还是世界级难题。
即便是超级计算机,也很难有效对两个质数相乘得到的合数进行质因数分解,所以这样的原理可以用于加密算法。
当合数所有的因子都很大时,采用强力方式得到具体的因子是很困难的,而这也正是 RSA体制理论的核心。
截止2000年,RSA模数分解的最大位数是768位。
截至目前,分解 1024 bit 以上的 RSA number 仍然是一项耗资巨大的工程难题,大整数分解问题仍然被认为是困难的。
所以,目前来说普通应该场景采用1024位的是相对安全的,一些比较机密的场景需要采用2048位。
我们可以在苹果的钥匙串中看到,大部分RSA整数基本都已经是2018。而通常我们应用时大多采用1024位就够了。位数越多加解密消耗的性能越高。
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。