6. RSA Hash

Course Information

• CS 4575/5575: Information Assurance and Security

• CS 4575/5575: Cryptography and Network Security

• Spring 2022

• Sources:

  • Introduction to Computer Security, Matt Bishop, Addison Wesley, 2003

  • Security in Computing, Pfleeger and Pfleeger, Prentice Hall, 2003

  • Cryptography & Network Security, B. Forouzan, McGraw Hill, 2007

Public Key Cryptography

• Definition: Asymmetric key cryptography proposed by Diffie and Hellman, 1976.

• Key Types:

  • Private Key: Known only to the individual.

  • Public Key: Available to anyone.

Symmetric vs. Asymmetric Cryptography

• Symmetric: Same key locks and unlocks.

• Asymmetric: One key locks, the other unlocks.

Key Characteristics of Public and Private Keys

• Keys are mathematically related and generated together.

• If a message is encrypted by one key, it can only be decrypted by the associated key.

• Each user has a pair of keys: Public Key (shared) and Private Key (kept secret).

Goals of Public Key Cryptography

• Confidentiality: Ensures that only intended parties can read the message.

• Data Authentication: Validates the integrity of the message.

• Origin Authentication and Non-repudiation: Confirms the sender's identity and prevents denial of sending.

Requirements for Key Security

1. Ease of Computation: Must be easy to encipher/decipher with the right key.

2. Infeasibility of Deriving Private Key: Must be computationally difficult to derive the private key from the public key or using chosen plaintext.

RSA (Rivest, Shamir, Adleman, 1977)

• Utilizes exponentiation functions based on arithmetic.

• One-Way Function Properties:

  • Given x, it is easy to compute y, but given y, it is hard to compute x.

  • Trapdoor Function: Something can make it easy to compute if you know a secret.

Prime Numbers and Totient Function

• Prime numbers: Have no common factors with any other numbers.

• Totient Function (φ(n)): Counts numbers coprime to a larger integer n.

  • Example: φ(10) = 4; φ(21) = 12.

RSA Algorithm Steps

1. Choose two large prime numbers (p, q).

2. Compute n = pq.

3. Compute φ(n) = (p-1)(q-1).

4. Choose e such that 1 < e < φ(n), and e is coprime to φ(n).

5. Compute d such that ed mod φ(n) = 1.

6. Public Key: (e, n); Private Key: d.

7. Encipher: c = m^e mod n; Decipher: m = c^d mod n.

Security with RSA

• Recovery of plaintext from intercepted ciphertext without the private key is infeasible.

• Attacks rely on the difficulty of reversing exponentiation or factoring large numbers.

Confidentiality and Integrity in RSA

• Confidentiality: Encipher using recipient's public key and decipher with recipient's private key.

• Integrity: Encipher using sender's private key and decipher with sender's public key for authentication.

Security Services Offered by RSA

• Confidentiality: Ensures data is unreadable without the private key.

• Data Integrity: Changes in enciphered text can be detected.

• Origin Authentication: Validates the true sender of the message.

Attacks Against RSA

• Susceptible to inference attacks much like substitution ciphers.

• Use of padding can help mitigate certain statistical attacks.

Use of RSA

• Commonly used in e-commerce; relies on long keys for security.

Comparison of Symmetric and Asymmetric Cryptography

• Symmetric: Single secret key; easier and faster but harder to distribute; lacks non-repudiation.

• Asymmetric: Two keys (one secret, one public); more complex but allows for non-repudiation.

Checksums and Hashes

• Checksums: Simple representations to detect data errors, e.g., using parity bits.

• Cryptographic Hash: Generates a set of k bits from a set of n bits to ensure integrity.

  • Key Properties:

    • Impossible to derive the original message from the digest.

    • Fixed-length regardless of message size.

    • Any change in the message generates a different hash.

Applications of Hash Function

• Used for integrity checks on messages and documents, system states, and identifier generation.