Danger

Nothing here should be used for any security purposes.

If you need cryptographic tools in a Python environment use pyca or PyNaCl.
If you need efficient and reliable abstract math utilities in a Python-like environment consider using SageMath.

Utility functions#

This module is imported with:

import toy_crypto.utils

Caution

Many libraries will have a module named utils, it is therefore unwise to do anything like

# This is unwise
from toy_crypto import utils

as you might later find yourself in trouble not knowing whose utils are being referred to.

toy_crypto.utils.digit_count(n: int, base: int = 10) → int[source]#

returns the number of digits (base b) of integer n.

Raises:

ValueError – if base < 1

Parameters:

n¶ (int)
base¶ (int, default: 10)

Return type:

int

Coding this is a math problem, not a string representation problem. Ideally the solution would be to use

\[d = \lfloor\log_b \| x \| + 1\rfloor\]

but that leads to erroneous results due to the precision limitations of math.log(). So a different approach is taken which correctly handles cases that would otherwise fail.

>>> from toy_crypto.utils import digit_count
>>> digit_count(999)
3
>>> digit_count(1000)
4
>>> digit_count(1001)
4
>>> digit_count(9999999999999998779999999999999999999999999999999999999999999)
61
>>> digit_count(9999999999999999999999999999999999999999999999999999999999999)
61
>>> digit_count(10000000000000000000000000000000000000000000000000000000000000)
62
>>> digit_count(0)
1
>>> digit_count(-10_000)
5

toy_crypto.utils.next_power2(n: int) → int[source]#

Returns smallest p such that \(2^p \geq n\).

Raises:: ValueError – if n is less than 1.
Parameters:: n¶ (int)
Return type:: int

This is yet another function where talking a logarithm (base 2 this time) would be the mathematically nice way to do things,

\[p = \lceil \log_2(n) \rceil\]

but because we may want to use this with large numbers, we have to worry floating point precision.

Because we are dealing with base 2, we can do all of our multiplications and and divisions by powers of 2 using bit shifts. I am not sure how Pythonic that leaves things.

toy_crypto.utils.nearest_multiple(n: int, factor: int, direction: str = 'round') → int[source]#

Returns multiple of factor that is near n.

Given an input number, n and a factor f returns m such that

\(f|m\) (f divides n);
\(\left|n - m\right| < f\)
(There is no multiples of f between n and m);

As a consequence this always returns n if n is a multiple of factor.

When n is not a multiple of factor, which of the two possible solutions to those conditions is returned depends on the value of of the direction parameter.

Parameters:

n¶ (int) – The integer get a nearby multiple of factor of
factor¶ (int) – The number that the returned values must be a multiple of.
direction¶ (str, default: 'round') –
Direction in which to round when n is not a multiple of factor

”next”
returns nearest multiple further from 0;

”previous”
returns nearest multiple toward 0;

”round”
returns nearest multiple and behaves like “previous” is if nearest multiples are equidistant from n

Raises:

ValueError – if direction is not one of ‘next’, ‘previous’, ‘round’.

Return type:

int

xor#

The utils.xor() and the class utils.Xor provide utilities for xoring strings of bytes together. There is some asymmetry between the two arguments. The message can be an collections.abc.Iterator as well as bytes. The pad arguement on the other hand, is expected to be bytes only (in this version.) The pad argument is will be repeated if it is shorter than the message.

Warning

The Byte type is just a type alias for int. There is no run time nor type checking mechanism that prevents you from passing an Iterator[Byte] message that contains integers outside of the range that would be expected for a byte. If you do so, bad things will happen. If you are lucky some exception from the bowels of Python will be raised in a way that will help you identify the error. If you are unlucky, you will silently get garbage results.

class toy_crypto.utils.Xor(message: Iterator[int] | bytes, pad: bytes) → None[source]#

Iterator that spits out xor of message with (repeated) pad.

The iterator will run through successful bytes of message xor-ing those with successive bytes of pad, repeating pad if pad is shorter than message.

Each iteration returns a non-negative int less than 256.

Parameters:

message¶ (Iterator[int] | bytes)
pad¶ (bytes)

toy_crypto.utils.xor(message: bytes | Iterator[int], pad: bytes) → bytes[source]#

Returns the xor of message with a (repeated) pad.

The pad is repeated if it is shorter than m. This can be thought of as bytewise Vigenère.

Parameters:

message¶ (bytes | Iterator[int])
pad¶ (bytes)

Return type:

bytes

>>> from toy_crypto.utils import xor
>>> message = b"Attack at dawn!"
>>> pad = bytes(10) + bytes.fromhex("00 14 04 05 00")
>>> modified_message = xor(message, pad)
>>> modified_message
b'Attack at dusk!'

Encodings for the RSA 129 challenge#

Martin Gardner first reported the Rivest, Shamir, and Adleman (RSA) in 1977. The examples and challenge described in it used an encoding scheme between text and (large) integers. This class provides an encoder and decoder for that scheme.

We will take the magic words, decrypted in 1995 by Atkins, Graff, Lenstra, and Leyland with the help of a large number of volunteers, from that challenge for our example:

