import random

Major_Arcana = ["The Fool", "The Magician", "The High Priestess","The Empress", "The Emperor", "The Hierophant","The Lovers", "The Chariot", "Strength","The Hermit", "Wheel of Fortune", "Justice","The Hanged Man", "Death", "Temperance","The Devil", "The Tower", "The Star","The Moon", "The Sun", "Judgement","The World"]
wands = ["Ace of Wands", "Two of Wands", "Three of Wands", "Four of Wands", "Five of Wands", "Six of Wands", "Seven of Wands", "Eight of Wands", "Nine of Wands", "Ten of Wands", "Page of Wands", "Knight of Wands", "Queen of Wands", "King of Wands"]
cups = ["Ace of Cups", "Two of Cups", "Three of Cups", "Four of Cups", "Five of Cups", "Six of Cups", "Seven of Cups", "Eight of Cups", "Nine of Cups", "Ten of Cups", "Page of Cups", "Knight of Cups", "Queen of Cups", "King of Cups"]
swords = ["Ace of Swords", "Two of Swords", "Three of Swords", "Four of Swords", "Five of Swords", "Six of Swords", "Seven of Swords", "Eight of Swords", "Nine of Swords", "Ten of Swords", "Page of Swords", "Knight of Swords", "Queen of Swords", "King of Swords"]
pentacles = ["Ace of Pentacles", "Two of Pentacles", "Three of Pentacles", "Four of Pentacles", "Five of Pentacles", "Six of Pentacles", "Seven of Pentacles", "Eight of Pentacles", "Nine of Pentacles", "Ten of Pentacles", "Page of Pentacles", "Knight of Pentacles", "Queen of Pentacles", "King of Pentacles"]
Minor_Arcana = wands + cups + swords + pentacles
tarot = Major_Arcana + Minor_Arcana
reversals = [0,-1]

Value = []
cards = []
YOUR_initial_FATE = []
while len(YOUR_initial_FATE)<5:
    card = random.choice(tarot)
    if card not in cards:
        cards.append(card)
        if card in Major_Arcana:
            k = random.choice(reversals)
            Value.append(tarot.index(card)^k)
            if k == -1:
                YOUR_initial_FATE.append("re-"+card)
            else:
                YOUR_initial_FATE.append(card)
        else:
            Value.append(tarot.index(card))
            YOUR_initial_FATE.append(card)
    else:
        continue
print("Oops!lets reverse 1T!")

FLAG=("hgame{"+"&".join(YOUR_initial_FATE)+"}").replace(" ","_")

YOUR_final_Value = Value
def Fortune_wheel(FATE):
    FATEd = [FATE[i]+FATE[(i+1)%5] for i in range(len(FATE))]
    return FATEd

for i in range(250):
    YOUR_final_Value = Fortune_wheel(YOUR_final_Value)
print(YOUR_final_Value)
YOUR_final_FATE = []
for i in YOUR_final_Value:
    YOUR_final_FATE.append(tarot[i%78])
print("Your destiny changed!\n",",".join(YOUR_final_FATE))
print("oh,now you GET th3 GOOd lU>k,^^")
"""
Oops!lets reverse 1T!
[2532951952066291774890498369114195917240794704918210520571067085311474675019, 2532951952066291774890327666074100357898023013105443178881294700381509795270, 2532951952066291774890554459287276604903130315859258544173068376967072335730, 2532951952066291774890865328241532885391510162611534514014409174284299139015, 2532951952066291774890830662608134156017946376309989934175833913921142609334]
Your destiny changed!
 Eight of Cups,Ace of Cups,Strength,The Chariot,Five of Swords
oh,now you GET th3 GOOd lU>k,^^
"""

