Protocol++® (Protocolpp®)  v5.6.2
jecdsafp Class Reference

#include "include/jecdsafp.h"

Detailed Description

Elliptic Curve Digital Signature Algorithm (ECDSA) for Fp

see https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm

In cryptography, the Elliptic Curve Digital Signature Algorithm (ECDSA) offers a variant of the Digital Signature Algorithm (DSA) which uses elliptic curve cryptography

Key and signature-size comparison to DSA

As with elliptic-curve cryptography in general, the bit size of the public key believed to be needed for ECDSA is about twice the size of the security level, in bits. For example, at a security level of 80 bits (meaning an attacker requires a maximum of about $ {2}^{80} $ operations to find the private key) the size of an ECDSA public key would be 160 bits, whereas the size of a DSA public key is at least 1024 bits. On the other hand, the signature size is the same for both DSA and ECDSA: approximately $ 4t$ bits, where $ t$ is the security level measured in bits, that is, about 320 bits for a security level of 80 bits

Signature generation algorithm

Suppose Alice wants to send a signed message to Bob. Initially, they must agree on the curve parameters ( CURVE , G , n ). In addition to the field and equation of the curve, we need G, a base point of prime order on the curve; n is the multiplicative order of the point G

ECDSA Fp Parameters
ParameterDescription
CURVEthe elliptic curve field and equation used
Gelliptic curve base point, such as a pt $(x_0,y_0)$ on $ {y}^{2} = {x}^{3} + 7$, a generator of the elliptic curve with large prime order n
ninteger order of $ G$, means that $ n \times G = O$, where O is the identity element

