Bitcoin Core  0.20.99
P2P Digital Currency
sha3.cpp
Go to the documentation of this file.
1 // Copyright (c) 2020 The Bitcoin Core developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 
5 // Based on https://github.com/mjosaarinen/tiny_sha3/blob/master/sha3.c
6 // by Markku-Juhani O. Saarinen <mjos@iki.fi>
7 
8 #include <crypto/sha3.h>
9 #include <crypto/common.h>
10 #include <span.h>
11 
12 #include <algorithm>
13 #include <array> // For std::begin and std::end.
14 
15 #include <stdint.h>
16 
17 // Internal implementation code.
18 namespace
19 {
20 uint64_t Rotl(uint64_t x, int n) { return (x << n) | (x >> (64 - n)); }
21 } // namespace
22 
23 void KeccakF(uint64_t (&st)[25])
24 {
25  static constexpr uint64_t RNDC[24] = {
26  0x0000000000000001, 0x0000000000008082, 0x800000000000808a, 0x8000000080008000,
27  0x000000000000808b, 0x0000000080000001, 0x8000000080008081, 0x8000000000008009,
28  0x000000000000008a, 0x0000000000000088, 0x0000000080008009, 0x000000008000000a,
29  0x000000008000808b, 0x800000000000008b, 0x8000000000008089, 0x8000000000008003,
30  0x8000000000008002, 0x8000000000000080, 0x000000000000800a, 0x800000008000000a,
31  0x8000000080008081, 0x8000000000008080, 0x0000000080000001, 0x8000000080008008
32  };
33  static constexpr int ROUNDS = 24;
34 
35  for (int round = 0; round < ROUNDS; ++round) {
36  uint64_t bc0, bc1, bc2, bc3, bc4, t;
37 
38  // Theta
39  bc0 = st[0] ^ st[5] ^ st[10] ^ st[15] ^ st[20];
40  bc1 = st[1] ^ st[6] ^ st[11] ^ st[16] ^ st[21];
41  bc2 = st[2] ^ st[7] ^ st[12] ^ st[17] ^ st[22];
42  bc3 = st[3] ^ st[8] ^ st[13] ^ st[18] ^ st[23];
43  bc4 = st[4] ^ st[9] ^ st[14] ^ st[19] ^ st[24];
44  t = bc4 ^ Rotl(bc1, 1); st[0] ^= t; st[5] ^= t; st[10] ^= t; st[15] ^= t; st[20] ^= t;
45  t = bc0 ^ Rotl(bc2, 1); st[1] ^= t; st[6] ^= t; st[11] ^= t; st[16] ^= t; st[21] ^= t;
46  t = bc1 ^ Rotl(bc3, 1); st[2] ^= t; st[7] ^= t; st[12] ^= t; st[17] ^= t; st[22] ^= t;
47  t = bc2 ^ Rotl(bc4, 1); st[3] ^= t; st[8] ^= t; st[13] ^= t; st[18] ^= t; st[23] ^= t;
48  t = bc3 ^ Rotl(bc0, 1); st[4] ^= t; st[9] ^= t; st[14] ^= t; st[19] ^= t; st[24] ^= t;
49 
50  // Rho Pi
51  t = st[1];
52  bc0 = st[10]; st[10] = Rotl(t, 1); t = bc0;
53  bc0 = st[7]; st[7] = Rotl(t, 3); t = bc0;
54  bc0 = st[11]; st[11] = Rotl(t, 6); t = bc0;
55  bc0 = st[17]; st[17] = Rotl(t, 10); t = bc0;
56  bc0 = st[18]; st[18] = Rotl(t, 15); t = bc0;
57  bc0 = st[3]; st[3] = Rotl(t, 21); t = bc0;
58  bc0 = st[5]; st[5] = Rotl(t, 28); t = bc0;
59  bc0 = st[16]; st[16] = Rotl(t, 36); t = bc0;
60  bc0 = st[8]; st[8] = Rotl(t, 45); t = bc0;
61  bc0 = st[21]; st[21] = Rotl(t, 55); t = bc0;
62  bc0 = st[24]; st[24] = Rotl(t, 2); t = bc0;
63  bc0 = st[4]; st[4] = Rotl(t, 14); t = bc0;
64  bc0 = st[15]; st[15] = Rotl(t, 27); t = bc0;
65  bc0 = st[23]; st[23] = Rotl(t, 41); t = bc0;
66  bc0 = st[19]; st[19] = Rotl(t, 56); t = bc0;
67  bc0 = st[13]; st[13] = Rotl(t, 8); t = bc0;
68  bc0 = st[12]; st[12] = Rotl(t, 25); t = bc0;
69  bc0 = st[2]; st[2] = Rotl(t, 43); t = bc0;
70  bc0 = st[20]; st[20] = Rotl(t, 62); t = bc0;
71  bc0 = st[14]; st[14] = Rotl(t, 18); t = bc0;
72  bc0 = st[22]; st[22] = Rotl(t, 39); t = bc0;
73  bc0 = st[9]; st[9] = Rotl(t, 61); t = bc0;
74  bc0 = st[6]; st[6] = Rotl(t, 20); t = bc0;
75  st[1] = Rotl(t, 44);
76 
77  // Chi Iota
78  bc0 = st[0]; bc1 = st[1]; bc2 = st[2]; bc3 = st[3]; bc4 = st[4];
79  st[0] = bc0 ^ (~bc1 & bc2) ^ RNDC[round];
80  st[1] = bc1 ^ (~bc2 & bc3);
81  st[2] = bc2 ^ (~bc3 & bc4);
82  st[3] = bc3 ^ (~bc4 & bc0);
83  st[4] = bc4 ^ (~bc0 & bc1);
84  bc0 = st[5]; bc1 = st[6]; bc2 = st[7]; bc3 = st[8]; bc4 = st[9];
85  st[5] = bc0 ^ (~bc1 & bc2);
86  st[6] = bc1 ^ (~bc2 & bc3);
87  st[7] = bc2 ^ (~bc3 & bc4);
88  st[8] = bc3 ^ (~bc4 & bc0);
89  st[9] = bc4 ^ (~bc0 & bc1);
90  bc0 = st[10]; bc1 = st[11]; bc2 = st[12]; bc3 = st[13]; bc4 = st[14];
91  st[10] = bc0 ^ (~bc1 & bc2);
92  st[11] = bc1 ^ (~bc2 & bc3);
93  st[12] = bc2 ^ (~bc3 & bc4);
94  st[13] = bc3 ^ (~bc4 & bc0);
95  st[14] = bc4 ^ (~bc0 & bc1);
96  bc0 = st[15]; bc1 = st[16]; bc2 = st[17]; bc3 = st[18]; bc4 = st[19];
97  st[15] = bc0 ^ (~bc1 & bc2);
98  st[16] = bc1 ^ (~bc2 & bc3);
99  st[17] = bc2 ^ (~bc3 & bc4);
100  st[18] = bc3 ^ (~bc4 & bc0);
101  st[19] = bc4 ^ (~bc0 & bc1);
102  bc0 = st[20]; bc1 = st[21]; bc2 = st[22]; bc3 = st[23]; bc4 = st[24];
103  st[20] = bc0 ^ (~bc1 & bc2);
104  st[21] = bc1 ^ (~bc2 & bc3);
105  st[22] = bc2 ^ (~bc3 & bc4);
106  st[23] = bc3 ^ (~bc4 & bc0);
107  st[24] = bc4 ^ (~bc0 & bc1);
108  }
109 }
110 
112 {
113  if (m_bufsize && m_bufsize + data.size() >= sizeof(m_buffer)) {
114  // Fill the buffer and process it.
115  std::copy(data.begin(), data.begin() + sizeof(m_buffer) - m_bufsize, m_buffer + m_bufsize);
116  data = data.subspan(sizeof(m_buffer) - m_bufsize);
118  m_bufsize = 0;
119  if (m_pos == RATE_BUFFERS) {
120  KeccakF(m_state);
121  m_pos = 0;
122  }
123  }
124  while (data.size() >= sizeof(m_buffer)) {
125  // Process chunks directly from the buffer.
126  m_state[m_pos++] ^= ReadLE64(data.data());
127  data = data.subspan(8);
128  if (m_pos == RATE_BUFFERS) {
129  KeccakF(m_state);
130  m_pos = 0;
131  }
132  }
133  if (data.size()) {
134  // Keep the remainder in the buffer.
135  std::copy(data.begin(), data.end(), m_buffer + m_bufsize);
136  m_bufsize += data.size();
137  }
138  return *this;
139 }
140 
142 {
143  assert(output.size() == OUTPUT_SIZE);
144  std::fill(m_buffer + m_bufsize, m_buffer + sizeof(m_buffer), 0);
145  m_buffer[m_bufsize] ^= 0x06;
147  m_state[RATE_BUFFERS - 1] ^= 0x8000000000000000;
148  KeccakF(m_state);
149  for (unsigned i = 0; i < 4; ++i) {
150  WriteLE64(output.data() + 8 * i, m_state[i]);
151  }
152  return *this;
153 }
154 
156 {
157  m_bufsize = 0;
158  m_pos = 0;
159  std::fill(std::begin(m_state), std::end(m_state), 0);
160  return *this;
161 }
CONSTEXPR_IF_NOT_DEBUG Span< C > subspan(std::size_t offset) const noexcept
Definition: span.h:160
void KeccakF(uint64_t(&st)[25])
The Keccak-f[1600] transform.
Definition: sha3.cpp:23
SHA3_256 & Write(Span< const unsigned char > data)
Definition: sha3.cpp:111
constexpr C * end() const noexcept
Definition: span.h:142
static void WriteLE64(unsigned char *ptr, uint64_t x)
Definition: common.h:50
Definition: sha3.h:16
constexpr std::size_t size() const noexcept
Definition: span.h:153
static constexpr size_t OUTPUT_SIZE
Definition: sha3.h:33
SHA3_256 & Finalize(Span< unsigned char > output)
Definition: sha3.cpp:141
uint64_t m_state[25]
Definition: sha3.h:19
unsigned char m_buffer[8]
Definition: sha3.h:20
unsigned m_bufsize
Definition: sha3.h:21
constexpr C * begin() const noexcept
Definition: span.h:141
SHA3_256 & Reset()
Definition: sha3.cpp:155
constexpr C * data() const noexcept
Definition: span.h:140
static uint64_t ReadLE64(const unsigned char *ptr)
Definition: common.h:31
A Span is an object that can refer to a contiguous sequence of objects.
Definition: span.h:82
unsigned m_pos
Definition: sha3.h:22
static constexpr unsigned RATE_BUFFERS
Sponge rate expressed as a multiple of the buffer size.
Definition: sha3.h:28