Major_Arcana = ["The Fool", "The Magician", "The High Priestess","The Empress", "The Emperor", "The Hierophant","The Lovers", "The Chariot", "Strength","The Hermit", "Wheel of Fortune", "Justice","The Hanged Man", "Death", "Temperance","The Devil", "The Tower", "The Star","The Moon", "The Sun", "Judgement","The World"]
wands = ["Ace of Wands", "Two of Wands", "Three of Wands", "Four of Wands", "Five of Wands", "Six of Wands", "Seven of Wands", "Eight of Wands", "Nine of Wands", "Ten of Wands", "Page of Wands", "Knight of Wands", "Queen of Wands", "King of Wands"]
cups = ["Ace of Cups", "Two of Cups", "Three of Cups", "Four of Cups", "Five of Cups", "Six of Cups", "Seven of Cups", "Eight of Cups", "Nine of Cups", "Ten of Cups", "Page of Cups", "Knight of Cups", "Queen of Cups", "King of Cups"]
swords = ["Ace of Swords", "Two of Swords", "Three of Swords", "Four of Swords", "Five of Swords", "Six of Swords", "Seven of Swords", "Eight of Swords", "Nine of Swords", "Ten of Swords", "Page of Swords", "Knight of Swords", "Queen of Swords", "King of Swords"]
pentacles = ["Ace of Pentacles", "Two of Pentacles", "Three of Pentacles", "Four of Pentacles", "Five of Pentacles", "Six of Pentacles", "Seven of Pentacles", "Eight of Pentacles", "Nine of Pentacles", "Ten of Pentacles", "Page of Pentacles", "Knight of Pentacles", "Queen of Pentacles", "King of Pentacles"]
Minor_Arcana = wands + cups + swords + pentacles
tarot = Major_Arcana + Minor_Arcana
def reverse_step(B):
    B0, B1, B2, B3, B4 = B
    numerator = B0 + B1 + B3 - B2 - B4
    if numerator % 2 != 0:
        raise ValueError("奇数无法整除")
    A1 = numerator // 2
    A0 = B0 - A1
    A2 = B1 - A1
    A3 = B2 - A2
    A4 = B3 - A3
    if A4 + A0 != B4:
        raise ValueError("验证失败")
    return [A0, A1, A2, A3, A4]
final_values = [
    2532951952066291774890498369114195917240794704918210520571067085311474675019,
    2532951952066291774890327666074100357898023013105443178881294700381509795270,
    2532951952066291774890554459287276604903130315859258544173068376967072335730,
    2532951952066291774890865328241532885391510162611534514014409174284299139015,
    2532951952066291774890830662608134156017946376309989934175833913921142609334
]
current = final_values.copy()
for _ in range(250):
    current = reverse_step(current)
def get_card(v):
    for k in range(22):
        if k ^ -1 == v:
            return f"re-{Major_Arcana[k]}"
    index = v % 78
    card = tarot[index]
    if card in Major_Arcana and v == index:
        return card
    return card
cards = [get_card(v) for v in current]
flag = "hgame{" + "&".join(cards).replace(" ", "_") + "}"
print(flag)
#hgame{re-The_Moon&re-The_Sun&Judgement&re-Temperance&Six_of_Cups}

from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from random import randint
import hashlib
from secrets import flag

def add_THCurve(P, Q):
    if P == (0, 0):
        return Q
    if Q == (0, 0):
        return P
    x1, y1 = P
    x2, y2 = Q
    x3 = (x1 - y1 ** 2 * x2 * y2) * pow(a * x1 * y1 * x2 ** 2 - y2, -1, p) % p
    y3 = (y1 * y2 ** 2 - a * x1 ** 2 * x2) * pow(a * x1 * y1 * x2 ** 2 - y2, -1, p) % p
    return x3, y3


def mul_THCurve(n, P):
    R = (0, 0)
    while n > 0:
        if n % 2 == 1:
            R = add_THCurve(R, P)
        P = add_THCurve(P, P)
        n = n // 2
    return R


p = getPrime(96)
a = randint(1, p)
G = (randint(1,p), randint(1,p))
d = (a*G[0]^3+G[1]^3+1)%p*inverse(G[0]*G[1],p)%p
x = randint(1, p)
Q = mul_THCurve(x, G)
print(f"p = {p}")
print(f"G = {G}")
print(f"Q = {Q}")

