LOV3 -> OV3

8abyRSA

题面

from Crypto.Util.number import getPrime, bytes_to_long
from LCGRandom import lcg

flag = b"DASCTF{xxxx}"
m = bytes_to_long(flag)
q = getPrime(512)
p = getPrime(512)
Q = pow(q, 2, p)  # Q = q^2 mod p


n = p*q
e = getPrime(512)
c = pow(m, e, n)
print('c = ' + str(c))

mul = p
n = e
c = Q


lcg1 = lcg(2023, mul, n, c)
print(lcg1.generate(6))

# Data
# c = 14968774972802568447907734980942381885170753466134942777553237930032293557412276601708303806296932877792965437305452274767013479132983066980557420348521340748653518789837988349171582558831336243036976332252071289409948879158346086243451785505819420501498240344839999096449458990633841326838003742773196414924
# [1829291767649461103161355195365566822501625317566021355553611375584303624765389047237072963403651896280059309840080549881138083110457632256619677785411889, 8614784647131959905489143385414473366220060118109917221659356152996027731619256154868253763867569947876938642677951734943013867186530789820165520197525548, 7845112879564311528346861967994968539141359532994486000551038947867807602664345244223622318955917969589790931596150225393028516278795565957075910272882168, 464696663556289552651401659156226806419638205935729756668755007052945250273596319671267391086858010496056118762904740103810918505838370732992982394379753, 6368769952056267497431070536699202267447921981615807369090285698513090854334005214066202915932322373348204466447234330868540529876844912401907159350901200, 4401214958628797991805307100256403706658940216552816808894942142670769563264366171079551655390635613048161714797548328158857275108940238519111063046341755]

c = 14968774972802568447907734980942381885170753466134942777553237930032293557412276601708303806296932877792965437305452274767013479132983066980557420348521340748653518789837988349171582558831336243036976332252071289409948879158346086243451785505819420501498240344839999096449458990633841326838003742773196414924
lcg_gen_6 = [1829291767649461103161355195365566822501625317566021355553611375584303624765389047237072963403651896280059309840080549881138083110457632256619677785411889, 8614784647131959905489143385414473366220060118109917221659356152996027731619256154868253763867569947876938642677951734943013867186530789820165520197525548, 7845112879564311528346861967994968539141359532994486000551038947867807602664345244223622318955917969589790931596150225393028516278795565957075910272882168,
             464696663556289552651401659156226806419638205935729756668755007052945250273596319671267391086858010496056118762904740103810918505838370732992982394379753, 6368769952056267497431070536699202267447921981615807369090285698513090854334005214066202915932322373348204466447234330868540529876844912401907159350901200, 4401214958628797991805307100256403706658940216552816808894942142670769563264366171079551655390635613048161714797548328158857275108940238519111063046341755]

seed = 2023

Exploit

SageMath's Code

from sage.all import *
import random
from Crypto.Util.number import long_to_bytes

lcg_gen_6 = [1829291767649461103161355195365566822501625317566021355553611375584303624765389047237072963403651896280059309840080549881138083110457632256619677785411889, 8614784647131959905489143385414473366220060118109917221659356152996027731619256154868253763867569947876938642677951734943013867186530789820165520197525548, 7845112879564311528346861967994968539141359532994486000551038947867807602664345244223622318955917969589790931596150225393028516278795565957075910272882168,
             464696663556289552651401659156226806419638205935729756668755007052945250273596319671267391086858010496056118762904740103810918505838370732992982394379753, 6368769952056267497431070536699202267447921981615807369090285698513090854334005214066202915932322373348204466447234330868540529876844912401907159350901200, 4401214958628797991805307100256403706658940216552816808894942142670769563264366171079551655390635613048161714797548328158857275108940238519111063046341755]

"""
seed = 2023

x = [seed]
x = x + lcg_gen_6
"""
x = lcg_gen_6

x1 = x[0]
x2 = x[1]
x3 = x[2]

t = []

for i in range(1, len(x)):
    t.append(x[i] - x[i-1])

