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.

RSA#

Imported with:

import toy_crypto.rsa

Let’s see a simple example, from the original publication describing the RSA algorithm. This will require the text decoding scheme used then which is in toy_crypto.utils.Rsa129.decode().

import toy_crypto.rsa as rsa
from toy_crypto.utils import Rsa129

# From the challenge itself
modulus=114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541
pub_exponent=9007
ctext=96869613754622061477140922254355882905759991124574319874695120930816298225145708356931476622883989628013391990551829945157815154

# We have since learned p and q
p=3490529510847650949147849619903898133417764638493387843990820577
q=32769132993266709549961988190834461413177642967992942539798288533

priv_key = rsa.PrivateKey(p, q, pub_exponent = pub_exponent)

pub_key = priv_key.pub_key
assert pub_key.N == modulus

decrypted = priv_key.decrypt(ctext)  # This is a large int

# Now the Rsa129 text decoder
ptext = Rsa129.decode(decrypted)
print(ptext)

THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE

class toy_crypto.rsa.PublicKey(modulus: int, public_exponent: int) → None[source]#

Public key from public values.

Parameters:

modulus (int)
public_exponent (int)

property N: int#: Public modulus N.

property e: int#: Public exponent e

encrypt(message: int) → int[source]#

Primitive encryption with neither padding nor nonce.

Raises:

ValueError – if message < 0
ValueError – if message isn’t less than the public modulus

Parameters:

message (int)

Return type:

int

oaep_encrypt(message: bytes, label: bytes = b'', hash_id: str = 'sha256', mgf_id: str = 'mgf1SHA256', _seed: bytes | None = None) → bytes[source]#

RSA OAEP encryption.

Parameters:

message (bytes) – The message to encrypt.
label (bytes, default: b'') – Rarely used. Just leave as default.
hash_id (str, default: 'sha256') – Name of the hash function.
mgf_id (str, default: 'mgf1SHA256') – Name of the MGF function (with hash).
_seed (bytes | None, default: None) – Used for testing only. OAEP is not supposed to be deterministic.

Raises:

ValueError – if hash or MGF is not recognized.
ValueError – if lengths of inputs exceed what modulus and hash sizes can accommodate.

Return type:

bytes

RFC 8017 Section 7.1.1

class toy_crypto.rsa.PrivateKey(p: int, q: int, pub_exponent: int = 65537) → None[source]#

RSA private key from primes p and q.

This does not perform any sanity checks on p and q. It is your responsibility to ensure that p and q are prime

Raises:

ValueError – if e is not coprime with lcm(p - 1, q - 1).

Parameters:

p (int)
q (int)
pub_exponent (int, default: 65537)

decrypt(ciphertext: int) → int[source]#

Primitive decryption.

Parameters:: ciphertext (int) – Ciphertext as int
Raises:: ValueError – if ciphertext is out of range for this key.
Return type:: int

property e: int#: Public exponent.

oaep_decrypt(ciphertext: bytes, label: bytes = b'', hash_id: str = 'sha256', mgf_id: str = 'mgf1SHA256') → bytes[source]#

RSA OAEP decryption.

Parameters:

ciphertext (bytes) – The message to encrypt.
label (bytes, default: b'') – Rarely used.
hash_id (str, default: 'sha256') – Name of the hash function.
mgf_id (str, default: 'mgf1SHA256') – Name of the MGF function (with hash).

Raises:

ValueError – if hash or MGF is not recognized.
DecryptionError – on various decryption errors. If unsafe error reporting is enabled, details of decryption errors will be provided.

Return type:

bytes

property pub_key: PublicKey#

The public key corresponding to self.

The public key does not contain any secrets.

toy_crypto.rsa.default_e() → int[source]#

Returns the default public exponent, 65537

Return type:: int

OAEP utilities#

Primitive RSA is deterministic, so it completely fails to provide IND-CPA security. It is also vulnerable to chosen ciphertext attacks. OAEP (Optimized Assymmetric Encryption Padding) is designed to address both of those when properly implemented. This module does not provide a proper implemenation.

Much of the code here attempts to follow RFC 8017, particularly section 7.1 and appendix B.2. My intention in doing that was to help me better understand OAEP. This is not intended to be interoperable with things out there in the world. To whatever extent it is interoperable with the world must not be taken as an invitation to use it that way.

Examples#

RSA keys used with OAEP need to have moduli large enough to handle a couple of hash digests and a few other bytes, so we will use a 1024-bit key for our examples.

key2048 is a 2048-bit private key already set up in some undisplayed code.

Just showing that the key exists and is the right size.

# key2048 = ...
pub2048 = key2048.pub_key
assert  2048 - 7 < pub2048.N.bit_length() <= 2048

And lets demo an unfortunate (unless you are an attacker) property of primitive RSA. Our primitive encryption and decryption functions take and yield integers

message = b"My hovercraft is full of eels"
i_message = rsa.Oaep.os2ip(message)

