From 9d875f041854593e5b19bc63961da102f9fd754e Mon Sep 17 00:00:00 2001 From: Matthias Schiffer Date: Sun, 23 Dec 2012 19:17:28 +0100 Subject: Lots of code documentation --- Doxyfile.in | 16 ++++----- include/libuecc/ecc.h | 92 +++++++++++++++++++++++++++++++++++++++++++++++---- src/ec25519.c | 60 +++++++++++++++++++++++++++++++++ src/ec25519_gf.c | 53 ++++++++++++++++++++++++++--- 4 files changed, 202 insertions(+), 19 deletions(-) diff --git a/Doxyfile.in b/Doxyfile.in index 5b8683e..3a61a6e 100644 --- a/Doxyfile.in +++ b/Doxyfile.in @@ -114,7 +114,7 @@ FULL_PATH_NAMES = NO # If left blank the directory from which doxygen is run is used as the # path to strip. -STRIP_FROM_PATH = +STRIP_FROM_PATH = include # The STRIP_FROM_INC_PATH tag can be used to strip a user-defined part of # the path mentioned in the documentation of a class, which tells @@ -123,7 +123,7 @@ STRIP_FROM_PATH = # definition is used. Otherwise one should specify the include paths that # are normally passed to the compiler using the -I flag. -STRIP_FROM_INC_PATH = +STRIP_FROM_INC_PATH = # If the SHORT_NAMES tag is set to YES, doxygen will generate much shorter # (but less readable) file names. This can be useful is your file systems @@ -137,7 +137,7 @@ SHORT_NAMES = NO # comments will behave just like regular Qt-style comments # (thus requiring an explicit @brief command for a brief description.) -JAVADOC_AUTOBRIEF = NO +JAVADOC_AUTOBRIEF = YES # If the QT_AUTOBRIEF tag is set to YES then Doxygen will # interpret the first line (until the first dot) of a Qt-style @@ -270,7 +270,7 @@ SUBGROUPING = YES # be useful for C code in case the coding convention dictates that all compound # types are typedef'ed and only the typedef is referenced, never the tag name. -TYPEDEF_HIDES_STRUCT = NO +TYPEDEF_HIDES_STRUCT = YES # The SYMBOL_CACHE_SIZE determines the size of the internal cache use to # determine which symbols to keep in memory and which to flush to disk. @@ -1199,13 +1199,13 @@ ENABLE_PREPROCESSING = YES # compilation will be performed. Macro expansion can be done in a controlled # way by setting EXPAND_ONLY_PREDEF to YES. -MACRO_EXPANSION = NO +MACRO_EXPANSION = YES # If the EXPAND_ONLY_PREDEF and MACRO_EXPANSION tags are both set to YES # then the macro expansion is limited to the macros specified with the # PREDEFINED and EXPAND_AS_DEFINED tags. -EXPAND_ONLY_PREDEF = NO +EXPAND_ONLY_PREDEF = YES # If the SEARCH_INCLUDES tag is set to YES (the default) the includes files # in the INCLUDE_PATH (see below) will be search if a #include is found. @@ -1233,14 +1233,14 @@ INCLUDE_FILE_PATTERNS = # undefined via #undef or recursively expanded use the := operator # instead of the = operator. -PREDEFINED = +PREDEFINED = DEPRECATED= # If the MACRO_EXPANSION and EXPAND_ONLY_PREDEF tags are set to YES then # this tag can be used to specify a list of macro names that should be expanded. # The macro definition that is found in the sources will be used. # Use the PREDEFINED tag if you want to use a different macro definition. -EXPAND_AS_DEFINED = +EXPAND_AS_DEFINED = # If the SKIP_FUNCTION_MACROS tag is set to YES (the default) then # doxygen's preprocessor will remove all function-like macros that are alone diff --git a/include/libuecc/ecc.h b/include/libuecc/ecc.h index 2f2c0d9..1cc2100 100644 --- a/include/libuecc/ecc.h +++ b/include/libuecc/ecc.h @@ -31,15 +31,28 @@ #define DEPRECATED __attribute__((deprecated)) #endif - +/** + * A 256 bit integer + * + * All functions of libuecc treat \ref ecc_int256_t as unsigned little-endian. + */ typedef union _ecc_int256 { + /** Data bytes */ unsigned char p[32]; - /* old name */ + /** + * Old name of p + * \deprecated Use \ref ecc_int256_t::p instead. + */ unsigned char s[32] DEPRECATED; } ecc_int256_t; -/* a point on the curve unpacked for efficient calculation */ +/** + * A point on the curve unpacked for efficient calculation + * + * The internal representation of an unpacked point isn't unique, so for serialization + * it should always be packed. + */ typedef struct _ecc_25519_work { unsigned int X[32]; unsigned int Y[32]; @@ -47,6 +60,10 @@ typedef struct _ecc_25519_work { unsigned int T[32]; } ecc_25519_work_t; +/** + * \defgroup curve_ops Operations on points of the Elliptic Curve + * @{ + */ void ecc_25519_load_xy(ecc_25519_work_t *out, const ecc_int256_t *x, const ecc_int256_t *y); void ecc_25519_store_xy(ecc_int256_t *x, ecc_int256_t *y, const ecc_25519_work_t *in); @@ -55,12 +72,18 @@ void ecc_25519_load_packed(ecc_25519_work_t *out, const ecc_int256_t *in); void ecc_25519_store_packed(ecc_int256_t *out, const ecc_25519_work_t *in); int ecc_25519_is_identity(const ecc_25519_work_t *in); -void ecc_25519_add(ecc_25519_work_t *out, const ecc_25519_work_t *in1, const ecc_25519_work_t *in2); void ecc_25519_double(ecc_25519_work_t *out, const ecc_25519_work_t *in); +void ecc_25519_add(ecc_25519_work_t *out, const ecc_25519_work_t *in1, const ecc_25519_work_t *in2); void ecc_25519_scalarmult(ecc_25519_work_t *out, const ecc_int256_t *n, const ecc_25519_work_t *base); void ecc_25519_scalarmult_base(ecc_25519_work_t *out, const ecc_int256_t *n); -/* operations on elements of the prime field F_q for q = 2^252 + 27742317777372353535851937790883648493 */ +/**@}*/ + +/** + * \defgroup gf_ops Prime field operations for the order of the base point of the Elliptic Curve + * @{ + */ + extern const ecc_int256_t ecc_25519_gf_order; int ecc_25519_gf_is_zero(const ecc_int256_t *in); @@ -69,42 +92,99 @@ void ecc_25519_gf_sub(ecc_int256_t *out, const ecc_int256_t *in1, const ecc_int2 void ecc_25519_gf_reduce(ecc_int256_t *out, const ecc_int256_t *in); void ecc_25519_gf_mult(ecc_int256_t *out, const ecc_int256_t *in1, const ecc_int256_t *in2); void ecc_25519_gf_recip(ecc_int256_t *out, const ecc_int256_t *in); - void ecc_25519_gf_sanitize_secret(ecc_int256_t *out, const ecc_int256_t *in); +/**@}*/ + /* declarations for the old names */ + +/** + * Old name of \ref ecc_int256_t + * \deprecated Use \ref ecc_int256_t instead. + */ typedef ecc_int256_t ecc_secret_key_256 DEPRECATED; + +/** + * Old name of \ref ecc_int256_t + * \deprecated Use \ref ecc_int256_t instead. + */ typedef ecc_int256_t ecc_public_key_256 DEPRECATED; + +/** + * Old name of \ref ecc_25519_work_t + * \deprecated Use \ref ecc_25519_work_t instead. + */ typedef ecc_25519_work_t ecc_25519_work DEPRECATED; + +/** + * Loads a packed point into its unpacked representation + * + * \deprecated Use \ref ecc_25519_load_packed instead. + */ DEPRECATED static inline void ecc_25519_load(ecc_25519_work_t *out, const ecc_int256_t *in) { ecc_25519_load_packed(out, in); } +/** + * Stores a point into its packed representation + * + * \deprecated Use \ref ecc_25519_store_packed instead. + */ DEPRECATED static inline void ecc_25519_store(ecc_int256_t *out, const ecc_25519_work_t *in) { ecc_25519_store_packed(out, in); } +/** + * Checks if an integer is equal to zero (after reduction) + * + * \deprecated Use \ref ecc_25519_gf_is_zero instead. + */ DEPRECATED static inline int ecc_25519_secret_is_zero(const ecc_int256_t *in) { return ecc_25519_gf_is_zero(in); } +/** + * Adds two integers as Galois field elements + * + * \deprecated Use \ref ecc_25519_gf_add instead. + */ DEPRECATED static inline void ecc_25519_secret_add(ecc_int256_t *out, const ecc_int256_t *in1, const ecc_int256_t *in2) { ecc_25519_gf_add(out, in1, in2); } +/** + * Subtracts two integers as Galois field elements + * + * \deprecated Use \ref ecc_25519_gf_sub instead. + */ DEPRECATED static inline void ecc_25519_secret_sub(ecc_int256_t *out, const ecc_int256_t *in1, const ecc_int256_t *in2) { ecc_25519_gf_sub(out, in1, in2); } +/** + * Reduces an integer to a unique representation in the range \f$ [0,q-1] \f$ + * + * \deprecated Use \ref ecc_25519_gf_reduce instead. + */ DEPRECATED static inline void ecc_25519_secret_reduce(ecc_int256_t *out, const ecc_int256_t *in) { ecc_25519_gf_reduce(out, in); } +/** + * Multiplies to integers as Galois field elements + * + * \deprecated Use \ref ecc_25519_gf_mult instead. + */ DEPRECATED static inline void ecc_25519_secret_mult(ecc_int256_t *out, const ecc_int256_t *in1, const ecc_int256_t *in2) { ecc_25519_gf_mult(out, in1, in2); } +/** + * Ensures some properties of a Galois field element to make it fit for use as a secret key + * + * \deprecated Use \ref ecc_25519_gf_sanitize_secret instead. + */ DEPRECATED static inline void ecc_25519_secret_sanitize(ecc_int256_t *out, const ecc_int256_t *in) { ecc_25519_gf_sanitize_secret(out, in); } diff --git a/src/ec25519.c b/src/ec25519.c index bc6cc13..f77fcff 100644 --- a/src/ec25519.c +++ b/src/ec25519.c @@ -40,6 +40,7 @@ #include +/** Adds two unpacked integers (modulo p) */ static void add(unsigned int out[32], const unsigned int a[32], const unsigned int b[32]) { unsigned int j; unsigned int u; @@ -48,6 +49,7 @@ static void add(unsigned int out[32], const unsigned int a[32], const unsigned i u += a[31] + b[31]; out[31] = u; } +/** Subtracts two unpacked integers (modulo p) */ static void sub(unsigned int out[32], const unsigned int a[32], const unsigned int b[32]) { unsigned int j; unsigned int u; @@ -61,6 +63,7 @@ static void sub(unsigned int out[32], const unsigned int a[32], const unsigned i out[31] = u; } +/** Performs carry and reduce on an unpacked integer */ static void squeeze(unsigned int a[32]) { unsigned int j; unsigned int u; @@ -72,6 +75,11 @@ static void squeeze(unsigned int a[32]) { u += a[31]; a[31] = u; } +/** + * Ensures that the output of a previous \ref squeeze is fully reduced + * + * After a \ref freeze, only the lower byte of each integer part holds a meaningful value + */ static void freeze(unsigned int a[32]) { static const unsigned int minusp[32] = { 19, 0, 0, 0, 0, 0, 0, 0, @@ -90,6 +98,7 @@ static void freeze(unsigned int a[32]) { for (j = 0; j < 32; j++) a[j] ^= negative & (aorig[j] ^ a[j]); } +/** Multiplies two unpacked integers (modulo p) */ static void mult(unsigned int out[32], const unsigned int a[32], const unsigned int b[32]) { unsigned int i; unsigned int j; @@ -104,6 +113,7 @@ static void mult(unsigned int out[32], const unsigned int a[32], const unsigned squeeze(out); } +/** Multiplies an unpacked integer with a small integer (modulo p) */ static void mult_int(unsigned int out[32], const unsigned int n, const unsigned int a[32]) { unsigned int j; unsigned int u; @@ -116,6 +126,7 @@ static void mult_int(unsigned int out[32], const unsigned int n, const unsigned u += out[j]; out[j] = u; } +/** Squares an unpacked integer */ static void square(unsigned int out[32], const unsigned int a[32]) { unsigned int i; unsigned int j; @@ -135,6 +146,7 @@ static void square(unsigned int out[32], const unsigned int a[32]) { squeeze(out); } +/** Checks for the equality of two unpacked integers */ static int check_equal(const unsigned int x[32], const unsigned int y[32]) { unsigned int differentbits = 0; int i; @@ -147,6 +159,11 @@ static int check_equal(const unsigned int x[32], const unsigned int y[32]) { return (1 & ((differentbits - 1) >> 16)); } +/** + * Checks if an unpacked integer equals zero + * + * The intergers must be must be \ref squeeze "squeezed" before. + */ static int check_zero(const unsigned int x[32]) { static const unsigned int zero[32] = {0}; static const unsigned int p[32] = { @@ -159,6 +176,7 @@ static int check_zero(const unsigned int x[32]) { return (check_equal(x, zero) | check_equal(x, p)); } +/** Copies r to out when b == 0, s when b == 1 */ static void selectw(ecc_25519_work_t *out, const ecc_25519_work_t *r, const ecc_25519_work_t *s, unsigned int b) { unsigned int j; unsigned int t; @@ -180,6 +198,7 @@ static void selectw(ecc_25519_work_t *out, const ecc_25519_work_t *r, const ecc_ } } +/** Copies r to out when b == 0, s when b == 1 */ static void select(unsigned int out[32], const unsigned int r[32], const unsigned int s[32], unsigned int b) { unsigned int j; unsigned int t; @@ -192,6 +211,11 @@ static void select(unsigned int out[32], const unsigned int r[32], const unsigne } } +/** + * Computes the square root of an unpacked integer (in the prime field modulo p) + * + * If the given integer has no square root, the result is undefined. + */ static void square_root(unsigned int out[32], const unsigned int z[32]) { static const unsigned int minus1[32] = { 0xec, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, @@ -281,6 +305,7 @@ static void square_root(unsigned int out[32], const unsigned int z[32]) { select(out, z2_252_1, z2_252_1_rho_s, check_equal(t1, minus1)); } +/** Computes the reciprocal of an unpacked integer (in the prime field modulo p) */ static void recip(unsigned int out[32], const unsigned int z[32]) { unsigned int z2[32]; unsigned int z9[32]; @@ -347,6 +372,7 @@ static void recip(unsigned int out[32], const unsigned int z[32]) { /* 2^255 - 21 */ mult(out, t1, z11); } +/** Loads a point with given coordinates into its unpacked representation */ void ecc_25519_load_xy(ecc_25519_work_t *out, const ecc_int256_t *x, const ecc_int256_t *y) { int i; @@ -359,6 +385,13 @@ void ecc_25519_load_xy(ecc_25519_work_t *out, const ecc_int256_t *x, const ecc_i mult(out->T, out->X, out->Y); } +/** + * Stores a point's x and y coordinates + * + * \param x Returns the x coordinate of the point. May be NULL. + * \param y Returns the y coordinate of the point. May be NULL. + * \param in The unpacked point to store. + */ void ecc_25519_store_xy(ecc_int256_t *x, ecc_int256_t *y, const ecc_25519_work_t *in) { unsigned int X[32], Y[32], Z[32]; int i; @@ -380,6 +413,7 @@ void ecc_25519_store_xy(ecc_int256_t *x, ecc_int256_t *y, const ecc_25519_work_t } } +/** Loads a packed point into its unpacked representation */ void ecc_25519_load_packed(ecc_25519_work_t *out, const ecc_int256_t *in) { static const unsigned int zero[32] = {0}; static const unsigned int one[32] = {1}; @@ -410,6 +444,7 @@ void ecc_25519_load_packed(ecc_25519_work_t *out, const ecc_int256_t *in) { mult(out->T, out->X, out->Y); } +/** Stores a point into its packed representation */ void ecc_25519_store_packed(ecc_int256_t *out, const ecc_25519_work_t *in) { ecc_int256_t y; @@ -417,8 +452,10 @@ void ecc_25519_store_packed(ecc_int256_t *out, const ecc_25519_work_t *in) { out->p[31] |= (y.p[0] << 7); } +/** The identity element */ static const ecc_25519_work_t id = {{0}, {1}, {1}, {0}}; +/** Checks if a point is the identity element of the Elliptic Curve group */ int ecc_25519_is_identity(const ecc_25519_work_t *in) { unsigned int Y_Z[32]; @@ -428,6 +465,13 @@ int ecc_25519_is_identity(const ecc_25519_work_t *in) { return (check_zero(in->X)&check_zero(Y_Z)); } +/** + * Doubles a point of the Elliptic Curve + * + * ecc_25519_double(out, in) is equivalent to ecc_25519_add(out, in, in), but faster. + * + * The same pointers may be used for input and output. + */ void ecc_25519_double(ecc_25519_work_t *out, const ecc_25519_work_t *in) { unsigned int A[32], B[32], C[32], D[32], E[32], F[32], G[32], H[32], t0[32], t1[32], t2[32], t3[32]; @@ -449,6 +493,11 @@ void ecc_25519_double(ecc_25519_work_t *out, const ecc_25519_work_t *in) { mult(out->Z, F, G); } +/** + * Adds two points of the Elliptic Curve + * + * The same pointers may be used for input and output. + */ void ecc_25519_add(ecc_25519_work_t *out, const ecc_25519_work_t *in1, const ecc_25519_work_t *in2) { unsigned int A[32], B[32], C[32], D[32], E[32], F[32], G[32], H[32], t0[32], t1[32], t2[32], t3[32], t4[32], t5[32]; @@ -472,6 +521,11 @@ void ecc_25519_add(ecc_25519_work_t *out, const ecc_25519_work_t *in1, const ecc mult(out->Z, F, G); } +/** + * Does a scalar multiplication of a point of the Elliptic Curve with an integer + * + * The same pointers may be used for input and output. + **/ void ecc_25519_scalarmult(ecc_25519_work_t *out, const ecc_int256_t *n, const ecc_25519_work_t *base) { ecc_25519_work_t Q2, Q2p; ecc_25519_work_t cur = id; @@ -489,6 +543,7 @@ void ecc_25519_scalarmult(ecc_25519_work_t *out, const ecc_int256_t *n, const ec *out = cur; } +/** The ec25519 default base */ static const ecc_25519_work_t default_base = { {0xd4, 0x6b, 0xfe, 0x7f, 0x39, 0xfa, 0x8c, 0x22, 0xe1, 0x96, 0x23, 0xeb, 0x26, 0xb7, 0x8e, 0x6a, @@ -505,6 +560,11 @@ static const ecc_25519_work_t default_base = { 0x47, 0x4b, 0x4c, 0x81, 0xa6, 0x02, 0xfd, 0x29} }; +/** + * Does a scalar multiplication of the default base point (generator element) of the Elliptic Curve with an integer + * + * The order of the base point is \f$ 2^{252} + 27742317777372353535851937790883648493 \f$. + */ void ecc_25519_scalarmult_base(ecc_25519_work_t *out, const ecc_int256_t *n) { ecc_25519_scalarmult(out, n, &default_base); } diff --git a/src/ec25519_gf.c b/src/ec25519_gf.c index ec3b543..d9f9bc1 100644 --- a/src/ec25519_gf.c +++ b/src/ec25519_gf.c @@ -24,19 +24,27 @@ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ -/* - Simple finite field operations on the prime field F_q for - q = 2^252 + 27742317777372353535851937790883648493, which +/** \file + Simple finite field operations on the prime field \f$ F_q \f$ for + \f$ q = 2^{252} + 27742317777372353535851937790883648493 \f$, which is the order of the base point used for ec25519 */ #include +/** Checks if the highest bit of an unsigned integer is set */ #define IS_NEGATIVE(n) ((int)((((unsigned)n) >> (8*sizeof(n)-1))&1)) + +/** Performs an arithmetic right shift */ #define ASR(n,s) (((n) >> s)|(IS_NEGATIVE(n)*((unsigned)-1) << (8*sizeof(n)-s))) +/** + * The order of the prime field + * + * The order is \f$ 2^{252} + 27742317777372353535851937790883648493 \f$. + */ const ecc_int256_t ecc_25519_gf_order = {{ 0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14, @@ -44,8 +52,12 @@ const ecc_int256_t ecc_25519_gf_order = {{ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10 }}; +/** An internal alias for \ref ecc_25519_gf_order */ static const unsigned char *q = ecc_25519_gf_order.p; +/** + * Copies the content of r into out if b == 0, the contents of s if b == 1 + */ static void select(unsigned char out[32], const unsigned char r[32], const unsigned char s[32], unsigned int b) { unsigned int j; unsigned int t; @@ -58,6 +70,7 @@ static void select(unsigned char out[32], const unsigned char r[32], const unsig } } +/** Checks if an integer is equal to zero (after reduction) */ int ecc_25519_gf_is_zero(const ecc_int256_t *in) { int i; ecc_int256_t r; @@ -71,6 +84,11 @@ int ecc_25519_gf_is_zero(const ecc_int256_t *in) { return (((bits-1)>>8) & 1); } +/** + * Adds two integers as Galois field elements + * + * The same pointers may be used for input and output. + */ void ecc_25519_gf_add(ecc_int256_t *out, const ecc_int256_t *in1, const ecc_int256_t *in2) { unsigned int j; unsigned int u; @@ -85,6 +103,11 @@ void ecc_25519_gf_add(ecc_int256_t *out, const ecc_int256_t *in1, const ecc_int2 } } +/** + * Subtracts two integers as Galois field elements + * + * The same pointers may be used for input and output. + */ void ecc_25519_gf_sub(ecc_int256_t *out, const ecc_int256_t *in1, const ecc_int256_t *in2) { unsigned int j; unsigned int u; @@ -99,6 +122,7 @@ void ecc_25519_gf_sub(ecc_int256_t *out, const ecc_int256_t *in1, const ecc_int2 } } +/** Reduces an integer to a unique representation in the range \f$ [0,q-1] \f$ */ static void reduce(unsigned char a[32]) { unsigned int j; unsigned int nq = a[31] >> 4; @@ -121,6 +145,11 @@ static void reduce(unsigned char a[32]) { select(a, out1, out2, IS_NEGATIVE(u1)); } +/** + * Reduces an integer to a unique representation in the range \f$ [0,q-1] \f$ + * + * The same pointers may be used for input and output. + */ void ecc_25519_gf_reduce(ecc_int256_t *out, const ecc_int256_t *in) { int i; @@ -130,7 +159,7 @@ void ecc_25519_gf_reduce(ecc_int256_t *out, const ecc_int256_t *in) { reduce(out->p); } -/* Montgomery modular multiplication algorithm */ +/** Montgomery modular multiplication algorithm */ static void montgomery(unsigned char out[32], const unsigned char a[32], const unsigned char b[32]) { unsigned int i, j; unsigned int nq; @@ -154,7 +183,11 @@ static void montgomery(unsigned char out[32], const unsigned char a[32], const u } } - +/** + * Multiplies two integers as Galois field elements + * + * The same pointers may be used for input and output. + */ void ecc_25519_gf_mult(ecc_int256_t *out, const ecc_int256_t *in1, const ecc_int256_t *in2) { /* 2^512 mod q */ static const unsigned char C[32] = { @@ -177,6 +210,11 @@ void ecc_25519_gf_mult(ecc_int256_t *out, const ecc_int256_t *in1, const ecc_int montgomery(out->p, R, C); } +/** + * Computes the reciprocal of a Galois field element + * + * The same pointers may be used for input and output. + */ void ecc_25519_gf_recip(ecc_int256_t *out, const ecc_int256_t *in) { static const unsigned char C[32] = { 0x01 @@ -230,6 +268,11 @@ void ecc_25519_gf_recip(ecc_int256_t *out, const ecc_int256_t *in) { montgomery(out->p, R2, C); } +/** + * Ensures some properties of a Galois field element to make it fit for use as a secret key + * + * The same pointers may be used for input and output. + */ void ecc_25519_gf_sanitize_secret(ecc_int256_t *out, const ecc_int256_t *in) { int i; -- cgit v1.2.3