CS 2413 Encryption

Introduction to Public Key Encryption

  • Discussion on the confusion regarding public key encryption.

  • Summary of the last lecture covering the basics of encryption (symmetric vs. public key).

Key Concepts

Symmetric vs. Public Key Encryption

  • Symmetric encryption uses one key for both encryption and decryption.

  • Public key encryption uses two keys:

    • Public Key: Used for encrypting text.

    • Private Key: Used for decrypting text.

  • Example: A sends an encrypted message using B's public key, and B decrypts it using their private key.

Functions of Public Key Encryption

  • Confidentiality: Only the holder of the private key can decrypt the text.

  • Authentication: Signing a message with one's private key allows the recipient to verify its source using the public key.

Scenarios and Requirements for Public Key Cryptography

Requirements

  • It should be easy for a user to generate a public/private key pair.

  • The sender (User A) must easily encrypt a message using the recipient's (User B) public key.

  • The receiver (User B) must be able to easily decrypt this message using their private key.

Additional Security Requirements

  1. Invisibility of Private Key: Private key must not be derivable from the public key.

  2. Independence: No direct relationship that allows the derivation of the private key from the public key.

  3. Impotent to Factor Without Private Key: An attacker should not be able to retrieve the plaintext even if they have both the ciphertext and public key.

Use Case of Public Key Cryptography

RSA Encryption Algorithm

  • Basic steps involved in RSA algorithm:

    1. Choose two prime numbers, $p$ and $q$, where $q > p$.

    2. Compute $n = p imes q$; $n$ is part of both the public and private keys.

    3. Compute $ ext{phi}(n) = (p-1)(q-1)$, which is used in key generation.

    4. Choose an integer $e$ (public exponent) such that $1 < e < ext{phi}(n)$ and $ ext{gcd}(e, ext{phi}(n)) = 1$.

    5. Compute $d$ (private exponent) such that $d imes e ext{ mod } ext{phi}(n) = 1$.

Example Calculation

  • Given numbers: $p = 3$ and $q = 11$.

    • Compute $n = 3 imes 11 = 33$.

    • Compute $ ext{phi}(n) = (3-1)(11-1) = 20$.

    • Choose $e = 7$, $ ext{gcd}(7, 20) = 1$.

    • Find $d$: 3 (since $3 imes 7 = 21 ext{ mod } 20 = 1$).

Encryption and Decryption Steps

  • To encrypt a message $m$: cext(ciphertext)extiscextmodnc ext{ (ciphertext)} ext{ is } c ext{ mod } n where cextiscomputedasmeextmodnc ext{ is computed as } m^e ext{ mod } n.

  • To decrypt, use mext(plaintext)=cdextmodnm ext{ (plaintext)} = c^d ext{ mod } n.

Alternative Public Key Cryptography Techniques

Diffie-Hellman Key Exchange

  • A method for two parties (A and B) to share a secret key without transmitting it over the network.

  • Each user chooses a secret number and computes an intermediary value to exchange with the other party.

  • The final computed keys by both users are the same due to mathematical properties.

Digital Signatures

  • Definition and purpose of digital signatures.

  • Created via cryptographic hashing and encrypting the hash with a private key, allowing origin verification and authentication.

  • Types of digital signature algorithms: RSA, DSS, and elliptic curve signature algorithms.

Security Concerns in Public Key Cryptography

Man-in-the-Middle Attacks

  • Issues related to public key sharing - a malicious user could impersonate someone else and issue fraudulent public keys.

  • Solution: Use Certificate Authorities (CAs) to provide authentication.

Digital Certificates

  • Exposure of public keys through digital certificates signed by reliable entities (CAs).

  • Process to create a signed certificate for a user to ensure authenticity.

Other Techniques and Topics

Digital Envelope Technique

  • A method used to securely exchange symmetric keys without transmitting them over the network.

Properties of Random Numbers in Cryptography

  1. Uniform Distribution: Each number should have an equal chance of appearing.

  2. Independence: No number in a sequence should affect the probability of occurrence of another number.

  3. Pseudo-Random Generation: Algorithms can generate sequences that appear random but are generated by deterministic processes.

Summary of Lecture Concepts

  • Importance of using multiple encryption techniques, including stream ciphers and block ciphers like ECB (Electronic Code Book).

  • Not all encryption methods are advisable for every application due to potential vulnerabilities (e.g., predictable encryption outputs).

  • Future lectures to elaborate on the types and applications of these theories in real-world scenarios such as file transfers and secure communications.