prim_ctext1 = pub2048.encrypt(i_message)
assert key2048.decrypt(prim_ctext1)

So far so good, but sadly, the encryption of the same message always yields the same ciphertext.

# same key and message as above
prim_ctext2 = pub2048.encrypt(i_message)
assert prim_ctext2 == prim_ctext1

# same message and keys as above
oaep_ctext1 = pub2048.oaep_encrypt(message)
decrypted1 = key2048.oaep_decrypt(oaep_ctext1)
assert decrypted1 == message

oaep_ctext2 = pub2048.oaep_encrypt(message)
decrypted2 = key2048.oaep_decrypt(oaep_ctext2)
assert decrypted2 == message

# but now we see that the two ciphertexts are different
assert oaep_ctext1 != oaep_ctext2

A (very limted) choice of hashes#

For my purposes, I could have just hardcoded use of hashlib.sha256() or a more modern one, but most of published test vectors for RSA-OAEP use hashlib.sha1().

For reasons I don’t understand, I had difficulty getting these type definition within the Oaep class, so those are given module scope.

type toy_crypto.rsa.HashFunc = Callable[[bytes], hashlib._Hash]#: Type for hashlib style hash function.

type toy_crypto.rsa.MgfFunc = Callable[[bytes, int, str], bytes]#: Type for RFC8017 Mask Generation Function.

The (short) lists of supported hash and mask generation functions are attributes of the Oaep class, as are the classes to describe them. Also note that these are more sanely and readably defined than what may appear in the automatically generated documentation.

Oaep.KNOWN_HASHES: dict[str, HashInfo]

Hashes known for OAEP. keys will be hashlib names.

{ 'sha256': HashInfo(hashlib_name='sha256',
                     function=<built-in function openssl_sha256>,
                     digest_size=32,
                     input_limit=2305843009213693951),
  'sha1': HashInfo(hashlib_name='sha1',
                   function=<built-in function openssl_sha1>,
                   digest_size=20,
                   input_limit=18446744073709551615)}

Oaep.KNOWN_MGFS: dict[str, MgfInfo]

Known Mask Generation Functions.

{ 'mgf1SHA256': MgfInfo(algorithm='id_mgf1',
                        hashAlgorithm='sha256',
                        function=<staticmethod(<function Oaep.mgf1 at 0x7f2b4c6a2200>)>),
  'mgf1SHA1': MgfInfo(algorithm='id_mgf1',
                      hashAlgorithm='sha1',
                      function=<staticmethod(<function Oaep.mgf1 at 0x7f2b4c6a2200>)>)}

Integers, octet-streams, and masks#

Primitive RSA operations on integers, but OAEP is designed for encryption and decryption of sequences of bytes, or octet-streams in the parlence of the standards. The standards define two functions, I2OSP and OS2IP for those conversions. I don’t implement them as in the standards, but use Python standard library utililties. So class methods Oaep.i2osp() and Oaep.os2ip() are wrappers for standard library method int.to_bytes() and class method int.from_bytes().

static Oaep.i2osp(n: int, length: int) → bytes[source]

Integer to an octet string of length length.

Implements function from RFC 8017 §4.1.

Parameters:

n (int) – A non-negative integer
length (int) – Length of returned bytes object

Raises:

ValueError – if n is negative.
ValueError – if n cannot fit in length bytes

Return type:

bytes

Warning

When called from a decryption operation, exceptions should be caught and handled discretely.

All operations big-endian.

static Oaep.os2ip(x: bytes) → int[source]

octet-stream to unsigned big-endian int.

Implements function from RFC 8017 §4.2.

Parameters:: x (bytes) – The octet-stream (bytes) you want to make an int from.
Return type:: int

Returned is a non-negative integer.

All operations are big-endian.

A dog with a big rear-end — Chena, like all operations in this class, is big-endian; although in her case it is her rear end is bigger than her bytey end.#

The security that OEAP offers comes from the clevernesss of applying a mask to the plaintext, while keeping the seed for the mask out of the clear. The mask is generated by a mask generation function, MGF1 in the standards. It is a lot like HKDF, which probably would have used had it been around when OAEP was first developed.

static Oaep.mgf1(seed: bytes, length: int, hash_id: str) → bytes[source]

Mask generation function.

Generates a unique mask of length length as described in appendix B.2.1 of RFC 8017.

Parameters:

seed (bytes) – This should come from a CSPRNG
length (int) – Length in bytes of the mask to generate.
hash_id (str) – The name hash function in KNOWN_HASHES.

Raises:

ValueError – if length \(> 2^{32}\) bytes.
ValueError – if hash_id is unknown.

Return type:

bytes

Full `Oaep` class listing#

All of the OAEP bits and piece, including the ones documented above.

class toy_crypto.rsa.Oaep[source]#

Tools and data for OAEP.

Although this attempts to follow RFC 8017 in many respects, this is not designed to be interoperable with compliant keys and ciphertext.

