# RaRCTF 2021
## sRSA
```python
from Crypto.Util.number import *
p = getPrime(256)
q = getPrime(256)
n = p * q
e = 0x69420
flag = bytes_to_long(open("flag.txt", "rb").read())
print("n =",n)
print("e =", e)
print("ct =",(flag * e) % n)
```
注意到最後一行，它加密的方式乘以 $e$，並不是取 $pow(flag, e, n)$，所以直接乘以 $e^{-1}$ 即可。
```python
from output import *
from Crypto.Util.number import long_to_bytes
pt = ct * pow(e, -1, n) % n
flag = long_to_bytes(pt)
print(flag)
```
:::success
rarctf{ST3GL0LS_ju5t_k1dd1ng_th1s_w4s_n0t_st3g_L0L!_83b7e829d9}
:::
## minigen
```python
exec('def f(x):'+'yield((x:=-~x)*x+-~-x)%727;'*100)
g=f(id(f));print(*map(lambda c:ord(c)^next(g),list(open('f').read())))
```
雖然我們不知道 $id(f)$ 的值，但是 $f(x)$ 只會回傳 $727$ 以內的數值，因此只要枚舉所有可能的起始值，然後看還原的 $flag$ 是否含有 $rarctf$ 。
```python
for i in range(727):
g = f(i)
test = ""
try:
for j in range(len(output)):
test += chr(output[j] ^ next(g))
if "rar" in test:
print(test)
except:
continue
```
:::success
rarctf{pyg01f_1s_fun}
:::
## unrandompad
```python
from random import getrandbits
from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long
def keygen(): # normal rsa key generation
primes = []
e = 3
for _ in range(2):
while True:
p = getPrime(1024)
if (p - 1) % 3:
break
primes.append(p)
return e, primes[0] * primes[1]
def pad(m, n): # pkcs#1 v1.5
ms = long_to_bytes(m)
ns = long_to_bytes(n)
if len(ms) >= len(ns) - 11:
return -1
padlength = len(ns) - len(ms) - 3
ps = long_to_bytes(getrandbits(padlength * 8)).rjust(padlength, b"\x00")
return int.from_bytes(b"\x00\x02" + ps + b"\x00" + ms, "big")
def encrypt(m, e, n): # standard rsa
res = pad(m, n)
if res != -1:
print(f"c: {pow(m, e, n)}")
else:
print("error :(", "message too long")
menu = """
[1] enc()
[2] enc(flag)
[3] quit
"""[1:]
e, n = keygen()
print(f"e: {e}")
print(f"n: {n}")
while True:
try:
print(menu)
opt = input("opt: ")
if opt == "1":
encrypt(int(input("msg: ")), e, n)
elif opt == "2":
encrypt(bytes_to_long(open("/challenge/flag.txt", "rb").read()), e, n)
elif opt == "3":
print("bye")
exit(0)
else:
print("idk")
except Exception as e:
print("error :(", e)
```
不難發現這隻程式還是使用原始的 $m$ 去加密，再加上 public exponent 只有 $3$，那肯定是直接用 Hastad boardcast attack。
```python
flag_cube = crt([c1,c2,c3], [n1,n2,n3])
flag = flag_cube.nth_root(3)
from Crypto.Util.number import *
print(long_to_bytes(flag))
```
:::success
rarctf{https://cdn.discordapp.com/attachments/751845431063085160/866641917714235392/unknown.png_8538853c64}
:::
## babycrypt
```python
from Crypto.Util.number import getPrime, bytes_to_long
flag = bytes_to_long(open("/challenge/flag.txt", "rb").read())
def genkey():
e = 0x10001
p, q = getPrime(256), getPrime(256)
if p <= q:
p, q = q, p
n = p * q
pubkey = (e, n)
privkey = (p, q)
return pubkey, privkey
def encrypt(m, pubkey):
e, n = pubkey
c = pow(m, e, n)
return c
pubkey, privkey = genkey()
c = encrypt(flag, pubkey)
hint = pubkey[1] % (privkey[1] - 1)
print('pubkey:', pubkey)
print('hint:', hint)
print('c:', c)
```
我們先來看一下 hint，$$hint = n \pmod{q-1} = p \pmod{q-1}$$ 注意到 $genkey()$ 中有確保 $2q>p>q$，所以上式其實是 $p-(q-1)$。接著就是解一元二次方程式...
```python
from output import *
from decimal import *
### hint = p-(q-1)
diff = hint - 1
getcontext().prec = 1000
pq_sum = int(Decimal(diff ** 2 + 4 * n) ** (Decimal(1)/Decimal(2)))
p, q = (pq_sum + diff) // 2, (pq_sum - diff) // 2
assert p*q == n
pt = pow(c, pow(e, -1, (p-1)*(q-1)), n)
from Crypto.Util.number import long_to_bytes
flag = long_to_bytes(pt)
print(flag)
```
:::success
rarctf{g3n3r1c_m4th5_equ4t10n_th1ng_ch4ll3ng3_5a174f54e6}
:::
## Shamir's Stingy Sharing
```python
import random, sys
from Crypto.Util.number import long_to_bytes
def bxor(ba1,ba2):
return bytes([_a ^ _b for _a, _b in zip(ba1, ba2)])
BITS = 128
SHARES = 30
poly = [random.getrandbits(BITS) for _ in range(SHARES)]
flag = open("/challenge/flag.txt","rb").read()
random.seed(poly[0])
print(bxor(flag, long_to_bytes(random.getrandbits(len(flag)*8))).hex())
try:
x = int(input('Take a share... BUT ONLY ONE. '))
except:
print('Do you know what an integer is?')
sys.exit(1)
if abs(x) < 1:
print('No.')
else:
print(sum(map(lambda i: poly[i] * pow(x, i), range(len(poly)))))
```
我們的目標很明確，就是將透過一次詢問將 $poly[0]$ 給找出來，但是不可以直接取 $x=0$。這裡就要用到 $$P(x) \equiv poly[0] \pmod{x}$$ 當 $|x|>|poly[0]|$ 時，餘數就恰恰好是 $poly[0]$。
```python
import random
from Crypto.Util.number import long_to_bytes
x = 10889035741470030830827987437816582766592
def bxor(ba1,ba2):
return bytes([_a ^ _b for _a, _b in zip(ba1, ba2)])
enc_flag = bytes.fromhex("88e39f174c26080b373b9bc7ae7d8cad95d56a7475ec035442f0ec51696016")
a = 190534637132143375685957506679310680480863339405938582444449143962690405859986472143460034693369773025504626732911418966373114939017878294194553640632792917591210219147119959461183027499174184467045117639864214986271793981241500737756074184720483905141278453930914741353266433395425726425312520994331518638359405458542281881551701324480451365675465360290750303522693184805519163377448364461291988285127560844142909629092296463360184200228478431172050187457961296417093565813624582905576545060659982135127710432555195640298858960426436887536779848225975212943082796344524171290042714607028901773307317828897257565965508196026690579778055479348407289264307979835906872293456477803249926363388887589801349394462859660332793967892610193387774340142111732514239655989994304072228568306509018656495390081679320916480128706930568302005718655546817028961367313499638100665301474421779493876442295678063661088730186043737560634757185231611152176808509882704542114991507666095914567522012795497740657890285438897345292418346804580502848802809140739940672650603206760402834276433520993036614693214507001908851596185356443242027867671634685155397744771590345162441239198620184835568444616300859896343442483468582
poly0 = a % x
random.seed(poly0)
flag = bxor(enc_flag, long_to_bytes(random.getrandbits(len(enc_flag)*8)))
print(flag)
```
:::success
rarctf{n3v3r_trust_4n_1nt3g3r}
:::
## rotoRSA
```python
from sympy import poly, symbols
from collections import deque
import Crypto.Random.random as random
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
def build_poly(coeffs):
x = symbols('x')
return poly(sum(coeff * x ** i for i, coeff in enumerate(coeffs)))
def encrypt_msg(msg, poly, e, N):
return long_to_bytes(pow(poly(msg), e, N)).hex()
p = getPrime(256)
q = getPrime(256)
N = p * q
e = 11
flag = bytes_to_long(open("/challenge/flag.txt", "rb").read())
coeffs = deque([random.randint(0, 128) for _ in range(16)])
welcome_message = f"""
Welcome to RotorSA!
With our state of the art encryption system, you have two options:
1. Encrypt a message
2. Get the encrypted flag
The current public key is
n = {N}
e = {e}
"""
print(welcome_message)
while True:
padding = build_poly(coeffs)
choice = int(input('What is your choice? '))
if choice == 1:
message = int(input('What is your message? '), 16)
encrypted = encrypt_msg(message, padding, e, N)
print(f'The encrypted message is {encrypted}')
elif choice == 2:
encrypted_flag = encrypt_msg(flag, padding, e, N)
print(f'The encrypted flag is {encrypted_flag}')
coeffs.rotate(1)
```
不管三七二十一，我們先傳 $16$ 次 $0$ 把多項式的係數拿出來。但是在 $GF(p)$ 下求解多項式的根是很難的，參考 Frenklin related message attack，看以下兩個多項式的公因式：$$a_{15}x^{15}+a_{14}x^{14}+\cdots+a_1x+a_0 - C_{1}$$ 和 $$a_{14}x^{15}+a_{13}x^{14}+\cdots+a_0x+a_{15} - C_{2}$$ 它有高機率是 $x-m$。
```python
from collections import deque
weight = deque([2 ** i for i in range(16)])
A = Matrix(ZZ, 16, 16)
for i in range(16):
for j in range(16):
A[i, j] = weight[j]
weight.rotate(15)
Y = vector([4978732,
3141824,
5169553,
5423981,
6129442,
4918964,
3612103,
2767826,
4224952,
5959574,
4448158,
3981191,
5734192,
6225584,
4652503,
5503976])
coef = A\Y
print(coef)
N = 7661390097649734971645170813670315640515367193176661723124492523771787060503737006824444244709748736037802701619994549056559846309506086614565557453133947
e = 11
enc_flags = [6391979643894258282207873662949703091852978151728933548794699743197774742341510199981080536714753760857390702790824914789875604581308419193796521148656341,
2719916709375804370737303381943697780007800261847823047269370734500397621436239194565538325800843288778974187794784857624279205096393510810624369587402213,
5891393159782000403710586923779949556733942113908057101500722744110330393067648912056279355064792741092819457229606542426336472104307098678479775126566512,
1089791603259975036616907669338490891370492565083613602678894020054081728713700968306345420684642209456219024639181124438391555765460813662182355455768002,
7382618063883456361096298367293576656463193178887809700357322971305678170935768941963148819310675853679763627308918129298402959020288518329382446263764355]
ZmodN = Zmod(N)
R.<x> = ZmodN[]
f, g = 0, 0
for i in range(16):
f += Zmod(N)(coef[i]) * x^i
g += Zmod(N)(coef[(i-1) % 16]) * x^i
f, g = f^e-enc_flags[0], g^e-enc_flags[1]
def polyGCD(a, b):
if b == 0:
return a.monic()
else:
return polyGCD(b, a%b)
_ = N - (polyGCD(f, g).coefficients()[0])
print(_)
```
:::success
rarctf{sp1n_spin_sp33n_sp00n_sp1n-b8765b7c3b}
:::
## PsychECC
```python
from collections import namedtuple
import random
def moddiv(x,y,p):
return (x * pow(y, -1, p)) %p
Point = namedtuple("Point","x y")
class EllipticCurve:
INF = Point(0,0)
def __init__(self, a, b, p):
self.a = a
self.b = b
self.p = p
def add(self,P,Q):
if P == self.INF:
return Q
elif Q == self.INF:
return P
if P.x == Q.x and P.y == (-Q.y % self.p):
return self.INF
if P != Q:
Lambda = moddiv(Q.y - P.y, Q.x - P.x, self.p)
else:
Lambda = moddiv(3 * P.x**2 + self.a,2 * P.y , self.p)
Rx = (Lambda**2 - P.x - Q.x) % self.p
Ry = (Lambda * (P.x - Rx) - P.y) % self.p
return Point(Rx,Ry)
def multiply(self,P,n):
n %= self.p
if n != abs(n):
ans = self.multiply(P,abs(n))
return Point(ans.x, -ans.y % p)
R = self.INF
while n > 0:
if n % 2 == 1:
R = self.add(R,P)
P = self.add(P,P)
n = n // 2
return R
# P256 parameters, secure.
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
order = 115792089210356248762697446949407573529996955224135760342422259061068512044369
a = -3
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291
E = EllipticCurve(a,b,p)
print("""Welcome to my prediction centre!
We're always looking out for psychics!
We're gonna choose a random number. You get to choose a point. We'll multiply that point by our random number.
Since this curve is of perfect and prime order, it'll be impossible to break this test.
Only a psychic could know!
Be psychic, get the flag.""")
x = int(input("Enter point x: "))
y = int(input("Enter point y: "))
P = Point(x,y)
n = random.randint(1,order)
Q = E.multiply(P,n)
print("Ok, where do you think the point will go?")
px = int(input("Enter point x: "))
py = int(input("Enter point y: "))
prediction = Point(px,py)
if prediction == E.INF or prediction == P:
print("Psychics don't use dirty tricks.")
quit()
if prediction == Q:
print("Wow! You're truly psychic!")
print(open("/challenge/flag.txt").read())
quit()
print("Better luck next time.")
print(f"Point was {Q}")
```
題目要求我們猜中 $nP$ 的座標，其中 $n$ 是一個隨機的數字。直覺的想法是想要找 $P$ 使得 $ord(P)$ 很小，那麼只要多猜幾次就會中了！然而 P256 Curve 的 order 是個大質數，所以不存在這樣的 $P$，還好上禮拜解 Crypto CTF 的時候，不小心瞄到 Invalid curve attack，因此目標變成找一個不在 P256 Curve 上的 P，滿足它的 $ord(P)$ 很小。
:::success
rarctf{w0ah_str4ight_cl41r0v0y4nc3!!_8119733d69}
:::
## snore
```python
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from hashlib import sha224
from random import randrange
import os
p = 148982911401264734500617017580518449923542719532318121475997727602675813514863
g = 2
assert isPrime(p//2) # safe prime
x = randrange(p)
y = pow(g, x, p)
def verify(s, e, msg):
r_v = (pow(g, s, p) * pow(y, e, p)) % p
return bytes_to_long(sha224(long_to_bytes(r_v) + msg).digest()) == e
def sign(msg, k):
r = pow(g, k, p)
e = bytes_to_long(sha224(long_to_bytes(r) + msg).digest()) % p
s = (k - (x * e)) % (p - 1)
return (s, e)
def xor(ba1,ba2):
return bytes([_a ^ _b for _a, _b in zip(ba1, ba2)])
otp = os.urandom(32)
messages = [
b"Never gonna give you up",
b"Never gonna let you down",
b"Never gonna run around and desert you",
b"Never gonna make you cry",
b"Never gonna say goodbye",
b"Never gonna tell a lie and hurt you"
]
print("p = ", p)
print("g = ", g)
print("y = ", y)
for message in messages:
k = bytes_to_long(xor(pad(message, 32)[::-1], otp)) # OTP secure
s, e = sign(message, k % p)
assert (verify(s, e, message))
print(message, sign(message, k % p))
flag = open("flag.txt","rb").read()
key = sha224(long_to_bytes(x)).digest()[:16]
iv = os.urandom(16)
cipher = AES.new(key, AES.MODE_CBC, iv)
ct = cipher.encrypt(pad(flag, 16)).hex()
print("ct = ", ct)
print("iv = ", iv.hex())
```
本來想說直接在 $GF(p)$ 上解 discrete log，可是 $p$ 不夠 smooth，所以只好從前面六個 Schnorr signatures 試著去將 $x$ 求出。查了不少的 google，感覺就是把它當成 Hidden number problem(HNP) 去解，
一般來說，HNP是有好幾個型如 $$\alpha_i x \equiv b_i+c_i \pmod{p_i}$$ 未知的東西是 $x, c_i$，其中 $c_i$ 相對於 $p_i$ 是小的。在這題，我們未知的 $k$ 是 message 跟一個固定的 random bytes 去做 XOR，所以高機率不會比 $q$ 明顯小。這邊用到的是 $$(e_i-e_j)x \equiv (k_i-k_j)+(s_i-s_j) \pmod{q}$$ 然後確保 $k_i-k_j$ 很小。這裡不難發現有兩組 message 的長度和前綴一樣，所以做完 XOR 後，對應的 $k$ 只有中間的 88bits 不一樣。如此拿去直接跑 HNP 沒結果，因此乘以 $pow(2, -96, q)$ 讓 $k_i-k_j$ 中間的 bits 跑去後面。這樣跑 HNP 就會有答案~
```python
p = 148982911401264734500617017580518449923542719532318121475997727602675813514863
q = (p-1) // 2
g = 2
y = 99943368625476277151400768907519717344447758596311103260066302523387843692499
s = [82164720827627951718117576622367372918842412631288684063666489980382312886875,
121728190859093179709167853051428045020048650314914045286511335302789797110644,
146082371876690961814167471199278995325899717136850705507399907858041424152875,
70503066417308377066271947367911829721247208157460892633371511382189117698027,
129356717302185231616252962266443899346987025366769583013987552032290057284641,
12183293984655719933097345580162258768878646698567137931824149359927592074910]
e = [20555462814568596793812771425415543791560033744700837082533238767135,
18832686601255134631820635660734300367214611070497673143677605724980,
17280327447912166881602972638784747375738574870164428834607749483679,
18679076989831101699209257375687089051054511859966345809079812661627,
2084781842220461075274126508657531826108703724816608320266110772897,
15768525934046641405375930988120401106067516205761039338919748323087]
def solve_HNP(a, b, k):
# http://www.isg.rhul.ac.uk/~sdg/igor-slides.pdf
N = len(a)
M = Matrix(RationalField(), N+1, N+1)
for i in range(N):
M[i, i] = q
M[N, i] = b[i]
M[N, N] = 1 / (2 ** (k + 1))
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
closest = babai(M, vector(RationalField(), a + [0]))
return (closest[-1] * (2 ** (k + 1))) % p
s_bar = [((s[4]-s[0]) * pow(2, -96, q)) % q,
((s[3]-s[1]) * pow(2, -96, q)) % q]
e_bar = [((e[0]-e[4]) * pow(2, -96, q)) % q,
((e[1]-e[3]) * pow(2, -96, q)) % q]
for i in range(250):
x = solve_HNP(s_bar, e_bar, i)
if pow(g, x, p) == y:
print(x)
break
```
:::success
rarctf{zZZzZZZZzzZZZzzZZZZZZzZzzzZzzZZzZzzZZzzzZZZZzZZz_s0rry_1_w4s_t00_t1r3d_t0_c0me-up_w1th_4n_4ctual-fl4g_7686f36b65}
:::
Sign in with Wallet
Connect another wallet