# AIS3 EOF 2025
這裡記錄兩題crypto jeopardy題的解法，我覺得兩題都滿有趣的

## prsa
:::spoiler 題目

from Crypto.Util.number import getPrime, getRandomRange, bytes_to_long
import os


def keygen(sz):
    p = getPrime(sz // 2)
    q = getPrime(sz // 2)
    n = p * q
    phi = (p - 1) * (q - 1)
    e = 0x10001
    d = pow(e, -1, phi)
    g = 1 + n     #pq+1
    mu = pow(phi, -1, n)
    pk = (n, e, g)
    sk = (n, d, phi, mu)
    return pk, sk


def rsa_encrypt(pk, m):
    n, e, g = pk
    return pow(m, e, n)


def rsa_decrypt(sk, c):
    n, d, phi, mu = sk
    return pow(c, d, n)


def paillier_encrypt(pk, m):
    n, e, g = pk
    r = getRandomRange(1, n)
    n2 = n * n
    return (pow(g, m, n2) * pow(r, n, n2)) % n2


def paillier_decrypt(sk, c):
    n, d, phi, mu = sk
    cl = pow(c, phi, n * n)
    return ((cl - 1) // n) * mu % n


def rsa_to_paillier(pk, sk, c):
    return paillier_encrypt(pk, rsa_decrypt(sk, c))


def paillier_to_rsa(pk, sk, c):
    return rsa_encrypt(pk, paillier_decrypt(sk, c))


def pad(m, ln):
    pad_ln = ln - len(m)
    pre = pad_ln // 2
    post = pad_ln - pre
    return os.urandom(pre) + m + os.urandom(post)


def main():
    pk, sk = keygen(1024)

    flag = os.environ.get("FLAG", "flag{fake_flag}")
    m = bytes_to_long(pad(flag.encode(), 1024 // 8 - 1))
    c = rsa_encrypt(pk, m)

    print("RSA Encrypted Flag:")
    print(f"{c = }")

    for _ in range(48763):
        print("1. RSA to Paillier")
        print("2. Paillier to RSA")
        print("3. Exit")
        choice = int(input("> "))
        if choice == 1:
            c = int(input("c = "))
            c = rsa_to_paillier(pk, sk, c)
            print(f"{c = }")
        elif choice == 2:
            c = int(input("c = "))
            c = paillier_to_rsa(pk, sk, c)
            print(f"{c = }")
        elif choice == 3:
            break
        else:
            print("Invalid choice")


if __name__ == "__main__":
    main()

:::
這題目給了一個可以將RSA的密文和[paillier](https://en.wikipedia.org/wiki/Paillier_cryptosystem)的密文相互轉換的功能

其實在遇見這題之前我並不知道Paillier cryptosystem是在幹嘛的，上網查了一下發現它的加密有同態的性質
$$
E_{paillier}(m_1) \cdot E_{paillier}(m_2) = E_{paillier}(m_1 + m_2) \mod n^2
$$

另外RSA我們本來就知道(?也具有同態加密的性質
$$
E_{RSA}(m_1) \cdot E_{RSA}(m_2) = E_{RSA}(m_1 \cdot m_2) \mod n
$$
我們便可以利用這些酷酷的同態性質做出酷酷的操作，但遇到的第一個問題是我們沒有n，而求n常見的方法是利用
$$ (x \hspace{0.2cm} mod \hspace{0.2cm} n) \hspace{0.3cm} \cdot \hspace{0.3cm} (y \hspace{0.2cm} mod \hspace{0.2cm} n) \hspace{0.3cm} - \hspace{0.3cm} (xy \hspace{0.2cm} mod \hspace{0.2cm} n) $$ 得到的數會有n這個因數

因此在這裡我們使用以下式子來求n
$$n = gcd( E_{RSA}(m)^2 - E_{RSA}(m^2), E_{RSA}(m)^3 - E_{RSA}(m^3) )$$

再來就是用酷酷的同態性質做出酷酷的操作的時刻了！

$$
\begin{flalign}
\\
& E_{RSA}(m) \xrightarrow{decrypt_{RSA}} m\xrightarrow{encrypt_{paillier}} E_{paillier}(m)
\\
\\
& E_{paillier}(m) \cdot E_{paillier}(m) = E_{paillier}(m+m)\xrightarrow{decrypt_{paillier}} 2m \xrightarrow{encrypt_{RSA}} E_{RSA}(2m)
\\
\\
& E_{RSA}(2) = E_{RSA}(2m) \cdot E_{RSA}(m)^{-1}
\hspace{0.2cm} mod \hspace{0.2cm} n
\\
\\
& E_{RSA}(2) \xrightarrow{decrypt_{RSA}} 2\xrightarrow{encrypt_{paillier}} E_{paillier}(2)
\\
\\
& E_{paillier}(m) \cdot E_{paillier}(2) = E_{paillier}(m+2)\xrightarrow{decrypt_{paillier}} m+2 \xrightarrow{encrypt_{RSA}} E_{RSA}(m+2)
\\
\\
\\
\end{flalign}
$$

至此我們有了$E_{RSA}(m)$和$E_{RSA}(m+2)$就可以使用[Franklin–Reiter related-message attack](https://github.com/ashutosh1206/Crypton/blob/master/RSA-encryption/Attack-Franklin-Reiter/README.md)了！然而一般的gcd速度太慢，因此我直接用了[這篇](https://github.com/death-of-rats/CTF/tree/master/Dice2021/plagiarism)裡面提到的更快計算gcd的方法
<br/>

以下為完整的payload(抱歉變數名稱取得很爛:p )
:::spoiler solution

from pwn import *
from Crypto.Util.number import GCD

r = remote('10.102.100.30', 21337)

r.recvline()
c = eval(r.recvline()[3:])
print(f'c = {c}')
e = 65537

def ans(choice, number):
    r.sendlineafter(b'> ',str(choice).encode())
    r.sendlineafter(b'= ',str(number).encode())
    return eval(r.recvline()[3:])


p = ans(1,c) # p(m)
c_2 = ans(2,p*p) #2^e * m^e
p_2 = ans(1,c_2) #p(2m)

c_e = c # c = m^e
p_m_square = ans(1, c_e*c_e) #p(m^2)
c_e_square = ans(2, p_m_square)

p_m_cube = ans(1, c_e*c_e*c_e) #p(m^2)
c_e_cube = ans(2, p_m_cube)

n = GCD(c_e_square - c_e*c_e, c_e_cube - c_e*c_e*c_e) # get n!!
print(n)

c_2_e = c_2 * pow(c,-1,n) % n #2^e
p_2_constant = ans(1,c_2_e)
c_m_plus_2 = ans(2,p*p_2_constant)
print( c_m_plus_2)

將得到的$E_{RSA}(m)$和$E_{RSA}(m+2)$丟入更快的GCD

#!/usr/local/bin/sage -python

import binascii
from sage.all import *
import numpy as np
import sys

def franklin(n, e, delta, c1, c2):
    R = PolynomialRing(Zmod(n), 'X')
    X = R.gen()
    f1 = (X)**e - c1
    f2 = (X + delta)**e - c2
    r = gcd(f1, f2)
    co = r.coefficients()
    return -co[0]//co[1]

def hgcd(a0,a1):
    if a1.degree() <= (a0.degree()//2):
        return np.array([[1,0],[0,1]])

    m = a0.degree()//2
    X = a0.variables()[0]
    b0 = a0 // X**m
    b1 = a1 // X**m

    R = hgcd(b0,b1)
    [d,e] = (R.dot(np.array([a0,a1]).transpose())).transpose()
    ff = d % e
    m = m // 2
    g0 = e // X**m
    g1 = ff // X**m

    S = hgcd(g0,g1)
    q = d // e
    return S.dot(np.array([[0,1],[1,-q]])).dot(R)

def gcd(a0,a1):
    while True:
        print(a0.degree(), end=", ", flush=True)
        if a0 % a1 == 0:
            return a1
        if a0.degree() == a1.degree():
            a1 = a0%a1
        #print(a0.degree())
        R = hgcd(a0,a1)
        [b0,b1] = R.dot(np.array([a0,a1]).transpose()).transpose()
        if b0%b1==0:
            return b1
        c = b0 % b1
        a0 = b1
        a1 = c

def main():

    c2 = 66834555546603916608333653016401878776688916551592143035167253275230240766945198849834436542517296027329563059685319968537731358565394668263762674040400032669021171984639375055846753356780038323808260737561179083071093870132320531102232585884330838200333219121130652393831449046975064423525272905434682119641
    # RSA(m + 2)
    c1 = 74309692513998681300874362475679715926141823491721960009423424837642075969042788863193700950542384139500474947327567396515929070514702368856717418697542499654732990670025110358696551237462617652678952298208884627721522533882340862877607645156704396035860036493500429926181474230249481785324891749678676998795
    # RSA(m)
    N = 110651064591193823655829340724584396245037917386997729630017486070807378214452780923854687746762264814933821458635154464755788173581406384989704032601333549693981377505193175063386380186949929980764866648996740397660096071335187937305844353276920699700989045357881610175517571094873215069218393380692395876769
    e = 65537
    diff = 2

    flag = franklin(N, e, diff, c1, c2)

    print(flag)

    h = hex(int(flag))[2:].rstrip("L")
    h = "0" * (len(h) % 2) + h
    print (binascii.unhexlify(h))

main()

:::
:::success
AIS3{this_is_what_could_happen_to_rsa_if_it_is_an_additively_homomorphic_encryption}
:::

## zkdlp
:::spoiler 題目

from Crypto.Util.number import bytes_to_long
from hashlib import shake_128
import os, random

p = 0x2CDE2997126F706BD27498A9FA07E93F321B4932982BC455910FF694160DB5484257D0886EC66E5D7BE59ECFD16AAFF6B5BD57E600FAB97E7CF75D76A7F12BC4619A036ED8787F4508CC7C1FB35689575E007B7DC6B1EECC4B9BC2E91AA31FBE027C62BFF3E2065912591ECC1C361CEEAE75B382F1BD7D967633FD91476A3ABC4AD22CD3372C3FC40C2841B3BC70DAC11E3A6631AB3BE49AB9F748AE9093FBAB15B5457244363F444D146C0ADE84CC1AB0D0CFB2AD329483E957235EDD0085BD2F5CDAFCD77D00622A9DFCD3C0098DCB42C7EF1DEE808E8216F0F0638F51D26614B0C61352A13565098FE60146FF7E46FAEBCB75629DAF517880E36AEEE617B9F
q = (p - 1) // 2
g = 2
assert pow(g, q, p) == 1


def main():
    flag = os.environ.get("FLAG", "flag{fake_flag}")
    hflag = shake_128(flag.encode()).digest(q.bit_length() // 8) #strong hash
    x = bytes_to_long(hflag)
    y = pow(g, x, p)

    print("Do you know the flag?")
    print(f"{y = }")

    wins = 0
    while wins < 10:
        t = int(input("t = ")) % p
        if t == 0:
            print("Nope")
            return
        c = random.randrange(q)
        print(f"{c = }")
        s = int(input("s = ")) % q
        if pow(g, s, p) == t * pow(y, c, p) % p:
            print("Hmm, you probably know the flag!")
            wins += 1
        else:
            print("No, you don't know the flag :(")
            wins = 0

    print("Okay, I am finally convinced that you know the flag:")
    print(flag)


if __name__ == "__main__":
    main()

:::
這題的code非常簡潔，就是在實作[Schnorr protocol](https://cs.au.dk/~ivan/Sigma.pdf)，把q丟到[factordb](https://factordb.com/) 沒辦法分解，所以這個離散對數問題應該很安全沒辦法解，另外步驟完全是照著Schnorr protocol所以也沒有問題

這時候敏銳的我們會注意到問題必定就是出現在```c = random.randrange(q)```了！眾所解知python 的random函式庫式使用名為MT19937的pseudo random number generator(PRNG)，因此我們只要試著找出如何用randrange吐出的數字還原出原本的PRNG狀態即可預測之後的c，便可以答對這題的提問
但實作比想像中的麻煩呢:)

上網搜尋了一下關於之前有沒有過類似的題目，找到了2019年BalsnCTF的[題目](https://github.com/sasdf/ctf/tree/master/tasks/2019/BalsnCTF/crypto/unpredictable)，可以知道randrange的實作方法如下

def _randbelow_with_getrandbits(self, n):
    "Return a random int in the range [0,n).  Raises ValueError if n==0."

    getrandbits = self.getrandbits
    k = n.bit_length()  # don't use (n-1) here because n can be 1
    r = getrandbits(k)          # 0 <= r < 2**k
    while r >= n:
        r = getrandbits(k)
    return r

這題的q為2049 bits，q/(1<<2049) ~= 0.701，表示每次使用randrange時會直接輸出當前getrandbits(2049)不重抽的機率約為0.7，我花了兩三個小時試圖看懂BalsnCTF那題writeup在幹嘛，發現實在是看不懂裡面的演算法QQ於是晚上回飯店後自己再想想

getrandbits(2049)在random中的作法會是一路從LSB往MSB的方向一直取getrandbits(32)，直到有2049個bits(嗯對沒錯最後會有31個bits直接丟棄不用)

故getrandbits(2049)會需要65個getrandbits(32)，由於第65個getrandbits(32)我們只能知道1 bit，資訊太少我就乾脆不用了。因此每次getrandbits(2049)，我就取後面的2048bits，然後即可以得到連續的64個getrandbits(32)的值，還原MT19937的狀態會需要624個getrandbits(32)的值，所以我們就假設連續10次都成功的話，那我們便可以拿到640個getrandbits(32)那麼應該就可以成功了，算一下機率大概是0.7^10^ ~= 0.03，嗯還在可接受的範圍耶！

啊我就直接抄[這裡](https://github.com/icemonster/symbolic_mersenne_cracker/blob/main/main.py)的來解

結果發現沒有成功笑死嗚嗚嗚，但預測的數字會對一半，想了想會不會是條件不夠多因此沒有唯一解(z3的SAT solver只會吐出解出來的第一個解，不會給所有解)，因此我就不斷上調得到的randrange(2049)的數量，最後在17個的時候成功，但相對的17次都是直接拿當前getrandbits(2049)而不重抽的機率為0.7^17^ ~= 0.0023，但沒關係我們時間很多可以慢慢等:))

有耐心慢慢等不著急~

我們的目標是給s和t要滿足
$$
g^s \mod p \hspace{0.2cm} = \hspace{0.2cm} (t \cdot y^c) \mod p
$$
既然c可以預測了，我們就設
$$
s=1 \hspace{0.2cm}, \hspace{0.2cm} t = g \cdot \left( y^{-c} \right) \mod p
$$

以下為完整的payload
:::spoiler solution

from z3 import *
from random import Random
from itertools import count
from time import time
import logging

logging.basicConfig(format='STT> %(message)s')
logger = logging.getLogger()
logger.setLevel(logging.DEBUG)

SYMBOLIC_COUNTER = count()
p = 0x2CDE2997126F706BD27498A9FA07E93F321B4932982BC455910FF694160DB5484257D0886EC66E5D7BE59ECFD16AAFF6B5BD57E600FAB97E7CF75D76A7F12BC4619A036ED8787F4508CC7C1FB35689575E007B7DC6B1EECC4B9BC2E91AA31FBE027C62BFF3E2065912591ECC1C361CEEAE75B382F1BD7D967633FD91476A3ABC4AD22CD3372C3FC40C2841B3BC70DAC11E3A6631AB3BE49AB9F748AE9093FBAB15B5457244363F444D146C0ADE84CC1AB0D0CFB2AD329483E957235EDD0085BD2F5CDAFCD77D00622A9DFCD3C0098DCB42C7EF1DEE808E8216F0F0638F51D26614B0C61352A13565098FE60146FF7E46FAEBCB75629DAF517880E36AEEE617B9F
q = (p - 1) // 2

class Untwister:
    def __init__(self):
        name = next(SYMBOLIC_COUNTER)
        self.MT = [BitVec(f'MT_{i}_{name}', 32) for i in range(624)]
        self.index = 0
        self.solver = Solver()

    #This particular method was adapted from https://www.schutzwerk.com/en/43/posts/attacking_a_random_number_generator/
    def symbolic_untamper(self, solver, y):
        name = next(SYMBOLIC_COUNTER)

        y1 = BitVec(f'y1_{name}', 32)
        y2 = BitVec(f'y2_{name}' , 32)
        y3 = BitVec(f'y3_{name}', 32)
        y4 = BitVec(f'y4_{name}', 32)

        equations = [
            y2 == y1 ^ (LShR(y1, 11)),
            y3 == y2 ^ ((y2 << 7) & 0x9D2C5680),
            y4 == y3 ^ ((y3 << 15) & 0xEFC60000),
            y == y4 ^ (LShR(y4, 18))
        ]

        solver.add(equations)
        return y1

    def symbolic_twist(self, MT, n=624, upper_mask=0x80000000, lower_mask=0x7FFFFFFF, a=0x9908B0DF, m=397):
        '''
            This method models MT19937 function as a Z3 program
        '''
        MT = [i for i in MT] #Just a shallow copy of the state

        for i in range(n):
            x = (MT[i] & upper_mask) + (MT[(i+1) % n] & lower_mask)
            xA = LShR(x, 1)
            xB = If(x & 1 == 0, xA, xA ^ a) #Possible Z3 optimization here by declaring auxiliary symbolic variables
            MT[i] = MT[(i + m) % n] ^ xB

        return MT

    def get_symbolic(self, guess):
        name = next(SYMBOLIC_COUNTER)
        ERROR = 'Must pass a string like "?1100???1001000??0?100?10??10010" where ? represents an unknown bit'

        assert type(guess) == str, ERROR
        assert all(map(lambda x: x in '01?', guess)), ERROR
        assert len(guess) <= 32, "One 32-bit number at a time please"
        guess = guess.zfill(32)

        self.symbolic_guess = BitVec(f'symbolic_guess_{name}', 32)
        guess = guess[::-1]

        for i, bit in enumerate(guess):
            if bit != '?':
                self.solver.add(Extract(i, i, self.symbolic_guess) == bit)

        return self.symbolic_guess


    def submit(self, guess):
        '''
            You need 624 numbers to completely clone the state.
                You can input less than that though and this will give you the best guess for the state
        '''
        if self.index >= 624:
            name = next(SYMBOLIC_COUNTER)
            next_mt = self.symbolic_twist(self.MT)
            self.MT = [BitVec(f'MT_{i}_{name}', 32) for i in range(624)]
            for i in range(624):
                self.solver.add(self.MT[i] == next_mt[i])
            self.index = 0

        symbolic_guess = self.get_symbolic(guess)
        symbolic_guess = self.symbolic_untamper(self.solver, symbolic_guess)
        self.solver.add(self.MT[self.index] == symbolic_guess)
        self.index += 1

    def get_random(self):
        '''
            This will give you a random.Random() instance with the cloned state.
        '''
        logger.debug('Solving...')
        start = time()
        self.solver.check()
        model = self.solver.model()
        end = time()
        logger.debug(f'Solved! (in {round(end-start,3)}s)')

        #Compute best guess for state
        state = list(map(lambda x: model[x].as_long(), self.MT))
        result_state = (3, tuple(state+[self.index]), None)
        rr = Random()
        rr.setstate(result_state)
        return rr

#以上只是用來還原MT19937的工具而已

from pwn import remote

p = 0x2CDE2997126F706BD27498A9FA07E93F321B4932982BC455910FF694160DB5484257D0886EC66E5D7BE59ECFD16AAFF6B5BD57E600FAB97E7CF75D76A7F12BC4619A036ED8787F4508CC7C1FB35689575E007B7DC6B1EECC4B9BC2E91AA31FBE027C62BFF3E2065912591ECC1C361CEEAE75B382F1BD7D967633FD91476A3ABC4AD22CD3372C3FC40C2841B3BC70DAC11E3A6631AB3BE49AB9F748AE9093FBAB15B5457244363F444D146C0ADE84CC1AB0D0CFB2AD329483E957235EDD0085BD2F5CDAFCD77D00622A9DFCD3C0098DCB42C7EF1DEE808E8216F0F0638F51D26614B0C61352A13565098FE60146FF7E46FAEBCB75629DAF517880E36AEEE617B9F
q = (p - 1) // 2
g = 2

r = remote('10.102.100.30', 11337)
r.recvline()
xx = r.recvline()
print(xx)
y = int(xx[3:].strip().decode())
print(y)

record = []

def split_into_32bit_chunks(num):
    chunks = []
    for _ in range(64):
        chunks.append(num & 0xFFFFFFFF)  # 取最低 32 位
        num >>= 32  # 右移 32 位，繼續取下一組
    chunks.append('?'*32)
    return chunks

def test():
    record = []
    for _ in range(17):
        r.sendlineafter(b't = ',str(1).encode())
        c = int(r.recvline()[3:].strip().decode())
        chunks = split_into_32bit_chunks(c)
        record.extend(chunks)

        r.sendlineafter(b's = ',str(1).encode())
        r.recvline()
    assert len(record) == 65*17
    return record

for _ in range(10000):
    record = test()
    #print(record)
    ut = Untwister()
    for i in range(65*17):
        if i % 65 !=64:
            ut.submit(bin(record[i])[2:])
        else:
            ut.submit(record[i])
    try:
        r2 = ut.get_random()
        for _ in range(10):
            c = r2.randrange(q)
            s = 1
            # g == t * y^c mod p
            tmp = pow(y,c,p)
            t = g * pow(tmp,-1,p) % p
        
            print(c,s,t)
            r.sendlineafter(b't = ',str(t).encode())
            print(r.recvline())

            r.sendlineafter(b's = ',str(s).encode())
            print(r.recvline())
        print(r.recvline().decode())
        print(r.recvline().decode())
    except:
        pass

:::

:::success
AIS3{if_you_know_the_flag......?_you_know_the_flag!_btw,你願意和我玩一輩子ZKP嗎🥺}
:::