FIT2093 INTRODUCTION TO CYBER SECURITY
Week 4 Lecture Cryptography III:
Public Key Encryption: Part 2 – Encryption Algorithms
Principles for CONFIDENTIALITY
Copyright By PowCoder代写 加微信 powcoder
www.monash.edu
Public-Key Cryptography
Last week: concept and maths of PKE
This week: how public-key algorithms work ● Sharing secrets over public channels
• Diffie- Exchange ● Public-key encryption
● HybridEncryption
Diffie- Exchange
Symmetric Key Encryption (SKE): Limitation
Public Key Crypto
● both sides share same secret key ● Q: how to share securely?
○ keydistributionproblem
Solving the Key Distribution Problem
Public Key Crypto
● share secret using public channel?
● jointly compute secret key based on public values?
● Diffie- Exchange (1976): 1st idea that suggests PKC
note: (UK GCHQ) secretly found it in 1974!
Diffie- Exchange
Public Key Crypto
● Used almost everywhere
○ SSL/TLS(https):web
○ IPsec:IPpackets
○ Bluetooth:personalareanetworks ○ 5G:mobilecomms
○ IoT:internetofthings/sensors ○ …
Diffie- E: Design Strategy
Public Key Crypto
● Easyforgoodguys(Tx,Rx)to:
• generate own public key pk
• compute K
● Infeasibleforattackerto:
• get other’s sk from pk
• compute K
Diffie- E: What
Public Key Crypto
● pandgarepublicparameters,pisaprimenumber
● aisprivatekeyofAlice,bisprivatekeyofBob
● AispublickeyofAlice,BispublickeyofBob
● A=f(a),B=f(b):privatekey&public key have special relationship
● K=sharedsecretkeybetweenAlice and Bob = g(A, b) = g(B, a)
● Functions f and g are modular exponentiation – efficiently computable
Diffie- E: Why It works
Public Key Crypto
● A=f(a)=ga modp;B=f(b)=gb modp:skandpkhavespecialrelationship ● K=sharedsecretkeybetweenAliceandBob
● Q:WhydoAliceandBobcomputethesameKwhentheyusedifferentformulas? ForAlice:K=Bamodp=(gb)a modp=gba modp
ForBob: K=Abmodp=(ga)b modp=gab modp Both can easily compute K, using
modulo exponentiation & their own private key
Diffie- E: Why it Solves the Problem
Public Key Crypto
● The only secret of Alice is a ● while p and g are public
● A is sent over channel, so public too:
• no secret is sent over channel,
• so no private key distribution problem
Diffie- E: Example I
Public Key Crypto
• p = 23, g = 5 • Alice
choose a = 6 (private) compute A=ga modp
= (52×5)2 mod 23 = (2×5)2 mod 23
= 8 (mod 23)
choose b = 15 (private) compute B=gb modp
=515 mod23
= ((52×5)2×5)2×5 mod 23
= (2×5)2×5)2×5 mod 23 = (8×5)2×5
= 13 x 5 (mod 23)
Diffie- E: Example I
Public Key Crypto
Alice (a = 6)
A=8 B = 19
compute K=Ba modp
= 196 mod 23
= (192×19)2 (mod 23)
= ((-7) x (-4))2 (mod 23) = 52 (mod 23)
= 2 (mod 23)
Bob (b = 15)
= ((82×8)2×8)2×8 mod 23
= (((-5)x8)2×8)2×8 mod 23
= (13×8)2×8 mod 23 = 6x8mod 23
= 2 (mod 23)
Diffie- E: Example II
Public Key Crypto
Suppose p = 17, g = 7, Alice’s private key a = 4.
1) What is Alice’s public key A?
2) If Alice receives Bob’s public key B = 5, what is the shared key K between Alice and Bob?
Activity (2 mins)
1) Click the latest link in the Zoom chat
2) Add your question response to the Ed forum
Diffie- E: Security
Public Key Crypto
● the secrets:
○ shared key: K
○ each person’s private key: a , b
● to attack (compute K), attacker needs to know a or b
● Q: can attacker get a?
○ can get/compute a from p, g, A?
○ Discrete Log Problem (DLP) – computationally infeasible (large a,b,p)
● Q: can attacker get K?
○ can get/compute K without knowing a , b but only knowing p, g, A?
○ Diffie- (DHP) – computationally infeasible (large a,b,p)
Diffie- E: Security
Public Key Crypto
● The secrets:
○ shared key: K
○ each person’s private key: a , b
● Discrete Log Problem (DLP)- infeasible:
○ given A= ga mod p is known, g and p known, ○ compute the exponent/discrete log a
● Diffie- (DHP) – infeasible: ○givenA=ga modpisknown,B=gb modp,g
and p also known,
○ compute K = gab mod p
Diffie- E: Security
Public Key Crypto
• use Rx’ public key B
• Q: what if public key B replaced with attacker’s pub key M?
• Integrity attack (also known as Man-in-the-Middle attack) on pk
value is devastating
Diffie- E: MIM Attack
Public Key Crypto
choose a (private) computeA=ga modp
compute M=gm modp AM
choose b (private) compute B=gb modp
Attacker shares a key with Alice and a key with Bob – can read their communications – we’ll return to this problem later (use authenticated certificates).
From Diffie-Hellman to ElGamal
Public Key Crypto
• In DHKE, both Alice/Bob publish their public key A and B
Alice (Tx)
• In public-key encryption, Bob (Rx) publishes his public key B, Alice generates a ciphertext based on Bob’s public key B
B C = E(B,P) C
From Diffie-Hellman to ElGamal
Public Key Crypto
• But can convert DH key exchange to public-key encryption (PKE) [ElGamal PKE, 1985]
• Idea: Alice includes “ephemeral” public key” A in her ciphertext to (Tx) Bob (Rx)
C = E(B,P) A, C
From Diffie-Hellman to ElGamal
Public Key Crypto
chooseg,p,b&B=gb modp
(private key: b, public key: B)
lookup public key of Bob: B
choose random ephemeral (one-time) a
compute A = ga mod p
(ephemeral private key: a, ephemeral public key: A) compute ephemeral shared key K = Ba mod p = gab mod p
A, C = Enc(K,P) ( Enc: symmetric key encryption)
From Diffie-Hellman to ElGamal
Public Key Crypto
A, C = Enc(K,P)
compute K = Ab mod p = gab mod p decrypt C using K to get P, i.e.
P = Dec(K,C)
RSA Public-key Encryption (PKE)
Public Key Crypto
1st Public-Key Encryption/Cipher [1977]
Note: Secretly discovered by (UK GCHQ) in 1973 following PKC concept discovery by (UK GCHQ) in 1969
RSA Public-key Encryption (PKE)
Public Key Crypto
• choose two distinct large primes p and q
• compute the modulus n = pq
• compute the Euler’s totient function ø(n) = (p–1)(q–1)
• choose an integer e coprime to ø: e is the public key
• compute d = e–1 mod ø(n) as e’s inverse: d is the private key
• Note: e×d ≡ 1 mod ø(n) since d is the multiplicative inverse of e
• Recall (last week): All of the above operations are efficiently computable
even for large numbers.
RSA Public-key Encryption (PKE)
Public Key Crypto
• outputs key pair: public key (e, n), private key d
• c = me mod n (modular exponentiation)
• m = cd mod n (modular exponentiation)
RSA PKE: KeyGen Example
Public Key Crypto
● choosetwoprimes:p=5,q=11
● computethemodulusn=pxq=55
● computeø(n)=(p–1)x(q–1)=4×10=40
● findouttwonumberse=3&d=27whichsatisfy (3 * 27) mod 40 = 1
● Bob’s public key: (e, n) = (3, 55)
○ encryption: modular exponentiation
● Bob’s private key: (d, n) = (27,55) ○ decryption: modular exponentiation
RSA PKE: Encrypt Example
Public Key Crypto
● Alice has a message m=13 to be sent to Bob
● Compute the ciphertext c as: c = me (mod n)
= 133 (mod 55)
= ( 169 (mod 55) x 13 mod 55 ) mod 55
= 4×13 mod 55 = 52 (mod 55)
RSA PKE: Decrypt Example
Public Key Crypto
• Bob receives c=52 from Alice
• Compute the plaintext as: (use 27 = 110112)
m = 5227 (mod 55)
= ((((-3)2x(-3))2)2x(-3))2x(-3) (mod 55) = ((14)2x(-3))2x(-3) (mod 55)
= 172 x (-3) (mod 55)
RSA Encryption – Example 2
Public Key Cryptography
Suppose Bob’s public key is (e = 7, n = 33).
1) What is Bob’s private key d?
2) If Bob receives a ciphertext c = 8 from Alice, what message m does Bob decrypt?
Activity (2 mins)
1) Click the latest link in the Zoom chat
2) Add your question response to the Ed forum
RSA PKE: Why Works?
Public Key Crypto
• Recall: e x d ≡ 1 mod ø(n)
• But recall from last week:
• Implication of Euler’s Theorem: My mod n = M if y mod ø(n) = 1
•Here,y=exd:soMy modn=Mexdmodn=M.
• Encrypt: c = me mod n
• Decrypt (why it works?)
• cd modn=mexd modn=m(modn) • by implication of Euler’s Theorem!
RSA PKE: Security
Public Key Crypto
● thesecrets:privatekeyd,ø,p,q,plaintextm
● The known info to attacker: known values pub key (e, n), ciphertext c
● Q1: Can attacker efficiently compute p, q from public key (e,n)? Why/Why not? ● Q2: What about computing ø? Why/Why not?
● Q3: What about computing d? Why/Why not?
● Q4: What about computing m? Why/Why not?
RSA PKE: Security
Public Key Crypto
• Attack approaches
• since knows m in range [1, (n–1)], brute force through
all n possible values (exp time, infeasible), or
• compute d based on d = e-1 mod ø(n)
• but need to compute ø(n)=(p–1)x(q–1) which needs
to know p and q,
• i.e. need to factor n – Integer Factorisation Problem
– infeasible (last week).
• (vs honest users just do efficient exponentiation)
Q: Is above RSA encryption method secure if m is chosen from a small set of possible messages (e.g. m = 10 (“yes”), m = 20 (“no”))? Why/Why not?
PKE Key Lengths vs Security
Public Key Crypto
Fig. source: https://www.keylength.com/
RSA PKE vs ElGamal PKE: Security Summary
Public Key Crypto
pk & sk relations
Problem for attacker
Integer Factorisation Problem
Discrete Logarithm Problem
Integrity Attack on PKE Key Directory
Public Key Crypto
Tx (Tania) Rx (Riley)
pkR
• Tania (Tx) uses Riley’s (Rx) public key pkR
• Q: Why is RSA PKE insecure if attacker Marvin can replace pkR received by Tania with pkM (pub key of Marvin)?
Solving the PKE Key Integrity Problem
Public Key Crypto
● digital certificates
● trusted certification authority authenticates public keys of user
● Anyone can verify user’s
certificate to check authenticity of
àprevent MIM/Integrity attacks.
(we’ll revisit in the Security protocols Week – after we study
digital signatures)
PKE or SKE?
Public Key Crypto
Each user has a public key pk & a private key sk;
pk & sk are mathematically related
Each user shares a secret key k with another
Do with pk, undo with sk
Do and undo with k
No Private Key Distribution Problem
Private Key Distribution Problem
Hybrid Encryption (a.k.a. Digital Envelope)
Public Key Crypto
In practice, we can combine best features of PKE and SKE
● use a PKE
○ todistribute/transportthekeyusedforSKE
■ keysmallsodoesnotmattermuchthatitisslow
■ solvesprivatekeydistributionproblem ● useanSKE
○ toencryptanddecryptmessages:
■ canencryptlargemessagesfast
Hybrid Encryption: Digital Envelope
Public Key Crypto
Further Reading
Public Key Crypto
Chapter 21 of the reference book: Computer Security: Principles and Practice” by & , , 2015
Optional deeper reading:
• Chapter 10 of the reference book: Introduction to Modern Cryptography, by and , Chapman & Hall/CRC, 2008
• PKCS #1 v2.2: RSA Cryptography Standard (EMC Corporation), available at https://www.emc.com/collateral/white-papers/h11300-pkcs-1v2-2- rsa-cryptography-standard-wp.pdf
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com