I wrote an elliptic curve signature system that uses a Granger Moss Prime and has some nice properties:
Yes, I know it is unlikely to be widely adopted. There were several reasons to write a signature system.
perf tool.The signature system is based on scalar multiplication of points on an elliptic curve over a prime field. The prime is (t11−1)/(t−1) where t = 226 − 15. This prime is congruent to 3 mod 4 for fast square roots. Approximate division by t is straightforward: $q = z >> 2^26; r = t & (2^26 - 1) + 15 ⋅ q$.
The curve is an edwards curve, defined as: x2 + y2 = dx2y2, d = − 49142 This is the smallest such d that yields a curve with cofactor 4. Thanks to the team at safecurves.cr.yp.to I was able to use sage and numerical sieves to construct proofs of safety for the curve.
The software uses a signed-all-bits-set representation for speedups and to avoid timing attacks by early termination. In signed-all-bits-set representation, a number is represented in binary, but each bit is ± 1. To convert a b bit number to this representation mod l, you do the following: First write the number e = sum(i=0 to b,2idi), di ∈ −1, 1. Then we can modify the equation. (e+2b−1)/2 = sum(i=0 to b,2i(di+1)/2). So given a binary number e, if we want its digits in SABS representation, we compute (e+2b−1)/2. Since the scalars that we are concerned about form a prime field, we can always divide by 2.
To Sign:
There is a well known point B. The signing key is a pair: A, a where A = a * B, and a is a scalar, the secret key. Choose a session key k. then compute the point R = kB. Use blake2b512 to produce a 512 bit value h = Hash(R,A,M), where A is the compressed public key. Compute s = k − ha. The signature is the pair R, s where R is compressed.
To Verify: Compute h = Hash(R,A,M). Check that sB + hA = R. This can be done without decompressing R. We can verify the check equation: sB + hA = (k−ha) ⋅ B + ha ⋅ B = k ⋅ B = R.
This particular system was chosen based on guidance from Dan Bernstein and Tanja Lange
The signature algorithm uses 4 5-bit combs with teeth separation of 13 bits. Combs are straightforward once you see what they are doing. The first table contains 16 entries:
| index | contents |
|---|---|
| 0 | B ⋅ 252 − B ⋅ 239 − B ⋅ 226 − B ⋅ 213 − B ⋅ 20 |
| 1 | B ⋅ 252 − B ⋅ 239 − B ⋅ 226 − B ⋅ 213 + B ⋅ 20 |
| … | … |
| 15 | B ⋅ 252 + B ⋅ 239 + B ⋅ 226 + B ⋅ 213 + B ⋅ 20 |
We only need 16 entries because we can use the 5th bit as a sign bit. The next comb is constructed in a similar manner, starting with B ⋅ 265. To multiply B by a scalar, we start with acc equal to the identity and do the following 13 times:
You always use a comb when signing, because B is known. You can use it in half of the verification, because you compute sB, and again B is known. If you need to verify several signatures from the same key, in can be effective to compute a comb for a known public key A to speed up the computation of hA.
At the very end of the article by DJB and Tanja Lange, there is a discussion of what to use to derive the session key. The article argues that using the message and the private key to generate the session key is best because it is stateless and simple, and there is no security to be gained by including randomness in the generation. This analysis misses a specific kind of attack: A fault attack. In this system, the message is hashed twice, once to generate the session key, k and then again to produce h. If an attacker can cause the document to be different for the second hashing, they can produce multiple signatures with the same session key, breaking the private key. If, however, the random number hardware is working, and you include a random value in the session key hash, then the fault attack won’t work.