class HashInfo(*, hashlib_name: str, function: HashFunc, digest_size: int, input_limit: int) → None[source]#

Information about hash function

Parameters:

hashlib_name (str) – Name as known by hashlib
function (TypeAliasType) – The callable function
digest_size (int) – in bytes
input_limit (int) – in bytes

Note that names and identifiers here do not conform to RFCs. These are not mean to be interoperable with anything out in the world.

digest_size: int#: in bytes

function: TypeAliasType#: The callable function itself

hashlib_name: str#: Name as known by hashlib

input_limit: int#: maximum input, in bytes

KNOWN_HASHES: dict[str, HashInfo] = {'sha1': Oaep.HashInfo(hashlib_name='sha1', function=<built-in function openssl_sha1>, digest_size=20, input_limit=18446744073709551615), 'sha256': Oaep.HashInfo(hashlib_name='sha256', function=<built-in function openssl_sha256>, digest_size=32, input_limit=2305843009213693951)}#: Hashes known for OAEP. keys will be hashlib names.

KNOWN_MGFS: dict[str, MgfInfo] = {'mgf1SHA1': Oaep.MgfInfo(algorithm='id_mgf1', hashAlgorithm='sha1', function=<staticmethod(<function Oaep.mgf1>)>), 'mgf1SHA256': Oaep.MgfInfo(algorithm='id_mgf1', hashAlgorithm='sha256', function=<staticmethod(<function Oaep.mgf1>)>)}#: Known Mask Generation Functions.

class MgfInfo(*, algorithm: str, hashAlgorithm: str, function: MgfFunc) → None[source]#

Information about Mask Generation function.

Parameters:

algorithm (str) – Name of the algorithm.
hashAlgorithm (str) – Key in KNOWN_HASHES.
function (TypeAliasType) – A Callable mask generation function

classmethod allow_unsafe_messages(allow: bool = True) → None[source]#

Allow (or disallow) verbose DecryptionError messages.

Parameters:: allow (bool, default: True)
Return type:: None

classmethod are_unsafe_messages_allowed() → bool[source]#

Does what it says on the tin.

Return type:: bool

static i2osp(n: int, length: int) → bytes[source]#

Integer to an octet string of length length.

Implements function from RFC 8017 §4.1.

Parameters:

n (int) – A non-negative integer
length (int) – Length of returned bytes object

Raises:

ValueError – if n is negative.
ValueError – if n cannot fit in length bytes

Return type:

bytes

Warning

When called from a decryption operation, exceptions should be caught and handled discretely.

All operations big-endian.

static mgf1(seed: bytes, length: int, hash_id: str) → bytes[source]#

Mask generation function.

Generates a unique mask of length length as described in appendix B.2.1 of RFC 8017.

Parameters:

seed (bytes) – This should come from a CSPRNG
length (int) – Length in bytes of the mask to generate.
hash_id (str) – The name hash function in KNOWN_HASHES.

Raises:

ValueError – if length \(> 2^{32}\) bytes.
ValueError – if hash_id is unknown.

Return type:

bytes

static os2ip(x: bytes) → int[source]#

octet-stream to unsigned big-endian int.

Implements function from RFC 8017 §4.2.

Parameters:: x (bytes) – The octet-stream (bytes) you want to make an int from.
Return type:: int

Returned is a non-negative integer.

All operations are big-endian.

Key Generation#

The algorithm used in fips186_prime_gen() roughly follows appendix A.1.3 FIPS 186-B [2023] for generation of suitable prime numbers. A nice thing about that algorithm is that where possible it checks that a randomly generated number meets various criteria prior to runing primality tests. The algorithm used is key_gen() roughly follows §6.3.1} of NIST-SP-56b [2019]. These, however, do not enforce the minimum modulus size requirements of the standards. 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.

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

toy_crypto.rsa.fips186_prime_gen(n_len: int, e: int = 65537, k: int = 4) → tuple[int, int][source]#

Prime generation from Appendix A of FIPS 186-5

Parameters:

n_len (int) – Desired length of modulus in bits
e (int, default: 65537) – Public exponent.
k (int, default: 4) – Trials for primality testing.

Raises:

ValueError – if e is out of range or odd.
Exception – if it fails to find a suitable prime after trying really hard.

Return type:

tuple[int, int]

toy_crypto.rsa.key_gen(strength: int = 112, key_size: int = 2048, e: int = 65537) → tuple[PublicKey, PrivateKey][source]#

Generates private key.

Parameters:

strength (int, default: 112) – Intended security parameter (in bits).
key_size (int, default: 2048) – size in bits of desired modulus.
e (int, default: 65537) – public exponent.

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:

tuple[PublicKey, PrivateKey]

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.

RSA#

OAEP utilities#

Examples#

A (very limted) choice of hashes#

Integers, octet-streams, and masks#

Full Oaep class listing#

Key Generation#

This Page

Full `Oaep` class listing#