Many Primes | T4QI-Blog

Challenge Description:

Big primes are sketch.
output.txt encrypt.py

Challenge script:

PYTHON

from Crypto.Util.number import bytes_to_long, getPrime
import random

flag = open("flag.txt").read().encode()
flag = bytes_to_long(flag)
n = 1
while n.bit_length()<4096:
    i = random.randint(10,16)
    reps = random.randint(2,5)
    p = getPrime(i)
    if n%p !=0:
        n*=p**reps
e = 65537
encryptedFlag = pow(flag, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"flag = {encryptedFlag}")

This challenge tests the understanding of how N operates in RSA and what are the vulnerabilities that could be used if N is miss formed. In the challenge script we can see that N is made from small primes raised to small exponents here we can exploit this to factor N and then calculate phi then get the flag.

PYTHON

from Crypto.Util.number import long_to_bytes
import math

n = 84957339878841249042661992015318775914153057891067549723671982778975957526984361748735670333426792012519248099265537115315835602057882318543112781196438953840653279029957533208045448649312183873062132255928109150470090982541502003013666939934181416473581073990221728448342533549843710383544743220364127453679761909368982493089369740815066106196444062558446312836612656666434089655206650558129894180991572670565328419648196602807190683488653617068325238542193033423978598565191919683033996144778397817249870630736098769732268174866389943010980427234356604782502318622853423388492983406635687647680770869588481426436811952986075832678887752706507835771052708232550208582584262345437818916577580806059662945066377375408508814381061305598911972399165132279018674832071994673661875185328115121586302490349253912699566783660070599552395205352917554104371784905394477629626963439266490743240318198729049054547013391348516066097465180775402810975266096525722415778248668765855332776864126033830969325570615444114396786906102536716873598804164196155179833683285635189223166238933318740720918827120989416013091102543382987278707392961157272937695585450287755023671116911370689655292160336521776501052329465384315585357461493649222793172462113102463
e = 65537
encryptedFlag = 45146787828557679140423580221442956925310977371109091853462843177826294442352634580160310989152235297235514141658881390908592470683795245870619319983451904537192781823855678086088663405872526980084960008183831288044960349605168173490367894375757787452024287989993362954206286853190401541606518731317814018817491109177360761859453002792899864984488524864028766239497641048919565458281765487932324396702580026094746189401141448947513512730220423629277692258527951902039531739842965067285622196418171785466236294324572986853688947727117303227689578683403160426800470263102483582737614730930657875098843867256713854784720793138228809768453579721222271047690131897888999884098995408016105397663714102200568327066068146128637742779637777800612639149916508879936573438036837445673606364763612971401591822166427703422764153960398983100036398400304771376839125152709954274549463602659761299411215766075895177151923436509501196662786766042103493713861194722614436307437016043581292216432028543923347478884441934980948114759937955940408027377458938151172837554432746134399838012547867483350557859826433321810794053681726512471838143910118068486851496148663526948219071671481909824342580081675074372829356225227848676981201731545407466857723499918017

def factorize(n):
    factors = {}
    while n % 2 == 0:
        factors[2] = factors.get(2, 0) + 1
        n = n // 2
    i = 3
    max_factor = math.isqrt(n) + 1
    while i <= max_factor:
        while n % i == 0:
            factors[i] = factors.get(i, 0) + 1
            n = n // i
            max_factor = math.isqrt(n) + 1
        i += 2
    if n > 1:
        factors[n] = factors.get(n, 0) + 1
    return factors

factors = factorize(n)
print("Factors:", factors)

phi = 1
for p, exp in factors.items():
    phi *= (p ** exp) - (p ** (exp - 1))

d = pow(e, -1, phi)

flag = pow(encryptedFlag, d, n)
print("Flag:", long_to_bytes(flag))

Here I choose to use Trial division to factor N because N is small . It is a simple algorithm to factorize integers. I will try to explain it in simple way

Start with the smallest prime (2) and check if it divides the number.
- If yes, divide the number by 2 and record it as a factor.
- Repeat until the number is no longer divisible by 2.
Move to the next prime (3) and repeat the process.
Continue with 5, 7, 11, … up to √N because there will be no number that factorizes N that is greater than √N.
If the remaining number is > 1, it is also a prime factor.

Here we would have got the factors of N now it is time to phi.

$$ \phi(n) = \prod_{i=1}^{k} \left( p_i^{r_i} - p_i^{r_i - 1} \right) $$ this is the equation of calculating phi, After we calculate it we decrypt the flag to get byuctf{3ulers_ph1_function_15_v3ry_us3ful_4nd_th15_I5_a_l0ng_fl4g}.

Thanks for reading hope you enjoyed it if you have any comments don’t hesitate to reach out.

Challenge Description:

Challenge script:

Output.txt: