RSA Attacks

Wiener's Attack

Implmentation of wiener's attack which is viable when d < N^(1/4). Another indiciation to attempt this attack is if e is large.

Arguments: n:integer, e:integer
Returns: integer, integer, integer (d, p, q)

Example usage:

# This problem is Super Safe RSA 2 from PicoCTF
>>> n = 77531969503748326589677418948315140870584015245386763633241518845356850979564402923266696704186567270006361208862086254527576010412135230279553684940635956656649728134893874567619948675304052482720430367748612708917105846534082863042823913166120865362252479206576942147071396319459112580853771742537940112457
>>> e = 56172436577459725698934391359139104915041430213184221292301658571726414059411889155782982024019814564512291421932489731563519296372873415080546379424619308859152360214209740169135159761234894923144971372974038021945201954600238994209605035703317119192844975463915465725406543097929017637859019950590916533609
>>> RSA.wiener_attack(n, e)
(65537, 7378976741566796197060049293831700178355367285954368722446941408821453416404178156616347704608205580844317832893779999699977892594442209725444425740109323, 10507143770626084625372769867908090388836545006827124055843791486155727314389374863050474785111869163080974026305280302634065146526795980161236365076948859)