key = hashlib.sha256(str(x).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = pad(flag,16)
ciphertext = cipher.encrypt(flag)
print(f"ciphertext={ciphertext}")

"""
p = 55099055368053948610276786301
G = (19663446762962927633037926740, 35074412430915656071777015320)
Q = (26805137673536635825884330180, 26376833112609309475951186883)
ciphertext=b"k\xe8\xbe\x94\x9e\xfc\xe2\x9e\x97\xe5\xf3\x04'\x8f\xb2\x01T\x06\x88\x04\xeb3Jl\xdd Pk$\x00:\xf5"
"""

d = (a*G[0]^3+G[1]^3+1)%p*inverse(G[0]*G[1],p)%p

p = 55099055368053948610276786301
Gx = 19663446762962927633037926740
Gy = 35074412430915656071777015320
Qx = 26805137673536635825884330180
Qy = 26376833112609309475951186883
# 计算 Gy^3 + 1 mod p
Gy_cubed = pow(Gy, 3, p)
Gy_cubed_plus_1 = (Gy_cubed + 1) % p
# 计算 Qy^3 + 1 mod p
Qy_cubed = pow(Qy, 3, p)
Qy_cubed_plus_1 = (Qy_cubed + 1) % p
# 计算分子：(Gy^3+1)*Qx*Qy - (Qy^3+1)*Gx*Gy mod p
term1 = (Gy_cubed_plus_1 * Qx) % p
term1 = (term1 * Qy) % p
term2 = (Qy_cubed_plus_1 * Gx) % p
term2 = (term2 * Gy) % p
numerator = (term1 - term2) % p
# 计算分母：Qx^3*Gx*Gy - Gx^3*Qx*Qy mod p
Qx_cubed = pow(Qx, 3, p)
term3 = (Qx_cubed * Gx) % p
term3 = (term3 * Gy) % p
Gx_cubed = pow(Gx, 3, p)
term4 = (Gx_cubed * Qx) % p
term4 = (term4 * Qy) % p
denominator = (term3 - term4) % p
# 计算逆元
inv_denominator = pow(denominator, -1, p)
a = (numerator * inv_denominator) % p
print(a)
#a=39081810733380615260725035189

from Crypto.Util.number import *
a = 39081810733380615260725035189
p = 55099055368053948610276786301
P = (19663446762962927633037926740, 35074412430915656071777015320)
Q = (26805137673536635825884330180, 26376833112609309475951186883)
d = (a * Q[0] ** 3 + Q[1] ** 3 + 1) * inverse(Q[0] * Q[1], p) % p
# construct ECC to get a solution of aX^3+Y^3+Z^3=dXYZ
R.<x,y,z> = Zmod(p)[]
cubic = a * x^3 + y^3 + z^3 - d*x*y*z
E = EllipticCurve_from_cubic(cubic,morphism=True)
P = E(P)
Q = E(Q)
P_ord = P.order()
def Pohlig_Hellman(n, P, Q):
    return discrete_log(Q, P, ord=n, operation='+')
x = Pohlig_Hellman(P_ord,P,Q)
print(x)
#x=2633177798829352921583206736

import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
x = 2633177798829352921583206736
key = hashlib.sha256(str(x).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
ciphertext = b"k\xe8\xbe\x94\x9e\xfc\xe2\x9e\x97\xe5\xf3\x04'\x8f\xb2\x01T\x06\x88\x04\xeb3Jl\xdd Pk$\x00:\xf5"
decrypted_flag = unpad(cipher.decrypt(ciphertext), 16)
print(f"解密后的数据: {decrypted_flag}")
#解密后的数据: b'hgame{N0th1ng_bu7_up_Up_UP!}'

from Crypto.Util.number import getPrime, long_to_bytes,bytes_to_long
from secrets import flag
from sage.all import *

def derive_M(n):
    iota=0.035
    Mbits=int(2 * iota * n^2 + n * log(n,2))
    M = random_prime(2^Mbits, proof = False, lbound = 2^(Mbits - 1))
    return Integer(M)

m = bytes_to_long(flag).bit_length()
n = 70
p = derive_M(n)


F = GF(p)
x = random_matrix(F, 1, n)
A = random_matrix(ZZ, n, m, x=0, y=2)
A[randint(0, n-1)] = vector(ZZ, list(bin(bytes_to_long(flag))[2:]))
h = x*A

with open("data.txt", "w") as file:
    file.write(str(m) + "\n")
    file.write(str(p) + "\n")
    for item in h:
        file.write(str(item) + "\n")

from Crypto.Util.number import *
from sage.all import *
import time
def read_data(filename):
    with open(filename, 'r') as f:
        m = int(f.readline().strip())
        n = 70
        p = int(f.readline().strip())
        h_line = f.readline().strip() 
        w = list(map(int, h_line[1:-1].split(', '))) 
    return m, n, p, w
# 生成 orthoLattice 的相关函数
def orthoLattice(b, x0):
    m = b.length()
    M = Matrix(ZZ, m, m)
    # 生成正交矩阵
    for i in range(1, m):
        M[i, i] = 1
    M[1:m, 0] = -b[1:m] * inverse_mod(b[0], x0)
    M[0, 0] = x0
    for i in range(1, m):
        M[i, 0] = mod(M[i, 0], x0)
    return M
def allpmones(v):
    return len([vj for vj in v if vj in [-1, 0, 1]]) == len(v)
def allones(v):
    if all(vj in (0, 1) for vj in v):
        return v
    if all(vj in (0, -1) for vj in v):
        return -v
    return None
# 恢复只包含 {0,1} 或 {-1,0,1} 的向量
def recoverBinary(M5):
    lv = [allones(vi) for vi in M5 if allones(vi)]
    n = M5.nrows()
    for v in lv:
        for i in range(n):
            nv = allones(M5[i] - v)
            if nv and nv not in lv:
                lv.append(nv)
            nv = allones(M5[i] + v)
            if nv and nv not in lv:
                lv.append(nv)
    return Matrix(lv)
def kernelLLL(M):
    n = M.nrows()
    m = M.ncols()
    if m < 2 * n:
        return M.right_kernel().matrix()
    K = 2 ^ (m // 2) * M.height()
    MB = Matrix(ZZ, m + n, m)
    MB[:n] = K * M
    MB[n:] = identity_matrix(m)
    MB2 = MB.T.LLL().T
    assert MB2[:n, : m - n] == 0
    Ke = MB2[n:, : m - n].T
    return Ke
def attack(m, n, p, w):
    print("n =", n, "m =", m)
    iota = 0.035
    nx0 = int(2 * iota * n^2 + n * log(n, 2))
    print("nx0 =", nx0)
    x0 = p
    b = vector(w)
    M = orthoLattice(b, x0)
    t = time.time()
    M2 = M.LLL()
    print("LLL step1: %.1f" % (time.time() - t))
    MOrtho = M2[: m - n]
    print("log(Height, 2) = ", int(log(MOrtho.height(), 2)))
    t2 = time.time()
    ke = kernelLLL(MOrtho)
    print("Kernel: %.1f" % (time.time() - t2))
    if n > 170:
        return
    beta = 2
    tbk = time.time()
    while beta < n:
        if beta == 2:
            M5 = ke.LLL()
        else:
            M5 = M5.BKZ(block_size=beta)
        if len([True for v in M5 if allpmones(v)]) == n:
            break
        if beta == 2:
            beta = 10
        else:
            beta += 10
    print("BKZ beta=%d: %.1f" % (beta, time.time() - tbk))
    t2 = time.time()
    MB = recoverBinary(M5)
    print("Recovery: %.1f" % (time.time() - t2))
    print("Number of recovered vector = ", MB.nrows())
    print("Number of recovered vector.T = ", MB.ncols())
    return MB
m, n, p, w = read_data('data.txt')
res = attack(m, n, p, w)
def bits_to_long(bits):
    return int(''.join(str(bit) for bit in bits), 2)
def extract_flags(MB):
    flags = []
    # 遍历 MB 的每一行，将每一行转换为一个二进制数字
    for row in MB:
        flag_bits = [int(element) for element in row]  # 获取每行的二进制位
        flag_long = bits_to_long(flag_bits)  # 转换为整数
        flag = long_to_bytes(flag_long)  # 转换为字节串
        flags.append(flag)    
    return flags
flags = extract_flags(res)
for flag in flags:
    print(f"Recovered flag: {flag}")
#Recovered flag: b'hgame{U_f0und_3he_5pec14l_0n3!}'