# 恢复 Modulus
m = 0
for i in range(1, len(t)-1):
    m = GCD(t[i+1]*t[i-1] - t[i]*t[i], m)
print(f'[+] modulus: {m}')
n = m

# 恢复 Multiplier, Increment (a, b)
R = Zmod(n)
a = R(x[2] - x[1]) / (x[1] - x[0])
b = R(x[1] - a * x[0])
print(f'[+] a = {a}\n[+] b = {b}')

# 也许参数位置不对
p = ZZ(a)
e = ZZ(b)
Q = ZZ(n)

# Q \equiv q^2 \pmod{p}
# 求二次剩余, 返回空, 大概率位置错了
# []

# check location
print(f'[*] Parameters location check:\t{is_prime(p)} {is_prime(e)} {is_prime(Q)}')
# 1 0 1
# p, q, e 均为 512-bits 素数, 而上面第二个返回值为 False, 则说明位置错了
Q, e = e, Q

# 判二次剩余
if not legendre_symbol(Q, p) == 1:
    print('[-] No solution')
else:
    print('[+] Found solution')

# Solution quadratic residue
# Modulus is prime, So
# Cipolla Algorithm

class CipollaAlgorithm:
    def __init__(self, p):
        self.p = p  # 模数p

    def mul(self, a, b, w):
        # 复数乘法
        x = (a[0] * b[0] + a[1] * b[1] * w) % self.p
        y = (a[0] * b[1] + a[1] * b[0]) % self.p
        return (x, y)

    def qpow_r(self, a, b):
        # 实数快速幂
        res = 1
        while b:
            if b & 1:
                res = res * a % self.p
            a = a * a % self.p
            b >>= 1
        return res

    def qpow_i(self, a, b, w):
        # 复数快速幂
        res = (1, 0)
        while b:
            if b & 1:
                res = self.mul(res, a, w)
            a = self.mul(a, a, w)
            b >>= 1
        return res[0]

    def cipolla(self, n):
        n %= self.p
        if self.qpow_r(n, (self.p - 1) // 2) == self.p - 1:
            return -1  # 没有解

        while True:
            a = random.randint(0, self.p-1)
            w = (a*a - n) % self.p
            if self.qpow_r(w, (self.p - 1) // 2) == self.p - 1:
                break
        
        x = (a, 1)
        return self.qpow_i(x, (self.p + 1) // 2, w)

# Q = q^2 mod p
p = p 
n = Q
cipolla = CipollaAlgorithm(p)
ans1 = cipolla.cipolla(n)
ans2 = (-ans1) % p

ans = []

if ans1 == -1:
    print("[-] No solution")
else:
    if ans1 > ans2:
        ans1, ans2 = ans2, ans1
    if ans1 == ans2:
        ans.append(ans1)
    else:
        ans.append(ans1)
        ans.append(ans2)

# check prime
for i in ans:
    if not is_prime(i):
        # print(f'[-] {i} is not prime')
        pass
    else:
        q = i
        print(f'[+] {i} is prime')
        
print('[*] DONE Quadratic Residue')
        
phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)

c = 14968774972802568447907734980942381885170753466134942777553237930032293557412276601708303806296932877792965437305452274767013479132983066980557420348521340748653518789837988349171582558831336243036976332252071289409948879158346086243451785505819420501498240344839999096449458990633841326838003742773196414924

m = pow(c, d, p * q)
print(f'[*] 全因子解密: \n{long_to_bytes(m)}')

# uuid 长 42 bytes
# DASCTF{} 长 8 bytes
# 50 * 8 = 400 bits < 512 bits
# 单因子解密
phi = p - 1
d = inverse_mod(e, phi)
m = power_mod(c, d, p)
print(f'[*] 单因子解密: \n{long_to_bytes(m)}')

"""
inva = inverse(a, n)
x1 = x[0]
for i in range(300):
    x1 = (x1 - b) * inva % n
    try:
        flag = long_to_bytes(x1)
        if b'flag{' in flag:
            print(flag)
    except Exception as err:
        print(err)
        continue
"""