[WMCTF 2023] crypto

 

似乎退步不了，这个比赛基本不会了，就作了两个简单题。

SIGNIN

第1个是签到题

from Crypto.Util.number import *
from random import randrange
from secret import flagdef pr(msg):print(msg)pr(br"""....''''''....                        .`",:;;II;II;;;;:,"^'.                    '"IlllI;;;;;;;;;;;;;Il!!l;^.                 `l><>!!!!!!!!iiiii!!!!!!!!i><!".               ':>?]__++~~~~~<<<<<<<<<<<<<<<<~~+__i".            .:i+}{]?-__+++~~~~~~<<<<<~~~~~~+_-?[\1_!^           .;<_}\{]-_++~<<<<<<<<<<<<<<<<<<<~+-?]\|]+<^          .!-{t|[?-}(|((){_<<<<<<<<<_}1)))1}??]{t|]_"          !)nf}]-?/\){]]]_<<<<<<<<<_]]}}{\/?-][)vf?`          '!tX/}]--<]{\Un[~~<<<<<~~<~-11Yz)<--?[{vv[".         .<{xJt}]?!ibm0%&Ci><<<<<<<<!0kJW%w+:-?[{uu)},         !1fLf}]_::xmqQj["I~<<<<<<>"(ZqOu{I^<?[{cc)[`         `}|x\}]_+<!<+~<<__~<<<<<<+_<<_+<><++-[1j/(>          !\j/{]-++___--_+~~<i;I>~~~__-______?}(jf}`          ;~(|}?_++++~~++~+]-++]?+++~~~~+++-[1/]>^           ;\([?__+_-?]?-_-----__-]?-_+++-]{/].             l||}?__/rjffcCQQQQQLUxffjf}+-]1\?'              ,[\)[?}}-__[/nzXXvj)?__]{??}((>.               .I[|(1{]_+~~~<~~<<<~+_[}1(1+^                 ,~{|\)}]_++++++-?}1)1?!`                   ."!_]{11))1{}]-+i:'                      .`^","^`'.                           
""".decode())def gen_prime(bit):while 1:P = getPrime(bit)if len(bin(P)) - 2 == bit:return Ppq_bit = 512
offset = 16P,Q = [gen_prime(pq_bit) for i in range(2)]
N = P * Q
gift = int(bin(P ^ (Q >> offset))[2+offset:],2)
pr(N)
pr(gift)inpP = int(input())
if inpP != P:pr(b"you lose!")exit()secret = randrange(0,P)
bs = [randrange(0,P) for _ in range(38)]results = [(bi * secret) % P for bi in bs]
rs = [ri & (2 ** offset - 1)  for ri in results]pr(bs)
pr(rs)
inpsecret = int(input())
if inpsecret == secret:pr(flag)

两部分第一部分是个爆破p^(q>>16)

gift = int(bin(P ^ (Q >> offset))[2+offset:],2)

第二部分是一个hnp问题，与常见的不同，原来是 B = A*x + b这里给的是A和b求B，这题本来不会，但前天有一个比赛也是这个题，也不会，广大姥要了WP，根据那个WP写一下就行了。

第一部分

from pwn import *io = remote('1.13.101.243', 26140 )
context.log_level = 'debug'for _ in range(24):io.recvline()def fac(x,tp,tq):global p if p != 0:returnif len(x) == 0:returnif tp*tq>N:returnif N%(tp+1)==0:print(tp+1)p = tp+1returnv = x[0]r = x[1:]l = len(r)if (tp+(1<<(l+1)))*(tq+(1<<(l+17)))<N:return      if v == '0':fac(r, tp, tq)fac(r, tp+(1<<l), tq+(1<<(l+16)))else:fac(r, tp+(1<<l), tq)fac(r, tp, tq+(1<<(l+16)))N = int(io.recvline())
print(N)
gift = int(io.recvline())
x = bin(gift)[2:].zfill(512-16)
print(x[:50])p = 0
#p前15位未知
for hp in range(1<<15):if hp%0x1000 == 0:print(hex(hp))tp = (1<<511)+ (hp<<512-16-1)if x[0] == '0':tp += 1<<(512-16-1)tq = (1<<(511))fac(x[1:],tp,tq)if p != 0:break io.sendline(str(p).encode())

第二部分

A = eval(io.recvline())
b = eval(io.recvline())
B = 2^16print(f"{p = }")
print(f"{A = }")
print(f"{b = }")sol = int(input('sol='))io.sendline(str(sol).encode())
print(io.recvline())io.interactive()

badprime

这是个RSA题，最后才出，难度比较小。

p = k*M + r

可以输入M，给出p%M的值，显然这里只能输入M，然后coppersimth求k

原题

