#! /usr/bin/env python ## # Script for PicoCTF SmallRSA challenge # Created by Amos (LFlare) Ng ## import binascii # Imports courtesy of @pablocelayes import continuedfractions import arithmetic # Values we are given e = 165528674684553774754161107952508373110624366523537426971950721796143115780129435315899759675151336726943047090419484833345443949104434072639959175019000332954933802344468968633829926100061874628202284567388558408274913523076548466524630414081156553457145524778651651092522168245814433643807177041677885126141 n = 380654536359671023755976891498668045392440824270475526144618987828344270045182740160077144588766610702530210398859909208327353118643014342338185873507801667054475298636689473117890228196755174002229463306397132008619636921625801645435089242900101841738546712222819150058222758938346094596787521134065656721069 c = 2729869850246221096831391096846794169956396740264942203903703342885290746934874117725386729017627214993949187059358671448548783102300956256114813913061908317052353475608677702004762353569798758999446296443701747957565699931341341707067812649227617863345146556649686184642966609793205244209896583560093620273 # Courtesy of @pablocelayes # I'm too lazy to rebuild a library. Thanks mate. def hack_RSA(e,n): ''' Finds d knowing (e,n) applying the Wiener continued fraction attack ''' frac = continuedfractions.rational_to_contfrac(e, n) convergents = continuedfractions.convergents_from_contfrac(frac) for (k,d) in convergents: if k!=0 and (e*d-1)%k == 0: phi = (e*d-1)//k s = n - phi + 1 discr = s*s - 4*n if(discr>=0): t = arithmetic.is_perfect_square(discr) if t!=-1 and (s+t)%2==0: return d # Attempt to derive D d = hack_RSA(e, n) # Decrypt c to m m = pow(c, d, n) message = binascii.unhexlify(format(m, 'x')).decode() print(message)