宁波市网络安全大赛2022-Crypto-WP

n_n

ucnd fclsmn.rmjy.irdapc jdsncm zpmscjdp, almph_mn_yniz
ucnd hpfcpm jdsncm uyvz
jdsncm zdsl2

s = zpmscjdp(1024)
x = zpmscjdp(1024)
i = s * x
p = 0g130u7u3
k = zdsl2.jiwpcm(p, (s-1)*(x-1))
jiws_x = zdsl2.jiwpcm(s, x)
jiwx_s = zdsl2.jiwpcm(x, s)

d = almph_mn_yniz(uyvz)
f = zdsl2.snbdnk(d, p, i)

scjim(p)
scjim(k)
scjim(jiws_x)
scjim(jiwx_s)
scjim(f)

一看就是字母替换了，拿到quipqiup - cryptoquip and cryptogram solver上分析一下就有了大致意思了，再稍微加点限制就行了。

出来是这样的：

from crypto.util.number import getprime, bytes_to_long
from secret import flag
import gmpy2

p = getprime(1024)
q = getprime(1024)
n = p * q
e = 0x130f7f3
d = gmpy2.invert(e, (p - 1) * (q - 1))
invp_q = gmpy2.invert(p, q)
invq_p = gmpy2.invert(q, p)
m = bytes_to_long(flag)
c = gmpy2.powmod(m, e, n)
print(e)
print(d)
print(invp_q)
print(invq_p)
print(c)

一道与长安“战疫”相同的题目（没写，还不会）。

为了方面书写，这里令$s = invp\_q,t = invq\_p$
$$
\begin{cases} s*p = 1\ mod\ q\\ t*q = 1\ mod\ p \end{cases}
$$
改写成
$$
\begin{cases} s*p = 1+k_1*q\\ t*q = 1+k_2*p \end{cases}
$$
两式相减
$$
(s+k_2)*p = (k_1+t)*q
$$
容易知道p≠q，所以
$$
\begin{cases} p = k_1 + t\\ q = k_2 + s \end{cases}
$$
将 p,q 代入$s*p = 1+k_1*q$，得
$$
s*t = 1 + k_1*k_2
$$
得出
$$
k_1 = \dfrac{s*t-1}{k_2}
$$
根据
$$
φ(n) = (p-1)*(q-1)
$$
有方程
$$
(t-1)*k_2^2+(2*s*t-t-s-φ(n))*k_2+(s*t-1)*(s-1)=0
$$
而$k = \dfrac{e*d-1}{φ(n)}$，$d<φ(n)$，所以$k<e$，于是将$k_2$的取值约束到$(0,e)$上？（这k能一样吗？）

通过枚举k，解方程求出$k_2$。

from gmpy2 import *
from Crypto.Util.number import *
from z3 import *

e = 19986419
d = 3246030980112569716252525489178402976566547966168594693884910274513154299462041341004375201921016318938426026345098668299377474330375073434720935772407207944175167323817898036516011079576927822972280584550642421759163857196487310343842151887753901290056007928776238985151298531470667875043069631236869106891057021962478109360022955201129953336276429238305672598460147562806963064866859947227329083491706302615233310732434276569920504055705370558759864687603230396302816302264528911561986103345422868194300484993924394687653074699941027740263298870609889050004072341364150017277319759241334188164360195703910784166355
s = 23389236347134283235213306702183810016424721867486963556461081084876520502820941836694411695676757754191365637169094291954507615676165999068189562213594619012687252636744435260033076208286475321060918985189871377901228212667433573382718485160649112811594950994116619369682212010587535385364596418447338709974
t = 102920556609507191536438498232122774923059359709189772008951429751731499708926283579532737890030392620334257693429608011647339365489651578950937878926965514185822024062626226427621775843089345409431424163821245825850075741313035783453477904427927137045546100973267423868918950101645341426259141920145517101346
c = 1553892238198363827492950017785469649883078335860404183601470514633985702148771439291915519584864956768837128975747502834867950051639396112333353729920983641277214334076161962538797900388907160490701194265684200572530520821773449401826082542234651817152190240489004982304794568360099499384170323027423530546020874791949260720440971235829841009999271630682762487975448340845503303511707467319967171026472363519627299488034799105120005884793797012235913877429590605758066993126024240880065915024533204819606519268788794771634158963247834960191894770256479582799808670787421459015846778168822826961225790849202125973374
kphi = e*d-1

