RSA 2 (90 pts)


Problem

RSA 2


Solution

  1. The patterns in the base 5 representation are rather interesting... It's somewhat similar to the Primey RSA problem I made for CryptoCTF
  2. Realize that in order for the repeated string of 1s in the middle to occur, the 2 factors must be of the form 1...1 (a ones) and 1...1 (b ones), in base 5
  3. a must be equal to the number of digits in the first repeating pattern, plus the number of repeated ones + 1
  4. b must be equal to the number of digits in the first repeating pattern+1, so
  5. Test to see if it works, then do a standard RSA decryption routine

Code below:

def bc(x,b,alphabet='0123456789abcdefghijklmnopqrstuvwxyz'):
    'convert an integer to its string representation in a given base'
    if b<2 or b>len(alphabet):
        if b==64: # assume base64 rather than raise error
            alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
        else:
            raise AssertionError("int2base base out of range")
    if isinstance(x,complex): # return a tuple
        return ( int2base(x.real,b,alphabet) , int2base(x.imag,b,alphabet) )
    if x<=0:
        if x==0:
            return alphabet[0]
        else:
            return  '-' + int2base(-x,b,alphabet)
    # else x is non-negative real
    rets=''
    while x>0:
        x,idx = divmod(x,b)
        rets = alphabet[idx] + rets
    return rets

N5 = "124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124012401240124011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111104320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204320432043204321"

N52 = "1240"*232+"1"*2478+"0432"*232+"1"

c = 155132684009663994250923371240177483736552962245035111157100289160054536420321767480347759751031459080914745049176252173663584369109276008091726170227341992483832825160495827180809800156674939243439909731477990868031426629965161449585567132182197509263325439187914382249684386029368424401172811587427536470105074710988250791880726112359069855098589071744198615877763470639144356501768429987219679083673597656513293976112924300870324919644792022840895154841283331799946720440962520279000035961538272002442344272416687646863948994065594572775392306597460952985929308969477943660013209726381325951618966691843032672886556083136986652622598042933473180218497758299937765674533880031603121040685977793863725696430928653308899580185718791954260726326766782971780919464071515527065468636925118433024530892971645020702188089826152811963559498563016491665028990784580030667543972372530453004422798281693346561798843274234309022967494500892696291418148839958034345794292638131832373910597771045061053246338645972904267709478436770597765526200126612776754114713175313679316946205499666668677848831235835306701466780769026264487444452915451299160958621904237851630638055642513690776135486636315815820022622210381221348518313439853735724984254802218680662610062568532235828833774743451069150516889601834909309483728594147876970525339616018047424776116938182774696261615479949752128424448912059363842026402065903756846996621925278036843658977068191154870869003724632592341741458299708908618159801041209453677190576151174308576466790706285250083740408532442545623183404467203306527055731389220523964716661232666738954491004349095642026322693407054178806459938502954686559108238871407819362527374771075137740798393191430983862244643454112474406387787656177124185510246893576243809749719691864350205232633618422561110236703753238344849163317059202504805316810005535411407829849491527181044259468782661943237961505596461202349184311622356152767225073607119530043938569790032612029422411317404300063030803680536781427746887193301621656008761284870462439080740353630168195775013203214826058326401182351995862367534895856909779679004860853809969151643492260786459616844175281941991980054485418880530935559732275605895397870026915417436949395231800768339528182620517453199721642214612576279768316819014421711052487730304933950891797901385500985483031733173341619159952956739723307545652211622867261080569676554699899351058696308152974629481579482353469358670507845762268245256262641145039436794833953956923481901340588722238427062765364780829707561460890560086866979355019084817835828137802944136982578759889236851614362045642718053281044512196514914633577772736803480558883670159029273386230970630593907413491210417592616870820293719290394789220772197398579647930784266035187235797101199745082689503012354428818108664375721965084747474233193734615503704956711492956852832509397798728457033850873467490322965984660296799641622893835917152238119926736392054697882846161837684350210151870199067768307242089059107570850246298012160053272116763627574368161

print N5==N52

N = int(N5, 5)

# base 5 rep of p
p5="1"*2478+"1"*(4*232+1)
# base 5 rep of q
q5 = "1"*(4*232+1)

p=int(p5,5)
q = int(q5,5)

print N==p*q
# worked! factored succesfully. Now just do a standard decryption routine

phi = (p-1)*(q-1)

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


d = modinv(65537, phi)
m = pow(c, d, N)

print m

print (hex(m)[2:])[:-1].decode('hex')

Flag

tjctf{7FtNg1Vu7bbAhszil8IBveu3jlxFhxsZDpV5AapNYQqnxz09VAHG4gOodNdj6SGcClq1hyVeRi27bdG2jO9Z50aoN6VbT6Z0UQhtoLwJZvRAHfoU7DVM5PXlbMFZFIbw3lUDe6KnnuhWclr5MrpDEAPDkpeuL3DY5WWcWJMOMY7sRflcK6l9UCFaofZqtyG2zmKZYqox}

results matching ""

    No results matching ""