LSB Bias for Bleichenbacher

LSBBias.py

import random
import cmath

MOD = 1 << 20
samples = 10000
FIXED_LSBS = 3  

# Generate nonces with FIXED_LSBS LSBs = 0
step = 1 << FIXED_LSBS
max_val = MOD // step
biased_nonces = [random.randint(0, max_val - 1) * step for _ in range(samples)]
uniform_nonces = [random.randint(0, MOD-1) for _ in range(samples)]

def bias(nonces, freq):
    total = sum(cmath.exp(2j * cmath.pi * freq * x / MOD) for x in nonces)
    return abs(total / len(nonces))

# Optimal frequency for LSB detection
optimal_freq = MOD // step

print(f"Fixed LSBs: {FIXED_LSBS} (numbers are multiples of {step})")
print(f"Optimal frequency: MOD/{step} = {optimal_freq}")
print()
print(f"f=1 (standard):")
print(f"  Biased nonces: {bias(biased_nonces, 1):.6f}")
print(f"  Uniform:       {bias(uniform_nonces, 1):.6f}")
print()
print(f"f=optimal (LSB-detecting):")
print(f"  Biased nonces: {bias(biased_nonces, optimal_freq):.6f}")
print(f"  Uniform:       {bias(uniform_nonces, optimal_freq):.6f}")