西湖论剑-2020-Wake me up until May ends-solve.py

from sage.all_cmdline import *
from gmpy2 import iroot, invert, is_prime
from Crypto.Util.number import long_to_bytes
from random import shuffle

s = pow(2, 790-256)

primes = [6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503118559, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503126443, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503193349, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503562289, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503734189, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503760301, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503782813, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503951191, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824504074953, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824504107911, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824504191461, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824504448729, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824504539989]
c = 84010209207136400037674900630630399007540527378939350615722225527845587559010102178617103738600464258190430641037546648203366413208680794400023737381999928100638870193135477985407368386033167118399673001236960699550393986712868487827560601610546135335952667201927052409197291462799539018091792246183307678928298241645258411316936304167124933556606198943248215284393941957893610109127025761289673484220381931928088574316265497075872825588843686573267223321714224535003053507039588501110165036609252972283465620670619170664971316238808580562960566239652372002792893860381585262550998380705474210656337505369024906108022045918104803080765059727578165530772500933465284347893453376016683018177839155666453880461050298815103588796089076127048997409337740340488597725920421812209214132626919132717242722587461710190518049279845280531076833361229586237230905386909567570882397978261647980071794688572393137428928552335623610968045342130104152766075095859252589558838654095036476181115093298573203118822557283958028992348972004110923680696213759378910314691270631431638964147123334674
_e = 372077403420031165815439199213704344304928202869941592969972103002464355333911024937074871410825817568355544126574173758702600945390438495248751733573391345292294888885607465578329781858741122278411513362633310583564023669185613282939355138576537165757775740881908805743008022348524049466231348651228609449357106436669219
_n = 470335762637936005588762180827192207993663594416060284974932410896705386687847439702920143090437462997342000428130417147164245577372958674672171462397851600930104979198327224831772288314005311036009419876584852939180439595289349509330868790367408195151323961061772542485151690708678904080061050887466315542337191307236199
_c = 333271281173306446630548720678701979402616631681988817880871964537046235416970583988475783551455814258102380169630603934095599959443467742430556704688855518165068592402751863811686579302153371106333344752494076921552527417915731880831363624299780159503812111855009880750695443491602523883753510968162389168190126033304497

# D = [
#     [s, 0, _e],
#     [0, s, -(_n+1)]
# ]

# M = matrix(ZZ, D)
# E = M.LLL()

# _sum = E[0][0] * _e // E[0][1] - (_n+1)
# delta = iroot(_sum**2 - 4*_n, 2)[0]
# _p = (_sum + delta)//2
# for i in range(-100, 100):
#     p = _p+i
#     if _n%p==0:
#         break
# if p<0:
#     p = -p
# print p

p = 19769576600565519125889505375792992406050004251569520971859725047743906669427655492699772142341740769220040483012351823754756561500184163887909573314574472102999
q = _n//p
assert p*q == _n
d = invert(_e, (p-1)*(q-1))
e = pow(_c, d, _n)
# for x in primes:
#     print is_prime(x-2)
while 1:
    shuffle(primes)
    tmp_primes = primes[:7]
    n = reduce(lambda x,y: x*y, [x-2 for x in tmp_primes])
    phin = reduce(lambda x,y: x*y, [x-2-1 for x in tmp_primes])
    d = invert(e, phin)
    # assert pow(pow(2, e, n), d, n) == 2
    res = pow(c, d, n)
    if res.bit_length()<1000:
        print long_to_bytes(res)
        break

西湖论剑-2020-Wake me up until May ends-task.py

from Crypto.Util.number import *
from gmpy2 import *
from secret import flag, source_p
from random import randint, shuffle
from sympy.ntheory import factorint


def all_factor(n):
    factors = []
    limit = n//2 + 1
    for i in range(1, limit):
        if n % i == 0:
            factors.append(i)
    factors.append(n)
    return factors


def u(d):
    if d == 1:
        return 1
    factors = factorint(d)
    primes = list(factors.keys())
    index = list(factors.values())
    for i in index:
        if i >= 2:
            return 0
    return pow(-1, len(primes) % 2)


def f(d):
    factors = factorint(d)
    primes = list(factors.keys())
    index = list(factors.values())
    base = 1
    for i in range(len(primes)):
        base *= pow(primes[i], index[i]-1)
        base *= (primes[i] - 1)
    return base


def combine(n):
    factors = all_factor(n)
    base = 0
    for i in factors:
        base += u(i) * f(i)
    return base


def Yusa(m):
    p = getPrime(533)
    q = getPrime(533)
    n = p * q
    _phi = (p - 1) * (q - 1)
    limit1 = (3 * n) // (2 * (int(iroot(n, 4)[0]) + 3 * (p + q)))

    while True:
        x = getPrime(256)
        y = getPrime(256)
        if x * y < limit1:
            break

    limit2 = (abs(p-q) * int(iroot(n, 4)[0]) * y) // (6 * (max(p, q)))
    e = (y * _phi) // x
    while True:
        z = e * x - y * _phi
        if abs(z) < limit2 and gcd(e, _phi) == 1:
            break
        e -= 1

    c = pow(m, e, n)
    return c, e, n


shuffle(source_p)
p = source_p[:7]
length = 7
index = []
n = 1
for i in range(length):
    index.append(randint(1, 23))
    n *= p[i] ** index[i]

n = -combine(n)
assert n.bit_length() > 2048

e = getPrime(256)
_c, _e, _n = Yusa(e)


m = bytes_to_long(flag.encode())
c = pow(m, e, n)
print('c =', c)
print('p =', source_p)
print('index =', index)
print('_e =', _e)
print('_n =', _n)
print('_c =', _c)

# data
'''
primes = [6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503118559, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503126443, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503193349, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503562289, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503734189, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503760301, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503782813, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503951191, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824504074953, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824504107911, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824504191461, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824504448729, 6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824504539989]
c = 84010209207136400037674900630630399007540527378939350615722225527845587559010102178617103738600464258190430641037546648203366413208680794400023737381999928100638870193135477985407368386033167118399673001236960699550393986712868487827560601610546135335952667201927052409197291462799539018091792246183307678928298241645258411316936304167124933556606198943248215284393941957893610109127025761289673484220381931928088574316265497075872825588843686573267223321714224535003053507039588501110165036609252972283465620670619170664971316238808580562960566239652372002792893860381585262550998380705474210656337505369024906108022045918104803080765059727578165530772500933465284347893453376016683018177839155666453880461050298815103588796089076127048997409337740340488597725920421812209214132626919132717242722587461710190518049279845280531076833361229586237230905386909567570882397978261647980071794688572393137428928552335623610968045342130104152766075095859252589558838654095036476181115093298573203118822557283958028992348972004110923680696213759378910314691270631431638964147123334674
index = [17, 4, 10, 5, 22, 23, 3]
_e = 372077403420031165815439199213704344304928202869941592969972103002464355333911024937074871410825817568355544126574173758702600945390438495248751733573391345292294888885607465578329781858741122278411513362633310583564023669185613282939355138576537165757775740881908805743008022348524049466231348651228609449357106436669219
_n = 470335762637936005588762180827192207993663594416060284974932410896705386687847439702920143090437462997342000428130417147164245577372958674672171462397851600930104979198327224831772288314005311036009419876584852939180439595289349509330868790367408195151323961061772542485151690708678904080061050887466315542337191307236199
_c = 333271281173306446630548720678701979402616631681988817880871964537046235416970583988475783551455814258102380169630603934095599959443467742430556704688855518165068592402751863811686579302153371106333344752494076921552527417915731880831363624299780159503812111855009880750695443491602523883753510968162389168190126033304497
'''