from Crypto.Util.number import *
from secret import flagM = 0x7cda79f57f60a9b65478052f383ad7dadb714b4f4ac069997c7ff23d34d075fca08fdf20f95fbc5f0a981d65c3a3ee7ff74d769da52e948d6b0270dd736ef61fa99a54f80fb22091b055885dc22b9f17562778dfb2aeac87f51de339f71731d207c0af3244d35129feba028a48402247f4ba1d2b6d0755baff6def getMyprime(BIT):while True:p = int(pow(65537, getRandomRange(M>>1, M), M)) + getRandomInteger(BIT-int(M).bit_length()) * Mif isPrime(p):return pp = getMyprime(1024)
q = getPrime(1024)
n = p * q
m = bytes_to_long(flag)print("Try to crack the bad RSA")
print("Public key:", n)
print("The flag(encrypted):", pow(m, 65537, n))
print("Well well, I will give you the hint if you please me ^_^")
leak = int(input("Gift window:"))
if M % leak == 0:print("This is the gift for you: ", p % leak)
else:print("I don't like this gift!")

取数

┌──(kali㉿kali)-[~]
└─$ nc 1.13.101.243 26086
Try to crack the bad RSA
Public key: 9742410937110696461407112349699118236918457640950632920212795068374737936993342570963570443656476362238888124280173501476715660532234383908363410810325565092828457724260500094074310976465439133379654136956954969400177970645885438501653328305955812320073239582404081688376029009382502861319019563066540964659677575484346073160213626650310710260741949702931555358818963239172398313264967023252795746331804500033700165496526109847749240713539566702141086846689655725502183261216470115828779150622670477792032393842776851714610961219730469419362345806447065512890382493060186679828260265857866140764306386881882549166059
The flag(encrypted): 1673402070143155927322001035133684146816738492230807731633827901952184786734541292011662658981062894242325327877506962350481690686305101327856759348839937660438396133590644401938568726337539332758333618463217894304453290225710789062464107920895112595149601246277505775421072733759692860886887303527889771493564848232892813177891652600172884862175447947822901530128111336592984421258891521336361945375551264204284260029356005647086620008139176194080359501299190921098147822016114664277256058464418457390881573150209603439315104193219972739816965833683983804527550309212725954113363913887790377813026135333782360027419
Well well, I will give you the hint if you please me ^_^
Gift window:19467773070115377343221509599623925236459751278180415885837207534756855405403128279156705968461708578168638327032034542684864920135818987044810141311008655898015207220772515212093850725541003213054560185603695585660265284153421684796257245143362498012760214539505870197264858636122745485373430
This is the gift for you:  3919234716983693931577570915609109697211099065875069949073051641072090520857441022482511192871418764059751265895543741460544614322144961090655257474754910444266016317938260233309368531551350066234134348206616531225276790017532193136255605520389973662219840028068705375923569595556552528548183

求值

P.<x> = PolynomialRing(Zmod(n))
f = x*M + M_prime
f.small_roots(X=2^53, beta=0.2, epsilon=0.03)
k = 4429807550221656p = k*M + M_prime
q = n//p 
d = inverse_mod(65537, (p-1)*(q-1))
m = pow(c,d,n)
#71802904779908417281632177730640329722234828721755228551576131323789654417934437971480843565056115983321708839293
bytes.fromhex(hex(m)[2:])
#b'wmctf{b4d_primE_f4ctor_1s_the_w3akness_for_RSA}'

welconsigner2

这是WP里的，在这里复制保存一下。

两题都是对快速注入错误，求d，第一题一开始给错了，反正不会也就没看。以下是WP原文

对于快速幂的第i步运算，正常情况下已知Ai = Ai-1 * Bi-1^di (mod n)；Bi = Bi-1^2 (mod n)
错误注入后，上述式子改为在模数n_下进行计算，此时得到Ai' = Ai-1 * Bi-1^di (mod n_)；Bi' = Bi-1^2 (mod n_)

我们以快速幂的最后一次计算为例（错误也注入在最后一次），此时An、An'即为错误注入前、后的RSA签名。此时Bn、Bn'的值都是可以通过计算得到的，通过在模n、n_上分别尝试计算An-1的值我们即可确定dn的值（对于正确的dn值，An、An'倒推出的An-1值应该是相同的）
类似地，在得到An-1与dn的值之后，我们可以将错误注入在倒数第二次，进一步求出An-2与dn-1的值，如此即可利用n次错误注入恢复完整的RSA私钥d

