[RoarCTF2019]RSA

题目

分析

这道题目其实有两种方法.

一种十分简单,直接到线上进行分解.

另一种方法则是常规解法.

1. 通过分析x,y的取值范围.
2. 枚举x,y从而得到x,y的解
3. 分析可得q与iroot(n/(x*y),2)的值相接近.从而可以得出p,q的值.

decrypt

p=842868045681390934539739959201847552284980179958879667933078453950968566151662147267006293571765463137270594151138695778986165111380428806545593588078365331313084230014618714412959584843421586674162688321942889369912392031882620994944241987153078156389470370195514285850736541078623854327959382156753458569
q=139916095583110895133596833227506693679306709873174024876891023355860781981175916446323044732913066880786918629089023499311703408489151181886568535621008644997971982182426706592551291084007983387911006261442519635405457077292515085160744169867410973960652081452455371451222265819051559818441257438021073941183
c=41971850275428383625653350824107291609587853887037624239544762751558838294718672159979929266922528917912189124713273673948051464226519605803745171340724343705832198554680196798623263806617998072496026019940476324971696928551159371970207365741517064295956376809297272541800647747885170905737868568000101029143923792003486793278197051326716680212726111099439262589341050943913401067673851885114314709706016622157285023272496793595281054074260451116213815934843317894898883215362289599366101018081513215120728297131352439066930452281829446586562062242527329672575620261776042653626411730955819001674118193293313612128
import gmpy2
e=0x10001
d=gmpy2.invert(e,(p-1)*(q-1))
import binascii
print(binascii.unhexlify(hex(gmpy2.powmod(c,d,p*q))[2:]))

结论:

有一个好的工具是真的舒服.