Primes Part 2

Infinite Descent

We are given this source code.

#!/usr/bin/env python3

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

FLAG = b"crypto{???????????????????}"


def getPrimes(bitsize):
    r = random.getrandbits(bitsize)
    p, q = r, r
    while not isPrime(p):
        p += random.getrandbits(bitsize//4)
    while not isPrime(q):
        q += random.getrandbits(bitsize//8)
    return p, q


m = bytes_to_long(FLAG)
p, q = getPrimes(2048)
n = p * q
e = 0x10001
c = pow(m, e, n)

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

It seems that the chosen prime are close to each other. This prime generation is susceptible to Fermat's attack. If p and q are selected so that (p-q) < N^(1/4), Fermat's attack is feasible.

Here is the code I used to verify Fermat's attack feasibility.

try.py

from Crypto.Util.number import bytes_to_long, isPrime
from gmpy2 import iroot
import random, math

def getPrimes(bitsize):
    r = random.getrandbits(bitsize)
    p, q = r, r
    while not isPrime(p):
        p += random.getrandbits(bitsize//4)
    while not isPrime(q):
        q += random.getrandbits(bitsize//8)
    return p, q

p, q = getPrimes(128)
n = p*q
print(f"[*] p = {p}")
print(f"[*] q = {q}")


# If p and q are selected so that (p-q) < N^(1/4), the Fermat’s factoring algorithm can effiently factor N.

print(f"======================================")
print(f"[*] Testing Fermat attack eligibility...")
print(f"[*] Eligible if (p-q) < N^(1/4)")
print(f"[*] p-q = {p-q}")
print(f"[*] N^(1/4) = {iroot(n,4)[0]}")
if ((p-q) < (iroot(n,4)[0])):
    print(f"[+] (p-q) is LOWER, Fermat attack is feasible")
else:
    print(f"[-] (p-q) is HIGHER, Fermat attack is not feasible")

# Fermat attack
a = iroot(n,2)[0]
b = a*a-n

while (b<0):
    a = a+1
    b = a*a-n

found_q = a-iroot(b,2)[0]
found_p = n//found_q

print(f"======================================")
print(f"[+] Calculations completed")
print(f"[*] p = {found_p}")
print(f"[*] q = {found_q}")

[*] p = 263636270242060688263551727716763385533
[*] q = 263636270242060688263551727381518676067
======================================
[*] Testing Fermat attack eligibility...
[*] Eligible if (p-q) < N^(1/4)
[*] p-q = 335244709466
[*] N^(1/4) = 16236879941727126297
[+] (p-q) is LOWER, Fermat attack is feasible
======================================
[+] Calculations completed
[*] p = 263636270242060688263551727716763385533
[*] q = 263636270242060688263551727381518676067

And here is the solver code.

solve.py

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

n = 383347712330877040452238619329524841763392526146840572232926924642094891453979246383798913394114305368360426867021623649667024217266529000859703542590316063318592391925062014229671423777796679798747131250552455356061834719512365575593221216339005132464338847195248627639623487124025890693416305788160905762011825079336880567461033322240015771102929696350161937950387427696385850443727777996483584464610046380722736790790188061964311222153985614287276995741553706506834906746892708903948496564047090014307484054609862129530262108669567834726352078060081889712109412073731026030466300060341737504223822014714056413752165841749368159510588178604096191956750941078391415634472219765129561622344109769892244712668402761549412177892054051266761597330660545704317210567759828757156904778495608968785747998059857467440128156068391746919684258227682866083662345263659558066864109212457286114506228470930775092735385388316268663664139056183180238043386636254075940621543717531670995823417070666005930452836389812129462051771646048498397195157405386923446893886593048680984896989809135802276892911038588008701926729269812453226891776546037663583893625479252643042517196958990266376741676514631089466493864064316127648074609662749196545969926051
e = 65537
c = 98280456757136766244944891987028935843441533415613592591358482906016439563076150526116369842213103333480506705993633901994107281890187248495507270868621384652207697607019899166492132408348789252555196428608661320671877412710489782358282011364127799563335562917707783563681920786994453004763755404510541574502176243896756839917991848428091594919111448023948527766368304503100650379914153058191140072528095898576018893829830104362124927140555107994114143042266758709328068902664037870075742542194318059191313468675939426810988239079424823495317464035252325521917592045198152643533223015952702649249494753395100973534541766285551891859649320371178562200252228779395393974169736998523394598517174182142007480526603025578004665936854657294541338697513521007818552254811797566860763442604365744596444735991732790926343720102293453429936734206246109968817158815749927063561835274636195149702317415680401987150336994583752062565237605953153790371155918439941193401473271753038180560129784192800351649724465553733201451581525173536731674524145027931923204961274369826379325051601238308635192540223484055096203293400419816024111797903442864181965959247745006822690967920957905188441550106930799896292835287867403979631824085790047851383294389


# Fermat attack
# If p and q are selected so that (p-q) < N^(1/4), the Fermat’s factoring algorithm can effiently factor N.

a = iroot(n,2)[0]
b = a*a-n

while (b<0):
    a = a+1
    b = a*a-n

found_q = a-iroot(b,2)[0]
found_p = n//found_q

# Decrypt flag
phi = (found_p - 1) * (found_q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)

print(long_to_bytes(m))

Flag: crypto{f3rm47_w45_4_g3n1u5}

Marin's Secrets

From the title and the source code below, we can infer that the secrets list refers to Mersenne primes.

#!/usr/bin/env python3

import random
from Crypto.Util.number import bytes_to_long
from secret import secrets, flag

# "secret" always returns a prime
def get_prime(secret):
    prime = 1
    for _ in range(secret):
        prime = prime << 1
    return prime - 1


random.shuffle(secrets)

m = bytes_to_long(flag)
p = get_prime(secrets[0])
q = get_prime(secrets[1])
n = p * q
e = 0x10001
c = pow(m, e, n)

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

Now, we can take the fact that there is only 52 known Mersenne primes out there. Even with the limited options, it is possible for us to limit the options to only the pair whose sum of bit lengths matches the bit length of n. Here is the solver code for this challenge.

from Crypto.Util.number import *
from itertools import combinations

# From output.txt
n = 658416274830184544125027519921443515789888264156074733099244040126213682497714032798116399288176502462829255784525977722903018714434309698108208388664768262754316426220651576623731617882923164117579624827261244506084274371250277849351631679441171018418018498039996472549893150577189302871520311715179730714312181456245097848491669795997289830612988058523968384808822828370900198489249243399165125219244753790779764466236965135793576516193213175061401667388622228362042717054014679032953441034021506856017081062617572351195418505899388715709795992029559042119783423597324707100694064675909238717573058764118893225111602703838080618565401139902143069901117174204252871948846864436771808616432457102844534843857198735242005309073939051433790946726672234643259349535186268571629077937597838801337973092285608744209951533199868228040004432132597073390363357892379997655878857696334892216345070227646749851381208554044940444182864026513709449823489593439017366358869648168238735087593808344484365136284219725233811605331815007424582890821887260682886632543613109252862114326372077785369292570900594814481097443781269562647303671428895764224084402259605109600363098950091998891375812839523613295667253813978434879172781217285652895469194181218343078754501694746598738215243769747956572555989594598180639098344891175879455994652382137038240166358066403475457 
e = 65537
c = 400280463088930432319280359115194977582517363610532464295210669530407870753439127455401384569705425621445943992963380983084917385428631223046908837804126399345875252917090184158440305503817193246288672986488987883177380307377025079266030262650932575205141853413302558460364242355531272967481409414783634558791175827816540767545944534238189079030192843288596934979693517964655661507346729751987928147021620165009965051933278913952899114253301044747587310830419190623282578931589587504555005361571572561916866063458812965314474160499067525067495140150092119620928363007467390920130717521169105167963364154636472055084012592138570354390246779276003156184676298710746583104700516466091034510765027167956117869051938116457370384737440965109619578227422049806566060571831017610877072484262724789571076529586427405780121096546942812322324807145137017942266863534989082115189065560011841150908380937354301243153206428896320576609904361937035263985348984794208198892615898907005955403529470847124269512316191753950203794578656029324506688293446571598506042198219080325747328636232040936761788558421528960279832802127562115852304946867628316502959562274485483867481731149338209009753229463924855930103271197831370982488703456463385914801246828662212622006947380115549529820197355738525329885232170215757585685484402344437894981555179129287164971002033759724456

n_len = len(bin(n)[2:])


# All 52 known Mersenne primes
mersenne_p = [2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161, 74207281, 77232917, 82589933, 136279841]

# Filter 1: p must not exceed n's bit length
mersenne_p = [x for x in mersenne_p if x < n_len]

# Filter 2: (p1 + p2) must equal n's bit length
pairs = list(combinations(mersenne_p, 2))
candidate_pairs = []
for p1, p2 in pairs:
    if (p1 + p2 == n_len):
        candidate_pairs.append((p1, p2))

# Try candidate pairs to check p*q == n
for p1, p2 in candidate_pairs:
    p = 2**p1 - 1
    q = 2**p2 - 1
    calc_n = p * q
    if (calc_n == n):
        phi = (p-1)*(q-1)
        d = pow(e,-1,phi)
        m = pow(c,d,n)

print(long_to_bytes(m))

Flag: crypto{Th3se_Pr1m3s_4r3_t00_r4r3}