SUCTF Crypto wp

SU_signin

加密代码：

from Crypto.Util.number import *
from secret import flag

bit_length = len(flag) * 8

p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
K = GF(p)
E = EllipticCurve(K, (0, 4))
o = 793479390729215512516507951283169066088130679960393952059283337873017453583023682367384822284289
n1, n2 = 859267, 52437899

while(1):
    G1, G2 = E.random_element(), E.random_element()
    if(G1.order() == o and G2.order() == o):
        P1, P2 = (o//n1)*G1, (o//n2)*G2
        break

cs = [(randrange(0, o) * P1 + randrange(0, o) * G2).xy() if i == "1" else (randrange(0, o) * G1 + randrange(0, o) * P2).xy() for i in bin(bytes_to_long(flag))[2:].zfill(bit_length)]
print(cs)

cs的数据输出还蛮长的，这边就不放了

这个其实一眼考点就是配对了，在sage里面对应是weil_pairing

我们只需要知道如下的性质

这边只给了我们cs，很明显就是遍历的思路，遍历到符合条件的，就是拼接’1’，不符合条件的就拼接’0’，那么这个判断的依据是什么呢？

先定义如下（先假定说都是第一组，分别结果为0或者1的情况

对于’1’的结果，有 $a_1 * P_1 + b_1 * G_2=t_1$

对于’0’的结果，有 $\alpha_1 * G_1 + \beta_1 * P_2=T_1$

我们先拿两组都是’1’对应的生成结果的点来做一下配对，阶肯定都是o

\begin{array}{l} e(a_1 * P_1 + b_1 * G_2, a_2 * P_1 + b_2 * G_2)\\ e(a_1 * P_1, a_2 * P_1 + b_2 * G_2) \cdot e(b_1 * G_2, a_2 * P_1 + b_2 * G_2)\\ e(a_1 * P_1, a_2 * P_1) \cdot e(a_1 * P_1, b_2 * G_2) \cdot e(b_1 * G_2, a_2 * P_1) \cdot e(b_1 * G_2, b_2 * G_2) \end{array}

然后因为有 $e(P, P)=1$ 和 $e(P,G) = e(G, P) ^ {-1}$ （这边是在模o下的逆元），所以可以继续化简

\begin{array}{l} e(a_1 * P_1, a_2 * P_1) \cdot e(a_1 * P_1, b_2 * G_2) \cdot e(b_1 * G_2, a_2 * P_1) \cdot e(b_1 * G_2, b_2 * G_2)\\ e(P_1, P_1)^{a_1 * a_2} \cdot e(P_1, G_2) ^ {a_1 * b_2} \cdot e(G_2, P_1) ^ {b_1 * a_2}\cdot e(G_2, G_2) ^ {b_1 * b_2}\\ e(P_1, G_2) ^ {a_1 * b_2} \cdot e(G_2, P_1) ^ {b_1 * a_2}\\ e(P_1, G_2) ^ {a_1 * b_2 - b_1 * a_2} \end{array}

另外，我们知道有 $P1 = \frac{o}{n_1} * G_1$ 和 $P2 = \frac{o}{n_2} * G_2$

我们将点P都化成点G，代入有

\begin{array}{l} e(P_1, G_2) ^ {a_1 * b_2 - b_1 * a_2} \\ e(\frac{o}{n_1} * G_1, G_2) ^ {a_1 * b_2 - b_1 * a_2} \\ e(G_1, G_2) ^ {(a_1 * b_2 - b_1 * a_2) * \frac{o}{n_1}} \end{array}

因为是在阶o下运算的，有 $e(G_1, G_2) ^ {o} = 1$

所以我们遍历每个结果，只要满足配对后的值的n1次幂的值是1，那么这两组就都是’1’，反之就是’0’，至于另外一种情况大家可以自行验证，是不能有这个性质的

exp：

from Crypto.Util.number import *

p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
K = GF(p)
E = EllipticCurve(K, (0, 4))
o = 793479390729215512516507951283169066088130679960393952059283337873017453583023682367384822284289
n1, n2 = 859267, 52437899

t = 
test = E(t[1])

flag = ''
for i in t:
    i = E(i)
    if test.weil_pairing(i, o) ^ n1 % p == 1:
        flag += '1'
    else:
        flag += '0'

print(long_to_bytes(int(flag, 2))) #b'SUCTF{We1come__T0__SUCTF__2025}'

SU_rsa

加密代码：

from Crypto.Util.number import *
from hashlib import sha256
flag = open("flag.txt").read()
p = getPrime(512)
q = getPrime(512)
e = getPrime(256)
n = p*q
d = inverse(e,(p-1)*(q-1))
d_m = ((d >> 512) << 512)
print("d_m = ",d_m)
print("n = ",n)
print("e = ",e)

assert flag[6:-1] == sha256(str(p).encode()).hexdigest()[:32]
# d_m =  54846367460362174332079522877510670032871200032162046677317492493462931044216323394426650814743565762481796045534803612751698364585822047676578654787832771646295054609274740117061370718708622855577527177104905114099420613343527343145928755498638387667064228376160623881856439218281811203793522182599504560128
# n =  102371500687797342407596664857291734254917985018214775746292433509077140372871717687125679767929573899320192533126974567980143105445007878861163511159294802350697707435107548927953839625147773016776671583898492755338444338394630801056367836711191009369960379855825277626760709076218114602209903833128735441623
# e =  112238903025225752449505695131644979150784442753977451850362059850426421356123

是一个已知d高位的攻击，但是这个因为未知的位数达到了总体的一半，所以肯定也不能用xyctf的那个板子来套

dh为d_m >> 512

很明显有如下的思路

\begin{array}{l} e * d = 1 + k* phi\\ e * (2 ^ {512} * dh + dl) = 1 + k * phi\\ \end{array}

这边的k其实是可以求的，这个下面展开再说

这边的dl和phi 都是未知的，而且数量级也比较大，先想办法把他们的数量级降低看能不能打二元copper

2 ^ {512} * e * dh + e * dl = 1 + k * (n - s + 1)

这边的s为p+q的值，也有513比特左右了

这时候，e * dl的数量级是七百多比特，所以等式左边整除一下n就可以把e * dl忽略不计了，等式右边整除一下n差不多只剩k了

我们可以看看这样求出来的k和预期的值差距是多少，这边本地测了几次，会发现只要对得到的值+1就得到了真正的k值

也就是

1	k = 2 ^ 512 * e * dh // n + 1

那么k知道了，就只有dl和s是未知的，直接打copper显然是不行的，因为n只有1024比特，要打五百多比特还是太勉强了

所以我们得想办法把s和dl降低一下数量级

注意到在等式两边同时模e可以消掉dl，同时可以得到s mod e的值，也就是

1 + k * (n - s + 1) \equiv 0\ (mod\ e)

即可得到

\begin{array}{l} sl \equiv s\ (mod\ e)\\ sl + k_1 * e = s \end{array}

dh =  54846367460362174332079522877510670032871200032162046677317492493462931044216323394426650814743565762481796045534803612751698364585822047676578654787832771646295054609274740117061370718708622855577527177104905114099420613343527343145928755498638387667064228376160623881856439218281811203793522182599504560128
n =  102371500687797342407596664857291734254917985018214775746292433509077140372871717687125679767929573899320192533126974567980143105445007878861163511159294802350697707435107548927953839625147773016776671583898492755338444338394630801056367836711191009369960379855825277626760709076218114602209903833128735441623
e =  112238903025225752449505695131644979150784442753977451850362059850426421356123



dh = dh >> 512
k = 2 ^ 512 * e * dh // n + 1

R.<sl> = Zmod(e)[]
f1 = 1 + k * (n - sl + 1)
f1.roots()

同理，在模k下，我们可以得到dl mod k的值

\begin{array}{l} 2 ^ {512} * e * dh + e * dl - 1 \equiv 0 \ (mod\ k)\\ dll + k_2 * k = dl \end{array}

R.<dll> = Zmod(k)[]
sl = 12677855676357332067422893881017592870238023521825087602333755713600088218484
f2 = 2 ^ 512 * e * dh + e * dll - 1
f2.roots(multiplicities=False)  #用roots求要这样，也可以不用，直接算逆元

本地测试的多，k1和k2只有258比特左右，这样拿去打二元可能性大一些，但是实际上测试还是打不出来，当时就卡在这里

这边的话需要用到一个技巧，我们已知了s的低位，也就是p+q的低位，那么我们就可以得到p或者是q对应的低位，推导也很简单

\begin{array}{l} sl \equiv s\ (mod\ e)\\ sl \equiv p+q\ (mod\ e)\\ sl * p \equiv p ^ 2 + n \ (mod \ e)\\ p ^ 2 - sl * p + n\equiv 0 \ (mod \ e)\\ pl ^ 2 - sl * pl + n\equiv 0 \ (mod \ e)\\ pl + k_3 * e = p \end{array}

1
2
3

R.<pl> = Zmod(e)[]
f3 = pl ^ 2 - sl * pl + n
f3.roots()

解得pl之后，直接打p低位就行了

本地测试的话最极限打p低位的话知道 $k_3$ 低267位可以用copper打出来（epsilon=0.02，因为0.01太慢了，不适合多线程）

保险起见我们爆个十四位

注意这边是拿关于p的等式去打copper，不是直接拿p低位去打copper，这样是打不出来的

开个16线程，大概跑个十分钟就能出

exp：

from multiprocessing import Pool
from tqdm import trange
import sys


def attack(range_):
    n =  102371500687797342407596664857291734254917985018214775746292433509077140372871717687125679767929573899320192533126974567980143105445007878861163511159294802350697707435107548927953839625147773016776671583898492755338444338394630801056367836711191009369960379855825277626760709076218114602209903833128735441623
    e =  112238903025225752449505695131644979150784442753977451850362059850426421356123
    res = [(68696458789499884692247635135148296989030879976312427541751994081257774325189,1),(56220299912083199824680953877514275031991586299490111910943821482768735249418,1)]
    R.<k3h> = Zmod(n)[]
    low = range_[0]
    high = range_[1]
    for pl in res:
        for i in trange(low, high):
            bits = int(pl[0]).bit_length()
            f = (2 ^ 14 * k3h + i) * e + pl[0]
            root =  f.monic().small_roots(X = 2 ^ (512 - bits - 14), beta = 0.49, epsilon = 0.02)
            if root:
                p = (2 ^ 14 * int(root[0]) + i) * e + pl[0]
                assert n % p == 0
                print(p)
                sys.exit()


if __name__ == "__main__":   
    ranges = [(i, i + 1024) for i in range(0, 2 ^ 14, 1024)]
    with Pool(16) as pool:    #2 ^ 14 // 16 = 1024
        try: 
            list(pool.imap(attack, ranges))
        except:
            pool.terminate()  # 强制终止线程池
            pool.join()  # 等待线程清理