Skip to content

Instantly share code, notes, and snippets.

@nomeaning777

nomeaning777/coppersmith.sage Secret

Last active July 27, 2020 01:21
Show Gist options
  • Save nomeaning777/8c8cc446fdf1e7a151ae30d72600c312 to your computer and use it in GitHub Desktop.
Save nomeaning777/8c8cc446fdf1e7a151ae30d72600c312 to your computer and use it in GitHub Desktop.
Download ZIP
DEFCON CTF 2020 Writeup
Raw
coppersmith.sage
import nclib
import base64
import rsa
from ctypes import CDLL
nc = nclib.Netcat(('coooppersmith.challenges.ooo', 5000), verbose=True)
nc.recv_until(b':')
nc.write(b'0' * 105 + b"1" + b"0" * 14 + b"\n")
nc.recv_until(b"Your public key:\n")
rsa_key = nc.recv_until(b"-----END RSA PUBLIC KEY-----\n")
rsa_key = rsa.PublicKey.load_pkcs1(rsa_key)
print(rsa_key)
libc = CDLL("libc.so.6")
libc.srand(libc.time(None))
x = libc.rand()
y = libc.rand()
nc.write(str(x+y).encode('utf-8') + b"\n")
nc.recv_until(b'Your flag message:\n')
flag_message = nc.recv_until(b'\n')
n = rsa_key.n
print(n)
p = None
for j in range(64, 192):
for i in range(65536):
if (n - 1) % ((2 ** j) + i) == 0:
p = (2 ** j) + i
print(p)
break
else:
continue
break
print('%x' % p)
assert (n-1) % p == 0
# n = (2p r1+1)(2p r2 + 1)
# n = 4p^2 r1 * r2 + 2p(r1 + r2) + 1
# n / 2p = 2p r1 * r2 + (r1 + r2)
rem = (n - 1) // (2 * p) // 2 // p
print(len(bin(rem)))
fac = factor(rem)
def search(fac, i=0, cur1 = 1, cur2 = 1):
if i == len(fac):
pp = cur1 * 2 * p + 1
qq= cur2 * 2 * p + 1
if n % pp == 0:
return pp
return None
prime, exp = fac[i]
for j in range(0, exp + 1):
ret = search(fac, i + 1, cur1 * prime ^ j, cur2 * prime ^ (exp - j))
if ret:
return ret
print(fac)
p = search(fac)
q = n // p
assert p * q == n
d = lift(Mod(65537, (p - 1) * (q - 1)) ^ -1)
flag = Mod(int(flag_message, 16), n) ^ d
print(repr(int(flag).to_bytes(64, 'big')))
Raw
not-be-fooled.sage
# https://math.boisestate.edu/reu/publications/AnomalousPrimesAndEllipticCarmichaelNumbers.pdf
while True:
n = ZZ.random_element(2**200)
p = (n + 1) ^ 3 - n ^ 3
if is_prime(p):
break
for i in range(1,100):
E = EllipticCurve(GF(p), [0, i])
if E.order() == p:
print(0)
print(i)
print(p)
g = E.gens()[0]
print(g[0])
print(g[1])
break
Display the source blob
Display the rendered blob
Raw
ooo-flag-shares.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The target vulnerability is that encryption doesn't use modulo operation.\n",
"\n",
" 1. leak p\n",
" * Decryption uses moduluo operation, so gcd of the difference between plain text and decryption result will leak p.\n",
" 2. leak the first column of matrix.\n",
" * If the input is enough large, The integer divisionof shares and plaintext will be the first column of matrix m.\n",
" 3. leak the first row of inverse of 5x5 submatrix.\n",
" 4. calculate submatrix m from the first row of inverse of 5x5 submatrix\n",
" * Get the small kernel of the row by LLL. \n",
" * Enumerate matrix candidate whose element are positive integer less than 1000.\n",
" 5. get the matrix overall.\n",
" * The randoms can be calculated from submatrix. Since the random numbers are known, the matrix can be recoverd with simple linear algebra.\n",
" 6. get flag shares from server.\n",
" * From one flag encryption, we can get the following three equations, and one equation with moduluo operation.\n",
" * $ m_{i,0}\\mathrm{flag} + m_{i,1}r_{i,1} + m_{i,2}r_{i,2} + m_{i,3}r_{i,4} + m_{i,4}r_{i,4} = \\mathrm{share}_i $\n",
" 7. solve linar equations by LLL.\n",
" * The equations have no unambiguous solution, but LLL can be applied because that r and flag is smaller than p. \n",
" * Experimentally, it can be solved from 64 equations (from 16 times flag encryption) "
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"import random\n",
"import nclib\n",
"\n",
"def get_shares(nc, data):\n",
" nc.send_line(b'1')\n",
" nc.send_line(data)\n",
" nc.recv_until(b'ID is: ')\n",
" id = nc.recv(6)\n",
" nc.send(b'100\\n')\n",
" nc.recv_until(b'Your shares are: ')\n",
" ast = nc.recv_until(b'\\n')\n",
" return (id, eval(ast))\n",
"\n",
"def get_flag(nc):\n",
" nc.send_line(b'3')\n",
" nc.recv_until(b'ID is: ')\n",
" id = nc.recv(6)\n",
" nc.recv_until(b'Your shares are: ')\n",
" ast = nc.recv_until(b'\\n')\n",
" return (id, eval(ast))\n",
"\n",
"\n",
"def get_secret(nc, id, shares):\n",
" nc.send_line(b'2')\n",
" nc.recv_until(b'ID: ')\n",
" nc.send_line(id)\n",
" nc.recv_until(b'secret: ')\n",
" nc.send_line(str(shares).encode('utf-8')) \n",
" nc.recv_until(b'Your secret is: ')\n",
" return eval(nc.recv_until(b'\\n'))\n",
"\n",
"def connect():\n",
" nc = nclib.Netcat(('ooo-flag-sharing.challenges.ooo', 5000), verbose=False)\n",
" nc.recv_until(b'Username: ')\n",
" nc.send(b\"ellie\\n\")\n",
" return nc"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"# calculate candidates of submatrix column\n",
"def candidate_submatrix(r, p):\n",
" M = Matrix(ZZ, 6, 6)\n",
" for i in range(5):\n",
" M[i, i] = 1\n",
" M[i, 5] = r[i] * 100000\n",
" M[5, 5] = p\n",
" basis = M.LLL()[0:4]\n",
" assert(all([row[-1] == 0 for row in basis]))\n",
" candis =[]\n",
" for i in range(-10, 11):\n",
" for j in range(-10, 11):\n",
" for k in range(-10, 11):\n",
" for l in range(-10, 11):\n",
" candi = basis[0] * i + basis[1] * j + basis[2] * k + basis[3] * l\n",
" if all([0 <= c <= 1000 for c in candi]) and candi != 0:\n",
" candis.append(candi)\n",
" if (len(candis) >= 16):\n",
" return candis\n",
" return candis"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"p= 95820804521871446624646154398560990164494336030962272285033480112778980081147\n"
]
}
],
"source": [
"# get prime from server\n",
"nc = connect()\n",
"try:\n",
" e1 = b'a' * 128\n",
" id, shares = get_shares(nc, e1)\n",
" e1 = int.from_bytes(e1, 'little')\n",
" s1 = int.from_bytes(get_secret(nc, id, shares), 'little')\n",
"\n",
" e2 = b'b' * 128\n",
" id, shares = get_shares(nc, e2)\n",
" e2 = int.from_bytes(e2, 'little')\n",
" s2 = int.from_bytes(get_secret(nc, id, shares), 'little')\n",
" p = (gcd(e1 - s1, e2 - s2)) \n",
" assert is_prime(p)\n",
" print('p=', p)\n",
"finally:\n",
" nc.close()"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"------ try -------\n",
"[(0, 0, 0, 0, 0, 0), (8, 53, 298, 497, 55, 0), (16, 106, 596, 994, 110, 0), (26, 138, 255, 611, 453, 0), (44, 223, 212, 725, 851, 0), (619, 864, 609, 321, 33, 0), (627, 917, 907, 818, 88, 0), (637, 949, 566, 435, 431, 0), (647, 981, 225, 52, 774, 0), (694, 235, 428, 28, 291, 0), (702, 288, 726, 525, 346, 0), (712, 320, 385, 142, 689, 0), (720, 373, 683, 639, 744, 0)]\n",
"13\n",
"\n",
"------ try -------\n",
"[(0, 0, 0, 0, 0, 0), (88, 486, 327, 63, 120, 0), (170, 933, 145, 401, 826, 0), (179, 795, 292, 223, 325, 0), (279, 966, 404, 205, 29, 0), (282, 789, 42, 302, 114, 0), (443, 107, 147, 821, 507, 0), (531, 593, 474, 884, 627, 0), (534, 416, 112, 981, 712, 0), (540, 455, 621, 706, 126, 0), (543, 278, 259, 803, 211, 0), (631, 764, 586, 866, 331, 0), (634, 587, 224, 963, 416, 0), (646, 272, 9, 882, 0, 0), (731, 935, 698, 848, 35, 0), (734, 758, 336, 945, 120, 0)]\n",
"16\n",
"\n",
"------ try -------\n",
"[(133, 978, 737, 871, 507, 0), (237, 692, 555, 355, 190, 0), (330, 638, 840, 364, 383, 0), (361, 922, 599, 270, 30, 0), (454, 868, 884, 279, 223, 0), (541, 956, 828, 763, 750, 0), (552, 724, 361, 238, 240, 0), (645, 670, 646, 247, 433, 0), (676, 954, 405, 153, 80, 0), (738, 616, 931, 256, 626, 0), (769, 900, 690, 162, 273, 0), (856, 988, 634, 646, 800, 0), (862, 846, 975, 171, 466, 0), (949, 934, 919, 655, 993, 0), (960, 702, 452, 130, 483, 0), (991, 986, 211, 36, 130, 0)]\n",
"16\n",
"\n",
"------ try -------\n",
"[(163, 16, 400, 319, 794, 0), (203, 46, 630, 246, 986, 0), (409, 242, 477, 772, 770, 0), (449, 272, 707, 699, 962, 0), (512, 174, 47, 866, 733, 0), (549, 308, 797, 182, 899, 0), (552, 204, 277, 793, 925, 0), (612, 210, 137, 349, 670, 0), (652, 240, 367, 276, 862, 0), (795, 534, 874, 635, 875, 0), (858, 436, 214, 802, 646, 0), (895, 570, 964, 118, 812, 0), (898, 466, 444, 729, 838, 0), (918, 442, 74, 358, 391, 0), (958, 472, 304, 285, 583, 0), (998, 502, 534, 212, 775, 0)]\n",
"16\n",
"\n",
"------ try -------\n",
"[(0, 0, 0, 0, 0, 0), (400, 346, 6, 645, 317, 0), (509, 492, 318, 856, 265, 0), (631, 789, 229, 248, 54, 0), (740, 935, 541, 459, 2, 0), (839, 20, 874, 926, 660, 0), (852, 171, 473, 107, 501, 0), (961, 317, 785, 318, 449, 0)]\n",
"8\n",
"(68382836894762605117546119022170744768997555669570093158912619107059096286798405583814597255974631349210396260186373159580010225784307499536494904988348980645660728087105694399220844318905376978772349201381355135597257318381250586286155183225334282371941174652568121291274050415813852868898155152837449965921, 86920660267327165539029008614598462708896228744747688804242715169022332159676, 87122843767786057797594030923847838142931809418117125488207131040323055957933, 72857092119301691625509979909577010459749724034143157922594497049142185320491, 48141937736865914968275212481111147894618899406015081335714388742832865231163)\n",
"!!! FOUND !!!!\n",
"[[-43020648847/27105353203276 60075087043/54210706406552 36399101911/54210706406552 -3373091261/6776338300819 12151930306/6776338300819]\n",
"[ 14405646433/6776338300819 11439206393/13552676601638 -56597899185/13552676601638 -1523878935/6776338300819 592405780/6776338300819]\n",
"[ 6187018467/27105353203276 -14430415811/54210706406552 35365849985/54210706406552 -4065512378/6776338300819 8205503891/6776338300819]\n",
"[ -2368115241/6776338300819 -15933385768/6776338300819 17981384692/6776338300819 15127833128/6776338300819 -10741776352/6776338300819]\n",
"[ 15105535141/27105353203276 65269615635/54210706406552 -25947980937/54210706406552 -4098695784/6776338300819 -5269225943/6776338300819]]\n"
]
}
],
"source": [
"# get submatrix from server\n",
"nc = connect()\n",
"m = Matrix(100, 5)\n",
"try:\n",
" e1 = b'a' * 128\n",
" e1n = int.from_bytes(e1, 'little')\n",
" id, shares = get_shares(nc, e1)\n",
" for (idx, share) in shares:\n",
" m[idx, 0] = share // e1n\n",
" \n",
" id, shares = get_shares(nc, e1)\n",
" while True:\n",
" random.shuffle(shares)\n",
" print()\n",
" print('------ try -------')\n",
" for (idx, share) in shares:\n",
" if m[idx, 0] != 0:\n",
" assert(m[idx, 0] == share // e1n)\n",
" m[idx, 0] = share // e1n\n",
" # leak random array\n",
" base_ret = int.from_bytes(get_secret(nc, id, shares[0:5]), 'little')\n",
" assert(base_ret == e1n % p)\n",
" v = vector([0, 0, 0, 0, 0])\n",
" m0 = vector([0, 0, 0, 0, 0])\n",
"\n",
" svec = vector(QQ, 5)\n",
" for i in range(0,5):\n",
" shares[i] = (shares[i][0], shares[i][1] + 1)\n",
" changed_ret = int.from_bytes(get_secret(nc, id, shares[0:5]), 'little')\n",
" v[i] = Mod((changed_ret - base_ret) % p, p)\n",
" shares[i] = (shares[i][0], shares[i][1] - 1)\n",
" m0[i] = m[shares[i][0], 0]\n",
" svec[i] = shares[i][1]\n",
"\n",
" if m0 * v % p != 1:\n",
" continue\n",
" \n",
" # v: submatrix.inverse().rows()[0]\n",
" matrix_candi = candidate_submatrix(v, p)\n",
" print(sorted(matrix_candi))\n",
" print(len(matrix_candi))\n",
" invs = []\n",
" if (len(matrix_candi)) <= 10:\n",
" mc = [r[0:5] for r in matrix_candi]\n",
" for i in range(len(matrix_candi)):\n",
" for j in range(i + 1,len(matrix_candi)):\n",
" for k in range(j + 1,len(matrix_candi)):\n",
" for l in range(k + 1, len(matrix_candi)):\n",
" sm = Matrix(QQ, [m0, mc[i], mc[j], mc[k], mc[l]]).transpose()\n",
" if sm.rank() == 5:\n",
" inv = sm.inverse() * svec\n",
" if inv[0] == e1n and all([int(c) == c and 0 <= int(c) < p for c in inv[1:]]):\n",
" print(inv)\n",
" invs.append(sm.inverse())\n",
" if len(invs) == 1:\n",
" break\n",
" \n",
"finally:\n",
" nc.close()\n",
" \n",
"\n",
"print('!!! FOUND !!!!')\n",
"print(invs)\n",
"inv = invs[0]\n",
"subrows = [v[0] for v in shares[0:5]]\n",
"\n",
" "
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"matrix\n",
"[ 0 0 0 0 0]\n",
"[663 493 386 737 105]\n",
"[435 907 796 880 404]\n",
"[931 887 253 90 627]\n",
"[734 155 908 616 116]\n",
"[510 323 491 428 397]\n",
"[104 647 176 238 878]\n",
"[708 346 171 492 935]\n",
"[310 815 685 194 589]\n",
"[176 400 852 509 740]\n",
"[290 670 604 988 778]\n",
"[928 956 158 937 903]\n",
"[848 182 28 831 308]\n",
"[558 146 447 948 994]\n",
"[755 235 132 929 430]\n",
"[469 433 684 800 47]\n",
"[928 414 529 326 42]\n",
"[209 752 910 431 517]\n",
"[150 804 895 497 850]\n",
"[812 662 416 845 238]\n",
"[963 9 145 224 542]\n",
"[144 514 89 308 402]\n",
"[823 411 211 124 131]\n",
"[708 720 44 26 627]\n",
"[990 319 210 231 948]\n",
"[876 853 249 752 567]\n",
"[149 146 365 791 614]\n",
"[278 247 915 646 229]\n",
"[ 41 199 384 839 410]\n",
"[642 668 81 801 227]\n",
"[630 218 474 510 354]\n",
"[107 674 447 351 153]\n",
"[126 3 182 446 150]\n",
"[543 52 279 56 722]\n",
"[400 182 246 549 933]\n",
"[742 576 142 214 566]\n",
"[581 482 98 685 26]\n",
"[439 317 501 265 2]\n",
"[302 727 502 390 285]\n",
"[301 429 715 815 223]\n",
"[762 560 274 726 201]\n",
"[658 646 170 634 76]\n",
"[ 79 0 826 416 536]\n",
"[998 445 293 267 918]\n",
"[701 401 781 264 213]\n",
"[963 470 995 247 228]\n",
"[591 598 254 362 532]\n",
"[464 639 725 611 818]\n",
"[666 558 327 892 482]\n",
"[547 829 262 406 551]\n",
"[782 286 275 36 991]\n",
"[176 374 11 462 767]\n",
"[561 218 70 956 692]\n",
"[927 703 354 596 459]\n",
"[545 903 456 749 663]\n",
"[664 783 913 999 787]\n",
"[781 232 633 866 864]\n",
"[679 645 438 651 542]\n",
"[115 942 375 216 485]\n",
"[723 225 790 257 755]\n",
"[470 178 65 863 39]\n",
"[452 683 212 255 907]\n",
"[852 645 107 856 459]\n",
"[770 123 525 163 888]\n",
"[233 557 991 14 711]\n",
"[902 880 935 1 804]\n",
"[958 298 184 730 476]\n",
"[586 432 794 867 3]\n",
"[388 288 562 577 218]\n",
"[285 946 745 573 856]\n",
"[977 385 331 683 427]\n",
"[940 297 794 45 959]\n",
"[420 864 639 546 291]\n",
"[762 107 414 504 967]\n",
"[952 165 275 836 267]\n",
"[222 780 178 670 368]\n",
"[192 185 219 209 821]\n",
"[178 798 726 675 227]\n",
"[124 373 223 138 917]\n",
"[ 40 468 304 323 852]\n",
"[594 882 401 963 144]\n",
"[225 124 486 508 813]\n",
"[308 732 796 269 682]\n",
"[250 304 384 718 462]\n",
"[784 504 648 597 373]\n",
"[196 6 473 318 541]\n",
"[755 25 366 578 410]\n",
"[941 970 746 869 990]\n",
"[804 272 933 587 801]\n",
"[159 901 217 23 246]\n",
"[805 555 61 18 608]\n",
"[852 396 664 145 273]\n",
"[470 986 332 212 435]\n",
"[701 118 87 123 469]\n",
"[848 744 851 453 88]\n",
"[799 6 268 894 775]\n",
"[ 60 632 231 886 39]\n",
"[817 369 660 913 342]\n",
"[628 700 873 106 683]\n",
"[871 82 271 323 323]\n"
]
}
],
"source": [
"# get matrix from server\n",
"nc = connect()\n",
"m = Matrix(ZZ, 100, 5)\n",
"try:\n",
" e1 = b'a'\n",
" e1n = int.from_bytes(e1, 'little')\n",
" rets = [[] for i in range(100)]\n",
" for _ in range(0, 10):\n",
" _, shares = get_shares(nc, e1)\n",
" shares_by_idx = [None] * 100\n",
" for idx, share in shares:\n",
" shares_by_idx[idx] = share\n",
" vec = vector([0, 0, 0, 0, 0])\n",
" found_err = False\n",
" for i in range(0, len(subrows)):\n",
" if shares_by_idx[subrows[i]] is None:\n",
" found_err = True\n",
" break\n",
" vec[i] = shares_by_idx[subrows[i]]\n",
" if found_err:\n",
" continue\n",
" rs = inv * vec\n",
" assert rs[0] == e1n\n",
" for i in range(100):\n",
" if shares_by_idx[i] is not None:\n",
" rets[i].append((rs, shares_by_idx[i]))\n",
" \n",
" for i in range(1, 100):\n",
" assert len(rets[i]) >= 5\n",
" q = Matrix(QQ, [r[0] for r in rets[i]])\n",
" v = vector(QQ, [r[1] for r in rets[i]])\n",
" m[i] = q.solve_right(v)\n",
"finally:\n",
" nc.close()\n",
"print('matrix')\n",
"print(m)"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"tries 0\n",
"63\n",
"tries 1\n",
"4\n",
"tries 2\n",
"61\n",
"tries 3\n",
"37\n",
"tries 4\n",
"51\n",
"tries 5\n",
"76\n",
"tries 6\n",
"27\n",
"tries 7\n",
"61\n",
"tries 8\n",
"52\n",
"tries 9\n",
"51\n",
"tries 10\n",
"42\n",
"tries 11\n",
"37\n",
"tries 12\n",
"30\n",
"tries 13\n",
"57\n",
"tries 14\n",
"2\n",
"tries 15\n",
"16\n",
"tries 16\n",
"10\n",
"tries 17\n",
"70\n",
"tries 18\n",
"99\n",
"error\n",
"tries 19\n",
"80\n",
"tries 20\n",
"11\n",
"tries 21\n",
"96\n",
"tries 22\n",
"46\n",
"tries 23\n",
"86\n",
"tries 24\n",
"52\n",
"tries 25\n",
"33\n",
"tries 26\n",
"16\n",
"tries 27\n",
"24\n",
"tries 28\n",
"98\n",
"tries 29\n",
"16\n",
"tries 30\n",
"55\n",
"tries 31\n",
"16\n"
]
}
],
"source": [
"# get flag shares\n",
"flag_shares_universe = []\n",
"for count in range(32):\n",
" print('tries', count)\n",
" try:\n",
" nc = connect()\n",
" flag_id, flag_shares_tmp = get_flag(nc)\n",
" try:\n",
" nc2 = connect()\n",
" sidx = 0\n",
" try:\n",
" for sidx in range(1, 100):\n",
" if all([idx != sidx for (idx, s) in flag_shares_tmp]):\n",
" get_secret(nc2, flag_id, flag_shares_tmp + [(sidx, 0)])\n",
" except:\n",
" pass\n",
" finally:\n",
" nc2.close()\n",
" finally:\n",
" nc.close()\n",
"\n",
" nc = connect()\n",
" try:\n",
" print(sidx)\n",
" tidx = [(idx, 0) for (idx, _) in flag_shares_tmp] + [(99, 0)]\n",
" zero_secret = get_secret(nc, flag_id, tidx)\n",
" tmp_sub_mat = Matrix(Zmod(p), [m[idx] for (idx, _) in tidx + [(sidx, 0)]]).inverse()\n",
" zero_secret = Mod(int.from_bytes(zero_secret, 'little'), p) / tmp_sub_mat[0, 4]\n",
" flag_shares_universe.append([(idx, share, False) for (idx, share) in flag_shares_tmp[0:3]] + [(sidx, int(zero_secret), True)])\n",
" finally:\n",
" nc.close()\n",
" except:\n",
" print('error')"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"b'OOO{ooo_c4nt_ke3p_secr3ts!}\\x00\\x00\\x00\\x00\\x00'\n"
]
}
],
"source": [
"random.shuffle(flag_shares_universe)\n",
"flag_shares = flag_shares_universe[0:16]\n",
"\n",
"lam = 2 ** 512\n",
"m_left = Matrix(ZZ, 2 + 4 * len(flag_shares), len(flag_shares) * len(flag_shares[0]))\n",
"m_right = Matrix(ZZ, 2 + 4 * len(flag_shares), len(flag_shares) * 4 + 2)\n",
"m_bottom = Matrix(ZZ, len(flag_shares), m_left.ncols() + m_right.ncols())\n",
"i = 0\n",
"m_right[1, 0] = 1\n",
"m_right[0, m_right.ncols() - 1] = 2**256\n",
"rm = []\n",
"k = 2\n",
"mod_index = 0\n",
"for flags_shares_tmp in flag_shares:\n",
" for (idx, share, use_mod) in flags_shares_tmp:\n",
" m_left[0, i] = -share * lam\n",
" m_left[1, i] = m[idx, 0] * lam\n",
" rm.append(m[idx])\n",
" for j in range(1, 5):\n",
" m_left[k + j - 1, i] = m[idx, j] * lam\n",
" m_right[k + j - 1, 1 + k + j - 3] = 1\n",
" if use_mod:\n",
" m_bottom[mod_index, i] = p * lam\n",
" mod_index += 1\n",
" i += 1\n",
" k += 4\n",
"mm = m_left.augment(m_right).stack(m_bottom)\n",
"rm = Matrix(rm)\n",
"llled = mm.LLL()\n",
"for row in llled:\n",
" if row != 0 and row[0:len(flag_shares) * len(flag_shares[0])] == 0 and abs(row[-1]) == 2**256:\n",
" flag = int(row[len(flag_shares) * len(flag_shares[0])]).to_bytes(32, 'little')\n",
" print(flag)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "SageMath 9.0",
"language": "sage",
"name": "sagemath"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.3"
}
},
"nbformat": 4,
"nbformat_minor": 4
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment