Write Up for RSA challenges in picoCTF

, , , , , ,

Before all

I love RSA and Number Theory!!!
picoCTF

Write Up

Mind your Ps and Qs

The file: 

1
2
3
4
Decrypt my super sick RSA:
c: 964354128913912393938480857590969826308054462950561875638492039363373779803642185
n: 1584586296183412107468474423529992275940096154074798537916936609523894209759157543
e: 65537

It’s easy to see that the N is too small, so just throw it into factordb(link)
The factorized result: 

1
2
1584586296183412107468474423529992275940096154074798537916936609523894209759157543=
2434792384523484381583634042478415057961*650809615742055581459820253356987396346063

After I found the p&q, I just cauculated the phi(n) / totient(n):

p.s. Crypto.Util.number is a python package with many cryptography function, like inverse and long_to_bytes(convert long int to string):
My solve script: 

1
2
3
4
5
6
7
8
9
c=964354128913912393938480857590969826308054462950561875638492039363373779803642185
n=1584586296183412107468474423529992275940096154074798537916936609523894209759157543
e=65537
p=2434792384523484381583634042478415057961
q=650809615742055581459820253356987396346063
phi=(p-1)*(q-1)
d=inverse(e, phi)
flag=pow(c, d, p*q)
print(long_to_bytes(flag))

FLAG:b'picoCTF{sma11_N_n0_g0od_73918962}'

Mini RSA

The file: 

1
2
3
N: 1615765684321463054078226051959887884233678317734892901740763321135213636796075462401950274602405095138589898087428337758445013281488966866073355710771864671726991918706558071231266976427184673800225254531695928541272546385146495736420261815693810544589811104967829354461491178200126099661909654163542661541699404839644035177445092988952614918424317082380174383819025585076206641993479326576180793544321194357018916215113009742654408597083724508169216182008449693917227497813165444372201517541788989925461711067825681947947471001390843774746442699739386923285801022685451221261010798837646928092277556198145662924691803032880040492762442561497760689933601781401617086600593482127465655390841361154025890679757514060456103104199255917164678161972735858939464790960448345988941481499050248673128656508055285037090026439683847266536283160142071643015434813473463469733112182328678706702116054036618277506997666534567846763938692335069955755244438415377933440029498378955355877502743215305768814857864433151287
e: 3
ciphertext (c): 1220012318588871886132524757898884422174534558055593713309088304910273991073554732659977133980685370899257850121970812405700793710546674062154237544840177616746805668666317481140872605653768484867292138139949076102907399831998827567645230986345455915692863094364797526497302082734955903755050638155202890599808146919581675891411119628108546342758721287307471723093546788074479139848242227243523617899178070097350912870635303707113283010669418774091018728233471491573736725568575532635111164176010070788796616348740261987121152288917179932230769893513971774137615028741237163693178359120276497700812698199245070488892892209716639870702721110338285426338729911942926177029934906215716407021792856449586278849142522957603215285531263079546937443583905937777298337318454706096366106704204777777913076793265584075700215822263709126228246232640662350759018119501368721990988895700497330256765579153834824063344973587990533626156498797388821484630786016515988383280196865544019939739447062641481267899176504155482

Since e is too small and pow(flag, 3) can be written as c+k*n, it is a sufficient method to crack the k value through brute forcing:
p.s. the iroot is from gmpy2 which would return a pair(int, bool), the bool is if the root value it an interger and the int value is the floor of result
My solve script: 

