git.samba.org - gd/nettle/blob - sha3-permute.c

   1 /* sha3-permute.c
   2
   3    The sha3 permutation function (aka Keccak).
   4
   5    Copyright (C) 2012 Niels Möller
   6
   7    This file is part of GNU Nettle.
   8
   9    GNU Nettle is free software: you can redistribute it and/or
  10    modify it under the terms of either:
  11
  12      * the GNU Lesser General Public License as published by the Free
  13        Software Foundation; either version 3 of the License, or (at your
  14        option) any later version.
  15
  16    or
  17
  18      * the GNU General Public License as published by the Free
  19        Software Foundation; either version 2 of the License, or (at your
  20        option) any later version.
  21
  22    or both in parallel, as here.
  23
  24    GNU Nettle is distributed in the hope that it will be useful,
  25    but WITHOUT ANY WARRANTY; without even the implied warranty of
  26    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  27    General Public License for more details.
  28
  29    You should have received copies of the GNU General Public License and
  30    the GNU Lesser General Public License along with this program.  If
  31    not, see http://www.gnu.org/licenses/.
  32 */
  33
  34 #if HAVE_CONFIG_H
  35 # include "config.h"
  36 #endif
  37
  38 #include "sha3.h"
  39
  40 #include "macros.h"
  41
  42 #define SHA3_ROUNDS 24
  43
  44 /* For fat builds */
  45 #if HAVE_NATIVE_sha3_permute
  46 void
  47 _nettle_sha3_permute_c(struct sha3_state *state);
  48 #define nettle_sha3_permute _nettle_sha3_permute_c
  49 #endif
  50
  51 void
  52 sha3_permute (struct sha3_state *state)
  53 {
  54   static const uint64_t rc[SHA3_ROUNDS] = {
  55     0x0000000000000001ULL, 0X0000000000008082ULL,
  56     0X800000000000808AULL, 0X8000000080008000ULL,
  57     0X000000000000808BULL, 0X0000000080000001ULL,
  58     0X8000000080008081ULL, 0X8000000000008009ULL,
  59     0X000000000000008AULL, 0X0000000000000088ULL,
  60     0X0000000080008009ULL, 0X000000008000000AULL,
  61     0X000000008000808BULL, 0X800000000000008BULL,
  62     0X8000000000008089ULL, 0X8000000000008003ULL,
  63     0X8000000000008002ULL, 0X8000000000000080ULL,
  64     0X000000000000800AULL, 0X800000008000000AULL,
  65     0X8000000080008081ULL, 0X8000000000008080ULL,
  66     0X0000000080000001ULL, 0X8000000080008008ULL,
  67   };
  68
  69   /* Original permutation:
  70
  71        0,10,20, 5,15,
  72       16, 1,11,21, 6,
  73        7,17, 2,12,22,
  74       23, 8,18, 3,13,
  75       14,24, 9,19, 4
  76
  77      Rotation counts:
  78
  79        0,  1, 62, 28, 27,
  80       36, 44,  6, 55, 20,
  81        3, 10, 43, 25, 39,
  82       41, 45, 15, 21,  8,
  83       18,  2, 61, 56, 14,
  84   */
  85
  86   /* In-place implementation. Permutation done as a long sequence of
  87      25 moves "following" the permutation.
  88
  89       T <--  1
  90       1 <--  6
  91       6 <--  9
  92       9 <-- 22
  93      22 <-- 14
  94      14 <-- 20
  95      20 <--  2
  96       2 <-- 12
  97      12 <-- 13
  98      13 <-- 19
  99      19 <-- 23
 100      23 <-- 15
 101      15 <--  4
 102       4 <-- 24
 103      24 <-- 21
 104      21 <--  8
 105       8 <-- 16
 106      16 <--  5
 107       5 <--  3
 108       3 <-- 18
 109      18 <-- 17
 110      17 <-- 11
 111      11 <--  7
 112       7 <-- 10
 113      10 <--  T
 114
 115   */
 116   uint64_t C[5], D[5], T, X;
 117   unsigned i, y;
 118
 119 #define A state->a
 120
 121   C[0] = A[0] ^ A[5+0] ^ A[10+0] ^ A[15+0] ^ A[20+0];
 122   C[1] = A[1] ^ A[5+1] ^ A[10+1] ^ A[15+1] ^ A[20+1];
 123   C[2] = A[2] ^ A[5+2] ^ A[10+2] ^ A[15+2] ^ A[20+2];
 124   C[3] = A[3] ^ A[5+3] ^ A[10+3] ^ A[15+3] ^ A[20+3];
 125   C[4] = A[4] ^ A[5+4] ^ A[10+4] ^ A[15+4] ^ A[20+4];
 126
 127   for (i = 0; i < SHA3_ROUNDS; i++)
 128     {
 129       D[0] = C[4] ^ ROTL64(1, C[1]);
 130       D[1] = C[0] ^ ROTL64(1, C[2]);
 131       D[2] = C[1] ^ ROTL64(1, C[3]);
 132       D[3] = C[2] ^ ROTL64(1, C[4]);
 133       D[4] = C[3] ^ ROTL64(1, C[0]);
 134
 135       A[0] ^= D[0];
 136       X = A[ 1] ^ D[1];     T = ROTL64(1, X);
 137       X = A[ 6] ^ D[1]; A[ 1] = ROTL64 (44, X);
 138       X = A[ 9] ^ D[4]; A[ 6] = ROTL64 (20, X);
 139       X = A[22] ^ D[2]; A[ 9] = ROTL64 (61, X);
 140       X = A[14] ^ D[4]; A[22] = ROTL64 (39, X);
 141       X = A[20] ^ D[0]; A[14] = ROTL64 (18, X);
 142       X = A[ 2] ^ D[2]; A[20] = ROTL64 (62, X);
 143       X = A[12] ^ D[2]; A[ 2] = ROTL64 (43, X);
 144       X = A[13] ^ D[3]; A[12] = ROTL64 (25, X);
 145       X = A[19] ^ D[4]; A[13] = ROTL64 ( 8, X);
 146       X = A[23] ^ D[3]; A[19] = ROTL64 (56, X);
 147       X = A[15] ^ D[0]; A[23] = ROTL64 (41, X);
 148       X = A[ 4] ^ D[4]; A[15] = ROTL64 (27, X);
 149       X = A[24] ^ D[4]; A[ 4] = ROTL64 (14, X);
 150       X = A[21] ^ D[1]; A[24] = ROTL64 ( 2, X);
 151       X = A[ 8] ^ D[3]; A[21] = ROTL64 (55, X); /* row 4 done */
 152       X = A[16] ^ D[1]; A[ 8] = ROTL64 (45, X);
 153       X = A[ 5] ^ D[0]; A[16] = ROTL64 (36, X);
 154       X = A[ 3] ^ D[3]; A[ 5] = ROTL64 (28, X);
 155       X = A[18] ^ D[3]; A[ 3] = ROTL64 (21, X); /* row 0 done */
 156       X = A[17] ^ D[2]; A[18] = ROTL64 (15, X);
 157       X = A[11] ^ D[1]; A[17] = ROTL64 (10, X); /* row 3 done */
 158       X = A[ 7] ^ D[2]; A[11] = ROTL64 ( 6, X); /* row 1 done */
 159       X = A[10] ^ D[0]; A[ 7] = ROTL64 ( 3, X);
 160       A[10] = T;                                /* row 2 done */
 161
 162       D[0] = ~A[1] & A[2];
 163       D[1] = ~A[2] & A[3];
 164       D[2] = ~A[3] & A[4];
 165       D[3] = ~A[4] & A[0];
 166       D[4] = ~A[0] & A[1];
 167
 168       A[0] ^= D[0] ^ rc[i]; C[0] = A[0];
 169       A[1] ^= D[1]; C[1] = A[1];
 170       A[2] ^= D[2]; C[2] = A[2];
 171       A[3] ^= D[3]; C[3] = A[3];
 172       A[4] ^= D[4]; C[4] = A[4];
 173
 174       for (y = 5; y < 25; y+= 5)
 175         {
 176           D[0] = ~A[y+1] & A[y+2];
 177           D[1] = ~A[y+2] & A[y+3];
 178           D[2] = ~A[y+3] & A[y+4];
 179           D[3] = ~A[y+4] & A[y+0];
 180           D[4] = ~A[y+0] & A[y+1];
 181
 182           A[y+0] ^= D[0]; C[0] ^= A[y+0];
 183           A[y+1] ^= D[1]; C[1] ^= A[y+1];
 184           A[y+2] ^= D[2]; C[2] ^= A[y+2];
 185           A[y+3] ^= D[3]; C[3] ^= A[y+3];
 186           A[y+4] ^= D[4]; C[4] ^= A[y+4];
 187         }
 188     }
 189 #undef A
 190 }