 매우 늦게 올린다. 결과는 6등으로, 예상보다는 매우 높았으나 여전히 만족스러운 결과는 아니었다. J를 풀지 못한것이 아쉬움.

작년의 팀과 멤버는 동일하다. rkm0959, junie, bjwj5505다. 내가 1년간 공부를 많이 한 건 맞지만, 정작 최근에는 CTF 참가 등으로 PS, CP에 집중하지 못해서 팀의 전체적인 실력이 강화된건지 퇴화된건지 좀 애매한 것 같다. 다른 팀원도 비슷하다. 일단 지금까지는 나쁘지 않게 하고 있는듯.

타임라인과 함께 간략한 설명을 붙이도록 하겠다. 모든 사람을 3인칭으로 명명하겠다.

• 시작하자마자 문제 12개 모두 출력
• 스코어보드 보니까 I가 0분컷으로 풀렸네? 진짜 쉽네?
• rkm0959가 바로 컴퓨터 잡고 AC (5분)
• 이때쯤 E도 퍼솔이 나왔고, 바로 rkm0959가 이어서 AC (8분)
• bjwj5505는 이때 L을 읽고 있었고, junie는 앞쪽 문제를 읽는 중.
• bjwj5505가 L을 구현했지만 WA 후 코드 프린트
• rkm0959는 G를 보면서 수학 문제라고 생각을 했으나 매우 어려워보여서 대기중
• 대신 K가 쉽다는 것을 확인하고, 풀이를 bjwj5505와 확인
• rkm0959가 H의 풀이를 찾고, 정당성을 bjwj5505와 확인
• 그러다가 F가 쉬워보여서 rkm0959, junie가 해결 시도
• bjwj5505가 L을 디버깅하고 있으며, rkm0959가 K를 짜기 시작
• bjwj5505가 L을 고치고 AC (39분), rkm0959도 곧 K AC (46분)
• bjwj5505, junie가 F의 풀이를 찾는동안 rkm0959 H 구현
• F의 풀이를 찾고 AC (51분), H도 곧 AC (58분) - 1시간 6솔브 도달
• 정확하게 기억은 안나지만 junie가 느린 J 풀이를 찾았음 (로그 2개)
• 그러나 정확하게 풀이를 이해하고 있는 사람은 junie 혼자
• bjwj5505, junie는 A의 해결에 집중. rkm0959는 B가 DP임을 확인
• rkm0959가 D가 세그먼트 트리로 해결될 수 있는 문제임을 확인
• A, B, D의 동시다발적 구현 + WA + 디버깅 파티 후 전부 AC (115, 133, 149분)
• J를 고치려고 했고, "맞는" 풀이를 1분 전에 찾았으나 TLE. 똑떨....

#### 'PS > 대회 후기' 카테고리의 다른 글

 ACM-ICPC Seoul Regional Preliminary 2020  (0) 2020.10.19 2020.09.05 2020.08.22 2020.08.22 2019.11.11 2018.12.22

I participated in N1CTF as a member of Super Guesser.

We solved all crypto problems, and it was a great collaboration of me and rbtree.

The explanation will be very brief, because I don't have a lot of free time on my hands :( :(

VSS

 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869 #!/usr/bin/python3import qrcode  # https://github.com/lincolnloop/python-qrcodeimport randomimport osfrom PIL import Imagefrom flag import FLAG  def vss22_gen(img):    m, n = img.size    share1, share2 = Image.new("L", (2*m, 2*n)), Image.new("L", (2*m, 2*n))    image_data = img.getdata()    flipped_coins = [int(bit) for bit in bin(random.getrandbits(m*n))[2:].zfill(m*n)]    for idx, pixel in enumerate(image_data):        i, j = idx//n, idx % n        color0 = 0 if flipped_coins[idx] else 255        color1 = 255 if flipped_coins[idx] else 0        if pixel:            share1.putpixel((2*j, 2*i), color0)            share1.putpixel((2*j, 2*i+1), color0)            share1.putpixel((2*j+1, 2*i), color1)            share1.putpixel((2*j+1, 2*i+1), color1)             share2.putpixel((2*j, 2*i), color0)            share2.putpixel((2*j, 2*i+1), color0)            share2.putpixel((2*j+1, 2*i), color1)            share2.putpixel((2*j+1, 2*i+1), color1)        else:            share1.putpixel((2*j, 2*i), color0)            share1.putpixel((2*j, 2*i+1), color0)            share1.putpixel((2*j+1, 2*i), color1)            share1.putpixel((2*j+1, 2*i+1), color1)             share2.putpixel((2*j, 2*i), color1)            share2.putpixel((2*j, 2*i+1), color1)            share2.putpixel((2*j+1, 2*i), color0)            share2.putpixel((2*j+1, 2*i+1), color0)    share1.save('share1.png')    share2.save('share2.png')  def vss22_superposition():    share1 = Image.open('share1.png')    share2 = Image.open('share2.png')    res = Image.new("L", share1.size, 255)    share1_data = share1.getdata()    share2_data = share2.getdata()    res.putdata([p1 & p2 for p1, p2 in zip(share1_data, share2_data)])    res.save('result.png')  def main():    qr = qrcode.QRCode(        version=1,        error_correction=qrcode.constants.ERROR_CORRECT_L,        box_size=12,        border=4,    )    qr.add_data(FLAG)    qr.make(fit=True)    img = qr.make_image(fill_color="black", back_color="white")    vss22_gen(img._img)    img.save('res.png')    vss22_superposition()  if __name__ == '__main__':    main() Colored by Color Scripter cs

The vulnerability lies in the use of "getrandbits" - it's implemented using MT19937. This PRNG is known to be predictable after 624 output values are known. Also, if you try to generate a QR code with a sample flag, we can see that the first few rows of the generated output are all white. With this fact, we can retrieve the first few thousand bits generated, and we can predict the following bits generated by MT19937. Therefore, we can recover the original QR code. This solution (and code itself) is due to rbtree.

 123456789101112131415161718192021222324252627282930313233343536373839 from mt import untemperimport randomfrom PIL import Image img = Image.open('share2.png')value = 0for i in range(444):    for j in range(444):        value <<= 1        value ^= 1 if 255 == img.getpixel((2 * j + 1, 2 * i)) else 0 tmp = valuevalues = []for i in range(444 * 444 // 32):    values.append(tmp & 0xffffffff)    tmp >>= 32 mt_state = tuple(list(map(untemper, values[:624])) + )random.setstate((3, mt_state, None)) # for i in range(444 * 444 // 32):#     assert values[i] == random.getrandbits(32) random.setstate((3, mt_state, None)) real_value = 0for i in range(444 * 444 // 32):    real_value ^= random.getrandbits(32) << (32 * i) value ^= real_valuearr = [int(bit) for bit in bin(value)[2:].zfill(444 * 444)] res = Image.new("L", (444, 444)) for i in range(444):    for j in range(444):        res.putpixel((j, i), 0 if arr[i * 444 + j] else 255)    res.save("res.png")Colored by Color Scripter cs

FlagBot

This problem was solved by me, so I can give you a brief look inside my brain.

• You can't really do anything with AES-CBC in this challenge
• You can't really do anything with SHA256 anywhere
• That means that we have to break the DH style shared secret generation
• The secret key is reused every time, so that's the vulnerability
• The curve generation only checks the existence of large primes, so small primes can exist

At this point, the solution was straightforward. For each small prime $p$ that divides the order of the elliptic curve used, we can find the value of the secret key $\pmod{p}$ by using Pohlig-Hellman approach. Combining these with CRT, we can recover $d$ since it is at most $2^{255}$.

Since we do need to deal with primes of size around $10^{12}$, Baby-Step-Giant-Step is required. Just use Sage.

The below code finds all the shared secrets. The remaining parts of the problem are straightforward.

 12345678910111213141516171819202122232425262728293031 cur_mod = 1cur_val = 0 for i in range(0, 7):    a = S[i]    b = S[i]    p = S[i]    E = EllipticCurve(GF(p), [a, b])    Ord = E.order()    L = list(factor(Ord))    GG = E(g[i])    SS = E(S_pub[i])    for pp, dd in L:        if pp <= 10 ** 12 and dd == 1:            Gp = (Ord // pp) * GG            Sp = (Ord // pp) * SS            tt = discrete_log(Sp, Gp, operation='+')            cur_val = crt(cur_val, tt, cur_mod, pp)            cur_mod = (cur_mod * pp) // gcd(pp, cur_mod)    print("Done ", i)    print("[+] Secret: ", cur_val) for i in range(0, 7):    a = S[i]    b = S[i]    p = S[i]    E = EllipticCurve(GF(p), [a, b])    RR = E(R_pub[i])    RES = RR * cur_val    print(RES.xy())Colored by Color Scripter cs

curve

 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778 #!/usr/bin/env sage import signal, hashlib, string, random, os  os.chdir(os.path.dirname(os.path.abspath(__file__)))FLAG = open("./flag.txt", 'r').read()ROUNDS = 30 def PoW():  s = ''.join([random.choice(string.ascii_letters + string.digits) for _ in range(20)])  h = hashlib.sha256(s.encode()).hexdigest()  prefix = s[:16]  print("sha256(%s+XXXX) == %s" % (prefix, h))  c = input("Give me XXXX: ")  if hashlib.sha256((prefix + c).encode()).hexdigest() == h:    return True   return False def chall():  p = ZZ(input("P: "))  # of course we are using sage >= 9  a = ZZ(input("A: "))  b = ZZ(input("B: "))   if not is_prime(p) or p.nbits() < 512:    print("No bad parameters.")    return   E = EllipticCurve(GF(p), [a, b])  if E.is_supersingular():    print("No this is not good enough.")    return   q = E.order()  x1 = ZZ(input("X1: "))  y1 = ZZ(input("Y1: "))  x2 = ZZ(input("X2: "))  y2 = ZZ(input("Y2: "))  G1 = E((x1, y1))  G2 = E((x2, y2))   for _ in range(ROUNDS):    a0 = randint(1, q - 1)    a1 = randint(1, q - 1)     c = -1    while c == -1 or c == a0 * a1:      c = randint(1, q - 1)     g0, g1 = G1 * a0, G2 * a1     c0, c1 = G1 * (a0 * a1), G1 * c    b = randint(0, 1)     if b == 0:      print(g0, g1, c0)    else:      print(g0, g1, c1)     choice = ZZ(input("Choice: "))    if choice != b:      print("Wrong choice.")      return   print(f"Thank you! Here's your reward: {FLAG}")  return  if __name__ == '__main__':  if not PoW():    print("Invalid PoW.")    exit()  signal.alarm(90)   try:    chall()  except:    print("oof...")    exit()  Colored by Color Scripter cs

We struggled greatly on this challenge, despite finding the solution quite immediately. Here's the process.

• $E$ is a large elliptic curve over a prime field, not supersingular
• We select two points $G_1, G_2$ on the curve, and play a sort of Decisional Diffie-Hellman game.
• Let's just fix $G = G_1 = G_2$ and see what we can do!
• If the order of $G$ is small, say $t$ - we can recover $a_0, a_1 \pmod{t}$ easily.
• Therefore, we can directly calculate $a_0a_1G$ as well!
• Check if this is equal to the third point given. If so, check $b=0$ and otherwise check $b=1$.
Now we do some analysis.
• If $b=0$ was chosen, this will give the correct answer with probability 1
• If $b=1$ was chosen, we fail if $c \equiv a_0 a_1 \pmod{t}$, so we succeed with probability $1-1/t$
• We do $30$ rounds, so $t$ shouldn't be too small (we want, say, $t> 50$)
• Obviously we do need to solve the discrete logarithm on a group of order $t$, so we want small $t$

This leads to the following goal.

• Find an elliptic curve that satisfies the server's desired conditions, with the order of the curve having a prime between $50$ and $400$

I think I took about 5 minutes until here, but the journey towards the flag for several reasons.

• First, my initial code used random $p, a, b$, generate the curve, find the order, then check for small primes.
• Seems good right? However, I tried to find $G$ using E.gens() * (Order // small_prime)
• This obviously takes infinite time, and my computer was on the verge of dying because of it
• I realized the problem and replaced it by generating any point with Tonelli-Shanks and multiplying it by Order // small_prime

So I thought I was done here. After sending the parameters, I realized that I was not done here. Why?

• The server calculates the order of the elliptic curve as well
• While order calculation is done in polynomial time, it's still slow with 512 bit curve parameters
• Therefore, the server times out, and I can't solve the problem

So I thought I was done here, in a different meaning. After solving the remaining challs, I tried the following.

• Simply try the curves of the form $y^2 = x^3 + b$.

This worked, as the order calculation was done much faster. The challenge was solved.

The parameter finding and solution finding was done by me, and the programming was done by rbtree.

I learned a lot from solving this problem :) I'm still inexperienced, lots of studying to do...

 123456789101112131415161718192021222324252627282930313233 pr = []for x in range(50, 200):    if x in Primes():        pr.append(x)while True:    p = random_prime(2 ** 512, False, 2 ** 511)    if p % 3 == 2: ## in this case, y^2 = x^3 + b is guaranteed to be supersingular        continue    d = randint(1, p-1)    E = EllipticCurve(GF(p), [0, d])    if E.is_supersingular() == True:        continue    print(p)    L = E.order()    for cc in pr:        if L % cc == 0:            print(p, d, cc, L)            break ## find any point on the elliptic curvefor u in range(1, 100):    goal = (u ** 3 + a * u + b) % p    if pow(goal, (p-1) // 2, p) == 1:        v = tonelli(goal, p) ## sqrt, so you can directly use sage        G = E(u, v)        break ## hope that G is nonzeroG = G * (Ord // pr)G1 = GG2 = G ## this ends parameter generationColored by Color Scripter cs

 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566 ## by rbtree from pwn import *import stringimport itertools conn = remote('47.242.140.57', 9998)conn.settimeout(None) # PoW challenge = conn.recvline().strip()print(challenge)prefix = challenge[7:7+16]h = challenge.split()[-1]charset = (string.ascii_letters + string.digits).encode()for suffix in itertools.product(charset, repeat=4):    if hashlib.sha256(prefix+bytes(suffix)).hexdigest() == h.decode():        conn.sendlineafter(b'Give me XXXX: ', bytes(suffix))        breakprint("PoW Done") p = 11572562087281212077294341316763410822093276559896892655806738743748493229131824454041157658617469079306138012813995393545636120267619633658087398895787057 a = 0b = 587626359248673832094266933340735482471140319598254235432650868938827936103013631493279303809976008538035914917596142929543705518144408460458007005924570pr = 97order = 11572562087281212077294341316763410822093276559896892655806738743748493229131918957581964494921602014693617723606720177358361724985583223555103419211299648 Gs = [] ## bunch of points (G, 2G, ... 97G)print(len(Gs)) def get_points():    points_s = conn.recvline().decode().strip()[1:-1].split(') (')    points = []    for point_s in points_s:        point = tuple(int(v.strip()) for v in point_s.split(':')[:2])        points.append(point)    return points conn.sendlineafter(b'P: ', str(p))conn.sendlineafter(b'A: ', str(a))conn.sendlineafter(b'B: ', str(b))conn.sendlineafter(b'X1: ', str(Gs))conn.sendlineafter(b'Y1: ', str(Gs))conn.sendlineafter(b'X2: ', str(Gs))conn.sendlineafter(b'Y2: ', str(Gs)) print("Parameter Sent") for _ in range(30):    points = get_points()     for i in range(96):        if points == Gs[i]:            a = i + 1            break     for i in range(96):        if points == Gs[i]:            b = i + 1            break     to_send = 0 if Gs[(a * b % 97) - 1] == points else 1    conn.sendlineafter(b'Choice: ', str(to_send)) conn.interactive()Colored by Color Scripter cs

BabyProof

 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748 from hashlib import sha256 from Crypto.Util.number import getRandomRangefrom Crypto.PublicKey import DSA from secret import proof_of_work, flag  x = int.from_bytes(flag, 'big')assert x.bit_length() == 247  def baby_proof():    key = DSA.generate(3072)  # It takes time to generate, plz be patient...    p, q, g = key.domain()    y = pow(g, x, p)     v = getRandomRange(1, x)    t = pow(g, v, p)     gyt = b"".join(        map(            lambda x: int.to_bytes(len(str(x)), 4, 'big') + str(x).encode(),            (g, y, t)        ))    c = int.from_bytes(sha256(gyt).digest(), 'big')    r = (v - c*x) % q     print("I want to prove to you that I am in the knowledge of the discrete "          "logarithm x that satisfies g^x = y modulo p, with the order of g "          "modulo p being q.")    print("However, I don't want to leak any information about x.")    print("So, I use a non-interactive zero-knowledge proof for my purpose.")    print("=================================================================")    print("Here is my proof: ")    print("Firstly, I choose a random (secret) v and compute t = g^v in Zq.")    print("Secondly, I compute c = SHA256(g, y, t).")    print("Then, I compute r = v - cx modulo q.")    print("Finally, I will send you my proof (t, r).")    print("You can check it by determining whether t == g^r * y^c or not.")    print("Since there's negligible probability that I could forge the value "          "r, you should believe that I really have knowledge of x.")    print(g, y, p, q, t, r, sep="\n")  if __name__ == "__main__":    if proof_of_work():        baby_proof()Colored by Color Scripter cs

The key here is that $x$ is quite small compared to $2^{256}$, and $v$ is selected in $[1, x]$.

Given the printed parameters, we can directly obtain the value of $c$ as well. We see that $$cx \equiv v - r \pmod{q}, \quad 1 \le v \le x$$ Since $x$'s bit length is $247$, we get $1 \le v \le 2^{247}$ and can write something like $$cx \pmod{q} \approx -r + 2^{246} \pmod{q}$$ This is an instance of Hidden Number Problem, so just gather a lot of these information and solve it.

 123456789101112131415161718192021 d = 60 ## get 60 instancesM = Matrix(ZZ, d+1, d+1)for i in range(0, d):    M[0, i] = cs[i]M[0, d] = 1for i in range(0, d):    M[i+1, i] = qs[i] Target =  * (d+1)for i in range(0, d):    Target[i] = (2 ** 246) - rs[i]Target[d] = (2 ** 246) M = M.LLL()GG = M.gram_schmidt()Target = vector(Target)TT = Babai_closest_vector(M, GG, Target) x = TT[d]print(x)print(bytes.fromhex(hex(x)[2:])) cs

easyRSA?

 12345678910111213141516171819202122232425262728293031323334353637 from Crypto.Util.number import *import numpy as np mark = 3**66 def get_random_prime():    total = 0    for i in range(5):        total += mark**i * getRandomNBitInteger(32)    fac = str(factor(total)).split(" * ")    return int(fac[-1]) def get_B(size):    x = np.random.normal(0, 16, size)    return np.rint(x) p = get_random_prime()q = get_random_prime()N = p * qe = 127 flag = b"N1CTF{************************************}"secret = np.array(list(flag)) upper = 152989197224467A = np.random.randint(281474976710655, size=(e, 43))B = get_B(size=e).astype(np.int64)linear = (A.dot(secret) + B) % upper result = []for l in linear:    result.append(pow(l, e, N)) print(result)print(N)np.save("A.npy", A) Colored by Color Scripter cs

Looking at the problem, we see that we need to do the following

• Factorize $N$ using the vulnerable random prime generator, and recover the array "linear"
• Solve the instance of LWE by using the fact that secret vector (the flag) is small as well

We first focus on the first part. I actually thought about coppersmith method, but I couldn't get it to work.

I already have an experience in wasting time with coppersmith approach, (sharsable) so I stopped attempting.

rbtree noted that there is a polynomial $f$ with small coefficients, degree 8, and $f(3^{66}) \equiv 0 \pmod{N}$.

This is because for each $p, q$, there's a degree 4 polynomial with small coefficients that vanishes at $3^{66}$ modulo that prime.

If we multiply the two degree 4 polynomials, we arrive at the described polynomial of degree 8.

He then suggested using a lattice to find this polynomial. This was an excellent idea!

Since we want a small-coefficient-linear-combination of $3^{66 \cdot 0}, 3^{66 \cdot 1}, \cdots , 3^{66 \cdot 8}$ that vanishes to zero, we must use scaling, as I did in sharsable. Check the code for technical details. As I do usually, I used Babai's closest vector algorithm. We can expect $f$ to be factorized into two polynomials of degree 4. By calculating each polynomial at $3^{66}$ and taking GCDs, we can retrieve $p, q$. This completes Part 1.

For Part 2, we need to solve the LWE problem. This is hard in general, but we know that the secret vector is small as well.

Of course, LWE problem can be modeled as CVP problem, and we use the "secret vector is small" fact here as well.

 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990 ## Step 1 : Factorization of Nrat = 2 ** 1000 ## scaling : super large to force zero in the first column for i in range(0, 9):    M[i, 0] = (3 ** (66 * i)) * ratM[9, 0] = n * ratfor i in range(0, 9):    M[i, i+1] = 1 Target =  * 10for i in range(1, 10):    Target[i] = (2 ** 64) M = M.LLL()GG = M.gram_schmidt()Target = vector(Target)TT = Babai_closest_vector(M, GG, Target) P. = PolynomialRing(ZZ)f = 0for i in range(1, 10):    f = f + TT[i] * x^(i-1)print(f.factor())## (2187594805*x^4 + 2330453070*x^3 + 2454571743*x^2 + 2172951063*x + 3997404950) ## (3053645990*x^4 + 3025986779*x^3 + 2956649421*x^2 + 3181401791*x + 4085160459) cc = 0cc += 2187594805 * (3 ** (66 * 4))cc += 2330453070 * (3 ** (66 * 3))cc += 2454571743 * (3 ** (66 * 2))cc += 2172951063 * (3 ** (66 * 1))cc += 3997404950 * (3 ** (66 * 0)) p = gcd(cc, n)print(p)print(n // p)print(n % p) ## Step 2 : housekeeping stuff## res in res.txt, A in A.npyp = 122286683590821384708927559261006610931573935494533014267913695701452160518376584698853935842772049170451497q = 268599801432887942388349567231788231269064717981088022136662922349190872076740737541006100017108181256486533e = 127n = p * qphi = (p-1) * (q-1)d = inverse(e, phi) cv = []for x in res:    cv.append(pow(x, d, n)) print(cv) np.set_printoptions(threshold=sys.maxsize)A = np.load("A.npy")A = np.ndarray.tolist(A)print(A) ## Step 3 : LWE with CVPmod = 152989197224467 sel = 15 ## sel can be large as 127, but that's too slowM = Matrix(ZZ, sel + 43, sel + 43)for i in range(0, 43):    for j in range(0, sel):        M[i, j] = A[j][i]    M[i, sel + i] = 1for i in range(43, 43+sel):    M[i, i-43] = modTarget =  * (sel + 43)for i in range(0, sel):    Target[i] = cv[i] - 8for i in range(sel, sel + 43):    Target[i] = 80 ## printable Target = vector(Target)M = M.LLL()GG = M.gram_schmidt()Target = vector(Target)TT = Babai_closest_vector(M, GG, Target) print(TT) res = ""for i in range(sel, sel+43):    res += chr(TT[i]) print(res) Colored by Color Scripter cs

#### '수학 > 암호론 및 CTF' 카테고리의 다른 글

 N1CTF 2020 Crypto Write-Ups  (0) 2020.10.18 2020.10.18 2020.10.11 2020.09.30 2020.09.20 2020.09.19 main.pdf

#### '수학 > 암호론 및 CTF' 카테고리의 다른 글

 N1CTF 2020 Crypto Write-Ups  (0) 2020.10.18 2020.10.18 2020.10.11 2020.09.30 2020.09.20 2020.09.19

I participated in SECCON 2020 Online CTF as a member of HangulSarang. We got 1st place :)

Hangul Day is also my birthday, so that's something I guess :D

The competition collided with ACM-ICPC quals, so I had to start solving at like 7PM. (4 hours late)

During that 4 hours, my teammate solved "This is RSA", which is solved using that each byte can be only 0x30 to 0x39. After that, we can compute solutions in $\pmod{2^k}$ and move upwards using recursion. It was the easiest crypto problem in this CTF, (and the solver wasn't me) so I think I don't need to explain further. The other four crypto problems were quite good, challenging, and very enjoyable, so I will describe my thought process as well. Huge thanks to the problem authors for creating these challenges. :D

koharu

 123456789101112131415161718192021222324252627282930313233343536373839404142434445 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. = 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*Qc = []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)  Colored by Color Scripter cs

The code screams "quadratic residue", and it's similar to bitcrypto in InterKosenCTF. (write-up in this blog)

The only difference is that we are not using large primes, but polynomials in $GF(p)[x]$. This is already weak.

The reason is that we can easily factorize polynomials in $GF(p)$. We can ask Sage to do it for us :)

