<div dir="auto"><div dir="auto" style="font-family:sans-serif;font-size:12.8px">[Cross Posted to <a href="mailto:curves@moderncrypto.org" style="text-decoration-line:none;color:rgb(66,133,244)">curves@moderncrypto.org</a>]</div><span style="font-size:12.8px;font-family:sans-serif"><div dir="auto"><br></div>I'd like to announce a complete signature system based off a Granger Moss Prime:</span><div dir="auto" style="font-size:12.8px;font-family:sans-serif">P11_260.</div><div dir="auto" style="font-size:12.8px;font-family:sans-serif">The primes is 260 bits, and is equal to t^11/(t - 1) for t = 2^26 - 15.</div><div dir="auto" style="font-size:12.8px;font-family:sans-serif">p is congruent to 3 mod 4 for cheap square roots.</div><div dir="auto" style="font-size:12.8px;font-family:sans-serif"><br></div><div dir="auto" style="font-size:12.8px;font-family:sans-serif">The curve is an edwards curve with d = -49142, and is the smallest such d with cofactor 4 and twist cofactor 4.</div><div dir="auto" style="font-size:12.8px;font-family:sans-serif">All of the safe curves tests pass.</div><div dir="auto" style="font-size:12.8px;font-family:sans-serif"><br></div><div dir="auto" style="font-size:12.8px;font-family:sans-serif">I currently have key generation running in 66928 cycles on haswell, and signing of 59 bytes in 70618 cycles. Verification is 248108 cycles. Verification could be sped up by using NAF instead of fixed sized windows. All of those measurements were made with supercop, HT and turbo off, with cset shield and are the median readings of 32 runs.</div><div dir="auto" style="font-size:12.8px;font-family:sans-serif"><br></div><div dir="auto" style="font-size:12.8px;font-family:sans-serif">For both signing and generation, </div><div dir="auto" style="font-size:12.8px;font-family:sans-serif"><br></div><div dir="auto" style="font-size:12.8px;font-family:sans-serif">The code is implemented for AVX2, as well as a reference implementation that is slow, but provides a comparison point and is easier to follow.</div><div dir="auto" style="font-size:12.8px;font-family:sans-serif"><br></div><div dir="auto" style="font-size:12.8px;font-family:sans-serif">The code is available here:</div><div dir="auto" style="font-size:12.8px;font-family:sans-serif"><a href="https://github.com/iteratee/p11_260" style="text-decoration-line:none;color:rgb(66,133,244)">https://github.com/iteratee/p11_260</a><br></div><div dir="auto" style="font-size:12.8px;font-family:sans-serif"><br></div><div dir="auto" style="font-size:12.8px;font-family:sans-serif">The signature system is similar to EdDSA, with 2 deviations:</div><div dir="auto" style="font-size:12.8px;font-family:sans-serif">The keys are not washed (setting the high bits), so that they form a group. If you use signed-all-bits-set, you don't have to worry about stopping early, because there are no zeroes.</div><div dir="auto" style="font-size:12.8px;font-family:sans-serif">Also, we don't clear the low bits. For signatures, this isn't necessary.</div><div dir="auto" style="font-size:12.8px;font-family:sans-serif"><br></div><div dir="auto" style="font-size:12.8px;font-family:sans-serif">Another deviation is session key derivation. Session key derivation uses entropy, and also hashing. This helps avoid both weak-entropy attacks and fault attacks.</div><div dir="auto" style="font-size:12.8px;font-family:sans-serif"><br></div><div dir="auto" style="font-size:12.8px;font-family:sans-serif">The signature equation is R = sB + h(R, compress(A), M)A.</div><div dir="auto" style="font-size:12.8px;font-family:sans-serif"><br></div><div dir="auto" style="font-size:12.8px;font-family:sans-serif">To facilitate simpler encoding and decoding, points on the curve are encoded not as 260-bits mod p, but as 10 26-bit coefficients mod t. This doesn't change the space requirements, and points never leave this domain.</div><div dir="auto" style="font-size:12.8px;font-family:sans-serif"><br></div><div dir="auto" style="font-size:12.8px;font-family:sans-serif">The code could be adapted to other Granger-Moss primes with little difficulty. The same multiplication routine and similar reduction routines would work up to 290 bits (t ~= 2^29).</div><div dir="auto" style="font-size:12.8px;font-family:sans-serif"><br></div><div dir="auto" style="font-size:12.8px;font-family:sans-serif">Signing and Key Generation spend over 1/3 of their time in inversion. I suspect that due to the unaligned loads, there are some pipeline stalls that can't be fixed with vector register forwarding. There are still places that I could squeeze, but I'm fairly happy with the way things are shaping up, and thought that the work was at a point it was worth sharing.</div><div dir="auto" style="font-size:12.8px;font-family:sans-serif"><br></div><div dir="auto" style="font-size:12.8px;font-family:sans-serif">Hopefully you find something interesting here,</div><div dir="auto" style="font-size:12.8px;font-family:sans-serif">Kyle.</div></div>