# ångstromCTF 2022 Writeups
## Randomly Sampled Algorithm
Since $\phi$ is given, we can compute $d$ as the inverse of $e\bmod \phi$, and then find $m\equiv c^d\bmod n$. We then get the flag by converting to hexadecimal -> ASCII.

Relevant code is below, full code is on [tio.run](https://tio.run/##zZM5bttgEIV7noKlBAjG7EuRKmdIbcA2EwuwSEFmEuj0yiORJjeICv6kOMt73wyv9/V9mfXx@H5bLuPX2/26Lk/f1vPH0/zz8jLdxvPlutzW8WOZfzyvy/PLfZ0@T@N5/jXdPqdhmMcvI6tSeralRoUYEQ6tYibv8iSJKKpkI5coDWdRCcch2Wnm1C0cHdaCcHXdSrRnUKpXNYkQXosbsRq7h1knnp2Jg8LDLS1T0b63fAQpQmsrUmiuVKVWppHsBKmc4k2BwkhnhCkJqQg3oT5LCRlyohydautTiDNRGGtyJAaZsnE3EXSklxf0FiVKREE3pUBBp0c3lLEZKkQnPGrqMIEcGGgOr7gz6W6raEVsUxYUugEsyAJOkYFGK1yKE5MVg5iRMCe8y86lgE7LkpghDZlmmz4840RBhMMhRBdssPYGp51cAb0y4d/TqNncWiE7QrMQR9zwC3mYFtqCABpizniX1FSgrRzIhwGgLQkGC3GwEHXBzB1NG2MOADYUVQDs9g4MB2cVorgLP1QGS2Uu8DbME7QJw0gg0MakyCx2gdTD9f38X69fAAPIAizzFoodIFTbKmmjsmAXIQCvo8wF/vaJhiR8YjM7NPZGuNa@kcHb2rJKYzcSpghD0UDBSMMKe@zWEFqNCxankdS82QUxx9igDIqG4Q3o/n7Gh@k0guVxuOC/6/L78Hoa307jfByG6@08r4d/vv7D5Xh8PP4A)

from Crypto.Util.number import long_to_bytes, inverse

d = inverse(e, phi)
m = pow(c, d, n)

print(long_to_bytes(m))

Flag: `actf{just_kidding_this_algorithm_wasnt_actually_randomly_sampled}`

## log log log
This seems like a standard discrete log problem, but the prime is constructed to be of the form $p=q\cdot2^{1024}+1$ (which, by the way, is called a [Proth prime](https://en.wikipedia.org/wiki/Proth_prime)). The order of the finite field `GF(p)` is $q\cdot2^{1024}$, which is nice because it has lots of factors, which makes us think of Pohlig-Hellman.

Well, using Pohlig-Hellman we can reduce the discrete log computation to a discrete log modulo $q$ and a discrete log modulo $2^{1024}$. We can do the discrete log modulo $2^{1024}$, but the other logarithm just seems infeasible. I guess the challenge is impossible then...

But wait, do we need the other logarithm? We know the flag is 880 bits, so if we find $e\bmod{2^{1024}}$ then that'll give us the flag, since the modulo operation with $2^{1024}$ preserves the 1024 lowest bits of $e$. That means we only need to find the value of the discrete logarithm that we can compute.

Code in sage:

q = 127049168626532606399765615739991416718436721363030018955400489736067198869364016429387992001701094584958296787947271511542470576257229386752951962268029916809492721741399393261711747273503204896435780180020997260870445775304515469411553711610157730254858210474308834307348659449375607755507371266459204680043
p = q * 2^1024 + 1

K = GF(p)

g = K(3)
a = K(0xaf99914e5fb222c655367eeae3965f67d8c8b3a0b3c76c56983dd40d5ec45f5bcde78f7a817dce9e49bdbb361e96177f95e5de65a4aa9fd7eafec1142ff2a58cab5a755b23da8aede2d5f77a60eff7fb26aec32a9b6adec4fe4d5e70204897947eb441cc883e4f83141a531026e8a1eb76ee4bff40a8596106306fdd8ffec9d03a9a54eb3905645b12500daeabdb4e44adcfcecc5532348c47c41e9a27b65e71f8bc7cbdabf25cd0f11836696f8137cd98088bd244c56cdc2917efbd1ac9b6664f0518c5e612d4acdb81265652296e4471d894a0bd415b5af74b9b75d358b922f6b088bc5e81d914ae27737b0ef8b6ac2c9ad8998bd02c1ed90200ad6fff4a37)
flagbits = 880

g_ = g^q
a_ = g^q
f = a_.log(g_)
print((f % 2^flagbits).to_bytes(flagbits//8, 'big'))

Flag: `actf{it's log, it's log, it's big, it's heavy, it's wood, it's log, it's log, it's better than bad, it's good}`

## Strike-Slip Fault
The three flipped bits correspond to either adding or subtracting three powers of two from the exponent. So basically, we are getting $c^{d'}\equiv m'\pmod n$, where $d'=d+A$ and $m'=m\cdot k$.

We start with the congruence $c^{d+A}\equiv k\cdot m\pmod n$. If we raise both sides to the power of $e$, then we get $c\cdot c^{eA}\equiv c^{ed+eA}\equiv k^e\cdot m^e\equiv k^e\cdot c\pmod n$. Dividing by $c$ gives $(c^e)^A\equiv k^e\pmod n$.

If we can find $A$, then we can finish the problem by computing $m\equiv m'\cdot k^{-1}\equiv m'\cdot (c^A)^{-1}\pmod n$. If we try bruteforcing the positions and signs of the 3 bits, then we have to do $2^3\cdot\binom{4096}{3}$ operations, which is about [91 billion](https://www.wolframalpha.com/input?i=2%5E3*%284096+choose+3%29). Too much!

To speed this up, we use meet-in-the-middle to improve computation time at the expense of memory. By storing the values of $(c^e)^X$ where $X$ is a power of two (from $2^{-4096}$ to $2^{4096}$), we only need to bruteforce two bits and look up the remaining value, resulting in the storage of $8192$ numbers and a computation of $2^2\cdot\binom{4096}{2}$ operations, or about [33 million](https://www.wolframalpha.com/input?i=2%5E2*%284096+choose+2%29). Definitely much more feasible. Code for bruteforcing below:

from Crypto.Util.number import bytes_to_long, long_to_bytes
from itertools import combinations
from tqdm import tqdm

BITS = 4096
n = 900070490622067320191637256322689412527951600989690014040742293402515652299807355416973524079799412242303695005849373445039400849591465597575071172369743191868426614517714438100741689051321511330353068870085391955380005924193452388879170080569217611534666723431228876665400462326676136834184598097637612462138913958737759322989904101853151206852072163254977079626441345648695044414743061561749348880019607938930572091154083635100263637181513759943165217032366307235262290149121982361740356299744695043277615922872281013512722579789196565526621382570308445038543830946971870143416647314522450656476380450926273955034941922166822345239863969969054173792809511555294506499479460733800203789975490744756171199513541914459052812970878813532508200185561086389173320140400837553390150640118664644728326976956623287728071670363574828765499081630098395101207132121557269428414754204021602411843144222862499913321787608802795431375613453451646357431858538087082423774836125541442108814662883958785416540932102786177408197877642161771714550028264013960050526390792232071691880271991611403599658754594252925331797512039370218705211962522382739680885820067113131946086305783275655204391316332325661610449937310593926456756974934432806107508584687
e = 65537
c = 785019041003063094605338644855048946920785904799316056061128856210648574008947823318103541165223596391441869599653542367469582749735833238881174760706303204193239490503494128261465176354669635814736470937192039240288549501040533102957388190144367063971050093258087028919607189745941929361743460532173075128757057170184845810592063392093611909588608434601111240804241210939629912198253922278311726074613374311364714503593835714701261515902458295964850200883428876941854713297600424159346665228238295844165261930957085099153766532230753418227132506795445835713828219025117217211988132423808868878491252074351084194298227654253015597086572860607173699553442586206642744564518363534136736457282374055689877416438808797889637908338960048452523853477755423540348739016013753910186174575168439451877576061110984631119994270572126858635951627682166569924669328090525845842805274374629938562576743743090674720310052196389604757172761607674745732712177986201837422518542301831341463977319044721933558836609327149863674429302791872305204502140781352055289953107204260973578971800635948027688728015052061073091633479965577903274852755170355267952134264963602557305761624298274953157061326235764865240265336589063356964395136173662984407099988044
mm = bytes_to_long(b'\xc0K*/\xfb{\xfd\xa36\xfe\'\xfc(l\xa5\xe1Nf\x17\xad\x9eZ"\xbd\xc2%rs\xbe\xb9\xf3\xc5e6\xeb\x9e\xceD\x86.\x03\xb2s\x95\xc2\xac}\xee \x9f\xb9\xbb\x87\x1c\x0b\t\x01D7\xcd\x05\xdcp\x84\x07K\xab\xc9\x14\x9e\x8b\xd5\x8e\xe4\xaeB\n(\r\xe3c\xbd\x97\xe9\x93&h5\xdf9\xaf%~\x9f&J\xf02\x9e\xd9JJe\xd6i\x85)\xd2\xb5\'\xe1x\xb6\xc5K\x84M\xbc_\x01\'\x80\xb5\xf5\x7f\xa1\x96\xbe\xe7\xb3R\xaa\xe7\xe0\x9c\xd4\xed\xde\n<\xdc\x16q\x10w\x8f\x1d\xa3XH\xe2M"C\xfa\x03\xdb\xf4\x00\xa0\xaf\x93=\x9fm\xb5\x94\xfa\xec\xf8\nd\xb1\x17\x8d\x84\x9f\xdfD\xb0FU\xd3\xc07q+\xcc|\xb7\xe7\x8dlk.\xa6S\xa3\x18\xbfi\x8e\xc2SW\\\xb4\x03o\xdd\xeb\xa41\x7fv\x8e\x07aka\x91i\xeb\xe0\xa6*\x17\x1f_*6\x90x\xcd\xaa$\xf9x\xadt\x00\xea\x01\x19\x11\xa9\xdd\xb6\xfa\x1e6\xa8<\x92\xf3w(\xbf;v\xe5\x92\n\xcd\x8ckD\xb1\x82\xe9\x16\x85\xbf\xbf81\xf6.\x9a\xbe\xe7\xf66+\xf4u\xce\xcf#\xb4i\x966\xbf\x96\xee568r\xc8\xd0\xfa\xf7\xfe\xd8>\x97j^\xbbc[\xc0\xe4\xf5\x9d\xb5\xac\xab2\xed\x90\x9cvf\x1a\xaa\xe2\xb27!h\xa5\xac\x0c\xff\xc8\x86F\x86\xaff\xdb\xc6\xc4\x94\xbd[\xf5\xf2\x85!\x1f\xf6\xb1.9\xc2\xf0>H\xd6 L\x9d\xe8\xf7V"\xfe"1\xf3I\xa9\xa9]\x10\x97&\xf6\xbb\xb3\xf4a_\x98\x85\x15v\xd4U\xfd\xeayj\xf4\x08b\xd95b\xf7\xcfI\xfc\x08k1\x8e\xc6\x98\xabY\x16fNRS-\x05<\xee\xe5\xc4\xe0\xad\x8aE\x03jL\xd5m~\x81\xfeqjw;0\xe5K\x889\xa9T\xa8\xc1/:\x96_\xee\x16\xe0\xca\xa6qm\xcb\xa5&\xd4\x94o\xa9\x94\xc6{sm\xc7\xf9\xff\xfe \xb3\xc0\x02\xc3\xe5O\xe8\xe7\x1d\xe0\xf4i\x07\xda\x97=\xfd\xc0\x0eW\xc0;\x8e(\x93\\G\x9bf\xd8\xcf0\x85')
k = pow(mm, e, n) * pow(c, -1, n) % n
cc = pow(c, e, n)
cc_inv = pow(cc, -1, n)
powers = [cc]
for i in tqdm(range(1, BITS)):
	powers.append(pow(powers[-1],2,n))
powers2 = [cc_inv]
for i in tqdm(range(1, BITS)):
	powers2.append(pow(powers2[-1],2,n))

targets = {}
for i in tqdm(range(BITS)):
	targets[k * powers[i] % n] = -2**i
for i in tqdm(range(BITS)):
	targets[k * powers2[i] % n] = 2**i

# we split this up into two loops since we know that there are two bits in either the left half or the right half, but we're not sure which
for i in tqdm(range(BITS//2)):
	p_i = powers[i]
	p_i2 = powers2[i]
	for j in range(i+1, BITS//2):
		p_j = powers[j]
		p_j2 = powers2[j]
		if (p_i * p_j % n) in targets: power = 2**i + 2**j + targets[p_i * p_j % n]
		elif (p_i * p_j2 % n) in targets: power = 2**i - 2**j + targets[p_i * p_j2 % n]
		elif (p_i2 * p_j % n) in targets: power = - 2**i + 2**j + targets[p_i2 * p_j % n]
		elif (p_i2 * p_j2 % n) in targets: power = - 2**i - 2**j + targets[p_i2 * p_j2 % n]
		else: continue
		print(long_to_bytes(mm * pow(c, -power, n) % n))

for i in tqdm(range(BITS//2+1,BITS)):
	p_i = powers[i]
	p_i2 = powers2[i]
	for j in range(i+1, BITS):
		p_j = powers[j]
		p_j2 = powers2[j]
		if (p_i * p_j % n) in targets: power = 2**i + 2**j + targets[p_i * p_j % n]
		elif (p_i * p_j2 % n) in targets: power = 2**i - 2**j + targets[p_i * p_j2 % n]
		elif (p_i2 * p_j % n) in targets: power = - 2**i + 2**j + targets[p_i2 * p_j % n]
		elif (p_i2 * p_j2 % n) in targets: power = - 2**i - 2**j + targets[p_i2 * p_j2 % n]
		else: continue
		print(long_to_bytes(mm * pow(c, -power, n) % n))

This took about 10 minutes to get the flag on my machine. Flag: `actf{the_earthquake_in_the_room}`

## RSA-AES
The server leaks whether the bit at position $2^{2048}$ (or some other position idk it's not really relevant) is set (identified by a change in length). The idea is to approximate (via binary search) some number $F$ such that the product of $F$ and the flag is as close to a target of $2^{2048}$ as possible. This gives some part of the flag. After this, you raise the target to $k\cdot n+2^{2048}$ for some large $k$ (in the script it increases exponentially) and find some new $F$ such that the product of the flag and $F$ is as close to the target as possible. Eventually the target gets long enough that you can get the entire flag through this process.

from Crypto.Util.number import bytes_to_long, long_to_bytes
from pwn import *
r = remote('challs.actf.co', 31500)
# this solve script was written before aplet123 massacred the challenge with a POW
n = 0xbb7bbd6bb62e0cbbc776f9ceb974eca6f3d30295d31caf456d9bec9b98822de3cb941d3a40a0fba531212f338e7677eb2e3ac05ff28629f248d0bc9f98950ce7e5e637c9764bb7f0b53c2532f3ce47ecbe1205172f8644f28f039cae6f127ccf1137ac88d77605782abe4560ae3473d9fb93886625a6caa7f3a5180836f460c98bbc60df911637fa3f52556fa12a376e3f5f87b5956b705e4e42a30ca38c79e7cd94c9b53a7b4344f2e9de06057da350f3cd9bd84f9af28e137e5190cbe90f046f74ce22f4cd747a1cc9812a1e057b97de39f664ab045700c40c9ce16cf1742d992c99e3537663ede6673f53fbb2f3c28679fb747ab9db9753e692ed353e3551
e = 0x10001

enc = int(r.readline(False))

def encrypt(fa):
	r.readuntil(b'Enter message to sign:')
	r.sendline(str(enc*pow(fa,e,n)%n).encode())
	r.readline()
	return len(eval(r.readline(False)))//16

NBITS = 2048

F = 1
while encrypt(F) * 128 <= NBITS:
	F *= 256
	print(F.bit_length()//8,end=' ',flush=True)
lb = F//256
ub = F

x = 1
boundary = 2**(NBITS-8)
while boundary//n * F < n:
	while ub-lb > 1:
		mid = (lb+ub)//2
		if encrypt(mid) * 128 <= NBITS:
			lb = mid
		else:
			ub = mid
		print(long_to_bytes(boundary//mid))
	
	newboundary = boundary + n*x
	ub = ub*newboundary//boundary+1
	lb = lb*newboundary//boundary-1
	boundary = newboundary
	x*=256

## Mask
The idea was to either use the [penalty scores](https://www.thonky.com/qr-code-tutorial/data-masking) used for computing the mask (specifically condition 3) to exfiltrate the flag, or to use the error correction bits to get the flag. With the amount of known data from the flag format and alphanumeric restriction, I was pretty sure this was solvable. Solve script is left as an exercise to the reader.