h1_sol.sage

import hashlib
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import padding
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from Crypto.Util.number import long_to_bytes, bytes_to_long
from lll_helper import resultant,prmat

a2b_r1,a2b_s1,_ = (8618416354247009865173783322782283385800726568519779763790691157278063798628048418532907783021806238103423515210146966468025964847364086792099622893845216, 2932674107137731789093617068375500084388905453653468925392946088867116597531950960271857205235755778202380084260003117176704579423285955014316540314931750, 27865871384804321325511205140263204607)
a2b_r2,a2b_s2,flag = (8832295267397231051293216564016639537146222596144354850230682204978731311879255662259663270183445827348338041752369314181111940713714991119349376636404112, 8683784208731634307361157916911868656279723101808163939313971801256736484458199874570532609285522391139002296248059424750941962344918156540408403221858292, 105398535464409171419472607677747462033030589690350997911381059472020486557672504778060748058626707326992258591478040500759349352824508941100030623708235493999018571171774658661651532338275358740821547158517615704187173346885098836066743736788259192831313414309775979590033581301910426314601982482556670097620)
r1,s1,_ = (6706720197123832142768727143395528571627385686729472279085077699672602636953568596628477227511870037092766007177588966333093607595831000050978265637877796, 1073779379108240410856990657565545229209771903946426639922087094813786902448520023335130808991515066506036954730763452318418336144389425011731474342543709, 111403492170712993917428321974111102656)
r2,s2,_ = (7616464676048536081690041693308621105395807976530049374449777558721544903144139995398352331701243976154631946836252022822278420653297509476320989403738186, 7381293847317597354132365685036776332763847784351725370466906894121224725876600151244989563125805807680044723478850091886778158534219876869209592138625256, 7994736246642278834331127451449673561762900804586058657648578638831731501930073150317394505661139656896430884711113)
h2 = bytes_to_long(hashlib.sha512(b'Dinner sounds good. Thanks for the flag.').digest())
h1 = bytes_to_long(hashlib.sha512(b'Hello Alice.').digest())
a2b_h1 = bytes_to_long(hashlib.sha512(b'Hello Bob.').digest())

p = 8948962207650232551656602815159153422162609644098354511344597187200057010413552439917934304191956942765446530386427345937963894309923928536070534607816947
a = 6294860557973063227666421306476379324074715770622746227136910445450301914281276098027990968407983962691151853678563877834221834027439718238065725844264138
b = 3245789008328967059274849584342077916531909009637501918328323668736179176583263496463525128488282611559800773506973771797764811498834995234341530862286627 
n = 8948962207650232551656602815159153422162609644098354511344597187200057010413418528378981730643524959857451398370029280583094215613882043973354392115544169
G = (5139617820728399941653175323358137352238277428061991823713659546881441331696699723004749024403291797641521696406798421624364096550661311227399430098134141,
     1798860115416690485862271986832828064808333512613833729548071279524320966991708554765227095605106785724406691559310536469721469398449016850588110200884962,
     5042518522433577951395875294780962682755843408950010956510838422057522452845550974098236475624683438351211176927595173916071040272153903968536756498306512)

F = GF(p)
R.<x,y,z> = PolynomialRing(F)
curve = y^2 - x^3 - a*x*z^4 - b*z^6
E = Jacobian(curve)

def point(x,y,z):
    if z != 0:
        return E(F(x/z^2), F(y/z^3))
    else :
        raise ValueError()


G = E(point(*G))
P = PolynomialRing(Zmod(n) ,33,'b')
B, d = P.gens()[:32], P.gens()[-1]
a = 16843009
b = 4294967296
k1 = a * sum(B[i] * 2^(32*i) for i in range(16))
k2 = a * sum(B[i+16] * 2^(32*i) for i in range(16))
f1 = k1 * s1 - h1 - r1 * d
f2 = k2 * s2 - h2 - r2 * d
f3 = resultant(f1, f2, d) # we can't do lll with 2 unkowns
coeffs = f3.coefficients()
vec = (coeffs + [n])
M = Matrix.identity(34)
M.set_column(33,vec)
M = M.dense_matrix()
prmat(M)
M = M.LLL()
assert M[0][-1] == 0
b_subs = { B[i]: abs(M[0][i]) for i in range(32) }
k1 = k1.subs(b_subs)
k2 = k2.subs(b_subs)
print("Recovered K for Alice:",k1) 
priv = F((s1*k1 - h1)/r1)

pub = inverse_mod(a2b_r1, n)*(a2b_s1 * -E.lift_x(a2b_r1) - a2b_h1 * G)

def Decrypt(ciphertext, x):
    key = hashlib.sha256(str(x).encode()).digest()
    aes = algorithms.AES(key)
    decryptor = Cipher(aes, modes.ECB(), default_backend()).decryptor()
    unpadder = padding.PKCS7(aes.block_size).unpadder()
    decrypted_data = decryptor.update(ciphertext) + decryptor.finalize() 
    plaintext = unpadder.update(decrypted_data) + unpadder.finalize()
    return plaintext 

x = (int(priv)*pub).xy()[0]
print(Decrypt(long_to_bytes(flag), x).decode())