umac-poly64.c

   1 /* umac-poly64.c
   2  */
   3
   4 /* nettle, low-level cryptographics library
   5  *
   6  * Copyright (C) 2013 Niels Möller
   7  *
   8  * The nettle library is free software; you can redistribute it and/or modify
   9  * it under the terms of the GNU Lesser General Public License as published by
  10  * the Free Software Foundation; either version 2.1 of the License, or (at your
  11  * option) any later version.
  12  *
  13  * The nettle library is distributed in the hope that it will be useful, but
  14  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  15  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  16  * License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public License
  19  * along with the nettle library; see the file COPYING.LIB.  If not, write to
  20  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  21  * MA 02111-1301, USA.
  22  */
  23
  24 #if HAVE_CONFIG_H
  25 # include "config.h"
  26 #endif
  27
  28 #include <assert.h>
  29
  30 #include "umac.h"
  31
  32 static uint64_t
  33 poly64_mul (uint32_t kh, uint32_t kl, uint64_t y)
  34 {
  35   uint64_t yl, yh, pl, ph, ml, mh;
  36   yl = y & 0xffffffff;
  37   yh = y >> 32;
  38   pl = yl * kl;
  39   ph = yh * kh;
  40   ml = yh * kl + yl * kh; /* No overflow, thanks to special form */
  41   mh = ml >> 32;
  42   ml <<= 32;
  43   pl += ml;
  44   ph += mh + (pl < ml);
  45
  46   /* Reduce, using 2^64 = UMAC_P64_OFFSET (mod p) */
  47   assert (ph < ((uint64_t) 1 << 57));
  48   ph *= UMAC_P64_OFFSET;
  49   pl += ph;
  50   if (pl < ph)
  51     pl += UMAC_P64_OFFSET;
  52
  53   return pl;
  54 }
  55
  56 uint64_t
  57 _umac_poly64 (uint32_t kh, uint32_t kl, uint64_t y, uint64_t m)
  58 {
  59   if ( (m >> 32) == 0xffffffff)
  60     {
  61       y = poly64_mul (kh, kl, y);
  62       if (y == 0)
  63         y = UMAC_P64 - 1;
  64       else
  65         y--;
  66       m -= UMAC_P64_OFFSET;
  67     }
  68   y = poly64_mul (kh, kl, y);
  69   y += m;
  70   if (y < m)
  71     y += UMAC_P64_OFFSET;
  72
  73   return y;
  74 }