区块链中的密码学系列之非对称密码概述(九)

目录

1. 前言

非对称加密是现代密码学历史上最为伟大的发明,可以很好的解决对称加密需要的提前分发密钥问题。

加密密钥和解密密钥是不同的,通常被人们称为公钥和私钥。这样来做解决了密钥的不安全传输的问题,在不安全的通道上也是可以使用的。但是没有什么是十全十美的,其缺点也是十分明显的。一般比对称加解密算法慢两到三个数量级。

和对称加密算法的安全性保障不同,其基于安全可信的通道。非对称加密算法的安全性是基于数学问题来保障的,目前主要有基于大数质因子分解、离散对数、椭圆曲线等几种思路。

其中比较有代表性的算法是:RSA、ElGamal、椭圆曲线( Elliptic Curve Crytosystems,ECC)系列算法。

RSA算法是经典的公钥算法,利用了对大数进行质因子分解困难的特性。

Diffie-Hellman 密钥交换:基于离散对数无法快速求解,可以在不安全的通道上,双方协商一个公共密钥。

ElGamal由 Taher ElGamal 设计,利用了模运算下求离散对数困难的特性。被应用在PGP 等安全工具中。

椭圆曲线算法( Elliptic curve cryptography,ECC):基于对椭圆曲线上特定点进行特殊乘法逆运算难以计算的特性。ECC系列算法一般认为具备较高的安全性,但是正如我们所知道的那样,安全性越高的算法加解密过程往往比较耗时。

非对称加密由于速度较慢,一般适用于签名或者密钥协商,不适合用在大量数据的加解密。

其实,非对称加密采用了单向陷门函数的原理,其中,RSA采用了大数分解困难的问题,即已知n,很难分解为正确的素数p和q,但是已知p和q,可以很快的求出n。

另外一种单向陷门函数是幂模,其应用比如DH密钥交换。

其中,截图来自我们老师上课的PPT。

2. 数学基础

因子:整数a,b,如果存在m,使a=mb,称为b整除a,记为b a,称b是a的因子。

最大公因子:所有同时整除a和b的整数中,最大的那个,称为a和b的最大公因子,记为(a,b)。

互素:最大公约数等于1。

模运算: 如果 a(mod n) =b (mod n),则称a与b模n同余,记为a≡ bmodn。 同余的性质如下: ① 若n|(a-b), 则a≡b mod n。 ② (a mod n)≡(b mod n), 则a≡b mod n。(同上) ③ a≡b mod n,则b≡a mod n。(交换) ④ a≡b mod n,b≡c mod n,则a≡c mod n。(传递性)

2.1 欧几里得算法

采用递归的思想。

def gcd(a, b):  
	if b == 0:  
		return a
    return gcd(b, a % b)

扩展欧几里得算法

欧几里得算法还有一种高级用法,即在求得和的最大公因子的公式,求出两个系数k1和k2,使得k1a+k2b=(a,b)

只需在欧几里得算法的基础上扩展一下,这就是扩展欧几里得算法。

def egcd(a, b):  
	if b == 0:    
		return a, 1, 0  
	gcd, k1, k2 = egcd(b, a % b) 
    return gcd, k2, k1 - a / b * k2

乘法逆元

当(a,b)=1时,即a,b互素时,有时候我们很希望求得一个数k,0<=k<b,使ka mod b=1,这样的数我们称为a的乘法逆元, 起始这看起来就像是在0到b-1这些整数中找到 的倒数一样。那怎么找到这样的数呢?

扩展欧几里得算法可以帮我们解决这个问题。

由于(a,b)=1,根据扩展欧几里得算法,可求得两个系数k1和k2,使得k1a+k2b=(a,b)=1,所以有 k1a=-k2b+1,所以k1amodb=1,所以(k1modb)amodb=1,而0<=(k1modb)<b,所以k1modb就是我们想要的那个乘法逆元。

定理:

任何整数模n后得到{0,1,…,n-1}中的数,把这个集合记为Zn:={0,1,…,n-1}。

定理 4-1 当(a,n)=1时,存在a的乘法逆元b∈Zn* ,满足ab≡ 1(mod n)。 证明:由于(a,n)=1,所以存在整数b,c满足ba+cn=1,等式两边同时模n即可。

费马定理和欧拉定理: 费马定理(Fermat): 定理4-2 若p是素数,a是整数且(a, p)=1(a,p互素),则

006tKfTcly1g1jok5lkt6j30z006yq4t

