---
# System prepended metadata

title: b01lersCTF

---

I have participated in b01lersCTF with HKUSTFirebird and I solved 2 crypto challenges.


Crypto/half-big-rsa
```
import math
from Cryptodome.Util.number import getPrime, bytes_to_long, long_to_bytes
import os
import sys
num_bits = 4096
e = (num_bits - 1) * 2
n = getPrime(num_bits)




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

m = bytes_to_long(flag)
c = pow(m, e, n)
print(c)

with open("output.txt", "w") as f:
    f.write("e = {0}\n".format(e))
    f.write("n = {0}\n".format(n))
    f.write("c = {0}\n".format(c))

# e = 8190
# n = 665515140120452927777672138241759151799589898667434054796291409500701895847040006534274017960741836352283431369658890777476904763064058571375981053480910502427450807868148119447222740298374306206049235106218160749784482387828757815767617741823504974133549502118215185814010416478030136723860862951197024098473528800567738616891653602341160421661595097849964546693006026643728700179973443277934626276981932233698776098859924467510432829393769296526806379126056800758440081227444482951121929701346253100245589361047368821670154633942361108165230244033981429882740588739029933170447051711603248745453079617578876855903762290177883331643511001037754039634053638415842161488684352411211039226087704872112150157895613933727056811203840732191351328849682321511563621522716119495446110146905479764695844458698466998084615534512596477826922686638159998900511018901148179784868970554998882571043992165232556707995154316126421679595109794273650628957795546293370644405017478289280584942868678139801608538607476925924119532501884957937405840470383051787503858934204828174270819328204062103187487600845013162433295862838022726861622054871029319807982173856563380230936757321006235403066943155942418392650327854150659087958008526462507871976852849
# c = 264114212766855887600460174907562771340758069941557124363722491581842654823497784410492438939051339540245832405381141754278713030596144467650101730615738854984455449696059994199389876326336906564161058000092717176985620153104965134542134700679600848779222952402880980397293436788260885290623102864133359002377891663502745146147113128504592411055578896628007927185576133566973715082995833415452650323729270592804454136123997392505676446147317372361704725254801818246172431181257019336832814728581055512990705620667354025484563398894047211101124793076391121413112862668719178137133980477637559211419385463448196568615753499719509551081050176747554502163847399479890373976736263256211300138385881514853428005401803323639515624537818822552343927090465091651711036898847540315628282568055822817711675290278630405760056752122426935056309906683423667413310858931246301024309863011027878238814311176040130230980947128260455261157617039938807829728147629666415078365277247086868327600962627944218138488810350881273304037069779619294887634591633069936882854003264469618591009727405143494184122164870065700859379313470866957332849299246770925463579384528152251689152374836955250625216486799615834558624798907067202005564121699019508857929778460

```

We are given this classic format of RSA encryption, but something is weird is that ```e = 8190```, and n is just a prime instead of multiplication of two primes. In this case, $\phi$(n) is just n-1. and e and $\phi$(n) is not coprime. 

The problem is when e and $\phi$(n) is not coprime. The decoded cipher is not unique anymore. There is multiple i such that m<sub>i</sub><sup>e</sup> % n = c.

To solve this, we have to reduce $\phi$(n) such that $\phi$(n) and e is coprime again, only then we could calculate d. We done that with the following codes.

```
new_phi = (n-1)//gmpy2.gcd(e, n-1)
while gmpy2.gcd(e, new_phi) != 1:
    new_phi = new_phi//gmpy2.gcd(e, new_phi)
```

denote the new $\phi$(n) as $\phi'$(n) ,we could proceed to tackle the next problem -- multiple possibilities of decoded cipher.

Since solving m<sup>e</sup> % n = c does not give us unique result, we need to find (m*x)<sup>e</sup> % n = c instead, where x<sup>e</sup> % n = 1. and this is identical to finding multiple primitive k-th roots modulo n.
```
d = pow(e, -1, new_phi)
plaintext = pow(c, d, n)

i = 1
while True:

    un = pow(i, new_phi, n)
    i += 1
    try:
        pt = long_to_bytes((un * plaintext) % n).decode()
        print(pt)
    except:
        continue
```
flag: `bctf{Pr1M3_NUM83r5_4r3_C001_bu7_7H3Y_4r3_57r0N6_0N1Y_WH3N_7H3Y_4r3_MU171P113D_3V3N_1F_7H3Y_4r3_b1g}`


Crypto/count_the_counter

```
#!/bin/python3
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from secret import flag
import os


def Encrypt(key, message, nonce):
    cipher = AES.new(key, AES.MODE_CTR, nonce=long_to_bytes(nonce))
    return cipher.encrypt(message).hex()


def chal():
    key = os.urandom(16)
    print("Treat or Trick, count my thing. ")
    nonce_counter = 1
    print(Encrypt(key, flag, nonce_counter))
    while True:
        nonce_counter += 1
        to_enc = input("Give me something to encrypt: ")
        print(Encrypt(key, bytes.fromhex(to_enc), nonce_counter))


if __name__ == "__main__":
    chal()
```
brief idea:
valuenarble part is the way it generate the nonce..

the flag is encrypted with nonce_counter 0x10,
after sending 254 text to encrypt, the next message will be encrypted with nonce_counter 0x1000.

Since the IV is just generated with concatenating nonce_counter and fixed the length to be 16 bytes.
so now flag and 255th encryption are using the same nonce. Which after xoring encrypted flag and the 255th encryption then we will get back the flag.


flag: `bctf{there_is_a_reason_for_random_nonce_and_with_fixed_length_8c6bf5a1398d1f1d95f1}``