1
2
3
4
5
6
c=c=1220012318588871886132524757898884422174534558055593713309088304910273991073554732659977133980685370899257850121970812405700793710546674062154237544840177616746805668666317481140872605653768484867292138139949076102907399831998827567645230986345455915692863094364797526497302082734955903755050638155202890599808146919581675891411119628108546342758721287307471723093546788074479139848242227243523617899178070097350912870635303707113283010669418774091018728233471491573736725568575532635111164176010070788796616348740261987121152288917179932230769893513971774137615028741237163693178359120276497700812698199245070488892892209716639870702721110338285426338729911942926177029934906215716407021792856449586278849142522957603215285531263079546937443583905937777298337318454706096366106704204777777913076793265584075700215822263709126228246232640662350759018119501368721990988895700497330256765579153834824063344973587990533626156498797388821484630786016515988383280196865544019939739447062641481267899176504155482
e=3
n=1615765684321463054078226051959887884233678317734892901740763321135213636796075462401950274602405095138589898087428337758445013281488966866073355710771864671726991918706558071231266976427184673800225254531695928541272546385146495736420261815693810544589811104967829354461491178200126099661909654163542661541699404839644035177445092988952614918424317082380174383819025585076206641993479326576180793544321194357018916215113009742654408597083724508169216182008449693917227497813165444372201517541788989925461711067825681947947471001390843774746442699739386923285801022685451221261010798837646928092277556198145662924691803032880040492762442561497760689933601781401617086600593482127465655390841361154025890679757514060456103104199255917164678161972735858939464790960448345988941481499050248673128656508055285037090026439683847266536283160142071643015434813473463469733112182328678706702116054036618277506997666534567846763938692335069955755244438415377933440029498378955355877502743215305768814857864433151287
for k in range(10000000):
     if iroot(c+k*n, 3)[1]:
         print(long_to_bytes(int(iroot(c+k*n, 3)[0])))

FLAG:picoCTF{e_sh0u1d_b3_lArg3r_60ef2420}

Dachshund Attacks

Since the d is too small, the Wiener’s Attack would work!(just as my last post said, maybe there would be a post in future talking about Wiener’s Attack)
Wiener’s Attack on Python
Online Solver
Datas: 

1
2
3
4
Welcome to my RSA challenge!
e: 47998212863157354127621639739476305765986673601357336558728306019187778428142566649727260419736550419222300070928309397739848008761033583656922580232411234944797902346444995792666554040981439722213553763409879159053025130797613795919836493258902898708727788888299246768245150392055262213452071670286948516183
n: 108450270285949346526350048750646710268918069236392973512666556070524106591394840719610692440100712487144849974036278198275813675381166111228464829157752311804319828824278457849476730380254297260586870398641503274370626516779600671443909726276180902673625434426727989117288738288809081300823291337863145072293
c: 14362726277537353830427536242915576814218893651489047235892885549520535379820316816514967371049302181658890049971283699505914239513061023829084172958449927939056155559271988904584654187152261970664052050272055884068094880675411623681388448156866220509351435473297816532975759051581569088327735597919736660468

FLAG:picoCTF{proving_wiener_6907362}

No Padding, No Problem

Well, well, well.
A funny one, this challenge would give you the encrypted flag and the public key, and it also allow to input intergers to decrypt it(but not the flag)
Data received: 

1
2
3
4
5
6
7
8
9
10
Welcome to the Padding Oracle Challenge
This oracle will take anything you give it and decrypt using RSA. It will not accept the ciphertext with the secret message... Good Luck!


n: 133049217096060230048644573425739918649950634329735874860181594086811938162707704420238875269503176879568678963867162580059653817683675108354519738044912928938017232590918506533061758792527840245394714875474445397523451401179617203900859068278397637211065280535031725192090486756426589573028646564004103844233
e: 65537
ciphertext: 94358969338652390102644924028147691030711298634986380650164278884952499986334429012692717646610958263845282354531226837663875103863965486724885153215561781299042382258495958558596258307791337558026498918805010409072341619722950473376728958503136804603535965168642205547902095786518209713087615531602706122630


Give me ciphertext to decrypt:

I came up with an idea to decrypt a value(2), which I named it t1; and decrypt(2*c), which I named it t2.
After that: 

1
2
3
d is the private key.
t1=2^d%n
t2=(2*c)^d%n=(2^d*c^d)%n=(t1*c^d)%n

