本文主要是介绍从零开始学RSA：已知p+q和(p+1)(q+1)和已知p-q和n，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
(17)已知p+q和(p+1)(q+1)
题目给出p+q，(p+1)(q+1)，e和c。
首先需要求出phi，然后求解d，最后再求解m。
phi = (p-1)(q-1)
= pq - (p+q) + 1
p+q的值题目已经给出了，接下来只需要求出pq的值即可求出phi的值。题目还给出了(p+1)(q+1)，我们考虑下pq是否可以表示为(p+1)(q+1)的形式：
(p+1)(q+1) = pq + p + q + 1
= pq + (p+q) + 1
那么pq就可以表示为：
pq = (p+1)(q+1) - (p+q) -1
然后，求解phi的值。
phi = (p-1)(q-1)
= pq - (p+q) + 1
= n - (p+q) + 1
最后：
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
完整的解题脚本如下：
#!/usr/bin/python#coding:utf-8import gmpy2from Crypto.Util.number import long_to_bytes#p+q通过p_add_q表示p_add_q = 326429100407681651814978442415826213864753565034919374282004148849764531414964129530662174521568050093736341197400405816551402307458686750141836996345723514698979514133066389538988520826440776264241138888155090851605191090286605183976443204444854546781116840786281855819689375353337207819361769484061133586660#(p+1)(q+1)为了方便用x表示x = 26601616557971867831128918184476970808722471200861600741488181559976427915212193001812160532906370924454473038671991616741424706794741682437728013348910646937734672343325523407437596920797247711273378236903138971315823251358525257853681659038646150834388504990678755552658405772625078429891153401221091704935464031276762725209220275197422069811202440482709667987828399235771854454331605660739185369563297937712412914621262089799368586352843414856752338979163598254668715003106493342377951882955338211218066635494610164992383277776336257215001515405312235576928828485922034700150519853591032361405975195251746299510720c = 24831377919906161196266552704492935537768087456188711284519872226691826290351027606307936414989585764319104737516021733938210516424254235349369088344349700976416957839221585194510124601438798302079231278339823353520868327987552051471031155633165987892206927171527428590536203275545528900845222038924459888879261986663709510987273937159905675940592632023428129764650249246182611973968609631056274792336171105433760493214971141615401120748113420469659787315651721605227003326305005720436114240966565179896456348773794946970503274768701856591123183247406604013805700201562056023223765073732621940021232679124486597812994e = 65537#n = pq = (p+1)(q+1) - (p+q) - 1 = x - p_add_q - 1n = x - p_add_q - 1#phi = (p-1)(q-1) = pq - (p+q) + 1 = n - (p+q) + 1 = n - p_add_q + 1phi = n - p_add_q + 1d = gmpy2.invert(e,phi)m = pow(c,d,n)print(long_to_bytes(m))运行结果：
flag{e2df5b739abba07ae93403d3915228c9}
(18)已知p-q和n
这个题相比于(17)而言，不太容易直接想到转化的等式。
题目给出p-q，n，e和c。
常规的RSA解密步骤：
n = p*q
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
因为n不可分解，所以，我们无法直接得到p和q的值，也就无法得到phi的值。
通过对phi的如下分解可知，如果已知n和p+q便可求得phi的值。
phi = (p-1)*(q-1)
= p*q - (p+q) + 1
= n - (p+q) + 1
因为，给了p-q的值，所以，我们需要设法将p+q表示为p-q，进而求得phi的值。
这样，我们就可以求出p+q的值，进而可以求出phi的值。最后就可以求出明文m的值了。
解题脚本如下：
#!/usr/bin/python#coding:utf-8#变量p_add_q：p + q#变量p_sub_q：p - qimport gmpy2from Crypto.Util.number import long_to_bytesn = 27552304606229034903366058815849954030287648695063385362955432137790872571412035824128918674719247737295565001575991597519270789776408208970323808016733976338433371328100880898942106515627607388226912870981180215883273805491209461671730377099185278711453949265641966582563910708529619185885928310168288810488784242368160743359666583499117949407921812317700250240067929572558785431071173411100434109661677786734923283679392823901052633992456780285091988542875991410528415886437666510014123352497264017734716859350294159440761760921548702546470902740121962033241003215821780125194400741190925169397917247376657863011603e = 65537c = 8643831704675414121804983915084443744489969712473300784256427784417167322852556975560503484179280700293119974607254037642425650493676448134024809335297135239994950178868535219541095694358323044214971760829173918774094415933808417722001811285178546917655837402000771685507972240389565704149610032767242977174132826100177368764169367458684152505611469248099487912367364804360878611296860803835816266114046682291529593099394952245852157119233687981777202751472502060481232341206366584532964027749320641690448228420342308891797513656897566100268729012788419021059054907653832828437666012596894150751431936476816983845357p_sub_q = 3216514606297172806828066063738105740383963382396892688569683235383985567043193404185955880509592930874764682428425994713750665248099953457550673860782324431970917492727256948066013701406000049963109681898567026552657377599263519201715733179565306750754520746601394738797021362510415215113118083969304423858p_add_q = gmpy2.iroot(p_sub_q**2 + 4*n, 2) #iroot()返回值为一个(x,y)元组。其中x为结果值，y为一个bool型变量，如果x为整数，y=True,否则y=False。phi = n - p_add_q[0] + 1d = gmpy2.invert(e,phi)m = pow(c,d,n)print(long_to_bytes(m))运行结果：
flag{9c0532a253809f180747b6da334b438f}
这篇关于从零开始学RSA：已知p+q和(p+1)(q+1)和已知p-q和n的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
