Skip to content

Instantly share code, notes, and snippets.

@maple3142
Last active April 19, 2024 16:43
Show Gist options
  • Star 4 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save maple3142/5a88040d4d3cb09c4505991cf0f1fe98 to your computer and use it in GitHub Desktop.
Save maple3142/5a88040d4d3cb09c4505991cf0f1fe98 to your computer and use it in GitHub Desktop.
LLL/CVP utilities
from lll_cvp import *
from functools import partial
def example1():
# copied from https://github.com/rkm0959/Inequality_Solving_with_CVP/blob/main/Example%20Challenge%204%20-%20HITCON%20CTF%202019%20Quals%20-%20not%20so%20hard%20RSA/solve_challenge_4.sage
## Example 4 : HITCON CTF 2019 Quals not so hard RSA
## d is 465 bits
data = [
(
61608417975397048843788515638593839325111098880518441270527767841153782846066445099077365303960932518098100778959123136871039627996767023258612684873083420234538156646585282154245553305607644427220207313162116929585370583379703086997585339296145409828300576290109728682441066135201997295424597733433471586151,
60032368056605168202792776655067640210910930719068898740685488293392455428589220656480049668823171895161714617099267690524276842795335016835073541061601545456195765907623303970146386500563913899580929779870429659650425339185233299118860275385880359287380867251468679962048998842668813298548390941601249105855,
0x1E4433543AD3EAB1D5A5490E33EE98C34785945C7B69DD0FD0A371C28E5FF45F6627AD0559D9837FD6439367543FF5670F4DF4FD36CBEE75950DB62E51811F98E3F34DB66B07196A5DFBD9867952D8E6D67C43BECF086087181E5F78582E98945E5C8C08D754B998EF01E836729F9620CDCD2CC8AAE9CB4BF3D8E4BEEC3CA8FD,
),
(
52084595054768217522676979342755393306305099169414947960508049057119329537162079071100773540172780699842974838973453517862170568297372572652378982794735495836797191260523386985555538123219596180065060457770169661533302156160201909218943628670173938802399175928847179180982290051008255643478089280887936398779,
15937444970326662770243305998311639639802081677519521519037892156989918335411343952028567001158781869582357356721336548356177945486289103616332672857562241745733313956089488246637981047367689313876169403573606972534488436195086998111247112950511965259280728899941655052549135516189815880662766290132607874671,
0x15DBECED76AB710B84982E67A839846CFE38CFCCCE4DACC585DF0E38D695E1C84EAC7281D8C83B3C6EEBFAE7C27D91496B19DE120374D08CBCCC251A464C2F7BB10FB9D1C1F13B78F1FBFE0CE37D01350978DCB192C92DB43560A9CD81481AA2E2D41A8C5B3C67D3E3AE4BE50DDF37A5A0193DA6F4BEFE71D5348BD7820F1B0A,
),
(
121675354261226402523384817752122501670754379029920951567545832861118347020889141951034949457467042630795199347469665294677977729959566390358589470405088739543312116123816666440234661644847943610733959265939955886506334607329368744886743083353218982597246897307234102346047327550059519916639261619453107169923,
1958149621008109700386193021020256359555810444022322757777842537494487439895477039590251808463946583928481366538370998263830913239177109491659797444270949612728937519312683847609162235917948298810271512469482956117395111528004250206351805086758526770795159863075378020975086922955262230095667701740508170151,
0x5B445089B4578B115B0293CC1922F5FDB784701FD533EEC7EC9BD7FDAD995BAEFB051B9793FF3DADC24FF8D5B52C89F9565F65409C58506C7E79DD787F8E388F019497461FA3DB0EAC5284D398F9E6A1B81C59BA74677CC01C38DDD6461DF029E1179F3EE63CCCE20F3090835B7BD7B4DE25C38CCDDF2EC622CD41FAFB49D68F,
),
(
70820434096887624688036248070441718528107270792728727307197623356369639890276828895683705436125317302252834211775910545775001651922925694194466935425170969939539346172633115232030274859268960310846965871663926227518137713901150141826470260092611613639370170779217268337906342955347156686598981918675591938393,
6264211827826908864953215815104077572906230669747226774603059704547415338199956437981145121700015020477626176620200121575740530313039227764537541481272011717745292622796843631960318813842515397395192806936521180850750841260559451018598913158548097304919304754876270597286947644956943158352022152801127867879,
0x4F56516D8E197A8FD6ED76433A836635DD5AD1247BE9CCBB5A88EA940F5746221B4BB5B60EF925019A11D36FBE8F1D948E9AFB4305937D7E017148B8BA324682D60ED6FB7F3DE80031432023BBEF81A96D0C1BD26C3A728BC6FDEBBD48BF86B93325584C1A1386E26374C9747754B858A01B73996CEA8FE4EDD2A8130504E63E,
),
(
82396665631738285668995082087133930047188890932442133336046256534530991902128696466596278088102928917626464109384091264437455382690583003229076491363732222934817133536320704449557698925700841043105303694696203472531025908797520768019280257689521302427077849286757365739653728248123114986191011560571298134089,
77541341309162852568860774868359137598587882474829780783306540898574011860779494674673722444562346968736216806881154962981695851598965376893425170303668270087989094501452417979429678869102952038600630142304872749698942475289176861137563927160985001506014089253274664444041660282426708388957971134224538326179,
0x6B35DFFADD327C0999EFC909A3C1D1482C6A286808801095EEC5EA88224467881B4081C1AEF02C273CC5DC4D3505DC50FCF4CE60052B6A5A9DC005FAAD4709FBCCA254C6FC1C552D51C8E15FBD8FC404B0136758E1BA57F6C04B1049E303A43AE60C1EB0B671289F6689D1CD104C407549C1BCFC081A28A3F3324A1611E81555,
),
(
64885222129962661919689742957615146346855998523264787345799887210230045803423356080820154546050540728264000944692170729880161760807788699983366314269171423680987673788784023826885067996007133127166699735414920427997399513922777341273346196540175237091469555617281522541592407225697228219483666768990986901207,
47625666889348051674457306461777570860477708163951567694477110559722255361844497439523737482859577232793119885759760321686098657292699849459852343686370029321619072315457562131610624443702007471950020751311592439673932509558946203816066868221203483167079506399876187240483994566182748627389022243608934595071,
0x0F79419A86361D668CED50FBCFA521C5117F7B2F72C3CC248DBA4B2B1C9E7DC3A32FA500F5167A0360AEEFCB8DAA973BC67B0537D641617C2D96D98EE27179DE1644B480C120B2D14054DB032B42AF33B23F8182F72CC8E752D6F89D556800F637BC492BD8EB2FB294EEE61BC3C55677066B6962C4D2A1F1896703D446D903F3,
),
(
130307595686638523389042871138355252466828093625912424932382409748014813151912412889866698513547588105179569464359905871041351306187955332098310075195714887141180801001191398677311128761953690562878908997464309620384635922453765468745206262477334243233099872249671186622159533482223573972729351847574480258349,
15517881429792452627724339825487038872077384939873021432131971858090290889497162855962736652640866521963165312583164013911162455865793567436833813352448640307756786561236246631146444590597902995591016928432988304077340670079503467394770901559567924809126517090243024890436892801283564005789256977822007581731,
0x69A8E0BB49427F3465C9F3A41A22E047BD348C886CDB07264A321F8B890BB48CD7A878E43C1EB4B2F496DAFB50677B3EEA032C8F7F2EE59695398C56CC3B183BB6E2F1AB2D5D633461A6592CA0C98C0F2DAE4100D6AAAF0D1166BDD46BEB68B07D9C9CF6C5A92EF7DB019DC065B3A8300CA25B50CBA51A3294D954C178BF3770,
),
(
65386448419573832864151040666988491321490532636782967162806795276671017479566436411594017000387653366263378617189553041765586083217125727980734225153709370447270596363822524978426540069479632490507360491377612488876553715272119578498102854909764339676652952568021321118127618560269626549257296451954041925283,
62417639911670877600600895776941278119707067464948560335387709799367122896567813566638216057171867961437006927011778910808189676129022776796728833211435603542364704330783289218396426543693678813151580911213239650850603907199690825764030369692366216968117035006819175280930722880390482701178418013436415892711,
0x2231E71788FE0FEC78ADA4F24A58BBAA5B1A0FB48DC94B18BF7409637DBCFD8E2755D80B5E4B309E20A69474A6E2EB245E40C1B3F81C6151DBF7E6871E90A9616A32F4A8443D30BFAAFF5D711BE39BC8F38C13234AF9FD867F508B8A6B097A49FB07A1392EC08C38F0939620CF644EC6631F7566B6BC7A1F1D01A9C736ECEDA4,
),
(
131618812326147470215836136712095159211663684841466199972335887950664101678748935713203393931245541362772506324940879455504378545672259298894346211770983161798960234145317156224604949365110464634198678301644727985645228605590810190481288852412139519629077007437022950591320600450976104529132138396249413028099,
14318453997383587408499979509282945054981178882287936277795320451723285671391694914929520724692059461777785480850364952738183846512279857119933447174333240691522012746191524101263192457454032837995702952840654708026147079321112397181981380295129696518148352311994008219805602114421675331461920408832158576071,
0x71A370974F020D338071E2B0480F38F2D5B488252F5EB206636D6DCD3C93EA586A507C29D2E611A9A8D5D0F849B913116B37E69345D6EAE71CF87CDB6B74E75BCCDB374C372562777A727F07E4272A5FF17B451D582074B565879453D028C5E9B91CB67AE923F0F09492E508422E65C1DAADA0564D91A9FEEC094AF77AB190FA,
),
(
99041226655569332839951771030354960649881033648844611842019981984694036670092050113949713459076512100815903654289240773362239468428010238444408944822516190193861719380849620966232652503444079295871086550223067647300451354087943235559953597249075277760677450645744584993036921709483731953822197438848939991653,
45917328654051873455626365238806652384056265616606200025887647202756379007355041189714541493038574645714670682101129613041399879280497291675656671383417575172090283625761438606371062142083212903854592596935358334738253893062615061401134834123551055465985828525720791523020773994634134135284036947641526947783,
0x336E810E66EEAC255F1714B290187773DE92EC044B654A4CC0EEF2070E9D8D86FA37D424B2E4B71FD135E634034E06DBC31E77BD13D470AA5D3E5DCC5E689B565178A4A445D4560F5569967315A0BBE163EF83063429EC8D1FBBA1A8DBD9E30A2A67E17793F8B19E7B184C3B989DADC85B7F060E3DAEFB66FF803C98BDA8862F,
),
]
## each data has n, e for fixed d
## ed = k(n-p-q+1) + 1 -> ed + kn == k(-p-q+1) + 1
## construct a bound on k(-p-q+1) + 1
## 2 sqrt(n) <= p + q <= 3 sqrt(n/2)
## (e * 2^464 - 1) / (n - 2sqrt(n) + 1) <= (e * d - 1) / (n - 2sqrt(n) + 1) <= k
## k <= (e * d - 1) / (n - 3sqrt(n/2) + 1) <= (e * 2^465 - 1) / (n - 3sqrt(n/2) + 1)
## combine these to get a decent bound for k(-p-q+1) + 1
## 11 variables, d, and k for each 10 equations
## 11 equations, bound on d and each bound on ed + kn
# build matrix
M = matrix(ZZ, 11, 11)
lb = [0] * 11
ub = [0] * 11
# encode d
M[10, 10] = 1
lb[10] = 2**464
ub[10] = 2**465
# encode ed + kn
for i in range(0, 10):
M[10, i] = data[i][1] # e * d
M[i, i] = data[i][0] # k * n
low_sum = int(2 * (data[i][0] ** 0.5))
high_sum = int(3 * ((data[i][0] // 2) ** 0.5))
low_k = (data[i][1] * (2**464) - 1) // (data[i][0] - low_sum + 1)
high_k = (data[i][1] * (2**465) - 1) // (data[i][0] - high_sum + 1)
lb[i] = high_k * (-high_sum + 1) + 1
ub[i] = low_k * (-low_sum + 1) + 1
res = solve_inequality(M, lb, ub)
recovered_d = res[10]
n = data[i][0]
enc = data[i][2]
ptxt = pow(enc, recovered_d, n)
print((int)(ptxt).to_bytes(128, byteorder="big"))
def example2():
# modified from https://github.com/rkm0959/Inequality_Solving_with_CVP/blob/main/Example%20Challenge%207%20-%20ACSC%20Share%20The%20Flag/solve_challenge_7.py
p = 251
X = bytes.fromhex("02d4623be12c8f01cb2ebe5f837c1d")
Y = bytes.fromhex("bbdc06ceb34da7b16336b007dc5492")
X2 = bytes.fromhex("2fb9e753b237e68d35e266b0f01c9e")
Y2 = bytes.fromhex("20c0be9140f5a33d71b9e82f8f9409")
X3 = bytes.fromhex("f42e3ee10edeade0a3804a22e86a63")
Y3 = bytes.fromhex("c7224da73d9d96254f94136d9a65f1")
X4 = bytes.fromhex("37c9b07870283dd3f6198c46f027dd")
Y4 = bytes.fromhex("8101a88a365526e8faf417b79599a0")
X5 = bytes.fromhex("b0342cb7b3f5a022d927f9019a1bf3")
Y5 = bytes.fromhex("e2666d892955494775aa3c96c441f5")
X6 = bytes.fromhex("e56bf4f9e746252dbacb93a0a95087")
Y6 = bytes.fromhex("cbb43831857333b2c4663ba2c9189a")
X7 = bytes.fromhex("99ca36b1633cf3d903d8e6291f1bdc")
Y7 = bytes.fromhex("25180068651818171d10422dbdb395")
M = Matrix(GF(p), 105, 128)
vec = []
for i in range(105):
x, y = 0, 0
if i < 15:
x = int(X[i])
y = int(Y[i])
elif i < 30:
x = int(X2[i - 15])
y = int(Y2[i - 15])
elif i < 45:
x = int(X3[i - 30])
y = int(Y3[i - 30])
elif i < 60:
x = int(X4[i - 45])
y = int(Y4[i - 45])
elif i < 75:
x = int(X5[i - 60])
y = int(Y5[i - 60])
elif i < 90:
x = int(X6[i - 75])
y = int(Y6[i - 75])
elif i < 105:
x = int(X6[i - 90])
y = int(Y6[i - 90])
vec.append(y)
for j in range(16):
M[i, j] = (x**j) % p
if i < 15:
for j in range(16):
M[i, j + 16] = (x ** (j + 16)) % p
elif i < 30:
for j in range(16):
M[i, j + 32] = (x ** (j + 16)) % p
elif i < 45:
for j in range(16):
M[i, j + 48] = (x ** (j + 16)) % p
elif i < 60:
for j in range(16):
M[i, j + 64] = (x ** (j + 16)) % p
elif i < 75:
for j in range(16):
M[i, j + 80] = (x ** (j + 16)) % p
elif i < 90:
for j in range(16):
M[i, j + 96] = (x ** (j + 16)) % p
elif i < 105:
for j in range(16):
M[i, j + 112] = (x ** (j + 16)) % p
vec = vector(GF(p), vec)
bas = M.right_kernel().basis()
print(len(bas))
v = M.solve_right(vec)
# v + bas -> all in 97 ~ 122
M = Matrix(ZZ, 151, 151)
lb = [0] * 151
ub = [0] * 151
for i in range(23):
for j in range(128):
M[i, j] = int(bas[i][j])
M[i, 128 + i] = 1
for i in range(128):
M[23 + i, i] = p
for i in range(128):
if i >= 16:
lb[i] = int(97 - int(v[i]))
ub[i] = int(122 - int(v[i]))
else:
lb[i] = int(32 - int(v[i]))
ub[i] = int(128 - int(v[i]))
for i in range(23):
lb[i + 128] = 0
ub[i + 128] = p
from functools import partial
res = solve_inequality(
M,
lb,
ub,
cvp=partial(kannan_cvp, reduction=lambda M: M.BKZ(block_size=20), weight=251),
)
print(vector(lb))
print(res)
print(vector(ub))
flag = ""
for i in range(16):
flag += chr((res[i] + int(v[i]) + 251 * 30) % 251)
print("ACSC{" + flag + "}")
# ACSC{wOAdvfst41xJzG6r}
def example3():
# modified from https://blog.maple3142.net/2021/10/11/pbctf-2021-writeups/#seed-me
from operator import xor
class JavaRNG:
# about the detail of java 17 rng
# https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Random.html
def __init__(self, seed):
self.seed = seed
def next(self):
self.seed = self.seed * 0x5DEECE66D + 0xB
return self.seed
Z = Zmod(2**48)
P = PolynomialRing(Z, "s")
s = P.gen()
aa = []
bb = []
zz = []
rng = JavaRNG(s)
for _ in range(16):
for _ in range(2047):
rng.next()
z = rng.next()
# print(z)
zz.append(z)
b, a = z.change_ring(ZZ)
aa.append(a)
bb.append(b)
# print(((ZZ(z(xs)) >> 24) / (1 << 24)).n())
M = 2**48
B = block_matrix(
[[matrix([1]), matrix(aa)], [matrix(len(aa), 1), matrix.identity(len(aa)) * M]]
)
# manually changing parameters...
vlb = [M - 3100000000000 for _ in range(len(bb))]
vlb[0] = M - 2900000000000
vub = [M - 2100000000000 for _ in range(len(bb))]
vub[-1] = M - 2400000000000
lb = [0] + [v - b for v, b in zip(vlb, bb)]
ub = [2**48] + [v - b for v, b in zip(vub, bb)]
res = solve_inequality(matrix(B), list(lb), list(ub))
s = ZZ(res[0])
for z in zz:
r = ZZ(z(s))
o = ((r >> 24) / (1 << 24)).n()
print(o, o > 7.331 * 0.1337)
print(
xor(s, 0x5DEECE66D)
) # Java RNG will xor your seed with 0x5DEECE66D when setting seed
# known good seed: 272404351039795
def example4():
n = 10
pub1 = random_vector(ZZ, n, x=1, y=2**256)
pub2 = random_vector(ZZ, n, x=1, y=2**256)
secret = random_vector(ZZ, n, x=1, y=2**64)
t1 = pub1 * secret
t2 = pub2 * secret
print(
solve_underconstrained_equations(
matrix([pub1, pub2]).T, vector([t1, t2]), [0] * n, [2**64] * n
)
)
print(secret)
def example5():
# https://github.com/maple3142/My-CTF-Challenges/tree/master/ImaginaryCTF/Round%2030/Easy%20DSA:%20LCG
from fastecdsa.curve import secp256k1
from hashlib import sha256
from Crypto.Cipher import AES
G = secp256k1.G
q = secp256k1.q
# fmt: off
p = 9927040122486684509203958106419420141058188722199373989012953585197167125223276141324574147521754273735827724127795605194092299982453828901469369136978219
sigs = [(98078224267884884220741740422077019843954009281647502734600509731511013529371, 54523865988310606978987830048871561792183822750263202533230451076893555969316), (104372973739209868434840748268723094332969140159620819033951611727659419363988, 39660851627725578124743718742328950528148285144862142963822549722002689280409), (103919709879086855178251181244489637133481828592253195107866903154222896468253, 35031204282583023574328215246485186335362731664384171126097342931654133207246), (63175283280752608661708773461972110889312169792285211062806717970617630555061, 34712080692439206749112321272818736084925608248138548106200594874651099131535)]
ct = b'\xe6\x9c\xcaZ\x01\x90-\xa0\xbc8\xeb\xe4\xc6\xc7b\x16\xb9t++@\xc0\x0ce\t\x9e\xb5\x07p\xe49*\xb8\xce\xfe@\xea%\xc9\xd6\xefF\xf8\x7fQ\x9bg\xbd\x7f\xcf{h\\^\x11\xf9\xf5\xe8\x7f}\x94\xd3+\x06\x19.`\x84\x8d)\x1e\xdey\xe4 [\x9e'
nonce = b'Z\x1c\xba\xbc\x95\\\xe1u'
# fmt: on
msgs = [
b"https://www.youtube.com/watch?v=S8MJvhgjXBY",
b"https://www.youtube.com/watch?v=wSTbdqo-j74",
b"https://www.youtube.com/watch?v=dkYHgxfQZBA",
b"https://www.youtube.com/watch?v=p8ET-m6y6VU",
]
ss = []
for m, (r, s) in zip(msgs, sigs):
z = int.from_bytes(sha256(m).digest(), "big") % q
ss.append((z, r, s))
a, b = G.x, G.y
syms = "d," + ",".join([f"k{i}" for i in range(len(ss))])
R = ZZ[syms]
d, *ks = R.gens()
# collect equations
eq_p = []
eq_q = []
for (z, r, s), k in zip(ss, ks):
eq_q.append(s * k - z - r * d)
eq_q = [f.resultant(g, d) for f, g in zip(eq_q, eq_q[1:])]
for k, kk in zip(ks, ks[1:]):
eq_p.append(a * k + b - kk)
# solve!
eqs = eq_p + eq_q
mods = [p] * len(eq_p) + [q] * len(eq_q)
lb = [0] * len(ks)
ub = [2**512] * len(ks)
ks = solve_multi_modulo_equations(eqs, mods, lb, ub)
z, r, s = ss[0]
k = ks[0]
d = (s * k - z) * pow(r, -1, q) % q
# get flag
key = sha256(str(d).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CTR, nonce=nonce)
print(cipher.decrypt(ct))
def example6():
n = ZZ(getrandbits(2048))
roots = [ZZ(getrandbits(128)) for _ in range(3)]
x, y, z = PolynomialRing(ZZ, ["x", "y", "z"]).gens()
f = randrange(1, n) * x * y + randrange(1, n) * y * z + randrange(1, n) * z * x
f -= f(*roots)
f %= n
g = randrange(1, n) * x**2 + randrange(1, n) * y**2 + randrange(1, n) * z**2
g -= g(*roots)
g %= n
eqs = [f, g]
bounds = {
x: 2**128,
y: 2**128,
z: 2**128,
}
for monos, sol in solve_underconstrained_equations_general(n, eqs, bounds):
print(monos, sol)
if sol[-1] < 0:
sol = -sol
if sol[-1] == 1:
polys = [f.change_ring(QQ) for f in sol - monos if f]
I = ideal(polys)
print(I.variety())
print(roots)
def example_flatter():
# https://github.com/maple3142/My-CTF-Challenges/tree/master/ImaginaryCTF/Round%2030/Easy%20DSA:%20LCG
from fastecdsa.curve import secp256k1
from hashlib import sha256
from Crypto.Cipher import AES
G = secp256k1.G
q = secp256k1.q
# fmt: off
p = 9927040122486684509203958106419420141058188722199373989012953585197167125223276141324574147521754273735827724127795605194092299982453828901469369136978219
sigs = [(98078224267884884220741740422077019843954009281647502734600509731511013529371, 54523865988310606978987830048871561792183822750263202533230451076893555969316), (104372973739209868434840748268723094332969140159620819033951611727659419363988, 39660851627725578124743718742328950528148285144862142963822549722002689280409), (103919709879086855178251181244489637133481828592253195107866903154222896468253, 35031204282583023574328215246485186335362731664384171126097342931654133207246), (63175283280752608661708773461972110889312169792285211062806717970617630555061, 34712080692439206749112321272818736084925608248138548106200594874651099131535)]
ct = b'\xe6\x9c\xcaZ\x01\x90-\xa0\xbc8\xeb\xe4\xc6\xc7b\x16\xb9t++@\xc0\x0ce\t\x9e\xb5\x07p\xe49*\xb8\xce\xfe@\xea%\xc9\xd6\xefF\xf8\x7fQ\x9bg\xbd\x7f\xcf{h\\^\x11\xf9\xf5\xe8\x7f}\x94\xd3+\x06\x19.`\x84\x8d)\x1e\xdey\xe4 [\x9e'
nonce = b'Z\x1c\xba\xbc\x95\\\xe1u'
# fmt: on
msgs = [
b"https://www.youtube.com/watch?v=S8MJvhgjXBY",
b"https://www.youtube.com/watch?v=wSTbdqo-j74",
b"https://www.youtube.com/watch?v=dkYHgxfQZBA",
b"https://www.youtube.com/watch?v=p8ET-m6y6VU",
]
ss = []
for m, (r, s) in zip(msgs, sigs):
z = int.from_bytes(sha256(m).digest(), "big") % q
ss.append((z, r, s))
a, b = G.x, G.y
syms = "d," + ",".join([f"k{i}" for i in range(len(ss))])
R = ZZ[syms]
d, *ks = R.gens()
# collect equations
eq_p = []
eq_q = []
for (z, r, s), k in zip(ss, ks):
eq_q.append(s * k - z - r * d)
eq_q = [f.resultant(g, d) for f, g in zip(eq_q, eq_q[1:])]
for k, kk in zip(ks, ks[1:]):
eq_p.append(a * k + b - kk)
# solve!
eqs = eq_p + eq_q
mods = [p] * len(eq_p) + [q] * len(eq_q)
lb = [0] * len(ks)
ub = [2**512] * len(ks)
ks = solve_multi_modulo_equations(
eqs, mods, lb, ub, cvp=partial(kannan_cvp, reduction=flatter)
)
z, r, s = ss[0]
k = ks[0]
d = (s * k - z) * pow(r, -1, q) % q
# get flag
key = sha256(str(d).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CTR, nonce=nonce)
print(cipher.decrypt(ct))
if __name__ == "__main__":
example1()
example2()
example3()
example4()
example5()
example6()
example_flatter()
from sage.all import (
matrix,
vector,
matrix,
block_matrix,
Sequence,
ZZ,
diagonal_matrix,
)
from subprocess import check_output
from re import findall
def build_lattice(mat, lb, ub):
n = mat.ncols() # num equations
m = mat.nrows() # num variables
if n != len(ub) or n != len(lb):
raise ValueError("Number of equations must match number of bounds")
if any([l > u for l, u in zip(lb, ub)]):
raise ValueError("All lower bounds must be less than upper bounds")
L = matrix(ZZ, mat)
target = vector([(l + u) // 2 for u, l in zip(ub, lb)])
bounds = [u - l for u, l in zip(ub, lb)]
K = max(bounds) or L.det()
Q = matrix.diagonal([K // x if x != 0 else K * n for x in bounds])
return L, target, Q
def flatter(M):
# compile https://github.com/keeganryan/flatter and put it in $PATH
z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
ret = check_output(["flatter"], input=z.encode())
return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))
def babai_cvp(mat, target, reduction=lambda M: M.LLL()):
M = reduction(matrix(ZZ, mat))
G = M.gram_schmidt()[0]
diff = target
for i in reversed(range(G.nrows())):
diff -= M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
return target - diff
def kannan_cvp(mat, target, reduction=lambda M: M.LLL(), weight=None):
if weight is None:
weight = max(target)
L = block_matrix([[mat, 0], [-matrix(target), weight]])
for row in reduction(L):
if row[-1] < 0:
row = -row
if row[-1] == weight:
return row[:-1] + target
def kannan_cvp_ex(mat, target, reduction=lambda M: M.LLL(), weight=None):
# still kannan cvp, but return all possible solutions
# along with a reduced basis (useful for cvp enumeration)
if weight is None:
weight = max(target)
L = block_matrix([[mat, 0], [-matrix(target), weight]])
cvps = []
basis = []
for row in reduction(L):
if row[-1] < 0:
row = -row
if row[-1] == weight:
cvps.append(row[:-1] + target)
elif row[-1] == 0:
basis.append(row[:-1])
return matrix(ZZ, cvps), matrix(ZZ, basis)
def solve_inequality(M, lb, ub, cvp=kannan_cvp):
# find an vector x such that x*M is bounded by lb and ub
# not checked for correctness
# note that the returned value is x*M, not x
L, target, Q = build_lattice(M, lb, ub)
return Q.solve_left(cvp(L * Q, Q * target))
def solve_inequality_ex(M, lb, ub, cvp_ex=kannan_cvp_ex):
# find an vector x such that x*M is bounded by lb and ub
# not checked for correctness
# note that the returned value is x*M, not x
L, target, Q = build_lattice(M, lb, ub)
cvps, basis = cvp_ex(L * Q, Q * target)
Qi = matrix.diagonal([1 / x for x in Q.diagonal()])
cvps = (cvps * Qi).change_ring(ZZ)
basis = (basis * Qi).change_ring(ZZ)
return cvps, basis
def solve_underconstrained_equations(M, target, lb, ub, cvp=kannan_cvp):
# find an vector x such that x*M=target and x is bounded by lb and ub
# not checked for correctness
n = M.ncols() # number of equations
m = M.nrows() # number of variables
if n != len(target):
raise ValueError("number of equations and target mismatch")
if n >= m:
raise ValueError("use gauss elimination instead")
M = block_matrix([[matrix(ZZ, M), 1], [matrix(target), 0]])
lb = [0] * n + lb
ub = [0] * n + ub
sol = solve_inequality(M, lb, ub, cvp=cvp)
return sol[-m:]
def solve_multi_modulo_equations(
eqs, mods, lb, ub, reduction=lambda M: M.LLL(), cvp=kannan_cvp
):
# solve a linear system of equations modulo different modulus
# eqs: a list of equations over ZZ
# mods: a list of modulus
if len(eqs) != len(mods):
raise ValueError("number of equations and modulus mismatch")
if len(lb) != len(ub):
raise ValueError("number of lower bounds and upper bounds mismatch")
M, v = Sequence(eqs).coefficient_matrix()
assert v.list()[-1] == 1, "only support equations with constant term"
A, b = M[:, :-1], -M[:, -1]
M = A.dense_matrix().T
nr, nc = M.dimensions()
L = M.stack(diagonal_matrix(mods))
L = L.augment(matrix.identity(nr).stack(matrix.zero(nc, nr)))
lbx = b.list() + lb
ubx = b.list() + ub
return solve_inequality(L, lbx, ubx, cvp=cvp)[-len(lb) :]
def solve_underconstrained_equations_general(
n, eqs, bounds, reduction=lambda M: M.LLL()
):
# given a underconstrained list of polynomials over Z/nZ
# where the unknown variables are bounded by some bounds
# bounds should be a dict mapping variable x to an positive integer W, such that |x| < W
# non-linear monomials will be linearized
M, monos = Sequence(eqs).coefficient_matrix(sparse=False)
L = block_matrix(ZZ, [[n, 0], [M.T, 1]])
bounds = [1] * len(eqs) + [ZZ(m.subs(bounds)) for m in monos.list()]
K = max(bounds)
Q = diagonal_matrix([K // b for b in bounds])
L *= Q
L = reduction(L)
L /= Q
L = L.change_ring(ZZ)
for row in L:
if row[: len(eqs)] == 0:
sol = row[len(eqs) :]
yield vector(monos), sol
__all__ = [
"build_lattice",
"flatter",
"babai_cvp",
"kannan_cvp",
"kannan_cvp_ex",
"solve_inequality",
"solve_underconstrained_equations",
"solve_multi_modulo_equations",
"solve_underconstrained_equations_general",
]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment