#!/usr/bin/env python3

import sys
from math import factorial

if len(sys.argv) == 1 or '-h' in sys.argv or '--help' in sys.argv:
    print('''
Usage:
  {self} <fingerprint-length> <number-of-attacked-bits> <bits-checked>

This tool calculates the likelihood, given the current settings,
for an attacker to get away with a forged fingerprint.

For example, assuming an attacker can brute force 72 bits of your 128-bit
fingerprint and you check a random block of 32 bits:
    {self} 128 72 32
'''.lstrip().format(self=sys.argv[0]))
    exit(1)

def choose(x, y):
    # combinatorial 'x choose y' algorithm
    return factorial(x) / (factorial(x - y) * factorial(y))

# fingerprint length in bits,
# attacker bits (how many bits can an attacker forge),
# shown bits (how many bits are randomly checked)
fpbits, attbits, shownbits = map(int, sys.argv[1:])

if attbits >= fpbits:
    print('If the attacker can brute force the whole fingerprint, there is no point'
        + ' verifying fingerprints.')
    exit(0)

if shownbits > attbits:
    print(('Attacker can only attack {} bits and you check {} bits. An attacker can '
        + 'never mount an attack.').format(attbits, shownbits))

c = shownbits
n = fpbits
m = attbits
s = 2  # alphabet is binary

result = 0
for d in range(999):
    if d <= m and d <= c and 0 <= c-d <= n-m:
        print('d={} is acceptable'.format(d))
    else:
        continue
    p1 = choose(m, d)
    p2 = choose(n-m, c-d)
    p3 = (1 / pow(s, c-d))
    result += p1 * p2 * p3

result = 1/choose(n, c) * result

print('Prob(successful attack) =', result * 100, '%')

result = 1/result
if result > 1e7:
    result = str(round(result/1e6)) + 'M'
elif result > 1e4:
    result = str(round(result/1e3)) + 'k'
elif result > 10:
    result = round(result)

print('Or 1 in', result)