Created
June 29, 2023 08:15
-
-
Save maple3142/58c6aa2e8b983b17d1ef81af8da20f9e to your computer and use it in GitHub Desktop.
stern's attack for recovering parameter from truncated lcg (On Stern’s Attack Against Secret Truncated Linear Congruential Generators)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| k, s = 128, 32 | |
| p = random_prime(1 << k) | |
| a = randint(1, p) | |
| b = randint(1, p) | |
| seed = randint(1, p) | |
| state = seed | |
| ys = [] | |
| xs = [] | |
| zs = [] | |
| for _ in range(64): | |
| state = (a * state + b) % p | |
| xs.append(state) | |
| ys.append(state >> (k - s)) | |
| zs.append(state & ((1 << (k - s)) - 1)) | |
| def find_ortho_zz(*vecs): | |
| assert len(set(len(v) for v in vecs)) == 1 | |
| L = block_matrix(ZZ, [[matrix(vecs).T, matrix.identity(len(vecs[0]))]]) | |
| print("LLL", L.dimensions()) | |
| nv = len(vecs) | |
| L[:, :nv] *= 2**256 | |
| L = L.LLL() | |
| ret = [] | |
| for row in L: | |
| if row[:nv] == 0: | |
| ret.append(row[nv:]) | |
| return matrix(ret) | |
| def hnp(a, b, p, xs, ys): | |
| # a: a matrix with m columns and columns are dim n vector | |
| # b: a vector of dim n | |
| # p: a modulus | |
| # xs: a vector of dim m | |
| # ys: a vector of dim n | |
| # find a vector x such that a*x+b=y (mod p) are small | |
| # and abs(x[i]) <= xs[i] for i in range(m) | |
| # and abs(y[i]) <= ys[i] for i in range(n) | |
| n = len(a) | |
| m = len(a[0]) | |
| assert len(b) == n | |
| assert len(xs) == m | |
| assert len(ys) == n | |
| A = matrix(a).T.stack(vector(b)) | |
| L = block_matrix([[matrix.identity(n) * p, 0], [A, 1]]) | |
| bounds = list(ys) + list(xs) + [1] | |
| D = max(bounds) | |
| scale = [D // x for x in bounds] | |
| Q = diagonal_matrix(scale) | |
| L *= Q | |
| L = L.LLL() | |
| L /= Q | |
| return L | |
| def hnp2(a, b, p, xs, ys): | |
| # a: a matrix with m columns and columns are dim n vector | |
| # b: a vector of dim n | |
| # p: a modulus | |
| # xs: a vector of dim m | |
| # ys: a vector of dim n | |
| # find a vector x such that a*x+b=y (mod p) are small | |
| # and abs(x[i]) <= xs[i] for i in range(m) | |
| # and 0 <= y[i] <= ys[i] for i in range(n) | |
| bb = [b - y // 2 for b, y in zip(b, ys)] | |
| return hnp(a, bb, p, xs, ys) | |
| def clean(n): | |
| for p in primes_first_n(100): | |
| while n % p == 0: | |
| n //= p | |
| return n | |
| def get_mod_and_mul(ys, t, n): | |
| # stern's attack parameter, works only if t > n | |
| vi = lambda i: [ys[i + j] - ys[i + j - 1] for j in range(1, t + 1)] | |
| # wi = lambda i: [xs[i + j] - xs[i + j - 1] for j in range(1, t + 1)] | |
| V = matrix(ZZ, [vi(i) for i in range(n)]) | |
| # W = matrix(ZZ, [wi(i) for i in range(n)]) | |
| PR = ZZ["x"] | |
| polys = [] | |
| for lam in find_ortho_zz(*V): | |
| assert lam * V.T == 0 | |
| # lam * W.T == 0 for some smaller lam too | |
| polys.append(PR(list(lam))) | |
| p0, p1, p2, *_ = polys | |
| # assume that all([f(a) % p == 0 for f in [p0, p1, p2]]) | |
| p_cand = clean(gcd(p0.resultant(p1), p0.resultant(p2))) | |
| R = Zmod(p) | |
| p0p = p0.change_ring(R) | |
| p1p = p1.change_ring(R) | |
| lin = p0p.gcd(p1p) | |
| a_cand = -lin[0] / lin[1] | |
| return p_cand, a_cand | |
| p_cand, a_cand = get_mod_and_mul(ys, 32, 8) | |
| assert p_cand == p | |
| assert a_cand == a | |
| print(p_cand, a_cand) | |
| def get_inc_and_s0(y, k, s, p, a): | |
| # s0 * a.T[0] + c * a.T[1] == z (mod p) | |
| a_ = [] | |
| b_ = [] | |
| K = 2 ** (k - s) | |
| for i in range(len(y)): | |
| n = i + 1 | |
| a_.append([a**n, (a**n - 1) / (a - 1) % p]) | |
| b_.append(-K * y[i]) | |
| return hnp2(a_, b_, p, (p, p), (K,) * len(y)) | |
| L = get_inc_and_s0(ys, k, s, p, a) | |
| print(L[3]) | |
| s0, inc = L[3][-3], L[3][-2] | |
| tmp = [] | |
| for _ in range(len(ys)): | |
| s0 = (a * s0 + inc) % p | |
| tmp.append(s0) | |
| print(vector([x >> (k - s) for x in tmp]) - vector(ys)) | |
| print(vector(tmp) - vector(xs)) | |
| # it is always off from the real output by a constant |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment