Skip to content

Instantly share code, notes, and snippets.

@ZenulAbidin
Last active October 3, 2021 06:54
Show Gist options
  • Save ZenulAbidin/63d13b05f5adda18f03ef2cab577fca3 to your computer and use it in GitHub Desktop.
Save ZenulAbidin/63d13b05f5adda18f03ef2cab577fca3 to your computer and use it in GitHub Desktop.
Birthday problem but applied to randomly generated OpenSSL keys. (different algo)
# First, run this in shell:
# j=1000 # Sample size, feel free to change.
# for ((i=0; $i<$j; i++)); do openssl rand -hex 32 >> ~/Documents/randalysis.txt; echo -en "\n" >> ~/Documents/randalysis.txt; done
# sed -i '/^\s*$/d' ~/Documents/randalysis.txt
# pip install bitarray
import bitarray
import bitarray.util
from os.path import expanduser
sample=1000 # This is the number of example private keys you have generated above.
nkeys = 260 # This is the number of keys you want, change it accordingly.
# This is the number of lower-most bits you want to analyze, valid values are from 1
# to 256 and this value must be an integer.
bits_toinspect = 20
home = expanduser("~")
with open(home+"/Documents/randalysis.txt", "r") as fp:
s = fp.read()
l = s.split("\n")
l = l[:-1] # Remove extraneous blank element
cl = [0]*256
clz = [0]*256
delta = [0]*256
deltaz = [0]*256
# Values closer to zero - more likely to be zero, values closer to one - more likely to be one
for i in l:
ba = bitarray.util.hex2ba(i)
ba.reverse()
for j in range(0, 256):
cl[j] += ba[j]
clz[j] += 1-int(ba[j])
delta[j] = cl[j]/sample
deltaz[j] = clz[j]/sample
# Values negative - more likely to be zero, values positive - more likely to be one
# Because values will be between -0.5 and 0.5, we must "explode" this
# (by two to get values from -1 to 1)
# to get percentages between 0% and 100% for likely zero and likely one.
# (the '0' and '1' are used to set the bits in case of 0.5 "equal", unseperable frequencies).
import math
deltat = [(delta[t], t, '0') for t in range(0,bits_toinspect)]
deltatz = [(deltaz[t], t, '1') for t in range(0,bits_toinspect)]
import itertools
lz = []
deltac = zip(deltat, deltatz)
pdt = itertools.product(*deltac)
for c in pdt:
total_prob = 1
z = bitarray.util.zeros(bits_toinspect)
for it in c:
if it[0] < 0.5:
# Zero
z[bits_toinspect-it[1]-1] = False
elif it[0] > 0.5:
# One
z[bits_toinspect-it[1]-1] = True
else:
# perfectly even, no bias here so skip to next one
# but first set the bit accordingly
if it[2] == '0':
z[bits_toinspect-it[1]-1] = False
elif it[2] == '1':
z[bits_toinspect-it[1]-1] = True
else:
raise ValueError("Unexpected character (only chars 0 and 1 are allowed, were you tweaking the script?)")
continue
total_prob *= abs(it[0])
lz.append((total_prob*100, z))
lz.sort(key = lambda x: x[0], reverse=True)
import pprint
print("========== TOP {} MOST LIKELY BIT CONFIGURATIONS (Highest probability first) ==========".format(nkeys))
print("Output format: <probability> [(<bit number between 0-255>, <0 or 1>), ...]")
pprint.pprint(lz[0:nkeys])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment