• More commonly called public key cryptography
• At the heart of modern security
– Digital signatures
Copyright By PowCoder代写 加微信 powcoder
– TLS (Transport Layer Security)
– Secure Messaging
– End-to-end Encryption (WhatsApp, Signal, etc.)
• Consists of two related keys
– Public Key – as per the name, can be made public
– Private/Secret Key – must be kept secret by the owner/user
© University of Melbourne 28
Asymmetric Cryptography
• Alice generates her key pair (PublicKey, PrivateKey)
• She posts her PublicKey online
• Bob wants to send Alice a secret message m
• Bob runs CipherText := Encrypt(PublicKey, m)
• Bob sends the CipherText to Alice over the internet
• Alice runs m := Decrypt(PrivateKey, CipherText)
– Alice recovers the secret message
• No need to meet or securely exchange any keys
© University of Melbourne 29
Asymmetric Cryptography
• Asymmetric Cryptography is slower than Symmetric
• It often isn’t suitable for encrypting large amounts of data or
even multiple blocks
• Often used together with Symmetric Cryptography as a way
of exchanging a joint secret key
© University of Melbourne 30
Asymmetric & Symmetric
• Secret key SK
• Cipher Text := Encrypt(SK, message)
• message := Decrypt(SK, Cipher Text )
• PublicKey, PrivateKey
• CipherText := Encrypt(PublicKey, message)
• message := Decrypt(PrivateKey, Cipher Text )
Bob knows Alice’s PublicKey and has a very very very long message m.
Q: How can Bob use Symmetric and Asymmetric Crypto to send m to
© University of Melbourne 31
Asymmetric & Symmetric
• Alice generates her key pair (PublicKey, PrivateKey)
• She posts her PublicKey online
• Bob generates a SK with symmetric encryption
• Bob runs CipherText := Encrypt(PublicKey, SK)
• Bob sends the CipherText to Alice
• Alice runs SK := Decrypt(PrivateKey, Cipher Text)
• Now Alice and Bob share a SK and can exchange
Symmetrically encrypted messages
• This is sort of how TLS (HTTPS) works
– A lot of further detail, but in principle, TLS is a key exchange protocol
© University of Melbourne 32
Key Exchange
• RSA is probably the most well known Public Key Cryptography
– Other examples are ElGamal, and Elliptic Curve ElGamal
– Generates a 2048 bit Key Pair
– Extract PublicKey from key pair file
© University of Melbourne 33
Asymmetric Cryptography in Action
openssl genpkey -algorithm RSA -out PrivateKey.pem -pkeyopt rsa_keygen_bits:2048
openssl rsa -pubout -in PrivateKey.pem -out PublicKey.pem
RSA: Rivest–Shamir–Adleman also Turing award!
• Simple example, would not normally directly encrypt a
message with RSA
• Encrypt msg.txt with PublicKey.pub (short message)
• Decrypt ciphertext.enc with PrivateKey returning plaintext.txt
• Normal approach would be to generate an AES key then
encrypt that with the PublicKey, and encrypt the file with the
symmetric key
© University of Melbourne 34
Asymmetric Cryptography in Action
openssl rsautl -in msg.txt -out ciphertext.enc -pubin -inkey PublicKey.pub -encrypt
openssl rsautl -in ciphertext.enc -out plaintext.txt -inkey PrivateKey.pem –decrypt
• Secure communication
• Authentication and verification
• Integrity
© University of Melbourne 35
Cryptography: where
My new cool C library
Was this code
written by Alice?
• Provides a link between a key holder and a
message/document/file
• Importantly, is considered to provide non-repudiation
– Cannot deny having signed the document
• Provides integrity (against tampering)
© University of Melbourne 36
Public Key Signatures
• Generate SignKey (kept private) and VerifKey (Public)
• s := Sign(SignKey, m)
• Anyone can check if verification succeeds:
– Verify(VerifyKey, s, m) ?
© University of Melbourne 37
Public Key Signatures
What happens with large documents?
– Use a Cryptographic Hash Function
• Takes a near arbitrary length input and outputs a fixed length digest
• SHA256, SHA512, (MD5, SHA1 – now deprecated)
– Sign the Hash Digest – which can be recalculated by the verifier:
s’ := Sign(SignKey, h) where h = Hash(m)
© University of Melbourne 38
Public Key Signatures
• Hash function H is a lossy compression function
– Collision: H(x)=H(x’) for some inputs x≠x’
• H(x) should look “random”
– Every bit (almost) equally likely to be 0 or 1
• A cryptographic hash function must have certain properties:
– Collision resistance: hard to find x≠x’ such that h(x)=h(x’)
• Hashing vs. encryption
• Applications: password storage(?), software integrity
© University of Melbourne 39
Cryptographic Hashing
• Two hashes, small difference, big change
• Small file hash (13 bytes)
• Large file hash (1.6 GB)
© University of Melbourne 40
Cryptographic Hashing
echo 123456 | openssl sha256
e150a1ec81e8e93e1eae2c3a77e66ec6dbd6a3b460f89c1d08aecf422ee401a0
echo 123457 | openssl sha256
4547694d80b0c7675bca81b8e9ea8efdeda10c92b910c19a83c08e2f06bf5cc8
openssl sha256 plaintext.txt SHA256
(plaintext.txt)=
03ba204e50d126e4674c005e04d82e84c21366780af1f43bd54a37816b6ab340
openssl sha256 ubuntu-16.04.3-desktop-amd64.iso SHA256
(ubuntu-16.04.3-desktop-amd64.iso)=
1384ac8f2c2a6479ba2a9cbe90a585618834560c477a699a4a7ebe7b5345ddc1
• Alice wants to sign a document, calls:
– Sign(PrivateKey, Hash(document)) -> Digital Signature
• Bob wants to verify Alice signed the document, calls:
– Verify(PublicKey, Hash(document)) -> True or False
– If we modify the document by a single character
© University of Melbourne 41
Public Key Signatures
openssl dgst -sha256 -sign PrivateKey.pem -out signature.txt plaintext.txt
openssl dgst -sha256 -verify PublicKey.pem -signature signature.txt plaintext.txt
Verified OK
openssl dgst -sha256 -verify PublicKey.pem -signature signature.txt modified.txt
Verification Failure
• Recall our security is based on a computationally hard problem,
taking an infeasibly long time to solve using brute force
• As such, our security parameter, which determines the degree of
security we achieve, is the key size
– Normally expressed in bits
• Different key lengths are required for symmetric and asymmetric
– Reflects the different mathematically hard problems they are based on
– Asymmetric is generally longer than Symmetric, current minimums:
• RSA – 2048 bits (3072*), AES – 128 bits
• Previously much shorter – 512 bits for RSA in the 90’s, 56 bits for DES
© University of Melbourne 42
*https://www.cyber.gov.au/
• Cryptography is dependent on randomness
– Key Generation
– IV generation for ciphers
• Pseudorandom generators
• Randomness must never be reused or discoverable
• Generating good randomness is hard
– Must be unpredictable
– Dependent on good OS implementations
© University of Melbourne 43
Randomness
https://xkcd.com/221/
© University of Melbourne 44
Do not roll your own cryptography
• Just because something looks
random, doesn’t mean it is
securely encrypted
• Even the smallest mistake can
weaken the entire approach
• When we talk about large
numbers in cryptography we
mean very large numbers
• Compromising
randomness generation is
a known attack
– NSA Dual EC DRBG
© University of Melbourne 45
And finally…
https://xkcd.com/538/
• Symmetric vs asymmetric cryptography
• Encryption
• Signatures
© University of Melbourne 46
• The slides were prepared by based on
material developed previously by: , , , , and .
• Some of the images included in the notes were supplied as
part of the teaching resources accompanying the text books
listed in lecture 1.
– (And also) Wikimedia Commons
• Reference: KR 8, 8.1, 8.2 till RSA (unless curious to learn
more about RSA), 8.3, 8.3.1, 8.3.3 till page 644
Acknowledgement
© University of Melbourne
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com