Danger
Nothing here should be used for any security purposes.
RSA Key Generation#
This page describes some of things that are part of
the toy_crypto.rsa module.
They are imported with:
from toy_crypto import rsa
Not every pair of primes, \((p, q)\),
is suitable for creating a good PrivateKey.
With public modulus \(N = pq\), and public exponent, e,
some of the conditions that should hold of them are
They should be large enough so that N is the desired bit size;
They should each be not much less then \(\sqrt{N}\);
But they shouldn’t be too close to each other, either;
The totient of N must be relatively prime to the public exponent, e. That is \(\gcd(p - 1, e)\) and \(\gcd(q - 1, e)\) must each be 1.
The prime generation function defined in appendix A.1.3 FIPS 186-B [NIST, 2023] guarentees those conditions are met. It is clever in that it checks those conditions on candidate primes before testing whether those candidates are prime, which is a much more computationally expensive test.
The algorithm defined in §6.3.1} of NIST-SP-56b [NIST, 2019] imposes the additional condition that the secret decryption exponent, d, of a private key is not less than \(\sqrt{N}\).
The functions in this module,
fips186_prime_gen() and key_gen(),
partially follow those specifications,
but they do not enforce the minimum strength
specifications (2048-bit moduli).
I want to be able to generate some extremely weak
keys for demonstration purposes.
Warning
Faithfully following (which we don’t here) secure algorithms does not mean that an implementation is secure. These are not.
Examples#
So that documentation building doesn’t take too long, we will use a tiny key size.
# Do not use RSA keys smaller than 2048 bits,
# Do as I say, not as I do
pub_key, priv_key = rsa.key_gen(strength=56, key_size=512)
assert pub_key.N.bit_length() == 512
Now we set up a message to encrypt with the tiny key. Any integer we encryption with a 512 bit key must be less than \(2^{512}\). OAEP padding (with SHA1) would take up 322 bits, so we will just use primitive RSA.
message = int.from_bytes(b"Attack @ dusk!")
assert message.bit_count() < 512
ctext = pub_key.encrypt(message)
decrypted = priv_key.decrypt(ctext)
assert message == decrypted
The API#
- toy_crypto.rsa.fips186_prime_gen(n_len: int, e: int = 65537, k: int = 4) tuple[int, int][source]#
Prime generation from Appendix A.1.3 of FIPS 186-5v2
- Parameters:
- Raises:
ValueError – if
eis out of range or odd.Exception – if it fails to find suitable primes after trying really hard.
- Return type:
- toy_crypto.rsa.key_gen(strength: int = 112, key_size: int = 2048, e: int = 65537) tuple[PublicKey, PrivateKey][source]#
Generates private key.
- Parameters:
- Raises:
ValueError – if bit_size is even smaller that the small values allowed by this toy.
ValueError – if bit_size doesn’t correspond to an even number of bytes. (This is not a requirement of standards, but is of this implementation.)
ValueError – if e is out of range or is not odd.
ValueError – if key_size doesn’t provide target strength.
Exception – if key that would be generated doesn’t seem to work.
Exception – if prime generation fails.
- Return type:
Warning
This allows for the generation of unconscionably small keys. But that is ok, because this is a toy implementation in lots of other respects, too.
Partially follows NIST SP 80056B, §6.3.1.