Geometry in Cryptography

Geometry in Cryptography

Luca Giuzzi

Summer School

Giuseppe Tallini

Cryptosystems • M set of messages • K set of keys • C set of cyphertexts • e : M _{× K 7→ C} encryption • d : C _{× K 7→ M} decryption ∀k ∈ K : ∃k0 ∈ K such that ∀m ∈ M :d(e(m, k), k0) = m.

Discrete Logarithm Problem • G = hgi group • m ∈ G Determine α _∈ N _{such that} m = gα

ElGamal cryptosystem/1 Common elements: • G: cyclic group; • g ∈ G, generator of _G. Secret key: • α ∈ N_. Public key: • gα ∈ G.

ElGamal cryptosystem/2

Encoding:

• M ∈ G message to be transmitted;

• the sender computes a random k _∈ N_;

• the sender transmits the pair

(e, f ) = (gk, M (gα)k) = (gk, M gkα). Decoding:

• the receiver computes

d = eα = gkα;

ElGamal cryptosystem/3

Requirements on _G:

• There is an efficient implementation of the group operation:

(x, α) 7→ xα; _{(M, x) 7→ Mx;}

• There is an efficient implementation of in-version:

d _{7→ d}−1;

• The Discrete Logarithm Problem is hard to solve in _G.

Massey–Omura cryptosystem/1

Common elements:

• G: Abelian group.

Secret key:

• eA ∈ N with gcd(e, |G|) = 1;

• dA ∈ N such that eAdA ≡ 1 (mod |G|).

Massey–Omura cryptosystem/2

Operation:

• P ∈ G: message to be sent from to
.

1. A computes and sends

P0 = PeA_;

2. B computes and sends back

P00 = P0eB = PeAeB_;

3. A computes and sends back

P000 = P00dA _{= P}eAdAeB _{= P}eB

4. B recovers

Massey–Omura cryptosystem/3

Requirements on _G:

• The order of _G is known;

• There is an efficient implementation of the exponentiation in _G:

(x, α) 7→ xα;

• The Discrete Logarithm Problem is hard to solve in _G.

Exponentiation in groups Given: • G group • g ∈ G • α ∈ N Determine: gα. Trivial approach: gα _{= g · · · g} | {z } α times .

Square and multiply

1. If α = 0, then return 1;

2. If α = 1, then return g;

3. If α = 2k, then compute h = g2 and return hk;

4. If α = 2k + 1, then compute h = g2 and return

Elliptic curves/1

• Elliptic curve over K_:

(birationally equivalnent to) non–singular cubic

with at least one point

y2 + ay = x3 + bx2 + cxy + dx + e.

• If charK _{6= 2, 3,}

y2 = x3 + ax + b or (equivalent)

Elliptic curves/2

Elliptic curve over GF(2n):

• non–supersingular

y2 + xy = x2 + ax2 + b;

• supersingular (_{2 = p | |C|)}

Elliptic curves/3:group law

PSfrag replacements A B _{−(A + B)}

A + B

Elliptic curves/4:group law

• C elliptic curve;

• O ∈ C fixed point (inflexion);

• Θ(A, B) third intersection of AB with _C.

Elliptic curves/5:group law, associativity PSfrag replacements A B C O R= Θ(C, B) P= Θ(A, B) Q= Θ(O, (A + B) + C) A + B B + C (A + B) + C Claim: _{(B + C) ∈ AQ}.

Elliptic curves/6:group law, inversion • O inflexion • P = (x, y) ∈ C • p _{6= 2, 3} P _{7→ −P = (−x, −y);} • p = 2, non–supersingular P _{7→ −P = (x, y + x);} • p = 2, supersingular P _{7→ −P = (x, y + c)}

Elliptic curves/7:group law, duplication, p _{6= 2, 3} • y2 = x3 + ax + b; • P = (x1, y1); • 2P = (x3, y3); • λ = 3x 2 1 + a 2y₁ • x₃ = λ2 _{− x1 − x2}; • y₃ = λ(x_{1 − x3) − y1}.

Elliptic curves/8:group law, sum, p _{6= 2, 3} • y2 = x3 + ax + b; • P = (x1, y1); • Q = (x2, y2); • P + Q = (x3, y3); • λ = y2 − y1 x_{2 − x1} • x₃ = λ2 _{− x1 − x2};

Elliptic curves/9:group law, duplication, non–supersing. • y2 + xy = x3 + ax2 + b, b _{6= 0}; • P = (x1, y1); • 2P = (x3, y3); • µ = x₁ + y1 x₁ • x₃ = µ2 + µ + a • y₃ = x2₁ + (µ + 1)x₃

Elliptic curves/10:group law, sum, non–supersing. • y2 + xy = x2 + ax2 + b, b _{6= 0}; • P = (x1, y1); • Q = (x2, y2); • P + Q = (x3, y3); • κ = y1 + y2 x₁ + x₂; • x₃ = κ2 + κ + x₁ + x₂ + a;

Elliptic curves/11:group law, duplication, super-sing. • y2 + cx = x3 + ax + b, c _{6= 0}; • P = (x1, y1); • 2P = (x3, y3); • η = x 2 1 + a c • x₃ = η2 • y₃ = η(x₁ + x₃) + y₁ + c

Elliptic curves/12:group law, sum, supersing. • y2 + cx = x3 + ax + b, c _{6= 0}; • P = (x1, y1); • Q = (x2, y2); • P + Q = (x3, y3); • κ = y1 + y2 x₁ + x₂; • x₃ = κ2 + κ + x₁ + x₂;

Elliptic curves/13:group order • |C| = q + 1 − t with _{|t| ≤ 2}√q. • K _{= GF(p), p 6= 2, 3:} p + X x_∈K x3 + ax + b p ! , where _p· is the Legendre symbol;

• C non–supersingular, K _{= GF(2}m_): 2m_+1+(−1)Tr(a) X 06=x∈K (−1)Tr(x+bx−2); • C supersingular, K _{= GF(2}m_): 2m_+1+(−1)Tr(c−2b) X x_∈K (−1)Tr[c−2(x3+ax)].

Elliptic curves/14:group structure Either: • C = Z_{n or} • C = Z_n 1 ⊕ Zn2 with n_{2 | n1} and n_{2 | (q − 1).}