RECORD THE LECTURE
PUBLIC KEY CRYPTOGRAPHY
COMP2420/COMP6420 INTRODUCTION TO DATA MANAGEMENT, ANALYSIS AND SECURITY
Copyright By PowCoder代写 加微信 powcoder
WEEK 9 – LECTURE 2 Wednesday 04 May 2022
John (course convenor)
School of Computing
College of Engineering and Computer Science
Credit: (previous course convenor)
HOUSEKEEPING
Things to note
• Assignment 1 marks released
• Please start working on Assignment 2 (seek help early and use available resources like labs and drop-ins and Piazza)
Outcomes you should be able to:
01 By the end of this lecture,
Describe a taxonomy of cryptosystems
Explain what a public key cryptosystem is
Apply relevant rules to perform encryption and decryption using a public key approach
Discuss how both public key and private key approaches can be used together
Reflect on the security of public key and private key systems
• We previously looked at symmetric key (or secret key) cryptography
• One shared key for both encryption and decryption.
• Key is secret
• Look at other approach today
TAXONOMY CRYPTOSYSTEMS
A taxonomy of Cryptosystems
• Ciphers in terms of encryption process
– Stream ciphers (symmetric key only)
– Block ciphers
»Symmetric key or secret key block
»Asymmetric key or public key ciphers
A taxonomy of Cryptosystems
• Ciphers in terms of number of keys – Symmetric key cipher (secret key
cipher) »Stream cipher »Block cipher
– Asymmetric key cipher (public key cipher)
PUBLIC KEY CRYPTOSYSTEMS
What is public (or asymmetric) key cryptography
• Has a pair of keys, one is public and the other is private.
• Given a public key, it is computationally infeasible to find the corresponding private key.
• Public key is used for message encryption; can be used by anyone.
• Private key is used by the owner to decrypt encrypted messages correctly.
How can public keys be accessed?
• Public keys can be put in a publicly accessible directory like telephone yellow pages.
• Some of the public key systems can be used for digital signatures.
Example: ICAO PKD (Internation Civil Aviation Organisation Public Key Directory) For Authentication of e-passport information
Attribution:Public Key System 13
Public Key System
PUBLIC KEY VS SECRET KEY CRYPTOSYSTEM
public key vs secret key cryptosystems
• Secret key cryptosystems normally employ faster algorithms than those in public key systems.
• Public key system is more convenient to use as no pre-established common key is required.
>>Public key system can be used in conjunction with secret key system.
– Public key algorithm is used for encryption of session keys which are then used for message encryption using secret key algorithms.
Session Key Exchange using Public Key
Attribution:Session Key Exchange
TRANSMITTING SECRET INFORMATION THROUGH PUBLIC CHANNELS
Diffie-Hellman key exchange (invented by Diffie, Hellman and Merkle)
Secret key distribution can be a problem (cost v.s. security)
Diffie-Hellman key exchange (1977): Common knowledge to 𝐴 and 𝐵:
• 𝑝, a large prime, and 𝑔 < 𝑝, a number called a primitive root of p
• 𝛼=𝑔!! mod𝑝,where𝑟" isa
random number
Further reading: Comparitech article Primitive roots explanation
More about primitive roots
• 𝛽 = 𝑔!" mod 𝑝, where 𝑟# is random number
𝐴 computes: "
𝐾! = 𝛽 ! mod 𝑝
𝐵 computes:
𝐾$ = 𝛼"" mod 𝑝
(i.e. g " ! mod p)
Common key:
(i.e. g#!#" mod p) Then 𝐾! = 𝐾$ is the common key
The security of Diffie-Hellman key exchange
• Given𝑝,𝑔and𝐺=𝑔! mod𝑝,howto compute 𝑥?
• It is a hard problem (difficulty is dependent on the size of p)
p needs to be a large prime number
g is a smaller number (called a primitive root of p or generator) less than p
Worked example: Diffie- is the number A (or alpha) that Alice sends to Bob? What is the number B (or beta) that Bob sends to Alice? What is the common secret key?
Attribution:Diffie Hellman Key Exchange 22
Diffie Hellman Key Exchange
Design Principle of Public Key System
Use a one-way trapdoor function. A one-way trapdoor function 𝑓$ 𝑥 satisfies the following properties:
Given 𝑥 and 𝜆, it is trivial to compute 𝑦 = 𝑓$ 𝑥 . Given 𝑦, without knowing the trapdoor parameter 𝜆, it is computationally infeasible to find 𝑥
Invertible:
Given 𝑦, with the knowledge of 𝜆, it is easy to find 𝑥
Design Principle of Public Key System
When a trapdoor is used as public key system:
Encryptionis𝑦=𝑓% 𝑥
Decryption is finding 𝑥 given 𝑦, which can be done only by someone knowing the secret 𝜆
RSA PUBLIC KEY SYSTEM
• Invented by Rivest, Shamir, and Adleman in 1979 (paper and patent for twenty years)
• It is a typical example of how pure mathematics can be used directly in the commercial world
• It revived the mathematical branch — Number Theory. Today Computational Number Theory is very popular
• Based on the computational infeasibility of integer factorization. Given a composite number 𝑛, find its prime factors 𝑝", 𝑝#, . . . , 𝑝% such that 𝑝" ∗ 𝑝# ∗ ⋯
• What are the prime factors if 𝑛 is: –6
What approach would you use?
• Known to be a hard problem, for classical computers
• Can be solved in polynomial time on quantum computers (Shor’s algorithm]
Q.1: Find the prime factors of 1240.
Prime Factors
Step 1: Divide by 2
1240 ÷ 2 = 620
Step 2: Divide by 2
620 ÷ 2 = 310
Step 3: Divide by 2
310 ÷ 2 = 155
Step 4: Divide by 5
155 ÷ 5 = 31
Step 4: Divide by 31
31 ÷ 31 = 1
Source:byjus.com 28
∴ The Prime Factors of 1240 will be 23 × 5 × 31.
Approach: Division method and factor tree method
• Choose large primes 𝑝 and 𝑞; let 𝑛 = 𝑝𝑞
• Choose a random number 𝑒 satisfying 𝑔𝑐𝑑𝑒,𝑝−1𝑞−1 =1,1<𝑒<𝑝−1𝑞−1; public key: (e,n)
• Compute𝑑suchthat𝑒𝑑mod 𝑝−1 𝑞−1 =1;(𝑒and 𝑑 are called inverses of each other in the sense of modulo
𝑝−1 𝑞−1 );privatekey:(d,n)
A number 𝑚 < 𝑛.
Chop message into small blocks. Size of each block
being less than 𝑛. Encryption:
𝑐 = 𝑚' mod 𝑛. Decryption:
𝑚 = 𝑐( mod 𝑛.
RSA: An Example
𝑝=13,𝑞=23,𝑛=𝑝𝑞=299, 𝑝−1 (𝑞 − 1) = 264
𝑒=5,𝑑=53.(Check:𝑒𝑑mod 𝑝−1 (𝑞 − 1) = 265%264 = 1!!)
If 𝑐 = 282,48,223,104 is the ciphertext, what is the original message?
Recap RSA key generation steps
• Choose large primes 𝑝 and 𝑞; let 𝑛 = 𝑝𝑞
• Choose a random number 𝑒 satisfying
𝑔𝑐𝑑 𝑒, 𝑝−1 𝑞−1 =1,1<𝑒< 𝑝−1 𝑞−1 ; public key: (e,n)
• Compute𝑑suchthat𝑒𝑑mod 𝑝−1 𝑞−1 =1;(𝑒and 𝑑 are called inverses of each other in the sense of modulo
𝑝−1 𝑞−1 );privatekey:(d,n)
Encryption:
Decryption:
𝑚 = 𝑐" mod 𝑛.
Decryption: 𝑐( mod 𝑛 = 𝑚
28201 mod 299 = 16
4801 mod 299 = 29 22301 mod 299 = 123 10401 mod 299 = 234
Message𝑚= 16,29,123,234
RSA Security
• If factorization of 𝑛, the public modulus, can be done, then RSA system is broken.
• If RSA is broken, it does not mean that the factorization of 𝑛 can be done easily.
Factoring ⟹⟹ the RSA problem •
Breaking RSA system is no harder than factorization of 𝑛, and it is publicly believed that it is no easier either.
The RSA problem ⟹?⟹? Factoring
• Practical use: Key size of 2048 bits. Use 4096 bits for highly confidential message encryption. What would be the sizes of 𝑝 and 𝑞 in these cases?
(note: RSA key sizes)
Further reading: discussion on crypto stackexchange 33
RSA key size and lay-out
Practical use: Key size of 2048 bits. 2048 bits = 256 bytes
Source: RSA key sizes
d (256 bytes) is the private exponent d
p (128 bytes) is the first prime multiple of the modulus n
q (128 bytes) is the second prime multiple of the modulus n dp (128 bytes) is the remainder d (mod p − 1)
dq (128 bytes) is the remainder d (mod q − 1)
RSA Factoring Challenge
• RSA Factoring Challenge was sponsored by RSA Laboratories, to learn about the actual difficulty of factoring large numbers of the type used in RSA keys. It involved a set of eight challenge numbers, ranging in size from 576 bits to 2048 bits. The challenge ended in 2007.
• On December 3, 2003, a team of researchers in Germany and other countries announced the factoring of RSA-576, a 576-bit or 176-digit number. Prize money: US$10,000
• The next challenge number RSA-640, a 193-digit number, was factored on November 2, 2005. Prize money: US$20,000.
• The challenge number next to this is RSA-704, a 212-digit number. This was factored on July 2, 2012. Prize money offered previously was US$30,000.
• The challenge number next to this is RSA-220, a 220-digit number. This was factored on May 13, 2016. No prize money for this one.
• The next challenge number is RSA-230, a 230-digit number. This was factored on August 15, 2018
• RSA-768, a 232 digit number, was factored on December 12, 2009
• The before last one factored is RSA-240, a 240 digit number, on December 2, 2019
• Last one factored (as of now) is RSA-250, a 250 digit number, on February 28, 2020
RSA-896 (270 digits) has prize money of USD$75k
RSA versus DES
• RSA is about 1000 times slower than DES
• DES is based on tricky design (as are other block ciphers such as IDEA), while RSA is based on hardness of mathematical problems (as are other public key algorithms)
• DES is suitable for bulk message encryption, and RSA suits for short message encryption
Use RSA In Conjunction With DES/AES
• Use RSA (or any other public key system) to encrypt session keys (A session key is a key temporarily used only for a communication session)
• Use AES (or any other secret key system) for real message encryption during a session (using that session key)
• No common secret key is required as would be the case when AES is used alone
Use RSA In Conjunction With DES/AES
• Speed of encryption and decryption can be roughly the same as AES, provided that the length of message is far larger than that of the session key (normally 128 bits)
• Note: We use AES here, but it could be any secret key block cipher
Other Public Key Systems
• ElGamal: Discrete logarithm based system
• Rabin: Similar to RSA, with security equivalent to factorization
• McEliece public key cryptosystem: Based on error-correcting codes
• There are many many other public key cryptosystems in public literature
Use of Public Key Systems
• Together with a secret key cipher (as stated above)
• Largely used for digital signatures (week 11 lecture). Note that some public key systems need to be modified to provide signature functionalities.
• Overview of public key crypto- system
• Details of Diffie-Hellman and RSA
• Using both public key and private key approaches together to increase security
End of lecture
• No live coding
• Next week, guest lectures by cybersecurity experts from IBM
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com