chiark - git - mdw - catacomb/blob - math/f25519.h

   1 /* -*-c-*-
   2  *
   3  * Arithmetic modulo 2^255 - 19
   4  *
   5  * (c) 2017 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Catacomb.
  11  *
  12  * Catacomb is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU Library General Public License as
  14  * published by the Free Software Foundation; either version 2 of the
  15  * License, or (at your option) any later version.
  16  *
  17  * Catacomb is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU Library General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Library General Public
  23  * License along with Catacomb; if not, write to the Free
  24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  25  * MA 02111-1307, USA.
  26  */
  27
  28 #ifndef CATACOMB_F25519_H
  29 #define CATACOMB_F25519_H
  30
  31 #ifdef __cplusplus
  32   extern "C" {
  33 #endif
  34
  35 /*----- Header files ------------------------------------------------------*/
  36
  37 #include <mLib/bits.h>
  38
  39 #ifndef CATACOMB_QFARITH_H
  40 #  include "qfarith.h"
  41 #endif
  42
  43 /*----- Data structures ---------------------------------------------------*/
  44
  45 typedef union {
  46   int32 p26[10];
  47   int16 p10[26];
  48 } f25519;
  49
  50 #if !defined(F25519_IMPL) && defined(HAVE_INT64)
  51 #  define F25519_IMPL 26
  52 #endif
  53
  54 #ifndef F25519_IMPL
  55 #  define F25519_IMPL 10
  56 #endif
  57
  58 #if F25519_IMPL == 26
  59   typedef int32 f25519_piece;
  60 #endif
  61 #if F25519_IMPL == 10
  62   typedef int16 f25519_piece;
  63 #endif
  64
  65 /*----- Functions provided ------------------------------------------------*/
  66
  67 /* --- @f25519_set@ --- *
  68  *
  69  * Arguments:   @f25519 *z@ = where to write the result
  70  *              @int a@ = a small-ish constant
  71  *
  72  * Returns:     ---
  73  *
  74  * Use:         Sets @z@ to equal @a@.
  75  */
  76
  77 extern void f25519_set(f25519 */*x*/, int /*a*/);
  78
  79 /* --- @f25519_load@ --- *
  80  *
  81  * Arguments:   @f25519 *z@ = where to store the result
  82  *              @const octet xv[32]@ = source to read
  83  *
  84  * Returns:     ---
  85  *
  86  * Use:         Reads an element of %$\gf{2^{255} - 19}$% in external
  87  *              representation from @xv@ and stores it in @z@.
  88  *
  89  *              External representation is little-endian base-256.  Elements
  90  *              have multiple encodings, which are not produced by correct
  91  *              software; use of noncanonical encodings is not an error, and
  92  *              toleration of them is considered a performance feature.
  93  *
  94  *              Some specifications, e.g., RFC7748, require the topmost bit
  95  *              (i.e., bit 7 of @wv[31]@) to be ignored.  Callers
  96  *              implementing such specifications should clear the bit
  97  *              explicitly.  (It's much easier for a caller who wants the bit
  98  *              to be ignored to clear it than for a caller who wants the bit
  99  *              to be significant to apply the necessary change by hand.)
 100  */
 101
 102 extern void f25519_load(f25519 */*z*/, const octet /*xv*/[32]);
 103
 104 /* --- @f25519_store@ --- *
 105  *
 106  * Arguments:   @octet zv[32]@ = where to write the result
 107  *              @const f25519 *x@ = the field element to write
 108  *
 109  * Returns:     ---
 110  *
 111  * Use:         Stores a field element in the given octet vector in external
 112  *              representation.  A canonical encoding is always stored, so,
 113  *              in particular, the top bit of @xv[31]@ is always left clear.
 114  */
 115
 116 extern void f25519_store(octet /*zv*/[32], const f25519 */*x*/);
 117
 118 /* --- @f25519_pick2@ --- *
 119  *
 120  * Arguments:   @f25519 *z@ = where to put the result (may alias @x@ or @y@)
 121  *              @const f25519 *x, *y@ = two operands
 122  *              @uint32 m@ = a mask
 123  *
 124  * Returns:     ---
 125  *
 126  * Use:         If @m@ is zero, set @z = y@; if @m@ is all-bits-set, then set
 127  *              @z = x@.  If @m@ has some other value, then scramble @z@ in
 128  *              an unhelpful way.
 129  */
 130
 131 extern void f25519_pick2(f25519 */*z*/, const f25519 */*x*/,
 132                          const f25519 */*y*/, uint32 /*m*/);
 133
 134 /* --- @f25519_pickn@ --- *
 135  *
 136  * Arguments:   @f25519 *z@ = where to put the result
 137  *              @const f25519 *v@ = a table of entries
 138  *              @size_t n@ = the number of entries in @v@
 139  *              @size_t i@ = an index
 140  *
 141  * Returns:     ---
 142  *
 143  * Use:         If @0 <= i < n < 32@ then set @z = v[i]@.  If @n >= 32@ then
 144  *              do something unhelpful; otherwise, if @i >= n@ then set @z@
 145  *              to zero.
 146  */
 147
 148 extern void f25519_pickn(f25519 */*z*/, const f25519 */*v*/, size_t /*n*/,
 149                          size_t /*i*/);
 150
 151 /* --- @f25519_condswap@ --- *
 152  *
 153  * Arguments:   @f25519 *x, *y@ = two operands
 154  *              @uint32 m@ = a mask
 155  *
 156  * Returns:     ---
 157  *
 158  * Use:         If @m@ is zero, do nothing; if @m@ is all-bits-set, then
 159  *              exchange @x@ and @y@.  If @m@ has some other value, then
 160  *              scramble @x@ and @y@ in an unhelpful way.
 161  */
 162
 163 extern void f25519_condswap(f25519 */*x*/, f25519 */*y*/, uint32 /*m*/);
 164
 165 /* --- @f25519_add@ --- *
 166  *
 167  * Arguments:   @f25519 *z@ = where to put the result (may alias @x@ or @y@)
 168  *              @const f25519 *x, *y@ = two operands
 169  *
 170  * Returns:     ---
 171  *
 172  * Use:         Set @z@ to the sum %$x + y$%.
 173  */
 174
 175 extern void f25519_add(f25519 */*z*/,
 176                        const f25519 */*x*/, const f25519 */*y*/);
 177
 178 /* --- @f25519_sub@ --- *
 179  *
 180  * Arguments:   @f25519 *z@ = where to put the result (may alias @x@ or @y@)
 181  *              @const f25519 *x, *y@ = two operands
 182  *
 183  * Returns:     ---
 184  *
 185  * Use:         Set @z@ to the difference %$x - y$%.
 186  */
 187
 188 extern void f25519_sub(f25519 */*z*/,
 189                        const f25519 */*x*/, const f25519 */*y*/);
 190
 191 /* --- @f25519_neg@ --- *
 192  *
 193  * Arguments:   @f25519 *z@ = where to put the result (may alias @x@)
 194  *              @const f25519 *x@ = an operand
 195  *
 196  * Returns:     ---
 197  *
 198  * Use:         Set @z = -x@.
 199  */
 200
 201 extern void f25519_neg(f25519 */*z*/, const f25519 */*x*/);
 202
 203 /* --- @f25519_condneg@ --- *
 204  *
 205  * Arguments:   @f25519 *z@ = where to put the result (may alias @x@)
 206  *              @const f25519 *x@ = an operand
 207  *              @uint32 m@ = a mask
 208  *
 209  * Returns:     ---
 210  *
 211  * Use:         If @m@ is zero, set @z = x@; if @m@ is all-bits-set, then set
 212  *              @z = -x@.  If @m@ has some other value then scramble @z@ in
 213  *              an unhelpful way.
 214  */
 215
 216 extern void f25519_condneg(f25519 */*z*/, const f25519 */*x*/, uint32 /*m*/);
 217
 218 /* --- @f25519_mulconst@ --- *
 219  *
 220  * Arguments:   @f25519 *z@ = where to put the result (may alias @x@)
 221  *              @const f25519 *x@ = an operand
 222  *              @long a@ = a small-ish constant; %$|a| < 2^{20}$%.
 223  *
 224  * Returns:     ---
 225  *
 226  * Use:         Set @z@ to the product %$a x$%.
 227  */
 228
 229 extern void f25519_mulconst(f25519 */*z*/, const f25519 */*x*/, long /*a*/);
 230
 231 /* --- @f25519_mul@ --- *
 232  *
 233  * Arguments:   @f25519 *z@ = where to put the result (may alias @x@ or @y@)
 234  *              @const f25519 *x, *y@ = two operands
 235  *
 236  * Returns:     ---
 237  *
 238  * Use:         Set @z@ to the product %$x y$%.
 239  */
 240
 241 extern void f25519_mul(f25519 */*z*/,
 242                        const f25519 */*x*/, const f25519 */*y*/);
 243
 244 /* --- @f25519_sqr@ --- *
 245  *
 246  * Arguments:   @f25519 *z@ = where to put the result (may alias @x@ or @y@)
 247  *              @const f25519 *x@ = an operand
 248  *
 249  * Returns:     ---
 250  *
 251  * Use:         Set @z@ to the square %$x^2$%.
 252  */
 253
 254 extern void f25519_sqr(f25519 */*z*/, const f25519 */*x*/);
 255
 256 /* --- @f25519_inv@ --- *
 257  *
 258  * Arguments:   @f25519 *z@ = where to put the result (may alias @x@)
 259  *              @const f25519 *x@ = an operand
 260  *
 261  * Returns:     ---
 262  *
 263  * Use:         Stores in @z@ the multiplicative inverse %$x^{-1}$%.  If
 264  *              %$x = 0$% then @z@ is set to zero.  This is considered a
 265  *              feature.
 266  */
 267
 268 extern void f25519_inv(f25519 */*z*/, const f25519 */*x*/);
 269
 270 /* --- @f25519_quosqrt@ --- *
 271  *
 272  * Arguments:   @f25519 *z@ = where to put the result (may alias @x@ or @y@)
 273  *              @const f25519 *x, *y@ = two operands
 274  *
 275  * Returns:     Zero if successful, @-1@ if %$x/y$% is not a square.
 276  *
 277  * Use:         Stores in @z@ the one of the square roots %$\pm\sqrt{x/y}$%.
 278  *              If %$x = y = 0% then the result is zero; if %$y = 0$% but %$x
 279  *              \ne 0$% then the operation fails.  If you wanted a specific
 280  *              square root then you'll have to pick it yourself.
 281  */
 282
 283 extern int f25519_quosqrt(f25519 */*z*/,
 284                           const f25519 */*x*/, const f25519 */*y*/);
 285
 286 /*----- That's all, folks -------------------------------------------------*/
 287
 288 #ifdef __cplusplus
 289   }
 290 #endif
 291
 292 #endif