O
Back to blogs
•14 min readCryptography

Asymmetric Cryptography Explained: Public Keys, Private Keys, and RSA

Diagram showing how public and private keys are used for confidentiality and digital signatures

Asymmetric cryptography solves one of the hardest problems in security: how two parties can communicate securely without first sharing the same secret. Instead of a single shared key, it uses a mathematically linked pair of keys: one public, one private.

The public key can be distributed widely. The private key must remain secret. What makes the system useful is the trapdoor property: the public-key operation is easy to perform, but reversing it without the private key is computationally infeasible.

1. What asymmetric cryptography is really doing

Asymmetric cryptography is used for three big jobs:

  • Confidentiality: encrypt with a public key, decrypt with the matching private key.
  • Authenticity: sign with a private key, verify with the matching public key.
  • Key exchange: safely establish a shared secret that can later be used with a fast symmetric cipher like AES.

Confidentiality

Alice locks with Bob's public key

Bob publishes a public key. Alice uses it to encrypt a message. Only Bob's private key can open that ciphertext.

Authenticity

Bob signs with his private key

Bob signs a digest of the message with his private key. Anyone with Bob's public key can verify it really came from him and was not modified.

2. How the public key and private key are created

The exact process depends on the algorithm. In RSA, both keys are derived from the same hidden arithmetic structure. In elliptic curve systems, the private key is a random number and the public key is a point computed from it. The crucial pattern is the same: generate a secret first, then derive a public value that is easy to share but hard to invert.

Flowchart showing the major steps of RSA key generation

For RSA, key generation works like this:

1. Prime generation

A cryptographically secure random number generator picks large candidate numbers, and probabilistic primality tests such as Miller-Rabin are used until two strong primes p and q are found.

2. Build the modulus

Multiply the primes to form n = p x q. This modulus becomes part of both keys and defines the arithmetic space used by RSA.

3. Compute phi(n)

For textbook RSA, phi(n) = (p - 1)(q - 1). Real libraries may use Carmichael's function instead, but the idea is the same: we need the size of the invertible set modulo n.

4. Choose the public exponent

Pick e so that gcd(e, phi(n)) = 1. The common choice is 65537 because it is large enough for safety and small enough for fast verification and encryption.

5. Compute the private exponent

Solve d = e^-1 mod phi(n) with the Extended Euclidean Algorithm. This value is secret because it lets us reverse the public-key operation.

6. Package the keys

The public key is (n, e). The private key is (n, d), often with extra CRT values dp, dq, and qInv to speed up decryption and signing.

Public key = (n, e)
Private key = (n, d)

That shared modulus n is not the secret. The secret is the knowledge needed to derive d, which comes from the hidden factorization of n. If an attacker can factor n into p and q, the system is broken. That is why RSA uses very large numbers.

How ECC key pairs are created

Elliptic Curve Cryptography is conceptually simpler to describe:

  • Pick a random private scalar d.
  • Multiply the curve's base point G by d to get the public key Q = dG.
  • Publish Q and keep d secret.

Recovering d from Q is the elliptic curve discrete logarithm problem, which is believed to be hard. This is why ECC can often deliver similar security with much smaller keys than RSA.

3. Common asymmetric algorithms and where they fit

RSA

Encryption, key transport, and digital signatures

Security comes from the difficulty of factoring a very large modulus n back into p and q.

Elliptic Curve Cryptography

TLS, Signal, cryptocurrencies, and compact signatures

A random private scalar is chosen, and the public key is produced by scalar multiplication on an elliptic-curve base point.

Diffie-Hellman / ECDH

Shared secret establishment

Each party publishes a public value derived from a private secret, and both sides independently derive the same shared key without sending it directly.

In practice, asymmetric algorithms are usually not used to encrypt entire files or long chat histories directly. They are slower than symmetric ciphers. A common pattern is hybrid cryptography: use RSA or ECDH to protect a temporary secret key, then use AES or ChaCha20 to encrypt the bulk data efficiently.

4. RSA in detail

RSA is the classic example because its structure is visible and easy to teach. Real RSA uses very large integers and padding schemes such as OAEP and PSS, but the core arithmetic is still the same.

Diagram showing RSA encryption, decryption, signing, and verification

Encryption

C = M^e mod n

Anyone with the public key can transform plaintext M into ciphertext C, but only the private key holder should be able to reverse it safely.

Decryption

M = C^d mod n

The private exponent d undoes the public-key operation because d was chosen as the modular inverse of e.

Signing

S = H(M)^d mod n

The signer applies the private key to a hash of the message, proving possession of the secret key without revealing it.

Verification

H(M) = S^e mod n

Anyone can use the public key to verify that the signature matches the expected digest and was not forged or altered.

Worked RSA example with actual numbers

The values below are intentionally tiny so we can calculate them by hand. They are not secure, but they clearly show how the math fits together.

p = 61
q = 53
n = p x q = 3233
phi(n) = (61 - 1)(53 - 1) = 3120
Choose e = 17
d = 2753 because 17 x 2753 mod 3120 = 1

That gives us:

  • Public key: (3233, 17)
  • Private key: (3233, 2753)

Encryption example

Let the plaintext be M = 65.

C = M^e mod n
C = 65^17 mod 3233
C = 2790

So the ciphertext sent across the network is 2790.

Decryption example

M = C^d mod n
M = 2790^2753 mod 3233
M = 65

The private exponent reverses the public operation and recovers the original message.

Signature example

Suppose the hash of a message is 42. Bob signs that digest with the private key:

S = H(M)^d mod n
S = 42^2753 mod 3233
S = 3065

Anyone can verify using the public key:

H(M) = S^e mod n
H(M) = 3065^17 mod 3233
H(M) = 42

Because the verified value matches the expected digest, the signature is valid.

5. Detailed algorithm summary

RSA key generation algorithm

  1. Choose large random primes p and q.
  2. Compute n = p x q.
  3. Compute phi(n) = (p - 1)(q - 1).
  4. Choose e such that 1 < e < phi(n) and gcd(e, phi(n)) = 1.
  5. Compute d such that d x e mod phi(n) = 1.
  6. Publish (n, e) and keep (n, d) secret.

RSA encryption algorithm

  1. Encode the plaintext as an integer M in the range 0 to n - 1.
  2. Apply secure padding such as OAEP in real systems.
  3. Compute C = M^e mod n.
  4. Send ciphertext C.

RSA decryption algorithm

  1. Receive ciphertext C.
  2. Compute M = C^d mod n.
  3. Remove the padding structure.
  4. Decode M back into the original plaintext bytes.

RSA signing and verification algorithm

  1. Hash the message with a secure hash function.
  2. Sign the hash using the private key: S = H(M)^d mod n.
  3. Verify by computing S^e mod n with the public key.
  4. Accept only if the result matches the expected hash and padding format.

6. Important security notes

  • Never use textbook RSA directly. Modern systems require padding such as OAEP for encryption and PSS for signatures.
  • Use large keys. Tiny values are useful for teaching only. Production RSA commonly uses 2048-bit or 3072-bit moduli.
  • Protect the private key operationally. If the key leaks through malware, logs, backups, or side channels, the mathematics no longer helps.
  • Use asymmetric crypto as part of a system. TLS, SSH, code signing, and messaging protocols combine it with hashes, certificates, random number generation, and symmetric encryption.

Conclusion

Asymmetric cryptography works because one direction of the math is easy and the reverse direction is hard without secret information. That idea gives us public-key encryption, digital signatures, and secure key exchange.

RSA is the clearest place to see the mechanism: generate two primes, derive n, choose e, compute d, then use the public key for open operations and the private key for secret ones. Once that foundation clicks, the rest of modern cryptography becomes much easier to reason about.