ECS726P: Security and Authentication
Week 3: Public Key Encryption
Pasquale Malacaria EECS, QMUL
Copyright By PowCoder代写 加微信 powcoder
Table of contents
1. Public-key Cryptosystem: the concept (high level idea)
2. Maths principles involved in public-key crypto (basics of number theory)
4. ElGamal and Elliptic Curve
Learning Outcomes
◃ Understand the basic principles of public-key encryption, and its differences with Symmetric key encryption;
◃ get some Familiarity with public-key encryption: RSA (how RSA works);
◃ Recognise the correctness and security underpinnings of RSA (why RSA works);
◃ Identify the main uses of public-key cryptography.
Public-key Cryptosystem: the concept (high level idea)
Symmetric Encryption
• Plaintext
Shared Key
Symmetric Encryption
• Encrypton process
Shared Key
Symmetric Encryption
• Ciphertext
Shared Key
Symmetric Encryption
• Message delivery
Shared Key
Symmetric Encryption
• Message delivery
Shared Key
Symmetric Encryption
• Decrypton process
Shared Key
Symmetric Encryption
• Plaintext
Shared Key
Motivation for Public Key cryptography
Some major issues with a symmetric key cryptosystem:
◃ How are these symmetric keys established in a secure way?
can we use encryption to send them securely?!
◃ How many secret keys are needed for N entities so
that each pair can communicate in secrecy?
How many secret keys each entity needs to maintain?
Is this practical for, say, Internet?!
◃ Anything cryptographic that the sender can do with
the key (say, “signing” messages), the receiver can also do. (why?)
Is it OK to assume this “symmetric trust”, say, e.g. in the context of Internet?!
Public-Key Encryption
• Encrypton and decrypton use diferent keys
Public Key Private Key
Public-Key Encryption
Public-Key Encryption
Public-Key Encryption
Public-Key Encryption
Public-Key Encryption
Public-Key Encryption
Public-key Cryptography: Requirements
Requirements (that we want of a public-key cipher):
– easy to generate a pair of keys (public and private);
– if Alice knows the public key of Bob, it should be easy for Alice to generate the ciphertext c of any plaintext message m of her liking (intended for Bob);
– it should be easy for Bob to decrypt the message intended for him using his private key;
– it should be computationally infeasible for an opponent, knowing the ciphertext and public key, to recover the original message m or private key.
Public-key Cryptography: Operations
Operation:
◃ Each user generates two keys: public and private;
◃ The users put their public keys in a public register. These public keys are accessible by anyone. Users keep their private keys, private!
◃ If Alice wishes to send a message to Bob, she encrypts her message using Bob’s public key;
◃ Bob decrypts it using his own private key. No one else could decrypt the message because his private key is private.
Motivation of Public Key cryptography: revisited!
Q: Which of the following problems of Symmetric Key crypto will a Public-Key crypto address?
◃ how are these symmetric keys established in a secure way?
◃ how many secret keys are needed for N entities so that each pair can communicate in secrecy? how many secret keys each entity needs to maintain? is this practical for, say, internet?!
◃ symmetric trust: anything cryptographic that the sender can do with the key (say, “signing” messages), the receiver can also do.
Maths principles involved in public-key crypto (basics of number theory)
Modular Arithmetic
modular arithmetic. same as arithmetic for integers (numbers with no decimal place) except that the results are allowed to “wrap-around” a modulus
congruence.
a≡b (modn)
means: exists k such that a = nk + b (all four numbers
integers) we read it as: a is congruent to b, modulo n. so let’s practice:
• 13 ≡ 1 (mod ?) • 15 ≡ ? (mod 7)
Modular Arithmetic
modular arithmetic.
Another way to look at modular arithmetic is
a (mod n) = remainder of the division of a by n
and a ≡ b (mod n) iff the remainder of the division of a by n is equal to remainder of the division of b by n
(intuitively b (mod n) = the hour we “end up” after b hours on a n hours clock)
Modular Arithmetic: Example
Non-modular arithmetic:
Modular arithmetic:
12×2≡0 (mod3) 12+2≡−1 (mod3)
122 ≡? (mod3)
12×2≡? (mod30) 12+2≡? (mod30) 122 ≡? (mod30)
12 × 2 = 24 12 + 2 = 14
modular arithmetic
many standard arithmetic rules holds in modular arithmetic.
For example in arithmetic we have
(xy)z =xyz
and in modular arithmetic this holds, i.e.
(xy (mod n))z (mod n) = xyz (mod n) example:
(23 (mod 3))2 (mod 3) = (8 (mod 3))2 (mod 3) = = 22 (mod 3) = 1 = 23∗2 (mod 3)
modular arithmetic
many standard arithmetic rules holds in modular arithmetic.
For example in arithmetic we have xy+1 =x×xy
and in modular arithmetic this holds, i.e. xy+1 ≡x×xy (modn)
23 ≡2×22 (mod3)
Prime numbers
Integers are numbers with no decimal place, e.g. 1,2, -1, 134 etc
If n and d are integers, and n/d is an integer, then d is said to divide n, e.g. 2 divides 10 because 10/2 = 5. gcd(n, d ) is the largest integer below n, d which divides both n, d
gcd(n, d ) is called the ”greatest common divisor” of n and d
gcd(3,4)=?, gcd(10,12)=?, gcd(30,25)=?
Prime numbers
an integer p is a prime if it is positive and of all positive integers less or equal to p, only 1 and p divides p. primes =1,2, 3, 5, 7…
hence p is prime iff gcd(p, n) = 1 for all 1 ≤ n < p
Two integers p and q are relatively prime if the only integer below p and q that divides both is 1; e.g. (4, 3) are relatively prime; (15, 7) are relatively prime; ...
hence p, q are relatively prime iff gcd(p, q) = 1
Prime numbers
a fundamental theorem of mathematics (and cryptography) is the following:
prime factorization theorem: All integers can be written (uniquely) as a product of powers of primes
30 = 5 ∗ 3 ∗ 2, 42 = 7 ∗ 3 ∗ 2, 84 = 7 ∗ 3 ∗ 22, 18 =?, 13 =? 7 =?,12 =?,19 =?
One way functions
One-Way Functions: these are functions which are very easy to compute for every input, but very difficult to “invert” for a given output, i.e., to find an input that produces that output.
- Easy to do: 7919 × 7927
- Difficult: what are the factors of: 1 689 259 081 189
One-way functions: Example 1
one-way function example 1: computing the product of two large primes:
Challenge number
20-digit number
600-digit number
600-digit even number
600-digit number with small factor
Difficulty of factoring to the two primes
Everyone can do this instantly
Doable with a little thought
Should not take more than a few minutes
A calculator is now useful
A computer is now required
This is impossible in practice
One factor immediate, the other is by division by 2 One factor easily found, other easily computed
One-way functions: Example 2
one-way function example 2: modular exponentiation with a large prime modulus
modular exponentiation: given the integers b and a large prime modulus n, the modular exponentiation function f(x) = bx mod n is believed to be a one-way function; because:
• computing f(x) is easy.
• but, given bx mod n and values of the base b and the
modulus n, working out a value for x has been a computationally infeasible problem, as long as the modulus is a large prime number.
this difficult problem is often referred to as the discrete logarithm problem.
Trapdoor One-Way Function
For public-key crypto, we need to be able to compute the inverse of the one-way function if we have the private key.
◃ trapdoor one-way function: functions which very easy to compute for every input, but very difficult to “invert” for a given output without a secret trapdoor (some specific input), however, easy to invert given a secret trapdoor.
Trapdoor one-way functions are template for public-key encryptions: the trapdoor would be the private key.
Euler totient function φ(n)
Euler totient function φ(n) is the function defined as follow: φ(n)= the number of integers less than n that are
relatively prime with n
example φ(6) = 2 because only 1 and 5 are relatively prime to 6
• Ifpisaprimenumberthenφ(p)=p−1(becauseall numbers below p are relatively prime with p)
• Ifp,qareprimenumbersthenφ(pq)=(p−1)(q−1)
Euler totient function φ(n)
φ(n)= the number of integers less than n that are relatively prime with n
Euler totient theorem: for all integers x relatively prime to n:
xφ(n)≡1 (modn)
e.g. 24 ≡ 1 (mod 5): indeed:24 =16=3∗5+1
(note: the theorem is actually more general but for our purposes the form stated is enough)
RSA Public-Key Algorithm
◃ The RSA algorithm was first published by (Ron) Rivest, (Adi) Shamir and (Leonard) Adleman in 1977
◃ Invented independently at GCHQ (in UK) earlier in 1973 (by , and others), but was not revealed until 1997 due to its top-secret classification!
RSA: Toy Example
◃ p = 13, q = 17 (these are ridiculously small primes, only for demonstration purposes!)
◃ n=p×q=221
◃ φ(n)=(p−1)(q−1)=12∗16=192
◃ Let’s choose e = 5 (it is relatively prime with 192)
◃ findds.t.ed≡1(modφ(n)),sodsuchthat5d≡1
(mod 192), so ed can be 1,193,385,...
◃ 385isdivisibleby5,sod =385/5=77.
So: public key (n, e) = (221, 5), and private key: d = 77.
Encryption: P5 (mod 221) Decryption: C77 (mod 221)
RSA’s correctness: Toy Example
So: public key (n, e) = (221, 5), and private key: d = 77. Encryption: P5 (mod 221)
Decryption: C77 (mod 221)
D(E(P)) = (P5 (mod 221))77 (mod 221) = (P5)77 (mod 221
= P5∗77 (mod 221) = P
notice we can’t naively compute (P5)77 for any number between 2 and 220! (but computers can do this immediately!)
RSA Algorithm: Encryption
in real RSA key sizes are 1,024 or 2,048 or 4,096 bits
RSA Algorithm: Encryption
◃ RSA is a block cipher in which the plaintext and ciphertext are integers between 0 and n − 1.
◃ So the first step is to represent the plaintext block in terms of an integer between 0 and n − 1.
RSA: Encryption
P: the plaintext block (an integer in 0,. . . ,n-1)
C: the ciphertext block (an integer in 0, . . . ,n-1)
( n,e): public key (both the base e and the modulus n
need to be known)
RSA Algorithm: Decryption
RSA: Decryption
Cd modn d: private key
RSA Algorithm: Correctness
◃ But does the decryption really recover the plaintext P?
◃ That is, how are we sure that:
((Pe mod n)d mod n) = Ped mod n = P
For any m in the range of 0, . . . , n − 1?
Turns out (thanks to number theory), that if the three integers (e, n, d) are chosen carefully, to satisfy a special relation, the above equation holds!
RSA Algorithm: Correctness
What is this special relation between n, e, d ? RSA: Key generation recipe!
• n: choose two large prime numbers p and q and let
• e: any number that is “relatively prime” to
φ(pq) = (p − 1) × (q − 1), i.e., e has no common factors with φ(n), i.e., gcd(e, φ(n)) = 1
• d: solve the equation: ed ≡ 1 (mod φ(n)) for d • (n, e) = public key, d = private key.
RSA algorithm: Correctness (Side note)
Why do we need to generate the keys this way? - recall: for RSA’s correctness, we need
Ped≡P (modn) - also recall: ed ≡ 1 (mod φ(n)) i.e.
ed =k(p−1)(q−1)+1forsomeintegerk. So: Ped = Pk(p−1)(q−1)+1 = P × Pk(p−1)(q−1) =
P×(P(p−1)(q−1))k =P×(Pφ(n))k ≡ P×1k (modn)≡P (modn)
we used Euler Theorem: Pφ(n) ≡ 1 (mod n)
RSA algorithm: Correctness (Side note)
RSA’s correctness:
Ped≡P (modn)
notice that in the previous derivation to use Euler Theorem: Pφ(n) ≡ 1 (mod n) P, n should be relatively prime, hence to complete the proof we also need to consider the case where P, n are not relatively prime. We leave that case out but you can find the general proof on the internet.
RSA Algorithm: Correctness
the maths behind the correctness of RSA had been known since Fermat & Euler (& Lagrange) (17th century!)
Security of RSA
Security of RSA 1: computational impossibility of decrypting a ciphertext without knowledge of private key.
Recall, the RSA’s encryption was:
C = Pe (mod n)
where n and e constitute the public key, and C can be
observed by anyone, including the adversary.
◃ computing P from the above equation while knowing C, e, and n is believed (but never proved!) to be a hard problem, called “the RSA problem”, and thus the encryption function of RSA is considered as of now a one-way function!
Security of RSA
Security of RSA 1: computational impossibility of decrypting a ciphertext without knowledge of private key.
Example: the public key is (221,5) (toy example RSA) and attacker sees the cipher text 113.
Attacker knows 113 = P5 (mod 221). Can he then derive the value of P?
(Now imagine this when the public key is not (221,5) but a pair of hundreds of digits numbers!!)
Security of RSA
Security of RSA 2: computational impossibility of determining the private key directly from the public key
◃ Attackerknowsn=p×qandalsoknowsdisa solution to ed ≡ 1 (mod (p − 1)(q − 1)), so why can’t it be done?
◃ However, for this, knowledge of (p − 1)(q − 1) is required. For this, the attacker needs to factor n into its prime factors p and q.
Factoring the product of two large prime numbers is believed (though, again, not proved yet!) to be a hard problem.
Security of RSA
Security of RSA 2: computational impossibility of determining the private key directly from the public key
Example: suppose the public key is (44010437, 4831) so you know the private key d is given by:
4831 × d ≡ 1 (mod φ(44010437)) can you compute d?
(again this is a toy example: remember RSA keys are way bigger than this!)
ElGamal and Elliptic Curve
ElGamal and Elliptic Curve (EC) Cryptosystem
RSA is not the only way to achieve a trapdoor one-way function (and hence public key cipher).
Other examples of trapdoor one-way function commonly used are given by “ElGamal algorithm, and “Elliptic Curve (EC). They use different maths (especially elliptic curves) Some of them provide some benefits over RSA e.g. shorter keys.
ElGamal, is based on the maths of Diffie-Hellman key exchange, which we will study later on.
Elliptic Curve (EC) Cryptosystem
Elliptic Curve (EC) Cryptosystem tends to be more used nowadays than RSA, mainly because they provide the same security as RSA with much shorter keys.
Elliptic Curves are solutions of equations of the form y2 = x3 − ax + b
Elliptic Curve (EC) Cryptosystem
Elliptic Curve (EC) Cryptosystem tends to be more used nowadays than RSA, mainly because they provide the same security as RSA with much shorter keys.
Elliptic Curves are solutions of equations of the form y2 = x3 − ax + b
Elliptic Curve (EC) Cryptosystem
However the points on this curve are also seen in modular arithmetics instead than reals so they look more like random noise, not a curve.
the arithmetic over points on a EC is not normal arithmetic, in particular the “hard EC problem” is: given two points p, q on the curve determine an integer k .st. q = kp. This k is the secret which allows to achieve several security services (e.g. ECDH and ECDS).
Public-Key Encryption: disadvantages
Problems with Public-Key Encryption
High Computational Cost much lower efficiency compared with symmetric encryption (a factor
of a thousand slower than AES)
Long-plaintext security issues For long plaintext, we have to split it into “blocks” and then encrypt
them separately.
- Essentially encrypting these blocks using
the public-key equivalent of ECB mode for a block cipher, which is not desirable (recall why!)
The case for Hybrid Encryption
So, symmetric and Public-key cryptography each have strengths and weaknesses. Often, we need the good properties of both:
◃ Ease of key sharing from Public-key cryptography
◃ Efficiency and simplicity from Symmetric
cryptography
So, what should we do?
- idea: Combine both!
Hybrid Encryption
Example scenario of Hybrid Encryption: Assuming Alice and Bob share their public keys,
1. Alice generates KAB = a “random” sequence of 128 bits ..
2. Alice then send {KAB}e (mod n) to Bob where (e,n) is Bob public key;
3. Bob using his private key, decrypts it, and recovers
4. From that point on, both parties (and only them) have
KAB which they use for bulk encryption of their messages during that session.
The full picture is more nuanced than this, we will revisit
this idea in week 6, when we investigate the TLS protocol! 42
Hybrid Encryption
Example: Alice wants to watch a video on YouTube
1. Alice generates KAB = a “random” sequence of 128 bits .
2. Alice look up YouTube public key (e, n) and send {KAB}e (mod n) to YouTube;
3. YouTube computes ({KAB}e (mod n))d (mod n) and retrieve KAB.
4. YouTube start sending the video encrypted with AES with key KAB using CTR mode
5. Alice receive the video and decrypt with AES with key KAB using CTR mode
Questions?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com