Skip to content

Instantly share code, notes, and snippets.

@Mukundan314
Last active October 28, 2024 09:10
Show Gist options
  • Save Mukundan314/15aee45c6a77c87da317e324083e19d7 to your computer and use it in GitHub Desktop.
Save Mukundan314/15aee45c6a77c87da317e324083e19d7 to your computer and use it in GitHub Desktop.
import time
import random
from collections import UserDict
class SafeDict(UserDict):
RAND = random.randint(0, 2 ** 31)
def __getitem__(self, k):
return self.data[k ^ SafeDict.RAND]
def __setitem__(self, k, v):
self.data[k ^ SafeDict.RAND] = v
def __contains__(self, k):
return k ^ SafeDict.RAND in self.data
def create_hack(lo, hi, n, unique=False, CPython=False):
pow2 = 2 ** ((hi - lo - 1).bit_length() - 1)
if unique:
pow2 //= 2
def advance(x, perturb):
if CPython:
perturb >>= 5
y = (5 * x + perturb + 1) % pow2
if not CPython:
perturb >>= 5
return y, perturb
def prime_dict(n):
A = []
i = perturb = hash(lo)
i %= pow2
for _ in range(min(n, pow2 // 2 - 10)):
A.append(i + (lo + 1 - i + pow2 - 1) // pow2 * pow2)
i, perturb = advance(i, perturb)
assert all(lo <= x < hi for x in A)
return A
def attack_dict(priming_idx, n):
# TODO: make sure resize does not occur
A, B = [], []
used = set()
for i in range(lo, hi):
if i in used or i in priming_idx:
continue
path = []
h = perturb = hash(i)
h %= pow2
while perturb != 0:
path.append(h)
h, perturb = advance(h, perturb)
if h not in priming_idx or priming_idx[h] > len(priming_idx) // 10: # TODO: different thresholds
continue
if len(A) + len(B) + len(path) + 1 > n:
break
for j in path:
j = j + (lo + 1 - j + pow2 - 1) // pow2 * pow2
if j == i:
j = j - pow2 if j - pow2 >= lo else j + pow2
if j not in priming_idx and j not in used:
A.append(j)
used.add(j)
B.append(i)
used.add(i)
assert all(lo <= x < hi for x in A)
assert all(lo <= x < hi for x in B)
return A, B
priming = prime_dict(n // 2) # TODO: different splits
if not unique:
return priming, [lo] * (n - len(priming))
priming_idx = SafeDict((j, i) for i, j in enumerate(priming))
extra_priming, attack = attack_dict(priming_idx, n - len(priming))
# NOTE: reordering priming will not lose any efficiency
# NOTE: reordering attack will slightly lose efficiency (shouldn't be noticable)
return priming + extra_priming, attack
start = time.time()
priming, attack = create_hack(1, 10 ** 7, 2 * 10 ** 5, True, False)
priming.sort()
print("generation", time.time() - start, len(priming) + len(attack))
start = time.time()
d = {}
for i in priming:
d[i] = 1
for i in attack:
d[i] = 0
print("attack", time.time() - start)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment