Birthday problem with frequency analysis stage and pattern analysis stage

divbirthday.py

# 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 fastecdsa bit

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.
divisor = 32 # The divisor (for 2^10, set to 1024, and so on).

# 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

## PHASE 1: ANALYZING THE FREQUENCY OF BITS IN BIT POSITIONS

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)

## PHASE 2: ANALYZING THE PATTERNS IN EACH BIT
# First we need an encoding to classify each of the bit lengths in a human-readable way
# The convention I'm using is to represent '0' as uppercase letters and '1' as lowercase letters.
# The letter'z' is reserved to add between the letters of the alphabet so that each
# group of consecutive letters represents a multiple of 25 bits.
def encode1():
    bitencoding = {}
    for i in range(0,256):
        mult = (i // 25) + 1
        lkey = "z"
        ukey = "Z"
        im = i % 25;
        if im == 0:
            lkey += "a" * mult
            ukey += "A" * mult
        elif im == 1:
            lkey += "b" * mult
            ukey += "B" * mult
        elif im == 2:
            lkey += "c" * mult
            ukey += "C" * mult
        elif im == 3:
            lkey += "d" * mult
            ukey += "D" * mult
        elif im == 4:
            lkey += "e" * mult
            ukey += "E" * mult
        elif im == 5:
            lkey += "f" * mult
            ukey += "F" * mult
        elif im == 6:
            lkey += "g" * mult
            ukey += "G" * mult
        elif im == 7:
            lkey += "h" * mult
            ukey += "H" * mult
        elif im == 8:
            lkey += "i" * mult
            ukey += "I" * mult
        elif im == 9:
            lkey += "j" * mult
            ukey += "J" * mult
        elif im == 10:
            lkey += "k" * mult
            ukey += "K" * mult
        elif im == 11:
            lkey += "l" * mult
            ukey += "L" * mult
        elif im == 12:
            lkey += "m" * mult
            ukey += "M" * mult
        elif im == 13:
            lkey += "n" * mult
            ukey += "N" * mult
        elif im == 14:
            lkey += "o" * mult
            ukey += "O" * mult
        elif im == 15:
            lkey += "p" * mult
            ukey += "P" * mult
        elif im == 16:
            lkey += "q" * mult
            ukey += "Q" * mult
        elif im == 17:
            lkey += "r" * mult
            ukey += "R" * mult
        elif im == 18:
            lkey += "s" * mult
            ukey += "S" * mult
        elif im == 19:
            lkey += "t" * mult
            ukey += "T" * mult
        elif im == 20:
            lkey += "u" * mult
            ukey += "U" * mult
        elif im == 21:
            lkey += "v" * mult
            ukey += "V" * mult
        elif im == 22:
            lkey += "w" * mult
            ukey += "W" * mult
        elif im == 23:
            lkey += "x" * mult
            ukey += "X" * mult
        elif im == 24:
            lkey += "y" * mult
            ukey += "Y" * mult
        lkey += "z"
        ukey += "Z"
        print(i, mult, lkey, ukey)
        bitencoding[ukey] = bitarray.bitarray('0' * (i+1))
        bitencoding[lkey] = bitarray.bitarray('1' * (i+1))
    return bitencoding


# In this encoding the number is written directly.
def encode2():
    bitencoding = {}
    for i in range(0,256):
        mult = (i // 25) + 1
        lkey = "_zero" + '{}'.format((i+1))
        ukey = "_one" + '{}'.format((i+1))
        bitencoding[lkey] = bitarray.bitarray('0' * (i+1))
        bitencoding[ukey] = bitarray.bitarray('1' * (i+1))
    return bitencoding

def decode01(b, table):
    # bitarray decode chokes on values with the same prefix so we define our own.
    kl = []
    greedybuffer = ''
    count = 0
    type = ''
    for i in range(0, len(b)):
        if str(int(b[i])) == type:
            count += 1
            for it in table.items():
                if it[1] == bitarray.bitarray(type*count):
                    greedybuffer = it[0]
                    break
        elif type == '':
            type = str(int(b[i]))
            count = 1
            for it in table.items():
                if it[1] == bitarray.bitarray(type*count):
                    greedybuffer = it[0]
                    break
        else:
            if greedybuffer != '':
                if table.get(greedybuffer, None) == None:
                    raise KeyError("There is no key corresponding to {}".format(str(bitarray.bitarray(type*count))))                    
                kl.append(greedybuffer)
                greedybuffer = ''
            type = str(int(b[i]))
            count = 1
            for it in table.items():
                if it[1] == bitarray.bitarray(type*count):
                    greedybuffer = it[0]
                    break
    if kl == []:  # In case the entire array is all zeros or all ones
        didBreak = False
        for it in table.items():
            if it[1] == b:
                kl.append(it[0])
                didBreak = True
                break
        if not didBreak:
            raise KeyError("There is no key corresponding to {}".format(str(b)))
    if greedybuffer != '':
        if table.get(greedybuffer, None) == None:
            raise KeyError("There is no key corresponding to {}".format(str(bitarray.bitarray(type*count))))                    
        kl.append(greedybuffer)
        greedybuffer = ''
    return kl

import pandas
from collections import Counter

bitencoding = encode2()
bz = []
frame = []
for i in range(0, len(l)):
    ba = bitarray.util.hex2ba(l[i])
    ba.reverse()
    de = decode01(ba[:bits_toinspect], bitencoding)
    bz.append(de)
    counts = Counter(de)
    df = pandas.DataFrame.from_dict(counts, orient='index', columns=[str(i+1)])
    frame.append(df)

sdf = pandas.concat(frame, axis=1)
sdf = sdf.fillna(0)
sdf = sdf.reindex(sorted(sdf.index), axis=0)
means = sdf.mean(axis=1)

lz2 = []
for it in lz:
    de = decode01(it[1], bitencoding)
    counts = Counter(de)
    df = pandas.DataFrame.from_dict(counts, orient='index')
    combtable = pandas.concat([means, df], axis=1)
    combtable = combtable.fillna(0)
    variation = math.sqrt(combtable.var(axis=1).mean())
    lz2.append((it[0], it[1], variation))


lz2.sort(key=lambda x: abs(x[2]))
    
# Now we are finally ready to compute public keys and subtraction-division.

from fastecdsa import curve
from fastecdsa.point import Point
import bit

G = curve.secp256k1.G
N = curve.secp256k1.q

def pub2point(pub_hex):
    x = int(pub_hex[2:66], 16)
    if len(pub_hex) < 70:
        y = bit.format.x_to_y(x, int(pub_hex[:2], 16) % 2)
    else:
        y = int(pub_hex[66:], 16)
    return Point(x, y, curve=curve.secp256k1)

# This function makes all the downscaled pubkeys obtained from subtracting
# numbers between 0 and divisor, before dividing the pubkeys by divisor.
# i is between 0 and divisor (inclusive)
def shiftdown(pubkey, divisor, i):
    # k = 1/divisor
    k = pow(divisor, N - 2, N)
    P = pubkey - (i * G)
    P = k * P
    if (P.y % 2 == 0):
        prefix = "02"
    else:
        prefix = "03"
    hx = hex(P.x)[2:].zfill(64)
    hy = hex(P.y)[2:].zfill(64)
    return(prefix+hx, "04"+hx+hy)

def point2pub(R):
    # Remove the following code if you are doing multiple additions successively
    # as it brings a speed improvement, and just return R
    if (R.y % 2 == 0):
        prefix = "02"
    else:
        prefix = "03"
    hx = prefix + hex(R.x)[2:].zfill(64)
    return hx

import pprint
print("========== TOP {} MOST LIKELY PUBLIC KEYS (Highest probability first) ==========".format(nkeys))
print("Output format: <key> <index> <std deviation> <compressed result> <uncompressed result> ")
print("="*10)

with open("input.txt") as f, open("output.txt", "w") as outf:
    line = f.readline()
    while line:
          P = pub2point(line)
          print("Key: {}".format(point2pub(P)))
          # Assign result of write operation so that it doesn't print stuff to screen
          _ = outf.write("Key: {}".format(point2pub(P)))
          for i in range(0, nkeys):
              j = bitarray.util.ba2int(lz2[i][1])
              print("index {}   Std. Deviation: {}".format(j, lz2[i][2]))
              _ = outf.write("index {}   Std. Deviation: {}".format(lz2[i][1], lz2[i][2]))
              comp, uncomp = shiftdown(P, divisor, j)
              print("Compressed Result: {}".format(comp))
              _ = outf.write("Compressed Result: {}".format(comp))
              print("Uncompressed Result: {}".format(uncomp))
              _ = outf.write("Uncompressed Result: {}".format(uncomp))
          line = f.readline()
          print("="*10)

print("Done")