-
Notifications
You must be signed in to change notification settings - Fork 10
/
Copy pathsolve_lance_roy.sage
107 lines (82 loc) · 5.59 KB
/
solve_lance_roy.sage
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
from chall import *
from sage.matrix.special import *
sigs = [(49045447930003829750162655581084595201459949397872275714162821319721992870137, 21098529732134205108109967746034152237233232924371095998223311603901491079093), (8434794394718599667511164042594333290182358521589978655877119244796681096882, 72354802978589927520869194867196234684884793779590432238701483883808233102754), (98981626295463797155630472937996363226644024571226330936699150156804724625467, 78572251404021563757924042999423436619062431666136174495628629970067579789086), (39876682309182176406603789159148725070536832954790314851840125453779157261498, 57493814845754892728170466976981074324110106533966341471105757201624065653133), (65207470758289014032792044615136252007114423909119261801100552919825658080689, 35801670032389332886673836105411894683051812268221960643533854039645456103322), (62310615350331421137050446859674467271639363124966403418757056624834651785981, 35521772482874533704942922179876531774398711539124898773478624535131725819343), (112968103298671409136981160931495676458802276287280410415332578623201858813402, 69136482735760979952358359721969881674752452777485098096528689791122554903910), (65185852906255515620576935005939230631603582432998989514260597054881976462676, 85379997570993122627264764907519703985819259494167121515303052416417601678111), (89525951822575634807524099747751997083879407738240060351122435098952102365970, 73032937908295382442051096857786822685807890991333822263666894552392531234105), (10051482171127490286979879686762557184173302546674808492445781875620932719446, 26217862064468074441046914792412948081058029471697661868711999974556608497458), (8842758449685028748615236698968197767772820788773190926335075554397256573640, 31652804170027719136589492610452674938583230853203431940531961290992398961987), (23751070894286517351443200111133743672788640335816140651282619979550868046371, 62545547750389706281745923819072901405095067763677430386609805435019439100532), (73526459114147520989492697207756783950511563270716718674108128391637651652182, 70851054921933366241324896134628440370210434216441807412696261358563604784468), (57753594385723283080008450150285839290328959323728215111064869128180653466512, 48682503345807264543892350428384011994195616727229911040222271121395096668630), (65263395028919805249304292530249376748389080058707453448295007353333046365479, 10365290276028966530454805043630476285018698618883354555344947391544138993674), (87437293666767613034832827186884716590065056433713359026118257811657437100576, 89500859891014369107213802143650102492250691913844472777312272074978411403745), (82006715584380621917183646856144618837928013528296150149335800289034986391573, 66403597255556240236430083902481022812584785679596388450322939858389337923701)]
ct = b'\xc6*\x17\xcce\xc1y\xb8\xb4\x8d\x87L\xf8\x81QK\xf4\x02\xf2\xf7\x8d\xe0\xe8\x92\xc7\xe7\x8fg\xb1M\xb4.\x89\x18\xf5\x7f\xed\xc3I\x92\x82\xfd\xfe9\x95\xc9(\x90\xce\x93\xb9+\xce\x958\xf3\x05PH'
nonce = b'6\xe7m\xcc\x8e\x0eG '
lcg_bits = 0x137
low_bits = q.bit_length()
high_bits = lcg_bits - low_bits
sigs = [
{
'r': r,
's': s,
'sinv': inverse_mod(s, q),
'z': int.from_bytes(sha256(m).digest(), "big") % q
} for (r, s), m in zip(sigs, msgs)]
n = 14
t = len(sigs) - n + 1
print(f'{n=}, {t=}')
constraints = block_matrix([
[
column_matrix([(sigs[i+j]['sinv'] * sigs[i+j]['z']) % q,
(sigs[i+j]['sinv'] * sigs[i+j]['r']) % q])
for j in range(n)
]
for i in range(t)
])
basis = constraints.change_ring(Zmod(q)).right_kernel().basis_matrix()
basis = block_matrix([[basis.change_ring(ZZ)], [block_matrix([[zero_matrix(2 * t, n - 2 * t), q * identity_matrix(2 * t)]])]])
print(basis)
basis = basis.BKZ()
print(basis)
# Find a multiple of (x - a) (Maybe times (x - 1)?)
R.<x> = PolynomialRing(ZZ)
polys = []
for b in basis[:4]:
# Verify that orthogonal vectors that we found are also orthogonal to the unreduced lcg outputs.
l1norm = sum(abs(u) for u in b)
assert l1norm * 2^high_bits < 2^(lcg_bits * (1 - 1/t))
print(N((l1norm * 2^high_bits) / (2^(lcg_bits * (1 - 1/t)))))
polys.append(sum(x^i * c for i, c in enumerate(b)))
p = gcd([poly.resultant(polys[0]) for poly in polys])
assert p.is_prime()
Rp = Zmod(p)
a = gcd([poly.change_ring(Rp) for poly in polys]).roots()[0][0]
poly = (x - a) * (x - 1)
# Now that we have the LCG parameters (other than b), can recover d with a mixed modulus lattice
# problem.
#
# Variables: 1, d, wraparounds mod q, wraparounds mod p (for len(sigs) - 2 constraints)
# Constraints (small):
# 1,
# d,
# ks mod p,
# constraints on ks mod p (exact)
d_scale = p // q
one_scale = p^2
exact_scale = p^3
ks_mod_p = matrix([[(sig['sinv'] * sig['z']) % q,
(sig['sinv'] * sig['r']) % q] for sig in sigs])
ks_mod_p = ks_mod_p.augment(diagonal_matrix([q] * len(sigs)))
ks_constraints = toeplitz(list(poly.change_ring(ZZ)) + [0] * (len(sigs) - 3), [0] * (len(sigs) - 3)).transpose() * ks_mod_p
ks_constraints = ks_constraints.augment(p * identity_matrix(len(sigs) - 2))
ks_constraints *= exact_scale
ks_mod_p = ks_mod_p.augment(zero_matrix(len(sigs), len(sigs) - 2))
A = diagonal_matrix([one_scale, d_scale]).augment(zero_matrix(2, 2 * len(sigs) - 2))
A = A.stack(ks_mod_p)
A = A.stack(ks_constraints)
#print(A)
basis = A.transpose().dense_matrix().LLL()
for b in basis:
if b[0] < 0:
b = -b
if b[0] == one_scale and b[-(len(sigs)-2):] == 0:
break
else:
assert False
d = b[1] // d_scale
print(d)
key = sha256(str(d).encode()).digest()
cipher = AES.new(key, AES.MODE_CTR, nonce=nonce)
pt = cipher.decrypt(ct)
print(pt)