Introduction to Cryptography and RSA

·

Cryptography is the science of securing information, ensuring that only intended recipients can access and understand transmitted messages. At its core, it combines mathematical theory with practical implementation to protect data in an increasingly digital world. One of the most influential developments in modern cryptography is the RSA algorithm—an asymmetric encryption method that revolutionized secure communication over untrusted networks.

This article explores the foundational principles of cryptography, from early symmetric systems like the one-time pad to the breakthrough of public key cryptography. We’ll walk through the mechanics of RSA, explain the mathematics behind its security, and discuss its real-world applications and limitations.

The Basics of Cryptography

Cryptography ensures confidentiality, integrity, and authenticity in digital communication. It allows two parties—commonly referred to as Alice and Bob—to exchange messages securely, even when adversaries may be monitoring the channel.

Symmetric Cryptography: The One-Time Pad

The simplest form of encryption is symmetric cryptography, where the same key is used for both encryption and decryption. A classic example is the one-time pad.

Suppose Alice wants to send a secret binary message (e.g., 01101) to Bob. They first meet in person to generate a shared random key of the same length (e.g., 10110). To encrypt, Alice applies the XOR operation between each bit of the message and the key:

Message:   0 1 1 0 1  
Key:       1 0 1 1 0  
XOR:       1 1 0 1 1 → Ciphertext

Bob decrypts by applying XOR again with the same key, recovering the original message. Since XOR applied twice cancels out, this method is perfectly secure—provided the key is truly random, used only once, and kept secret.

👉 Discover how modern encryption builds on these foundational ideas.

However, this system has a major flaw: the key must be as long as the message, requiring prior secure coordination. If Alice and Bob can meet securely to exchange keys, why not just deliver the message directly?

To work around this, some systems reuse shorter keys repeatedly. But this introduces patterns that statistical analysis can exploit—especially given predictable language structures (like common letter combinations in English). Reused keys weaken security dramatically.

Pseudorandom Number Generators (PRNGs)

A more practical approach uses pseudorandom number generators (PRNGs). These algorithms generate long sequences of seemingly random bits from a short initial "seed." Alice and Bob agree on a seed beforehand; then both use it to generate identical keystreams for encryption and decryption.

While efficient, PRNG-based systems rely on unproven assumptions: we don’t know whether truly secure PRNGs exist. Moreover, they still require pre-shared secrets, limiting their usefulness in open environments like the internet.

A New Approach: Asymmetric Cryptography

Symmetric methods face a fundamental challenge: how do two strangers establish a shared secret without prior contact?

Asymmetric cryptography solves this by using two different keys: one for encryption (public) and one for decryption (private). This breakthrough eliminates the need for pre-shared secrets.

A Physical Analogy: Locks and Keys

Imagine Alice wants to send contraband to Bob in a surveillance-heavy regime. Both have unique locks, but only they hold their respective keys. Here’s how they communicate securely:

  1. Alice puts the item in a box and locks it with her lock.
  2. She sends it to Bob, who adds his own lock.
  3. Bob returns the double-locked box.
  4. Alice removes her lock and sends it back.
  5. Bob unlocks his lock and accesses the contents.

No one else can open the box at any stage.

In cryptography, Bob’s “lock” can be publicly distributed—his public key—while his private key remains secret. Anyone can encrypt messages using his public key, but only he can decrypt them.

👉 See how decentralized systems use similar trustless models today.

This model enables secure communication between parties who’ve never met—a cornerstone of online security.

The Mathematics Behind RSA

RSA, named after Rivest, Shamir, and Adleman, is one of the first practical implementations of public key cryptography. Its security relies on the computational difficulty of factoring large integers.

Key Concepts: Public and Private Keys

In RSA:

Only the owner holds the private key, making decryption impossible for eavesdroppers—even if they know the public key.

Step-by-Step: How RSA Works

1. Key Generation (Bob's Side)

Bob generates two large prime numbers, p and q, each about 250 bits long (~60 digits). He computes:

He selects an exponent e (commonly 3 or 65537) such that e and ϕ(N) are coprime. Then he calculates d, the modular inverse of e modulo ϕ(N):

d × e ≡ 1 mod ϕ(N)

2. Encryption (Alice's Side)

Alice wants to send message x (as a number less than N). She computes:

Ciphertext = x^e mod N

She sends this value to Bob.

3. Decryption (Bob's Side)

Bob receives x^e mod N. Using his private key d, he computes:

(x^e)^d mod N = x^(ed) mod N

Since ed ≡ 1 mod ϕ(N), Euler’s Theorem guarantees:

x^(k⋅ϕ(N)+1) ≡ x mod N

Thus, Bob recovers the original message x.

Why RSA Is Secure

RSA’s strength lies in prime factorization hardness:

No known classical algorithm can factor large numbers efficiently. Brute-force methods scale exponentially with digit length, making attacks impractical.

However, quantum computers threaten RSA’s future. Shor’s algorithm can factor large numbers in polynomial time on a quantum machine—highlighting the need for post-quantum cryptographic alternatives.

Benefits and Limitations of RSA

Advantages

Drawbacks

In practice, RSA is often used to securely exchange a symmetric session key, after which faster algorithms (like AES) handle bulk data encryption.

Authentication Using Public Key Cryptography

Beyond encryption, RSA enables authentication—proving identity.

If Alice wants to sign a message:

  1. She applies her private key to create a signature.
  2. She sends the message + signature + her public key.
  3. Bob verifies by applying her public key; if he recovers the original message, he knows only Alice could have signed it.

This process ensures non-repudiation: Alice cannot deny sending the message.

For combined security, Alice can:

  1. Sign the message with her private key (authentication).
  2. Encrypt it with Bob’s public key (confidentiality).

Bob reverses the steps: decrypt first, then verify signature.

Frequently Asked Questions

Q: What makes RSA different from symmetric encryption?
A: RSA uses two mathematically linked keys—one public, one private—while symmetric encryption uses a single shared secret key for both operations.

Q: Is RSA still safe to use today?
A: Yes, when implemented correctly with sufficiently large keys (2048+ bits). However, it should be combined with other protections and eventually replaced by quantum-resistant algorithms.

Q: Can RSA be broken by brute force?
A: Not practically. Factoring a 2048-bit number would take classical computers thousands of years with current technology.

Q: How does padding improve RSA security?
A: Padding adds randomness to prevent patterns and thwart attacks like chosen-ciphertext exploits.

Q: What role does Euler’s Theorem play in RSA?
A: It ensures that raising a number to ed modulo N returns the original number, enabling correct decryption.

Q: Why is prime number generation critical in RSA?
A: Weak or predictable primes make factoring easier. High-quality randomness is essential for generating secure keys.

👉 Learn how cryptographic principles underpin blockchain and digital asset security.