I only solved the first two challenges during the CTF, but the challenges were great and I learnt a lot doing writeups for them. The writeups here are very similar to rkm0959's as I was only able to solve the other three challenges after reading his writeups (all of the code is my own, but the ideas behind them are heavily inspired). I decided to write these and publish them to convince myself that I actually understood the solutions, and also to give a (slightly) different perspective that might be easier to understand.

crypto
- This is RSA
- koharu
- urara
- sharsable
- crypto01

This is RSA

As you may know.

rsa.rb:

require 'openssl'

def get_prime
  i = OpenSSL::BN.rand(512).to_s.unpack1('H*').hex
  OpenSSL::BN.new(i).prime? ? i : get_prime
end

p = get_prime
q = get_prime
n = p * q
e = 65537
m = File.read('flag.txt').unpack1('H*').hex
c = m.pow(e, n)

puts "N = #{n}"
puts "c = #{c}"

output.txt:

N = 13234306273608973531555502334446720401597326792644624514228362685813698571322410829494757436628326246629203126562441757712029708148508660279739210512110734001019285095467352938553972438629039005820507697493315650840705745518918873979766056584458077636454673830866061550714002346318865318536544606580475852690351622415519854730947773248376978689711597597169469401661488756669849772658771813742926651925442468141895198767553183304485662688033274567173210826233405235701905642383704395846192587563843422713499468379304400363773291993404144432403315463931374682824546730098380872658106314368520370995385913965019067624762624652495458399359096083188938802975032297056646831904294336374652136926975731836556951432035301855715375295216481079863945383657
c = 9094564357254217771457579638296343398667095069849711922513911147179424647045593821415928967849073271368133854458732106409023539482401316282328817488781771665657515880026432487444729168909088425021111879152492812216384426360971681055941907554538267523250780508925995498013624610554177330113234686073838491261974164065812534037687990653834520243512128393881497418722817552604416319729143988970277812550536939775865310487081108925130229024749287074763499871216498398695877450736179371920963283041212502898938555288461797406895266037211533065670904218278235604002573401193114111627382958428536968266964975362791704067660270952933411608299947663325963289383426020609754934510085150774508301734516652467839087341415815719569669955613063226205647580528

Solution

The vulnerability is in the prime generation (as we would expect). The prime is generated by choosing a random 512 bit number, and converting each digit into its ASCII hex value. For example if the randomly generated number was 1234 the prime would be 0x31323334 = 825373492 (clearly not a prime, but you get the point). The vulnerability is that in the hex representation of the primes, the first nibble of each byte is 3. We can then bruteforce the 2nd nibble of each byte starting from the least significant byte and working our way up since there are only 10*10 = 100 possibilities to check for each pair of bytes.

Solve script:

from Crypto.Util.number import isPrime, long_to_bytes

N = 13234306273608973531555502334446720401597326792644624514228362685813698571322410829494757436628326246629203126562441757712029708148508660279739210512110734001019285095467352938553972438629039005820507697493315650840705745518918873979766056584458077636454673830866061550714002346318865318536544606580475852690351622415519854730947773248376978689711597597169469401661488756669849772658771813742926651925442468141895198767553183304485662688033274567173210826233405235701905642383704395846192587563843422713499468379304400363773291993404144432403315463931374682824546730098380872658106314368520370995385913965019067624762624652495458399359096083188938802975032297056646831904294336374652136926975731836556951432035301855715375295216481079863945383657
e = 0x10001
c = 9094564357254217771457579638296343398667095069849711922513911147179424647045593821415928967849073271368133854458732106409023539482401316282328817488781771665657515880026432487444729168909088425021111879152492812216384426360971681055941907554538267523250780508925995498013624610554177330113234686073838491261974164065812534037687990653834520243512128393881497418722817552604416319729143988970277812550536939775865310487081108925130229024749287074763499871216498398695877450736179371920963283041212502898938555288461797406895266037211533065670904218278235604002573401193114111627382958428536968266964975362791704067660270952933411608299947663325963289383426020609754934510085150774508301734516652467839087341415815719569669955613063226205647580528

def bf_2nd_nibbles(N, A, B, n):
    for x in range(16):
        for y in range(16):
            bfA = 0x3 * pow(16, n - 1) + pow(16, n - 2)*x + A
            bfB = 0x3 * pow(16, n - 1) + pow(16, n - 2)*y + B
            if bfA * bfB % pow(16, n) == N % pow(16, n):
                return bfA, bfB

p = q = 0
for i in range(2, 312, 2):
    p, q = bf_2nd_nibbles(N, p, q, i)
assert isPrime(p) and isPrime(q) and p*q == N

d = pow(e, -1, (p-1)*(q-1))
m = pow(c, d, N)
print(long_to_bytes(m).decode())

Flag: SECCON{I_would_always_love_the_cryptography_and_I_know_RSA_never_gets_old_So_Im_always_a_fan_of_this_mathematical_magic_and...Wait_This_flag_can_be_longer_than_I_expected_What_happened?}

koharu

Koharu chan walks on the polynomial.

task.sage:

while True:
    p = random_prime(1<<64)
    if is_prime((p+1) // 2):
        break

with open("flag.txt", "rb") as f:
    flag = f.read()
flag = int.from_bytes(flag, "big")


PR.<x> = PolynomialRing(GF(p))
while True:
    P = PR.random_element(degree=64)
    if P.is_irreducible():
        break

while True:
    Q = PR.random_element(degree=64)
    if Q.is_irreducible():
        break

NP = p**P.degree()
NQ = p**Q.degree()

while True:
    R = PR.random_element(degree=64)
    if power_mod(R, (NP-1)//2, P) != 1 and power_mod(R, (NQ-1)//2, Q) != 1:
        break

PQ = P*Q
c = []
while flag:
    S = PR.random_element(degree=64)
    if flag & 1:
        c.append((S * S) % PQ)
    else:
        c.append((S * S * R) % PQ)
    flag = flag >> 1

print("p =", p)
print("PQ =", PQ)
print("R =", R)
print("c =", c)

output.txt:

p = 4832823609987476353
PQ = 2475361839038406994*x^128 + 1816580044636445865*x^127 + 771106714052997910*x^126 + 2532248969060743840*x^125 + 157159147928168793*x^124 + 1165294508775017303*x^123 + 54498477947855453*x^122 + 564670281176250610*x^121 + 4686383084102262935*x^120 + 4798143559496813901*x^119 + 2373759188753852032*x^118 + 3458843219210551923*x^117 + 3389173528515223367*x^116 + 3175114023644661971*x^115 + 2668820643276713526*x^114 + 1644657084961816584*x^113 + 1949973045428555331*x^112 + 2314884799372359978*x^111 + 1614909032209480656*x^110 + 3706101120120959039*x^109 + 1443476119293487220*x^108 + 507539962924420368*x^107 + 2851578707595377440*x^106 + 2660707099322090529*x^105 + 2275120831055073492*x^104 + 4642644673121099806*x^103 + 780741129747777966*x^102 + 3824963851609159359*x^101 + 1445016816241934269*x^100 + 4706494165496469049*x^99 + 91460120231848540*x^98 + 2033361932245472629*x^97 + 4657205830657809352*x^96 + 627579987075662316*x^95 + 2638155163726745709*x^94 + 773248040814209977*x^93 + 4426134463977473378*x^92 + 1748835523159978170*x^91 + 2545886874835388035*x^90 + 4318027045196127783*x^89 + 529092995613843935*x^88 + 37621695756851259*x^87 + 724317479549357114*x^86 + 235872728824864204*x^85 + 1409136599403563059*x^84 + 984842291673572708*x^83 + 1000642979551429427*x^82 + 2599952022893048437*x^81 + 33489199855748196*x^80 + 2138571356326295553*x^79 + 357904099457660261*x^78 + 1388605866466399741*x^77 + 2123614714168365349*x^76 + 1296407111118101425*x^75 + 3175149128196009486*x^74 + 4407671566428651830*x^73 + 3653949472018283742*x^72 + 2150666969917189331*x^71 + 2425834809198809729*x^70 + 202017664024051124*x^69 + 4656859267960293209*x^68 + 95544718007904685*x^67 + 551963924883187932*x^66 + 1220133766833256737*x^65 + 418789913385574936*x^64 + 3140425594489130574*x^63 + 653426727346469624*x^62 + 2168508737790275670*x^61 + 1350675684196344669*x^60 + 86970043713584944*x^59 + 3125122442296761190*x^58 + 1691082709013935740*x^57 + 14954357710735056*x^56 + 1951640599446313225*x^55 + 3057759244385615044*x^54 + 2842299299534580663*x^53 + 60118912044101305*x^52 + 3791459205438092561*x^51 + 3961025931327708139*x^50 + 3352223936735193809*x^49 + 458087980170556413*x^48 + 303065746752057039*x^47 + 270269323703788403*x^46 + 3435561048914221019*x^45 + 244980776425782882*x^44 + 1756735569264346021*x^43 + 1049402079460555244*x^42 + 1181023304135761892*x^41 + 2480814159047994100*x^40 + 3359295278584507081*x^39 + 1031815312165038169*x^38 + 2284789340145013050*x^37 + 2507227047920435897*x^36 + 4212274843760760739*x^35 + 1874163516348469998*x^34 + 4184876619139253979*x^33 + 2454055493008310058*x^32 + 4810631595605704078*x^31 + 2705618732956794205*x^30 + 4588422028499215564*x^29 + 1362947071518584749*x^28 + 200625668549982104*x^27 + 4162225127389871946*x^26 + 3671964574429446847*x^25 + 497776717675475749*x^24 + 3171362364421276926*x^23 + 4040585504650270495*x^22 + 55143980688943936*x^21 + 1680279432641096886*x^20 + 1141249890787830167*x^19 + 1632171956841566025*x^18 + 4489792289887403690*x^17 + 72863318133800422*x^16 + 3512973315964270180*x^15 + 1880837549990432714*x^14 + 629108155937185931*x^13 + 605563550674482475*x^12 + 3125052390516629852*x^11 + 3434353753938817079*x^10 + 2199180089161294937*x^9 + 4128993677150612079*x^8 + 875038461592559534*x^7 + 1344699457303227348*x^6 + 3605318452000064928*x^5 + 1825112182884559504*x^4 + 4214849563830404245*x^3 + 3018789469914511583*x^2 + 4256870332540451928*x + 3478109193918270445
R = 10529800129354981*x^64 + 4658846300069202283*x^63 + 1343603688498785880*x^62 + 77535778799313918*x^61 + 3909004297055292936*x^60 + 1574062357470841720*x^59 + 2255026177942473610*x^58 + 2913895405335010190*x^57 + 910153010204378491*x^56 + 4823161627331431259*x^55 + 4314926186108070132*x^54 + 3776194104903441585*x^53 + 4218241384907734159*x^52 + 2928099962473177675*x^51 + 3620663369166129209*x^50 + 4671199329340054093*x^49 + 2953252709684913819*x^48 + 1470028746745533363*x^47 + 393509208258687360*x^46 + 2631641671658679748*x^45 + 4823463900549231672*x^44 + 22025139085889956*x^43 + 3905072220448754367*x^42 + 3525611426409694274*x^41 + 1087703571442464513*x^40 + 983613039355879671*x^39 + 2292836760450398296*x^38 + 2429042383184252432*x^37 + 4241866215562144008*x^36 + 3567456235250802214*x^35 + 289826756486726727*x^34 + 3070079221437908111*x^33 + 3164478508626375897*x^32 + 4028195041942471423*x^31 + 1611744044712776226*x^30 + 682031605725048858*x^29 + 2334009162012075842*x^28 + 1056698946696323305*x^27 + 1193918408929283326*x^26 + 1546583097398597126*x^25 + 632624061599387394*x^24 + 3924194912006864689*x^23 + 836241738980292724*x^22 + 2019639656826418643*x^21 + 646182266409329495*x^20 + 3568811299250961381*x^19 + 4024124722170180214*x^18 + 2765626713849083593*x^17 + 830125243533734584*x^16 + 3773807917205041413*x^15 + 4579071273569219071*x^14 + 4169012455774239610*x^13 + 2779202281389813792*x^12 + 1668767138196611027*x^11 + 3668902156196312613*x^10 + 2118966174503976203*x^9 + 2876683474352545557*x^8 + 4749450906737437136*x^7 + 2048549559963146669*x^6 + 2337906091414592304*x^5 + 3234395871197583532*x^4 + 624006023034932764*x^3 + 1020142386943254010*x^2 + 4346889740151908150*x + 2337193413394346074
c = [big list of polynomials...]

Solution

This is just Goldwasser-Micali but over polynomials instead of integers, making the cryptosystem completely insecure as we can easily factor the polynomial.

Solve script:

from Crypto.Util.number import long_to_bytes
from tqdm import tqdm

p = 4832823609987476353
PR.<x> = PolynomialRing(GF(p))

exec(open('output.txt', 'r').read().replace('^', '**'))

P = factor(PQ)[0][0]

o = ''
NP = p**P.degree()
for x in tqdm(c):
    if power_mod(x, (NP-1)//2, P) == 1:
        o = '1' + o
    else:
        o = '0' + o

print(long_to_bytes(int(o, 2)))

Flag: SECCON{p01y-p01y-p3r0-p3r0-hy0ukun-p3r0p3r0}

urara

SECKON -- Kon, who is initiated into cryptography, said: "I can tell the fortune-flag with this -- Elliptic RSA kokkuri-san."

task.sage:

from flag import flag

p = random_prime(1 << 1024)
q = random_prime(1 << 1024)
n = p * q

print("n =", n)

# ---

x = int.from_bytes(flag, "big")
y = randint(0, n-1)

a = randint(0, n-1)
b = (y^2 - (x^3 + a*x)) % n

EC = EllipticCurve(Zmod(n), [a, b])

P = EC((x, y))
Q = 2 * P

print("a, b =", [a, b])
print("Q =", Q.xy())

# ---

m = int.from_bytes(flag, "big")
t = randint(0, n-1)

c = power_mod(m + t, 65537, n)
print("t =", t)
print("c =", c)

output.txt:

n = 2495486283720196414658156567206136253284019243567958059321851922493511599099119079680539265897209530360296446936208426800428584598438104476991265428916133300767614183255586657557318228860960807727808759584720952822528262134841932977582943502095440882371004412919346559104839698667880585368725210776035801955698546309524104974030342228550787050046049567579065187788994920743809520302849445149655730482323230359606160072691147584028808470430189686361894038637340270209743137983546710783035439259335812370392005195583920997311705713592323771863115626855381027900474814101769171537793566286513448923754562724664313084249
a, b = [972698759004177594974248512452291945375078088533797369007356091167161417126661888563796734970930291849416186353401136601333663184182496443559710260512865444011720544123349975347739686656458945047235004231083887412945922041617098821848109846466185381123572906286526866381831235952511603159063112700803240801865531290422765608302160438343367509056504904308915457764244188011067916227743467457188390983251694692503189881215955070503001896424929414573915023552143884558308649592326241873353092050570518609492131325132956538067260949200100411641491893433056989039052880009034587425997261355587991692486739450094236514758, 1008573312161911000752400660247274100068850370101842340234132233694416751783423219213618251410638912974573281248522724039762013929414424219508458136249643022502332214316678524707691239057071086157162469422064755831275222236081328847657177640054036054045406160824940362440246044883298682522453311877923136432805003451856768017606479097933453907524689590456734108278484158414310289226885363416716427913861763258366781222560451163637643863000635404382308239958732271399310367790172837289160588101927655476531792837448724884102324974548266581640538857040307464673210901987003942198966596512095342443290488073222934653919]
Q = (867873247748174812072354447691943457644353996950272562674084117171032057450250434260859133245258701778341990173401264117064176603158749478700828272476995001485212129112894717807517326303812223951203313709014636942885555951223369106229497656316475383382128690099423171335569734684044941751080119216645566879454705354381241993772833561805053182217457917853140417414526348110486320351897963479122149636934280817200288672007854340543650563779551397976130991102876798375410531876063549460135790157054904126255613039452837589835705186004228042174285947129036321556613553671390037190356528190615214682864974887455909937619, 92156177218703573237225387608427402840283864799028130419669842561042657427033824263488342006248150114770090783060742870361337890590575949279141298574463897596258155388694505972290467228718686940706114514588166273676766526477678084721956511277781446249434968683955693367295727100489236602819441636378541120672736441095144636166942675405988795394557885388103901609694713050343823947711145939998064604641585844723037739727543720657955244689568060357318664843191704220939056774964806734882132924887657592200535178476768157269833478823542760608627255145238265363439669379993951234531206810550094244882515659269421133342)
t = 1777168232191821289919361506719035105250381465284676268198289506955330183480124536544599410896048478441274216496360402574201869585399683211082212730215235958242478585658417025279266624856606193964114464891213954565004165135702759126347979656143036294768812017453240638705726695168190715353794422332588623776474921669253740204759173522894816230138329334719993075279033623376817492761735171138485911978022373863743336360226609344072307935615642938848948516305275434543979476810981458780983782786892497139062392102615609343631554433368313342218231607432462736876822618694937755989879907893923918048177205572935961542238
c = 2495229390232434790849433815327288468942817979063945643796061305651846860246802186265725586015982098870449933396313764591953669092562225099204762704457578001689923221436404745009925073617272135602713059363827274464818599027905362654459980006227162213728037809437236173304627762460414746305401818555455721634808613093466198536909678291636025089911028651869899954385806560064211623734732747231127694454204886697599833768585606205744494003870149200884542308351359803929906608329439509726117597736110772616668829705345022404944932702135376373114568136049373919012494457087384217492589157659130773882703580148119446812556

Solution

Looking at the handout code, we see that the ECC part and RSA part have almost nothing to do with each other. The fact that we are given the encryption of $m + t$ in the RSA part however hints at the Franklin-Reiter related-message attack.

Let $E : y^2 = x^3 + ax + b$ be an elliptic curve, let $P = (x, y)$ and let $Q = (Q_x, Q_y) = 2P$ . Then, by the point addition formula,

\begin{aligned} Q_x &\equiv \left (\frac{3x^2 + a}{2y} \right )^2 - 2x \pmod n \\ \implies &Q_x + 2x \equiv \frac{(3x^2 + a)^2}{4y^2} \pmod n \\ \implies (3x^2 + a)^2 &+ 4y^2 (Q_x + 2x) \equiv 0 \pmod n \\ \implies (3x^2 + a)^2 &+ 4(x^3 + ax + b)(Q_x + 2x) \equiv 0 \pmod n \end{aligned}

which is a univariate polynomial in $x$ .

So let

g(x) \equiv (3x^2 + a)^2 + 4(x^3 + ax + b)(Q_x + 2x) \pmod n

Now notice from the RSA part, we are given $t$ and $c$ such that

c \equiv (x + t)^e \pmod n

Letting

f(x) \equiv (x+t)^e - c \pmod n

we see that $f(x)$ and $g(x)$ both have $m$ (the flag) as a root. Therefore $x - m$ divides both polynomials. We can compute the GCD of the two polynomials efficiently using the Euclidean algorithm. From this, we can easily recover the flag.

Solve script:

n = 2495486283720196414658156567206136253284019243567958059321851922493511599099119079680539265897209530360296446936208426800428584598438104476991265428916133300767614183255586657557318228860960807727808759584720952822528262134841932977582943502095440882371004412919346559104839698667880585368725210776035801955698546309524104974030342228550787050046049567579065187788994920743809520302849445149655730482323230359606160072691147584028808470430189686361894038637340270209743137983546710783035439259335812370392005195583920997311705713592323771863115626855381027900474814101769171537793566286513448923754562724664313084249
a, b = [972698759004177594974248512452291945375078088533797369007356091167161417126661888563796734970930291849416186353401136601333663184182496443559710260512865444011720544123349975347739686656458945047235004231083887412945922041617098821848109846466185381123572906286526866381831235952511603159063112700803240801865531290422765608302160438343367509056504904308915457764244188011067916227743467457188390983251694692503189881215955070503001896424929414573915023552143884558308649592326241873353092050570518609492131325132956538067260949200100411641491893433056989039052880009034587425997261355587991692486739450094236514758, 1008573312161911000752400660247274100068850370101842340234132233694416751783423219213618251410638912974573281248522724039762013929414424219508458136249643022502332214316678524707691239057071086157162469422064755831275222236081328847657177640054036054045406160824940362440246044883298682522453311877923136432805003451856768017606479097933453907524689590456734108278484158414310289226885363416716427913861763258366781222560451163637643863000635404382308239958732271399310367790172837289160588101927655476531792837448724884102324974548266581640538857040307464673210901987003942198966596512095342443290488073222934653919]
t = 1777168232191821289919361506719035105250381465284676268198289506955330183480124536544599410896048478441274216496360402574201869585399683211082212730215235958242478585658417025279266624856606193964114464891213954565004165135702759126347979656143036294768812017453240638705726695168190715353794422332588623776474921669253740204759173522894816230138329334719993075279033623376817492761735171138485911978022373863743336360226609344072307935615642938848948516305275434543979476810981458780983782786892497139062392102615609343631554433368313342218231607432462736876822618694937755989879907893923918048177205572935961542238
c = 2495229390232434790849433815327288468942817979063945643796061305651846860246802186265725586015982098870449933396313764591953669092562225099204762704457578001689923221436404745009925073617272135602713059363827274464818599027905362654459980006227162213728037809437236173304627762460414746305401818555455721634808613093466198536909678291636025089911028651869899954385806560064211623734732747231127694454204886697599833768585606205744494003870149200884542308351359803929906608329439509726117597736110772616668829705345022404944932702135376373114568136049373919012494457087384217492589157659130773882703580148119446812556
e = 0x10001
Qx, Qy = (867873247748174812072354447691943457644353996950272562674084117171032057450250434260859133245258701778341990173401264117064176603158749478700828272476995001485212129112894717807517326303812223951203313709014636942885555951223369106229497656316475383382128690099423171335569734684044941751080119216645566879454705354381241993772833561805053182217457917853140417414526348110486320351897963479122149636934280817200288672007854340543650563779551397976130991102876798375410531876063549460135790157054904126255613039452837589835705186004228042174285947129036321556613553671390037190356528190615214682864974887455909937619, 92156177218703573237225387608427402840283864799028130419669842561042657427033824263488342006248150114770090783060742870361337890590575949279141298574463897596258155388694505972290467228718686940706114514588166273676766526477678084721956511277781446249434968683955693367295727100489236602819441636378541120672736441095144636166942675405988795394557885388103901609694713050343823947711145939998064604641585844723037739727543720657955244689568060357318664843191704220939056774964806734882132924887657592200535178476768157269833478823542760608627255145238265363439669379993951234531206810550094244882515659269421133342)

pgcd = lambda g1, g2: g1.monic() if not g2 else pgcd(g2, g1%g2)

P.<x> = PolynomialRing(Zmod(n))
f = (x + t)^e - c
g = (3*x^2 + a)^2 - 4*(x^3 + a*x + b)*(2*x + Qx)
m = -pgcd(f, g).coefficients()[0]
print(bytes.fromhex(hex(m)[2:]).decode())

Flag: SECCON{0n3_tw0_thr33_f0ur_fiv3_six_chachan}

sharsable

You must collect exponents from Alice and Bob.

generate.py:

from Crypto.Util.number import getPrime, GCD
from flag import FLAG
import random

def egcd(a, b):
    r0, r1 = a, b
    s0, s1 = 1, 0
    t0, t1 = 0, 1
    while r1 > 0:
        q = r0 // r1
        r0, r1 = r1, r0 % r1
        s0, s1 = s1, s0 - q * s1
        t0, t1 = t1, t0 - q * t1
    return s0, t0

def generateKey():
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    phi = (p-1)*(q-1)

    while True:
        d1 = getPrime(int(n.bit_length()*0.16))
        e1 = random.randint(1, phi)
        ed1 = e1 * d1 % phi

        d2 = getPrime(int(n.bit_length()*0.16))
        e2, k = egcd(d2, phi)
        e2 = e2 * (phi + 1 - ed1) % phi
        ed2 = e2 * d2 % phi

        if GCD(e1, e2) > 10:
            break

    assert((ed1 + ed2) % phi == 1)

    return (n, (e1, d1), (e2, d2))

n, A, B = generateKey()
M = int.from_bytes(FLAG, 'big')
C1 = pow(M, A[0], n)
C2 = pow(M, B[0], n)
assert(pow(C1, A[1], n) * pow(C2, B[1], n) % n == M)

import json
print(json.dumps({
    "n": n,
    "A": (A[0], C1),
    "B": (B[0], C2),
    #"d": (A[1], B[1]), # for debug
    }))

output:

{"n": 142793817321992828777925840162504083304079023834001118099549928854335392622287928254035247188624975743042449746066633491912316354241339908190889792327014012472372654378644158878787350693992259970146885854641856991605625756536504266728483088687985429310233421251081614258665472164668993082471923690196082829593, "A": [82815162880874815458042429141267540989513396527359063805652845923737062346339641683097075730151688566721221542188377672708478777831586255213972947470222613130635483227797717393291856129771004300757155687587305350059401683671715424063527610425941387424425367153041852997937972925839362190900175155479532582934, 108072697038795075732704334514926058617161875495016327352871122917196026504758904760148391499245235850616838765611460630089577948665981247735905622903872682862860306107704253287284051312867625831877418240290183661755993649928399992531008191618616452091127799880839665225093055618092869662205901927957599941568], "B": [84856171747859965508406237198459622554468224770252249975158471902036102010991476445962577679301719179079633469099994226630172251817358960347828156301869905575867853640850107406452911333646573296923235424617864473580743418995994067645338437540627399276292679100115018844287273293945121023787594592185295794983, 101960082023987498941061751761131381167414505957511290567652602520714324823481487410890478130601013005035303795327512367595187718926017321227779179404306882163521882309833982882201152721855538832465833869251505131262098978117904455226014402089126682222497271578420753565370375178303927777655414023662528363360]}

Solution

We look to the generateKey function to find the vulnerability. Something that sticks out as suspicious is the size of the private exponents d1 and d2 (which are the values we are trying to recover). They are on the order of $n^{0.16}$ which is pretty suspicious. We also note that $\gcd(e_1, e_2) > 10$ so that rules out an easy common modulus attack. However, we see that

e_1 d_1 + e_2 d_2 \equiv 1 \pmod{\varphi(n)}

which is given in the assert statement in the generateKey function.

Writing this out, we see that

\begin{aligned} e_1 d_1 + e_2 d_2 &\equiv 1 \pmod{\varphi(n)} \\ \implies e_1 d_1 + e_2 d_2 &= k\varphi(n) + 1, \qquad k \in \mathbb{Z} \\ &= k(n - p - q + 1) + 1 \\ \implies e_1 d_1 + e_2 d_2 &\equiv -k(p + q - 1) + 1 \pmod n \end{aligned}

Now, since $e_1$ and $e_2$ are on the order of $\varphi(n)$ it follows that $k$ will be on the order of $d_1$ and $d_2$ , so around $n^{0.16}$ . $p$ and $q$ should be on the order of $n^{0.5}$ (since they are both randomly generated 512 bit primes), so bringing this all together, we gather that the RHS of the last equivalence is on the order of $n^{0.66}$ . This gives us the following result.

e_1 d_1 + e_2 d_2 \approx -n^{0.66} \pmod n

Now consider the lattice spanned by the rows of the matrix

L = \begin{bmatrix} e_1 & n^{0.5} & 0 \\ e_2 & 0 & n^{0.5} \\ n & 0 & 0 \end{bmatrix}

Letting $\mathbf{b_1}, \mathbf{b_2}$ and $\mathbf{b_3}$ denote the three rows, we see that

d_1 \mathbf{b_1} + d_2 \mathbf{b_2} + c \mathbf{b_3} = (-n^{0.66}, d_1 n^{0.5}, d_2 n^{0.5})

for some $c \in \mathbb{Z}$ , will be a vector close to $(-n^{0.66}, n^{0.5}, n^{0.5})$ . So if we throw this at some CVP algorithm, we should be able to read off $d_1$ and $d_2$ from the result!

More precisely, there should probably be some constant in front of the $-n^{0.66}$ , but in this case, it looks like we're lucky and $1$ works well as the constant (see rkm0959's writeup for a better explanation).

Solve script:

from Crypto.Util.number import long_to_bytes

n = 142793817321992828777925840162504083304079023834001118099549928854335392622287928254035247188624975743042449746066633491912316354241339908190889792327014012472372654378644158878787350693992259970146885854641856991605625756536504266728483088687985429310233421251081614258665472164668993082471923690196082829593
e1 = 82815162880874815458042429141267540989513396527359063805652845923737062346339641683097075730151688566721221542188377672708478777831586255213972947470222613130635483227797717393291856129771004300757155687587305350059401683671715424063527610425941387424425367153041852997937972925839362190900175155479532582934
C1 = 108072697038795075732704334514926058617161875495016327352871122917196026504758904760148391499245235850616838765611460630089577948665981247735905622903872682862860306107704253287284051312867625831877418240290183661755993649928399992531008191618616452091127799880839665225093055618092869662205901927957599941568
e2 = 84856171747859965508406237198459622554468224770252249975158471902036102010991476445962577679301719179079633469099994226630172251817358960347828156301869905575867853640850107406452911333646573296923235424617864473580743418995994067645338437540627399276292679100115018844287273293945121023787594592185295794983
C2 = 101960082023987498941061751761131381167414505957511290567652602520714324823481487410890478130601013005035303795327512367595187718926017321227779179404306882163521882309833982882201152721855538832465833869251505131262098978117904455226014402089126682222497271578420753565370375178303927777655414023662528363360

def babai(A, w):
    A = A.LLL(delta=0.75)
    G = A.gram_schmidt()[0]
    t = w
    for i in reversed(range(A.nrows())):
        c = ((t * G[i]) / (G[i] * G[i])).round()
        t -= A[i] * c
    return w - t

L = Matrix(ZZ, [
    [e1, n^0.5, 0],
    [e2, 0, n^0.5],
    [n, 0, 0]
])

t = vector(ZZ, [-n^0.66, n^0.5, n^0.5])
D = babai(L, t)
d1 = D[1]//int(n^0.5)
d2 = D[2]//int(n^0.5)
flag = pow(C1, d1, n) * pow(C2, d2, n) % n
flag = long_to_bytes(flag)
print(flag.decode())

Flag: SECCON{sh4r4bl3_r54_1s_useful?}

crypto01

Our new HumaGear "Crypto01" encrypted the FLAG.

challenge.py:

from sage.all import *
from flag import flag
from functools import reduce

def encrypt(m, e, n):
    n = int(n)
    size = n.bit_length() // 2
    m_low = m & ((1 << size) - 1)
    m_high = (m >> size)

    b = (m_low**2 - m_high**3) % n
    EC = EllipticCurve(Zmod(n), [0, b])

    return (EC((m_high, m_low)) * e).xy()

def decrypt(c, d, n):
    n = int(n)
    size = n.bit_length() // 2

    c_high, c_low = c
    b = (c_low**2 - c_high**3) % n
    EC = EllipticCurve(Zmod(n), [0, b])
    m_high, m_low = (EC((c_high, c_low)) * d).xy()
    m_high, m_low = int(m_high), int(m_low)

    return (m_high << size) | m_low

def gen_prime(size):
    p = random_prime(1 << size)
    while p % 3 != 2:
        p = random_prime(1 << size)

    q = random_prime(1 << size)
    while q % 3 != 2:
        q = random_prime(1 << size)

    if q > p:
        p, q = q, p

    return int(p), int(q)



SIZE = 512
HINTSIZE = 96
N = 3

flag = int.from_bytes(flag, "big")
assert flag < (1 << SIZE)

masks = [randint(1 << (SIZE-1), 1 << SIZE) for _ in range(N)]
masked_flag = reduce(lambda a, b: a ^ b, masks, flag)


count = 0
ciphertexts = []
while count < N:
    try:
        p, q = gen_prime(SIZE)
        n = p * q

        x = random_prime(int(n ** 0.40))
        y = random_prime(int(sqrt(2 * n // (144 * x*x))))
        zbound = -1 * int(round(((p-q) * (n ** 0.25) * y) / (3 * (p + q))))

        z_ = zbound + ((p + 1)*(q + 1)*y - zbound) % x
        e = ((p + 1) * (q + 1) * y - z_) // x
        d = inverse_mod(e, (p + 1)*(q + 1))

        assert (x*y*x*y < (2 * n // 144))
        assert (gcd(x, y) == 1)

        d = inverse_mod(e, (p+1)*(q+1))
        c = encrypt(masks[count], e, n)
        assert decrypt(c, d, n) == masks[count]

        ciphertexts.append({
            "n": n,
            "e": e,
            "c": c,
            "hint": p & ((1<<HINTSIZE)-1)
        })
        count += 1
    except KeyboardInterrupt:
        break
    except (ZeroDivisionError, OverflowError):
        pass


print("masked_flag = " ,masked_flag)
print("ciphertexts = ", ciphertexts)

output.txt:

masked_flag =  8077275413285507538357977814283814136815067070436948406142717872478737670143034266458000767181162602217137657160614964831459653429727469965712631294123225
ciphertexts =  [{'n': 886775008733978973740257525650074677865489026053222554158847150065839924739525729402395428639350660027796013999414358689067171124475540042281892825140355436902197270317502862419355737833115120643020255177020178331283541002427279377648285229476212651491301857891044943211950307475969543789857568915505152189, 'e': 428559018841948586040450870835405618958247103990365896475476359721456520823105336402250177610460462882418373365551361955769011150860740050608377302711322189733933012507453380208960247649622047461113987220437673085, 'c': (80103920082434941308951713928956232093682985133090231319482222058601362901404235742975739345738195056858602864819514638254604213654261535503537998613664606957411824998071339098079622119781772477940471338367084695408560473046701072890754255641388442248683562485936267601216704036749070688609079527182189924, 842529568002033827493313169405480104392127700904794758022297608679141466431472390397211660887148306350328312067659313538964875094877785244888004725864621826211254824064492961341512012172365417791553455922872091302295614295785447354268009914265614957287377743897340475899980395298019735631787570231395791009), 'hint': 59051335744243522933765175665}, {'n': 37244493713246153778174562251362609960152354778990433088693945121840521598316370898923829767722653817418453309557995775960963654893571162621888675965423771020678918714406461976659339420718804301006282789714856197345257634581330970033427061846386874027391337895557558939538516456076874074642348992933600929747, 'e': 152657520846237173082171645969128953029734435220247551748055538422696193261367413610113664730705318574898280226247526051526753570012356026049784218573767765351341949785570284026342156807244268439356037529507501666987, 'c': (14301224815357080657295611483943004076662022528706782110580690613822599700117720290144067866898573981166927919045773324162651193822888938569692341428439887892150361361566562459037438581637126808773605536449091609307652818862273375400935935851849153633881318435727224452416837785155763820052159016539063161774, 711567521767597846126014317418558888899966530302382481896965868976010995445213619798358362850235642988939870722858624888544954189591439381230859036120045216842190726357421800117080884618285875510251442474167884705409694074544449959388473647082485564659040849556130494057742499029963072560315800049629531101), 'hint': 56178670950277431873900982569}, {'n': 6331516792334912993168705942035497262087604457828016897033541606942408964421467661323530702416001851055818803331278149668787143629857676822265398153269496232656278975610802921303671791426728632525217213666490425139054750899596417296214549901614709644307007461708968510489409278966392105040423902797155302293, 'e': 2041454339352622193656627164408774503102680941657965640324880658919242765901541504713444825283928928662755298871656269360429687747026596290805541345773049732439830112665647963627438433525577186905830365395002284129, 'c': (4957181230366693742871089608567285130576943723414681430592899115510633732100117146460557849481224254840925101767808247789524040371495334272723624632991086495766920694854539353934108291010560628236400352109307607758762704896162926316651462302829906095279281186440520100069819712951163378589378112311816255944, 2715356151156550887523953822376791368905549782137733960800063674240100539578667744855739741955125966795181973779300950371154326834354436541128751075733334790425302253483346802547763927140263874521376312837536602237535819978061120675338002761853910905172273772708894687214799261210445915799607932569795429868), 'hint': 70953285682097151767648136059}]

Solution

The key thing to notice is that zbound and z_ are actually somewhat useless. Since z_ (which we will write as $z'$ ) is computed mod x, it follows that $z' < x$ . So, in the definition of e, the - z_ term doesn't do anything when performing integer division by $x$ :

\begin{aligned} e &= \left \lfloor \frac{(p+1)(q+1)y - z'}{x} \right \rfloor \\ &= \left \lfloor \frac{(p+1)(q+1)y}{x} \right \rfloor \end{aligned}

From this, we get

\begin{aligned} \frac{e}{(p+1)(q+1)} &\approx \frac{y}{x} \\ \implies \frac{e}{n} &\approx \frac{y}{x} \end{aligned}

Now, similarly to how it is done in Wiener's attack, we can easily find $x$ and $y$ given $e$ and $n$ . We do this by checking the convergents of $\frac{e}{n}$ . If we find one that has a prime numerator and prime denominator, those will be our candidates for $y$ and $x$ respectively.

Once we have $x$ and $y$ , we use these to approximate $p+q$ and therefore get a good approximation for $p$ .

From the above, we have

\begin{aligned} e &\approx \frac{(p+1)(q+1)y}{x} \\ \implies (p+1)(q+1) &\approx \frac{ex}{y} \\ \implies n + p + q + 1 &\approx \frac{ex}{y} \\ \implies p + q &\approx \frac{ex}{y} - n - 1 \end{aligned}

Now, similarly to my 1337crypt challenge from DownUnderCTF, we construct a polynomial whose roots will give us an approximation for $p$

(x+p)(x+q) = x^2 + (p+q)x + n

It turns out this approximation for $p$ is accurate to around 200 MSB. The hint gives us the 96 LSB of $p$ , so in total we have around 296 known bits of $p$ . Since $p$ is only 512 bits, this gives us enough information to recover $p$ completely using Coppersmith's method!

We use the polynomial in $\mathbb{Z}_n[x]$

f(x) = 2^{312} p' + 2^{96} x + \text{hint}

where $p'$ is the 200 known MSB of $p$ .

Once we've recovered the primes, the rest is easy.

Solve script:

masked_flag =  8077275413285507538357977814283814136815067070436948406142717872478737670143034266458000767181162602217137657160614964831459653429727469965712631294123225
ciphertexts =  [{'n': 886775008733978973740257525650074677865489026053222554158847150065839924739525729402395428639350660027796013999414358689067171124475540042281892825140355436902197270317502862419355737833115120643020255177020178331283541002427279377648285229476212651491301857891044943211950307475969543789857568915505152189, 'e': 428559018841948586040450870835405618958247103990365896475476359721456520823105336402250177610460462882418373365551361955769011150860740050608377302711322189733933012507453380208960247649622047461113987220437673085, 'c': (80103920082434941308951713928956232093682985133090231319482222058601362901404235742975739345738195056858602864819514638254604213654261535503537998613664606957411824998071339098079622119781772477940471338367084695408560473046701072890754255641388442248683562485936267601216704036749070688609079527182189924, 842529568002033827493313169405480104392127700904794758022297608679141466431472390397211660887148306350328312067659313538964875094877785244888004725864621826211254824064492961341512012172365417791553455922872091302295614295785447354268009914265614957287377743897340475899980395298019735631787570231395791009), 'hint': 59051335744243522933765175665}, {'n': 37244493713246153778174562251362609960152354778990433088693945121840521598316370898923829767722653817418453309557995775960963654893571162621888675965423771020678918714406461976659339420718804301006282789714856197345257634581330970033427061846386874027391337895557558939538516456076874074642348992933600929747, 'e': 152657520846237173082171645969128953029734435220247551748055538422696193261367413610113664730705318574898280226247526051526753570012356026049784218573767765351341949785570284026342156807244268439356037529507501666987, 'c': (14301224815357080657295611483943004076662022528706782110580690613822599700117720290144067866898573981166927919045773324162651193822888938569692341428439887892150361361566562459037438581637126808773605536449091609307652818862273375400935935851849153633881318435727224452416837785155763820052159016539063161774, 711567521767597846126014317418558888899966530302382481896965868976010995445213619798358362850235642988939870722858624888544954189591439381230859036120045216842190726357421800117080884618285875510251442474167884705409694074544449959388473647082485564659040849556130494057742499029963072560315800049629531101), 'hint': 56178670950277431873900982569}, {'n': 6331516792334912993168705942035497262087604457828016897033541606942408964421467661323530702416001851055818803331278149668787143629857676822265398153269496232656278975610802921303671791426728632525217213666490425139054750899596417296214549901614709644307007461708968510489409278966392105040423902797155302293, 'e': 2041454339352622193656627164408774503102680941657965640324880658919242765901541504713444825283928928662755298871656269360429687747026596290805541345773049732439830112665647963627438433525577186905830365395002284129, 'c': (4957181230366693742871089608567285130576943723414681430592899115510633732100117146460557849481224254840925101767808247789524040371495334272723624632991086495766920694854539353934108291010560628236400352109307607758762704896162926316651462302829906095279281186440520100069819712951163378589378112311816255944, 2715356151156550887523953822376791368905549782137733960800063674240100539578667744855739741955125966795181973779300950371154326834354436541128751075733334790425302253483346802547763927140263874521376312837536602237535819978061120675338002761853910905172273772708894687214799261210445915799607932569795429868), 'hint': 70953285682097151767648136059}]

def decrypt(c, d, n):
    n = int(n)
    size = n.bit_length() // 2

    c_high, c_low = c
    b = (c_low**2 - c_high**3) % n
    EC = EllipticCurve(Zmod(n), [0, b])
    m_high, m_low = (EC((c_high, c_low)) * d).xy()
    m_high, m_low = int(m_high), int(m_low)

    return (m_high << size) | m_low

def recover_x_and_y(e, n):
    for yx in continued_fraction(e/n).convergents():
        y = yx.numerator()
        x = yx.denominator()
        if x.is_prime() and y.is_prime():
            return x, y

masks = []
for ct in ciphertexts:
    c, n, e, hint = ct['c'], ct['n'], ct['e'], ct['hint']
    x, y = recover_x_and_y(e, n)
    p_plus_q_approx = (x*e + x)//y - 1 - n
    p_approx = (p_plus_q_approx + isqrt(p_plus_q_approx^2 - 4 * n)) // 2
    p_top =  p_approx >> 312

    P.<x> = PolynomialRing(Zmod(n), implementation='NTL')
    f = 2^312 * p_top + 2^96 * x + hint
    f = f.monic()
    delta = f.small_roots(X=2^216, beta=0.5, epsilon=0.05)[0]
    
    p = int(2^312 * p_top + 2^96 * delta + hint)
    q = n//p
    d = inverse_mod(e, (p+1)*(q+1))

    masks.append(decrypt(c, d, n))

flag = reduce(lambda a, b: a ^^ b, masks, masked_flag)
print(bytes.fromhex(hex(flag)[2:]).decode())

Flag: SECCON{gut_poweeeeeeeeeeeeeer}