前言

又是打CTF遇到的考点,也不是啥新鲜玩意了,这东西属于密码学的范畴,不过却是学信安的同学必须掌握的内容。今天就来打算好好学学这RSA究竟是个怎样的东西,让CTF考了这么多遍至今仍是一道频率极高的考点。

正文

我们都知道,对于数字届来说,质数无遗是一种十分特殊的存在。他不会被除了1和他自身之外的正整数给整除,即他的因子只有1和他自己。而以目前的计算机算力来说,对于一个由两个1024位长的质数相乘得到的整数,想要反求他是由哪两个质数相乘而来实在困难重重。根据这一特性,RSA加密算法应运而生。

数学基础

想要弄清楚RSA加密原理,就不得不提到一位数学家——欧拉。

这里主要围绕他最经典的欧拉定理来展开

欧拉定理(n为正整数,a为非零整数):

image-20200908223414176

推论1,若m,n为互斥的正整数,则如下式子成立:

image-20200908223630798

推论2:设存在整数a,b满足如下定义:

image-20200908224005384

故ab相乘得到:

image-20200908224148997

可推出:

image-20200908224321011

又因为:

image-20200908224500068

故:

image-20200908224823445

且由于:

image-20200908224938453

故得到:

image-20200908225033382

RSA过程

  1. 选取两个质数pq
  2. 计算n=q*p(RSA密钥位数即为n的二进制表示位数)
  3. 根据公式image-20200908225726707算出大于0小于n且与n互质的整数个数
  4. 选取一个正整数e且与(p-1)*(q-1)互质
  5. 由模反运算求出整数dimage-20200908230244190

此时我们的基本准备工作就做好了。

对于需要加密的明文m来说,可根据如下公式得到密文c

image-20200908230523568

而对于密文c来说,可根据下边的公式得到明文m

image-20200908230624219

公式验证

让我们来证明该方程组的正确性。

由上文的模反运算可得:

image-20200908231346509

故而:

image-20200908231713855

又因为:

image-20200908231936285

所以:

image-20200908232120112

综上所述:

image-20200908232228506

又因为:

image-20200908232928816

进而得到:

image-20200908233112434

我们令:

image-20200908233241743

则可得到:

image-20200908233313770

等式方程组成立。

安全性探讨

在上述方程组中,(n,e)为公钥,(n,d)为私钥。公钥为公开状态,可供用户端进行加解密,私钥为私密状态,供服务端加解密。

对于流量嗅探来说,攻击者获取到受害者发送的流量,此时的数据在上述方程来说为c,除此之外攻击者还知道的值有:n与e

对于式子image-20200908234349434由于无法知道与余数c有关的商为多少,所以也无法得知m^e的值,故而无法求出m

而对于式子image-20200908234513093来说,私钥d是关键,如果d能被攻击者成功找到,那么数据m自然也是轻松算出。

私钥d是有模反运算得出的,由上文,我们知道:

image-20200908231346509

其中k为任意正整数。若想得到私钥d,就得想办法算出image-20200908235018917的值。

其中n在公钥内已给出,而剩下的内容就是计算。

若在已知pq的前提下,由公式:

image-20200908225726707

可以很方便的计算出该值。

若在不知道pq的前提下,则只能通过其定义进行计算与因数分解找出pq两种办法,前者具体指的是找出大于0小于n且与n互质的整数个数。

这两种方法以当前计算机的发展来看,在n极大且未有解的情况下,需要难以估计的计算机算力去花费很长时间运算才有可能计算出来,故而可以认为该值在不知道质数pq值的情况下是不可能算出来的。

故而在不知道私钥d的情况下,可以认为数据m是安全的,无法被窃取与串改。

RSA的应用

SSL证书

关于RSA的应用,我觉得SSL证书肯定是得讲讲的。简单的说,我们的操作系统内部内置由一些权威的CA证书机构的根证书(Root CA)。一个网站如果想要申请SSL证书(CA证书的一种)来保护自己用户的隐私,就需要向这些证书机构的代理商申请/购买证书,并需要验证网站的拥有者权限后才能成功获得SSL证书。

此证书通常包含格式为pem的证书文件(内容证书信息与证书公钥)与格式为key的私钥文件。

网站站长在部署SSL证书时候,当用户访问https://www.example.com/时,首先会判断是否下载过含公钥的证书,若没有下载,则与服务器通信将证书下载回本地。用户浏览器在使用证书里的公钥加密前会通过证书信息的内容向SSL证书发行链向上验证,判断当前SSL证书的合法性,此内容不在本文讨论范畴,感兴趣的读者可自行查阅资料。

当用户证书验证合法之后,浏览器会将流量与公钥进行加密运算,确保传输过程中的数据安全。

APP签名

在一些封闭的手机环境,如IOS。用户无法安装费AppleStore的应用,原因就在于苹果系统内置了一份公钥,而在你想要安装新应用的时候,会去尝试使用这份公钥去解密APP内由AppleStore颁布的签名,此签名由苹果绝密的私钥生成,若签名正确,则代表此应用来自AppleStore,属于正常应用,允许用户安装,否则会禁止用户安装此应用,一定程度上确保用户的手机安全。

后记

非对称算法里边RSA应该算是比较好学习的了,不仅在日常中应用广泛,近年来各种CTF也有相应的题目,可谓是不可不学。由于笔者是个纯web狗,第一次写这类文章,若出现什么错误,欢迎指正,感谢。

参考