Cryptography

Symmetric-Key Distribution

Symmetric-key cryptography is efficient for encrypting large messages but requires a shared secret key between the communicating parties. Distributing these keys securely is a challenge.

Two Possible Ways for Key Distribution:

1. Key-Distribution Center (KDC):

• A trusted third party that helps distribute symmetric keys to parties wishing to communicate. Each party shares a separate secret key with the KDC, which then uses these keys to securely distribute session keys.

1. Session Keys:

• Temporary keys used for the duration of a session. They provide an extra layer of security, ensuring that even if a session key is compromised, it doesn't affect other sessions.

Symmetric-Key Agreement:

• Alice and Bob can create a session key between themselves without using a KDC. This method is known as symmetric-key agreement.

Secure Techniques for Key Agreement:

1. Diffie-Hellman Key Exchange:

• Enables two users to securely exchange a key for subsequent encryption of messages. Its security relies on the difficulty of computing discrete logarithms.

• Steps involved:

1. Alice and Bob agree on a large prime number and a base (both can be public).

2. Alice chooses a secret number and computes a value based on the base and prime.

3. Bob chooses his own secret number and computes a similar value.

4. They exchange these computed values.

5. Both compute the shared secret key using their own secret number and the received value from the other party.

6. Station-to-Station Key Agreement:

• A protocol that combines Diffie-Hellman key exchange with digital signatures to provide mutual authentication along with key agreement.

Both methods ensure that the key exchanged between Alice and Bob remains secure and can be used for encrypting messages in subsequent communications.

Primitive Root

A number aaa is a primitive root modulo ppp (where ppp is a prime) if the powers of aaa modulo ppp generate all integers from 1 to p−1p-1p−1 in some permutation.

Example:

• Let p=7p = 7p=7, a primitive root is 333 because: 31mod  7=33^1 \mod 7 = 331mod7=3 32mod  7=9mod  7=23^2 \mod 7 = 9 \mod 7 = 232mod7=9mod7=2 33mod  7=27mod  7=63^3 \mod 7 = 27 \mod 7 = 633mod7=27mod7=6 34mod  7=81mod  7=43^4 \mod 7 = 81 \mod 7 = 434mod7=81mod7=4 35mod  7=243mod  7=53^5 \mod 7 = 243 \mod 7 = 535mod7=243mod7=5 36mod  7=729mod  7=13^6 \mod 7 = 729 \mod 7 = 136mod7=729mod7=1

The sequence (3, 2, 6, 4, 5, 1) covers all integers from 1 to 6, making 3 a primitive root of 7.

Diffie-Hellman Key Exchange

The Diffie-Hellman key exchange allows two parties to establish a shared secret key over an insecure channel. The algorithm's security relies on the difficulty of computing discrete logarithms.

Steps:

1. Publicly agree on a prime number ppp and a base ggg (primitive root modulo ppp).

2. Alice selects a private key xxx and computes her public value R1R_1R1​:

• R1=gxmod  pR_1 = g^x \mod pR1​=gxmodp

1. Bob selects a private key yyy and computes his public value R2R_2R2​:

• R2=gymod  pR_2 = g^y \mod pR2​=gymodp

1. Alice and Bob exchange their public values R1R_1R1​ and R2R_2R2​.

2. Alice computes the shared secret key KKK using Bob's public value R2R_2R2​:

• K=R2xmod  pK = R_2^x \mod pK=R2x​modp

1. Bob computes the shared secret key KKK using Alice's public value R1R_1R1​:

• K=R1ymod  pK = R_1^y \mod pK=R1y​modp

Both Alice and Bob now share the same secret key KKK.

Example with Small Numbers:

• Public values: p=23p = 23p=23, g=9g = 9g=9

1. Alice selects private key x=4x = 4x=4 and computes her public value:

• R1=94mod  23=6561mod  23=6R_1 = 9^4 \mod 23 = 6561 \mod 23 = 6R1​=94mod23=6561mod23=6

1. Bob selects private key y=3y = 3y=3 and computes his public value:

• R2=93mod  23=729mod  23=16R_2 = 9^3 \mod 23 = 729 \mod 23 = 16R2​=93mod23=729mod23=16

1. Exchange public values: Alice receives R2=16R_2 = 16R2​=16, Bob receives R1=6R_1 = 6R1​=6

