codebook.rsa

 1"""
 2This module defines the RSA public-key algorithm.
 3
 4The RSA cryptosystem involves multiple steps:
 5key generation, key distribution, encryption, and decryption.
 6This solution focuses solely on the **encryption** stage.
 7
 8It implements the encryption operation using the PKCS1 v1.5 padding scheme.
 9"""
10import base64
11import secrets
12
13
14def _pkcs1v15(n: int, e: int, M: bytes) -> bytes:
15    """RSAES-PKCS1-V1_5 encryption operation
16
17    - `n` is the public modulus
18    - `e` is the public exponent
19    - `M` is the message to be encrypted - an octet string
20
21    See:
22      - <https://datatracker.ietf.org/doc/html/rfc8017#section-7.2>
23      - <https://stackoverflow.com/q/70910756/5818220>
24    """
25    k = (n.bit_length() - 1) // 8 + 1
26
27    # Length checking
28    if len(M) > k - 11:
29        raise ValueError("message too long")
30
31    # EME-PKCS1-v1_5 encoding
32    PS = bytes(secrets.randbelow(255) + 1 for _ in range(k - len(M) - 3))
33    EM = b"\x00\x02" + PS + b"\x00" + M
34
35    # RSA encryption
36    m = int.from_bytes(EM, "big")
37    c = pow(m, e, n)
38    C = c.to_bytes(k, "big")
39
40    return C
41
42
43def rsa(plaintext: str, *, public_key: tuple[int, int]) -> str:
44    """RSA public-key algorithm (Appendix J, page 379)
45
46    - `plaintext` is the message to be encrypted
47    - `public_key` is the tuple `(n, e)` consisting of the public modulus and exponent
48
49    Unlike the example in the book, practical applications of RSA require the
50    usage of a padding scheme; this implementation employs the PKCS1 v1.5
51    encryption operation as defined in RFC 8017.
52    """
53    message = bytes(plaintext, "utf-8")
54    ciphertext = _pkcs1v15(*public_key, message)
55    return base64.b64encode(ciphertext).decode()