证明:由于(a, p)=1,所以{amodp, 2amodp, …,(p-1)amodp}={1,2,…,p-1} 因此, a×2a×…×(p-1)a modp=1×2×…×p-1modp 于是, (p-1)!ap-1≡ (p-1)!modp 两边同乘以(p-1)!模p的逆即可得到 ap-1≡1modp。 Fermat定理也可以写成如下形式: 若p是素数, a是整数且(a, p)=1,则ap≡amodp

## 2.2 欧拉函数

对任意一个正整数 n,在1 到 n的这 n个整数里,显然有些和 n是互素的,而有些和 n是不互素的,那些和 n互素的整数的数量就是 n的欧拉函数,记作φ(n)。那么 φ(n)该怎么计算呢?

我们都知道任意整数n都可以表示成它的所有素因子的乘积:

006tKfTcly1g1jpe5wyblj3076026749

所以所有那些和 n不互素的数,一定和n 有其中某个素因子作为公共因子。

所以我们只要从1到 n中的所有整数中,是p1,p2…ps 的倍数的依次剔除,剩下的就是与n 互素的数。

例如, p1的倍数一共有多少个呢,由于p1的倍数在1到 n中是均匀分布的,所以占据的比例是1/p1 ,剔除p1的倍数后,还剩下n(1-1/p1)个;在剩下的数中,由于p2的倍数在1到n中也是均匀分布的,所以占据的比例是1/p2,所以再剔除p2的倍数后,剩下n(1-1/p1)(1-1/p2)个。以此类推,当把所有素因子的整数倍都剔除后,剩下的数共有n(1-1/p1)(1-1/p2)…(1-1/ps)个。即

006tKfTcly1g1jpfqynokj30a803ewej

由此可见,求欧拉函数的关键在于求出n的的所有素因子,即对n做素因子分解。

素因子分解可以用于加解密。

欧拉定理:

现在要进入最精彩的一个部分——欧拉定理了。欧拉定理是RSA所依赖的直接数学基础。我们先给出欧拉定理的结论,再予以证明。

φ(n)是n的欧拉函数。

当(a,n)=1 时,a^φ(n)≡1(modn)。也就是说,当 a和 n互素时,φ(n)个a相乘再模 n等于1。

我们先把在 1到 n之间,与n互素的那φ(n)个数都列出来,将它们相乘,然后模n,用符号表示如下:

P=x1,x2…xφ(n) mod n,考虑其中任一个 xi,由于它和n互素,而a也和n互素,所以 axi也和 n互素,所以axi mod n 也和n互素。考虑任何两个xi,xj,一定有axi mod n 不等于 axj mod n 。因为若axi mod n 等于 axj mod n ,则 n a(xi-xj),由于a和 n互素,所以n (xi-xj),所以xi≡xj(modn),由于 xi和 xj各不相同,所以xi≡xj(modn)不可能。

也就是说,下列这些元素都与n互素,且两两各不相等。

ax1mod n,x2mod n…xφ(n) mod n.

所以这些元素和x1,x2…xφ(n)是同一拨。

所以如果将这些元素相乘,应当和 P,即

006tKfTcly1g1jprw60lej30v405c759

由于x1,x2…xφ(n)通通与n互素,等式两边可以约去,从而得到a^φ(n)≡1(modn)

006tKfTcly1g1joqfs4fmj31cu0ns7c4

欧拉定理推论

a^kφ(n)≡1(modn),也即a^(kφ(n)+1)≡a(modn)

这个结论就有意思了, a经过若干次幂再模n后又等于a,如果我们能把这个操作拆成两步,第一步不就是相当于加密,第二步不就相当于是解密了吗?

那怎么拆呢?如果我们能找到两个数e和d,使得ed=kφ(n)+1不就可以得到:

a^ed mod n=(a^e mod n)^d mod n

这就相当于做 e次幂模 n是加密,做 d次幂模 n是解密。

哇哦!如果e 和 d不相等,这不就是一种非对称密码吗,加密和解密使用不同的密钥。

可是,怎样找到这样的 e和d 呢?

我们希望找到的 e和 d满足ed=kφ(n)+1其实就是满足:ed mod φ(n)=1

这不就是说e和d互为乘法逆元吗!

因此,我们只需要先找一个 e,使得 e和φ(n)互素,即(e,φ(n))=1,然后再用扩展欧几里得算法求出d不就行啦!

等等,还差一点,还记得我们一开始介绍公钥密码时讲过,公钥密码除了机密和解密的密钥不同之外,还要求除了私钥的拥有者之外的其他人,无法由公钥求出私钥。那怎样才能让已知公钥不能求出私钥呢?

无论是由d求 e或者由e求d,其关键都在于等式ed mod φ(n)=1,如果私钥的拥有者能计算出φ(n) ,而其他人不能求出 φ(n),不就行了吗?

