您好、欢迎来到现金彩票网!
当前位置:热购彩票app下载 > 公钥 >

RSA加密解密原理深度剖析(附CTF中RSA题型实战分析)

发布时间:2019-05-27 17:20 来源:未知 编辑:admin

  凡是从事信息安全领域的技术人才一定会与密码学打交道,而对于经常参与国内各大CTF大赛的各位技术人员而言密码学也是一个常见的题型,本文章就密码学中的RSA发展、RSA的数学基础理论、RSA的加密解密算法原理、CTF中的RSA题型剖析等多方面进行详细的分析讨论,希望对各位有所帮助。

  1976年,Diffie和Hellman发表了非对称密码的奠基性文章《密码学的新方向》,建立了公钥密码的概念。很多密码学家加入到了解决这个问题的行列当中。1978年,麻省理工学院的Rivest、Shamir和Adleman在他们的论文《获得数学签名和公钥密码系统的一种方法》中,实现了Diffie和Hellman提出的思想的一种算法,简称RSA,即为三个人名字的手字谜的缩写。这三个人中,Rivest和Shamir是计算机学家,负责提出解决方案,Adleman是数学家,负责指出方案的不足,让他们在错误的道路上少浪费时间。Rivest和Shamir花费了一年的时间尝试各种想法,Adleman也花了一年多的时间来一一击破。当他们失望的时候,Rivest终于找到了一种解决方案,这就是我们现在看到的RSA算法。他们获得了2002年的图灵奖。图灵奖是计算机最负盛名、最崇高的一个奖项,有“计算机界的诺贝尔奖”之称。Diffie和Hellman获得了2015年的图灵奖。

  从RSA算法产生到现在,密码学家对该算法的安全性进行了广泛的研究和讨论,并且在实践中有了广泛的应用,比如:数字签名算法、身份认证算法等等,这些算法都是基于大数分解难题的算法(在后面的安全性部分会详细介绍)。

  素数:一个数如果除了1与它本身之外没有其他的因数,那么这个数就被称为素数(或者质数,取自英文单词prime的首字母)。

  设m为正整数,则1,2,3,4…….,m中与m互素的整数的个数记为,叫做欧拉函数,欧拉函数的值叫做欧拉函数值。

  如果存在一个正整数m与两个整数a,b,如果a-b能够被m整除,也就是说m(a-b),那么a和b模m同余。记为:

  在Python中给出了相应的处理函数(这在之后的使用Python进行编码求解相关问题的时候非常重要):

  函数是计算x的y次方,如果z存在,则再对结果进行取模,其结果等效于pow(x,y)%z注意:pow() 通过内置的方法直接调用,内置方法会把参数作为整型,而 math 模块则会把参数转换为 float。

  算法定义:对于不完全为0的非负整数a,b,gcb(a,b)表示a,b的最大公约数,必然存在整数对x,y使得gcd(a,b)=ax+by成立。

  上面的思想是以递归定义的,因为 gcd 不断的递归求解一定会有个时候 b=0,所以递归可以结束。

  注:扩展欧几里得算法是之后RSA在知晓p、q、e的情况下求解d的主要思维算法,请详细了解。

  N:大整数N,我们称之为模数(modulus) p 和 q :大整数N的两个因子(factor) e 和 d:互为模反数的两个指数(exponent) c 和 m:分别是密文和明文,这里一般指的是一个十进制的数还有一个就是n的欧拉函数值,在求解d的时候常用 RSA算法密钥的产生

  (1)选择两个满足需要的大素数p和q,计算n=p*q,,其中是n的欧拉函数值。

  假设Alice是秘密消息的接收方,则只有Alice知道秘密密钥{d,n},所有人都可以知道公开密钥{e,n}。

  如果发送方发送需要保密的消息m给Alice,就选择Alice的公钥{e,n},然后计算,之后把密文c发送给接收方Alice即可。

  接收方Alice收到密文c之后,根据自己掌握的私钥计算,所得结果即为发送方要发送的消息。可以根据上面的“简单保密通信模型”来了解这一个过程。

  通过上面的对RSA的加密解密的简单的解释与描述,可以知道,对于RSA加密解密算法而言,{e,n}为公开密钥,那么破解RSA最直接的方法就是分解整数n,计算n=p*q中的p与q的值,之后计算,通过即可求出d,之后使用{d,n}即可得出加密之前的明文。但是如果密钥的大小过大的话,那么就会产生“大整数分解难题”,从而导致解密失败。说完了“大整数分解难题”之后,下面就来简单的了解一些其他的影响RSA安全性的问题

  (4)p-1与q-1都应该有大的素因子,一般建议选择的两个大素数p、q使得p=2p+1和q=2q+1也是素数。

  分解模数n是最直接的攻击方法,也是最困难的方法。攻击者可以获得公钥e和模数n,如果n=pq被成功分解,则攻击者可以计算出,进而从解得私钥d,之后即可进行解密。

  打开链接后我们可以看到给出了RSA加密之后的密文、加密所用到的e、n的值

  经过上面的操作之后我们的到来p、q、e、d、n、c,那么接下来我就可以求解相应的明文了(将RSAROLL.txt中的{920139713,19}删除并且重新命名为rsa.txt保存在与Show_c.py同一目录下,之后执行以下操作):

  在上面的RSA的安全性保障中曾表名不同用户不可以使用相同的模数n,那么我们下面就来看看如果使用了相同的模数n会有什么情况发生。

  若一个多用户系统中只采用一个模数n,不同的用户拥有不同的e和d,系统将是危险的。在此系统中,若用不同的公钥加密,这些公钥公模且互质,那么该信息无需私钥就可以解密。举例来说,设m为信息明文,两个加密公钥为e1和e2,公共模数是n,有

  如果攻击者得到了n、e1、e2、C1、C2,就可以得到m,因为e1与e2互质,故用欧几里得算法能够找到x和y,满足,假设x为负数,需再使用欧几里得算法来计算则:

  此时有两个员工A与员工B,员工A持有密钥d1,他可以通过解密得到消息m。

  如果此时有一个攻击者,同时监听了员工A、B接收到的密文C1和C2,因为模数不变,以及所有公钥都是公开的,那么利用同模攻击,他就可以在不知道d1、d2的情况下解密得到消息m.

  下载题目中所给出的压缩包之后会发现里面有两个加密之后的文件flag.enc1和flag.enc2以及一个veryhardRSA.py的py文件,在veryhardRSA.py文件中给出了N的值、e1、e2的值,由此确定这个很是符合我们所提到的“公模攻击”

  #由于根据前面的运算,s1是正数,s2是负数,后面需要运算c2的s2次幂。因为在数论模运算中,要求一个数的负数次幂,与常规方法并不一样,比如此处要求c2的s2次幂,就要先计算c2的模反元素c2r,然后求c2r的-s2次幂。

  如果RSA系统的公钥e选取较小的值,可以使得加密和验证签名的速度有所提高,但是如果e的选取太小,就容易受到攻击。

  例如:使用同一个系统的三个用户,分别使用不同的模数n1,n2,n3,但是都选取e=3;另有一个用户欲将同一明文消息m发送给以上三人,使用个人的公钥加密得到:

  一般情况下,n1,n2,n3互素,否则会比较容易求出公因子,从而安全性大幅度的减低,根据中国剩余定理,可以通过C1、C2、C3计算:

  选择密文攻击是指攻击者能选择不同的密文,并拥有对应的明文,由此推出想要的信息。一般攻击者会伪装若干信息,让拥有四亚欧的用户签名,由此获得有用的明文-密文对,然后推算想要的信息,这一个工程量的大小要视情况而定。

  (3)RSATools(Windows下的工具,这个在网上特别多可以随意找)(4)yafu:一个用于分解大整数的工具,可以运行与Windows平台上,语法简单易用操作。

  附加:另外附加一个最近在GitHub上看到一一个非常不错的工具 CTF-RSA-tool,具体的使用方法在文档中读给出了相应的说明。下面是下载地址:

  解题思路:根据 这一欧拉函数式, 可以使用所给的p、q求解出n的欧拉函数值,之后再根据即可求解出d的值。

  可以对已知的n进行大数分解(可以使用在线工具,也可以使用python自己写脚本),之后得到p、q,之后根据,可以求解出n的欧拉函数值

  ,之后根据,求解出d,最后可以根据经过编码求解出c,当然也可以使用RSAtools来操作。

  思路:首先可以对N的十六进制进行转换,将其转换为十进制,之后使用yafu进行分解出p、q(此处在线分解无效,结果集太大),之后求解出d的值,并且将其转换为十六进制。在知道d、n、c的情况下就可以使用python进行编程求解最后的flag了:

  求解d,并且转换十六进制(在第一步的代码之后跟着写就行,不必新建文件):

  求解出n的值,之后再根据,求解出n的欧拉函数的值,之后再根据求解出d的值,之后再根据求解出明文信息即可!

  思路:可能很多人看到这个情形,会觉得不可能解出最后的明文结果,但是对于一些知晓python的Crypto库的人来说这个也许是可行的,通过调用Crypto库中的相关函数模块可以实现对n、e的求解,之后就可以依次进行对n、n的欧拉函数、p、q、d的求解,最后即可求解出明文信息m.

  可以看到n的位数过大,所以推荐使用yafu来进行分解(使用在线分解是可以,但是当位数过多的时候就不行了):

  到目前为止,我们获得了n、e、p、q、c,那么我们就可以求解私钥,之后就可以进行解密了

  在有些情况下你会发现有时候题目中给出的n的值使用在线大整数分解后虽然有结果,但是你看不全,比如下面的这个:

  这时即便是使用yafu、msieve等也长时间无果,那么这个时候你就应该换一换思路,比如说:发现加密的指数比较小、采用了相同的模等等,之后联想一下针对RSA的一些攻击方法来破解,而不是长时间的去想如何实现分解这个数,有时候CTF中的一些题目也会出现一些脑洞题。对于CTF中常常出现的RSA题型而言,解题的思路非常重要,只要你懂的了解题的方法原理,那么在你会一门编程语言的基础之上你就非常容易通过编程进行求解该问题。(强烈推荐Python)

  建议大家不要过于依赖于各种工具,最好还是多熟悉熟悉原理,同时使用python多多编程,这样收获到的会更多,而且在实践中你的CTF中的题型的攻破能力也越来越强。

  在本文中,笔者讲述了RSA的发展、RSA中的数学基础原理、RSA加密解密原理、RSA的安全性问题、RSA在CTF中的各种题型以及对使用到的工具的一些推荐,其中对RSA的加密解密原理以及CTF中的解题思路做了重点分析,希望对各位读者有所帮助!谢谢!

http://e-ndicus.com/gongyue/325.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有