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
Electronic Signature vs Digital Signature
Digital signature: mathematical evidence linking a document to a public key
Electronic signatures: a security service for associating documents with legal persons
- the link between a public key and a person has to be established by procedural means
- This link can be recorded in a certificate
Certificates are not necessary for verifying digital signatures, verification keys are
Digital signature misconceptions
Verification is decryption with the public key (as stated in X.509)
- the output of ‘decrypt’ is of type ‘message’, the output of ‘verify’ is of type Boolean, …
A signature binds the signer A to the document
- verification links document and verification key
Digital signatures are legally binding
- even if recognized by law, digital signatures do not guarantee that there is a court with jurisdiction
Non-repudiation
Non-repudiation: a technical term introduced to distinguish digital signatures from symmetric key authentication services (MAC), where the verifier has the key for generating the MAC
Calling digital signatures “irrefutable evidence” creates the erroneous impression that they cannot be repudiated in court
The legal system does not have the concept of “irrefutable evidence”
Certificates
Today: a certificate is a signed document binding a subject (or “entity”) to other information; subjects can be people, keys, names,…
Certification Authorities
- Certificates are signed by an Issuer
- Certification Authority (CA) is just another name for Issuer
- Sometimes CA is used more narrowly for organizations issuing ID certificates
- The application determines the technical and procedural ‘trust’ requirements a CA has to meet
- Sometimes Trusted Third Party (TTP) is used as a synonym for CA
