祥云杯2022

from secret import p, q, flag
from Crypto.Util.number import bytes_to_long

def gcd(a, b):
    s = 0
    while b != 0:
        print(a, b)
        if isOdd(a):
            if isOdd(b):
                a = a - b
                a = rshift1(a)
                if a < b:
                    a, b = b, a
            else:
                b = rshift1(b)
                if a < b:
                    a, b = b, a
        else:
            if isOdd(b):
                a = rshift1(a)
                if a < b:
                    a, b = b, a
            else:
                a = rshift1(a)
                b = rshift1(b)
                s += 1
    if s:
        return lshift(a, s)
    return a

def isOdd(a):
    return a & 1 == 1

def rshift1(a):
    return a >> 1

def lshift(a, s):
    return a << s


n = p * q
e = 65537
phi = (p - 1) * (q - 1)
assert gcd(phi, e) == 1
c = pow(bytes_to_long(flag), e, n)
print(c)
print(n)

import gmpy2
from Crypto.Util.number import long_to_bytes

e = 65537
c = 64885875317556090558238994066256805052213864161514435285748891561779867972960805879348109302233463726130814478875296026610171472811894585459078460333131491392347346367422276701128380739598873156279173639691126814411752657279838804780550186863637510445720206103962994087507407296814662270605713097055799853102
n = 113793513490894881175568252406666081108916791207947545198428641792768110581083359318482355485724476407204679171578376741972958506284872470096498674038813765700336353715590069074081309886710425934960057225969468061891326946398492194812594219890553185043390915509200930203655022420444027841986189782168065174301
a = 1
b = 0

f = open("trace.out","r")
lines = f.readlines()
for i in range(12621):
    line = lines[-1-i]
    if "a, b = b, a" in line:
        a, b = b, a
    elif "a = rshift1(a)" in line:
        a = a << 1
    elif "a = a - b" in line:
        a = a + b
    elif "b = rshift1(b)" in line:
        b = b << 1
    else:
        continue

# print("phi = ",a)
# print("e = ", b)

phi =  113793513490894881175568252406666081108916791207947545198428641792768110581083359318482355485724476407204679171578376741972958506284872470096498674038813744206060043230633366541996120990867169768523014939944773017185662017479011094588132516102178922759206005551241577259317764398494195585166584573218495824732
e =  65537
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

# flag{a526344-a8c7-411d-bf53-ef6a2479de1a}

from Crypto.Util.number import *
from random import *
from libnum import *
import gmpy2
from secret import x

