Diffie-Hellman Protocol on Elliptic Curves

Elliptic curve Diffie – Hellman protocol ( ECDH ) is a cryptographic protocol that allows two parties with public / private key pairs on elliptic curves to obtain a shared secret key using a communication channel that is not protected from listening ^[1] ^[2] . This secret key can be used both for encryption of further exchange, and for the formation of a new key , which can then be used for subsequent exchange of information using symmetric encryption algorithms. This is a variation of the Diffie-Hellman protocol using elliptical cryptography ^[3] .

Content

Algorithm Description

Suppose there are two subscribers: Alice and Bob . Suppose Alice wants to create a shared secret key with Bob, but the only channel available between them can be eavesdropped by a third party. Initially, a set of parameters ( $(p,a,b,G,n,h)$ ${\ displaystyle (p, a, b, G, n, h)}$ for the general case and $(m,f(x),a,b,G,n,h)$ ${\ displaystyle (m, f (x), a, b, G, n, h)}$ for the characteristic field $2$ ${\ displaystyle 2}$ ) Each side must also have a key pair consisting of a private key $d$ ${\ displaystyle d}$ ( randomly selected integer from the interval $[1,n-1]$ ${\ displaystyle [1, n-1]}$ ) and public key $Q$ ${\ displaystyle Q}$ (Where $Q=d\cdot G$ ${\ displaystyle Q = d \ cdot G}$ Is the result of doing $d$ ${\ displaystyle d}$ times an item sum operation $G$ ${\ displaystyle G}$ ) Let then a pair of Alice’s keys be $(d_{A},Q_{A})$ ${\ displaystyle (d_ {A}, Q_ {A})}$ and a pair of bob $(d_{B},Q_{B})$ ${\ displaystyle (d_ {B}, Q_ {B})}$ . Before executing the protocol, the parties must exchange public keys.

Alice calculates $(x_{k},y_{k})=d_{A}\cdot Q_{B}$ ${\ displaystyle (x_ {k}, y_ {k}) = d_ {A} \ cdot Q_ {B}}$ . Bob is calculating $(x_{k},y_{k})=d_{B}\cdot Q_{A}$ ${\ displaystyle (x_ {k}, y_ {k}) = d_ {B} \ cdot Q_ {A}}$ . Shared Secret - $x_{k}$ ${\ displaystyle x_ {k}}$ (x-coordinate of the resulting point). Most standard ECDH-based protocols use key generation functions to obtain a symmetric key from a value $x_{k}$ ${\ displaystyle x_ {k}}$ ^[4] ^[5] .

The values calculated by the participants are equal, since $d_{A}\cdot Q_{B}=d_{A}\cdot d_{B}\cdot G=d_{B}\cdot d_{A}\cdot G=d_{B}\cdot Q_{A}$ ${\ displaystyle d_ {A} \ cdot Q_ {B} = d_ {A} \ cdot d_ {B} \ cdot G = d_ {B} \ cdot d_ {A} \ cdot G = d_ {B} \ cdot Q_ { A}}$ . Of all the information associated with her private key, Alice reports only her public key. Thus, no one except Alice can determine her private key, except for a participant who can solve the problem of discrete logarithm on an elliptic curve . Bob's private key is likewise protected. No one, except Alice or Bob, can calculate their common secret, except for a participant who can solve the Diffie – Hellman problem ^[6] .

Public keys are either static (and confirmed by a certificate) or ephemeral (abbreviated ECDHE). Ephemeral keys are used temporarily and do not necessarily authenticate the sender, so if authentication is required, authentication must be obtained in another way ^[3] . Authentication is necessary to eliminate the possibility of an intermediary attack . If Alice or Bob use a static key, the danger of an intermediary attack is excluded, but neither direct secrecy nor resistance to spoofing when a key is compromised can be ensured, as well as some other attack resistance properties. Users of static private keys are forced to check someone else's public key and use the key generation function for a shared secret to prevent leakage of information about the statically private key ^[7] . For encryption with other properties, the MQV protocol is often used.

When using a shared secret as a key, it is often desirable to hash a secret in order to get rid of vulnerabilities that arose after applying the protocol ^[7] .

Example ^[8]

Elliptic curve E over the field $GF(2^{163})$ ${\ displaystyle GF (2 ^ {163})}$ has order $2\cdot P49$ ${\ displaystyle 2 \ cdot P49}$ where P49 is a prime number consisting of 49 digits in decimal notation.

E:\quad Y^{2}+XY=X^{3}+X^{2}+1

{\ displaystyle E: \ quad Y ^ {2} + XY = X ^ {3} + X ^ {2} +1}

We choose an irreducible polynomial

1+X+X^{2}+X^{8}+X^{163}

{\ displaystyle 1 + X + X ^ {2} + X ^ {8} + X ^ {163}}

And take the point of the elliptic curve

P=(d42149e09429df4563ec1816488c92de89f93a9b2,~ccd18d6cc3042c4c17a213506345c80965ac19476)\neq 0

{\ displaystyle P = (d42149e09429df4563ec1816488c92de89f93a9b2, ~ ccd18d6cc3042c4c17a213506345c80965ac19476) \ neq 0}

.

Check that its order is not equal to 2

2P=(ccd18d6cc3042c4c17a213506345c809b5ac1d476,~835a2f56b88d6a249b4bd2a7550a4375e531d8a37)

{\ displaystyle 2P = (ccd18d6cc3042c4c17a213506345c809b5ac1d476, ~ 835a2f56b88d6a249b4bd2a7550a4375e531d8a37)}