Now we can determine whether a given polynomial is a quadratic residue or not. Combine this to get the flag.

 1234567891011121314151617 p = 4832823609987476353F. = PolynomialRing(GF(p))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 + 3478109193918270445R = 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 + 2337193413394346074c = []P = (x^64 + 2705838326093066801*x^63 + 1861763125820805142*x^62 + 1919270169024731361*x^61 + 728192979251886197*x^60 + 3703504742135431297*x^59 + 608310330267197202*x^58 + 677522369546315305*x^57 + 45111914222503868*x^56 + 3231090245423531905*x^55 + 4439626063971680541*x^54 + 264779255326565930*x^53 + 943573327092647824*x^52 + 3642035360519473519*x^51 + 4624797912514728904*x^50 + 815168423497123035*x^49 + 2058290770523809000*x^48 + 4368972367338353614*x^47 + 1102710837251449034*x^46 + 1838631000574578462*x^45 + 1550208773716319692*x^44 + 4479635398032603580*x^43 + 2547505501081696879*x^42 + 4733577241261296757*x^41 + 1459044726889718801*x^40 + 4736670792998507780*x^39 + 3481084975759672453*x^38 + 4491590348438475003*x^37 + 4286960290474469508*x^36 + 2519824328645383346*x^35 + 722570560813334776*x^34 + 3203376079187925593*x^33 + 2137713042365333594*x^32 + 2529680584881125743*x^31 + 881878615185959251*x^30 + 2648895700342509353*x^29 + 3093613170934869890*x^28 + 1839149659686122740*x^27 + 901352037355979824*x^26 + 3079388294575162468*x^25 + 4316897640303347156*x^24 + 3768144827267250554*x^23 + 1585476600468626452*x^22 + 2408180731465025131*x^21 + 2754322334879778466*x^20 + 1965864600205111832*x^19 + 3016989393277154199*x^18 + 993850365653028982*x^17 + 1661221355151932055*x^16 + 2141520480611688809*x^15 + 636670112723307258*x^14 + 1200822100799196786*x^13 + 2223563845526420680*x^12 + 3134534498746508642*x^11 + 1820327632682349699*x^10 + 4628418849122802568*x^9 + 3731553570235638636*x^8 + 1636534607043587796*x^7 + 1007966122754856335*x^6 + 3571611463638839115*x^5 + 4733247188903796455*x^4 + 3512981852602786831*x^3 + 1560667366459827025*x^2 + 1113839338158290233*x + 4011393002849553527)Q = (x^64 + 2776622066009961678*x^63 + 1020248994272362724*x^62 + 1812889731002797017*x^61 + 3946133096396475132*x^60 + 1064362775780462120*x^59 + 4267166204741846229*x^58 + 4461168980925876722*x^57 + 3701193932757315736*x^56 + 4004259984657770019*x^55 + 2566923830139634808*x^54 + 2958380329303059106*x^53 + 4642913814072279374*x^52 + 713990683265973444*x^51 + 2282781718594249732*x^50 + 1691679008052617295*x^49 + 4723620313305465430*x^48 + 4052669689859242595*x^47 + 4607757741831461143*x^46 + 3048879536065529044*x^45 + 2012013680568798151*x^44 + 2125237235418450484*x^43 + 2622384625077739224*x^42 + 710661875195936255*x^41 + 375897308743404378*x^40 + 3253268532586707019*x^39 + 3759767504239334681*x^38 + 2945194932005180334*x^37 + 1316716161821289054*x^36 + 2210075866459201344*x^35 + 3421886933443572088*x^34 + 2124192011313760002*x^33 + 3183242335232871177*x^32 + 4722704310996441203*x^31 + 1640862527872462873*x^30 + 292078618156889354*x^29 + 3970255331239899451*x^28 + 290424178543927660*x^27 + 3979382049081683506*x^26 + 3341058157535181184*x^25 + 1891458780676141416*x^24 + 4585931142037966308*x^23 + 2621586816910493860*x^22 + 4526407296014662985*x^21 + 3345825075365423903*x^20 + 433595205227433076*x^19 + 3510443356995660854*x^18 + 1469161865274264871*x^17 + 1968552305256496645*x^16 + 1902262417167822976*x^15 + 3211385257470450715*x^14 + 259183745852362935*x^13 + 1368548986536267534*x^12 + 3726482530039832086*x^11 + 1196244075361051439*x^10 + 3346319329141804238*x^9 + 2362535635162047034*x^8 + 2131037938034625812*x^7 + 3970887869581347678*x^6 + 4428522899784697485*x^5 + 2482987898184812388*x^4 + 3180131420672415636*x^3 + 4690602932003451909*x^2 + 2572790493146370264*x + 802891458181310745)cv = (p ** 64 - 1) // 2fin = 0add = 1for ply in c:    Pv = power_mod(ply, cv, P)    Qv = power_mod(ply, cv, Q)    if Pv == 1 and Qv == 1:        fin += add    add = add * 2print(fin) ## long to bytes hereColored by Color Scripter cs

urara

 123456789101112131415161718192021222324252627282930313233 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) Colored by Color Scripter cs

Very concise problem. We are given $t, e, n$ and $(m+t)^e \pmod{n}$, and a point is double the point with [$x$-coordinate equal to $m$] [which lies on the elliptic curve $y^2 = x^3 + ax + b$]. I broke that sentence up into pieces because it's pretty long and confusing. So anyways, doing actually elliptic curve stuff seems nearly impossible with the lack of hints we have, and we have a huge hint in $(m+t)^e \pmod{n}$. If we have another polynomial equation about $m$ in $\mathbb{Z}_n[x]$, we can solve this problem using polynomial GCD. (Franklin-Reiter related message attack, like padrsa in InterKosen CTF) Of course, we do have another polynomial equation! Directly using the doubling formula, we have $$(3m^2 + a)^2 - (2m + Q_x)(4(m^3 + am+b)) \equiv 0 \pmod{n}$$ which is the type of equation we want. Write polynomial GCD, and we can easily find $m$. Again, note that if we encounter a problem while performing standard Euclidean Algorithm, it's because the leading coefficient has a non-trivial GCD with $n$. In this case, we can just factorize $n$ to solve the problem. I was stuck in sharsable for so long before solving this one, so I got some energy from it :D

For the implementation of polynomial GCD, refer to the write-up of the problem padrsa

 123456 K = Zmod(n)P. = PolynomialRing(K, implementation='NTL')f = (3 * x^2 + a)^2 - (2*x + Qx) *(4*(x^3 + a*x+b))g = power_mod(x + t, 65537, f) - cprint(GCD(f, g, n))## the remaining details are trivial cs

