from sage.all import *
from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler
from secret import flagstd_limit = 0.01def get_accurate_Discrete_Gaussian(sigma, limit=std_limit):factor = 1while True:Df = DiscreteGaussianDistributionIntegerSampler(sigma * factor)if abs(RR(std([Df() for _ in range(2 ** 15)])) - sigma) / sigma < limit:return Dffactor += 0.01def ZZ_to_Fq(_vector, _q, _n):return [int(i % _q) if abs(_q - int(i % _q)) > int(i % _q) else (int(i % _q) - _q) for i in _vector] + [0] * (_n - len(_vector))def My_generator(Sampler, _n, limit=std_limit):while True:tmp = [Sampler() for _ in range(_n)]if abs(RR(std(tmp)) - Sampler.sigma) < limit:return tmpdef generate_key():while True:F = Matrix([[PRz(My_generator(Df, d)) for _ in range(n)] for _ in range(n)])G = Matrix([[PRz(My_generator(Df, d)) for _ in range(k)] for _ in range(n)])try:H = F.change_ring(PRqm).inverse() * G.change_ring(PRqm)H = Matrix([[PRz(Hij.lift()) for Hij in Hi] for Hi in H.transpose()]).transpose()return F, G, Hexcept ArithmeticError:continued = 64
q = 12289
p = 17
n = 2
k = 1
sigma_f, sigma_s, sigma_e = 0.4, 0.6, 0.6PRq = PolynomialRing(Zmod(q), 'xq')
PRp = PolynomialRing(Zmod(p), 'xp')
PRz = PolynomialRing(ZZ, 'xz')
mod_polynomial = PRz.cyclotomic_polynomial(d * 2)
PRqm = PRq.quotient(mod_polynomial)
PRpm = PRp.quotient(mod_polynomial)
Df = get_accurate_Discrete_Gaussian(sigma_f)
Ds = get_accurate_Discrete_Gaussian(sigma_s)
De = get_accurate_Discrete_Gaussian(sigma_e)
m = []
base = int.from_bytes(flag, byteorder='big')
while base > 0:m.append(int(base % p))base = base // p
m = PRz(m)s = vector([PRz(My_generator(Ds, d)) for _ in range(n)])
e = PRz(My_generator(Ds, d))
open('data.txt', 'w').write('H = ' + str([list(vi) for vi in H]) + '\n' + 'c = ' + str(c) + '\n')
data.txt
H = [[2843*xz^63 + 85*xz^62 + 4520*xz^61 + 78*xz^60 + 11643*xz^59 + 6614*xz^58 + 4474*xz^57 + 9119*xz^56 + 776*xz^55 + 5793*xz^54 + 2138*xz^53 + 2519*xz^52 + 10514*xz^51 + 9964*xz^50 + 6521*xz^49 + 10848*xz^48 + 1755*xz^47 + 10322*xz^46 + 6811*xz^45 + 11786*xz^44 + 6181*xz^43 + 5823*xz^42 + 6122*xz^41 + 12142*xz^40 + 7233*xz^39 + 6265*xz^38 + 11787*xz^37 + 465*xz^36 + 4755*xz^35 + 2294*xz^34 + 2144*xz^33 + 6079*xz^32 + 9945*xz^31 + 108*xz^30 + 4692*xz^29 + 11592*xz^28 + 3321*xz^27 + 1117*xz^26 + 6393*xz^25 + 8536*xz^24 + 1048*xz^23 + 2302*xz^22 + 6446*xz^21 + 8105*xz^20 + 1288*xz^19 + 3186*xz^18 + 747*xz^17 + 8430*xz^16 + 9984*xz^15 + 6482*xz^14 + 6155*xz^13 + 1151*xz^12 + 11861*xz^11 + 8425*xz^10 + 7300*xz^9 + 9975*xz^8 + 2080*xz^7 + 6955*xz^6 + 7368*xz^5 + 8106*xz^4 + 11950*xz^3 + 913*xz^2 + 4287*xz + 1141], [265*xz^63 + 3391*xz^62 + 1931*xz^61 + 1440*xz^60 + 7587*xz^59 + 2319*xz^58 + 10450*xz^57 + 379*xz^56 + 2766*xz^55 + 1467*xz^54 + 9648*xz^53 + 4414*xz^52 + 4897*xz^51 + 11816*xz^50 + 8692*xz^49 + 7519*xz^48 + 8238*xz^47 + 1975*xz^46 + 8454*xz^45 + 6737*xz^44 + 11645*xz^43 + 7319*xz^42 + 1929*xz^41 + 5687*xz^40 + 9480*xz^39 + 11811*xz^38 + 5272*xz^37 + 2643*xz^36 + 576*xz^35 + 10186*xz^34 + 3258*xz^33 + 2902*xz^32 + 6733*xz^31 + 10270*xz^30 + 12230*xz^29 + 12122*xz^28 + 4927*xz^27 + 8868*xz^26 + 1559*xz^25 + 7925*xz^24 + 2508*xz^23 + 6085*xz^22 + 6503*xz^21 + 9088*xz^20 + 9683*xz^19 + 2312*xz^18 + 4106*xz^17 + 1151*xz^16 + 273*xz^15 + 1892*xz^14 + 5438*xz^13 + 9533*xz^12 + 10530*xz^11 + 10054*xz^10 + 10006*xz^9 + 985*xz^8 + 6387*xz^7 + 10149*xz^6 + 1797*xz^5 + 3033*xz^4 + 1446*xz^3 + 11397*xz^2 + 10717*xz + 1416]]
c = 7635*xz^63 + 1534*xz^62 + 9618*xz^61 + 4546*xz^60 + 6159*xz^59 + 10395*xz^58 + 11714*xz^57 + 3269*xz^56 + 6296*xz^55 + 9108*xz^54 + 5537*xz^53 + 651*xz^52 + 6929*xz^51 + 5488*xz^50 + 8300*xz^49 + 5213*xz^48 + 12047*xz^47 + 9993*xz^46 + 11823*xz^45 + 3490*xz^44 + 678*xz^43 + 4959*xz^42 + 9860*xz^41 + 10996*xz^40 + 6067*xz^39 + 10514*xz^38 + 5232*xz^37 + 4182*xz^36 + 9022*xz^35 + 2167*xz^34 + 8118*xz^33 + 7651*xz^32 + 2014*xz^31 + 9431*xz^30 + 6267*xz^29 + 5133*xz^28 + 2450*xz^27 + 4056*xz^26 + 9448*xz^25 + 4112*xz^24 + 8518*xz^23 + 9126*xz^22 + 210*xz^21 + 10079*xz^20 + 4555*xz^19 + 5448*xz^18 + 1772*xz^17 + 8663*xz^16 + 4925*xz^15 + 6972*xz^14 + 11894*xz^13 + 1421*xz^12 + 10213*xz^11 + 10002*xz^10 + 10890*xz^9 + 1063*xz^8 + 1426*xz^7 + 7368*xz^6 + 7084*xz^5 + 4688*xz^4 + 5728*xz^3 + 9219*xz^2 + 10453*xz + 11673关于格密码， 貌似当时零解。有没有高手试试。