Asymmetric encryption (RSA) in Computer Networks - Full Explanation

Introduction

Imagine you want to send a secret message to a friend without anyone else reading it, but you can't meet to share a secret key first. This problem needs a way to lock and unlock messages using different keys so that only the right person can read them.

Explanation

Public and Private Keys

Asymmetric encryption uses two keys: one public and one private. The public key is shared openly and used to lock (encrypt) messages. The private key is kept secret and used to unlock (decrypt) messages. This way, anyone can send a secret message using the public key, but only the owner of the private key can read it.

Two different keys work together: one to lock messages and one to unlock them.

How RSA Works

RSA creates the public and private keys using two large prime numbers. These numbers are multiplied to form a key that is easy to share but hard to reverse without the private key. The security depends on how difficult it is to factor this large number back into primes.

RSA’s security relies on the difficulty of factoring large numbers made from two primes.

Encryption and Decryption Process

When someone wants to send a secret message, they use the receiver’s public key to encrypt it. The encrypted message looks like random data to anyone else. The receiver then uses their private key to decrypt and read the original message.

Encryption uses the public key, and decryption uses the private key to keep messages secure.

Digital Signatures

RSA can also prove who sent a message by reversing the process. The sender encrypts a message or its summary with their private key. Anyone with the sender’s public key can decrypt it to verify the sender’s identity and that the message was not changed.

RSA allows verifying message origin and integrity using digital signatures.

Real World Analogy

Imagine a locked mailbox where anyone can drop letters inside using a slot (public key), but only the mailbox owner has the key to open it and read the letters (private key). For sending proof of identity, the owner can put a special stamp only they can make, which others can check to confirm it’s genuine.

Public and Private Keys → Mailbox slot for dropping letters (public key) and mailbox key for opening it (private key)

How RSA Works → The mailbox’s unique lock made from a complex combination that’s easy to use but hard to copy

Encryption and Decryption Process → Dropping letters through the slot (encrypting) and opening mailbox to read letters (decrypting)

Digital Signatures → Special stamp on letters proving they came from the mailbox owner

Diagram

Diagram

┌───────────────┐        ┌───────────────┐
│ Sender        │        │ Receiver      │
│               │        │               │
│ Message       │        │               │
│               │        │               │
└──────┬────────┘        └──────┬────────┘
       │ Encrypt with Public Key      │
       │────────────────────────────>│
       │                             │
       │ Encrypted Message           │
       │                             │
       │ Decrypt with Private Key    │
       │<────────────────────────────│
       │                             │
       │ Original Message            │
       │                             │
       └─────────────────────────────┘

This diagram shows how a sender encrypts a message with the receiver’s public key and the receiver decrypts it with their private key.

Key Facts

Asymmetric Encryption → Encryption method using two different keys: public for encrypting and private for decrypting.

Public Key → A key shared openly to encrypt messages.

Private Key → A secret key used to decrypt messages encrypted with the matching public key.

RSA → A widely used asymmetric encryption algorithm based on large prime number multiplication.

Digital Signature → A way to prove message origin and integrity by encrypting with a private key.

Code Example

Computer Networks

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

# Generate RSA keys
key = RSA.generate(2048)
private_key = key.export_key()
public_key = key.publickey().export_key()

# Encrypt message with public key
encryptor = PKCS1_OAEP.new(RSA.import_key(public_key))
message = b'Hello, RSA!'
ciphertext = encryptor.encrypt(message)

# Decrypt message with private key
decryptor = PKCS1_OAEP.new(RSA.import_key(private_key))
plaintext = decryptor.decrypt(ciphertext)
print(plaintext.decode())

Common Confusions

Believing the public key can decrypt messages.

Believing the public key can decrypt messages. The public key only encrypts messages; only the private key can decrypt them.

Thinking RSA encrypts data faster than symmetric encryption.

Thinking RSA encrypts data faster than symmetric encryption. RSA is slower and usually used to securely exchange symmetric keys, which then encrypt data faster.

Summary

Asymmetric encryption uses two keys: a public key to encrypt and a private key to decrypt messages securely.

RSA relies on the difficulty of factoring large numbers made from two prime numbers to keep keys safe.

RSA also supports digital signatures to verify who sent a message and ensure it was not changed.

Practice

1. What is the main purpose of the private key in RSA asymmetric encryption?

