Skip to content
Tutorials Center
My learning

Topics

Lesson 35 of 37 ยท Projects and Practice

Project: A Toy RSA Messenger

Build a small RSA messenger in Python with key pairs, fingerprints, block encryption, signatures and a break-it challenge on a weak key.

This project puts the cryptography chapter to work. You will build a toy messenger in which Alice and Bob each own an RSA key pair, exchange public keys, send signed and encrypted messages, and detect tampering. At the end you will break a deliberately weak key, to feel why key size matters.

The code is educational. It uses simplified randomized padding and no side-channel defenses, so it is not safe for real secrets. For anything real, use a vetted library. The goal is to see every number-theoretic step: primes from Miller-Rabin, keys from RSA, and the weaknesses from the attacks lesson.

Design

  • KeyPair: generate p, q, n, e, d; expose a public part (n, e).
  • fingerprint(public): a short SHA-256 hash so humans can compare keys over the phone.
  • encrypt(message, recipient_public): split into blocks, pad each with random bytes, apply m^e mod n.
  • sign(message, sender_key) and verify(...): hash, then exponentiate with d and e.
  • A message envelope that bundles ciphertext blocks and a signature.

Step 1: keys and fingerprints

Python Step 1: key pairs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The fingerprints differ for every key, so two people can confirm over a trusted channel that the key they received is the right one. That check is what defeats a man-in-the-middle attack.

Step 2: block encryption with padding

A 512-bit key encrypts at most 63 bytes at a time. We take blocks of 20 bytes, add a random 16-byte salt, mask the block with a hash of the salt and add a short check value. This is the simplified padding idea from the attacks lesson: equal blocks encrypt differently and bit flips are detected.

Python Step 2: encrypt and decrypt blocks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Equal messages give different ciphertexts, and the tampering attempt (multiplying a ciphertext block by 2^e) fails the integrity check.

Step 3: signatures

Alice signs the SHA-256 hash of her message with her private key. Bob verifies with her public key. Because the hash is 256 bits and the key is 512 bits, the hash fits below n (a real scheme such as PSS adds padding).

Python Step 3: signed envelopes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Only the right message, the right signature and the right public key give True. Notice the order: sign with your private key and verify with the sender's public key; the opposite of encryption, where you use the recipient's public key.

Step 4: break a weak key

Finally, see why 512-bit toy keys are not safe. We generate a 96-bit modulus and factor it with a library call in seconds, recovering the private key from the public one alone.

Python Step 4: factor the weak key and read the message

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The attacker needed no secret: factoring the public n gave ฯ†(n), hence d. Real keys use 2048 bits or more because the cost of factoring grows faster than any polynomial in the number of digits.

Extensions

  • Add hybrid encryption: encrypt a random 128-bit key with RSA and the long message with a stream built from SHA-256 in counter mode.
  • Store keys in a dictionary "address book" and print fingerprints when a new contact is added.
  • Replace RSA with the elliptic-curve scheme from the elliptic-curve lesson.
  • Add CRT decryption and time it against plain decryption.
sequenceDiagram
    participant A as Alice
    participant B as Bob
    A->>B: public key (n, e)
    B->>A: public key (n, e)
    Note over A,B: compare fingerprints out of band
    A->>B: Enc(Bob public, message) + Sign(Alice private, hash)
    B->>B: decrypt with own d, verify with Alice's e

The messenger protocol: keys, fingerprints, encrypted and signed messages.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. To send Bob a confidential message, which key do you use to encrypt?

    Only Bob's private key can decrypt what was encrypted with his public key.
  2. 2. To prove you wrote a message, which key makes the signature?

    Anyone can check it with your public key, but only you can produce it.
  3. 3. Why compare fingerprints out of band?

    A substituted key has a different fingerprint, which the two people notice when they compare.
  4. 4. What made the 96-bit key easy to break?

    Factoring n reveals phi(n) and therefore d.

Summary

  • A messenger needs key pairs, a way to authenticate keys (fingerprints), encryption and signatures.
  • Encrypt with the recipient's public key; sign with your own private key.
  • Randomized padding with an integrity check hides repeated messages and detects tampering.
  • Small moduli are factored easily: key size is the security parameter.

Next: Project: Factoring Benchmark