PKC Flashcards
Public key encryption
- Proposed (in the open literature) by Diffie & Hellman in 1976
- Each party has a public encryption key and a private decryption key
- Computing the private key from the public key should be computationally infeasible
- The public key need not be kept secret but it is also not necessarily known to everyone
Public key cryptography
A Public Key Encryption Scheme {eKp :Kp ∈Κ} and {dKs :Ks ∈Κ}
has the the following property:
- Knowing eKp and given c ∈ C,it is infeasible to find anm∈M,such thateKp(m) = c
eKp can be public information!
Advantage:
- eKp can be communicated over unsecure channels
Disadvantage
- eKp and dKs are computationally more expensive than in symmetric schemes
PKI application
One way function
A function f: X → Y is called a one-way function if
∀ x ∈ X:
1. Computing f(x) is „easy“,
2. Computing f -1(y) is „hard“ or „infeasible“
Example: modular cube roots
- Select primes p = 48611 and q = 53993
- Let n = pq = 2624653723 and X = {1,2,…,n-1}
- Definef:X→Yby f(x)=x3 modn Example: f(2489991) = 1981394214
It is easy to compute f(x), but computingf -1(y)is infeasible
Discrete exponentiation
Discrete exponentiation: h(x):= gx mod p
- Discrete Logarithm Problem (DLP): givenyfind the logarithm
x so that y = gx mod p.
For a judicious choices of parameters p and g the DLP is difficult to solve and discrete exponentiation is a one-way function.
Discrete exponentiation is a useful primitive in the construction of cryptographic schemes but it is too slow for many applications.
trapdoor functions
A trapdoor one-way function is a one-way function f where, given extra information (the trapdoor information) it is feasible to computef -1:
Given y ∈ Img(f), find an x ∈ X such that f(x) = y
Example 1:
- Select primes p = 48611 and q = 53993
- Let n = pq = 2624653723 and X = {1,…,n-1}
- Definef:X→Nasf(x)=x3 mod n
- f(2489991) = 1981394214 (computing f is easy…)
Computing modular cube roots (f-1) is also easy if p and q are known (basic number theory)
Example 2:
- *Factoring of large numbers (RSA):** Every positive integer N has a unique prime factorization, but it is hard to find.
- *(Remark: checking if N is prime is (likely) easier.)**
RSA fundamentals
- A prime number is an integer p > 1 whose only factors are 1 and p
- Two natural numbers n and m are relatively prime if n and m have no common factor greater than 1; written: gcd(n,m)=1
- For any natural number n, theEuler functionφ(n), is the number of positive integers less than n that are relatively prime to n
Example: φ(10) = 4 since 1, 3, 7, 9 are relatively prime to 10
1. For p a prime, φ(p) = p-1
- 2. Forp,qprimes,φ(p⋅q)=φ**(p)**⋅φ**(q*)
- *(see any textbook on number theory for a proof)**
3. φ (p⋅ q)=(p-1) ⋅ (q-1)
RSA
1. Choose large primes p and q
2. Let n = p ⋅ q
3. Choose a random encryptionexponent e such that 1 < e < φ(n), and e is relatively prime to φ(n)
φ(n) = (p-1) * (q-1)
4. Derive the decryption exponent d = e-1modφ(n)dise’s inverse (see Euler)
5. Kp= (n,e) and Ks= (n,d)
RSA System:
RSA System:
eKp(x) =xe modn and dKs(c)=cd modn
Consider:
- e* ⋅ d = 1 mod φ(n)
- =* k⋅φ(n)+1 for some k
Then:
x ed mod n
= xk⋅ φ(n)+1mod n
= x⋅xk⋅φ(n) modn
= x ⋅ 1 mod n
= x
RSA summary
Public and private keys (e,n) and (d,n) are derived from two secret prime numbers
- Keys are today typically 2048 Bits
Plaintext message is treated as a (large!) binary number
Encryption is exponentiation
- c = xe mod n
To break the encryption, one must be able to factor large numbers
- Hopefully not in P…
Decrpytion uses the trapdoor information d:
- m = cd mod n
RSA: examples of real life pitfalls 1
RSA encryption: c = xe mod n
Plaintext: encoded as a natural number x < n
Simple encoding of short plain text as (very) small x
- Possibility of a brute-force search for x
- In case of using a small e (such as e=3): if xe < n, then invers is simply e√x
RSA: examples of real life pitfalls 2
RSA encryption: c = xe mod n
Assume that x is 64 bit session key: 0 < x < 264
- Attacker sees c
- Assume that x = x1 * x2 with x1,x2<234 (prob. approx. 20%)
- This means that c/x1e = x2e (mod n)
• Build table c/1e, c/2e, .. 2/234 e (234 operations)
for x2 = 0, …, 234 test if x2e is in table (34 * 234 operations)
• Total attack time << 264
RSA encryption is homomorphic:
• RSA(m1 m2) = RSA(m1) RSA(m2) (mod n)
Chosen ciphertext attack to learn cipher text cm = RSA(m) for some random m
- Assume that oracle decrypts any c ≠ cm for the attacker
- Attacker may:
- Encrypt cr = RSA(r) for some arbitrary r
- Calculate c = cmcr
- Ask oracle to decrypt c (resulting in value of m*r)
- Calculate m = m*r * r-1
Elliptic curves cryptosystems
- Analogs of existing public-key cryptosystems in which modular arithmetic is replaced by operations defined over elliptic curves
- the security of elliptic curve cryptosystems relies on the underlying hard mathematical problems: Given two points G and Y on an elliptic curve such that
Y = kG (that is, Y is G added k times to itself), find the integer k.
(This problem is known as the elliptic curve discrete logarithm problem)
Elliptic curves for cryptography
- Elliptic curve over finite field is a finite set of points
- There is a (complicated) definition of an “addition” operation on these points
- You can define an “integer multiplication” for points (2*P=P+P, 3*P=P+P+P, etc.)
- Elliptic curve discrete logarithm problem: given P and k*P, it is difficult to find k
Cryptographic algorithms based on the discrete logarithm problem can be transformed into elliptic curve algorithms
PKI Trade offs
Public Key systems are computationally more expensive than symmetric systems
- Algorithms are harder to implement
- More powerful computers requ’d
There is a formal rationale of security
- based on results of complexity theory
A principal needs one private key and one public key
- n parties need O(n) keys to communicate (compare to symmetric systems…)
Digital Signatures
Protect authenticity of documents ‘signed by A’.
More precisely, a cryptographic mechanism for associating
documents with verification keys
A has a public verification key and a private signature key
A procedure is required for B to get an authentic copy of A’s public key
A has to protect the signature key and be sure that the key is only used as intended
Encryption with public key
Digital Signature