.

So its order is equal to the order of the group $2\cdot P49$ ${\ displaystyle 2 \ cdot P49}$ , namely the number $P49$ ${\ displaystyle P49}$ , and it can be used to build the key. Let be $k_{A}=12$ ${\ displaystyle k_ {A} = 12}$ , $k_{b}=123$ ${\ displaystyle k_ {b} = 123}$ . Then the public keys of the protocol participants are calculated as

k_{A}\cdot P=12\cdot P=(bd9776bbe87a8b1024be2e415952f527eee928b43,~c67a28ed7b137e756c37654f186a71bf64e5ac546)

{\ displaystyle k_ {A} \ cdot P = 12 \ cdot P = (bd9776bbe87a8b1024be2e415952f527eee928b43, ~ c67a28ed7b137e756c37654f186a71bf64e5ac546)}

.

k_{B}\cdot P=123\cdot P=(a5684e246044fc126e9832d17513387e474290547,~568b4137f09f5f79a8a6b0fe44cdf41d8e68ae2c6)

{\ displaystyle k_ {B} \ cdot P = 123 \ cdot P = (a5684e246044fc126e9832d17513387e474290547, ~ 568b4137f09f5f79a8a6b0fe44cdf41d8e68ae2c6)}

.

A common secret will be equal to:

k_{B}\cdot k_{A}\cdot P=k_{A}\cdot k_{B}\cdot P=12\cdot 123\cdot P=(bb7856cece13c71919534878bcb6f3a887d613c92,~f661ffdfe1ba8cb1b2ad17b6550c65aa6d4f07f41)

{\ displaystyle k_ {B} \ cdot k_ {A} \ cdot P = k_ {A} \ cdot k_ {B} \ cdot P = 12 \ cdot 123 \ cdot P = (bb7856cece13c71919534878bcb6f3a887d613c92, ~ f661ffbffbdb1651fdbbfad

.

The value (or part of it) is used as the key to the symmetric system $x=bb7856cece13c71919534878bcb6f3a887d613c92$ ${\ displaystyle x = bb7856cece13c71919534878bcb6f3a887d613c92}$ .

Software

Curve25519 is a set of elliptical parameters and references implemented by Daniel J. Bernstein in C language.

Notes

↑ An Efficient Protocol for Authenticated Key Agreement, 2003 , p. 119.
↑ Barker et al., 2013 , p. eleven.
↑ ¹ ² Suite B Implementer's Guide to NIST SP 800-56A, 2009 , p. eight.
↑ SEC 1: Elliptic Curve Cryptography, 2009 , p. 63.
↑ Barker et al., 2013 , p. 40.
↑ Barker et al., 2013 , p. 20.
↑ ¹ ² SEC 1: Elliptic Curve Cryptography, 2009 , p. thirty.
↑ An elementary introduction to elliptical cryptography. Elliptic Curve Cryptography Protocols, 2006 , p. 85.

Literature

Elaine Barker, Lily Chen, Allen Roginsky, Miles Smid. Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography // http://nvlpubs.nist.gov/ . - National Institute of Standards and Technology, 2013. - ISBN 1495447502 .
Standards for Efficient Cryptography Group (SECG). SEC 1: Elliptic Curve Cryptography : [ eng. ] . - http://www.secg.org . - Certicom Corp, 2009. - P. 15-28, 56-58.
National Institute of Standards and Technology (NIST). Suite B Implementer's Guide to NIST SP 800-56A : [ eng. ] . - https://www.nsa.gov . - 2009.
Laurie Law. An Efficient Protocol for Authenticated Key Agreement: [ eng. ] / Laurie Law, Alfred Menezes , Minghua Qu ... [et al. ] . - Designs, Codes and Cryptography. - Kluwer Academic Publishers, 2003. - Vol. 28, no. 2. - P. 119–134. - ISSN 0925-1022 . - DOI : 10.1023 / A: 1022595222606 .
Bolotov A. A. , Gashkov S. B. , Frolov A. B. Chapter 2. Protocols on elliptic curves // Elementary introduction to elliptic cryptography. Cryptography protocols on elliptic curves. - M .: KomKniga, 2006 .-- S. 83-86. - ISBN 5-484-00444-6 , BBK 32.81, UDC 512.8.

[_aaf8291034dc1e98-1] An Efficient Protocol for Authenticated Key Agreement, 2003 , p. 119.

[_80e1f4bc835b9eb4-2] Barker et al., 2013 , p. eleven.

[_652192779e14020d-3] ¹ ² Suite B Implementer's Guide to NIST SP 800-56A, 2009 , p. eight.

[_285878425f2b3ac6-4] SEC 1: Elliptic Curve Cryptography, 2009 , p. 63.

[_80e1efbc835b9636-5] Barker et al., 2013 , p. 40.

[_80e1f1bc835b995c-6] Barker et al., 2013 , p. 20.

[_285873425f2b3246-7] ¹ ² SEC 1: Elliptic Curve Cryptography, 2009 , p. thirty.

[_c85fa0c98c8751e7-8] An elementary introduction to elliptical cryptography. Elliptic Curve Cryptography Protocols, 2006 , p. 85.

Diffie-Hellman Protocol on Elliptic Curves

Content

Algorithm Description

Example ^[8]

Software

See also

Notes

Literature

More articles:

Diffie-Hellman Protocol on Elliptic Curves

Content

Algorithm Description

Example [8]

Software

See also

Notes

Literature

More articles:

Example ^[8]