Securinets Quals 2022 | Escrime - crypto-writeup-public

#Securinets_Quals_2022

from Crypto.Util.number import getStrongPrime, getPrime, isPrime, bytes_to_long

FLAG = b"Securinets{REDACTED}"

def genPrime(prime):
    while True:
        a = getPrime(256)
        p = 2*prime*a + 1
        if isPrime(p):
            break
    while True:
        b = getPrime(256)
        q = 2*prime*b + 1
        if isPrime(q):
            break
    return p, q

prime = getStrongPrime(512)
p1, q1 = genPrime(prime)
p2, q2 = genPrime(prime)
assert p1 != p2 != q1 != q2

n1 = p1*q1
n2 = p2*q2
e = 65537

m1 = bytes_to_long(FLAG[:len(FLAG)//2])
m2 = bytes_to_long(FLAG[len(FLAG)//2:])

c1 = pow(m1, e, n1)
c2 = pow(m2, e, n2)

print(f"n1 = {n1}")
print(f"n2 = {n2}")
print(f"e = {e}")
print(f"c1 = {c1}")
print(f"c2 = {c2}")

RSAでSuspicious Prime

512bitの素数 $p$ を持ってきて

$n_1 = (2pa_1+1)*(2pb_1+1) = 4p^2a_1b_1 + 2p(a_1 + b_1) + 1$

$n_2 = (2pa_2+1)*(2pb_2+1) = 4p^2a_2b_2 + 2p(a_2 + b_2) + 1$

$a_i, b_i$ は256bit

$\gcd(n_1 - 1, n_2 - 1) = 2px$ として $p$ が求まる（ $x$ は適当なゴミ）

$a_i, b_i$ は $n$ に対して比較的小さいのであとはmultivariate coppersmith

p = factor(gcd(n1 - 1, n2 - 1))[-1][0]
load("./defund.sage")

PR.<a, b> = PolynomialRing(Zmod(n1))
f = 4*p**2*a*b + 2*p*(a + b) + 1
a_1, b_1 = small_roots(f, [2**256, 2**256])[0]
p1 = 2*p*a_1 + 1
q1 = 2*p*b_1 + 1

d1 = inverse_mod(e, (p1-1)*(q1-1))
m1 = bytes.fromhex(hex(pow(c1, d1, n1))[2:])


PR.<a, b> = PolynomialRing(Zmod(n2))
f = 4*p**2*a*b + 2*p*(a + b) + 1
a_2, b_2 = small_roots(f, [2**256, 2**256])[0]
p2 = 2*p*a_2 + 1
q2 = 2*p*b_2 + 1

d2 = inverse_mod(e, (p2-1)*(q2-1))
m2 = bytes.fromhex(hex(pow(c2, d2, n2))[2:])

print(m1 + m2)

https://blog.y011d4.com/20220411-securinets-ctf-writeup#escrime