Introduction to Information Security

Digital signatures

Message
rfwekfs
Sign
Private key
Message
rfwekfs
Verify
Public key
Valid/Invalid
(fixed-length signature)

• Only the signer (who has a private key) can generate a valid signature
• Everyone (since the corresponding public key is published) can verify if a signature with respect to a message is valid

Digital Envelopes -- Symmetric + Asymmetric

• Generate a secret key (session key) at random.
• Encrypt the message using the session key and symmetric algorithm.
• Encrypt the session key with the recipient’s public key. This becomes the “digital envelope”.
• Send the encrypted message and the digital envelope to the recipient.
• Figure …

Digital Envelopes

Plain
Cipher
Cipher
Plain
Session Key
Session Key
Session Key
Session Key
Recipient’s
Public key
Digital Envelope
Digital Envelope

Motivation

Revision

• One problem with symmetric key algorithms is that the sender needs a secure method of telling the receiver the key.
• Plus, you need a separate key for everyone you might communicate with.
• Public key algorithms use a public-key and private-key pair to tackle key management problem.
• Each receiver has a public key pair.
• The public key is publicly known (published).
• A sender uses the receiver’s public key to encrypt a message.
• Only the receiver can decrypt it with the corresponding private key.

RSA

• Invented by Rivest, Shamir & Adleman of MIT in 1977
• Best known and widely used public-key scheme
• Based on exponentiation in a finite (Galois) field over integers modulo a prime
• exponentiation takes O((log n)3) operations (easy)
• Use large integers (e.g. 1024 bits)
• Security due to cost of factoring large numbers
• factorization takes O(e log n log log n) operations (hard)