from Crypto.Util.number import *nbits = 512def oracle(index):io.sendlineafter(b'|	[Q]uit', b's')io.sendlineafter(b'Where your want to interfere:', str(index).encode())io.recvuntil(b'signature of \"Welcome_come_to_WMCTF\" is ')sig = int(io.recvline().strip())return sigmsg = bytes_to_long(b"Welcome_come_to_WMCTF")
def func(sig, n, e, n_):nn = nbits*2dbit = [0 for _ in range(nn+1)]from tqdm import trangefor i in trange(nn):for now_dbit in range(2):now = dbit[:]now[nn-i] = now_dbitB, B_ = msg, msgN, N_ = n, nres, res_ = 1, 1for j in range(nn):if now[j] == 1:res = res * B % Nres_ = res_ * B_ % N_if j >= nn-1-i:N_ = n_B = B ** 2 % NB_ = B_**2 % N_sig_ = oracle(i)tmp = (sig * inverse(res, N) % N) * res_ % N_if tmp == sig_:dbit = nowbreakelse:raise Exception(f"Failure[{i}]")dbit[0] = 1d = int(''.join(str(_) for _ in dbit)[::-1], 2)print(d)print(pow(233, e*d, n))return dfrom pwn import *
io = remote('1.13.101.243', 26891)io.sendlineafter(b'|	[Q]uit', b'g')
io.recvuntil(b'n = ')
n = int(io.recvline().strip())
io.recvuntil(b'flag_ciphertext = ')
ct = bytes.fromhex(io.recvline().strip().decode())sig = oracle(0)io.sendlineafter(b'|	[Q]uit', b'f')
io.sendlineafter(b'bytes, and index:', b'255,1')
tmp = 255
index = 1
n_ = n ^ (int(tmp)<<int(index))
e = 17d = func(sig, n, e, n_)
io.close()
from Crypto.Cipher import AES
from hashlib import md5key = bytes.fromhex(md5(str(d).encode()).hexdigest())
enc = AES.new(key, mode=AES.MODE_ECB)
flag = enc.decrypt(ct)
print(flag)
# WMCTF{F4u1t_1nj3ct1on_1n_RS4*&iu2726457}

welcomesigner1

第二个的快速幂算法有变化

def myfastexp(m,d,N,j,N_):A = 1d = bin(d)[2:]n = len(d)for i in range(n-1,-1,-1):if i < j:#print(A)N = N_A = A*A % Nif d[i] == "1":A = A * m % Nreturn A

这需要将N_改为一个素数且%4==3然后通过勒让德符号计算，反正特别复杂，看得头大

from Crypto.Util.number import *
from tqdm import trangenbits = 512
m = bytes_to_long(b"Welcome_come_to_WMCTF")def init():while True:# generatep = getPrime(nbits)q = getPrime(nbits)n = p*qe = 17if GCD(e,(p-1)*(q-1)) == 1:d = inverse(e,(p-1)*(q-1))breakwhile True:n_ = next_prime(n)if n_ % 4 == 3:breakprint(f"{n = }\n{n_ = }")return n, e, n_, ddef oracle(index):io.sendlineafter(b'|	[Q]uit', b's')io.sendlineafter(b'Where your want to interfere:', str(index).encode())io.recvuntil(b'signature of \"Welcome_come_to_WMCTF\" is ')sig = int(io.recvline().strip())return sigdef func(sig, n, e, n_):def ZZ_sqrt_root(res):R.<x> = ZZ[]return (x^2-ZZ(res)).roots()def GF_sqrt_root(res, p):if pow(res, (p-1)//2, p) == 1:ans = ZZ(pow(res, (p+1)//4, p))return [ans, p-ans]return []nn = 2*nbitsdbits = ''A = sigfor i in trange(1, nn+1):sig_ = oracle(i)As_ = [sig_]for j in dbits:nxt = list()for A_ in As_:if j == '1':nxt += GF_sqrt_root(ZZ(A_*inverse(m, n_)%n_), n_)else:nxt += GF_sqrt_root(ZZ(A_), n_)As_ = [ZZ(_) for _ in nxt]flag = Falsefor j in range(2):for A_ in As_:if j == 1:s = crt([ZZ(A*inverse(m, n)%n),ZZ(A_*inverse(m, n_)%n_)], [n, n_])else:s = crt([A, A_], [n, n_])ans = ZZ_sqrt_root(s)if ans:dbits += str(j)A = max(_[0] for _ in ans)flag = Trueif not flag:raise Exception(f"Error[{i}], {dbits}")ans = int(dbits.rstrip('0')[::-1], 2)print(f"{ans = }")print(pow(233, e*ans, n))return ansfrom pwn import *
host, port = '1.13.101.243:26592'.split(':')
io = remote(host, int(port))
io = process('./server.py')io.sendlineafter(b'|	[Q]uit', b'g')
io.recvuntil(b'n = ')
n = int(io.recvline().strip())
io.recvuntil(b'flag_ciphertext = ')
ct = bytes.fromhex(io.recvline().strip().decode())sig = oracle(0)flag = False
for tmp in trange(256):for index in range(1024):n_ = n ^^ (int(tmp)<<int(index))if isPrime(n_) and n_%4 == 3:print(tmp, index)flag = Truebreakif flag:break
io.sendlineafter(b'|	[Q]uit', b'f')
io.sendlineafter(b'bytes, and index:', f'{tmp},{index}'.encode())print(f"{ct = }")e = 17
d = func(sig, n, e, n_)
io.close()from Crypto.Cipher import AES
from hashlib import md5key = bytes.fromhex(md5(str(d).encode()).hexdigest())
enc = AES.new(key, mode=AES.MODE_ECB)
flag = enc.decrypt(ct)
print(flag)
# WMCTF{F4u1t_1nj3ct1on_1n_RS4!$%@5!#$128467}