mdw@git.distorted.org.uk Git - secnet/blob - f25519.h

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