picoGYM - Crypto Category

As I keep practicing more and more crypto problems at picoctf.com, I'll try to add them here. However, only those giving me a hard time will be posted here.

Transformation (Crypto)

Solution:

def decrypt():
    ct = open("enc", "r").read()
    pt = ""
    for i in range(0, len(ct)):

        pt += chr(ord(ct[i]) >> 8)
        pt += chr(0b0000000011111111 & ord(ct[i]))

    print(pt)

if __name__ == "__main__":
    decrypt()

Flag is: picoCTF{16_bits_inst34d_of_8_04c0760d}

Mind Your Ps and Qs

Solution:

from Cryptodome.Util.number import inverse

p = 1899107986527483535344517113948531328331
q = 674357869540600933870145899564746495319033

N = 1280678415822214057864524798453297819181910621573945477544758171055968245116423923
E = 65537
C = 62324783949134119159408816513334912534343517300880137691662780895409992760262021

phi = (p-1)*(q-1)
d = inverse(E, phi)
m = pow(C, d, N)

hex_val = hex(m)[2:]
print(hex_val)
ascii_val = bytes.fromhex(hex_val).decode("utf-8")
print(ascii_val)

And the flag is picoCTF{sma11_N_n0_g0od_05012767}. Help taken from amazingtricks.in/how-to-solve-rsa-crypto-ch..

Mini RSA

Solution:

import gmpy2

N = 1615765684321463054078226051959887884233678317734892901740763321135213636796075462401950274602405095138589898087428337758445013281488966866073355710771864671726991918706558071231266976427184673800225254531695928541272546385146495736420261815693810544589811104967829354461491178200126099661909654163542661541699404839644035177445092988952614918424317082380174383819025585076206641993479326576180793544321194357018916215113009742654408597083724508169216182008449693917227497813165444372201517541788989925461711067825681947947471001390843774746442699739386923285801022685451221261010798837646928092277556198145662924691803032880040492762442561497760689933601781401617086600593482127465655390841361154025890679757514060456103104199255917164678161972735858939464790960448345988941481499050248673128656508055285037090026439683847266536283160142071643015434813473463469733112182328678706702116054036618277506997666534567846763938692335069955755244438415377933440029498378955355877502743215305768814857864433151287
E = 3
C = 1220012318588871886132524757898884422174534558055593713309088304910273991073554732659977133980685370899257850121970812405700793710546674062154237544840177616746805668666317481140872605653768484867292138139949076102907399831998827567645230986345455915692863094364797526497302082734955903755050638155202890599808146956044568639690002921620304969196755223769438221859424275683828638207433071955615349052424040706261639770492033970498727183446507482899334169592311953247661557664109356372049286283480939368007035616954029177541731719684026988849403756133033533171081378815289443019437298879607294287249591634702823432448559878065453908423094452047188125358790554039587941488937855941604809869090304206028751113018999782990033393577325766685647733181521675994939066814158759362046052998582186178682593597175186539419118605277037256659707217066953121398700583644564201414551200278389319378027058801216150663695102005048597466358061508725332471930736629781191567057009302022382219283560795941554288119544255055962

"""
First time using gmpy2. Apparently, `iroot` method returns
a bool too if it's the inverse-root or not. Cool.
"""

for x in range(10000):
    p, is_inverse = gmpy2.iroot(C + x * N, E)
    if is_inverse:
        print("Is inverse")
        print(p)
        pt = hex(p)[2:]
        flag = bytes.fromhex(pt).decode('utf-8')
        print(flag)

Thanks to ctftime.org/writeup/27358 for the heads up. Really useful. The flag we got is picoCTF{e_sh0u1d_b3_lArg3r_6e2e6bda}

Dachshund Attacks

Solution:

import owiener

e = 87026672509155209234915874042364286890825974133141990455436993531048134365092562717580114304144480778531605035630317913956267246231573511520333092508297324717373635621208227196134307004491654634277284944156511719975713067466878375206768656267204571722097208390011110017845353799030081876053226903159741611323
n = 139779907127414159792798588639028170582699704943473058292678923699882404797153162000329887583428513882561376602799890920301107681468553260464804297928607463521131881667495723491657166927991809392069751351987198588785301586192894623674014982154103644613411531910156069613006490211296624586698984813090505053033
c = 25268149087023893424267387971462141293341730313844076969737846218628955675939897074270778426710426606956717359620649253964130575757118926542646329218860388408233251366540329819797851849219879080777893368099980694250548416751970254784856412160210461476843827026921402301865053057765631799078998802649079650071

d = owiener.attack(e, n)
m = pow(c, d, n)

hex_val = hex(m)[2:]
print(bytes.fromhex(hex_val).decode("utf-8"))

Apparently, when d is small in RSA, Wiener's attack can be applied to find d. And there exists a python library, how cool is that! Well, the flag we got is picoCTF{proving_wiener_2635457}