than the value of c^d%n can be computed by t2*(inverse)%n
My solve script: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
n=77005793532156829443826803097860385958429704134359957637962926177934403877451468634606875280571177101376040766342983289098122572766275185898756903614078539784650110642427440373150549948561881450266294450458211623996840066758889050119302108617577179256103345583934605532457065261663814241851573597453325390383
e=65537
c=11083565797963011596598422114147242960498027263265537140695852060483304170572402080447617368582247544249565427218342463450867701716837615269698655189093864610527399894745981808123574701574734368657189803828233266256559440511169340526918081011349892249901897223344684589278999848235076029339046880893130380042
#t1=decrypt(2)
t1=44716442020597541357343469015420742184907396729043973250538824036075491335429307776287226123666994142286193691198484313690025018110374213083495951170250459616408339179426774132280251606553770401935507743572600589506560431670893701883862520310597753475145452682096576393010164768050991341600484527711094189893
#t2=decrypt(2*c)
t2=61002231760645453432330216276395586149529179098766541387367721531195448417171964477822685724290709728443085011562753553589437892416841056012738979370307340514180611653844736326960725464682872941352882838473224341241514443754886967218881777625139191033912032360286580829970384203603032358259283155282461716340
key=inverse(t1, n)
flag=(t2*key)%n
print(long_to_bytes(flag))
'''
Welcome to the Padding Oracle Challenge
This oracle will take anything you give it and decrypt using RSA. It will not accept the ciphertext with the secret message... Good Luck!


n: 77005793532156829443826803097860385958429704134359957637962926177934403877451468634606875280571177101376040766342983289098122572766275185898756903614078539784650110642427440373150549948561881450266294450458211623996840066758889050119302108617577179256103345583934605532457065261663814241851573597453325390383
e: 65537
ciphertext: 11083565797963011596598422114147242960498027263265537140695852060483304170572402080447617368582247544249565427218342463450867701716837615269698655189093864610527399894745981808123574701574734368657189803828233266256559440511169340526918081011349892249901897223344684589278999848235076029339046880893130380042


Give me ciphertext to decrypt: 2
Here you go: 44716442020597541357343469015420742184907396729043973250538824036075491335429307776287226123666994142286193691198484313690025018110374213083495951170250459616408339179426774132280251606553770401935507743572600589506560431670893701883862520310597753475145452682096576393010164768050991341600484527711094189893
Give me ciphertext to decrypt: 22167131595926023193196844228294485920996054526531074281391704120966608341144804160895234737164495088499130854436684926901735403433675230539397310378187729221054799789491963616247149403149468737314379607656466532513118881022338681053836162022699784499803794446689369178557999696470152058678093761786260760084
Here you go: 61002231760645453432330216276395586149529179098766541387367721531195448417171964477822685724290709728443085011562753553589437892416841056012738979370307340514180611653844736326960725464682872941352882838473224341241514443754886967218881777625139191033912032360286580829970384203603032358259283155282461716340
'''

FLAG:picoCTF{m4yb3_Th0se_m3s54g3s_4r3_difurrent_4005534}

triple-secure

encrypt.py: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#!/usr/bin/env python3

from Crypto.Util.number import getPrime, bytes_to_long

with open('flag.txt', 'rb') as f:
    flag = f.read()

p = getPrime(1024)
q = getPrime(1024)
r = getPrime(1024)

n1 = p * q
n2 = p * r
n3 = q * r

moduli = [n1, n2, n3]

e = 65537
c = bytes_to_long(flag)

for n in moduli:
    c = pow(c, e, n)

with open('public-key.txt', 'w') as f:
    f.write(f'n1: {n1}\n')
    f.write(f'n2: {n2}\n')
    f.write(f'n3: {n3}\n')
    f.write(f'e: {e}\n')
    f.write(f'c: {c}\n')

public-keys.txt: 