The order n of the base point G must be prime. Indeed, we assume that every nonzero element of the ring $ \frac{Z}{nZ}$ are invertible, so that $ \frac{Z}{nZ}$ must be a field. It implies that n must be prime (cf. Bézout's identity)

Alice creates a key pair, consisting of a private key integer $ d_A$, randomly selected in the interval $ [ 1 , n - 1 ]$; and a public key curve point $ Q_A = d_A \times G$

We use $ \times$ to denote elliptic curve point multiplication by a scalar

For Alice to sign a message m, she follows these steps:

  • Calculate $ e = HASH(m)$, where $ HASH$ is a cryptographic hash function, such as SHA-2
  • Let $ z$ be the $ L_n$ leftmost bits of $ e$, where $ L_n$ is the bit length of the group order $ n$
  • Select a cryptographically secure random integer k from $ [1 , n - 1]$
  • Calculate the curve point $ (x_1, y_1) = k \times G$
  • Calculate $ r = x_1 mod n$. If $ r = 0$, go back to step 3
  • Calculate $ s = {k}^{-1} ( z + rd_A ) mod n $
  • If $ s = 0$, go back to step 3
  • The signature is the pair $ (r, s)$

When computing $ s$, the string $ z$ resulting from $ HASH(m)$ shall be converted to an integer. Note that $ z$ can be greater than $ n$ but not longer

As the standard notes, it is not only required for k to be secret, but it is also crucial to select different k for different signatures, otherwise the equation in step 6 can be solved for $ d_A$, the private key: Given two signatures $ (r,s)$ and $ (r, {s}^{'})$, employing the same unknown $ k$ for different known messages $ m$ and $ {m}^{'}$, an attacker can calculate $ z$ and $ {z}^{'}$, and since $ s - {s}^{'} = {k}^{-1}(z - {z}^{'})$ (all operations in this paragraph are done modulo n ) the attacker can find $ k = \frac{z - {z}^{'}}{s - {s}^{'}}$. Since $ s = {k}^{-1}(z + rd_A)$, the attacker can now calculate the private key $ d_A = \frac{sk - z}{r}$.

Another way ECDSA signature may leak private keys is when k is generated by a faulty random number generator. To ensure that k is unique for each message one may bypass random number generation completely and generate deterministic signatures by deriving k from both the message and the private key

Signature verification algorithm

For Bob to authenticate Alice's signature, he must have a copy of her public-key curve point $ Q_A$

Bob can verify $ Q_A$ is a valid curve point as follows:

  • Check that $ Q_A$ is not equal to the identity element $ O$, and its coordinates are otherwise valid
  • Check that $ Q_A$ lies on the curve
  • Check that $ n \times Q_A = O$

After that, Bob follows these steps:

  • Verify that $ r$ and $ s$ are integers in $ [1, n - 1]$. If not, the signature is invalid.
  • Calculate $ e = HASH (m)$, where $ HASH$ is the same function used in the signature generation
  • Let $ z$ be the $ L_n$ leftmost bits of $ e$
  • Calculate $ w = {s}^{-1} mod n$
  • Calculate $ u_1 = zw mod n and u_2 = rw mod n$
  • Calculate the curve point $ (x_1, y_1) = u_1 \times G + u_2 \times Q_A$
  • If $ (x_1, y_1) = O$ then the signature is invalid
  • The signature is valid if $ r \equiv x_1 ( mod n )$, invalid otherwise

Note that using Shamir's trick, a sum of two scalar multiplications $ u_1 \times G + u_2 \times Q_A$ can be calculated faster than two scalar multiplications done independently

Concerns

There exist two sorts of concerns with ECDSA:

  • Political concerns: the trustworthiness of NIST-produced curves being questioned after revelations that the NSA willingly inserts backdoors into software, hardware components and published standards were made; well-known cryptographers have expressed doubts about how the NIST curves were designed, and voluntary tainting has already been proved in the past
  • Technical concerns: the difficulty of properly implementing the standard, its slowness, and design flaws which reduce security in insufficiently defensive implementations of the Dual EC DRBG random number generator

For API information:

See also
ProtocolPP::jecdsafp
ProtocolPP::jsecass
ProtocolPP::jprotocol
ProtocolPP::jprotocolpp
ProtocolPP::jenum

For Additional Documentation:

See also
jecdsafp
jsecass
jprotocol
jprotocolpp
jenum
Protocol++® (ProtocolPP®) written by : John Peter Greninger • © John Peter Greninger 2015-2024 • All Rights Reserved
All copyrights and trademarks are the property of their respective owners

The source code contained or described herein and all documents related to the source code (herein called "Material") are owned by John Peter Greninger and Sheila Rocha Greninger. Title to the Material remains with John Peter Greninger and Sheila Rocha Greninger. The Material contains trade secrets and proprietary and confidential information of John Peter Greninger and Sheila Rocha Greninger. The Material is protected by worldwide copyright and trade secret laws and treaty provisions. No part of the Material may be used, copied, reproduced, modified, published, uploaded, posted, transmitted, distributed, or disclosed in any way without prior express written consent of John Peter Greninger and Sheila Rocha Greninger (both are required)

No license under any patent, copyright, trade secret, or other intellectual property right is granted to or conferred upon you by disclosure or delivery of the Materials, either expressly, by implication, inducement, estoppel, or otherwise. Any license under such intellectual property rights must be express and approved by John Peter Greninger and Sheila Rocha Greninger in writing

Licensing information can be found at www.protocolpp.com/license with use of the binary forms permitted provided that the following conditions are met:

  • Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution
  • Any and all modifications must be returned to John Peter Greninger at GitHub.com https://github.com/jpgreninger/protocolpp for evaluation. Inclusion of modifications in the source code shall be determined solely by John Peter Greninger. Failure to provide modifications shall render this license NULL and VOID and revoke any rights to use of Protocol++®
  • Commercial use (incidental or not) requires a fee-based license obtainable at www.protocolpp.com/shop
  • Academic or research use requires prior written and notarized permission from John Peter and Sheila Rocha Greninger

Use of the source code requires purchase of the source code. Source code can be purchased at www.protocolpp.com/shop

  • US Copyrights at https://www.copyright.gov/
    • TXu002059872 (Version 1.0.0)
    • TXu002066632 (Version 1.2.7)
    • TXu002082674 (Version 1.4.0)
    • TXu002097880 (Version 2.0.0)
    • TXu002169236 (Version 3.0.1)
    • TXu002182417 (Version 4.0.0)
    • TXu002219402 (Version 5.0.0)
    • TXu002272076 (Version 5.2.1)
    • TXu002383571 (Version 5.4.3)

The name of its contributor may not be used to endorse or promote products derived from this software without specific prior written permission and licensing

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER AND CONTRIBUTOR "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE

The documentation for this class was generated from the following file: