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.

هذا الاختبار يستعرض أساسيات التشفير، بما في ذلك التشفير بالمفتاح الخاص والمفتاح العام. ستتعلم الفرق بين النظامين وأهم خصائص كل منهما. استعد لاختبار معلوماتك حول كيفية حماية المعلومات باستخدام التشفير.