1
2
3
4
5
n1: 15192492059814175574941055248891268822162533520576381643453916855435310880285336743521199057138647926712835561752909538944229702432795423884081992987060760867003375755338557996965825324749221386675061886921763747311599846248565297387814717840084998677273427776535730840343260681623323972936404815862969684384733188827100528542007213405382537935243645704237369770300643318878176739181891072725262069278646319502747718264711249767568106460533935904219027313131270918072460753061248221785076571054217566164086518459844527639082962818865640864990672033657423448004651989761933295878220596871163544315057550871764431562609
n2: 15896482259608901559307142941940447232781986632502572991096358742354276347180855512281737388865155342941898447990281534875563129451327818848218781669275420292448483501384399236235069545630630803245125324540747189305877026874280373084005881976783826855683894679886076284892158862128016644725623200756074647449586448311069649515124968073653962156220351541159266665209363921681260367806445996085898841723209546021525012849575330252109081102034217511126192041193752164593519033112893785698509908066978411804133407757110693612926897693360335062446358344787945536573595254027237186626524339635916646549827668224103778645691
n3: 16866741024290909515057727275216398505732182398866918550484373905882517578053919415558082579015872872951000794941027637288054371559194213756955947899010737036612882434425333227722062177363502202508368233645194979635011153509966453453939567651558628538264913958577698775210185802686516291658717434986786180150155217870273053289491069438118831268852205061142773994943387097417127660301519478434586738321776681183207796708047183864564628638795241493797850819727510884955449295504241048877759144706319821139891894102191791380663609673212846473456961724455481378829090944739778647230176360232323776623751623188480059886131
e: 65537
c: 5527557130549486626868355638343164556636640645975070563878791684872084568660950949839392805902757480207470630636669246237037694811318758082850684387745430679902248681495009593699928689084754915870981630249821819243308794164014262751330197659053593094226287631278905866187610594268602850237495796773397013150811502709453828013939726304717253858072813654392558403246468440154864433527550991691477685788311857169847773031859714215539719699781912119479668386111728900692806809163838659848295346731226661208367992168348253106720454566346143578242135426677554444162371330348888185625323879290902076363791018691228620744490

Is just a simple math, let n=n1*n2*n3, then sqrt(n)=p*q*r, which means that the values of p, q, r can be solved.
My solve script: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from gmpy2 import *
from Crypto.Util.number import *
n1= 15192492059814175574941055248891268822162533520576381643453916855435310880285336743521199057138647926712835561752909538944229702432795423884081992987060760867003375755338557996965825324749221386675061886921763747311599846248565297387814717840084998677273427776535730840343260681623323972936404815862969684384733188827100528542007213405382537935243645704237369770300643318878176739181891072725262069278646319502747718264711249767568106460533935904219027313131270918072460753061248221785076571054217566164086518459844527639082962818865640864990672033657423448004651989761933295878220596871163544315057550871764431562609
n2= 15896482259608901559307142941940447232781986632502572991096358742354276347180855512281737388865155342941898447990281534875563129451327818848218781669275420292448483501384399236235069545630630803245125324540747189305877026874280373084005881976783826855683894679886076284892158862128016644725623200756074647449586448311069649515124968073653962156220351541159266665209363921681260367806445996085898841723209546021525012849575330252109081102034217511126192041193752164593519033112893785698509908066978411804133407757110693612926897693360335062446358344787945536573595254027237186626524339635916646549827668224103778645691
n3= 16866741024290909515057727275216398505732182398866918550484373905882517578053919415558082579015872872951000794941027637288054371559194213756955947899010737036612882434425333227722062177363502202508368233645194979635011153509966453453939567651558628538264913958577698775210185802686516291658717434986786180150155217870273053289491069438118831268852205061142773994943387097417127660301519478434586738321776681183207796708047183864564628638795241493797850819727510884955449295504241048877759144706319821139891894102191791380663609673212846473456961724455481378829090944739778647230176360232323776623751623188480059886131
e= 65537
c= 5527557130549486626868355638343164556636640645975070563878791684872084568660950949839392805902757480207470630636669246237037694811318758082850684387745430679902248681495009593699928689084754915870981630249821819243308794164014262751330197659053593094226287631278905866187610594268602850237495796773397013150811502709453828013939726304717253858072813654392558403246468440154864433527550991691477685788311857169847773031859714215539719699781912119479668386111728900692806809163838659848295346731226661208367992168348253106720454566346143578242135426677554444162371330348888185625323879290902076363791018691228620744490
n=int(iroot(n1*n2*n3, 2)[0])
print(iroot(n1*n2*n3, 2)[1])
p=n//n3
q=n//n2
r=n//n1
moduli=[n1, n2, n3]
phi1=(p-1)*(q-1)
phi2=(p-1)*(r-1)
phi3=(q-1)*(r-1)
phi=[phi1, phi2, phi3]
flag=c
for i in range(3):  
    flag=pow(flag, inverse(e, phi[2-i]), moduli[2-i])