easy

A. To share with anyone for secure communication

B. To encrypt messages for everyone to read

C. To decrypt messages encrypted with the public key

D. To generate the public key

Solution

1. Step 1: Understand RSA key roles

   In RSA, the public key encrypts data, and the private key decrypts it.

2. Step 2: Identify private key function

   The private key is kept secret and used to decrypt messages encrypted by the public key.

3. Final Answer:

   To decrypt messages encrypted with the public key -> Option C

4. Quick Check:

   Private key = decrypt [OK]

Hint: Private key always decrypts what public key encrypts [OK]

Common Mistakes:

• Confusing encryption and decryption roles
• Thinking private key is shared publicly
• Assuming private key encrypts messages

2. Which of the following is the correct way to describe RSA keys?

easy

A. Both keys are identical and interchangeable

B. Public key encrypts, private key decrypts

C. Private key is public, public key is private

D. Keys are randomly generated but not related

Solution

1. Step 1: Recall RSA key relationship

   RSA uses a pair of keys where the public key encrypts and the private key decrypts.

2. Step 2: Evaluate options

   Only Public key encrypts, private key decrypts correctly states the roles of the keys in RSA encryption.

3. Final Answer:

   Public key encrypts, private key decrypts -> Option B

4. Quick Check:

   Public encrypt, private decrypt [OK]

Hint: Public encrypts, private decrypts in RSA [OK]

Common Mistakes:

• Thinking keys are the same
• Mixing up public and private key roles
• Believing keys are unrelated

3. Consider this simplified RSA scenario:
Public key: (e=3, n=33)
Private key: (d=7, n=33)
Message m = 4
What is the encrypted message c using c = m^e mod n?

medium

A. 31

B. 12

C. 16

D. 4

Solution

1. Step 1: Calculate encryption formula

   Compute c = 4^3 mod 33 = 64 mod 33.

2. Step 2: Find remainder

   64 divided by 33 leaves remainder 64 - 33*1 = 31, so 64 mod 33 = 31.

3. Step 3: Re-check calculation

   Actually, 4^3 = 64, 64 mod 33 = 31, so c = 31.

4. Final Answer:

   31 -> Option A

5. Quick Check:

   4^3 mod 33 = 31 [OK]

Hint: Calculate power then mod for encryption [OK]

Common Mistakes:

• Forgetting to apply modulo
• Calculating power incorrectly
• Mixing up encryption and decryption formulas

4. In an RSA implementation, a developer wrote:
c = (m ** d) % n
to encrypt a message. Why is this incorrect?

medium

A. Because d is the private key exponent used for decryption, not encryption

B. Because m should be raised to e for decryption

C. Because modulo n should not be used in RSA

D. Because exponentiation operator ** is invalid in Python

Solution

1. Step 1: Understand RSA key usage

   Encryption uses the public exponent e, decryption uses private exponent d.

2. Step 2: Identify error in code

   The code uses d to encrypt, which is incorrect; it should use e.

3. Final Answer:

   Because d is the private key exponent used for decryption, not encryption -> Option A

4. Quick Check:

   Encrypt with e, decrypt with d [OK]

Hint: Encrypt with e, decrypt with d [OK]

Common Mistakes:

• Using private key exponent for encryption
• Confusing exponentiation operator validity
• Ignoring modulo operation necessity

5. A company wants to use RSA to securely send a 128-bit message. Which of the following is the best practice to ensure security and efficiency?

hard

A. Encrypt the entire 128-bit message directly with RSA public key

B. Share the private key with the recipient to speed up encryption

C. Use the private key to encrypt the message and public key to decrypt

D. Use RSA to encrypt a symmetric key, then use that key to encrypt the message

Solution

1. Step 1: Understand RSA limitations

   RSA is slow and inefficient for large data encryption like 128-bit messages directly.

2. Step 2: Identify best practice

   Common practice is to encrypt a symmetric key with RSA, then use that key for fast message encryption.

3. Final Answer:

   Use RSA to encrypt a symmetric key, then use that key to encrypt the message -> Option D

4. Quick Check:

   Hybrid encryption = RSA + symmetric key [OK]

Hint: Encrypt keys with RSA, data with symmetric cipher [OK]

Common Mistakes:

• Encrypting large data directly with RSA
• Sharing private key publicly
• Reversing encryption/decryption key roles