要么改变世界,要么适应世界

公钥密码算法之RSA

2022-08-14 12:45:56
307
目录

本文参考自文章【从0到1:CTFer成长之路】

前言

笼统而言,密码学可以分为古典密码和现代密码阶段,古典密码涉及知识较为简单,容易理解,现代密码融入了大量数论知识,安全性能也大幅提升。

自从科克霍夫原则和对称加密体制被提出后,密码学进入了现代密码阶段。成熟的分组密码、流密码的加密强度和加密效率都非常优秀,然而对称密码体系存在着一个不可忽略的问题——密钥的传输需要一个安全的信道,否则一旦密钥被截获,对称加密就毫无安全性可言。另外,对称加密体制并没有解决信息的认证与不可否认性的问题。

1976年,Whitfield Diffie和Martin Hellman发表了New directions in cryptography这篇划时代的文章,奠定了公钥密码系统的基础,而在1977年,Ron Rivest、Adi Shamir和Leonard Adleman发明了一种直到今天还被广泛运用的公钥密码算法——RSA。

该算法运用的数学原理是:将两个大素数相乘比较简单,但是要把这两个素数的乘积进行因式分解却是及其困难的。

原理

算法开始之前,先选取两个较大的不同素数pq(一般大于512bit,即2^512)。令:

$$ n=pq $$

再求n的欧拉函数:

$$ \varphi (n)=\varphi (p)\varphi (q)=(p-1)(q-1) $$

再选取一个与该欧拉函数值互质的整数e,为了加速运算,通常选一个较小,但不至于太小的素数,如65537。

求得e模$\varphi (n)$的逆元d,即:

$$ ed \equiv 1 \pmod{\varphi (n)} $$

然后<n, e>作为公钥,可以对外公布,不用担心别人窃取,可以用于发送方加密信息;<n, d>作为私钥,用户自己保留,用于解密信息。

RSA系统工作流程如下:

  1. 发送消息双方产生密钥对(公钥和私钥),保留私钥,交换公钥。

  2. 假设阿珍要传输信息给阿强,传输的内容为m,阿强的公钥为<n, e>计算:

$$ c=m^e\pmod{n},其中(0\le m\lt n) $$

  1. 阿珍将c发送给阿强

  2. 阿强收到信息后,计算:

$$ m1=c^d\pmod{n} $$

  1. 可以验证,m1m是相等的。

举个简单的例子:

p=11,q=7,则n=77,再取e=13,则d=37(13 x 37 = 481,481 % 60 = 1),发送的明文为8:

$$ c=8^{13}\pmod{77}=50 $$

解密:

$$ m=50^{37}\pmod{77}=8 $$

下面我们来证明m1m是相等的,即$m=c^d\pmod{n}$,由于m<n,故只要证明:

$$ c^d\equiv m\pmod{n} $$

而加密的时候:

$$ c=m^e\pmod{n} $$

即,只要证:

$$ m^{e*d}\equiv m\pmod{n} $$

因为ed互为逆元,即$ed \equiv 1 \pmod{\varphi (n)}$,则必存在整数k,使得:

$$

ed=k\varphi (n)+1

$$

存在两种情况:

情况1:m和n互素

欧拉定理:若 gcd(a, m) =1,则$ a^{\varphi (m)}\equiv 1\pmod{m} $

m和n互素,有$ gcd(n, m)=1 $,根据欧拉定理,有

$$ m^{\varphi (n)}\equiv 1\pmod{n} $$

即:

$$ m^{ed}\equiv m^{k\varphi (n)+1} \equiv mm^{k\varphi (n)}\equiv m\pmod{n} $$

得证!

情况2:m和n不互素

二者不互素,则最大公约数不为1,由于$m<n$,且$n=pq$,p和q都是素数,且二者不等,故m的因子中必含p或者q中之一,且只含一个而不含另外一个(同时含的话,则$m>=pq=n$,矛盾)。不妨含p,即存在$m=cp$,同时m与q互素,由费马小定理可得:

$$ m^{q-1}\equiv 1\pmod{q} $$

费马小定理:如果q是一个质数,而整数a不是q的倍数,则有$a^{q-1}\equiv 1\pmod{q}$

进一步,有:

$$ m^{k\varphi (n)} \equiv m^{k(p-1)(q-1)}\equiv 1^{k(p-1)}\equiv 1 \pmod{q} $$

即存在一个整数h,使得:

$$ m^{k\varphi (n)}=hq+1 $$

两边同乘以一个m,注意上文中$m=cp$,有:

$$ m^{k\varphi (n)+1}=cp(hq+1)=cphq+m=hcn+m $$

两边模n,有:

$$ m^{k\varphi (n)+1}\equiv m^{ed}\equiv m \pmod{n} $$

综上,解密得到的m1和原来的明文m是相等的。

后记

RSA公钥密码的安全性依赖于大整数因式分解的困难性,如果知道了p和q,很容易求得公钥e关于模$\varphi (n)$的逆元d。如果不知道p和q,按照现在的计算机能力,听说分解一个400位整数需要花费上亿年时间,:D

当p和q是超过两百位的素数时候,可以粗略地说,RSA是暂时安全的。

历史评论
开始评论