RSA算法原理详解

栏目: 编程工具 · 发布时间: 5年前

内容简介:如果两个或两个以上的整数的最大公约数是 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=bb=a%b ,进行相同欧几里得扩展算法,然后压栈。此时不知道x、y,所以x、y还是初始值
  • 当碰到一个特例 b=0 时,因为0与任何数的公约数是该数本身。即,当 b=0 时,a * 1 + 0 * 0 = a,也就是说x=1,y=0。
  • 得到 x=1y=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=>0y=-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、随机选择两个不相等的大质数 pq 。假设我们取
p=61,q=53
复制代码
  • 2、计算 pq 的乘积 nn 的二进制长度是 密钥长度 ,一般是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=kpM=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=kpn=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位就够了。位数越多加解密消耗的性能越高。


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

新机器的灵魂

新机器的灵魂

Tracy Kidder / 龚益、高宏志 / 机械工业出版社华章公司 / 2011-10 / 45.00元

计算机从1981年开始发生巨大的变化。《新机器的灵魂》完整地记录下了当时一家公司齐心协力把一种新的小型计算机推向市场的过程中所发生的一系列戏剧性的、充满戏剧色彩的、激动人心的故事。 本书以美国通用数据公司研制鹰电子计算机的全过程为主线,对美国计算机工业的发展和管理中鲜为人知的侧面,作了条理清晰、颇具诗情画意的描述。 你想知道一代新型计算机怎样诞生,精明干练而又富于幽默感的工程技术人员怎......一起来看看 《新机器的灵魂》 这本书的介绍吧!

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具