Elliptic Curve DSA

The Elliptic Curve Digital Signature Algorithm ( ECDSA ) is a variant of the Digital Signature Algorithm (DSA) that uses elliptic curve cryptography .

Differences to the normal DSA procedure

In general, with elliptic curve cryptography, the rule of thumb is that the bit length of the generator of the subgroup used should be about twice the security  level. At a security level of bits, at which an attacker would have to perform elementary operations to find the private key, a DSA key would have a length of around 1024 bits, while an ECDSA key would only be 160 bits. However, a signature is the same length for both methods: Bit, i.e. 320 bits for a security level of 80 bits. ${\displaystyle t}$ ${\displaystyle t=80}$ ${\displaystyle 2^{80}}$ ${\displaystyle 4t}$

Key generation

Alice wants to write a signed message to Bob . At the beginning you have to agree on the curve parameters . The first parameters describe the curve used: is the order of the body on which the curve is defined; is the indication of the base used; and are two body elements that describe the equation of the curve; is a possible, randomly generated character string that is present if the curve was demonstrably generated randomly. You also need: ${\displaystyle (q,FR,a,b,DomainParameterSeed,G,n,h)}$ ${\displaystyle q}$ ${\displaystyle FR}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle DomainParameterSeed}$

• ${\displaystyle G}$, a fixed generator of the torsion subgroup of the curve (i. e., ); ${\displaystyle n}$ ${\displaystyle G=(x_{G},y_{G})}$
• ${\displaystyle n}$, the order of the point , and , the cofactor (equal to the order of the curve divided by the group order ); ${\displaystyle G}$ ${\displaystyle h}$ ${\displaystyle n}$
• ${\displaystyle L_{n}}$, the bit length of the group order ; ${\displaystyle n}$
• a cryptological hash function HASH, such as B. SHA-2 .

In order to generate her key pair, Alice generates a random integer in the interval as a secret key . The associated public key is . ${\displaystyle d_{A}}$ ${\displaystyle [1,n-1]}$ ${\displaystyle Q_{A}=d_{A}G}$

Algorithm for generating a signature

If Alice wants to sign a message , she does the following: ${\displaystyle m}$

1. Compute and define as the most significant bits of . ${\displaystyle e={\textrm {HASH}}(m)}$ ${\displaystyle z}$ ${\displaystyle L_{n}}$ ${\displaystyle e}$
2. Pick a random integer of . ${\displaystyle k}$ ${\displaystyle [1,n-1]}$
3. Calculate where . If so , go back to step 2. ${\displaystyle r=x_{1}{\pmod {n}}}$ ${\displaystyle (x_{1},y_{1})=kG}$ ${\displaystyle r=0}$
4. Calculate . If so , go back to step 2. ${\displaystyle s=k^{-1}(z+rd_{A}){\pmod {n}}}$ ${\displaystyle s=0}$
5. The signature is the couple . ${\displaystyle (r,s)}$

When calculating, the value that comes from should be converted to an integer. It should be noted that it can be larger than , but not longer . ${\displaystyle s}$ ${\displaystyle z}$ ${\displaystyle {\textrm {HASH}}(m)}$ ${\displaystyle z}$ ${\displaystyle n}$

