/* Copyright (c) 2009-2010 Christopher A. Taylor. All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. * 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. * Neither the name of LibCat nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "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 HOLDER 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. */ /* Addition and doubling formulas using Extended Twisted Edwards coordinates from Hisil–Wong–Carter–Dawson paper "Twisted Edwards Curves Revisited" (Asiacrypt 2008) w-MOF scalar multiplication from http://www.sdl.hitachi.co.jp/crypto/mof/index-e.html Scalar multiplication precomputation with "conjugate addition" inspired by Longa-Gebotys paper "Novel Precomputation Schemes for Elliptic Curve Cryptosystems" (2008) */ /* Twisted Edwards E(p) Curve: a * x^2 + y^2 = 1 + d * x^2 * y^2, a = -1, p = 2^256 - c, c small Edwards coordinates: (X : Y : Z) Extended Edwards coordinates: (X : Y : T : Z), T = XY Edwards to Extended Edwards: (X : Y : Z) -> (XZ : YZ : XY : ZZ) Extended Edwards to Edwards: (X : Y : T : Z) -> (X : Y : Z) -(X : Y : T : Z) = (-X : Y : -T : Z) Additive Identity element: X = 0 When Z = 1, a multiplication can be omitted Mixing operations for more speed: doubling, doubling -> E = 2E doubling, add -> Ee = 2E, E = Ee + Ee */ #ifndef CAT_BIG_TWISTED_EDWARDS_HPP #define CAT_BIG_TWISTED_EDWARDS_HPP #include #include namespace cat { class BigTwistedEdwards : public BigPseudoMersenne { static const int POINT_REGS = 4; static const int XOFF = 0; int YOFF, TOFF, ZOFF, POINT_STRIDE; // Point multiplication default window static const int WINDOW_BITS = 6; static const int PRECOMP_POINTS = 1 << (WINDOW_BITS-1); static const int PRECOMP_NEG_OFFSET = PRECOMP_POINTS / 2; static const int TE_OVERHEAD = (1 + PRECOMP_POINTS) * POINT_REGS + 9 + POINT_REGS * 2; int te_regs; // Local workspace Leg *A, *B, *C, *D, *E, *F, *G, *H, *CurveQ, *Generator; Leg *TempPt; protected: Leg curve_d; // Simultaneous Add and Subtract for efficient precomputation (A +/- B) in 14M 1D 11a (versus 16M 2D 16a) void PtPrecompAddSub(const Leg *in_a, const Leg *in_b, Leg *sum, Leg *diff, int neg_offset); public: BigTwistedEdwards(int regs, int bits, int C, int D, const u8 *Q, const u8 *GenPt); int PtLegs() { return Legs() * POINT_REGS; } Leg GetCurveD() { return curve_d; } const Leg *GetCurveQ() { return CurveQ; } const Leg *GetGenerator() { return Generator; } public: // Unpack an Extended Projective point (X,Y,T,Z) from affine point (x,y) void PtUnpack(Leg *inout); // Set a point to the identity void PtIdentity(Leg *inout); // Check if the affine point (x,y) is the additive identity x=0 bool IsAffineIdentity(const Leg *in); public: void PtCopy(const Leg *in, Leg *out); // Fill the X coordinate of the point with a random value void PtFillRandomX(IRandom *prng, Leg *out); // Generate a random point on the curve that is not part of a small subgroup void PtGenerate(IRandom *prng, Leg *out); public: // Solve for Y given the X point on a curve void PtSolveAffineY(Leg *inout); // Verify that the point (x,y) exists on the given curve bool PtValidAffine(const Leg *in); public: // out(x) = X/Z void SaveAffineX(const Leg *in, void *out_x); // out(x,y) = (X/Z,Y/Z) void SaveAffineXY(const Leg *in, void *out_x, void *out_y); // out(X,Y) = (X,Y) without attempting to convert to affine from projective void SaveProjectiveXY(const Leg *in, void *out_x, void *out_y); // out(X,Y,Z,T) = (in_x,in_y), returns false if the coordinates are invalid bool LoadVerifyAffineXY(const void *in_x, const void *in_y, Leg *out); // Compute affine coordinates for (X,Y), set Z=1, and compute T = xy void PtNormalize(const Leg *in, Leg *out); public: // Extended Twisted Edwards Negation Formula void PtNegate(const Leg *in, Leg *out); // Extended Twisted Edwards Unified Addition Formula (works when both inputs are the same) in 8M 1D 9a void PtEAdd(const Leg *in_a, const Leg *in_b, Leg *out); void PtAdd(const Leg *in_a, const Leg *in_b, Leg *out); // -1M, cannot be followed by PtAdd // Extended Twisted Edwards Unified Subtraction Formula (works when both inputs are the same) in 8M 1D 9a void PtESubtract(const Leg *in_a, const Leg *in_b, Leg *out); void PtSubtract(const Leg *in_a, const Leg *in_b, Leg *out); // -1M, cannot be followed by PtAdd // Extended Twisted Edwards Dedicated Doubling Formula in 4M 4S 5a void PtEDouble(const Leg *in, Leg *out); void PtDouble(const Leg *in, Leg *out); // -1M, cannot be followed by PtAdd // Extended Twisted Edwards Dedicated Doubling Formula Assuming Z=1, in 4M 3S 4a void PtEDoubleZ1(const Leg *in, Leg *out); void PtDoubleZ1(const Leg *in, Leg *out); // -1M, cannot be followed by PtAdd public: // Allocate a table for use with PtMultiplyPrecomp() // Free the table with Aligned::Delete() Leg *PtMultiplyPrecompAlloc(int w); // Precompute odd multiples of input point void PtMultiplyPrecomp(const Leg *in, int w, Leg *table); public: // Extended Twisted Edwards Scalar Multiplication k*p // Requires precomputation with PtMultiplyPrecomp() // CAN *NOT* BE followed by a Pt[E]Add() void PtMultiply(const Leg *in_precomp, int w, const Leg *in_k, u8 msb_k, Leg *out); // Extended Twisted Edwards Scalar Multiplication k*p // Uses default precomputation // CAN *NOT* BE followed by a Pt[E]Add() void PtMultiply(const Leg *in_p, const Leg *in_k, u8 msb_k, Leg *out); // A reference multiplier to verify that PtMultiply() is functionally the same void RefMul(const Leg *in_p, const Leg *in_k, u8 msb_k, Leg *out); public: // Extended Twisted Edwards Simultaneous Scalar Multiplication k*P + l*Q // Requires precomputation with PtMultiplyPrecomp() // CAN *NOT* BE followed by a Pt[E]Add() void PtSiMultiply(const Leg *precomp_p, const Leg *precomp_q, int w, const Leg *in_k, u8 msb_k, const Leg *in_l, u8 msb_l, Leg *out); }; } // namespace cat #endif // CAT_BIG_TWISTED_EDWARDS_HPP