sha3-permute.c

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