RSA large e: Wiener's attack

e and d can often have an inverse relationship with regards to their size, where if e is relatively small, then d is relatively large, and vice versa. In the case that e is relatively large (and d is relatively small), we can find d using Wiener’s attack.

# pip install owiener
import owiener
from Crypto.Util.number import long_to_bytes


N = 23749605390773022838319361272691200936906718135827620356598794201372662945345021031163227649091340302648826916342325314606631754182417026196412816320913993780434160532447612698631385159745710290610165059264991088485604580750505172102700412411594482935137302745940441901457332776484364761615848179355675675965840418936685419863458446194266217764129113265785365011840447620486132981252145242107353219050757114577306454933784522684194386605772192945165315151012020886254550598423480283402244283417671979104110363434439907003802511636964273526861780673984365320657725556936438914356526789883211191225188777396892876284849
e = 17420240922574672236206703766839397274890109038319418383840303577214427724015717754551963226688096804383148706583760501534042368373580803495716486992526345243618890724377235683145809078774422442850634457598775491208423007139875663628292107696418444848210140620233169012374313171879223617064510844402538245957457340913637649981481225959369431815985423386878836983226385312898213472006780982720002483413612802217541370640573078292561735626251949789908428671190570203679596377441277138036622573605038512120761478180193449842100060756205451096518207105789011164008394887441881611956558137705516268825062836680656531833247
c = 20657462021108867935419230982544573807061068405645869172928772970848519342831038241278758733096974139495221593619199863541220958772515335833101876908412860437797892512148648262588277049424030159236256917152673390939893831607827094212972246819780442915343531068092895921229492197135010903255237941578434712003166210227699216600830111768170503294711383593988801993780115497069949209553104983455910106561582944897882409570010933961125048465034094805776816627738869228385024765147205745983996814166530197725387516938219177789241038503063894290779949332189209453248274427618017665382273295405299242426822723262541364500057

d = owiener.attack(e, N)
m = pow(c, d, N)
print(long_to_bytes(m).decode("utf-8"))

Another viable solution is the Boneh-Durfee attack, which is an extension of Wiener’s attack that also targets a low private exponent d.