Public Key Cryptology

Asymmetric Cryptography

  • Also known as public key cryptography.

  • Utilizes different keys for encryption and decryption; no shared secret is needed between sender and receiver.

  • One key is designated for encrypting the message (public key) and the other for decrypting (private key).

  • The keys are mathematically related but it's difficult to derive one from the other.

Modular Arithmetic

  • Central to public key cryptography.

  • Operates like arithmetic on a circle (e.g., a clock).

  • Example: modulo 12 system ranges from 0 to 11. Adding 3 to 11 results in 2 (11 + 3 = 14, remainder 2).

  • Modular systems have unique mathematical properties that are leveraged in cryptography, making certain problems difficult to solve.

Prime Numbers and Relative Primality

  • Prime: A number only divisible by 1 and itself (e.g., 7 is prime, 12 is not).

  • Unique prime factorization is a key concept; every integer can be expressed as a product of primes.

  • Relative primes: Two numbers are relatively prime if they have no common prime factors (GCD is 1).

  • Algorithms for determining relative primality include Euclid's algorithm, where repeated division yields the GCD.

Diffie-Hellman Key Exchange

  • Enables two parties (e.g., Alice and Bob) to establish a shared secret without transmitting it.

  • Named after Whitfield Diffie and Martin Hellman (1970s); it revolutionized cryptography.

  • Each party generates a random number (a for Alice, b for Bob). Then:

    • Alice calculates G^a mod P.

    • Bob calculates G^b mod P.

    • They exchange these values.

  • Using the received values, they can both compute a shared secret (G^(ab) mod P), unknowable to an eavesdropper (Eve).

  • The security relies on the discrete logarithm problem, which is computationally difficult.

Public Key Cryptography

  • Public keys can be shared openly; private keys should remain confidential.

  • When Alice wants to send a message to Bob:

    • She uses Bob's public key to encrypt the message.

  • This ensures that only Bob can decrypt the message with his private key, providing confidentiality.

RSA Algorithm

  • Named after Rivest, Shamir, and Adleman.

  • Involves steps to create a secure key pair:

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

    2. Compute n = p * q.

    3. Calculate Euler's totient function: φ(n) = (p-1)(q-1).

    4. Choose e (encryption key) such that e is relatively prime to φ(n).

    5. Compute d (decryption key) such that e * d ≡ 1 (mod φ(n)).

  • Publish (e, n) as public key, keep d private.

  • Encryption: c ≡ m^e (mod n); Decryption: m ≡ c^d (mod n).

ElGamal Encryption

  • An alternative to RSA, based on similar principles:

    • Uses a large prime number p, a generator α.

    • Alice chooses a secret key d and computes β = α^d mod p (public key).

    • Bob encrypts using Alice's public information and can decrypt using his secret key.

Digital Signatures

  • Ensure message authenticity; methods include:

    • Compute a hash of the message.

    • Encrypt the hash with the sender's private key (signature).

    • The recipient can verify the signature by decrypting it with the corresponding public key and checking against the computed hash.

  • Example of signing process:

    • Signature S = d(M) where M is the message.

  • Verifying: If a computed hash of the message and the decrypted hash match, authenticity is confirmed.

Digital Signature Algorithm (DSA)

  • A standardized approach for creating digital signatures that builds on ElGamal.

  • Involves generating keys and using a random value for each message signed during the signing process.

Authentication in SSH

  • SSH uses public key cryptography for secure connection authentication.

    1. Client identifies itself.

    2. Server sends a random value encrypted with the client's public key.

    3. Client decrypts and responds with a hash of the random value and session ID to the server.

  • If hashes match, identity is confirmed.

Public Key Infrastructure (PKI)

  • Framework for managing public keys securely.

  • Certifying authorities (CAs) verify identities and issue certificates containing public keys.

  • The challenge lies in trust; users must trust the CA to avoid deception.

  • Certificates help enforce security, but vulnerabilities exist with self-signed certificates or expired keys.

Conclusion

  • Asymmetric cryptography, particularly RSA and ElGamal, forms the backbone of secure online communication through digital signatures and public key exchange.

  • Ongoing developments include elliptic curve cryptography, a promising area of research for future security protocols.