Fork me on GitHub

RSA入门

Posted on | Edited on

参考文献：https://www.anquanke.com/post/id/84632

RSA的加密过程

  • 选择两个大素数p和q，计算出模数N = p * q
  • 计算φ = (p−1) * (q−1) 即N的欧拉函数，然后选择一个e(1<e<φ),且e和φ互质
  • 取e的模反数为d，计算方法: e * d ≡ 1 (mod φ)
  • 对明文A进行加密： B = pow(A,e,n)，得到的B即为密文。
  • 对密文B进行解密，A = pow(B,d,n)，得到的A即为明文，这个pow()在python中的gmpy库中有，可以直接用
1
2
3
4
p 和 q ：大整数N的两个因子
N：大整数N，我们称之为模数
e 和 d：互为模反数的两个指数
c 和 m：分别是密文和明文，这里一般指的是一个十进制的数，是16进制数的时候

RSA的算法涉及三个参数，n、e、d。

  • 其中，n是两个大质数p、q的积，n以二进制表示时所占用的位数，就是所谓的密钥长度。
  • e和d是一对相关的值，e可以任意取，但要求e与(p-1)(q-1)互质；再选择d，要求(ed) ≡ 1(mod(p-1)×(q-1))。
  • 令φ = (p-1)(q-1),上式即 d*e = 1 mod φ即：(d*e - 1)% φ = 0
    *（n，e),(n，d)就是密钥对。其中(n，e)为公钥，(n，d)为私钥。RSA加解密的算法完全相同，设A为明文，B为密文，则：A≡B^d( mod n)；B≡A^e (mod n)；
  • e和d可以互换使用，即：A≡B^e (mod n)；B≡A^d( mod n);

实验吧ctf的RSA的题

1.RSA实践
嗯，用工具RSA-Tool 2 by tE!（没有就自己下啊），至于E为啥子是11而不是题目上给的17，因为17出来的结果提交不对，公钥进制工具默认是hex不是十进制，需要将10进制17转换为16进制的11

2.RSAROLL
题目给的{920139713,19}，则n是920139713，在http://www.atool.org/quality_factor.php或者http://factordb.com这个网址上可以分解出两个质数pq，然后用pqe求出d，再用密文nd求出每个明文，最后合并下就行了，直接python脚本跑下就行了

1
2
3
4
5
6
7
8
9
import gmpy2
N,p,q,e=920139713,18443,49891,19
d=gmpy2.invert(e,(p-1)*(q-1))
res=[]
with open("1.txt")as f:
    f.readline()
    for i in f:
        res.append(chr(pow(int(i),d,N)))
    print ("".join(res))

3.rsarsa
其实挺简单的，贴下代码

1
2
3
4
5
6
7
8
9
10
11
# -*- coding: UTF-8 -*-
import gmpy2
p =9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q =11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
n = p*q
e =65537
c=83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034
d=gmpy2.invert(e,(p-1)*(q-1))
print ("d：",d)
key=pow(c, d, n)
print ("pwd：",key)

4.warmup
这道题真的是神烦，下载下来是个txt文件和pub文件，打开pub文件能看到是一个公钥文件，这是用openssl加密过的一段密码，直接kali解下

1
openssl rsa -pubin -text -modulus -in warmup.pub

  • 然后解开之后有点蒙，完全不知道啥是啥，有Modulus：和Exponent：两个模块，后来看了下大佬的wp知道了前者是N，后者是E，知道了N和E就可以求d了，用github中https://github.com/pablocelayes/rsa-wiener-attack这个里面的RSAwienerHacker.py文件来解，但是需要改一下，前面的不用动，把测试函数后面的内容改成下面的内容

  • 然后就能求出d了，求出d之后

其他解密方式

1.利用公约数
两次公钥的加密过程中使用的$n_1$和$n_2$具有相同的素因子，那么可以利用欧几里得算法直接将$n_1$和$n_2$分解,通过欧几里得算法可以直接求出$n_1$和$n_2$的最大公约数p,通常题目给了若干个n，均不相同，并且都是2048bit，4096bit级别，无法正面硬杠，并且明文都没什么联系，e也一般取65537。

  • 例题：
    1
    2
    n1=9051013965404084482870087864821455535159008696042953021965631089095795348830954383127323853272528967729311045179605407693592665683311660581204886571146327720288455874927281128121117323579691204792399913106627543274457036172455814805715668293705603675386878220947722186914112990452722174363713630297685159669328951520891938403452797650685849523658191947411429068829734053745180460758604283051344339641429819373112365211739216160420494167071996438506850526168389386850499796102003625404245645796271690310748804327
    n2=13225948396179603816062046418717214792668512413625091569997524364243995991961018894150059207824093837420451375240550310050209398964506318518991620142575926623780411532257230701985821629425722030608722035570690474171259238153947095310303522831971664666067542649034461621725656234869005501293423975184701929729170077280251436216167293058560030089006140224375425679571181787206982712477261432579537981278055755344573767076951793312062480275004564657590263719816033564139497109942073701755011873153205366238585665743

通过直接分解，上factordb都分解失败。通过尝试发现：

1
print gcd(n1,n2)

打印出：

1
1564859779720039565508870182569324208117555667917997801104862601098933699462849007879184203051278194180664616470669559575370868384820368930104560074538872199213236203822337186927275879139590248731148622362880471439310489228147093224418374555428793546002109

即为两个n共有的素因子p，然后进一步求出q。

2.Fermat方法与Pollard rho方法
在p，q的取值差异过大，或者p，q的取值过于相近的时候，Format方法与Pollard rho方法都可以很快将n分解成功。可直接使用开源项目yafu将其自动化，不论n的大小，只要p和q存在相差过大或者过近时，都可以通过yafu很快地分解成功。

3.低加密指数攻击
在RSA中e也称为加密指数。由于e是可以随意选取的，选取小一点的e可以缩短加密时间，但是选取不当的话，就会造成安全问题。
当e=3时，如果明文过小，导致明文的三次方仍然小于n，那么通过直接对密文三次开方，即可得到明文。

4.低加密指数广播攻击
如果选取的加密指数较低，并且使用了相同的加密指数给一个接受者的群发送相同的信息，那么可以进行广播攻击得到明文。即，选取了相同的加密指数e（这里取e=3），对相同的明文m进行了加密并进行了消息的传递。
一般来说都是给了三组加密的参数和明密文，其中题目很明确地能告诉这三组的明文都是一样的，并且e都取了一个较小的数字。

5.低解密指数攻击
e看起来很大就行了。通过Wiener Attack可以在多项式时间中分解n。

6.共模攻击
如果在RSA的使用中使用了相同的模n对相同的明文m进行了加密，那么就可以在不分解n的情况下还原出明文m的值。
此时不需要分解n，不需要求解私钥，如果两个加密指数互素，就可以通过共模攻击在两个密文和公钥被嗅探到的情况下还原出明文m的值。
若干次加密，每次n都一样，明文根据题意也一样。

  • 如果已知：n1，n2，c1，c2，e1，e2，并且其中n1=n2的话：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    s = egcd(e1, e2)
     s1 = s[1]
     s2 = s[2]
       print s
     n=n1
       if s1<0:
         s1 = - s1
         c1 = modinv(c1, n)
       elif s2<0:
         s2 = - s2
         c2 = modinv(c2, n)
     m=(pow(c1,s1,n)*pow(c2,s2,n)) % n
-------------本文结束感谢您的阅读-------------