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 /*----- Functions provided ------------------------------------------------*/
  59
  60 /* --- @f25519_set@ --- *
  61  *
  62  * Arguments:   @f25519 *z@ = where to write the result
  63  *              @int a@ = a small-ish constant
  64  *
  65  * Returns:     ---
  66  *
  67  * Use:         Sets @z@ to equal @a@.
  68  */
  69
  70 extern void f25519_set(f25519 */*x*/, int /*a*/);
  71
  72 /* --- @f25519_load@ --- *
  73  *
  74  * Arguments:   @f25519 *z@ = where to store the result
  75  *              @const octet xv[32]@ = source to read
  76  *
  77  * Returns:     ---
  78  *
  79  * Use:         Reads an element of %$\gf{2^{255} - 19}$% in external
  80  *              representation from @xv@ and stores it in @z@.
  81  *
  82  *              External representation is little-endian base-256.  Elements
  83  *              have multiple encodings, which are not produced by correct
  84  *              software; use of noncanonical encodings is not an error, and
  85  *              toleration of them is considered a performance feature.
  86  *
  87  *              Some specifications, e.g., RFC7748, require the topmost bit
  88  *              (i.e., bit 7 of @wv[31]@) to be ignored.  Callers
  89  *              implementing such specifications should clear the bit
  90  *              explicitly.  (It's much easier for a caller who wants the bit
  91  *              to be ignored to clear it than for a caller who wants the bit
  92  *              to be significant to apply the necessary change by hand.)
  93  */
  94
  95 extern void f25519_load(f25519 */*z*/, const octet /*xv*/[32]);
  96
  97 /* --- @f25519_store@ --- *
  98  *
  99  * Arguments:   @octet zv[32]@ = where to write the result
 100  *              @const f25519 *x@ = the field element to write
 101  *
 102  * Returns:     ---
 103  *
 104  * Use:         Stores a field element in the given octet vector in external
 105  *              representation.  A canonical encoding is always stored, so,
 106  *              in particular, the top bit of @xv[31]@ is always left clear.
 107  */
 108
 109 extern void f25519_store(octet /*zv*/[32], const f25519 */*x*/);
 110
 111 /* --- @f25519_pick2@ --- *
 112  *
 113  * Arguments:   @f25519 *z@ = where to put the result (may alias @x@ or @y@)
 114  *              @const f25519 *x, *y@ = two operands
 115  *              @uint32 m@ = a mask
 116  *
 117  * Returns:     ---
 118  *
 119  * Use:         If @m@ is zero, set @z = y@; if @m@ is all-bits-set, then set
 120  *              @z = x@.  If @m@ has some other value, then scramble @z@ in
 121  *              an unhelpful way.
 122  */
 123
 124 extern void f25519_pick2(f25519 */*z*/, const f25519 */*x*/,
 125                          const f25519 */*y*/, uint32 /*m*/);
 126
 127 /* --- @f25519_pickn@ --- *
 128  *
 129  * Arguments:   @f25519 *z@ = where to put the result
 130  *              @const f25519 *v@ = a table of entries
 131  *              @size_t n@ = the number of entries in @v@
 132  *              @size_t i@ = an index
 133  *
 134  * Returns:     ---
 135  *
 136  * Use:         If @0 <= i < n < 32@ then set @z = v[i]@.  If @n >= 32@ then
 137  *              do something unhelpful; otherwise, if @i >= n@ then set @z@
 138  *              to zero.
 139  */
 140
 141 extern void f25519_pickn(f25519 */*z*/, const f25519 */*v*/, size_t /*n*/,
 142                          size_t /*i*/);
 143
 144 /* --- @f25519_condswap@ --- *
 145  *
 146  * Arguments:   @f25519 *x, *y@ = two operands
 147  *              @uint32 m@ = a mask
 148  *
 149  * Returns:     ---
 150  *
 151  * Use:         If @m@ is zero, do nothing; if @m@ is all-bits-set, then
 152  *              exchange @x@ and @y@.  If @m@ has some other value, then
 153  *              scramble @x@ and @y@ in an unhelpful way.
 154  */
 155
 156 extern void f25519_condswap(f25519 */*x*/, f25519 */*y*/, uint32 /*m*/);
 157
 158 /* --- @f25519_add@ --- *
 159  *
 160  * Arguments:   @f25519 *z@ = where to put the result (may alias @x@ or @y@)
 161  *              @const f25519 *x, *y@ = two operands
 162  *
 163  * Returns:     ---
 164  *
 165  * Use:         Set @z@ to the sum %$x + y$%.
 166  */
 167
 168 extern void f25519_add(f25519 */*z*/,
 169                        const f25519 */*x*/, const f25519 */*y*/);
 170
 171 /* --- @f25519_sub@ --- *
 172  *
 173  * Arguments:   @f25519 *z@ = where to put the result (may alias @x@ or @y@)
 174  *              @const f25519 *x, *y@ = two operands
 175  *
 176  * Returns:     ---
 177  *
 178  * Use:         Set @z@ to the difference %$x - y$%.
 179  */
 180
 181 extern void f25519_sub(f25519 */*z*/,
 182                        const f25519 */*x*/, const f25519 */*y*/);
 183
 184 /* --- @f25519_neg@ --- *
 185  *
 186  * Arguments:   @f25519 *z@ = where to put the result (may alias @x@)
 187  *              @const f25519 *x@ = an operand
 188  *
 189  * Returns:     ---
 190  *
 191  * Use:         Set @z = -x@.
 192  */
 193
 194 extern void f25519_neg(f25519 */*z*/, const f25519 */*x*/);
 195
 196 /* --- @f25519_condneg@ --- *
 197  *
 198  * Arguments:   @f25519 *z@ = where to put the result (may alias @x@)
 199  *              @const f25519 *x@ = an operand
 200  *              @uint32 m@ = a mask
 201  *
 202  * Returns:     ---
 203  *
 204  * Use:         If @m@ is zero, set @z = x@; if @m@ is all-bits-set, then set
 205  *              @z = -x@.  If @m@ has some other value then scramble @z@ in
 206  *              an unhelpful way.
 207  */
 208
 209 extern void f25519_condneg(f25519 */*z*/, const f25519 */*x*/, uint32 /*m*/);
 210
 211 /* --- @f25519_mulconst@ --- *
 212  *
 213  * Arguments:   @f25519 *z@ = where to put the result (may alias @x@)
 214  *              @const f25519 *x@ = an operand
 215  *              @long a@ = a small-ish constant; %$|a| < 2^{20}$%.
 216  *
 217  * Returns:     ---
 218  *
 219  * Use:         Set @z@ to the product %$a x$%.
 220  */
 221
 222 extern void f25519_mulconst(f25519 */*z*/, const f25519 */*x*/, long /*a*/);
 223
 224 /* --- @f25519_mul@ --- *
 225  *
 226  * Arguments:   @f25519 *z@ = where to put the result (may alias @x@ or @y@)
 227  *              @const f25519 *x, *y@ = two operands
 228  *
 229  * Returns:     ---
 230  *
 231  * Use:         Set @z@ to the product %$x y$%.
 232  */
 233
 234 extern void f25519_mul(f25519 */*z*/,
 235                        const f25519 */*x*/, const f25519 */*y*/);
 236
 237 /* --- @f25519_sqr@ --- *
 238  *
 239  * Arguments:   @f25519 *z@ = where to put the result (may alias @x@ or @y@)
 240  *              @const f25519 *x@ = an operand
 241  *
 242  * Returns:     ---
 243  *
 244  * Use:         Set @z@ to the square %$x^2$%.
 245  */
 246
 247 extern void f25519_sqr(f25519 */*z*/, const f25519 */*x*/);
 248
 249 /* --- @f25519_inv@ --- *
 250  *
 251  * Arguments:   @f25519 *z@ = where to put the result (may alias @x@)
 252  *              @const f25519 *x@ = an operand
 253  *
 254  * Returns:     ---
 255  *
 256  * Use:         Stores in @z@ the multiplicative inverse %$x^{-1}$%.  If
 257  *              %$x = 0$% then @z@ is set to zero.  This is considered a
 258  *              feature.
 259  */
 260
 261 extern void f25519_inv(f25519 */*z*/, const f25519 */*x*/);
 262
 263 /* --- @f25519_quosqrt@ --- *
 264  *
 265  * Arguments:   @f25519 *z@ = where to put the result (may alias @x@ or @y@)
 266  *              @const f25519 *x, *y@ = two operands
 267  *
 268  * Returns:     Zero if successful, @-1@ if %$x/y$% is not a square.
 269  *
 270  * Use:         Stores in @z@ the one of the square roots %$\pm\sqrt{x/y}$%.
 271  *              If %$x = y = 0% then the result is zero; if %$y = 0$% but %$x
 272  *              \ne 0$% then the operation fails.  If you wanted a specific
 273  *              square root then you'll have to pick it yourself.
 274  */
 275
 276 extern int f25519_quosqrt(f25519 */*z*/,
 277                           const f25519 */*x*/, const f25519 */*y*/);
 278
 279 /*----- That's all, folks -------------------------------------------------*/
 280
 281 #ifdef __cplusplus
 282   }
 283 #endif
 284
 285 #endif