Danger

Nothing here should be used for any security purposes.

  • If you need cryptographic tools in a Python environment use pyca.

  • If you need efficient and reliable abstract math utilities in a Python-like environment consider using SageMath.

Birthday Paradox Computations

This module is imported with:

import toy_crypto.birthday

The classic Birthday Paradox example is to estimate the number of individuals (whose birthdays are uniformly distributed among 365 days of the year) for there to be at least a 0.5 probability of there being at least one pair of individuals who share the same birthday.

The function that returns a propbably is named P(), and the one that returns a quantile is named Q(). This follows the pattern of R’s qbirthday and pbirthday.

from toy_crypto import birthday

computed_n = birthday.Q(0.5, 367)
print(computed_n)

23

Birthday computations are useful for computing collision probabilites. Suppose you had a hash function (truncated to ) returning 32 bit hashes and you wished to know the probability of a collision if you hashed ten thousand items.

from toy_crypto import birthday
from math import isclose

n = 10_000
c = 2 ** 32

p = birthday.P(n, c)
assert isclose(p,  0.011574013876)

The birthday functions

toy_crypto.birthday.EXACT_THRESHOLD = 1000

With auto mode, the threshold for using exact or approximate modes.

toy_crypto.birthday.MAX_QBIRTHDAY_P = 0.99999999

Maximum probability that Q can handle.

toy_crypto.birthday.P(n: int, classes: int = 365, coincident: int = 2, mode: str = 'auto') → Prob

probability of at least 1 collision among n individuals for c classes”.

The “exact” method still involves floating point approximations and may be very slow for large n.

Raises:

ValueError – if not all arguments are positive integers.

Parameters:
Return type:

Prob

toy_crypto.birthday.Q(prob: float = 0.5, classes: int = 365, coincident: int = 2) → int

Returns minimum number n to get a probability of p for c classes.

Raises:

ValueError – if prop is not a probability.

Parameters:
Return type:

int