small_e.py

from sage.all import *
import argparse

# Implemented from https://crypto.stackexchange.com/questions/33561/cube-root-attack-rsa-with-low-exponent


def small_e(e, ct, n=None):
    ct = Integer(ct)
    
    # n not provided
    if n is None:
        print("n not provided, only trying the e-th root of ct")
        try:
            pt = ct.nth_root(e)
        except ValueError:
            print("No integer e-th root of ct, try providing n")
            return None
        
        if pow(pt, e) == ct:
            return pt
        else:
            print("No integer e-th root of ct, try providing n")
            return None
    
    # n provided
    else:
        k = 0
        while True:
            try:
                pt = ct.nth_root(e)
            except ValueError:
                k += 1
                ct += n
                if k % 1000 == 0:
                    print("Trying k={}...".format(k))
                continue
            
            if pow(pt, e) == ct:
                return pt
            k += 1
            ct += n


def test():
    c1 = 2975366704669994427319214105748069371510893509655940635770315034818550654122704992528583545323042864978192856164779307483849673395238543775535495613262139067474537249974348575064086792663179322403563553643570489396671123214138738498714023722519655680898681313747453831401399011687754018500002439626159443362832520134871694334997005547270854392937664202616467477629086609015603943861855287237919677362080851124186762044112800867950450685022985443662119869525817680815307244383576985738633622680991204234391108735870074369514231814701720303043447577166054973199842974415508449058362894952152249932816476528775700125
    c2 = 18742874764753118255779129909617729205574130722901498454726717415788050142920177351667812719545190125730340698455093821154656718613005702081311904080230245737985855907690399762917799353828067636016827515358628280214201587382264055182197091930042365793368511236646975500218594920477419718291308841463830281367616631228337247217933767578885877258697770422513534947926045291560241137516151304400879649830480742847035566403242965496015555467133040343624065038918722138484799912983141474946367971234231493664879421695207172354672240777722375809642397120288580028207491402626362359260314503605846599973511274371309325615187
    n = 25227313400403003289291316040964706793284526130307773148182567990181812103363366492141868094341253168514098087977707768352520652692143206065406906643084095767849329466558935239586943914389925429616795559049929569740742883151498832979927915567828657543757871650853272541594015354947860164753295474118247326770430739348498870310114642065925503324951264351013482315725877175994479883134119470270775988034913135302127722176827339225792610659723969082753807504414521250872063048608812550101510336558064093636352586121260624931803298322088622685800438189865267661921807764104595582348335380035988782396542471100276681082383
    e = 3

    print("Success without n: ")
    print(small_e(e, c1))
    print()

    print("Success with n: ")
    print(small_e(e, c1, n))
    print()

    print("Failure without n: ")
    print(small_e(e, c2))
    print()

    print("Success with n: ")
    print(small_e(e, c2, n))
    print()


if __name__ == "__main__":
    parser = argparse.ArgumentParser(description="Crack a RSA ciphertext with small e")
    parser.add_argument("e", type=int, help="Exponent")
    parser.add_argument("ct", type=int, help="Ciphertext")
    parser.add_argument("-n", type=int, help="Modulus", default=None)
    args = parser.parse_args()

    print(small_e(args.e, args.ct, args.n))