print(long_to_bytes(flag))

FLAG:picoCTF{1_gu3ss_tr1pl3_rs4_1snt_tr1pl3_s3cur3!!!!!!}

b00tl3gRSA2

yep another Winener’s Attack since d is too small
DATA: 

1
2
3
c: 79396535588353630695486234014424929916205425304761091938030999059051581563198817503471784068587452953675941441350902358478355554368623855312096803479190639431422004857778295425507105153807293475639758387513183460099315344512961115213991958994879582567855434834786245483772632420424135418087952312013784447104
n: 135353553008819297596740335339273679542882393695679559322286049659355156071182446202866363658452910881055640447592736005033375384280627574497016576001512272083463306254606627449113272614835389290642248900003987526599788620219498490945529378728109334543317754090740699052350653159051922670156288897456971301477
e: 62845007621730662169022257107263969891975042460988957544865376887628637931092522628546021022675185394504510172571209605217824733635583204363485014436883229586360414955518882953345099159399543114307850329322548225862640531212783162556849902351176619695825848691413009881363312562974634505047548635398733234653

FLAG:picoCTF{bad_1d3a5_4783252}

Very smooth

A Pollard p-1 attack
(many mathematics, that’s why I love RSA)
Pollard p-1 algorithm
Dcode.fr Online Solver
Pollard p-1 algo 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def pollard_algorithm(n: int):
    """
    - input : `n (int)` , n has a factor p that (p - 1)'s large prime factor is really small
    - output : `(p, q) (int, int)` , n's factors
    """

    a = 2
    b = 2
    while True:
        a = int(pow(a, b, n))
        p = int(gcd(a - 1, n))
        if 1 < p < n:
            return p, n // p
        b += 1

gen.py: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#!/usr/bin/python

from binascii import hexlify
from gmpy2 import *
import math
import os
import sys

if sys.version_info < (3, 9):
    math.gcd = gcd
    math.lcm = lcm

_DEBUG = False

FLAG  = open('flag.txt').read().strip()
FLAG  = mpz(hexlify(FLAG.encode()), 16)
SEED  = mpz(hexlify(os.urandom(32)).decode(), 16)
STATE = random_state(SEED)

def get_prime(state, bits):
    return next_prime(mpz_urandomb(state, bits) | (1 << (bits - 1)))

def get_smooth_prime(state, bits, smoothness=16):
    p = mpz(2)
    p_factors = [p]
    while p.bit_length() < bits - 2 * smoothness:
        factor = get_prime(state, smoothness)
        p_factors.append(factor)
        p *= factor

    bitcnt = (bits - p.bit_length()) // 2

    while True:
        prime1 = get_prime(state, bitcnt)
        prime2 = get_prime(state, bitcnt)
        tmpp = p * prime1 * prime2
        if tmpp.bit_length() < bits:
            bitcnt += 1
            continue
        if tmpp.bit_length() > bits:
            bitcnt -= 1
            continue
        if is_prime(tmpp + 1):
            p_factors.append(prime1)
            p_factors.append(prime2)
            p = tmpp + 1
            break

    p_factors.sort()

    return (p, p_factors)

e = 0x10001