flag = b'?????????'
m = bytes_to_long(flag)
def obfuscate(p, k):
    nbit = p.bit_length()
    while True:
        l1 = [getRandomRange(-1, 1) for _ in '_' * k]
        l2 = [getRandomRange(100, nbit) for _ in '_' * k]
        l3 = [getRandomRange(10, nbit//4) for _ in '_' * k]
        l4 = [getRandomRange(2, 6) for _ in '_' *k]
        A = sum([l1[_] * 2 ** ((l2[_]+l3[_])//l4[_]) for _ in range(0, k)])
        q = p + A
        if isPrime(q) * A != 0:
            return q

p = getPrime(512)
q = obfuscate(p, 5)
e = 65537
n = p*q
print(f'n = {n}')

assert 114514 ** x % p == 1
m = m ^ (x**2)
c = pow(m, e, n)
print(f'c = {c}')

'''
n = 141321067325716426375483506915224930097246865960474155069040176356860707435540270911081589751471783519639996589589495877214497196498978453005154272785048418715013714419926299248566038773669282170912502161620702945933984680880287757862837880474184004082619880793733517191297469980246315623924571332042031367393
c = 81368762831358980348757303940178994718818656679774450300533215016117959412236853310026456227434535301960147956843664862777300751319650636299943068620007067063945453310992828498083556205352025638600643137849563080996797888503027153527315524658003251767187427382796451974118362546507788854349086917112114926883
'''

import gmpy2
from Crypto.Util.number import *

e = 65537
n = 141321067325716426375483506915224930097246865960474155069040176356860707435540270911081589751471783519639996589589495877214497196498978453005154272785048418715013714419926299248566038773669282170912502161620702945933984680880287757862837880474184004082619880793733517191297469980246315623924571332042031367393
c = 81368762831358980348757303940178994718818656679774450300533215016117959412236853310026456227434535301960147956843664862777300751319650636299943068620007067063945453310992828498083556205352025638600643137849563080996797888503027153527315524658003251767187427382796451974118362546507788854349086917112114926883
a = gmpy2.iroot(n, 2)[0]

while True:
    tmp = pow(a, 2) - n
    if gmpy2.is_square(tmp):
        b = gmpy2.iroot(tmp, 2)[0]
        p = a + b
        q = a - b
        print(p)
        # p = 11887853772894265642834649929578157180848240939084164222334476057487485972806971092902627112665734648016476153593841839977704512156756634066593725142934001
        print(q)
        # q = 11887853772894265642834649929578157180848240939084164222334476057487485972806971092902627112665734646483980612727952939084061619889139517526028673988305393
        break
    a += 1

phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
x = p-1
m = m^(x**2)
print(long_to_bytes(m))
# b'flag{I~ju5t_w@nt_30_te11_y0u_how_I_@m_f3ll1ng~}45108#@7++3@79?3328?!!@08#712/+963-60#9-/83#+/1@@=59!/84@?3#4!4=-9542/##'

from Crypto.Util.number import getPrime, isPrime, bytes_to_long, inverse
from math import lcm
from secret import flag

def gen(g):
    bits = 512 - g.bit_length()
    while True:
        a = getPrime(bits)
        p = 2 * a * g + 1
        if isPrime(p):
            return p

flag = bytes_to_long(flag)
g = getPrime(320)
p = gen(g)
q = gen(g)
n = p * q
d = getPrime(135)
phi = lcm(p - 1, q - 1)
e = inverse(d, phi)
c = pow(flag, e, n)
print("n = {}".format(n))
print("e = {}".format(e))
print("c = {}".format(c))

import gmpy2
from Crypto.Util.number import *

n = 253784908428481171520644795825628119823506176672683456544539675613895749357067944465796492899363087465652749951069021248729871498716450122759675266109104893465718371075137027806815473672093804600537277140261127375373193053173163711234309619016940818893190549811778822641165586070952778825226669497115448984409
e = 31406775715899560162787869974700016947595840438708247549520794775013609818293759112173738791912355029131497095419469938722402909767606953171285102663874040755958087885460234337741136082351825063419747360169129165
c = 97724073843199563126299138557100062208119309614175354104566795999878855851589393774478499956448658027850289531621583268783154684298592331328032682316868391120285515076911892737051842116394165423670275422243894220422196193336551382986699759756232962573336291032572968060586136317901595414796229127047082707519
p = 12080882567944886195662683183857831401912219793942363508618874146487305963367052958581455858853815047725621294573192117155851621711189262024616044496656907
q = n//p
d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))
# b'flag{9aecf8d8-6966-4ffa-96b0-2e744d28baf2}'

from Crypto.Util.number import *
from random import *
from gmpy2 import gcd
from numpy import dot

nbits = 32
msg = getRandomNBitInteger(nbits)
flag = b'flag{sha256(msg)}'
tmp_m = bin(msg)[2:]
f_list = []
for i in range(len(tmp_m)):
    f_list.append(int(tmp_m[i]))

r_list =[randint(20, 50)]
for i in range(nbits - 1):
    r_list.append(randint(2 * r_list[-1], 3 * r_list[-1]))

while True:
    A = randint(2 * r_list[-1] + 1, 3 * r_list[-1])
    B = randint(2 * r_list[-1] + 1, 3 * r_list[-1])
    if gcd(A, B) == 1:
        break

M = [A * x % B for x in r_list]

S = dot(f_list, M)
print(S)

seed = getRandomNBitInteger(30)
s = [0] * nbits
s[0] = seed
m = getRandomNBitInteger(20)
c = getPrime(24)
n = 991125622
for i in range(1, nbits):
    s[i] = (s[i-1]*m+c)%n
print(s[0], s[1], s[2])
for t in range(nbits):
    M[t] = M[t] + s[t]
print(M)


'''
492226042629702
562734112 859151551 741682801
M = [19621141192340, 39617541681643, 3004946591889, 6231471734951, 3703341368174, 48859912097514, 4386411556216, 11028070476391, 18637548953150, 29985057892414, 20689980879644, 20060557946852, 46908191806199, 8849137870273, 28637782510640, 35930273563752, 20695924342882, 36660291028583, 10923264012354, 29810154308143, 4444597606142, 31802472725414, 23368528779283, 15179021971456, 34642073901253, 44824809996134, 31243873675161, 27159321498211, 2220647072602, 20255746235462, 24667528459211, 46916059974372]
'''