Elliptic Curve DSA
The Elliptic Curve Digital Signature Algorithm ( ECDSA ) is a variant of the Digital Signature Algorithm ( DSA), which uses elliptic curve cryptography.
- 5.1 Open Source
Differences to the normal DSA method
The general rule in the Elliptic Curve Cryptography the rule of thumb that the bit length of the generator of the subgroup used should correspond to about twice the level of safety. At a confidence level of bits, in which an attacker must perform elementary operations in order to find the private key could have been a DSA key has a length of approximately 1024 bits, an ECDSA key but only a length of 160 bits. A signature is, however, in both methods the same length: bits, ie 320 bits for a security level of 80 bits.
Algorithm for generating a signature
Alice wants to sign a signed message to Bob. At the beginning you have to agree on the curve parameters. The first parameter describing the curve used: is the order of the body on which the curve is defined; is an indication of the basis used; and two body elements which describe the equation of the curve; is a possible, randomly generated string that is present, if the curve was shown to randomly generated. Furthermore, are required:
- Is a fixed generator of the torsion subgroup, the curve (i.e., );
- , The order of the point, and the cofactor (equal to the order of the curve divided by the group order );
- , The bit length of the group order;
- A cryptographic hash function HASH, such as SHA -2.
Alice must be in possession of an appropriate key pair, consisting of a secret key ( a random integer in the interval) and the corresponding public key ().
If Alice wants to sign the message, it proceeds as follows:
When calculated, the value comes from, be converted to an integer should. It should be noted that greater than can be, but not longer.
It is crucial that different values are used for different signatures, otherwise the equation in step 4 can be solved for the secret key: For two signatures and the same, unknown, various known news and sign, an attacker can calculate and. Because equivalent (all the operations in this paragraph shall be performed with modulo ), then it can also be calculated. For, because of the attacker also calculate the private key. This error in the encryption was used, for example, to calculate the encryption in the game console PlayStation 3, and thus overturn the copy protection.
Verification of a signature
If Bob wants to verify the authenticity of a signature generated by Alice, he must have a copy of their public key. If he is not sure that has been properly generated, it has to check if it really is a key ( the neutral element is denoted by ):
Then Bob performs the following steps:
Using Straus's algorithm ( also known as Shamir 's trick ), the sum of two scalar multiplications ( ) can be computed faster.
Norms and Standards
ANSI
The standard X9.62 -2005 American National Standards Institute is the authoritative specification of ECDSA, which is used by the standards listed below as a reference.
NIST
The U.S. National Institute of Standards and Technology recommends 186-3 fifteen elliptic curves in FIPS.
SECG
The "Standards for Efficient Cryptography Group" ( SECG ) is a Consortium founded in 1998 to promote the use of ECC algorithms, which also specifies the ECDSA in SEC1 document.
ISO / IEC
The International Organization for Standardization and the International Electrotechnical Commission defined ECDSA in International Standard 14888-3 ( the older standard 15946-2 has been retired in 2007 ). In the standard 14888-3 and a supplement (Amendment 1), in addition to EC- DSA ( the abbreviation used in the standard ) nor 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 ) specified.
BSI
The Federal Office for Security in Information Technology sets TR- 03111 specifications and recommendations, inter alia, for the implementation of ECDSA in the Technical Guideline.