for k in range(2,e):
    if kphi%k == 0:
        phi = kphi//k
        x = Int('x')
        solve = Solver()
        solve.add(x*phi == (s*t-1+(t-1)*x)*(x+s-1))
        if solve.check() == sat:
            result = solve.model()
            k2 = int(str(result[x]))
            k1 = (s*t-1)//k2
            p = k1 + t
            q = k2 + s
            print(long_to_bytes(pow(c,d,p*q)))
            print(long_to_bytes(pow(c, d, p)))
            print(long_to_bytes(pow(c, d, q)))

#flag{e171892fdcccfc5b0c390806b975a72c}

PRNG

from Crypto.Util.number import *
import random
p0 = 115792089210356248762697446949407573530086143415290314195533631308867097853951
a = 115792089210356248762697446949407573530086143415290314195533631308867097853948
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291
E=EllipticCurve(GF(p0),[a,b])
P0=E(0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296,0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)
n=0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
rlist1=[]
for j in range(624):
    rlist1.append(random.getrandbits(32))
print(rlist1)
s0=random.getrandbits(256)
RMT=random.getrandbits(256)
s0=s0%n
p=getPrime(256)
q=getPrime(256)
assert p!=q
x0=int(inverse_mod(q,n))
e1=(p*x0)%n
#print("e1",hex(e1))
def GenRNG():
    si=s0
    p_point=p*P0
    q_point=q*P0
    Random_i=0
    for j in range(8):
        si=int((p_point*si)[0])
        ri=int((q_point*si)[0])
        Random_i=ri&(0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff)
    r_point=si*p_point
    return hex(Random_i),r_point
rand,point=GenRNG()
print(int(rand,16)^^RMT)

def genPrime():
    while True:
        a = random.getrandbits(256)
        b = random.getrandbits(256)
        if b % 3 == 0:
            continue
        p = int(a ** 2 + 3 * b ** 2)
        if p.bit_length() == 512 and p % 3 == 1 and isPrime(p):
            return p
def add(P, Q, mod):
    m, n = P
    p, q = Q
    if p is None:
        return P
    if m is None:
        return Q
    if n is None and q is None:
        x = m * p % mod
        y = (m + p) % mod
        return (x, y)
    if n is None and q is not None:
        m, n, p, q = p, q, m, n
    if q is None:
        if (n + p) % mod != 0:
            x = (m * p + 2) * inverse(n + p, mod) % mod
            y = (m + n * p) * inverse(n + p, mod) % mod
            return (x, y)
        elif (m - n ** 2) % mod != 0:
            x = (m * p + 2) * inverse(m - n ** 2, mod) % mod
            return (x, None)
        else:
            return (None, None)
    else:
        if (m + p + n * q) % mod != 0:
            x = (m * p + (n + q) * 2) * inverse(m + p + n * q, mod) % mod
            y = (n * p + m * q + 2) * inverse(m + p + n * q, mod) % mod
            return (x, y)
        elif (n * p + m * q + 2) % mod != 0:
            x = (m * p + (n + q) * 2) * inverse(n * p + m * q + r, mod) % mod
            return (x, None)
        else:
            return (None, None)
def power(P, a, mod):
    res = (None, None)
    t = P
    while a > 0:
        if a % 2:
            res = add(res, t, mod)
        t = add(t, t, mod)
        a >>= 1
    return res
def random_pad(msg, ln):
    pad = bytes([random.getrandbits(8) for _ in range(ln - len(msg))])
    return msg + pad

p, q = genPrime(), genPrime()
N = p * q
phi = (p ** 2 + p + 1) * (q ** 2 + q + 1)
print(f"N: {N}")
d = getPrime(400)
e2 = inverse(d, phi)
k = (e * d - 1)/phi
print("e2:",e2)
to_enc=long_to_bytes(e1)
ln = len(to_enc)
print(f"Length: {ln}")
pt1, pt2 = random_pad(to_enc[: ln // 2], 127), random_pad(to_enc[ln // 2 :], 127)
M = (bytes_to_long(pt1), bytes_to_long(pt2))
E = power(M, e2, N)
print(f"E: {E}")

flag=b"flag{**********}"
m=bytes_to_long(flag)
c=m^^int(point[0])
print("c:",c)

没有头绪。应该可以通过给出的随机数分别预测$s_0,RMT$，每次预测32bit，共8次，但是后面不知道怎么下手了。

不过这道题貌似是一个原题，只是稍微改了一下。可以参考pbctf 2021 Writeup | y011d4.log。