>>> from toy_crypto.utils import Rsa129
>>> decrypted = 200805001301070903002315180419000118050019172105011309190800151919090618010705
>>> Rsa129.decode(decrypted)
'THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE'

And we will use an example from [Gardner, 1977].

>>> latin_text = "ITS ALL GREEK TO ME"
>>> encoded = Rsa129.encode(latin_text)
>>> encoded
9201900011212000718050511002015001305
>>> assert Rsa129.decode(encoded) == latin_text

class toy_crypto.utils.Rsa129[source]#

Text encoder/decoder used in RSA-129 challenge.

Encoding scheme from Martin Gardner’s 1977 article.

classmethod decode(number: int) → str[source]#

Decode number to text.

Parameters:: number¶ (int)
Return type:: str

classmethod encode(text: str) → int[source]#

Encode text to number

Parameters:: text¶ (str)
Return type:: int

Simple frozen bi-directional mapping#

For the Rsa129.encode() and Rsa129.decode(), as well as for methods in the toy_crypto.vigenere.Alphabet, I found myself needing to look up the index of a character within a string.

I very strongly recommend that people use the outstanding bidict library library instead of this. I include my own, inferior version, simply because I wanted to reduce dependencies.

>>> from toy_crypto.utils import FrozenBidict
>>> bi_mapping = FrozenBidict("ABCDEF")
>>> bi_mapping[2]
'C'
>>> bi_mapping.inverse['C']
2

This also can be initialized with a dictionary as long as the values in the the dictionary are hashable.

>>> d = { "eggs": "ok", "bacon": "yummy", "SPAM": "essential"}
>>> tastes = FrozenBidict(d)
>>> tastes["bacon"]
'yummy'
>>> tastes.inverse["essential"]
'SPAM'

The FrozenBidict is type parameterized, with types representing the forward direction of the mapping, so the annotated versions of the above would be

bi_mapping: FrozenBidict[int, str] = FrozenBidict("ABCDEF")
tastes: FrozenBidict[str, str] = FrozenBidict(d)

class toy_crypto.utils.FrozenBidict(s: Sequence | Mapping) → None[source]#

A bidirectional dictionary-like object.

This is a very limited utility just for specific uses in this project. You will find more robust, flexible, and much more broadly applicable classes and functions in the outstanding bidict library.

Parameters:: s¶ (Sequence[TypeVar(V, bound= Hashable)] | Mapping[TypeVar(K, bound= Hashable | int), TypeVar(V, bound= Hashable)])

property inverse: Mapping#: The inverse map.

Find zero#

There are excellent equation and function solvers available in Python. This is not one of them.

This was built explicitly has a helper function for the quantile() function in the birthday module. As such it assumes that

The the input function, \(f(n)\), is non-decreasing in n;
\(f: \mathbb{Z} \to \mathbb{R}\), or in Python has the type signature def f(n: int) -> float;
You want the least n for which \(f(n) \geq 0\) even though \(f(n -1)\) might be closer to 0;
You don’t mind using an embarrassingly kludgy implementation because for some reason I struggled with what should be a simple piece of code.

toy_crypto.utils.find_zero(function: Callable[[int], float], initial_estimate: int = 0, initial_step: int = 256, max_iterations: int = 500, lower_bound: int | None = None, upper_bound: int | None = None) → int[source]#

Finds (nearly) smallest n for f(x) such that f(n) > 0.

Performs a binary search for +0 of a non-decreasing function, \(f(n)\), to return an \(n_0\) such that \(f(n_0) \geq 0 \land f(n_0 - 1) < 0\).

Parameters:

function¶ (Callable[[int], float]) – The function for which you want to find the zero. Must be non-decreasing.
initial_estimate¶ (int, default: 0) – The closer this is to the actual zero, the less the computer will need to work to find it.
initial_step¶ (int, default: 256) – The initial step size.
max_iterations¶ (int, default: 500) – The number of times this will compute the function before it just gives you its best estimate that that time.
lower_bound¶ (int | None, default: None) – Smallest meaningful n in f(n). If None, treated as -math.inf.
upper_bound¶ (int | None, default: None) – Largest meaningful n in f(n). If None, treated as math.inf.

Raises:

ValueError – if initial_step isn’t positive.
ValueError – if not lower_bound <= initial_estimate <= upper_bound.

Return type:

int

Warning

Results are undefined if function is not non-decreasing or if function isn’t defined for every n in [lower_bound, upper_bound].

Caution

If f(n) is close to flat around n₀ and n₀ is large then the result may be approximate.

Caution

This has only been tested for use in toy_crypto.birthday.quantile().

Added in version 0.6.

Example#

Let’s take \(f(n) = n^3 - 40\) as an example. It is non-decreasing and has a real zero at \(\sqrt[3]{40} \approx 3.42\). The smallest integer equal to or greater than that is 4.

>>> from toy_crypto.utils import find_zero
>>> find_zero(lambda n: n ** 3 - 40)
4

Once again, note that a proper solver would have been able to solve this analytically, without resorting to a binary search or restricting to non-decreasing functions only. But this root finder is built to be just good enough for the specific need in toy_crypto.birthday.quantile().

Utility functions#

xor#

Encodings for the RSA 129 challenge#

Simple frozen bi-directional mapping#

Find zero#

Example#

This Page