while True:
    p, p_factors = get_smooth_prime(STATE, 1024, 16)
    if len(p_factors) != len(set(p_factors)):
        continue
    # Smoothness should be different or some might encounter issues.
    q, q_factors = get_smooth_prime(STATE, 1024, 17)
    if len(q_factors) != len(set(q_factors)):
        continue
    factors = p_factors + q_factors
    if e not in factors:
        break

if _DEBUG:
    import sys
    sys.stderr.write(f'p = {p.digits(16)}\n\n')
    sys.stderr.write(f'p_factors = [\n')
    for factor in p_factors:
        sys.stderr.write(f'    {factor.digits(16)},\n')
    sys.stderr.write(f']\n\n')

    sys.stderr.write(f'q = {q.digits(16)}\n\n')
    sys.stderr.write(f'q_factors = [\n')
    for factor in q_factors:
        sys.stderr.write(f'    {factor.digits(16)},\n')
    sys.stderr.write(f']\n\n')

n = p * q

m = math.lcm(p - 1, q - 1)
d = pow(e, -1, m)

c = pow(FLAG, e, n)

print(f'n = {n.digits(16)}')
print(f'c = {c.digits(16)}')

DATA: 

1
2
n = a1355e27e1419c3f129f1db20915bf2a2d8db159b67b55858ccb2fbe4c6f4f8245411928326496b416f389dc88f6f89f1e7dc2f184a4fb5efd40d53c4f578bd4643aea45971c21bde2ddfc6582c2955466cb8f5f2341d11ad3bdcb678efeadd043d203105545d104b1c6bde632fe72e89e37af6c69b8ca3c0d7f1367e3f9967f719e816ff603544530999eda08d28b6390fc9e3c8e0eb7432e9506bf5e638c4f548dd8c6c6c0791915f2e31b4f4114c89036650ebf541fec907017d17062114f6d2008aa641166a27734c936e7cb0f4c9df4ca5c7b57019901cbb4f3d3bbc78befbfb770ca8cbf0f3d9b752d55b81f57379e9a13bd33cf3ee17f131c16db8b21
c = 73d31ba14f88d1343a774e5d4315e1733af382318d7bf99116e5e42f0b11dc9561dfa7eafca3e061504538396fd5e463247596e8524df1c51600644d9ea7e607d5be8f79ef237907616d2ab958debc6bef12bd1c959ed3e4c2b0d7aff8ea74711d49fc6e8d438de536d6dd6eb396587e015289717e2c6ea9951822f46aae4a8aa4fc2902ceeddefd45e67fe6d15a6b182bafe8a254323200c728720bfd2d727cc779172f0848616ed37d467179a6912e8bbeb12524c7ac5cda79eee31b96cc7e36d9d69ef673f3016d0e6f0444b4f9de3d05f9d483ee6c1af479a0ffb96e9efab8098e12c7160fe3e4288364be80633a637353979c3d62376abfc99c635b703c

FLAG:picoCTF{p0ll4rd_f4ct0r1z4at10n_FTW_148cbc0f}

Sum-O-Prime

This challenge would give you the sum of p and q
than the value of p-q can be computed with sqrt((p+q)^2-4*n)
gen.py: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#!/usr/bin/python

from binascii import hexlify
from gmpy2 import mpz_urandomb, next_prime, random_state
import math
import os
import sys

if sys.version_info < (3, 9):
    import gmpy2
    math.gcd = gmpy2.gcd
    math.lcm = gmpy2.lcm

FLAG  = open('flag.txt').read().strip()
FLAG  = int(hexlify(FLAG.encode()), 16)
SEED  = int(hexlify(os.urandom(32)).decode(), 16)
STATE = random_state(SEED)

def get_prime(bits):
    return next_prime(mpz_urandomb(STATE, bits) | (1 << (bits - 1)))

p = get_prime(1024)
q = get_prime(1024)

x = p + q
n = p * q

e = 65537

m = math.lcm(p - 1, q - 1)
d = pow(e, -1, m)

