网鼎杯-Qualifier-2022/白虎组/Crypto/? writeup

题目名字不知道

challenge

from Crypto.Util.number import getPrime
import hashlib

e = 2022
m = getPrime(512)
m1 = getPrime(512)
m2 = getPrime(512)
flag = m+m1+m2
flag = hashlib.md5(str(flag).encode('utf-8')).hexdigest()

c1 = pow(m+m1, e, m*m1)
c2 = pow(m+m2, e, m*m2)
c3 = pow(m1+m2, e, m1*m2)

x = pow(m1+2022, m, m*m1)
y = pow(m2+2022, m, m*m2)
z = pow(m+2022, m1, m*m1)

print("c1 = ", c1)
print("c2 = ", c2)
print("c3 = ", c3)
print("x = ", x)
print("y = ", y)
print("z = ", z)

分析

$$ \begin{align} & (m+m_1)^e \equiv c_1 \mod mm_1 \notag \newline & (m+m_2)^e \equiv c_2 \mod mm_2 \notag \newline & (m_1+m_2)^e \equiv c_3 \mod m_1m_2 \notag \newline & (m_1+e)^m \equiv x \mod mm_1 \notag \newline & (m_2+e)^m \equiv y \mod mm_2 \notag \newline & (m+e)^{m_1} \equiv z \mod mm_1 \notag \end{align} $$

根据数论的性质，可以推出很多式子：

$$ \begin{align} & m_1^e \equiv c_1 \mod m\tag{1} \newline & m^e \equiv c_1 \mod m_1\tag{2} \newline \notag \newline & m_2^e \equiv c_2 \mod m\tag{3} \newline & m^e \equiv c_2 \mod m_2\tag{4} \newline \notag \newline & m_1^e \equiv c_3 \mod m_2\tag{5} \newline & m_2^e \equiv c_3 \mod m_1\tag{6} \newline \notag \newline & m_1+e \equiv x \mod m\tag{7} \newline & e^m \equiv x \mod m_1\tag{8} \newline \notag \newline & m_2+e \equiv y \mod m\tag{9} \newline & e^m \equiv y \mod m_2\tag{10} \newline \notag \newline & m+e \equiv y \mod m_1\tag{11} \newline & e^{m_1} \equiv y \mod m\tag{12} \newline \notag \newline & 由(7): \notag \newline & m_1\equiv x-e \mod m \notag \newline & 又由(1): \notag \newline & (x-e)^e \equiv c_1 \mod m \notag \newline & \Rightarrow (x-e)^e-c_1 = k_1m \notag \newline & 同理，由(3), (9): \notag \newline & (y-e)^e-c_2 = k_2m \notag \newline & \Rightarrow m = gcd((x-e)^e-c_1, (y-e)^e-c_2) \notag \end{align} $$

3. Solver

from Crypto.Util.number import getPrime
# import hashlib

e = 2022
m = getPrime(512)
m1 = getPrime(512)
m2 = getPrime(512)
# flag = m+m1+m2
# flag = hashlib.md5(str(flag).encode('utf-8')).hexdigest()

c1 = pow(m+m1, e, m*m1)
c2 = pow(m+m2, e, m*m2)
c3 = pow(m1+m2, e, m1*m2)

x = pow(m1+2022, m, m*m1)
y = pow(m2+2022, m, m*m2)
z = pow(m+2022, m1, m*m1)

m3 = gcd(Integer(pow(x-e, e)-c1), Integer(pow(y-e, e)-c2))
while not is_prime(m3):
    m3=max(m3.factor())[0]
print("m=", m3)
    
m4 = Integer((x-e)%m3)
if m4.nbits() < 512:
    m4 += m3
print("m2=", m4)

m5 = Integer((y-e)%m3)
if m5.nbits() < 512:
    m5 += m3
print("m5=", m5)

assert m3 == m
assert m4 == m1
assert m5 == m2
print("ok")

m= 7118720259706239740305137951911732402969987929524547444851950877506312984069352034009095275081680311758669878793244045227889362955734722453100841143548033
m2= 7108430137084219836773217660392603820991459506843363980563501987103264045379764167844893288579200970211583422408191541717109914729741191349555605737532891
m5= 10314184155653100949586733371377643592337306207790750904674051212420413332553293415287164275431131107876785228642595517356004403525571470519812972911339059
ok