Introduction to Information Security

Asymmetric Encryption for Authentication

Bob
Alice

Applications for Asymmetric Encryption

• Three categories
• Encryption/decryption: sender encrypts a message with receiver’s public key
• Digital signature: sender “signs” a message with its private key
• Key exchange: two sides exchange a session key

Security of Asymmetric Encryption

• Like symmetric schemes brute-force exhaustive search attack is always theoretically possible, but keys used are too large (>512bits)
• Not more secure than symmetric encryption, dependent on size of key
• Security relies on a large enough difference in difficulty between easy (en/decrypt) and hard (cryptanalyse) problems
• Generally the hard problem is known, just made too hard to do in practice
• Require using very large numbers, so is slow compared to symmetric schemes

Public key directory
encryption
decryption
M
Alice’s public key
cryptanalysis
M
private key
C
M
Alice
Eve
private key
Public key Cryptographic System

• C = EPK(M)
• M = DSK(C) = DSK(EPK(M))
• Public keys are published.
• Each private key is known to the receiver only.
• Difficult for Eve to find out SK from PK.

Public key vs. Symmetric key

Symmetric key
Public key
Both share same key
(or one key is computable from the other)
Typically faster
Typically slower
Two parties MUST trust each other
Two parties DO NOT need to trust each other
Two separate keys: a public and a private key
Examples:
DES, IDEA, RC5, CAST, AES, …
Examples:
RSA, ElGamal Encryption, ECC…

Digital signatures

• Is there a functional equivalent to a handwritten signature?
• Easy for legitimate user to sign
• But hard for anyone else to forge
• Easy for anyone to verify
• Dependent on message & signer (key)
• Public key!
• Sign: “invert” function using private key
• Verify: compute function using public key