密码学学习记录(四)
《图解密码技术》[1]学习记录
对称密码由于解密和加密的密钥相同,无法解决密钥配送问题(key distribution problem)
而解决这个问题的方法有以下几种:
- 通过事先共享密钥
- 通过密钥分配中心
- 通过Diffie-Hellman密钥交换
- 通过公钥密码
解决密钥配送问题的方法
通过事先共享密钥
事先用安全的方法把密钥给对方,称为密钥的事先共享,比如线下给予密钥。
局限性就是如果两个是线上认识的,无法安全传递密钥。
通过密钥分配中心
每次加密通话时,密钥分配中心(Key Distribution Center, KDC)都会生成一个通信密钥,每个人只需要事先和KDC共享密钥即可,步骤大致为:
- 发出通信请求
- KDC随机生成一个会话密钥,用于双方本次通信的临时密钥
- KDC从数据库取出双方密钥
- KDC分别用双方密钥对会话密钥加密,然后发给双方(例如用A的密钥加密会话密钥然后发给A)
- 双方解密得到会话密钥,发送方使用会话密钥加密发送信息
- 接收方使用会话密钥对收到的密文进行解密
- 双方删除会话密钥
局限性:可以看到,由于每个人都需要在KDC事先存储密钥,如果人非常多,导致KDC负荷太大而故障,整个加密通信都会瘫痪;同时,如果入侵者入侵了KDC的计算机,就能得到所有人的密钥,从而能够破译存储密钥的所有人的加密信息。
通过Diffie-Hellman密钥交换
进行加密的双方交换一些信息,然后各种生成相同的密钥,在这个过程中,即使信息被截取到也无法生成和通信双方相同的密钥
通过公钥密码
和对称密码不同,公钥密码的加密和解密密钥是不同的,所以任何人都可以进行加密,但没有解密密钥就无法对其进行解密。这就是公钥密码的一个重要性质:只有拥有解密密钥的人才能进行解密。
公钥密码(public-key cryptography)中,密钥分为加密密钥(public key)和解密密钥两种,分析两者关系可以总结出几个特点:
- 发送者只需要加密密钥
- 接收者只需要解密密钥
- 解密密钥不能被窃听者获取
- 加密密钥被窃听者获取也没问题
加密密钥是公开的,可以公开展示,在任何地方分享,而解密密钥则不能公开,只能自己使用,所以解密密钥一般称作私钥(private key)。私钥不能告诉任何人,包括通信对象。
1978年,Ron Rivest、Adi Shamir 和 Reonard Adlema 共同发表了一种公钥密码算法——RSA,是现在公钥密码的事实标准。
公钥通信流程
在刚开始,A有两个密钥,一个公钥和一个私钥,将公钥发给B,接着B使用A的公钥对消息进行加密,在这个过程中,即使有人获取到公钥也不用担心,使用A的公钥加密后的消息只有A的私钥才能解密,此时B发送的消息被窃听者获取到也无法解密。
其他术语
公钥密码有很多称谓,如非对称密码(asymmetric cryptography)和公钥密码是相同含义。
私钥也有很多其他别名,如 个人密钥、私有密钥、非公开密钥、私密密钥、私有秘密密钥等。
其中公钥和私钥是最普遍的叫法。
RSA
RSA是目前使用最广泛的公钥密钥算法,很多CTF比赛也喜欢出RSA相关的密码学题目。
什么是RSA
RSA是一种公钥密码算法,它的名字是由它的三位开发者的姓氏的首字母组成的(Rivest-Shamir-Adlema)。
1983年,RSA算法在美国取得专利,但该专利已经过期。
RSA加密
RSA的加密流程很简单:
将明文表示的数字和自己相乘E次再对N取模,得到的就是密文,在这个过程中,得到密文需要用到E(Encryption的首字母)和N(Number的首字母),也就是说,E和N的组合就是公钥。
公钥一般写作{E,N}或者(E,N)
注:E和N不是密钥对,E和N组成公钥,密钥对是公钥和私钥的密钥对
RSA解密
解密就和加密一样简单:
也就是将表示密文的数字的D次方求mod N就可以得到明文。
和加密同理,D(Decryption的首字母)和N组成了私钥,这里的N和加密使用的N是相同的。
因为N是公钥的一部分,所以也可以单独将D称为私钥。
密钥对的生成
密钥对的生成步骤如下:
- 求N
- 求L(过程中使用的数)
- 求E
- 求D
(1) 求N
准备两个很大的质数:p和q
使得 $ N=p \times q $ ( p和q为质数)
(2) 求L
在RSA的加密和解密中都未曾出现L,它只出现在生成密钥对的过程中。
L是p-1和q-1的最小公倍数(least common multiple, lcm),令lcm(x,y)表示“x和y的最小公倍数”,则:
(3) 求E
E和L的最大公约数(greatest common divisor, gcd)为1,并且1<E<L
也就是同时具备以下关系:
此时已经有了E和N,即公钥(E,N)
(4) 求D
D是由E计算得出的,D、E和L需要具备如下关系:
D如果满足以上条件,那么就可以解密E和N加密的密文。而\(gcd(E,L)=1\)就是为了确保存在满足条件的D。
RSA加解密示例
生成密钥对
(1) 求N
准备两个质数p、q,例如p = 23, q = 29
(2)求L
(3)求E
这里可以使用欧几里得辗转相除法,如果结果是1,那么就说明两者互质,也就找到了可能的E,核心算法如下:
// 注意 E < L ,所以不需要比较大小
int data = L % E;while (data)
{L = E;E = data;data = L % E;
}
最后的E就是最大公约数。把上面的算法写成函数,使用循环就可以找到一定范围内(小于L)和L互质的E了。
L=308时,可能的E有3、5、9、13、15、17、19、23 ···
这里要注意一下,和L互质的不一定是质数,比如9就不是质数。
令E = 3,则已知E = 3,N = 667,公钥已知。
(4)求D
已知D满足条件:
也就是要找出和E相乘后再mod L = 1的数。
一个循环加一个判断条件很容易就能找到E对应的D,E=3时,D=103。
此时知道私钥为D=103,N=667。
密钥对如下:
公钥:
E = 3
N = 667
私钥:
D = 103
N = 667
加密
要加密的明文所表示的数字必须小于N,也就是小于667(需要mod N)
假设需要加密的明文是233,公钥是E=3,N=667,则:
因此密文就是349
解密
对密文349进行解密,已知私钥D=103,N=667
得到明文233。
较大指数计算再取模的算法可以使用欧拉降幂和快速幂,参考欧拉降幂 | 公式 / 例题分析 / 代码实现-CSDN博客,也可自行搜索学习。
对RSA的攻击
通过密文
$ 密文 = 明文^E \ mod \ N $
求明文相当于求离散对数,目前没有较为高效求离散对数的算法,比较困难。
暴力破解求D
一般RSA使用的p和q都是512比特以上,求D需要进行至少1024比特的暴力破解,比较困难。
通过E和N求D
求D的公式为$ E \times D \ mod \ L = 1$
E和N是已知的,其中$ L = lcm(q-1,p-1) $
因此要求出D需要知道p和q,而$ N = p \times q$
此时不知道p和q因此无法破译(如果知道p和q,那么就和知道D没有区别)
对N进行质因数分解
目前对大整数进行质因数分解的算法都不够高效,如果一旦发现了能够对大整数进行质因数分解的高效算法,RSA算法加密的密文就能够被破译。
推测p和q进行攻击
如果p和q是使用某种简单的伪随机数生成器生成的质数,并且这个伪随机数生成器的算法很差,攻击者就有可能推测出p和q。
中间人攻击
中间人攻击(man-in-the-middle attack)不能破译RSA,但仍然可以获取机密信息(如果可以拦截并且修改信息)
(1)A向B发送消息询问B的公钥
(2)假设M是中间人,M可以拦截和篡改A向B或者B向A发送的消息。
(3)B将自己的公钥发给了A
(4)M拦截了B的消息,保存了B的公钥,然后将自己的公钥发给了A
(5)A使用B的(其实是M的)公钥加密后发送消息:你好
(6)M再次拦截了消息,使用自己的私钥解密获取到消息内容,然后将消息修改为:我不好,接着用B的公钥加密后发送给B
(7)B收到消息后解密看到的内容是:我不好
以上过程可以反复多次,这种中间人攻击可以针对任何公钥密码,为了防御中间人工具,需要认证公钥是否属于B,也就是公钥的证书。
其他公钥密码
ElGamal
ElGamal算法是由Tather ElGamal在1985年提出的,它是一种基于离散对数难题的加密体系,与RAS算法一样,既能用于数据加密,也能用于数字签名。ElGamal算法是基于因数分解,而ElGamal算法是基于离散对数问题。与RSA算法相比,ElGamal算法哪怕是使用相同的私钥,对相同的明文进行加密,每次加密后得到的签名也各不相同,有效的防止了网络中可能出现的重放攻击。特点是密文是明文的两倍长度。
Rabin
Rabin算法是一种基于模平方和模平方根的非对称加密算法,由Michael O. Rabin于1979年提出。它是RSA加密算法的一种变体,但与RSA不同,Rabin算法不是基于单向陷门函数,而是基于计算大整数的模平方根的难度。这意味着对于同一个密文,可能存在多个对应的明文。破解Rabin算法等同于分解大整数,和RAS求N的质因数分解等价,这是一个已知的困难问题。
椭圆曲线密码
椭圆曲线密码学(Elliptic Curve Cryptography, ECC)属于现代非对称密码体系的核心技术,通过将传统离散对数问题(DLP)映射到代数曲线上的有理点群,构建了兼具高安全性和低计算开销的密码系统。相较于RSA算法,ECC通过将曲线上特定点进行特殊的乘法运算实现加密,实现同等安全强度时密钥长度可缩减到1/6。利用了这种乘法运算的逆运算非常困难这一特性。
结城浩. 图解密码技术[M]. 周自恒,译. 第2版. 北京:人民邮电出版社, 2014. ↩︎