c = pow(FLAG, e, n)

print(f'x = {x:x}')
print(f'n = {n:x}')
print(f'c = {c:x}')

output.txt: 

1
2
3
x = 1626a189dcb38ca6b8e9ee26623ab5c3c6cd7e4c7ff6726f4b03831ca48c617a056827c5763458d0aa7172650072b892649cc73f943f156b795ff5dd2fc9a53b140cf9c3ee2cbb8181d17bb0275f404b4090766f798ad156db7e71000e93db65f3e1bc7406532d0f509fbecf095ef215b4ad51f5e8ac765861e5f93808948bf72
n = 720d66204ec312d7f1bc688495d4585ec58520170b86ed3488c3f9c76407b7e9e466b82a282ba90d484698160f2e27f413b07cf8805d560abdffa977547d5fec3190a1ce284dfc8e92193f2f70590bf9c6e6d0ab449e35ef43ed20232b7f8686696125cde1f950230fbc6858392a3715c1b8a4947748b7fadd5cc921716ad5e0129c91ea88fceee140fb1c594606186afacb69143ef8f7b3b1aa2cc3206395c60e71ec0555dd15838d8a8395e8ccf9a4e4c4199ae0ab3f8af7ebc6605edc5ddd480be2d6c41e38618eba5822a1e566080877268802750de71e890ac865ebf87fdc290d9151e407dff4c97390c9e7388fd538e2716515cea2240f55963c2e0c21
c = 554b90eb12fbece709d7bf23ab91f9b52d71cd77fbf42f65d68623c2055d99956b9bcf2eaf14771fa5781fae86624e44b452a0f68768849faba1b9695ce353a17238a3e7040ee7aede68b35bf4b51daf0982653910b280ac98aad9a5b3c49d226e10b2e8660effc2cb2a553039bde527e42f1795bc078af6ed2928505be6df1ebe993f2ed8c10477dd5cc9f899d1e69b6512b71c732472dde521f5393c76b2f9fbed668560d4e50ca177dd14b923414549d688b20fab94dba7cad7b5a729941c772dc4a1db79b0e6a111d2d2e8998b4e2a272dc940a9dd4cf856faa5a2ee0cb6f36f0ce6edbb421697e517a4d589cc5a880eecf6fbf65e5f6a1a437b06e5ff9a

My solve script: 

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
from gmpy2 import *
x = 0x1626a189dcb38ca6b8e9ee26623ab5c3c6cd7e4c7ff6726f4b03831ca48c617a056827c5763458d0aa7172650072b892649cc73f943f156b795ff5dd2fc9a53b140cf9c3ee2cbb8181d17bb>
n = 0x720d66204ec312d7f1bc688495d4585ec58520170b86ed3488c3f9c76407b7e9e466b82a282ba90d484698160f2e27f413b07cf8805d560abdffa977547d5fec3190a1ce284dfc8e92193f2>
c = 0x554b90eb12fbece709d7bf23ab91f9b52d71cd77fbf42f65d68623c2055d99956b9bcf2eaf14771fa5781fae86624e44b452a0f68768849faba1b9695ce353a17238a3e7040ee7aede68b35>
e=65537
dif=int(iroot(x*x-4*n, 2)[0])
p=(x+dif)//2
q=x-p
phi=(p-1)*(q-1)
d=inverse(e, phi)
flag=pow(c, d, n)
print(long_to_bytes(flag))

FLAG:picoCTF{pl33z_n0_g1v3_c0ngru3nc3_0f_5qu4r35_92fe3557}

b00tl3gRSA3

I didn’t know how to solve this until I saw the hint:there’s many primes XD
online totient cauculator
DATA received: 

