Cryptography Basics: Key Types

Private-Key Cryptography

• Private-key cryptography uses a single key shared by both sender and receiver.
• If this key is disclosed, communications are compromised.
• It's symmetric, meaning parties have equal roles.
• It doesn't protect the sender from the receiver forging a message and claiming it was sent by the sender.

Public-Key Cryptography

• This is a significant advancement in cryptography, using a public and private key pair.
• The system is asymmetric, meaning different parties have different key roles (public & private).
• It uses clever applications of number theory.
• It complements rather than replaces private-key cryptography.

Public-Key Cryptography (continued)

• Public-key/two-key/asymmetric cryptography uses two keys:
  • A public key that anyone can use to encrypt messages and verify signatures.
  • A private key known only to the recipient, used to decrypt messages and sign/create signatures.
• Asymmetric because those who encrypt can't decrypt, and vice versa.

RSA Encryption Algorithm

• RSA is a type of public-key encryption algorithm.
• Also called asymmetric algorithm.
• Sender and receiver use different keys for encryption and decryption.
• Each sender has a pair of keys (public and private).

RSA Encryption Algorithm (continued)

• The public key is used for encryption.
• The private key is used for decryption.
• Decryption cannot be done using a public key, because the private key can't be derived from the public key.
• Public keys are publicly known, while private keys are kept secret by their owners.
• Anyone can send a message using the recipient's public key; But only the recipient can decrypt it using their private key.

RSA Encryption Algorithm (continued 2)

• Data is encrypted by the sender using the recipient's public key, then decrypted using the recipient's private key.
• Recipients reply by encrypting using the sender's public key.
• Senders decrypt received messages using their own private keys.

RSA Encryption Algorithm (continued 3)

• Shows how RSA encryption and decryption process works.
  • Plaintext is input.
  • Encryption algorithm (e.g., RSA) is applied resulting ciphertext.
  • Ciphertext is transmitted.
  • Decryption algorithm is applied to recover plaintext.

Public-Key Characteristics

• Public-key algorithms rely on two keys:
  • Computationally infeasible to derive a decryption key from an encryption key.
  • Computationally easy to encrypt/decrypt messages using the correct key.
  • Either key (public or private) can be used for encryption, the other then used for decryption.

RSA Algorithm Key Generation

• Select two large prime numbers (p and q).
• Calculate n = p * q (this is the modulus for encryption and decryption).
• Choose an integer e which is less than φ(n), such that gcd(e, φ(n)) = 1 (this is the public key).
• Find an integer d such that (e * d) mod φ(n) = 1 where 1 < d < φ(n)) (this is the private key).

RSA Algorithm Examples

• Shows how to obtain the public and private keys in practice using example numbers:
  • p = 7, q = 11 -> n = 77
  • ϕ(n) = 60
  • Choose e =7
  • Find d = 43 such that (7 * 43) mod 60 =1
• This explains the steps to find different values, which are then used in formulas for encryption and decryption.

RSA Use

• To encrypt a message (M):
  • Obtain the recipient's public key (e, n).
  • Compute C = M^e mod n (where 0 ≤ M < n).
• To decrypt the ciphertext (C):
  • Use the recipient's private key (d, n).
  • Compute M = C^d mod n.

Exponentiation

• The algorithm for exponentiation (e.g., 7⁵) can use the Square and Multiply Algorithm.
• This algorithm is fast and efficient.
• It works by repeatedly squaring the base and multiplying when needed to compute the result

Efficient Encryption

• Encryption uses exponentiation for efficiency.
• Small values of e will speed up encryption.
• A common choice is e=65537.
• However if e is too small, attacks can exploit this, for example, using the Chinese remainder theorem and different moduli.
• For any fixed e, ensure that gcd(e, Ø(n)) = 1.

Efficient Decryption

• Decryption uses exponentiation to power d, which is often large.
• The Chinese Remainder Theorem can speed up decryption by calculating separately modulo p and q, then combining the results.
• This technique is significantly faster than direct computation.
• Requires access to the factors p and q of the modulus n.

RSA Key Generation

• RSA key generation involves selecting two large prime numbers (p and q) and calculating the system modulus n = p * q.
• The values of p and q must be large enough to resist factoring attacks.
• Exponents e and d are calculated, the inverse of each other.
• The public key is {e, n}, and the private key is {d,n}.

RSA Security

• Potential RSA attacks include brute-force key search (infeasible), mathematical attacks (based on factoring the modulus), timing attacks, and chosen-ciphertext attacks.

Factoring Problem

• Factoring the modulus n into its primes p and q is crucial to compromising RSA.
• There are theoretical and practical limitations, as factoring is computationally difficult.
• Improvements have been slow.

Timing Attacks

• Exploiting the varying execution times of operations (e.g., multiplying small versus large numbers) to infer the size of operands and eventually recover the private key.
• Countermeasures including constant exponentiation time and random delays are employed.

Chosen Ciphertext Attacks

• Attackers can choose ciphertexts and obtain decrypted plaintexts from the system.
• This can be used to gather information needed to break RSA.
• Countermeasures include random padding of plaintext and using Optimal Asymmetric Encryption Padding (OASP).

Summary

• Principles of public-key cryptography.
• RSA algorithm implementation and security.