sharsable

 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152 from Crypto.Util.number import getPrime, GCDfrom flag import FLAGimport 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, n)C2 = pow(M, B, n)assert(pow(C1, A, n) * pow(C2, B, n) % n == M) import jsonprint(json.dumps({    "n": n,    "A": (A, C1),    "B": (B, C2),    #"d": (A, B), # for debug    })) Colored by Color Scripter cs

The code looks convoluted, but it can be compressed (without information loss) into the following results:

• $d_1, d_2$ are quite small, around $n^{0.16}$.
• $e_1d_1 + e_2d_2 \equiv 1 \pmod{\phi(n)}$.
• We know $e_1, e_2, n$, but we can't use common modulus attack due to $\text{gcd}(e_1, e_2) = 11$.

I didn't even realize we could use common modulus attack here, but that was okay since it doesn't give us useful information anyway. The key clearly lies in the small $d_1, d_2$. At first, my thought was headed to the Wiener's Attack, which I think is justifiable because that attack works with small $d$ as well. Of course, it's hard (if not impossible) to use the continued fraction idea directly. After reading up on some generalizations of Wiener's Attacks, I thought this problem was related to the coppersmith attack. I tried weird stuff like 3-variable coppersmith but it all failed pretty badly. That led to me solving this problem the last out of the four I solved. The idea of the last problem helped me :)

We begin by writing (note that this kind of manipulation is done in Wiener's Attack as well) $$e_1 d_1 + e_2 d_2 = k \phi(n) + 1 = k(n-p-q+1) + 1 \equiv -k(p+q-1) + 1 \pmod{n}$$ We may now note that $k$ is probably around $n^{0.16}$ as well, so the RHS is around $-n^{0.66}$ multiplied by some constant.

Okay, so we want $d_1, d_2$ to be around $n^{0.16}$, and $e_1d_1 + e_2d_2 \pmod{n}$ to be around $-n^{0.66} \cdot c$ for some "reasonable" constant $c$. Let's first decide the range of $c$ we will look for. We can expect $k$ to be $0.4 \cdot n^{0.16}$ to $2 \cdot n^{0.16}$. We can expect $p+q$ to be $2 \cdot n^{0.5}$ to $3/\sqrt{2} \cdot n^{0.5}$. Combining, we can get something like $c \in [0.8, 4]$. Note that I'm using a lot of handwaving. Now we will fix $c$.

The result? We have goal values for $d_1, d_2, e_1d_1 + e_2d_2 \pmod{n}$. Sounds like CVP to me now.

Indeed, we can work this as a CVP with the lattice generated by $$[e_1, 1, 0], \quad [e_2, 0, 1], \quad [n, 0, 0]$$ and making the result vector as close as possible to $$[-c \cdot n^{0.66}, n^{0.16}, n^{0.16} ]$$ Here's a problem. The scale between the first column and the next two columns are off by $n^{0.5}$. If we run CVP now, it'll probably ignore the $n^{0.16}$ condition in order to get similar values for the first column. At least, that's what I thought :D

Therefore, we rescale. We will work with the lattice generated by $$[e_1, n^{0.5}, 0], \quad [e_2, 0, n^{0.5}], \quad [n, 0, 0]$$ and making our result vector as close as possible to $$[-c \cdot n^{0.66}, n^{0.66}, n^{0.66} ]$$ which sounds more reasonable. If we run the CVP algorithm, (Babai's) we will have our candidate values for $d_1, d_2$.

If correct, we will have that $e_1d_1 + e_2d_2 - 1$ is a product of $\phi(n)$, so we can finish easily. So, how do we find the right $c$ to use?

Simple. Just try a whole bunch of them. Refer to the code below for details.

 1234567891011121314151617181920212223242526272829303132333435363738 def Babai_closest_vector(M, G, target):        small = target        for _ in range(1):            for i in reversed(range(M.nrows())):                c = ((small * G[i]) / (G[i] * G[i])).round()                small -=  M[i] * c        return target - small     n  = 142793817321992828777925840162504083304079023834001118099549928854335392622287928254035247188624975743042449746066633491912316354241339908190889792327014012472372654378644158878787350693992259970146885854641856991605625756536504266728483088687985429310233421251081614258665472164668993082471923690196082829593e1 = 82815162880874815458042429141267540989513396527359063805652845923737062346339641683097075730151688566721221542188377672708478777831586255213972947470222613130635483227797717393291856129771004300757155687587305350059401683671715424063527610425941387424425367153041852997937972925839362190900175155479532582934C1 = 108072697038795075732704334514926058617161875495016327352871122917196026504758904760148391499245235850616838765611460630089577948665981247735905622903872682862860306107704253287284051312867625831877418240290183661755993649928399992531008191618616452091127799880839665225093055618092869662205901927957599941568e2 = 84856171747859965508406237198459622554468224770252249975158471902036102010991476445962577679301719179079633469099994226630172251817358960347828156301869905575867853640850107406452911333646573296923235424617864473580743418995994067645338437540627399276292679100115018844287273293945121023787594592185295794983C2 = 101960082023987498941061751761131381167414505957511290567652602520714324823481487410890478130601013005035303795327512367595187718926017321227779179404306882163521882309833982882201152721855538832465833869251505131262098978117904455226014402089126682222497271578420753565370375178303927777655414023662528363360 rat = int(n ** 0.5)M = Matrix(ZZ, 3, 3)M[0, 0] = e1M[1, 0] = e2M[2, 0] = nM[0, 1] = ratM[1, 2] = rat L = []for i in range(800, 2450):    Target = vector([-int(n ** 0.66 * i / 1000) , int(n ** 0.16) * rat, int(n ** 0.16) * rat])    M = M.LLL()    GG = M.gram_schmidt()    TT = Babai_closest_vector(M, GG, Target)    d1 = TT // rat    d2 = TT // rat    L.append(e1 * d1 + e2 * d2 - 1)print(list(set(L))) ## this is c for phi in c:    d1 = inverse(e1, phi)    print(long_to_bytes(pow(C1, d1, n)))    d2 = inverse(e2, phi)    print(long_to_bytes(pow(C2, d2, n)))Colored by Color Scripter cs

crypto01

 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192 from sage.all import *from flag import flagfrom 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 = 512HINTSIZE = 96N = 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 = 0ciphertexts = []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<

@diff (pcw) noted that the order of the elliptic curve must be $(p+1)(q+1)$ since $p \equiv q \equiv 2 \pmod{3}$.

This is a cool fact that I didn't know, but it could be easily guessed by the definition of $d$ in the script.

So, first things first : is this really a elliptic curve challenge? The answer : probably not?

I thought this for a few reasons - I thought the generation of $e$ was quite convoluted so there should be a weakness.

The elliptic curve part looked too clean to have a vulnerability, and it's not even over a field. Hard to do anything, really.

Therefore, I decided to take a look at how the parameter generation behaves.

First, I look at the sizes of the values. It 's clear that $y$ is small, so $zbound$ and $z$ are also quite small compared to $x$.

This leads to the following suspicion, is $e = \lfloor (p+1)(q+1)y / x \rfloor$? Generating parameters on our own, we see that this is true with a very high probability. This means that we can ignore $zbound$ and $z$ completely now! This is a good progress indeed :)

This simplifies a lot of things, and we have a good, clean equation to work with. Start with $$xe = (p+1)(q+1)y - r \equiv (p+q+1)y - r\pmod{n}$$ with $r < x \approx n^{0.4}$. With $y \approx n^{0.1}$, we see that $(p+q+1)y - r \approx n^{0.6}$. So $x \approx n^{0.4}$ satisfies $xe \pmod{n} < \approx n^{0.6}$.

Heuristically speaking, there should be a fairly small number of $x$ that satisfy that condition! Can we find them though?

Turns out the answer is yes. I guess you can do this with lattices, but here's a method I learned from competitive programming.

In fact, given $L, R, M, A$, we can find the minimum nonnegative integer $x$ such that $L \le Ax \pmod{M} \le R$.

The method is not long, but I don't want to type it all out, so here's a link (scroll down to the end of the editorial)

Also, a problem using this algorithm appeared in NWRRC, (problem G) set by tourist.

Since we know $e, n$, we can select some $CUT \approx n^{0.6}$ and find the minimum $x$ such that $1 \le ex \pmod{n} \le CUT$. Of course, we have to be cautious with constants when selecting $CUT$. It's not too hard, since we can always verify our value of $x$ by checking its primality and size. This concludes the recovery of $x$, which is a huge progress again! Now we try to recover $y$.

To recover $y$, we use basic inequalities. Note the following two inequalities $$y = \frac{xe+r}{(p+1)(q+1)} \ge \frac{xe}{n + 3 \sqrt{n/2} + 1}$$ $$y = \frac{xe+r}{(p+1)(q+1)} \le \frac{xe + x-1}{n + 2\sqrt{n} + 1}$$ which gives us decent lower/upper bounds. Turns out that this is also perfect, as the two bounds are actually equal! This recovers $y$.

With this information, we can now bound $p+q$. Simply use $$p+q = \frac{xe+r}{y} - 1 \ge \frac{xe}{y} - 1$$ $$p+q = \frac{xe+r}{y} -1 \le \frac{xe+x-1}{y} - 1$$ which gives us a good bound for $p+q$. Now we proceed as we did in l33tcrypt in DownUnderCTF and use quadratic formula to get a good bound for $p$. Note that $p > q$. If we analyze the two bounds, we see that this gives us about 200 MSBs of $p$. Now we are practically done.

We already know 96 LSBs of $p$ via the hint. This adds up to 296 bits of information, so we only need to determine 216 bits of $p$. This can be easily done with coppersmith method, i.e. Sage's small_roots. This part is very straightforward. Now we calculate $p, q, d$ and eventually the masks. The conversion of masks to the actual flag was done by @ironore15. This concludes the problem :D

Also, maybe you can recover $x, y$ with continued fractions on $e/n$? Maybe. I didn't try it :P

UPD : Okay I tried it and it works easily. Why didn't I think about this lmao... This is a much easier way to solve. :)

Basically, from $e = \lfloor (p+1)(q+1)y / x \rfloor$, we can guess that $$\frac{e}{n} \approx \frac{e}{(p+1)(q+1)} \approx \frac{y}{x}$$ so $y/x$ is a good approximation of $e/n$. Find all convergents of $e/n$, and find those that have primes as its numerator and denominator.

This gives us $x, y$, so we can proceed with the coppersmith attack as above. Much easier :)

UPD : The continued fraction solution is indeed the intended sol. I guess it could be proved using the given bounds :)

UPD : So apparently this thing had a name, KMOV cryptosystem. didn't know that :P

 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879 def kthp(n, k):    if n == 0:        return 0    lef = 1    rig = 2    while rig ** k < n:        rig = rig << 1    while lef <= rig:        mid = (lef + rig) // 2        if mid ** k <= n:            best = mid            lef = mid + 1        else:            rig = mid - 1    return best def ceil(n, m):    return (n + m - 1) // m def optf(A, M, L, R):    if L == 0:        return 0    if 2 * A > M:        L, R = R, L        A = M - A        L = M - L        R = M - R    cc_1 = ceil(L, A)    if A * cc_1 <= R:        return cc_1    cc_2 = optf(A - M % A, A, L % A, R % A)    return ceil(L + M * cc_2, A) 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 ciphertexts =  []for C in ciphertexts:    n = C['n']    e = C['e']    c = C['c']    hint = C['hint']    CUT = kthp( (int)(n ** 0.2) // 72, 2) * kthp(n, 2) * 8    x = optf(e, n, 1, CUT)    R = ((e * x + x - 1) // (n + 2 * kthp(n, 2) + 1))    L = ((e * x) // (n + 3 * kthp(n//2, 2) + 1))    y = (L + R) // 2    assert L == R and x in Primes() and y in Primes()    sum_L = (x * e) // y - 1 - n    sum_R = (x * e + x - 1) // y - 1 - n    lr = (sum_R + kthp(sum_R * sum_R - 4 * n, 2)) // 2    sm = (sum_L + kthp(sum_L * sum_L - 4 * n, 2)) // 2    assert sm <= lr    assert (sm >> 312) == (lr >> 312)    p_hint = hint    K = Zmod(n)    P. = PolynomialRing(K, implementation='NTL')    f = (p_hint * inverse_mod(2 ** 96, n)) % n + t + (2 ** (312-96)) * (lr >> 312)    x0 = f.small_roots(X = (2 ** 220), beta = 0.5, epsilon = 0.03)    ## print(x0)    p = p_hint + x0 * (2 ** 96) + (2 ** 312) * (lr >> 312)    p = (int)(p)    q = n // p    d = inverse_mod(e, (p+1) * (q+1))    print(decrypt(c, d, n)) ## thanks, ironore!def recover_flag(masks, masked_flag):    flag = reduce(lambda a, b: a ^ b, masks, masked_flag)    return flag.to_bytes(512 // 8, 'big')Colored by Color Scripter cs

 123456789101112131415161718192021222324252627282930313233 def get_red(e, n):    cur_num, cur_den = e, n    num_1, den_1 = 0, 1    num_2, den_2 = 1, 0    while True:        val = cur_num // cur_den        nxt_num = cur_den        nxt_den = cur_num - val * cur_den        # calculate new convergent        num_3 = val * num_2 + num_1        den_3 = val * den_2 + den_1        if isPrime(num_3) and isPrime(den_3):            return num_3, den_3        if den_3 > int(n ** 0.4):            return -1        # update convergents        num_1, den_1 = num_2, den_2        num_2, den_2 = num_3, den_3        # update continued fractions        cur_num, cur_den = nxt_num, nxt_den ciphertexts =  []for C in ciphertexts:    n = C['n']    e = C['e']    c = C['c']    hint = C['hint']    y, x = get_red(e, n)    R = ((e * x + x - 1) // (n + 2 * kthp(n, 2) + 1))    L = ((e * x) // (n + 3 * kthp(n//2, 2) + 1))    assert y == (L + R) // 2    assert L == R and isPrime(x) and isPrime(y)    ## continue as the initial solution cs

#### '수학 > 암호론 및 CTF' 카테고리의 다른 글

 N1CTF 2020 Crypto Write-Ups  (0) 2020.10.18 2020.10.18 2020.10.11 2020.09.30 2020.09.20 2020.09.19 오늘 남았던 2문제를 해결하여 올솔브를 했습니다. 2문제 다 쫄아서 못 건드리고 있었는데 펜 굴리니까 생각보다 무난하게 풀리네요 :)

여기서 접근한 새로운 정보들이 많으니 공부 좀 해야겠습니다. 그래도 올솔하니까 후련하네요 ㅋㅋ

#### '수학 > 암호론 및 CTF' 카테고리의 다른 글

 Leftover Hash Lemma and its Applications  (0) 2020.10.18 2020.10.11 2020.09.30 2020.09.20 2020.09.19 2020.09.06
1. rkm 그는 갓인가.. rkm 그는 갓인가..rkm 그는 갓인가..rkm 그는 갓인가..rkm 그는 갓인가..

• 2020.10.07 18:56 신고

바킹독 그는 킹인가.. 바킹독 그는 킹인가.. 바킹독 그는 킹인가.. 바킹독 그는 킹인가.. 바킹독 그는 킹인가..

2. mathboy7 2020.10.08 07:04

당신의 팬을 멈출 수 없습니다!!

I participated in TWCTF 2020 as a member of the team D0G$. We got 1st place! easy hash I tried to do something but then @yoshiking sensei solved it. :D sqrt  12345678910111213141516171819202122 from Crypto.Util.number import bytes_to_long, isPrimefrom secret import flag, p def encrypt(m, k, p): return pow(m, 1 << k, p) assert flag.startswith("TWCTF{")assert len(flag) == 42assert isPrime(p) k = 64pt = bytes_to_long(flag.encode())ct = encrypt(pt, k, p) with open("output.txt", "w") as f: f.write(str(ct) + "\n") f.write(str(p) + "\n") # 5602276430032875007249509644314357293319755912603737631044802989314683039473469151600643674831915676677562504743413434940280819915470852112137937963496770923674944514657123370759858913638782767380945111493317828235741160391407042689991007589804877919105123960837253705596164618906554015382923343311865102111160# 6722156186149423473586056936189163112345526308304739592548269432948561498704906497631759731744824085311511299618196491816929603296108414569727189748975204102209646335725406551943711581704258725226874414399572244863268492324353927787818836752142254189928999592648333789131233670456465647924867060170327150559233 cs So we are given$m^{2^{64}} \pmod{p}$and$p$. We need to find$m$. The first thing we note is that$\nu_2 (p-1) = 30$. Therefore, we have$\text{gcd}(2^{64}, p-1) = 2^{30}$possibilities for$m$, if we disregard the length and "TWCTF{" condition. This is a large number of solutions, but it's not impossible to brute force. We first find any solution of$m^{2^{64}} \equiv enc \pmod{p}$by repeated usage of Tonelli-Shanks. Now, we may write all solutions as$m \cdot g^{(p-1)/2^{30} \cdot k}$, where$g$is some generator easily found by Sage. We go over each solution, check if it's small enough to be a candidate first (optimization), then convert it to bytes and see if it meets the desired conditions. It was estimated to run in ~1.5 hours in my computer, so I asked for some computational help. @theoldmoon0602 and @ironore15 were kind enough to help me in this brute force.  1234567891011121314151617181920212223242526272829303132 ## Step 1 : Find any solutiondef gogo(r, d, m): if d == 0: print(r) exit() return u = tonelli(m, r) if u == -1: return gogo(u, d-1, m) gogo((m-u)%m, d-1, m) ## Step 2 : Start Brute Forceres = 5602276430032875007249509644314357293319755912603737631044802989314683039473469151600643674831915676677562504743413434940280819915470852112137937963496770923674944514657123370759858913638782767380945111493317828235741160391407042689991007589804877919105123960837253705596164618906554015382923343311865102111160p = 6722156186149423473586056936189163112345526308304739592548269432948561498704906497631759731744824085311511299618196491816929603296108414569727189748975204102209646335725406551943711581704258725226874414399572244863268492324353927787818836752142254189928999592648333789131233670456465647924867060170327150559233ex = 1948865039294009691576181380771672389220382961994854292305692557649261763833149884145614983319207887860531232498119502026176334583810204964826290882842308810728384018930976243008464049012096415817825074466275128141940107121005470692979995184344972514864128534992403176506223940852066206954491827309484962494271assert pow(ex, 1 << 64 , p) == res def is_ascii(s): return all(c < 128 for c in s) gen = 3jp = pow(3, (p-1) // (2 ** 30), p) for i in tqdm(range(0, 2**30)): ex = (ex * jp) % p if ex.bit_length() <= 400: u = long_to_bytes(ex) if is_ascii(u) and b"TWCTF{" in u: print(u) exit()Colored by Color Scripter cs twin-d  1234567891011121314151617181920 require 'json'require 'openssl' p = OpenSSL::BN::generate_prime(1024).to_iq = OpenSSL::BN::generate_prime(1024).to_i while true d = OpenSSL::BN::generate_prime(1024).to_i break if ((p - 1) * (q - 1)).gcd(d) == 1 && ((p - 1) * (q - 1)).gcd(d + 2) == 1end e1 = OpenSSL::BN.new(d).mod_inverse(OpenSSL::BN.new((p - 1) * (q - 1))).to_ie2 = OpenSSL::BN.new(d + 2).mod_inverse(OpenSSL::BN.new((p - 1) * (q - 1))).to_i flag = File.read('flag.txt')msg = OpenSSL::BN.new(flag.unpack1("H*").to_i(16))n = OpenSSL::BN.new(p * q)enc = msg.mod_exp(OpenSSL::BN.new(e1), n) puts ({ n: (p*q).to_s, e1: e1.to_s, e2: e2.to_s, enc: enc.to_s }).to_json cs So we have$e_1, e_2$corresponding to$d_1, d_2$, which have a difference of$2$. Basically what this says is that$e_2^{-1} - e_1^{-1} \equiv 2 \pmod{\phi(n)}$. Therefore, we can simply write$e_1-e_2 \equiv 2e_1e_2 \pmod{n}$. This implies that$2e_1e_2 + e_2 - e_1$is a multiple of$\phi(n)$. It is very well-known fact that given$n$and a multiple of$\phi(n)$, we can factorize$n$. So apply that method to factorize$n$. The rest is basic RSA. Happy to get first solve :)  12345678910111213141516171819202122232425262728 n = 26524843197458127443771133945229625523754949369487014791599807627467226519111599787153382777120140612738257288082433176299499326592447109018282964262146097640978728687735075346441171264146957020277385391199481846763287915008056667746576399729177879290302450987806685085618443327429255304452228199990620148364422757098951306559334815707120477401429317136913170569164607984049390008219435634838332608692894777468452421086790570305857094650986635845598625452629832435775350210325954240744747531362581445612743502972321327204242178398155653455971801057422863549217930378414742792722104721392516098829240589964116113253433e1 = 3288342258818750594497789899280507988608009422632301901890863784763217616490701057613228052043090509927547686042501854377982072935093691324981837282735741669355268200192971934847782966333731663681875702538275775308496023428187962287009210326890218776373213535570853144732649365499644400757341574136352057674421661851071361132160580465606353235714126225246121979148071634839325793257419779891687075215244608092289326285092057290933330050466351755345025419017436852718353794641136454223794422184912845557812856838827270018279670751739019476000437382608054677808858153944204833144150494295177481906551158333784518167127e2 = 20586777123945902753490294897129768995688830255152547498458791228840609956344138109339907853963357359541404633422300744201016345576195555604505930482179414108021094847896856094422857747050686108352530347664803839802347635174893144994932647157839626260092064101372096750666679214484068961156588820385019879979501182685765627312099064118600537936317964839371569513285434610671748047822599856396277714859626710571781608350664514470335146001120348208741966215074474578729244549563565178792603028804198318917007000826819363089407804185394528341886863297204719881851691620496202698379571497376834290321022681400643083508905enc = 18719581313246346528221007858250620803088488607301313701590826442983941607809029805859628525891876064099979252513624998960822412974893002313208591462294684272954861105670518560956910898293761859372361017063600846481279095019009757152999533708737044666388054242961589273716178835651726686400826461459109341300219348927332096859088013848939302909121485953178179602997183289130409653008932258951903333059085283520324025705948839786487207249399025027249604682539137261225462015608695527914414053262360726764369412756336163681981689249905722741130346915738453436534240104046172205962351316149136700091558138836774987886046 cc = 2 * e1 * e2 + e2 - e1 tt = 0cv = ccwhile cv % 2 == 0: cv //= 2 tt += 1 for i in range(3, 100): t = pow(i, cv, n) for j in range(0, tt): g = GCD(t-1, n) if g != 1 and g != n: print(g) ## this is p exit() t = (t * t) % n p = 177276401739167429751099686272064967069179029118915820763787396008698833618702905602522557760805466539182350759150950532254737829482867347218636052172454990031666206911810532732619372311183056810552780771197878348351916381506465238562588760944922289622011858546760490648690942678177540128777265354408766804279q = n // p phi = (p-1) * (q-1)d = inverse(e1, phi)print(long_to_bytes(pow(enc, d, n)))Colored by Color Scripter cs The Melancholy of Alice  1234567891011121314151617181920212223242526272829303132333435363738394041 from Crypto.Util.number import getStrongPrime, getRandomRange N = 1024 def generateKey(): p = getStrongPrime(N) q = (p - 1) // 2 x = getRandomRange(2, q) g = 2 h = pow(g, x, p) pk = (p, q, g, h) sk = x return (pk, sk) def encrypt(m, pk): (p, q, g, h) = pk r = getRandomRange(2, q) c1 = pow(g, r, p) c2 = m * pow(h, r, p) % p return (c1, c2) def main(): with open("flag.txt") as f: flag = f.read().strip() pk, sk = generateKey() with open("publickey.txt", "w") as f: f.write(f"p = {pk}\n") f.write(f"q = {pk}\n") f.write(f"g = {pk}\n") f.write(f"h = {pk}\n") with open("ciphertext.txt", "w") as f: for m in flag: c = encrypt(ord(m), pk) f.write(f"{c}\n") if __name__ == "__main__": main() Colored by Color Scripter cs I had good fun solving this problem, so I'll write my thought process as well. This honestly looks like a perfect code, but the key line that left a question mark for me was line 35.$ord(m)$is incredibly small, so maybe we can bypass the entire discrete logarithm? To think further in this direction, we need some knowledge on$p-1$. I first checked if$q$was prime - it was not. Then I checked the factors of$q$- I could brute force small primes, but I just went to FactorDB. Why not? I found out that$3, 5, 19$were factors of$q$, which was quite surprising to me. I thought StrongPrimes generated a prime of a form$2 \cdot q + 1$where$q$is a prime. Oops? Anyways, since$3 \cdot 5 \cdot 19$was pretty large, so it seems this should be fine. Discrete Logarithm calculation is hard, but calculation modulo a small prime is easy by Pohlig-Hellman style thinking. Can we abuse this? Well, given the signature data we can calculate the logarithm of the$ord(m)$modulo$3 \cdot 5 \cdot 19$. So if we precompute all logarithms of 0 to 255 modulo$3 \cdot 5 \cdot 19$, we can find the "candidates" for each letter. I did this, but found there are multiple solutions. I tried to fix this by working with$5710354319$, which is another prime divisor. I thought this should also work using sage's BSGS and stuff, but it was way too slow. I posted my partial result (candidates) on discord and asked for guesswork/recovery, then @yoshiking found the solution.  123456789101112131415161718192021222324252627282930313233343536373839 def crt(a, b): u, v = 0, 1 for i in range(len(a)): u, v = CRT(u, v, a[i], b[i]) return u def get_DL(x, pr): gg = pow(x, (p-1) // pr, p) for i in range(0, pr): gt = pow(g, i * (p-1) // pr, p) if gt == gg: return i def get_DLs(x): p_1 = get_DL(x, 3) p_2 = get_DL(x, 5) p_3 = get_DL(x, 19) return crt([p_1, p_2, p_3], [3, 5, 19]) cc = [-1]for i in range(1, 255): cc.append(get_DLs(i)) xx = get_DLs(h) res = []fin = []fom = ""for x, y in res: s = "" u = get_DLs(x) v = get_DLs(y) ## v = xx * u + get_DLs(desire) res = (v - xx * u) % (3 * 5 * 19) for j in range(0, 255): if cc[j] == res and j <= 128: s += chr(j) print(s) Colored by Color Scripter cs XOR and shift encryptor  12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182 #!/usr/bin/python3 s = []p = 0 def init(): global s,p s = [i for i in range(0,64)] p = 0 return def randgen(): global s,p a = 3 b = 13 c = 37 s0 = s[p] p = (p + 1) & 63 s1 = s[p] res = (s0 + s1) & ((1<<64)-1) s1 ^= (s1 << a) & ((1<<64)-1) s[p] = (s1 ^ s0 ^ (s1 >> b) ^ (s0 >> c)) & ((1<<64)-1) return res def jump(to): # Deleted... return def check_jump(): init() jump(10000) assert randgen() == 7239098760540678124 init() jump(100000) assert randgen() == 17366362210940280642 init() jump(1000000) assert randgen() == 13353821705405689004 init() jump(10000000) assert randgen() == 1441702120537313559 init() for a in range(31337):randgen() for a in range(1234567):randgen() buf = randgen() for a in range(7890123):randgen() buf2 = randgen() init() jump(31337+1234567) print (buf == randgen()) jump(7890123) print (buf2 == randgen()) check_jump() init()for a in range(31337):randgen() flag = open("flag.txt").read()assert len(flag) == 256 enc = b"" for x in range(len(flag)): buf = randgen() sh = x//2 if sh > 64:sh = 64 mask = (1 << sh) - 1 buf &= mask jump(buf) enc += bytes([ ord(flag[x]) ^ (randgen() & 0xff) ]) print ("%r" % enc) open("enc.dat","wb").write(bytearray(enc)) Colored by Color Scripter cs So basically what we have to do is efficiently "advance" the RNG large amount of times. The given RNG state transition can be regarded as a linear transformation over the$64^2$bits in the state. Therefore, we can model this by matrix multiplication, where the size of the matrix is$64^2$. Using binary exponentiation, we can get our random numbers relatively quickly. I had thought of this but believed this would be way too slow, but @theoldmoon0602 wrote a beautiful code in sage and managed to find the flag. The code took about 30 minutes ~ 1 hour to run, according to the solver. The below code, by @theoldmoon0602, derives the key sequence. Also, for the write-up written by the actual solver @theoldmoon0602, check here.  123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103 N = 64F = GF(2) def L(n): m = [[0 for x in range(N)] for y in range(N)] for i in range(N - n): m[i + n][i] = 1 return matrix(F, m) def R(n): m = [[0 for x in range(N)] for y in range(N)] for i in range(N - n): m[i][i + n] = 1 return matrix(F, m) def I(): m = [[0 for x in range(N)] for y in range(N)] for i in range(N): m[i][i] = 1 return matrix(F, m) def O(): m = [[0 for x in range(N)] for y in range(N)] return matrix(F, m) def genM(): a = 3 b = 13 c = 37 o = O() i = I() la = L(a) rb = R(b) rc = R(c) blocks = [ [i + rc, i + la + rb + la*rb] + [o for _ in range(62)] ] for j in range(1, N): row = [o for _ in range(N)] row[(j+1) % N] = i blocks.append(row) M = block_matrix(F, [*zip(*blocks)]) return M def initial_state(): s = "".join(["{:064b}".format(i) for i in range(N)]) vec = [] for c in s: vec.append(F(int(c))) return Matrix(F, vec) def getvalue(row, index): v = 0 for i in range(N): v = v*2 + int(row[index*N + i]) return v def dumpstate(a): xs = [] for i in range(N): xs.append(getvalue(a, i)) print(xs) s = initial_state()M = genM() def init(): global s, M s = initial_state() M = genM() def randgen(): global s, M res = (getvalue(s, 0) + getvalue(s, 1)) % ((1<<64)-1) s = s * M return res def jump(n): global s,M s = s * (M^n) init()jump(31337)for x in range(256): buf = randgen() sh = x//2 if sh > 64:sh = 64 mask = (1 << sh) - 1 buf &= mask jump(buf) print(randgen() & 0xff) Colored by Color Scripter cs circular  123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657 ## keygen require "openssl"require "json" p = OpenSSL::BN.generate_prime(1024)q = OpenSSL::BN.generate_prime(1024)k = OpenSSL::BN.generate_prime(2048, false)n = p * qFile.write("pubkey.txt", { n: n.to_s, k: k.to_s }.to_json) ## interaction require "functions_framework"require "digest/sha2" fail unless ENV["FLAG"] key = JSON.parse(File.read("pubkey.txt"))n = key["n"].to_ik = key["k"].to_i EXPECTED_MESSAGE = 'SUNSHINE RHYTHM' FunctionsFramework.http("index") do |request| if request.request_method != "POST" return "Bad Request" end data = JSON.parse(request.body.read) cmd = data["cmd"] if cmd == "pubkey" return { pubkey: { n: n.to_s, k: k.to_s } } elsif cmd == "verify" x = data["x"].to_i y = data["y"].to_i msg = data["msg"].to_s hash = "" 4.times do |i| hash += Digest::SHA512.hexdigest(msg + i.to_s) end hash = hash.to_i(16) % n signature = (x ** 2 + k * y ** 2) % n if signature == hash if msg == EXPECTED_MESSAGE return { result: ENV["FLAG"] } end return { result: "verify success" } else return { result: "verify failed" } end else return "invalid command" endend Colored by Color Scripter cs Basically, we have to find$x, y$such that$x^2 + ky^2 \equiv HASH \pmod{n}$. We know$k, HASH, n$, but not the factorization of$n$. This seemed to be very difficult. First few ideas of mine included the Brahmagupta's Identity and Pell's Equation. I tried to work on Pell's Equation + continued fractions, but it failed as well. After a while, @ironore15 notified us that this scheme has a name - OSS signature. I was quite surprised because I didn't think this would be an actual scheme in the literature. Anyways, after a bit of googling I was able to find a paper that describes the attack. The rest was relatively straightforward implementation. I was glad to see one of my ideas used in the attack.  12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091 def comb(x1, y1, x2, y2, k, n): return (x1 * x2 + k * y1 * y2) % n, (x1 * y2 - x2 * y1) % n def solve(k, m, n): ## solve x^2 + ky^2 == m mod n print("solve", k, m, n) fu = kthp(m, 2) if fu * fu == m: return (fu, 0) if k < 0: se = kthp(-k, 2) if se * se == -k: retx = (m+1) * inverse(2, n) % n rety = (m-1) * inverse(2 * se, n) % n return retx, rety if m == 1: return (1, 0) if m == k % n: return (0, 1) while True: u = random.getrandbits(1024) v = random.getrandbits(1024) m_0 = (m * (u * u + k * v * v)) % n if isPrime(m_0): if GCD(m_0, n) != 1: print("LOL", m_0) exit() x_0 = tonelli(m_0, (-k) % m_0) if (x_0 * x_0 + k) % m_0 == 0: break ms = [m_0] xs = [x_0] sz = 1 while True: new_m = (xs[sz-1] * xs[sz-1] + k) // ms[sz-1] ms.append(new_m) if k > 0 and xs[sz-1] <= ms[sz] <= ms[sz-1]: sz = sz + 1 break if k < 0 and abs(ms[sz]) <= kthp(abs(k), 2): sz = sz + 1 break xs.append(min(xs[sz-1] % ms[sz], ms[sz] - (xs[sz-1] % ms[sz]))) sz = sz + 1 assert sz == len(ms) assert sz - 1 == len(xs) uu, vv = xs, 1 dv = 1 for i in range(1, sz-1): assert (xs[i] ** 2 + k) % n == (ms[i] * ms[i+1]) % n uu, vv = comb(uu, vv, xs[i], 1, k, n) dv = (dv * ms[i]) % n dv = (dv * ms[sz-1]) % n uu = (uu * inverse(dv, n)) % n vv = (vv * inverse(dv, n)) % n X, Y = solve(-ms[sz-1], (-k) % n, n) soly = inverse(Y, n) solx = (X * soly) % n finx, finy = comb(solx, soly, uu, vv, k, n) godx = ((finx * u - k * finy * v) * inverse(u * u + k * v * v, n)) % n gody = ((finx * v + finy * u) * inverse(u * u + k * v * v, n)) % n return godx, gody msg = 'SUNSHINE RHYTHM'hsh = '' for i in range(0, 4): cc = msg + chr(ord('0') + i) hsh += hashlib.sha512(cc.encode()).hexdigest() request = { 'cmd': 'pubkey'}X = web_request('POST', 'https://crypto02.chal.ctf.westerns.tokyo', request, False) n = 25299128324054183472341067223932160732879350179758036557232544635970111090474692853470743347443422497121006796606102551210094872253782062717537548880909979729182337501587763866901367212812697076494080678616385493076865655574412317879297160790121009524506015912113098690685202868184636344610142590510988192306870694667596904330867479578103616304053889409982447653859514868824002960431331342963562137691362725961627846051021103954795862501700267818317148154520620016172888281127685503677751830350686839873220480306266506898497203511851305686566444690384065880667273398255172752236076702247451872387522388546088290187449k = 31019613858513746556266176233462864650379070310554671955689986199007361221356361736128815989480106678809272137963430923820800280374078610631771089089882153619351592434728588050285853284795554255483472955286848474793299446184220594124878818081534965835159741218233013815338595300394855159744354636541274026478456851924371621879725248093305782590590080796638483359868136648681381332610536250576568502512250581068814961097404403694071264894656697723213779631364079010490113719021172301802643377777927176399460547584115127172190000090756708138720022664973312744713394243720961199400948876916817452969615149776530401604593 % ngoal = int(hsh, 16) % n x, y = solve(k, goal, n)print((x * x + k * y *y - goal) % n) request = { 'cmd': 'verify', 'x': str(x), 'y': str(y), 'msg': msg} X = web_request('POST', 'https://crypto02.chal.ctf.westerns.tokyo', request, False)print(X)Colored by Color Scripter cs #### '수학 > 암호론 및 CTF' 카테고리의 다른 글  SECCON 2020 OnlineCTF Crypto Write-Ups (0) 2020.10.11 2020.09.30 2020.09.20 2020.09.19 2020.09.06 2020.08.16 I played DownUnderCTF as a member of Defenit, and solved all cryptography problems. rot-i  12 Ypw'zj zwufpp hwu txadjkcq dtbtyu kqkwxrbvu! Mbz cjzg kv IAJBO{ndldie_al_aqk_jjrnsxee}. Xzi utj gnn olkd qgq ftk ykaqe uei mbz ocrt qi ynlu, etrm mff'n wij bf wlny mjcj :). Colored by Color Scripter cs The problem seems to imply a variant of rotation cipher. Now, it's reasonable to guess that "Mbz cjzg kv IAJBO" is actually "The flag is DUCTF". We subtract the alphabet order of each text to find that the "amount of rotation" changes by 1 each time. I changed all letters into lowercase, cleaned up some parts of the string, and wrote the following code.  123456789101112131415 t = 'ypw zj zwufpp hwu txadjkcq dtbtyu kqkwxrbvu! mbz cjzg kv iajbo{ndldie_al_aqk_jjrnsxee}. xzi utj gnn olkd qgq ftk ykaqe uei mbz ocrt qi ynlu, etrm mffn wij bf wlny mjcj :'u = 'the flag is ductf'v = 'mbz cjzg kv iajbo' for i in range(0, 26): s = "" st = i for j in range(len(t)): if ord('a') <= ord(t[j]) <= ord('z'): cc = chr(ord('a') + (ord(t[j]) - ord('a') + st) % 26) s += cc else: s += t[j] st = st - 1 print(s)Colored by Color Scripter cs babyrsa  1234567891011 from Crypto.Util.number import bytes_to_long, getPrime flag = open('flag.txt', 'rb').read().strip()p, q = getPrime(1024), getPrime(1024)n = p*qe = 0x10001s = pow(557*p - 127*q, n - p - q, n)c = pow(bytes_to_long(flag), e, n)print(f'n = {n}')print(f's = {s}')print(f'c = {c}')Colored by Color Scripter cs The extra information we have here is$s$. Since$n-p-q = \phi(n) - 1$, we see that$s$is the modular inverse of$557p - 127q\pmod{n}$. Therefore, we may recover$557p-127q \equiv s^{-1} \pmod{n}$with Extended Euclidean algorithm. Since$557p - 127q$is between$0$and$n$, we can just recover$557p-127q$. Since we already know$n = pq$, we can just solve a quadratic equation. I did it with a binary search.  12345678910111213141516171819202122 n = 19574201286059123715221634877085223155972629451020572575626246458715199192950082143183900970133840359007922584516900405154928253156404028820410452946729670930374022025730036806358075325420793866358986719444785030579682635785758091517397518826225327945861556948820837789390500920096562699893770094581497500786817915616026940285194220703907757879335069896978124429681515117633335502362832425521219599726902327020044791308869970455616185847823063474157292399830070541968662959133724209945293515201291844650765335146840662879479678554559446535460674863857818111377905454946004143554616401168150446865964806314366426743287s = 3737620488571314497417090205346622993399153545806108327860889306394326129600175543006901543011761797780057015381834670602598536525041405700999041351402341132165944655025231947620944792759658373970849932332556577226700342906965939940429619291540238435218958655907376220308160747457826709661045146370045811481759205791264522144828795638865497066922857401596416747229446467493237762035398880278951440472613839314827303657990772981353235597563642315346949041540358444800649606802434227470946957679458305736479634459353072326033223392515898946323827442647800803732869832414039987483103532294736136051838693397106408367097c = 7000985606009752754441861235720582603834733127613290649448336518379922443691108836896703766316713029530466877153379023499681743990770084864966350162010821232666205770785101148479008355351759336287346355856788865821108805833681682634789677829987433936120195058542722765744907964994170091794684838166789470509159170062184723590372521926736663314174035152108646055156814533872908850156061945944033275433799625360972646646526892622394837096683592886825828549172814967424419459087181683325453243145295797505798955661717556202215878246001989162198550055315405304235478244266317677075034414773911739900576226293775140327580e = 65537 tt = inverse(s, n)lef = 2 ** 1023rig = 2 ** 1025while lef <= rig: mid = (lef + rig) // 2 p = mid q = (557 * p - tt) // 127 if p * q >= n: best = mid rig = mid - 1 else: lef = mid + 1p = best q = (557 * best - tt) // 127phi = (p-1) * (q-1)d = inverse(e, phi)print(long_to_bytes(pow(c, d, n)))Colored by Color Scripter cs Extra Cool Block Chaining  123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657 from Crypto.Cipher import AESfrom Crypto.Util.Padding import pad, unpadfrom Crypto.Util.strxor import strxorfrom os import urandom flag = open('./flag.txt', 'rb').read().strip()KEY = urandom(16)IV = urandom(16) def encrypt(msg, key, iv): msg = pad(msg, 16) blocks = [msg[i:i+16] for i in range(0, len(msg), 16)] out = b'' for i, block in enumerate(blocks): cipher = AES.new(key, AES.MODE_ECB) enc = cipher.encrypt(block) if i > 0: enc = strxor(enc, out[-16:]) out += enc return strxor(out, iv*(i+1)) def decrypt(ct, key, iv): blocks = [ct[i:i+16] for i in range(0, len(ct), 16)] out = b'' for i, block in enumerate(blocks): dec = strxor(block, iv) if i > 0: dec = strxor(dec, ct[(i-1)*16:i*16]) cipher = AES.new(key, AES.MODE_ECB) dec = cipher.decrypt(dec) out += dec return out flag_enc = encrypt(flag, KEY, IV).hex() print('Welcome! You get 1 block of encryption and 1 block of decryption.')print('Here is the ciphertext for some message you might like to read:', flag_enc) try: pt = bytes.fromhex(input('Enter plaintext to encrypt (hex): ')) pt = pt[:16] # only allow one block of encryption enc = encrypt(pt, KEY, IV) print(enc.hex())except: print('Invalid plaintext! :(') exit() try: ct = bytes.fromhex(input('Enter ciphertext to decrypt (hex): ')) ct = ct[:16] # only allow one block of decryption dec = decrypt(ct, KEY, IV) print(dec.hex())except: print('Invalid ciphertext! :(') exit() print('Goodbye! :)')Colored by Color Scripter cs Let's first consider what the encryption function is actually doing. Given a plaintext$P_1 P_2 \cdots P_n$, we are basically doing$C_i = E_K(P_i) \oplus C_{i-1}$for each$i$, then XORing the$IV$to all ciphertexts before returning. In other words, we are just sending$IV \oplus E_K(P_1), IV \oplus E_K(P_1) \oplus E_K(P_2)$,$\cdots , IV \oplus E_K(P_1) \oplus \cdots \oplus E_K(P_n)$. Now what we can do is ask for an encryption of a single block, and a decryption of a single block. Say we want to find$P_k$. To do so, we need to ask for a decryption of$IV \oplus E_K(P_k)$. How do we find that? Note that this is trivial for$k=1$. Assume$k \ge 2$. Now, by XORing the two consecutive results of the output, we can easily get$E_K(P_k)$. Therefore, we need to find a way to get$IV$. This looks like a time for encryption oracle. Note that if$P_1 = P_2$, our second output will be$IV \oplus E_K(P_1) \oplus E_K(P_2) = IV$. We want to use this to our benefit, but we can only ask for one block! It's okay, because we can abuse the padding. By asking for the encryption of b'\x10' * 16, we can make our padded plaintext of the form$P_1 P_1$. This enables us to get$IV$, and we can decrypt each block as we want. I did this manually, so code below is not perfect.  12345678910111213141516171819 cc = 'Here is the ciphertext for some message you might like to read: 'print(conn.recvline())T = conn.recvline()print(T)hxval = T[len(cc):-1]hxval = hxval.decode()print(len(hxval))conn.send((b'\x10' * 16).hex() + "\n")T = conn.recvline()cc = "Enter plaintext to encrypt (hex): "print(T)IV = T[len(cc):-1]print(IV)IV = IV.decode()IV = bytes.fromhex(IV)IV = IV[-16:]## change indexes to find different blocks (below)conn.send((strxor(bytes.fromhex(hxval[160:192]), strxor(bytes.fromhex(hxval[128:160]), IV))).hex() + "\n") print(conn.recvline()) ## change hex -> bytes hereColored by Color Scripter cs ceebc  123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354 #!/usr/bin/env python3from os import urandomfrom cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modesfrom cryptography.hazmat.primitives import constant_timefrom cryptography.hazmat.backends import default_backend backend = default_backend()key = urandom(32)solution_message = b'flagflagflagflag' def CBC_MAC(key, message, iv): if len(message) != 16 or len(iv) != 16: raise ValueError('Only messages/IVs of size 16 are allowed!') cipher = Cipher(algorithms.AES(key), modes.CBC(iv), backend=backend) enc = cipher.encryptor() return enc.update(message) + enc.finalize() def sign(message, iv): return CBC_MAC(key, message, iv) + iv def verify(message, signature): iv = signature[16:] computed_sig = sign(message, iv) return constant_time.bytes_eq(signature, computed_sig) sample = b'cashcashcashcash'print('Hey there, have a message {} and its signature {}!'.format( sample.decode('utf-8'), sign(sample, urandom(16)).hex() )) received_message = input('Now give me your message: ').encode('utf-8')try: received_signature = bytes.fromhex(input('Now the signature (in hex): '))except ValueError: print('Signature was not in hex!') exit() try: valid = verify(received_message, received_signature)except ValueError as e: print(e) exit() if valid: print('Signature valid!') if received_message == solution_message: print(open('flag.txt').read()) else: print('Phew! Good thing the message isn\'t {}!' .format(solution_message.decode('utf-8')))else: print('Invalid signature!') Colored by Color Scripter cs We are given a signature of an known example message, and we have to forge a signature of a desired message. The signature is given by$E_{K, IV}^{CBC} (P) || IV$which is just$E_{K}^{ECB} (P \oplus IV) || IV$. So we have$IV$,$E_{K}^{ECB}(P_{ex} \oplus IV)$, and$P_{ex}$. We want to forge a signature of$P_{flag}$. To do so, calculate$IV'$such that$P_{ex} \oplus IV = P_{flag} \oplus IV'$. This can be easily done. Then simply send$P_{K}^{ECB} (P_{ex} \oplus IV) || IV'$as a signature. It's clear that this works.  12345678910111213141516 T = conn.recvline()cc = 'Hey there, have a message cashcashcashcash and its signature 'SIG = T[len(cc) : -2]SIG = bytes.fromhex(SIG.decode())INC = SIG[0:16]IV = SIG[16:32]ms = b'cashcashcashcash'goal = "flagflagflagflag"conn.send(goal + "\n")TT = INC + bytexor(ms, bytexor(IV, goal.encode()))conn.send(TT.hex() + "\n")print(conn.recvline())conn.send(TT.hex() + "\n")print(bytes.fromhex(TT.hex()))print(conn.recvline())print(conn.recvline())Colored by Color Scripter cs Hex Shift Cipher  1234567891011121314151617181920212223242526272829303132333435363738394041 from random import shufflefrom secret import secret_msg ALPHABET = '0123456789abcdef' class Cipher: def __init__(self, key): self.key = key self.n = len(self.key) self.s = 7 def add(self, num1, num2): res = 0 for i in range(4): res += (((num1 & 1) + (num2 & 1)) % 2) << i num1 >>= 1 num2 >>= 1 return res def encrypt(self, msg): key = self.key s = self.s ciphertext = '' for m_i in msg: c_i = key[self.add(key.index(m_i), s)] ciphertext += c_i s = key.index(m_i) return ciphertext plaintext = b'The secret message is:'.hex() + secret_msg.hex() key = list(ALPHABET)shuffle(key) cipher = Cipher(key)ciphertext = cipher.encrypt(plaintext)print(ciphertext) # output:# 85677bc8302bb20f3be728f99be0002ee88bc8fdc045b80e1dd22bc8fcc0034dd809e8f77023fbc83cd02ec8fbb11cc02cdbb62837677bc8f2277eeaaaabb1188bc998087bef3bcf40683cd02eef48f44aaee805b8045453a546815639e6592c173e4994e044a9084ea4000049e1e7e9873fc90ab9e1d4437fc9836aa80423cc2198882a Colored by Color Scripter cs It's simple to see that the 'add' function is just XOR. We will brute force the key by backtracking. Basically, with the known parts of the plaintext, we have pieces of information like$key(key^{-1}(m_i) \oplus s) = c_i$. If$key^{-1}(m_i)$are known, then we can figure out$key^{-1}(c_i)$and vice-versa. If this information is contradictory to the previous assumption of our key, we can stop the backtracking. If we have no idea on$key^{-1}(m_i)$and$key^{-1}(c_i)$, we can brute force what their value will be. If we have the complete key, it's straightforward to decrypt the given output. Select those that can be cleanly decrypted. Also, now we can obviously see what the "linear algebra solution" is. Seems like a lot of work to be honest... My code seems to have a few buggy pieces, but it got the job done so I didn't bother to fix it.  12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758 def fr(x): if 0 <= x and x <= 9: return chr(ord('0') + x) return chr(ord('a') + x - 10) def cv(x): if ord('0') <= ord(x) <= ord('9'): return ord(x) - ord('0') else: return ord(x) - ord('a') + 10 def finisher(key, s): ct = 'b80e1dd22bc8fcc0034dd809e8f77023fbc83cd02ec8fbb11cc02cdbb62837677bc8f2277eeaaaabb1188bc998087bef3bcf40683cd02eef48f44aaee805b8045453a546815639e6592c173e4994e044a9084ea4000049e1e7e9873fc90ab9e1d4437fc9836aa80423cc2198882a' pt = "" for i in range(len(ct)): ot = cv(ct[i]) myidx = key.index(ot) ^ s m_i = key[myidx] pt += fr(m_i) s = myidx print(bytes.fromhex(pt)) def solve(key, s, res, cts, idx): if idx == len(res): # print("found", key, s) finisher(key, s) return p = cv(res[idx]) q = cv(cts[idx]) ## key[index(p) ^ s] == q if p in key: if key[key.index(p) ^ s] != -1 and key[key.index(p) ^ s] != q: return it = key.index(p) ^ s key[it] = q solve(key, key.index(p), res, cts, idx+1) key[it] = -1 if q in key: it = key.index(q) ^ s if key[it] != -1 and key[it] != p: return key[it] = p solve(key, key.index(p), res, cts, idx+1) key[it] = -1 for i in range(0, 16): if key[i] == -1 and key[i ^ s] == -1: key[i] = p key[i ^ s] = q solve(key, key.index(p), res, cts, idx+1) key[i] = -1 key[i ^ s] = -1 res = '54686520736563726574206d6573736167652069733a'cts = '85677bc8302bb20f3be728f99be0002ee88bc8fdc045' key = [-1] * 16s = 7solve(key, s, res, cts, 0)Colored by Color Scripter cs Cosmic Rays  12345678910111213141516171819202122232425262728293031323334 from Crypto.Util.Padding import padfrom Crypto.Cipher import AESfrom Crypto.Util.strxor import strxorfrom os import urandom flag = open('flag.txt', 'rb').read().strip()flag = flag.lstrip(b'DUCTF{').rstrip(b'}')assert len(flag) == 32 KEY = urandom(16) def encrypt(msg, key, p0, c0): msg = pad(msg, 16) blocks = [msg[i:i+16] for i in range(0, len(msg), 16)] out = b'' for p in blocks: c = strxor(p, c0) c = AES.new(key, AES.MODE_ECB).encrypt(c) out += strxor(p0, c) c0 = c p0 = p return out msg = 'If Bruce Schneier multiplies two primes, the product is prime. On a completely unrelated note, the key used to encrypt this message is ' + KEY.hex()ciphertext = encrypt(msg.encode(), KEY, flag[16:], flag[:16]) print('key = ' + KEY.hex())print('ciphertext = ' + ciphertext.hex())## ke▒ = 0▒9d0fe1920ca▒85e3851b162b8cc9▒5 ## ci▒her▒ext = ed5dd65ef5ac36e886830cf006359b300▒1▒▒7▒▒▒▒▒▒c▒▒▒▒▒a▒▒▒▒▒8▒▒▒▒▒▒▒d6▒▒▒▒▒7▒▒▒▒b▒▒▒▒2▒▒▒▒▒▒▒▒▒f▒d▒0▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒6▒▒▒▒▒▒▒▒▒▒▒▒▒f▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒d▒▒b▒▒▒a▒▒▒▒▒e▒▒c▒▒▒▒▒2▒▒▒▒▒▒▒▒▒▒0▒▒3▒0c▒▒f▒▒▒▒▒▒▒▒▒▒▒▒1▒▒7▒▒▒▒▒▒▒▒▒▒▒▒▒1e▒▒0▒0▒▒▒▒▒9▒▒c▒▒e▒▒2▒▒4▒▒▒▒7▒▒▒▒▒0▒▒▒▒▒4▒▒▒▒▒▒▒▒f▒▒▒7▒▒▒▒▒e▒b▒▒9▒▒▒▒4▒f▒▒1▒c▒▒6▒0a▒3a0e6▒d7▒975d▒1cde66e41791b▒780988c9b8329 Colored by Color Scripter cs Let's analyze the encryption process first. Given the padded message$P_1 P_2 \cdots P_n$, we see that$C_i = E_K(P_i \oplus C_{i-1})$, and the$i$th output block is$O_i = C_i \oplus P_{i-1}$. Since the key bytes and the latter parts of the output are quite known, we will start by figuring them all out. There are five unknowns in the hex data of the key and the final block (32 hex digits) of the output. We brute-force all$2^{20}$combinations. How do we verify correctness? Since$C_n = O_n \oplus P_{n-1} = E_K(P_n \oplus C_{n-1})$, we see that$O_{n-1} = C_{n-1} \oplus P_{n-2} = D_K(O_n \oplus P_{n-1}) \oplus P_n \oplus P_{n-2}$. We know partial outputs of$O_{n-1}$, so we compare the known values of$O_{n-1}$and$D_K(O_n \oplus P_{n-1}) \oplus P_n \oplus P_{n-2}$. Turns out that this is enough to uniquely determine all five unknowns. Now that we know all plaintext data, key, and the final block of output, we can use the above formula to completely decide the output value. Now we can work on finding$P_0$and$C_0$. We may find$C_2 = O_2 \oplus P_1$. Then$C_1 = D_K(C_2) \oplus P_2$,$C_0 = D_K(C_1) \oplus P_1$. Now to find$P_0$, we use$P_0 = O_1 \oplus C_1$. This solves the problem. Unfortunately, my code is a bit dirty. You can still see all the key ideas.  12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455 ## part 1 : brute force to find the key and final 32 bytes of outputdef solve(KEY): msg = 'If Bruce Schneier multiplies two primes, the product is prime. On a completely unrelated note, the key used to encrypt this message is ' + KEY msg = msg.encode() msg = pad(msg, 16) CV = ctxt[-32:] for i in range(0, 16): for j in range(0, 16): CVV = CV[0:4] + cc[i] + CV[5:18] + cc[j] + CV[19:] c_n = bytes.fromhex(CVV) c_n_1 = AES.new(bytes.fromhex(KEY), AES.MODE_ECB).decrypt(strxor(c_n, msg[-32:-16])) c_n_1 = strxor(c_n_1, msg[-16:]) c_n_1 = strxor(c_n_1, msg[-48:-32]) found_c = False tt = c_n_1.hex() for k in range(0, 32): if ctxt[-64+k] != '▒' and ctxt[-64+k] != tt[k]: found_c = True break if found_c == False: print("found!", KEY, i, j) for i in range(0, 16): for j in range(0, 16): for k in range(0, 16): KEY = key0 + cc[i] + key1 + cc[j] + key2 + cc[k] + key3 solve(KEY) ## part 2 : recover entire outputKEY = '0b9d0fe1920ca685e3851b162b8cc9e5'## change the final 32 hex data of 'ciphertext' accordingly for i in range(1, 10): if i == 1: CVV = ctxt[-32*i : ] else: CVV = ctxt[-32*i : -32*(i-1)] c_n = bytes.fromhex(CVV) print(len(c_n)) print(len(msg[-16*(i+1):-16*i])) c_n_1 = AES.new(bytes.fromhex(KEY), AES.MODE_ECB).decrypt(strxor(c_n, msg[-16*(i+1):-16*i])) if i == 1: c_n_1 = strxor(c_n_1, msg[-16*i:]) else: c_n_1 = strxor(c_n_1, msg[-16*i:-16*(i-1)]) c_n_1 = strxor(c_n_1, msg[-16*(i+2):-16*(i+1)]) ctxt = ctxt[0:-32*(i+1)] + c_n_1.hex() + ctxt[-32*i:] ## part 3 : recover answerctxt = 'ed5dd65ef5ac36e886830cf006359b300112c744b0aac58207aea28e804ec6abd6e5c397d1d4bd6f42539db06aff5de0a45d08c7dee9da217412bb6edcdab75f3096f135f702fdda23b764c1bfde3b103a1fe35ed6c0b03d2e1a8badb6c04e330c0dff963317506a110a742feea43cf2ed1e8e0f0f5e33993c8ee28200461ad755fca0ebd654e6962862f31270f414eab7c9076140feb15c1e690a83a0e60d75975d21cde66e41791b8780988c9b8329'c_2 = strxor(bytes.fromhex(ctxt[32:64]), msg[0:16])c_1 = strxor(AES.new(bytes.fromhex(KEY), AES.MODE_ECB).decrypt(c_2), msg[16:32])c_0 = strxor(AES.new(bytes.fromhex(KEY), AES.MODE_ECB).decrypt(c_1), msg[0:16])p_0 = strxor(bytes.fromhex(ctxt[0:32]), c_1)print(c_0 + p_0)Colored by Color Scripter cs impECCable  12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485 #!/usr/bin/env python3.8 import ecdsaimport randomimport hashlib Curve = ecdsa.NIST384pG = Curve.generatorn = Curve.order flag = open('flag.txt', 'r').read().strip()auth_msg = b'I know alll of your secrets!' def inv(z, n=n): return pow(z, -1, n) def gen_keypair(): d = random.randint(1, n-1) Q = d*G return d, Q def sign(msg, d): x = int(hashlib.sha1(int.to_bytes(d, 48, byteorder='big')).hexdigest(), 16) % 2**25 while True: k1 = (random.getrandbits(340) << 25) + x k2 = (random.getrandbits(340) << 25) + x r1 = (k1*G).x() r2 = (k2*G).y() if r1 != 0 or r2 != 0: break h = int(hashlib.sha384(msg).hexdigest(), 16) s = inv(k1)*(h*r1 - r2*d) % n return (r1, r2, s) def verify(msg, Q, sig): if any(x < 1 or x >= n for x in sig): return False r1, r2, s = sig h = int(hashlib.sha384(msg).hexdigest(), 16) v1 = h*r1*inv(s) v2 = r2*inv(s) x1 = (v1*G + (-v2 % n)*Q).x() return (x1 - r1) % n == 0 def menu(): m = '''Here are your options: [S]ign a message [V]erify a signature [P]ublic Key [Q]uit''' print(m) choice = input().lower() if choice == 's': print('Enter your message (hex):') msg = bytes.fromhex(input()) if len(msg) >= 8: print('Message too long!') exit() sig = sign(msg, d) print(' '.join(map(str, sig))) elif choice == 'v': print('Enter your message (hex):') msg = bytes.fromhex(input()) print('Enter your signature:') sig = [int(x) for x in input().split()] if verify(msg, Q, sig): if msg == auth_msg: print('Hello there authenticated user! Here is your flag:', flag) exit() else: print('Verified!') else: print('Invalid Signature!') elif choice == 'p': print(Q.x(), Q.y()) else: print('Oh ok then... Bye!') exit() d, Q = gen_keypair() print('Welcome to my impECCable signing service.')for _ in range(11): menu() Colored by Color Scripter cs So we have to forge a signature. Let's try that by finding the private key$d$. Let's take a look at the signature scheme.$x$, while unknown, is always fixed for each signature.$h$is a hash of the message, so we know this value too. We are also given$r_1, r_2, s$as a result of the signature. So let's take a look at the last equation$s \equiv k_1^{-1} \cdot (hr_1 - dr_2) \pmod{n}$. We already know$r_1, r_2, s, h$, so the unknowns are$k_1$and$d$. Note that$d$is also always fixed. Also, note that$k_1 = small \cdot 2^{25} + x$, where$small$is around$2^{340}$, far less than$n$. Taking this into account, we can rewrite our equation as follows: $$k_1 s \equiv hr_1 - dr_2 \pmod{n}$$ $$(small \cdot 2^{25} + x) s \equiv hr_1 - dr_2 \pmod{n}$$ $$- 2^{-25}s^{-1} r_2 d + 2^{-25}s^{-1} hr_1 \equiv small + x \cdot 2^{-25} \pmod{n}$$ This starts to look like a hidden number problem! But the$x$variable seems like a problem. It doesn't matter, since there are 10 such equations, and we can subtract two of them to get 9 (or more?) equations without$x$. Now it resolves into solving$A_i x + B_i \equiv small \pmod{n}$for some known$A_i, B_i$. I'm sure there are many ways to solve this, but the method I enjoy is to use LLL + Babai's Closest Vector Algorithm. Check the implementation below. For details, ask in comments :)  12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061 def rhexc(): t = random.randrange(0, 16) if t <= 9: return chr(ord('0') + t) if t >= 10: return chr(ord('a') + t - 10) conn.recvline()msgs = []h = []r1 = []r2 = []s = []for i in range(0, 10): conn.recvline() conn.recvline() conn.recvline() conn.recvline() conn.recvline() conn.send("S\n") conn.recvline() msg = rhexc() + rhexc() + rhexc() + rhexc() msgs.append(bytes.fromhex(msg)) hh = int(hashlib.sha384(bytes.fromhex(msg)).hexdigest(), 16) h.append(hh) conn.send(msg + "\n") T = conn.recvline().split() r1.append(int(T.decode())) r2.append(int(T.decode())) s.append(int(T.decode())) f = open("data.txt", "w") def goprint(t, s): f.write(s + " = [") for i in range(len(t)): f.write(str(t[i])) if i != len(t) - 1: f.write(", ") f.write("]") goprint(h, "h")f.write("\n")goprint(r1, "r1")f.write("\n")goprint(r2, "r2")f.write("\n")goprint(s, "s")f.write("\n")f.close()print("DONE") a = int(input())b = int(input())c = int(input()) conn.recvline()conn.recvline()conn.recvline()conn.recvline()conn.recvline()Colored by Color Scripter cs  12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364 import hashlibimport random def Babai_closest_vector(M, G, target): small = target for _ in range(1): for i in reversed(range(M.nrows())): c = ((small * G[i]) / (G[i] * G[i])).round() small -= M[i] * c return target - small def sign(msg, d): x = int(hashlib.sha1(int.to_bytes((int)(d), 48, byteorder='big')).hexdigest(), 16) % 2**25 while True: k1 = (random.getrandbits(340) << 25) + x k2 = (random.getrandbits(340) << 25) + x r1 = (k1*G).xy() r1 = (int)(r1) r2 = (k2*G).xy() r2 = (int)(r2) if r1 != 0 or r2 != 0: break r1 = (int)(r1) r2 = (int)(r2) d = (int)(d) h = int(hashlib.sha384(msg).hexdigest(), 16) s = ((int)(inverse_mod(k1, n)*(h*r1 - r2*d))) % n return (r1, r2, s) p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFFE = EllipticCurve(GF(p), [-3, 0xB3312FA7E23EE7E4988E056BE3F82D19181D9C6EFE8141120314088F5013875AC656398D8A2ED19D2A85C8EDD3EC2AEF])n = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643G = E(0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7, 0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f) M = Matrix(ZZ, 10, 10) h = [233731106310751937192664573894149799156520678027609284447669359448796436322955092470459836110792934841120158122984, 24811003402020297682803985280385324059294547276381651936828219428316450314628727089306406877936309521585868406250470, 17531688510937980482168807263229017380075873963160377208275450719528636667269895679466032893594537651522283322716674, 36047996617843056294579056584530136441992332560008111725661742840889647330983212663288175229441011598065500536724651, 11272134849660563344197668625651398585469230739650422640053316031881717853156318362750855003467577550566014131759397, 12921752283394782997197083154961040846567875585176615600282439213271258534634490795163442206145433928804694064497184, 23550485659661088231333360400047313315118168135461773986636400711616230052409480901284050511344421804458290935165361, 28496735302713412781192449440072502796901684384799422985608472930590031587697602766375490458840116389733463012282962, 8277886329528032187549731002807594806536689677333903394331300955320330584538612138873925253500020691928232999586476, 15008843981182040291480007346492436282071178418873478338505839724866567471088415321631607204728733513138973751666571]r1 = [12579209808189312915327132001276994446255172328500500695944989889711062858983163741271309992272077550124869505655381, 751327735728556148057917754296484320013694567443429719964844556884059843931387861716234725405209534287623519155458, 5371112946404190387697534646035651694165960225187891433236446686273017304702714837212569297073575677253044266881569, 331352105137929972597744016411888049220372925675806096677491319577734959841100142754252499792455324441192018313181, 7888617807239874165986404317109270600428296541740743307263264541916487472897668559357227416927514439026859501878365, 27761407228814320863611585879580881526756177120011066949498954824121650008685326439038329973891388684478285112725357, 27729723957967183136564649593980227227433733353902657860894937180736101915856597513173881921545820999053402276812094, 7364956988030862701298496872632133592704536625686657579967644830046483396779789062671782387408609718000755429523017, 37812330351370334405023218191363149079167490389863184907107776623417575732769914373075308521813667861691959707092667, 2624169019517838564518311384425555195298893854856387163253094963173848316296091845329567038393753791750586302201087]r2 = [3362705797849617878647365660985990566049333116696565173083098561696239463413527201559140422082923583525045722549763, 14145060354523589059216194767137578723898667342472872089321140612118830294396552192914912108964170720929305735415873, 29896158881994803685845271456929722092964179790028911234436030397936425532648870182944208462169501559557896423331008, 28295713529327846754165290558634286334350103809603649440117629677663367232344783261643275422157945835517134018581552, 9832320742110221576843735934134914437015558355201552824473334305115758409450236891997901207964296770834208882940712, 4863643686082209193655332852839008988042953344444353171052414901807831698624799620686397115822220675031235649084871, 2172376087957939144239533590664428657297700738539681962241559027660276255529486815550264413927604748955534219627695, 39270978975994145259001854586943865848306851245548202584185719889584304215280317078715908462808066433518126930812549, 34215025679986052889776564064620447574359162481440315252719789122933592974697130074626618888824626087631554900691781, 31458354800313627611820028529141092961133175220661883156536844963568120403379640053999048076879854251402929920752081]s = [17925111440396892739033187521377597454621431410987251376820936783063824269472232155851393375468659283009982667848669, 21853582586273412881491430100511011448648027948649700911052731210656190304335253416414001734385549707694334614279337, 19106220304410988776781688031238993716481941836023244437887325024470240140203226637806963202138139801315239237169074, 17507801404065436507268995586301878815717284846882572361951752925726533505019428040074124887812030279468394962880645, 4900819118697444872055280551871388610242725910301521205805242844252676607768719405815620318563132591329844695620900, 28480294438694078949495111903243339194235498093230054160772397254022021764455096010558032230371482379081669589216030, 25703610354773191595397225912857234424274497331129500961893925842562869928957637655440191485239263057624366236967535, 25089230670220425716164780435793841951903552099807404714502656133071929486670807789632806166532377757560189053522629, 38581148690570764731827681277745747604768765690301001244659037510529992367464486509918486337349511386868684709829501, 33302053638667654050592244700225839457979855163938098516151926858754963517053234739223403629384061080926568390283532] iv = inverse_mod(2 ** 25, n) for i in range(0, 9): M[0, i] = (((inverse_mod(s[i+1], n) * r2[i+1] - inverse_mod(s, n) * r2) * iv) % n) * n M[i+1, i] = n * nM[0, 9] = 1 Target =  * 10for i in range(0, 9): Target[i] = (((inverse_mod(s[i+1], n) * r1[i+1] * h[i+1] - inverse_mod(s, n) * r1 * h) * iv) % n) * nTarget = 2 ** 383 M = M.LLL()GG = M.gram_schmidt()Target = vector(Target)TT = Babai_closest_vector(M, GG, Target)print(TT) ## d sec = b'I know alll of your secrets!'X = sign(sec, TT)print(X)print(X)print(X)Colored by Color Scripter cs LSB || MSB Calculation Game  1234567891011121314151617181920212223242526272829303132333435363738394041424344 #!/usr/bin/env python3from os import urandomfrom random import randint print('Welcome! As you may know, guessing is one of the most important skills in CTFs and in life in general. This game is designed to train your guessing skills so that you\'ll be able to solve any CTF challenge after enough practice. Good luck!\n') class LCG: M = 937954372991277727569919570466170502903005281412586514689603 a = randint(2, M-1) c = randint(2, M-1) print(f'M = {M}') print(f'a = {a}') trunc = 20 def __init__(self, x0): self.x = x0 def next(self): self.x = (self.a * self.x + self.c) % self.M return ((self.x % 2**self.trunc) << self.trunc) + (self.x >> (self.M.bit_length() - self.trunc)) NUM_GUESSES = 5 # higher chances of winning!!rng = LCG(int(urandom(25).hex(), 16))wins = 0 for r in range(1, 24): try: num = rng.next() print('Round ' + str(r) + '. What\'s the lucky number? ') guesses = [int(guess) for guess in input().split(' ')[:NUM_GUESSES]] if any(guess == num for guess in guesses): print('Nice guess! The number was', num) wins += 1 else: print('Unlucky! The number was', num) except ValueError: print('Please enter your three numbers separated by spaces next time! e.g. 123 1337 999') exit() if wins > 10: print('YOU WIN! Your guessing skills are superb. Here\'s the flag:', open('flag.txt', 'r').read().strip())else: print('Better luck next time :(') Colored by Color Scripter cs This is yet another LCG breaking with lattices :) Basically we are given 20 LSB and 20 MSB of each number. We can such number as$2^{180} \cdot a_i + 2^{20} \cdot small + b_i$, where$a_i, b_i$are known and$small$is around$2^{160}$. We know$a$, but we do not know$c$. Denote the 0th number as$x$. Then our next numbers will be$ax+c$,$a^2x+(a+1)c$,$\cdots, a^n x + (a^{n-1} + \cdots + 1)c$. Therefore, our goal here is to solve the set of equations $$a^k x + (a^{k-1} + \cdots + 1) c \equiv 2^{180} a_k + 2^{20} \cdot small + b_k \pmod{m}$$ $$2^{-20} a^k x + 2^{-20}(a^{k-1} + \cdots + 1) c - 2^{-20}(2^{180} a_k + b_k) \equiv small \pmod{m}$$ for each$k$. This is yet another hidden number problem, so we can set up a similar procedure as the above problem. However, the bounds are kinda tight, so we have to optimize a little bit. Refer to the following code, and leave comments if there are parts you don't understand.  1234567891011121314151617181920212223 print(conn.recvline())print(conn.recvline())print(conn.recvline())print(conn.recvline()) num = []for i in range(1, 24): if i <= 12: conn.recvline() conn.send("0\n") T = conn.recvline() cc = 'Unlucky! The number was ' T = T[len(cc):-1] T = T.decode() num.append(int(T)) if i == 12: print(num) if i >= 13: conn.recvline() x = int(input()) conn.send(str(x) + " " + str(x) + "\n") conn.recvline()print(conn.recvline())print(conn.recvline())Colored by Color Scripter cs  1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859 def Babai_closest_vector(M, G, target): small = target for _ in range(1): for i in reversed(range(M.nrows())): c = ((small * G[i]) / (G[i] * G[i])).round() small -= M[i] * c return target - small n = 937954372991277727569919570466170502903005281412586514689603a = 340191373049582240414926177838297382326391494482892283959227num = [766060457621, 362859134107, 54864930141, 719063617319, 570095548300, 385643485103, 400992666914, 1095280053170, 105685083393, 701621243850, 981672150015, 408709955639] low = []upp = []for x in num: low.append(x >> 20) upp.append(x % (2 ** 20)) mult_1 = [a]mult_2 =  for i in range(1, 12): mult_1.append((a * mult_1[i-1]) % n) mult_2.append((a * mult_2[i-1] + 1) % n) M = Matrix(ZZ, 14, 14)iv = inverse_mod(2 ** 20, n) for i in range(0, 12): M[0, i] = ((int)(mult_1[i] * iv % n)) * nM[0, 12] = 1 for i in range(0, 12): M[1, i] = ((int)(mult_2[i] * iv % n)) * nM[1, 13] = 1 for i in range(0, 12): M[i+2, i] = n * n Target =  * 14for i in range(0, 12): Target[i] = (((2 ** 160) * upp[i] + iv * low[i]) % n + (2 ** 159)) * nTarget = n // 2Target = n // 2 M = M.LLL()GG = M.gram_schmidt()Target = vector(Target)TT = Babai_closest_vector(M, GG, Target)x = TTc = TT for i in range(1, 24): x = (a * x + c) % n if i <= 12: print(x % (2 ** 20) == low[i-1]) print((x >> 180) == upp[i-1]) if i >= 13: print( ((x % (2 ** 20)) << 20) + (x >> 180)) Colored by Color Scripter cs l337crypt  123456789101112131415161718192021222324252627282930 from Crypto.Util.number import getPrime, bytes_to_longfrom random import randint flag = open('flag.txt', 'rb').read().strip() p, q = getPrime(1337), getPrime(1337)n = p*q D = (1*3*3*7)^(1+3+3+7)hint = int(D*sqrt(p) + D*sqrt(q)) x = randint(1337, n)while 1337: lp = legendre_symbol(x, p) lq = legendre_symbol(x, q) if lp * lq > 0 and lp + lq < 0: break x = randint(1337, n) m = map(int, bin(bytes_to_long(flag))[2:])c = []for b in m: while 1337: r = randint(1337, n) if gcd(r, n) == 1: break c.append((pow(x, 1337 + b, n) * pow(r, 1337+1337, n)) % n) print(f'hint = {hint}', f'D = {D}', f'n = {n}', f'c = {c}', sep='\n') Colored by Color Scripter cs We assume that$p<q$in the following analysis. It's easy to see that it doesn't matter. First, the obvious part. Since$x$is a quadratic non-residue modulo$p$and$q$, we easily see that the appended value in the ciphertext is a quadratic residue modulo$n$if and only if$b=1$. This can be determined with legendre symbols if we know the factorization of$n$. The only hint here is the bounds on$D(\sqrt{p} + \sqrt{q})$. With this bound, we can easily manipulate the inequalities to get a bound on$p+q$, so eventually a bound on$q$using quadratic equations and the knowledge of$n$. Now this is a good time to use coppersmith's attack. Assume that we derived$L \le q \le R$. Set$f(x) = x + L$, set a bound$X = R - L$, then perform sage's small_roots() algorithm. However, like rbtree wrote in the coppersmith attack tutorial (Korean, check the blog) we need to carefully select$\beta$and$\epsilon$. We are working with$q$, so$\beta = 0.5$is fine. Doing some calculations, we see that$n$is around 2674 bits and$R-L$is around 600 bits. We do some math and find$\epsilon = 0.02$to be sufficient. This provides a slow, yet guaranteed solution in sage. Full code is below.  12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849 ## kth root of n, (integer rounded) using binary searchdef kthp(n, k): lef = 1 rig = 2 while rig ** k < n: rig = rig << 1 while lef <= rig: mid = (lef + rig) // 2 if mid ** k >= n: best = mid rig = mid - 1 else: lef = mid + 1 return best hint = 49380072119923666878249192613131592074839617141388577115293351423167399196342955381916004805107462372075198711094652660372962743330048982663144511583693085794844754920667876917018671057410534100394910738732436580386544489904637D = 15515568475732467854453889n = 6337195756161323755030821007055513472030952196189528055855325889406457327105118920711415415264657259037549360570438684177448730672113983949019501534456306880443480045757556693491657382839313528872206247714019569057234809244745178637139314783799705976807860096251357543835678457306901513720623505353691449216464755029227364954566851544050983088509816181294050114090489118245225264446360947782705558298586215673137402419393055466097552149369002210996708260599901728735979196557443301850639382966378922196935480476418239903494619475397129088135961432456212959427154766737697387874383258702208776154403167756944619240167487825357079536617150547060929824469887270443261440975473300946304087345552321787097829023298865763114083681766490064879774973163395320826072815425507105417077348332650202626344592023021273 ## hint / D <= sqrt(p) + sqrt(q) <= (hint + 1) / DX = (hint * hint) // (D * D) - 2 * kthp(n, 2)Y = (hint * hint + 2 * hint + 1) // (D * D) - 2 * kthp(n, 2)X = int(X)Y = int(Y)## small p + q = Ylr = (X + kthp(X * X - 4 * n, 2)) // 2sm = (Y + kthp(Y * Y - 4 * n, 2)) // 2 sm = int(sm)lr = int(lr)df = sm-lrassert df >= 0print((int)(df).bit_length()) K = Zmod(n)P. = PolynomialRing(K, implementation='NTL')f = x + lr T = f.small_roots(X = 2**600, beta=0.5, epsilon = 0.02)print(T) ## T + lr is a factor of n for x in c: if pow(x, (p-1) // 2, p) == 1 and pow(x, (q-1) // 2, q) == 1: s += '1' else: s += '0' s = int(s, 2)print(long_to_bytes(s))Colored by Color Scripter cs #### '수학 > 암호론 및 CTF' 카테고리의 다른 글  CryptoHack All Solve (3) 2020.09.30 2020.09.20 2020.09.19 2020.09.06 2020.08.16 2020.06.25 1. mathboy7 2020.10.08 09:20 ECDSA 문제에서 Lattice를 만들 때 왜 모든 식에 n이 곱해져 있는 건가요? • 2020.10.08 10:37 신고 이론적인 근거는 사실 저도 잘 모르고, 실험적으로 저렇게 하니까 잘 되는 것 같더라구요 ㅋㅋ 제 직관은 격자의 각 벡터의 마지막 entry가 d를 편하게 복구하려고 있는 거지 사실 원하는 CVP 문제의 일부라고 보기는 어려워서 (원하는거는 첫 9개의 entry가 target에 가깝도록 하는 것이니까) 그냥 첫 9개의 entry에 대한 행렬 원소 및 target vector에다가 scale을 오지게 크게 주면 잘 되겠다~ 정도인 것 같아요 쓰고 보니까 설명 참 못쓰네여 참가팀들 중 2번째로 올솔브를 찍어서 해피엔딩으로 끝냈다. 나는 Crypto 문제를 맡았고 결과적으로 5문제를 풀었다. Ciphertexts  123456789101112131415161718192021222324252627282930313233 from Crypto.Util.number import *import gmpy2from flag import flag p = getPrime(512)q = getPrime(512)r = getPrime(512)n1 = p * qn2 = p * q * r e1 = getPrime(20)e2 = int(gmpy2.next_prime(e1)) m = bytes_to_long(flag)c1 = pow(m, e1, n1)c2 = pow(m, e2, n2) print("n1 = {}".format(n1))print("n2 = {}".format(n2))print("e1 = {}".format(e1))print("e2 = {}".format(e2))print()print("c1 = {}".format(c1))print("c2 = {}".format(c2)) '''n1 = 112027309284322736696115076630869358886830492611271994068413296220031576824816689091198353617581184917157891542298780983841631012944437383240190256425846911754031739579394796766027697768621362079507428010157604918397365947923851153697186775709920404789709337797321337456802732146832010787682176518192133746223n2 = 1473529742325407185540416487537612465189869383161838138383863033575293817135218553055973325857269118219041602971813973919025686562460789946104526983373925508272707933534592189732683735440805478222783605568274241084963090744480360993656587771778757461612919160894779254758334452854066521288673310419198851991819627662981573667076225459404009857983025927477176966111790347594575351184875653395185719233949213450894170078845932168528522589013379762955294754168074749e1 = 745699e2 = 745709c1 = 23144512980313393199971544624329972186721085732480740903664101556117858633662296801717263237129746648060819811930636439097159566583505473503864453388951643914137969553861677535238877960113785606971825385842502989341317320369632728661117044930921328060672528860828028757389655254527181940980759142590884230818c2 = 546013011162734662559915184213713993843903501723233626580722400821009012692777901667117697074744918447814864397339744069644165515483680946835825703647523401795417620543127115324648561766122111899196061720746026651004752859257192521244112089034703744265008136670806656381726132870556901919053331051306216646512080226785745719900361548565919274291246327457874683359783654084480603820243148644175296922326518199664119806889995281514238365234514624096689374009704546'''Colored by Color Scripter cs$n_1, n_2$를 알고 있으니$r$을 얻을 수 있다.$m^{e_2} \pmod{r}$도 알고 있으니 여기서$m \pmod{r}$을 알 수 있다. 또한,$m^{e_1} \pmod{n_1}$과$m^{e_2} \pmod{n_1}$을 알고 있으니,$e_1d_1 + e_2d_2 = 1$인$d_1, d_2$를 찾아서$m \pmod{n_1}$도 구할 수 있다. 이제 중국인의 나머지 정리로 두 정보를 합치면 flag를 얻는다. 수식 잘 가지고 노는 문제 :)  12345678 r = n2 // n1d = inverse(e2, r - 1)mr = pow(c2, d, r)d1 = inverse(e1, e2)d2 = (e1 * d1 - 1) // e2mn1 = pow(c1, d1, n1) * inverse(pow(c2, d2, n1), n1) % n1u, v = CRT(mn1, n1, mr, r)print(long_to_bytes(u))Colored by Color Scripter cs No Pressure  1234567891011121314 from Crypto.Cipher import ARC4from hashlib import sha256from base64 import b64encodeimport zlibimport os flag = open("./flag.txt", "rb").read() nonce = os.urandom(32)while True: m = input("message: ") arc4 = ARC4.new(sha256(nonce + m.encode()).digest()) c = arc4.encrypt(zlib.compress(flag + m.encode())) print("encrypted! :", b64encode(c).decode()) cs 사실 거의 비슷한 문제가 CryptoHack에 있어서 풀이를 쓰기가 조금 애매하긴 하다 ㅋㅋ 문제 이름에서도 나오듯이 compression이 적용되었다는 것을 활용하는 문제이다. 대충 직관적으로 넣어준 메시지와 flag의 공통 prefix가 크다면 압축이 더 많이 되어 ciphertext의 길이가 작다는 것이다. flag가 'KosenCTF{' 으로 시작된다는 것은 알고 있으니, 여기에 문자를 하나씩 추가해보며 작은 ciphertext를 찾는 것을 반복하면 된다.  123456789101112131415161718192021222324252627282930313233 HOST = "misc.kosenctf.com"PORT = 10002 conn = pwnlib.tubes.remote.remote(HOST, PORT) solution = "KosenCTF{"chars = [chr(x) for x in range(32, 128)]dumb = ';' while True: p = (solution + dumb) * 5 r = conn.send(str.encode(p + "\n")) res = conn.recvline() res = res[22:-1] res = base64.b64decode(res) res = len(res) ## print(res) for c in chars: ntry = (solution + c) * 5 r = conn.send(str.encode(ntry + "\n")) r = conn.recvline() r = r[22:-1] r = base64.b64decode(r) r = len(r) ## print(r) if r < res: res = r solution += c print(solution) if c == "}": print(solution) exit() breakColored by Color Scripter cs BitCrypto  12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485 from Crypto.Util.number import *from secret import flag def legendre_symbol(x, p): a = pow(x, (p-1) // 2, p) if a == 0: return 0 elif a == 1: return 1 else: return -1 def key_gen(bits): p = getPrime(bits) q = getPrime(bits) n = p * q while True: z = getRandomRange(2, n) a, b = legendre_symbol(z, p), legendre_symbol(z, q) if a == -1 and b == -1: break return (n, z), (p, q) def enc(pubkey, m): n, z = pubkey bits = [int(b) for b in "{:b}".format(m)] c = [] for b in bits: while True: x = getRandomRange(2, n) if GCD(x, n) == 1: break c.append( ((z**b) * (x**2)) % n ) return c def dec(privkey, c): p, q = privkey m = "" for b in c: if legendre_symbol(b, p) == 1 and legendre_symbol(b, q) == 1: m += "0" else: m += "1" return int(m, 2) def main(): pubkey, privkey = key_gen(256) keyword = "yoshiking, give me ur flag" m = input("your query: ") if any([c in keyword for c in m]): print("yoshiking: forbidden!") exit() if len(m) > 8: print("yoshiking: too long!") exit() c = enc(pubkey, bytes_to_long(m.encode())) print("token to order yoshiking: ", c) c = [int(x) for x in input("your token: ")[1:-1].split(",")] if len(c) != len(set(c)): print("yoshiking: invalid!") exit() if any([x < 0 for x in c]): print("yoshiking: wow good unintended-solution!") exit() m = long_to_bytes(dec(privkey, c)) if m == keyword.encode(): print("yoshiking: hi!!!! flag!!!! here!!! wowowowowo~~~~~~") print(flag) else: print(m) print("yoshiking: ...?") if __name__ == '__main__': main() Colored by Color Scripter cs 뭔가 길게 생겼는데 코드부터 대충 해석해보자. • KeyGen: 소수$p, q$를 고르고$n = pq$라 한자.$z$는$p, q$모두에 대해 이차비잉여이다. • 이 과정에서 public key는$n, z$이며, private key는$p, q$이다. • Encryption: 메시지를 이진법으로 쓰고$0$을 위해서는 이차잉여,$1$을 위해서는 이차비잉여를 추가한다. • Decryption: 르장드르 기호를 직접 계산하여 주어진 값에서$0$,$1$을 복원한다. • 목표: 플래그 내놓으라는 저 문장이 복호화 결과가 되도록하는 암호문을 만들라는 것이다. • 단, 암호문의 각 정수는 모두 서로 달라야 하며, 음수면 안된다. • 쿼리를 날릴 수도 있는데 문제를 날로 먹을 수는 없고 쿼리의 길이에도 제한이 있다. 이러면 문제가 풀렸다. 사실 encryption을 못하는 이유는 그냥 우리가$n$도 모르고$z$도 몰라서다. 그런데 애초에$n, z$을 몰라도$\pmod{n}$에 대한 이차잉여/비이차잉여를 만드는 것은 쉽다. • 이차잉여: 그냥 제곱수를 하나 보내주면 된다. • 비이차잉여: 정수 하나를 잡고 비이차잉여라고 기도하자. 이 값에 제곱수를 곱하면 된다. • 비이차잉여를 뽑을 확률은 든든하게 높으니까 별로 기도하지 않아도 된다.  12345678910111213141516171819202122232425262728 HOST = "crypto.kosenctf.com"PORT = 13003 conn = pwnlib.tubes.remote.remote(HOST, PORT)conn.send("@\n")print(conn.recvline())print(bytes_to_long("yoshiking, give me ur flag".encode())) z = 195139091440424100361889710829481093024970143303085039083610471c = bin(z)[2:]c = str(c) q = 2res = ""for t in c: if t == '0': q += 1 res += str(q*q) + "," if t == '1': q += 1 res += str(2*q*q) + "," res = res[:-1]print(res)conn.send(res + "\n") print(conn.recvline())print(conn.recvline())Colored by Color Scripter cs PadRSA  1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859 import osimport signalfrom binascii import unhexlify, hexlifyfrom Crypto.Util.number import *from flag import flag r = os.urandom(8)nonce = 1 p = getPrime(256)q = getPrime(256)n = p * qes = set() def pad(x: bytes) -> bytes: global r, nonce y = long_to_bytes(r | nonce) + x + r nonce += 1 r = long_to_bytes(((bytes_to_long(r) << 1) ^ nonce) & (2**64 - 1)) return y def encrypt(m: bytes, e: int) -> bytes: m_ = bytes_to_long(pad(m)) return long_to_bytes(pow(m_, e, n)) MENU = """1. Encrypt the flag2. Encrypt your message3. EXIT""" signal.alarm(30)print("n: {}".format(n)) while True: print(MENU) choice = input("> ") if choice not in ["1", "2"]: break e = int(input("e: ")) if not(3 <= e <= 65537): print("[-] invalid e") break if e in es: print("[-] e already used") break if choice == "1": m = flag if choice == "2": m = unhexlify(input("m: ")) c = encrypt(m, e) print("c: {}".format(hexlify(c).decode())) es.add(e)Colored by Color Scripter cs 뭔가 패딩이 있고 정신이 나갈 것 같다. 우선 주어진 코드부터 분석해보자. •$e$를 고른 뒤, flag의 ciphertext를 얻거나 임의의 메시지에 대한 ciphertext를 얻을 수 있다. • 하지만 한 번 사용한$e$의 값은 다시 사용할 수가 없다. • 랜덤한 패딩처럼 생긴 뭔가를 쓰는데 사실 nonce의 값을 대놓고 알려줬다. • nonce 값을 안다는 것은$r$을 구하기만 하면 그 뒤의$r$값을 싹 다 구할 수 있다는 것이다. •$r$이 8 바이트인데 8 비트라고 생각해서 브루트포스하면 되는 줄 알았다 ㅋㅋ$r$을 구해보자. 사실$r$이 64 비트라는 점은 꽤 치명적인데,$r^3 < n$을 강제하기 때문이다. 그러니까 사실 빈 메시지와$e=3$을 보내고 암호화 하라고 부탁하면 얘가 알아서$r$을 갖다 바친다. 이제$r$을 알았으니 문제를 풀 수 있다.$e=4, 5, 6, 7$에 대해서 flag의 암호문을 달라고 하자. 우리는 각 암호화 과정에서 사용된$r, nonce$의 값을 전부 알고 있다. 그러니 우리가 얻은 정보는 사실상 $$( (r|nonce) \cdot 2^{l(x) + 64} + 2^{64} \cdot x + r)^e \equiv c \pmod{n}$$ 형태로 쓸 수 있다. 여기서$l(x)$는 flag의 길이이며,$x$는 flag 자체이다. 이는 결국$x$가 여러 차수 낮은$\mathbb{Z}_n$위의 다항식의 공통근임을 의미한다. 그러니 저 다항식들의 GCD를 구하면 된다.$l(x)$의 값을 모르지만 이 정도는 brute-force가 가능하다. Sage에서$\mathbb{Z}_n$위 다항식의 GCD를 지원하지 않는 것 같은데, 그냥 직접 구현하면 된다. 예전에 쓴 RSA 논문리딩에서 언급했듯이, 유클리드 호제법 과정이 망한다면 그때$n$의 약수를 하나 얻을 수 있고, 이 경우에는 문제가 바로 풀린다. 첫 부분은 Python으로, 두 번째 부분은 Sage로 작성하였다. pwntools를 살면서 처음 써봐서 통신 부분 코드가 지나치게 더럽고, 그래서 여기서는 생략했다. Part 1 :$r$값 복원하고$e=4,5,6,7$에 대한 flag의 ciphertext 얻기 아래 코드에서 kthp는 그냥 이분탐색으로$k$th root를 구하는 코드이다.  123456789101112131415161718192021222324252627282930313233343536373839 n = 13213917004013074941883923518155352500136040759518468945870343732851737037017858345555718553480688185605981252067134741952110065084206701357744511961587797rg = 0x0ae26226b16dfc3ca101a1b750f38d0f131fff3c93f04a1222586fr = kthp(rg, 3)r = long_to_bytes(r)r = r[1:]nonce = 1 print("For c4")nonce += 1r = long_to_bytes(((bytes_to_long(r) << 1) ^ nonce) & (2**64 - 1)) print(r | nonce)print(bytes_to_long(r)) print("For c5")nonce += 1r = long_to_bytes(((bytes_to_long(r) << 1) ^ nonce) & (2**64 - 1)) print(r | nonce)print(bytes_to_long(r)) print("For c6")nonce += 1r = long_to_bytes(((bytes_to_long(r) << 1) ^ nonce) & (2**64 - 1)) print(r | nonce)print(bytes_to_long(r)) print("For c7")nonce += 1r = long_to_bytes(((bytes_to_long(r) << 1) ^ nonce) & (2**64 - 1)) print(r | nonce)print(bytes_to_long(r)) c4 = 0x8043b337fd500f49ff23589ac40d6208d1ba5e8b6af341da6c63d4dc4af8944930cd5812076686450967c0b36a52b66e25a632d9b1780ca0195be15f81c7efe7c5 = 0x13d464f1f4d139c78e8bbf20eaf9b7693a931e65649db09f259ffc9a17674d72187fb10b10ad3db629c0dcb7048cf9b836972320b0018edae6c0604bf9911a59c6 = 0x0a7c1297094b925b4dcb42b001c2cfa9b0524939b4bb13048fb8e3778238e28b93c59b010ee2e45c7d7d25da69824a729141caf8c613e6dae1a8c08e153e5ae9c7 = 0x5ee21f49be33499cce3a157a1ad55d3df5bce4ad99e90f8f91929c2a7a1a8f56a99bf69789137276eaac3294fd4b91fc1ee857eeb3544cd0c4f95be49ab3abd7 cs Part 2: 다항식 GCD를 통해서 공통근 도출 (혹시 싶어서$2^{64} \cdot x$를 변수로 잡았다)  123456789101112131415161718192021222324252627282930313233343536373839404142 def GCD(f, g, n): g = g % f if g == 0: return f t = g.lc() if gcd(t, n) != 1: print(t) exit() tt = inverse_mod(Integer(t), n) g = g * tt return GCD(g, f, n) n = 13213917004013074941883923518155352500136040759518468945870343732851737037017858345555718553480688185605981252067134741952110065084206701357744511961587797K = Zmod(n)P. = PolynomialRing(K, implementation='NTL')t4 = 179b4 = 12905559065630283676t5 = 103b5 = 7364374057551015739t6 = 204b6 = 14728748115102031474t7 = 157b7 = 11010752156494511329 c4 = 0x8043b337fd500f49ff23589ac40d6208d1ba5e8b6af341da6c63d4dc4af8944930cd5812076686450967c0b36a52b66e25a632d9b1780ca0195be15f81c7efe7c5 = 0x13d464f1f4d139c78e8bbf20eaf9b7693a931e65649db09f259ffc9a17674d72187fb10b10ad3db629c0dcb7048cf9b836972320b0018edae6c0604bf9911a59c6 = 0x0a7c1297094b925b4dcb42b001c2cfa9b0524939b4bb13048fb8e3778238e28b93c59b010ee2e45c7d7d25da69824a729141caf8c613e6dae1a8c08e153e5ae9c7 = 0x5ee21f49be33499cce3a157a1ad55d3df5bce4ad99e90f8f91929c2a7a1a8f56a99bf69789137276eaac3294fd4b91fc1ee857eeb3544cd0c4f95be49ab3abd7 for i in range(2, 200): f4 = (b4 + x + 2^(8*i) * t4)^4 - c4 f5 = (b5 + x + 2^(8*i) * t5)^5 - c5 f6 = (b6 + x + 2^(8*i) * t6)^6 - c6 f7 = (b7 + x + 2^(8*i) * t7)^7 - c7 f5 = GCD(f4, f5, n) f6 = GCD(f5, f6, n) f7 = GCD(f6, f7, n) if f7.degree() >= 1: print(f7) ## x + 13213917004013074941883923518155157707200933836201561801562186284370121597148945566062799149031981069879277394219016188339927598569756720133104910406574165 Colored by Color Scripter cs Part 3: 마무리 및 flag 도출  123 res = n - 13213917004013074941883923518155157707200933836201561801562186284370121597148945566062799149031981069879277394219016188339927598569756720133104910406574165tt = (res * inverse(2 ** 64, n)) % nprint(long_to_bytes(tt))Colored by Color Scripter cs Ochazuke  12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455 from Crypto.Util.number import bytes_to_longfrom binascii import unhexlifyfrom hashlib import sha1import re EC = EllipticCurve( GF(0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff), [-3, 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b])n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551 # EC.order()Zn = Zmod(n)G = EC((0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)) def sign(private_key, message): z = Zn(bytes_to_long(message)) k = Zn(ZZ(sha1(message).hexdigest(), 16)) * private_key assert k != 0 K = ZZ(k) * G r = Zn(K) assert r != 0 s = (z + r * private_key) / k assert s != 0 return (r, s) def verify(public_key, message, signature): r, s = signature, signature if r == 0 or s == 0: return False z = Zn(bytes_to_long(message)) u1, u2 = z / s, r / s K = ZZ(u1) * G + ZZ(u2) * public_key if K == 0: return False return Zn(K) == r if __name__=="__main__": from secret import flag, d public_key = ZZ(d) * G print("public key:", public_key) your_msg = unhexlify(input("your message(hex): ")) if len(your_msg) < 10 or b"ochazuke" in your_msg: print("byebye") exit() your_sig = sign(d, your_msg) print("your signature:", your_sig) sig = input("please give me ochazuke's signature: ") r, s = map(Zn, re.compile("$(\d+), (\d+)$").findall(sig)) if verify(public_key, b"ochazuke", (r, s)): print("thx!", flag) else: print("it's not ochazuke :(") Colored by Color Scripter cs 일단 생긴 것으로 보아 ECDSA 문제인 것 같고, 요구하는 것은 주어진 메시지에 대한 서명이다. 곡선 자체가 이상한 것 같지도 않고$G$도 제대로 된 generator 임을 확인할 수 있었다. 그러니 우선 저 ECDSA처럼 생긴 서명 및 verify 과정을 한 번 살펴보자고 생각했다. 일단 sign 과정에서 랜덤성이 정확히 0mg 추가되었고 verify 과정에서 해싱 과정이 하나도 없으니 뭔가 벌써 망했다. 적당한 조건을 만족하는 메시지를 서명 받을 수 있으니, 메시지와 서명의 쌍 하나를 가지고 생각해보자. sign 알고리즘을 보고, 우리가 여기서$m, r, s$를 안다고 가정하자.$z$는 단순히 bytes_to_long을 때린 결과이므로 계산할 수 있다.$k$는 계산할 수는 없으나, 계산할 수 있는 값$kt$가 있어$k = kt \cdot pvk$로 쓸 수 있다. ($pvk$는 비밀키) 이제$s = (z + r \cdot pvk) / k$라는 식을 보면, 이는$pvk$에 대한 일차방정식이다. 그러니$pvk\$를 도출할 수 있고, 이제 서명을 알아서 잘 하면 된다.

 1234567891011121314151617181920212223242526272829303132 HOST = "crypto.kosenctf.com"PORT = 13005 conn = pwnlib.tubes.remote.remote(HOST, PORT)print(conn.recvline())conn.send("ffffffffffffffffffff\n")print(conn.recvline()) ## (98664527284046924431103876265370791373438293020179316375883642857046660842422 : 51449822108608164116773906593599196539335313713052966364410874461652593273305 : 1) msg = binascii.unhexlify("ffffffffffffffffffff")r = 98909165505886332260977490746820914928283581853841477470132641900339514121815s = 86962637426480431206806090924202825437488410614468755585865520420765819501712 z = bytes_to_long(msg)kt = int(sha1(msg).hexdigest(), 16)n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551 ## s = (z + r * pvk) / (kt * pvk)## s * kt * pvk == z + r * pvk pvk = z * inverse(s * kt - r, n) % n print(pvk)print(bytes_to_long(b'ochazuke')) fr = 98165594340872803797719590291390519389514915039788511532783877037454671871717fs = 115665584943357876566217145953115265124053121527908701836053048195862894185539 mys = "(" + str(fr)  + ", " + str(fs) + ")"conn.send(mys + "\n")print(conn.recvline())Colored by Color Scripter cs

sage에서 서명하는 부분은 자명하므로 따로 첨부하지 않았다.

#### '수학 > 암호론 및 CTF' 카테고리의 다른 글

 TokyoWesternCTF 2020 Crypto Write-Ups  (0) 2020.09.20 2020.09.19 2020.09.06 2020.08.16 2020.06.25 2020.04.02