It is crucial that different values ​​are used for different signatures , otherwise the equation in step 4 can be solved for the secret key : An attacker can calculate and from two signatures and , which sign different known messages and with the same unknown . Because corresponds (all operations in this paragraph are carried out with modulo ) can then also be calculated. The attacker can also calculate the private key from . This error in the encryption was e.g. B. used to calculate the encryption in the PlayStation 3 game console and thus overturn the restriction on officially published software. ${\displaystyle k}$ ${\displaystyle d_{A}}$ ${\displaystyle (r,s)}$ ${\displaystyle (r,s')}$ ${\displaystyle k}$ ${\displaystyle m}$ ${\displaystyle m'}$ ${\displaystyle z}$ ${\displaystyle z'}$ ${\displaystyle s-s'=k^{-1}(z-z')}$ ${\displaystyle n}$ ${\displaystyle k={\frac {z-z'}{s-s'}}}$ ${\displaystyle k}$ ${\displaystyle s=k^{-1}(z+rd_{A})}$ ${\displaystyle d_{A}={\frac {sk-z}{r}}}$

Verification of a signature

If Bob wants to verify the authenticity of a signature created by Alice, he must have a copy of her public key . If he is not sure that it was generated correctly, he must check whether it really is a key (the neutral element is denoted by): ${\displaystyle Q_{A}}$ ${\displaystyle Q_{A}}$ ${\displaystyle O}$

1. Check whether is unequal and that the coordinates are otherwise valid ${\displaystyle Q_{A}}$ ${\displaystyle O}$
2. Check if lies on the curve ${\displaystyle Q_{A}}$
3. Check if . Here it is checked whether it is a multiple of the producer . If the cofactor is in the curve parameters , this step can be omitted. ${\displaystyle nQ_{A}=O}$ ${\displaystyle Q_{A}}$ ${\displaystyle G}$ ${\displaystyle h=1}$

After that, Bob does the following:

1. Check whether and are whole numbers and are in the interval . If it doesn't, the signature is invalid. ${\displaystyle r}$ ${\displaystyle s}$ ${\displaystyle [1,n-1]}$
2. Compute , where HASH is the same function as when generating the signature. Use to denote the most significant bits of . ${\displaystyle e={\textrm {HASH}}(m)}$ ${\displaystyle z}$ ${\displaystyle L_{n}}$ ${\displaystyle e}$
3. Calculate . ${\displaystyle w=s^{-1}{\pmod {n}}}$
4. Calculate and . ${\displaystyle u_{1}=zw{\pmod {n}}}$ ${\displaystyle u_{2}=rw{\pmod {n}}}$
5. Calculate . ${\displaystyle (x_{1},y_{1})=u_{1}G+u_{2}Q_{A}}$
6. The signature is valid if , otherwise it is invalid. ${\displaystyle r=x_{1}{\pmod {n}}}$

Using Straus' algorithm (also known as Shamir 's trick ), the sum of two scalar multiplications ( ) can be calculated more quickly. ${\displaystyle u_{1}G+u_{2}Q_{A}}$

Norms and standards

ANSI

The American National Standards Institute standard X9.62-2005 is the authoritative specification of the ECDSA and is used as a reference by the following standards.

NIST

The US National Institute of Standards and Technology recommends fifteen elliptic curves in the FIPS 186-4 standard.

SECG

The Standards for Efficient Cryptography Group (SECG) is a consortium founded in 1998 to promote the use of ECC algorithms, which in document SEC1 also specifies the ECDSA.

ISO / IEC

The International Organization for Standardization and the International Electrotechnical Commission define ECDSA in the international standard 14888-3 (the older standard 15946-2 was withdrawn in 2007). In standard 14888-3 and a supplement (Amendment 1), in addition to EC-DSA (the abbreviation used in the standard), the variants EC-GDSA (Elliptic Curve German Digital Signature Algorithm), EC-KCDSA (Korean Certificate-based Digital Signature Algorithm ), EC-RDSA (Russian Digital Signature Algorithm), EC-SDSA and EC-FSDSA (Schnorr and Full Schnorr Digital Signature Algorithm).

BSI

In the technical guideline TR-03111, the Federal Office for Information Security lays down requirements and recommendations u. a. for the implementation of the ECDSA.

Implementations

Open source

• OpenSSH : As of version 5.7 (January 24, 2011), ECDSA and the key exchange via Elliptic Curve Diffie-Hellman (ECDH) from RFC 5656 are implemented.
• OpenSSL : Implemented from version 0.9.8 (July 5, 2005).
• BouncyCastle  : From March 10, 2014
• GnuTLS
• .Net Framework from version 3.5

Individual evidence

1. ↑ NIST FIPS 186-4, July 2013, pp. 19 and 26 (PDF; 0.7 MB)
2. ↑ CCC, 27C3, Console Hacking 2010, pages 123–128 ( Memento of the original from December 15, 2014 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. (PDF; 9 MB) 
3. ↑ http://www.lirmm.fr/~imbert/talks/laurent_Asilomar_08.pdf The double base number system in elliptic curve cryptography
4. ↑ [1]  ( Page no longer available , search in web archives )  Info: The link was automatically marked as defective. Please check the link according to the instructions and then remove this notice. On the complexity of certain multi-exponentiation techniques in cryptography  
5. ↑ ANSI X9.62-2005, Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)
6. ↑ NIST: Digital Signature Standard (DSS) . ( nist.gov [PDF]).
7. ↑ http://www.secg.org/ Standards for Efficient Cryptography Group (SECG)
8. ↑ TR-031111: Elliptic Curve Cryptography (ECC)
9. ↑ OpenSSH 5.7 has just been released. OpenBSD, accessed August 19, 2011 . 
10. ↑ OpenSSH 5.7: Faster through the curve. Heise.de, January 25, 2011, accessed on August 19, 2011 . 
11. ↑ https://www.openssl.org/news/changelog.html
12. ↑ Supported Curves (ECDSA and ECGOST) - Java APIs 1.X - The Legion of the Bouncy Castle. Retrieved March 9, 2018 . 
13. ↑ ECDsa Class (System.Security.Cryptography). Accessed March 9, 2018 . 

literature

• Accredited Standards Committee X9 , American National Standard X9.62-2005, Public Key Cryptography for the Financial Services Industry, The Elliptic Curve Digital Signature Algorithm (ECDSA) , November 16, 2005.
• Certicom Research, Standards for efficient cryptography, SEC 1: Elliptic Curve Cryptography (PDF; 970 kB), Version 2.0, May 21, 2009.
• López, J. and Dahab, R. An Overview of Elliptic Curve Cryptography , Technical Report IC-00-10, State University of Campinas, 2000.
• Daniel J. Bernstein, Pippenger's exponentiation algorithm (PDF; 293 kB), 2002.
• Daniel RL Brown, Generic Groups, Collision Resistance, and ECDSA , Designs, Codes and Cryptography, 35 , 119-152, 2005. ePrint version
• Ian F. Blake, Gadiel Seroussi, and Nigel P. Smart, editors, Advances in Elliptic Curve Cryptography , London Mathematical Society Lecture Note Series 317, Cambridge University Press, 2005.
• Darrel Hankerson, Alfred Menezes and Scott Vanstone, Guide to Elliptic Curve Cryptography, Springer , Springer, 2004.

Web links

• Digital signature standard; includes info on ECDSA