Created
February 21, 2021 04:37
-
-
Save recuraki/c1d0236c302eb8c280d9bf5993488383 to your computer and use it in GitHub Desktop.
ハッシュ衝突をさせたい
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
""" | |
static Py_ssize_t | |
find_empty_slot(PyDictKeysObject *keys, Py_hash_t hash) | |
{ | |
assert(keys != NULL); | |
const size_t mask = DK_MASK(keys); | |
size_t i = hash & mask; | |
Py_ssize_t ix = dictkeys_get_index(keys, i); | |
printf("find_empty_slot %lx %lx %lx\n", mask, i, ix); | |
printf("find_empty_slot inputhash %lx\n", hash); | |
for (size_t perturb = hash; ix >= 0;) { | |
perturb >>= PERTURB_SHIFT; | |
i = (i*5 + perturb + 1) & mask; | |
printf("loopb key:%lx per:%lx i:%lx ix:%lx\n", keys, perturb,i , ix); | |
ix = dictkeys_get_index(keys, i); | |
printf("loopa key:%lx per:%lx i:%lx ix:%lx\n", keys, perturb,i , ix); | |
} | |
printf("find_empty_slot RES %lx %lx %lx\n", mask,i , ix); | |
return i; | |
} | |
""" | |
PERTURB_SHIFT = 5 | |
used = dict() | |
vala = 10 | |
valb = (10<<10)*5-1 | |
nn = 5 | |
data = [] | |
datb = [] | |
hash = vala | |
mask = 2**8 - 1 | |
i = hash & mask | |
perturb = hash | |
magic = [2,52,460,511,867] | |
for loop in range(nn): | |
perturb >>= PERTURB_SHIFT | |
i = (i * 5 + perturb + 1) & mask | |
print(">", loop, hex(i)) | |
data.append(hex(i)) | |
print("-------------------") | |
res = [] | |
for hashcore in range(10000000): | |
for hashdiff in range(1): | |
hash = (hashcore << 0) + hashdiff | |
datb = [] | |
i = hash & mask | |
perturb = hash | |
for loop in range(nn): | |
perturb >>= PERTURB_SHIFT | |
i = (i * 5 + perturb + 1) & mask | |
#print(">", loop, hex(i)) | |
datb.append(hex(i)) | |
if data == datb: | |
print(hashcore, hashdiff) | |
print(hash,"\t", hex(hash), "{:040b}".format(hash),"{:010b}".format(hash<<30>>30 & 2**12-1)) | |
res.append(hash) | |
print(res) | |
import sys | |
sys.exit(1) | |
print("-------------------") | |
res = [] | |
for hashcore in range(10000): | |
hash = 2 ** 125 -1 + hashcore | |
datb = [] | |
i = hash & mask | |
perturb = hash | |
for loop in range(nn): | |
perturb >>= PERTURB_SHIFT | |
i = (i * 5 + perturb + 1) & mask | |
#print(">", loop, hex(i)) | |
datb.append(hex(i)) | |
if data == datb: | |
print(hash,"\t", hex(hash), "{:040b}".format(hash),"{:010b}".format(hash<<30>>30 & 2**12-1)) | |
res.append(hash) | |
#print(res) | |
d = dict() | |
print(res) | |
print("res") | |
print("--") | |
for i in range(len(res )- 1): | |
print(res[i+1] - res[i+0]) | |
for x in res: | |
d[x] = True | |
print(d) | |
print("--") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment