Primes Part 1

Factoring

Resources:

• Modern method to factor numbers

• How big an RSA key is considered secure today?

• primefac-fork

Current recommendation is 1024 bits prime. Multiplied, it will give us 2048 bits modulus and therefore called RSA-2048. Other than manual factorization, there is a prime factors database for large integers called factordb.

Here's the PoC for the challenge.

n = 510143758735509025530880200653196460532653147

# from factordb
p = 19704762736204164635843
q = 25889363174021185185929

print(min(p,q))

Flag: 19704762736204164635843

Inferius Prime

We are given the source code:

#!/usr/bin/env python3

from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes, GCD

e = 0x10001

# n will be 8 * (100 + 100) = 1600 bits strong (I think?) which is pretty good
p = getPrime(100)
q = getPrime(100)
phi = (p - 1) * (q - 1)
d = inverse(e, phi)

n = p * q

FLAG = b"crypto{???????????????}"
pt = bytes_to_long(FLAG)
ct = pow(pt, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {ct}")

pt = pow(ct, d, n)
decrypted = long_to_bytes(pt)
assert decrypted == FLAG

The code "calculated" that n is 1600 bits long. It assumed that the number inside getPrime() is in bytes, which is wrong. The number is in bits. Therefore, n is only 100 + 100 = 200 bits long, a length that is easily breakable.

Here is the solution for the challenge.

from Crypto.Util.number import *

n = 984994081290620368062168960884976209711107645166770780785733
e = 65537
ct = 948553474947320504624302879933619818331484350431616834086273

# n is NOT 1600 bits
print(f"n length in bits: {len(bin(n)[2:])}")

# from factordb
p = 848445505077945374527983649411
q = 1160939713152385063689030212503
phi = (p-1)*(q-1)

d = pow(e,-1,phi)
m = pow(ct,d,n)

print(long_to_bytes(m))

n length in bits: 200
b'crypto{N33d_b1g_pR1m35}'

Flag: crypto{N33d_b1g_pR1m35}

Monoprime

For any prime number p, the Euler's totient function is φ(p) = p-1.

Here's the PoC for the challenge.

from Crypto.Util.number import *

n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942  

# Ensure n is prime
assert isPrime(n)

# Calculate totient function
phi = n-1

# Decryption
d = pow(e,-1,phi)
m = pow(ct,d,n)

print(long_to_bytes(m))

Flag: crypto{0n3_pr1m3_41n7_pr1m3_l0l}

Square Eyes

This time, n is a square of prime p. Remember Euler's totient function formula:

With n = p^2, then phi = p(2-1)*(p-1), which is simplified to phi = p*(p-1).

Here is the solver code for the challenge.

from Crypto.Util.number import *
from gmpy2 import iroot

n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e = 65537
ct = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896

p = iroot(n, 2)[0]
phi = p*(p-1)
d = pow(e,-1,phi)

m = pow(ct,d,n)
print(long_to_bytes(m))

Flag: crypto{squar3_r00t_i5_f4st3r_th4n_f4ct0r1ng!}

Manyprime

This time, n has over 30 prime factors. We can solve this using factordb, but we can also use an optimized factoring method for this scenario (ref: Sage Elliptic Curve).

Here is a solver to the challenge.

from sage.all import *
from Crypto.Util.number import *

n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e = 65537
ct = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464

n_factors = ecm.factor(n)
print(f"Found factors: {n_factors}")

phi = 1
for p in n_factors:
	phi *= (p-1)

d = pow(e,-1,phi)

m = pow(ct,d,n)
print(long_to_bytes(m))

Flag: crypto{700_m4ny_5m4ll_f4c70r5}