1
2
3
c: 3798291345622232828545625884608355778200508418441257100989411897904139623617684581137446299126199954497239868324888648801262748153348933672898642876177156562954121430975134763536012436437663935722829225419618487120286073707231243067686035684397308337509258231644866314310307005915281389361476818972849148586431011664590904603610058099969223522
n: 8729126666460774954335950980778226450552655275963874331584951440681876336912593854275664177683981585872871837731962225766891218022005808717477023954039311742477353852131523068552519474576711658262694637540615684267124200918711730673489232487609573305460354446932384278842210951786295463872891982246284528503447328498259541563662769737904553597
e: 65537

the totient(n) extracted: 

1
8729126641569990303349941606358213543795611870013849035074534525735935994444149215240124561974468564177494971546223568802571662758666597072143145474781361778670492800310421961638425936064882823367160808667013708822249027718180930758164867107306628372647183993871293208192833265135465846321884844227832557551800909959600794442399744000000000000

My solve script: 

1
2
3
4
5
6
7
8
9
from Crypto.Util.number import *
from gmpy2 import *
phi=8729126641569990303349941606358213543795611870013849035074534525735935994444149215240124561974468564177494971546223568802571662758666597072143145474781361778670492800310421961638425936064882823367160808667013708822249027718180930758164867107306628372647183993871293208192833265135465846321884844227832557551800909959600794442399744000000000000
c=3798291345622232828545625884608355778200508418441257100989411897904139623617684581137446299126199954497239868324888648801262748153348933672898642876177156562954121430975134763536012436437663935722829225419618487120286073707231243067686035684397308337509258231644866314310307005915281389361476818972849148586431011664590904603610058099969223522
n=8729126666460774954335950980778226450552655275963874331584951440681876336912593854275664177683981585872871837731962225766891218022005808717477023954039311742477353852131523068552519474576711658262694637540615684267124200918711730673489232487609573305460354446932384278842210951786295463872891982246284528503447328498259541563662769737904553597
e=65537
d=inverse(e, phi)
flag=pow(c, d, n)
print(long_to_bytes(flag))

SRA

A relaxing problem which brought me confidence.
Something cute but strange like this: 

1
2
3
4
anger = 73768303422649948577186525821079928269979190983329894967009810920290675100355
envy = 73001188472029255507658713864524755933553198761720678866636731130354948599821
vainglory?
>

chal.py: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from Crypto.Util.number import getPrime, inverse, bytes_to_long
from string import ascii_letters, digits
from random import choice

pride = "".join(choice(ascii_letters + digits) for _ in range(16))
gluttony = getPrime(128)
greed = getPrime(128)
lust = gluttony * greed
sloth = 65537
envy = inverse(sloth, (gluttony - 1) * (greed - 1))

anger = pow(bytes_to_long(pride.encode()), sloth, lust)

print(f"{anger = }")
print(f"{envy = }")

print("vainglory?")
vainglory = input("> ").strip()

if vainglory == pride:
    print("Conquered!")
    with open("/challenge/flag.txt") as f:
        print(f.read())
else:
    print("Hubris!")

ok, ok… I just converted those strange variables into the familiar ones. 

1
2
3
4
5
6
gluttony=p
greed=q
lust=n
sloth=e
envy=d
anger=c

So the problem statement change into to cauculate the value of n, p, and q with d and e.
let u=d*e-1, than u=(p-1)*(q-1)*t, so I enumerated the values of t by factorizing u!
My solve script(partial?)
p.s. sympy.ntheory us a package contain the function divisors which would return a list of divisors of an interger.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
from gmpy2 import *
from sympy.ntheory import *
e=65537
c=int(input('anger = '))
d=int(input('envy = '))
u=d*e-1
factorlist=divisors(u)
for i in factorlist:
    for j in factorlist:
        if j%i==0 and isprime(j//i+1) and isprime(u//j+1):
            n=(j//i+1)*(u//j+1)
            if(len(long_to_bytes(pow(c, d, n))))==16:
                print(long_to_bytes(pow(c, d, n)))

FINNALY: 

1
2
3
4
> WrLH8Ulmjcbb2TbC
WrLH8Ulmjcbb2TbC
Conquered!
picoCTF{7h053_51n5_4r3_n0_m0r3_b2f9b414}