RSA简介

RSA加密是由罗纳德 · 李维斯特（Ron Rivest）、阿迪 · 萨莫尔（Adi Shamir）和伦纳德 · 阿德曼（Leonard Adleman）共同设计推出的加密算法。按照老师讲的，过程中还有相当多趣闻。不过，今夜我不关心趣闻，我只想你，不，我只想水个wp。

rsa算法加密过程

网上有很多写的，只说下大致思路（凑个字数）：

  1. 选择两个大质数p，q，和公钥指数e；
  2. 得到N=pq和φ(N)=(p-1)(q-1)，并计算 $de\equiv1\pmod{φ(N)}$ ，e和N公开，d藏起来。
  3. 待加密m，计算$c\equiv m^e\pmod{N}$得到加密后c，所以我们把c加密，只需要知道e和N，这就是公钥，
  4. 解密的时候，收到密文c，自己手里d，公开的N，计算
    $m’\equiv c^d\pmod{N}$ 得到m’，那么m和m’为啥相等呢？
  5. 证明：
    对 $de\equiv1\pmod{φ(N)}$，有$de=1+kφ(N)$
    要证明$m=m’$，即证明$m\equiv m’\equiv c^d\equiv(m^e)^d\pmod{N}$
    $\Rightarrow m\equiv m^{ed} \pmod{N}$
    $\Rightarrow m\equiv m^{kφ(N)+1} \pmod{N}$
    由费马定理，有$(m^k)^{φ(N)}\equiv1\pmod N$,
    $\Rightarrow m\equiv m’\pmod N$
    ok证完了。

题目1

N=103461035900816914121390101299049044413950405173712170434161686539878160984549
e=65537
c=67692316911846383515666937548215377516026242122014572162117994514425606283681

数不大，直接factordb分解，得到

p=282164587459512124844245113950593348271
q=366669102002966856876605669837014229419
然后根据流程，算d，求逆有很多方法，gmpy2库就很快

1
2
3
import gymp2
d=gmpy2.invert(e,(p-1)*(q-1))%n
m=pow(m,d,N)

d=91646299298871237857836940212608056141193465208586711901499120163393577626813
m=149691910197844278231054287240052451118322966162813
题目说是字符串，先转16进制，再每两位16进制求其char。

1
2
3
4
5
6
x=hex(m)
flag=''
for i in range(2,len(hex(m)),2):
    flag+=chr(eval('0x'+x[i:i+2]))
print(flag)  
flag{hello_hash_team}

题目2

n = 0xa1d4d377001f1b8d5b2740514ce699b49dc8a02f12df9a960e80e2a6ee13b7a97d9f508721e3dd7a6842c24ab25ab87d1132358de7c6c4cee3fb3ec9b7fd873626bd0251d16912de1f0f1a2bba52b082339113ad1a262121db31db9ee1bf9f26023182acce8f84612bfeb075803cf610f27b7b16147f7d29cc3fd463df7ea31ca860d59aae5506479c76206603de54044e7b778e21082c4c4da795d39dc2b9c0589e577a773133c89fa8e3a4bd047b8e7d6da0d9a0d8a3c1a3607ce983deb350e1c649725cccb0e9d756fc3107dd4352aa18c45a65bab7772a4c5aef7020a1e67e6085cc125d9fc042d96489a08d885f448ece8f7f254067dfff0c4e72a63557L
e1 = 0xf4c1158fL
c1 = 12051796366524088489284445109295502686341498426965277230069915294159131976231473789977279364263965099422235647723775278060569378071469131866368399394772898224166518089593340803913798327451963589996734323497943301819051718709807518655868569656941242449109980876397661605271517459716669684900920279597477446629607627693769738733623143693170696779851882404994923673483971528314806130892416509854017091137325195201225617407959645788145876202882024723106204183257094755002924708009138560347432552090905489132135154932987521239299578509008290614398700799670928805692609756924823628055245227290288940649158862576448537833423L
e2 = 0xf493f7d1L
c2 = 16648382384980770705624348910895797622774711113202207693584907182552301186239613809347201161450012615995859738410661452438496756353485538305614949211776668793864984429696790944750894691957799234264508530084026894611228513698963347402329109838109621609770406925700520983387811451074838470370044678634099202003480925903267508744006195455234025325060817223813858985074720872124168142943926467694676717713503559007112874381750005406371400109962943508349497151148446064846096531445037416174913915923050332242843403926133165817310272633884358263778516770288515592959832151762499526363131801945163501999337808208074381212795L

很大的俩数，有两个e，1个N，意思是用不同的e，加密同一个m，得到了两个c。分解是不可能了，那就百度，然后发现有一个叫共模攻击。

共模攻击

我们知道

$\begin {cases}c1\equiv m^{e1}\pmod N \ c2\equiv m^{e2}\pmod N\end{cases}$

当$(e_1,e_2)=1$,有$e_1s_1+e_2s_2=1$,计算得到$s_1$,$s_2$；
然后有
$c_1^{s_1}c_2^{s_2}\equiv(m^{e_1})^{s_1}(m^{e_2})^{s_2}\equiv m^{e_1s_1+e_2s_2}\equiv m\pmod{N}$

$m=c_1^{s_1}c_2^{s_2}mod N$

python代码：

1
2
3
4
import gymp

_, s1, s2 = gmpy2.gcdext(e1, e2)
m = pow(c1, s1, n) * pow(c2, s2, n) % n

CSDN链接：csdn