#!/usr/bin/python3
from math import log2, floor, fsum
from gmpy2 import mpq
def factorial(n, limit=1):
res = mpq(1, 1)
while n > limit:
res *= n
n = n - 1
return res
# n! / ((n-k)! * k!)
def binomial_coefficient(n, k):
if k > n-k: k = n-k
return factorial(n, n-k) / factorial(k)
def binompdf(n, k, p): return binomial_coefficient(n, k) * pow(p, k) * pow(1-p, n-k)
def binomcdf(n, k_min, k_max, p): return sum((binompdf(n, k, p) for k in range(k_min, k_max+1)))
# S and H are lengths in bits. S for the salt, H for the hash.
# wanted_p_success is the success probability that the attacker is allowed to have
def calc_security(S, H, wanted_p_success):
number_of_salts = pow(2, S) # how many salts are possible?
needed_correct_salts = floor(number_of_salts * wanted_p_success) # floor: underestimate the security
success_probability = binomcdf(number_of_salts, needed_correct_salts, number_of_salts, mpq(1, pow(2,H)))
return -log2(success_probability)
print(float(calc_security(13, 9, 0.01)))