© University of Melbourne 2022
Introduction to Cryptography
Copyright By PowCoder代写 加微信 powcoder
• Announcement on LMS
• Spec is available via LMS
• Extra consultation hours
© University of Melbourne 2
Project 1 is out
• Operating System concepts
– Processes
– Process Scheduling
– Memory management
• Version Control (Git)
• Security & Cryptography
• Network Services and Development
© University of Melbourne
• Introduction to cryptography
• Secure communication
• Public Key Infrastructure
• System security
© University of Melbourne 4
Security & Cryptography
Introduction to Cryptography
• Symmetric encryption
• Asymmetric encryption
• Digital signatures
© University of Melbourne
It is not bitcoin or cryptocurrency or blockchains
What cryptography is not
© University of Melbourne
• Secure communication
• Authentication and verification
• Confidentiality of data when stored
© University of Melbourne 7
Cryptography: where
My credit card number is XXXX-XXX
• Secure communication
• Authentication and verification
• Confidentiality of data when stored
© University of Melbourne 8
Cryptography: where
My credit card number is XXXX-XXX
• Secure communication
• Authentication and verification
• Confidentiality of data when stored
© University of Melbourne 9
Cryptography: where
My credit card number is XXXX-XXX
Am I talking to Bob?
• Secure communication
• Authentication and verification
• Integrity
© University of Melbourne 10
Cryptography: where
My new cool C library
Was this code
written by Alice?
• Encryption
– Hiding data (plaintext) from everyone except those holding the
decryption key
– Output is a cipher text
• Decryption
– Recovering the original data from the cipher text using the key
– Output is a plaintext
© University of Melbourne 11
Encryption/Decryption
• Long and varied history
– Caesar cipher – simple substitution/shift cipher
• (founder of modern computing) led the breaking of it
• Modern cryptography developed significantly since WW2
© University of Melbourne 12
Encryption/Decryption
• Modern cryptography is based on mathematics
– Problems that are considered to be hard, or are well studied
• Factorising the product of 2 large primes (RSA)
• Solving discrete logs (ElGamal)
• AES – substitution-permutation network
• Information theoretic crypto: one time pad
– where m is a message, x is a secret key, ⊕ is XOR
© University of Melbourne 13
What is Cryptography?
Cryptography is not absolute – there is no perfect security
– Always susceptible to brute force attack
• Trying every possible key value
– The challenge is to make the brute force attack take so long as to
be infeasible to perform within the useful lifetime of the data
© University of Melbourne 14
How secure is cryptography
• Symmetric Cryptography
– Same key is used for encryption and decryption
• Asymmetric Cryptography (Public Key Crypto)
– Two keys, encrypt with one, decrypt with the other
– One of the most important developments in modern computer
• We won’t be able to cover all the details
– Be aware that in cryptography the devil is in the detail
© University of Melbourne 15
Keys in Cryptography
• Modern example is AES (Advanced Encryption Standard)
• CipherText := Encrypt(SecretKey, Message)
• Message := Decrypt(SecretKey, CipherText)
• If you want to use it to share a message with someone you
have to find some way of securely exchanging the secret key
• Useful for keeping your own data secure
– Full disk encryption
© University of Melbourne 16
Symmetric Cryptography
• AES breaks data into blocks and encrypts each block
• AES has different modes of operation
– ECB, CBC, CTR, etc.
– Determines how each block is treated, and/or linked
• AES-NI instruction set extension on Intel
© University of Melbourne 17
Symmetric Cryptography
© University of Melbourne 18
ECB – Electronic Codebook
• Simple, parallelisable
• Does not provide
diffusion, may not even
provide confidentiality
• Generally should never
© University of Melbourne 20
ECB – Electronic Codebook
• Simple, parallelisable
• Does not provide
diffusion, may not even
provide confidentiality
• Generally should never
• Good example of the problems with ECB
• The problem is that the same plaintext encrypts to the same
cipher text
• Repeated patterns will be evident in the output, albeit at a
lower fidelity
© University of Melbourne 22
ECB Penguin
© University of Melbourne 23
Symmetric Cryptography
https://xkcd.com/1286/
• Turing award 2012 to and
• Secure notion of encryption
• Enc(SK, …, “msg”) != Enc(SK, …, “msg”)
© University of Melbourne 24
Probabilistic encryption
Image source: Wikipedia
© University of Melbourne 25
CBC – Cipher Block Chaining
• IV – not secret, but must
be random and not
• Encryption must be done
sequentially
• Decryption can be done
in parallel
• Loss or corruption of a
ciphertext block or IV
affects correct decryption
of at most two blocks
© University of Melbourne 26
CBC – Cipher Block Chaining
• IV – not secret, but must
be random and not
• Encryption must be done
sequentially
• Decryption can be done
in parallel
• Loss or corruption of a
ciphertext block or IV
affects correct decryption
of at most two blocks
© University of Melbourne 27
CBC – Cipher Block Chaining
• IV – not secret, but must
be random and not
• Encryption must be done
sequentially
• Decryption can be done
in parallel
• Loss or corruption of a
ciphertext block or IV
affects correct decryption
of at most two blocks
© University of Melbourne 27
CBC – Cipher Block Chaining
• IV – not secret, but must
be random and not
• Encryption must be done
sequentially
• Decryption can be done
in parallel
• Loss or corruption of a
ciphertext block or IV
affects correct decryption
of at most two blocks
© University of Melbourne 27
CBC – Cipher Block Chaining
• IV – not secret, but must
be random and not
• Encryption must be done
sequentially
• Decryption can be done
in parallel
• Loss or corruption of a
ciphertext block or IV
affects correct decryption
of at most two blocks
• More commonly called public key cryptography
• At the heart of modern security
– Digital signatures
– 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 30
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 31
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 32
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 33
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 34
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 35
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 36
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 37
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 38
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 39
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 40
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 41
Cryptographic Hashing
• Two hashes, small difference, big change
• Small file hash (13 bytes)
• Large file hash (1.6 GB)
© University of Melbourne 42
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 43
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 44
*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 45
Randomness
https://xkcd.com/221/
© University of Melbourne 46
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 47
And finally…
https://xkcd.com/538/
• Symmetric vs asymmetric cryptography
• Encryption
• Signatures
© University of Melbourne 48
• 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