2. Alice computes the shared secret key:

• K=R2xmod  p=164mod  23=65536mod  23=9K = R_2^x \mod p = 16^4 \mod 23 = 65536 \mod 23 = 9K=R2x​modp=164mod23=65536mod23=9

1. Bob computes the shared secret key:

• K=R1ymod  p=63mod  23=216mod  23=9K = R_1^y \mod p = 6^3 \mod 23 = 216 \mod 23 = 9K=R1y​modp=63mod23=216mod23=9

Both Alice and Bob now share the secret key K=9K = 9K=9.

Man-in-the-Middle Attack on Diffie-Hellman Key Exchange

A man-in-the-middle (MitM) attack occurs when an adversary intercepts and possibly alters the communication between two parties. Here’s an example using Diffie-Hellman key exchange with Alice, Bob, and an attacker named Darth.

1. Darth generates two sets of private keys: XD1X_{D1}XD1​ and XD2X_{D2}XD2​, and corresponding public keys YD1Y_{D1}YD1​ and YD2Y_{D2}YD2​.

2. Alice transmits her public key YAY_AYA​ to Bob.

3. Darth intercepts Alice's public key YAY_AYA​ and sends his own public key YD1Y_{D1}YD1​ to Bob. Darth also computes K2=(YA)XD2mod  qK_2 = (Y_A)^{X_{D2}} \mod qK2​=(YA​)XD2​modq.

4. Bob receives YD1Y_{D1}YD1​ and calculates K1=(YD1)XBmod  qK_1 = (Y_{D1})^{X_B} \mod qK1​=(YD1​)XB​modq.

5. Bob transmits his public key YBY_BYB​ to Alice.

6. Darth intercepts Bob's public key YBY_BYB​ and sends his own public key YD2Y_{D2}YD2​ to Alice. Darth computes K1=(YB)XD1mod  qK_1 = (Y_B)^{X_{D1}} \mod qK1​=(YB​)XD1​modq.

7. Alice receives YD2Y_{D2}YD2​ and calculates K2=(YD2)XAmod  qK_2 = (Y_{D2})^{X_A} \mod qK2​=(YD2​)XA​modq.

Now, Darth has established two different shared keys, K1K_1K1​ with Bob and K2K_2K2​ with Alice, effectively allowing him to decrypt and re-encrypt all messages between Alice and Bob, remaining undetected.

RSA Cryptosystem

RSA is a widely-used public-key encryption algorithm named after its inventors, Rivest, Shamir, and Adleman.

Key Setup

1. Select two large prime numbers ppp and qqq.

2. Compute nnn as n=p×qn = p \times qn=p×q.

3. Compute ϕ(n)\phi(n)ϕ(n) as (p−1)×(q−1)(p-1) \times (q-1)(p−1)×(q−1).

4. Select an encryption key eee where 1<e<ϕ(n)1 < e < \phi(n)1<e<ϕ(n) and gcd(e,ϕ(n))=1\text{gcd}(e, \phi(n)) = 1gcd(e,ϕ(n))=1.

5. Determine the decryption key ddd such that e×d≡1mod  ϕ(n)e \times d \equiv 1 \mod \phi(n)e×d≡1modϕ(n).

6. Publish the public key {e,n}\{e, n\}{e,n} and keep the private key {d,n}\{d, n\}{d,n} secret.

Encryption

1. Obtain the recipient's public key {e,n}\{e, n\}{e,n}.

2. Convert the message MMM to an integer 0≤M<n0 \le M < n0≤M<n.

3. Compute the ciphertext C=Memod  nC = M^e \mod nC=Memodn.

Decryption

1. Use the private key {d,n}\{d, n\}{d,n}.

2. Compute the original message M=Cdmod  nM = C^d \mod nM=Cdmodn.

Why RSA Works

• RSA relies on the difficulty of factoring large numbers.

• Euler's Theorem states that for aaa and nnn where gcd(a,n)=1\text{gcd}(a, n) = 1gcd(a,n)=1: aϕ(n)≡1mod  na^{\phi(n)} \equiv 1 \mod naϕ(n)≡1modn

• In RSA, n=p×qn = p \times qn=p×q and ϕ(n)=(p−1)×(q−1)\phi(n) = (p-1) \times (q-1)ϕ(n)=(p−1)×(q−1).

