南邮CTF平台RSA EASY

先看题

首先复习一下RSA加密算法

RSA加密

1. 首先随机选择两个大素数p,q，计算n = pq；
2. 计算 φ(n)=(p-1)(q-1)；
3. 选取一个大整数e作为加密密钥，满足gcd(e,φ(n))=1；
4. 解出解密密钥d，满足e*d ≡ 1 mod φ(n)；
5. 公开整数n和e，秘密保存d；
6. 将明文m（m<n）加密成密文c，加密算法为：
   c = m^e mod n
7. 将密文c解密为明文m，解密算法为
   m = c^d mod n

解题思路

题目已知n，p-q，e，c，我们想求m就必须知道d，而想求d就必须求出φ(n) = (p-1)(q-1) = pq - (p+q)；问题简化一下就是已知n = pq，p-q，求p+q，利用初中数学知识求解（嗯，题目真的没骗人）

按照这个思路就可以题目中的各个参数，进而求出flag

import gmpy2
import math
#a=p-q
n=24585768801100871989460458412563674690545986652089097718040761783186739174559136657307807040444318337561194142282186006216583089898423180103199568738639814413601595196467099996734334212909157604318709957690532885862891927163713619932622153281344607898846228206181834468325246573910857887714824338949742479585089251882243488454602710292507668577598274622372304293403731722318890268908300308478539449464617438721833942643889296634768118375076052778833640986893990732882252524850152650060780854621796349622086656401914022236044924841914313726991826438982902866584892213702893596657746111940812657202364588469026832387629 
a=14048479366496281701869293063643750801596179514889914988732592464154208813942939793532694949932787548745769133200541469022315588864587160064703369956054828780928008235304461825448872454098086255531582368864754318040219023548966787642948010656526691472780392631956031751285174567712974691729142190835749586660
e=65537
x=a*a
y=x+4*n
b=gmpy2.isqrt(y)  #b=p+q
p=(a+b)/2
q=b-p

phi_n=(p-1)*(q-1)
d=gmpy2.invert(e,phi_n)

print hex(d)

c=13043206753625359891696429504613068427529111016070088678736297291041435652992434742862062899975037273524389833567258051170507686131853178642412748377655159798601888072877427570380109085131089494464136940524560062629558966202744902709909907514127527274581612606840291391818050072220256661680141666883565331886278443012064173917218991474525642412407692187407537171479651983318468186723172013439034765279464665108704671733067907815695414348312753594497823099115037082352616886076617491904991917443093071262488786475411319592529466108485884029307606114810451140886975584959872328937471166255190940884805476899976523580343
m=pow(c,d,n)
m_hex=hex(m)[2:]
flag = str(bytearray.fromhex(m_hex))

print flag

大功告成！(*^▽^*)