CYG Chapter 8 Public Key Cryptography

1. Idea of public key based on paper by Diffie and Hellman in 1976

2. Original idea in paper by James Ellis in 1970 but not published due to nondisclosure interests of the British secret service // Author died one month before paper was actually published

1. All users use same en- and decryption function e and d

2. Each user has a pair of keys (K,L) with d(e(M,K),L)=M and K public, L private

1. Computing C=e(M,K) must be computationally easy

2. Computing M=d(C,L) must be computationally easy

3. Generating (K,L) must be computationally easy

4. Finding M without L must be infeasible

5. There exist sufficiently many pairs (K,L) in order to prevent exhaustive key search

1. First cs implementing above idea by Rivest, Shamir and Adleman in 1978

2. Also the idea was invented earlier but not published until 1997 by the British secret service

1. Choose two large prime numbers p!=q and n=p*q and phi(n)=(p-1)(q-1)

2. Choose d in Z_phi(n)* and compute e=d^-1 mod phi(n)

3. Public key is (e,n) and private key d

4. Encryption is c=m^e mod n

5. Decryption is b=c^d mod n

1. Let p!=q be prime and x,y in N

2. x equiv y (mod p) and x equiv y (mod q) ↔ x equiv y (mod p*q)

p and q|x-y ↔ p*q|x-y (since p and q are relatively prime)

Correctness of RSA

1. Let p!=q be prime, n=p*q, d,d^-1 in Z_phi(n)* and 0<=m<n, c=m^{d^-1} mod n

2. m=c^d mod n

1. From dd^-1 equiv 1 (mod phi(n)) we can follow that dd^-1=t*phi(n)+1

2. Case gcd(m,p)=1: c^d equiv (m^{d^-1})^d equiv m^t*phi(n)+1 equiv 1^t(q-1) m (mod p) // With Fermat’s little theorem

3. Case gcd(m,p)=p: (m^{d^-1})^d equiv 0 equiv m (mod p) // Analog for (mod q)

CP is most relevant attack against RSA

1. Factoring of n into p and q // Actually infeasible

2. Allows to compute phi(n) and d=e^-1 (mod phi(n)) // With extended euclidean algorithm

1. Computation of square roots modulo n allows factoring n

2. If x² equiv 1 (mod n) a non-trivial solution with x != ±1 (mod n) then gcd(x+1,n) in {p,q}

1. Compute phi(n) without factoring

2. Derive (1) p+q = n-phi(n)+1, (2) (p-q)² = (p+q)²-4n and (3) q = ½((p+q)-(p-q))

3. Compute q and thus p

4. Not easier than factoring, otherwise we would have an efficient algorithm for it

1. Computing d=e^-1 without knowing phi(n)

2. Not easier than factoring, otherwise we would have an efficient algorithm for it

1. Introduced by Paul Kocher in 1996

2. Investigate physical quantities as time or power consumption

1. Key generation with MRPT

2. Choice of d in Z_phi(n)* by incrementing some d₀ until gcd(d₀,phi(n))=1 or choose d prime greater than p,q

3. Compute inverse e=d^-1 mod phi(n) with extended euclidean algorithm

4. En- and decryption by use of the square and multiply algorithm

5. Hardware can be looked up in a list

1. Verifiable

2. Forgery-proof

3. Firmly connected to the document

1. A generates by s=m^d mod n

2. B computes m’=s^e mod n and compares m’ with m

1. O cannot use own ~m

2. O cannot generate own signatures as d is private

3. O can generate q with valid signature s but meaningless with high probability

1. In each procedure a session key k is chosen mapping the same pt to different ct

2. Related to Diffie-Hellman protocol

3. Decryption of ElGamal without knowing private key x is equivalent to DHP

1. Public domain parameters are prime p and a pem p

2. Private key x in [2,…,p-2]

3. Public key y = a^x mod p

4. Encryption C=(C₁,C₂)=e(m,…)

5. Decryption m=d(C,…)

1. k is randomly secretly chosen in [1,…,p-1]

2. K = y^k mod p

3. C₁=a^k mod p and C₂=K*m mod p

1. C₁^x mod p = K

2. m = K^-1C₂ mod p

1. Works on any cyclic group

2. Security is based on the intradictability of the dl

1. Z_p* with p prime

2. F_2^m* the multiplicative group of the finite field F_2^m

3. Group of points of an elliptic curve

4. F_p^m* the multiplicative group of F_p^m

1. Public domain parameters are cyclic group G or order n and a pe

2. Private key x in [1,…,n-1]

3. Public key a, description of G and y = a^x in G

4. Encryption C=(C₁,C₂)=e(m,…)

5. Decryption m=d(C,…)

1. k is randomly secretly chosen in [1,…,n-1]

2. K = y^k mod p

3. C₁=a^k and C₂=K*m in G

1. C₁^x = K

2. m = K^-1C₂

Pervasive security infrastructure with public-key concepts

1. Certificate issuance // Trusted/certification authorities

2. Certificate revocation // Recognize revoked certificates

3. Key backup, recovery, update // See banking, computer systems

4. Time stamping // Fixed length validity periods

1. Secure communication // PGP, SSL, VPN

2. Access control // Privilege management

3. Privacy architecture // Anonymous certificates, web browsing

1. Client may not even have a public key or a certificate

2. How to accept the identity of a party that you never met?

3. Conventional via trusted third party // A friend and here the CA

1. CA gives relation between public key and identity of a party

2. CA maintains a blacklist of canceled certificates

3. Certificate is transmitted signed to a receiver

4. Receiver does not necessarily communicate with CA and just reads published certificates from sender

1. CA name

2. Sequential number

3. Public key of user

4. Identity of user

5. Issuing date

6. Expiration date

7. Signature of CA on all above

1. User itself is a CA

2. Select which CA to trust

1. Trust any CA unconditionally

2. Trust CA only conditionally // Amount of certificates

3. Design own certificate trust scheme