• The encryption and decryption keys eee and ddd are chosen such that: e×d≡1+k×ϕ(n)e \times d \equiv 1 + k \times \phi(n)e×d≡1+k×ϕ(n) This ensures: Cd≡(Me)d≡Me×d≡Mmod  nC^d \equiv (M^e)^d \equiv M^{e \times d} \equiv M \mod nCd≡(Me)d≡Me×d≡Mmodn

Example

1. Select primes: p=7p = 7p=7, q=19q = 19q=19.

2. Compute nnn: n=p×q=7×19=133n = p \times q = 7 \times 19 = 133n=p×q=7×19=133.

3. Compute ϕ(n)\phi(n)ϕ(n): ϕ(n)=(7−1)×(19−1)=108\phi(n) = (7-1) \times (19-1) = 108ϕ(n)=(7−1)×(19−1)=108.

4. Select eee: e=5e = 5e=5 (since gcd(5,108)=1\text{gcd}(5, 108) = 1gcd(5,108)=1).

5. Determine ddd: d=65d = 65d=65 (since 5×65≡1mod  1085 \times 65 \equiv 1 \mod 1085×65≡1mod108).

6. Public key: {e,n}={5,133}\{e, n\} = \{5, 133\}{e,n}={5,133}.

7. Private key: {d,n}={65,133}\{d, n\} = \{65, 133\}{d,n}={65,133}.

Encryption

1. Message M=6M = 6M=6.

2. Ciphertext CCC: C=65mod  133=7776mod  133=62C = 6^5 \mod 133 = 7776 \mod 133 = 62C=65mod133=7776mod133=62.

Decryption

1. Ciphertext C=62C = 62C=62.

2. Original message MMM: M=6265mod  133=6M = 62^{65} \mod 133 = 6M=6265mod133=6.
   

Message Authentication

Message authentication is a procedure used to verify that received messages come from the genuine source and have not been altered. It ensures that the data received are exactly as sent, containing no modifications, insertions, deletions, or replays.

Message Authentication Requirements

1. Disclosure: Prevent unauthorized parties from gaining access to the content of the message.

2. Traffic Analysis: Protect against analysis of the pattern of traffic to derive useful information.

3. Masquerade: Ensure that the sender's identity cannot be forged.

4. Content Modification: Ensure the content of the message cannot be altered.

5. Sequence Modification: Maintain the correct order of messages.

6. Timing Modification: Ensure messages are timely and not delayed or replayed.

7. Source Repudiation: Prevent the sender from denying sending the message.

8. Destination Repudiation: Prevent the receiver from denying receipt of the message.

Requirements for Message Authentication

• Confidentiality: Ensuring the message content is kept secret from unauthorized parties.

• Authentication: Verifying the identity of the sender and ensuring the message has not been tampered with.

• Digital Signature: Providing a way to ensure non-repudiation, authenticity, and integrity of a message.

Motivation for Hash Algorithms

• Intuition: Non-cryptographic checksums are easy to forge; hence, cryptographic hash functions are needed to ensure message integrity.

• Goal: Design a code where the original message cannot be inferred based on its checksum, and any changes to the message will change the hash value.

Hash Function

A hash function takes a variable-length input message and produces a fixed-length output called the hash value or message digest. This digest acts as a digital fingerprint of the original document, ensuring data integrity.

Hashing vs. Encryption

• Hashing: One-way process, no key required, used for integrity checks.

• Encryption: Two-way process, key required, used for confidentiality.

Hash Function Applications

• Fingerprint: Used for file integrity verification and public key fingerprinting.

• Password Storage: Store the hash of the password instead of the actual password.

• HMAC (Hash-based Message Authentication Code): Used for both message integrity and confidentiality.

• Digital Signatures: Ensure non-repudiation by encrypting the hash with a private key.

Requirements for Hash Functions

1. Applicability: Can be applied to any sized message.

2. Fixed Output: Produces a fixed-length output.

3. Efficiency: Easy to compute.

4. Preimage Resistance: Infeasible to find any message with a given hash value.

5. Second Preimage Resistance: Infeasible to find another message with the same hash value.

6. Collision Resistance: Infeasible to find two different messages with the same hash value.

Hash Function Properties