那怎么才能做到这一点呢?还记得我们在介绍欧拉函数时所讲的那个特殊情况了吗?n 等于两个大素数的乘积,那么知道这两个大素数p,q 的人很容易求得欧拉函数,而仅知道n,而不知道那两个素因子 的人就很难求得欧拉函数!

2.3 平方剩余

n是一个正整数, a是一个非零整数, 如果方程 x^2≡amodn有解,则称a是模n的平方剩余,否则称为非平方剩余。 例4-20:x^2≡1mod7有解, x=1, x=6; x^2≡2mod7有解, x=3, x=4; x^2≡3mod7无解; x^2≡4mod7有解, x=2, x=5; x^2≡5mod7无解; x^2≡6mod7无解;

2.4 中国剩余定理CRT

006tKfTcly1g1jqbdmlqtj31240n8whw

2.5 离散对数

根据欧拉定理:如果(a, n)=1,则a^φ(n)≡1 mod n。

更一般的形式:如果(a, n)=1,则至少存在一个整 数m(比如m=φ(n)使得下式成立

a^m ≡ 1 mod n,称满足上述等式最小正整数m为a模n的阶,记为ordn(a) 。

设p为素数,若存在一个正整数α,使得α、α2、…、αp-1关于模p互不同余,则称α为模p的一个原根。于是有如下运算:

α的幂乘运算:y=αx(mod p),1≤x≤p-1

α的对数运算:x=logαy,1≤y≤p-1

 只要p足够大,求解离散对数问题时相当复杂的,并没有比较通用的解法。所以离散对数问题具有较好的单向性。

2.6 幂模

正向计算容易,而反向计算难的一个函数被称为单向陷门函数。幂模正是一种单向陷门函数。

幂模:就是先做一次幂运算,再做一次模运算。g^x mod n = y。

模运算有以下特别好的性质:

(a mod n)* (b mod n) mod n= a*b mod n。也就是说,先模再乘和先乘再模,只要最后都模了同一个模数,结果都是一样的。

交换律:

006tKfTcly1g1jtjc6ernj30n401gglz

单向性:

g^x mod n = y。

已知g和x很容易求出y,已知g和y求x困难。

3. DH密钥交换

由于幂模运算的单向性,离散对数和大整数素因子分解一样都是一种陷门函数,所以同样可以基于幂模运算设计一套公钥密码。

DH算法用于密钥协商,不能用于加密或解密。需要加密的话,可以使用协商出来的对称密钥进行加密。

基于幂模运算的公钥密码:

利用幂模运算的交换律和单向性设计一种密钥协商机制——DH密钥交换。

假设通信双方Alice和Bob需要使用对称密码进行加密通信,对称密码所使用的密钥我们通常称为会话秘钥,那么可以用一下的DH密钥交换过程在不安全的信道上实现会话密钥的安全协商。

第一步,双方协商公共参数g和n;

第二步,Alice和Bob分别在0到n-1之间随机生成xa,xb作为各自的私钥,这个私钥是要保密的;

第三步,Alice和Bob分别计算ya=g^xa mod n,yb=g^xb mod n作为各自的公钥;

第四步,Alice和Bob将各自的公钥发送给对方;

第五步,此时Alice收到了Bob发来的yb,Bob收到了Alice发来的ya,然后分别计算ka=yb^xa mod n,kb=ya^xb mod n,并分别使用ka和kb作为对称密码的密钥。

正确性:

由于幂模运算满足交换律,所以:

006tKfTcly1g1ju39kskhj30d008k3zh

所以,他们协商出的会话密钥一定是相同的!并且,由于xa和xb都是随机生成的,所以还确保了会话密钥的随机性。

4. RSA密码体制

关于RSA的讲解请参考这里。RSA算法

5. 数字签名方案DSA

数字签名方案

6. Rabin密码体制

Rabin利用合数模下求解平方根的困难性构造了一种安全的公钥体制。Rabin公钥体制已经被证明:对该体制的破译的难度等价于大整数分解

Rabin体制是RSA的一种特例,RSA中选取的公开钥e满足1<e<φ(n),且gcd(e, φ(n))=1,而Rabin体制则选择e=2。

下面我们来学习下Rabin体制密钥的产生:

  1. 密钥生成:随机选取两个大素数p,q,在模4下与3同余,即这两个素数的形式为4k+3,以模数n=pq为公钥。

  2. 加密:设m为待加密消息,计算密文c=m^2 mod n, 0<=m<n。

  3. 解密:

006tKfTcly1g1ju6f5s6gj30ei07mt9j

7. ELGamal密码

ELGamal算法

8. 椭圆曲线密码体制

打赏一个呗

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