1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122
| from sage.all import * proof.arithmetic(False)
p = 0x95a599ab706381e861caf2c6e757204c704b77a38592ae0db282000d8537ab0e4608ecd9a524ad6e14eb9564353b5c1036ff13c8503bfad7e8695d0bcf15df766c1be64aa4e73b75e0ecb28ea9e74eafc613d2fb9299fac060826bd071a92d2bd5be44d6d65e6b63146d617e800b79e25358b4a3e22a62457f2d39c21a694f54c03ad5d69a674fa6cd91c2971524152c1b6d177c455e0f255ce4fa18253da252613959c17b49ac422a9009933d0c59210646fca85e8ae35d5df34d6afde9d951909585c3f3e53e06ef5ae319fa035e57941599c2a73133bba490b66ab38e7537fd3ed322bf3a0431f02f276b5b18b623865883e3f0b67a511293b5a7576c97e6663cb1c32bdff5cda825549742d067e1b4ca847c75ef6b601feced3a9bb4dea41f1e5c40a8f2af2983f010d7bbc9ba992cedcdac6922a056d52873af110ae578da5e875fa6a121cdb45fe5e8198c121f7e9609d100d023a9155d6aa9efe28aa9036079564780db663aad36796ee8349b98b11d1b108125 F = GF(p)
x0 = F(0x93436a2bdfecc923d69385f164ef891ef5b08418e5b4e65c980e0b054e86ee8b8e24a527dad9fe3883234179167ada4b5f413c07c548f3dc224db1f2791c8a44bb857c722676d621fa07ad4beee4dc2be679c351cc19423aaff444e5c908b767d9ebec006bf0f020b8c0d15775fc84524333c47d4bc46ae8bd3cb18e1b037e59a388e39a81c1d97c9654742979ed54741df9aba6954c2801efb63d91ed1a51889ee1e8848b7bf111c987cb558e08b9caa17e50f578fa0af70bf855393dcc6c52420897eae663700818dbec237e094c1d4904a249d92702ab4046e52694db73a5fb83953262dff0251fa5fd1b4a99fb70addcde2a38d8766e02360b7b29aad1382ecdd63650f2b597469267dccc11ee7d0b10178c68a02b2d03db5bfcd6d663c11bc2ef855e30528aec48a9f4f53f71c52ac6e0c92fcaf0f8576982b1135bbb15fb5035c7853de51b8aa5b858646dd23b7b01d837c6b3c38f4bdcef6009ee02456bbdcbe8978eb400326c4fd0a899ed9f559ba963b25317) y0 = F(0x47b8c9d33929bfe12657a2f482213cca803fe37e8485ebde814dc91ce56ed480cea04f24176edce77ebfd7d9bba3a864cfe6176ef1d68ebc184dcde0667704adc472d1d16688affa657cff460edf05f92dad743ca3421150ec7ef98e08a9d17af033a555ed49f0e9c7457bf339a9270e8b44b7b75dd43afd27614d0ce59878c019d902d9ed23a26f04a431130534f85b05db586fd9a65a178204eb7d568a0e64dd16a369d2af6f2b8cd32a9e9be8322885c78a30dc8019ca3c48f39bad38de4ab60970ee1c44688d2afa901f46af7d2e7ced0e34204d6b38330fd87d6bf5bb61378e092780a48b985654de1c65b0a6146a82f84bfe09359820942980ce5c607bfc14497a79436bc4f351ae697875d93049c30dafc698208a17f9b785aa35448e4ef341102053c62a9923287f4cf597ff492fd0eac4ef77ae879a22c6c8a3a53baef09f574316fd872e1a6dd1ad9eb72a3e39f925e25fe06f7983b785dcb110bd127c8e2736e7345fd7ffce687c66c492a541e00c500574) x1 = F(0x37a181d88a683e2eeba3147bfb3043be6067fc722b8578255e25a335fadda9ead31c41d7742dbf3df7e4c3effc9297ef528730b3d8920978e342e123b9f19ab15a5ed2c19c45aaee728e53acd8c44e7543c4b9bcd40f27b8efac1a1e431ddbab15b4341c6cc817516634c2ab1117e784e429b9f797963b18442127342455d469ca9d9ff24b241afe9b7fdd4b91bb9750710e6f00b9fe631c1db71c308ef4642251fc00d0433910161d588c100944d55935ddf7dc656cc1670065c5bc6607358304c228f8495cca579a3a78102b4e617687f3aad0c5826e3aa7a85c85c99af2254002d3578c0af342ea1f49b9a425eba90e2473470fec77a945b45cf67dde9cb4e0ef445b974164cbcb61ec7cbcd77c94d42c6dce15ae500e4b6b15d38923ba2773176ae1e3354baaae47b422ec0ff8273538ad0a6a03a33d60a52257698130f6db6baaa4d338e167443eb4ac1b57b0d6f424e9d0b2f6b6b0df609b81150928286443afe7d1b9bbb30389af0db1597945d233cd19121d11) y1 = F(0x7696ea73e7345896be516aac44aa8ba35242babc3853a2a3fbf7081a3f5a845dba81f01d7aba946f7a9886eb1918d367baa87f387e86e095bb88bbc44f58768e8c2db3a1926301c984ea19f8e680fb7f4f7108c4c8565fc7cb66284bdf81e547e446faa80e88a59ceae3bb43b2c6ac1f8858e5f126fcc224f62aef611184d714db86a5c19060e0a9844def0e047d3a46e9d64f42c0cef9f85812068d580f9722b1520c2847b34c6ed7afc89b633113606aa397c10f1ea653e4d15fb160f2c1d4750a6c4eaef7e6fa56c35d393fe7d3ef91fc9ea56a69fd9614e8c39da6dc0981c6004468db1d81a13ebaf3bfd9e640c39b63b107605ba28a5c18b4a03ca627102ff63ddc8483dce2c06e97f614a4d93f9d615f849a6ce0c164217dabe849ceaf1ade997700daf9aca95f7811cc615cf61887e199ddf963a780829cc186b96d96f2b3c1f001eaa0e289b7fc79e5c24ce2aad55f9adb9ecaacba5445773222aee3cf997c171f7bcbcba65caa6c254186a1fa1982521d8ab1) x2 = F(0x3117ba57d46bd2da19fed7e3f087ec252b45340c1a338a5096a94538be0f9776388ec70cc22c475968a352f2a34f1637b660aea2f5a741d925d550b9bc91f3b5da0e9b6585aee5413d89f6734651439f7c6905c2b98b7e4aef425a50852b626ad7bd2a4f67909acc0d6ac7e33688f3cf676ac3c00a32e12eecb384cd9b099244c2ef37f054a271a2c174f3eac5553415b097ee84b590258df022d1142b28be0ca756784bfae2e42a1bf98a3c48ea9baa2466172673b978d1372a2ac5e20ff869dacbbfe0f56d4d4de947d39a5bb643cd3b00c1e6d4b82e090105358fc105f75ee1dec962696ef406474d5934ed27e375952012bf797ebd8fff2d4b08935086850fc89039b3c4c0ab712a9859c6e43dad3fae4c5048d60a5069c338a63ac49f3a7fa99614bd8a17a9522c82333ecaf88c41b0b8be60ebee5b52df4d853ef397786a113b5064e236299e795dbec72baf001c6dd973e424e86e79368d6b10f3b43a47eb8fae6e48c2b42aa7e2566879f9b675e4837a59366b) y2 = F(0x1e6d85c241d60abc738c606cc4237a617f7a341934d59cd0a3becbb1f4acdc740673a84df7646d1afd08d0d132d8188a35eca0ca8bee5208b73b141de1c4a4a254c6f6278f6860d8d40d9eb301281373dadb1e9bfbeeaa4b0b1ef48b787b47a490cce2f2c64d03a61036ebe565fe4f93dec2e030ecf1a91d1c65b82dfca045b07c526a87293d4844d92327669ca19a2a2e62d4e6e9d46d24d0994434e52f2ea1e9492d46039959afa75365d88e90ab13097f075c4a93d102514cac901ca760155152788e5d352c09e012f6d87fb262d3db9174014c2d9c88e289c902700dc202b05c0600b3f96be0ffc10ae58738718fee7c21e387ddf390a9a1e26a6cb2b744971b67621c1211f0127969a969318beb60a361b924db7707b4170ed3af22dc412d15eb71c553dc79dbebc238dc2baecea806351288b05db9f6885cc53af7509aa3c810540e648ff5e94ba75bf0dbf097d515babe0f99dcd4ddcc10f7a6549a3f12148ca51e4f4f5ab16bf0cb5c069b2cd87c1738bce308)
BITS = 32
R = PolynomialRing(F, names='aa1, aa2, bb1, bb2, a, b') aa1, aa2, bb1, bb2, a, b = R.gens() bounds = dict(aa1=2**BITS, aa2=2**BITS, bb1=2**BITS, bb2=2**BITS)
eq0 = x0**3 + a*x0 + b - y0**2 eq1 = (x1 + aa1)**3 + a*(x1 + aa1) + b - (y1 + bb1)**2 eq2 = (x2 + aa2)**3 + a*(x2 + aa2) + b - (y2 + bb2)**2
def resultant(p1, p2, var): p1 = p1.change_ring(QQ) p2 = p2.change_ring(QQ) var = var.change_ring(QQ) r = p1.resultant(p2, var) return r.change_ring(F)
poly = eq0 poly1 = resultant(poly, eq1, b) poly2 = resultant(poly, eq2, b) poly = resultant(poly1, poly2, a) poly /= poly.coefficients()[0] print(poly.monomials())
bits = 0 for mono in poly.monomials(): mono_bits = RR(log(mono.change_ring(ZZ).subs(**bounds), 2)) print(mono, "%.2f" % mono_bits ) bits += mono_bits
n = len(poly.monomials()) m = matrix(ZZ, n, n) m[0] = vector(poly.coefficients()) m[1:,1:] = p * identity_matrix(n-1) def prmat(m): for row in m: print(*[{0: "0", 1: "1", p: "p"}.get(v, "x") for v in row]) prmat(m)
monos = vector(poly.change_ring(ZZ).monomials()) factors = [mono(**bounds) for mono in monos]
[m.rescale_col(i, factor) for i, factor in enumerate(factors)] m = m.LLL() m = m.change_ring(QQ) [m.rescale_col(i, QQ(1)/factor) for i, factor in enumerate(factors)] m = m.change_ring(ZZ)
polys = [] for pol in m*monos: maxval = sum( (abs(int(coef)) * mono).change_ring(ZZ).subs(**bounds) for coef, mono in pol ) print("polynomial with max value", RR(log(maxval, 2)), "bits") if maxval < p: polys.append(pol) print("got", len(polys), "polynomials")
def recover(hs, vars, solbits, padbits=20): nbits = solbits + padbits from itertools import product sols = {(0,) * len(vars)} polys = [h.change_ring(Zmod(2**nbits)) for h in hs] for i in range(nbits): print("bit", i, "/", nbits, ":", len(sols), "candidates") sols2 = set() mod = 2**i polys = [h.change_ring(Zmod(2*mod)) for h in hs] for bits in product(range(2), repeat=len(vars)): for sol in sols: sol2 = tuple(ss + bit*mod for ss, bit in zip(sol, bits)) if any(poly(*sol2) for poly in polys): continue sols2.add(sol2) sols = sols2 if not sols: print("fail", i) return print("sols?", i, len(sols)) for sol in sols: sol = [v if v < 2**(nbits-1) else (v-2**nbits) for v in sol] if any(abs(v) >= 2**solbits for v in sol): continue if any(poly(*sol) for poly in hs): continue yield sol R = PolynomialRing(ZZ, names='aa1, aa2, bb1, bb2') polys = [R(pol) for pol in polys] sols = list(recover(polys[:4], R.gens(), BITS))
from struct import pack ct = bytes.fromhex("1df819824bb4299817560c5ee69bd8eaabaf3c47e33a57e39eb1ccddec66d9fb38c6df8ebf35b368ebeecd803d66afb2") sol_aa1, sol_aa2, sol_bb1, sol_bb2 = sols[0] parts = [ (int(x1)+int(sol_aa1))^^int(x1), (int(y1)+int(sol_bb1))^^int(y1), (int(x2)+int(sol_aa2))^^int(x2), (int(y2)+int(sol_bb2))^^int(y2), ] key = pack(">4I", *parts) print(AES.new(key, mode=AES.MODE_ECB).decrypt(ct).decode())
|