• Arbitrary-Length to Fixed-Length Digest: Converts any length of data to a fixed-length hash.

• Preimage Resistant: Difficult to find any message that corresponds to a given hash.

• Second Preimage Resistant: Difficult to find another message that hashes to the same value as a given message.

• Collision Resistant: Difficult to find any two different messages that hash to the same value.

Hash Function Attacks

1. Preimage Attack: Given a hash value y=h(M)y = h(M)y=h(M), find any message M′M'M′ such that y=h(M′)y = h(M')y=h(M′).

2. Second Preimage Attack: Given a message MMM and its hash h(M)h(M)h(M), find another message M′≠MM' \neq MM′=M such that h(M)=h(M′)h(M) = h(M')h(M)=h(M′).

3. Collision Attack: Find two different messages MMM and M′M'M′ such that h(M)=h(M′)h(M) = h(M')h(M)=h(M′).

Simple Hash Function

• Bit-by-Bit XOR: One of the simplest hash functions is the bit-by-bit exclusive-OR (XOR) of every block of the input.

Hash Functions Family

• MD (Message Digest): Designed by Ron Rivest. Examples include MD2, MD4, MD5.

• SHA (Secure Hash Algorithm): Designed by NIST. Examples include SHA-0, SHA-1, SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512), and SHA-3.

• RIPEMD (Race Integrity Primitive Evaluation Message Digest): Developed by Katholieke University Leuven Team. Examples include RIPEMD-128, RIPEMD-160, RIPEMD-256, and RIPEMD-320.

Distribution of Public Keys

To securely distribute public keys, several methods can be employed:

1. Public Announcement

2. Publicly Available Directory

3. Public-Key Authority

4. Public-Key Certificates

1. Public Announcement

Process:

• Public keys are broadcasted or sent to participants.

Issues:

• Vulnerable to forgery. An attacker can pretend to be a user and distribute a forged public key.

• Until the forgery is discovered, the attacker can intercept and read all encrypted messages meant for the user.

2. Publicly Available Directory

Process:

1. An authority maintains a directory containing a (name, public key) entry for each participant.

2. Each participant registers their public key with the directory authority.

3. Participants can update their public key as needed.

4. Secure, authenticated communication from the authority to the participant is essential for directory access.

Advantages:

• Reduces the risk of forgery compared to public announcements.

• Ensures that the directory can be accessed electronically in a secure manner.

3. Public-Key Certificates

Process:

• Certificates contain a participant’s public key and are signed by a Certificate Authority (CA).

• Participants can read and verify certificates to determine the owner and authenticity of the public key.

Advantages:

• Certificates are signed by a trusted CA, preventing forgery.

• Participants can verify the currency and validity of certificates.

Steps:

1. Participants apply to the CA, supplying a public key and requesting a certificate.

2. The CA issues a certificate in the form: CA's signature (PRauth, [T || IDa || PUa]).

3. Participants pass the certificate to others, who verify it using the CA’s public key.

X.509 Certificates

X.509 Format:

1. Version: Indicates the certificate format version.

2. Serial Number: Unique within the issuing CA.

3. Signature Algorithm Identifier: The algorithm used to sign the certificate.

4. Issuer Name: The CA’s X.500 name.

5. Period of Validity: Start and end dates for certificate validity.

6. Subject Name: The name of the certificate owner.

7. Subject’s Public-Key Information: The public key and associated algorithm.

8. Issuer Unique Identifier: Optional, for uniquely identifying the issuing CA.

9. Subject Unique Identifier: Optional, for uniquely identifying the subject.

10. Extensions: Additional fields for extended functionality.

Public Key Infrastructure (PKI)

Components:

• End Entity: End users, devices, or any entity identified in the subject field of a certificate.

• Certification Authority (CA): Issues certificates and Certificate Revocation Lists (CRLs).

• Registration Authority (RA): Performs administrative functions on behalf of the CA.

• CRL Issuer: Optional, delegated by the CA to publish CRLs.

• Repository: Stores certificates and CRLs for retrieval by end entities.

Objective:

• To enable secure, convenient, and efficient acquisition and management of public keys.

• Ensures that the PKI components work together to maintain a secure cryptographic environment.

By implementing these methods, the integrity, authenticity, and security of public keys can be maintained, thereby enabling secure communication and authentication in various digital environments.