Bitcoin ABC  0.24.7
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/common.h>
9 #include <crypto/sha3.h>
10 #include <span.h>
11 
12 #include <algorithm>
13 #include <array> // For std::begin and std::end.
14 #include <cstdint>
15 
16 // Internal implementation code.
17 namespace {
18 uint64_t Rotl(uint64_t x, int n) {
19  return (x << n) | (x >> (64 - n));
20 }
21 } // namespace
22 
23 void KeccakF(uint64_t (&st)[25]) {
24  static constexpr uint64_t RNDC[24] = {
25  0x0000000000000001, 0x0000000000008082, 0x800000000000808a,
26  0x8000000080008000, 0x000000000000808b, 0x0000000080000001,
27  0x8000000080008081, 0x8000000000008009, 0x000000000000008a,
28  0x0000000000000088, 0x0000000080008009, 0x000000008000000a,
29  0x000000008000808b, 0x800000000000008b, 0x8000000000008089,
30  0x8000000000008003, 0x8000000000008002, 0x8000000000000080,
31  0x000000000000800a, 0x800000008000000a, 0x8000000080008081,
32  0x8000000000008080, 0x0000000080000001, 0x8000000080008008};
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);
45  st[0] ^= t;
46  st[5] ^= t;
47  st[10] ^= t;
48  st[15] ^= t;
49  st[20] ^= t;
50  t = bc0 ^ Rotl(bc2, 1);
51  st[1] ^= t;
52  st[6] ^= t;
53  st[11] ^= t;
54  st[16] ^= t;
55  st[21] ^= t;
56  t = bc1 ^ Rotl(bc3, 1);
57  st[2] ^= t;
58  st[7] ^= t;
59  st[12] ^= t;
60  st[17] ^= t;
61  st[22] ^= t;
62  t = bc2 ^ Rotl(bc4, 1);
63  st[3] ^= t;
64  st[8] ^= t;
65  st[13] ^= t;
66  st[18] ^= t;
67  st[23] ^= t;
68  t = bc3 ^ Rotl(bc0, 1);
69  st[4] ^= t;
70  st[9] ^= t;
71  st[14] ^= t;
72  st[19] ^= t;
73  st[24] ^= t;
74 
75  // Rho Pi
76  t = st[1];
77  bc0 = st[10];
78  st[10] = Rotl(t, 1);
79  t = bc0;
80  bc0 = st[7];
81  st[7] = Rotl(t, 3);
82  t = bc0;
83  bc0 = st[11];
84  st[11] = Rotl(t, 6);
85  t = bc0;
86  bc0 = st[17];
87  st[17] = Rotl(t, 10);
88  t = bc0;
89  bc0 = st[18];
90  st[18] = Rotl(t, 15);
91  t = bc0;
92  bc0 = st[3];
93  st[3] = Rotl(t, 21);
94  t = bc0;
95  bc0 = st[5];
96  st[5] = Rotl(t, 28);
97  t = bc0;
98  bc0 = st[16];
99  st[16] = Rotl(t, 36);
100  t = bc0;
101  bc0 = st[8];
102  st[8] = Rotl(t, 45);
103  t = bc0;
104  bc0 = st[21];
105  st[21] = Rotl(t, 55);
106  t = bc0;
107  bc0 = st[24];
108  st[24] = Rotl(t, 2);
109  t = bc0;
110  bc0 = st[4];
111  st[4] = Rotl(t, 14);
112  t = bc0;
113  bc0 = st[15];
114  st[15] = Rotl(t, 27);
115  t = bc0;
116  bc0 = st[23];
117  st[23] = Rotl(t, 41);
118  t = bc0;
119  bc0 = st[19];
120  st[19] = Rotl(t, 56);
121  t = bc0;
122  bc0 = st[13];
123  st[13] = Rotl(t, 8);
124  t = bc0;
125  bc0 = st[12];
126  st[12] = Rotl(t, 25);
127  t = bc0;
128  bc0 = st[2];
129  st[2] = Rotl(t, 43);
130  t = bc0;
131  bc0 = st[20];
132  st[20] = Rotl(t, 62);
133  t = bc0;
134  bc0 = st[14];
135  st[14] = Rotl(t, 18);
136  t = bc0;
137  bc0 = st[22];
138  st[22] = Rotl(t, 39);
139  t = bc0;
140  bc0 = st[9];
141  st[9] = Rotl(t, 61);
142  t = bc0;
143  bc0 = st[6];
144  st[6] = Rotl(t, 20);
145  t = bc0;
146  st[1] = Rotl(t, 44);
147 
148  // Chi Iota
149  bc0 = st[0];
150  bc1 = st[1];
151  bc2 = st[2];
152  bc3 = st[3];
153  bc4 = st[4];
154  st[0] = bc0 ^ (~bc1 & bc2) ^ RNDC[round];
155  st[1] = bc1 ^ (~bc2 & bc3);
156  st[2] = bc2 ^ (~bc3 & bc4);
157  st[3] = bc3 ^ (~bc4 & bc0);
158  st[4] = bc4 ^ (~bc0 & bc1);
159  bc0 = st[5];
160  bc1 = st[6];
161  bc2 = st[7];
162  bc3 = st[8];
163  bc4 = st[9];
164  st[5] = bc0 ^ (~bc1 & bc2);
165  st[6] = bc1 ^ (~bc2 & bc3);
166  st[7] = bc2 ^ (~bc3 & bc4);
167  st[8] = bc3 ^ (~bc4 & bc0);
168  st[9] = bc4 ^ (~bc0 & bc1);
169  bc0 = st[10];
170  bc1 = st[11];
171  bc2 = st[12];
172  bc3 = st[13];
173  bc4 = st[14];
174  st[10] = bc0 ^ (~bc1 & bc2);
175  st[11] = bc1 ^ (~bc2 & bc3);
176  st[12] = bc2 ^ (~bc3 & bc4);
177  st[13] = bc3 ^ (~bc4 & bc0);
178  st[14] = bc4 ^ (~bc0 & bc1);
179  bc0 = st[15];
180  bc1 = st[16];
181  bc2 = st[17];
182  bc3 = st[18];
183  bc4 = st[19];
184  st[15] = bc0 ^ (~bc1 & bc2);
185  st[16] = bc1 ^ (~bc2 & bc3);
186  st[17] = bc2 ^ (~bc3 & bc4);
187  st[18] = bc3 ^ (~bc4 & bc0);
188  st[19] = bc4 ^ (~bc0 & bc1);
189  bc0 = st[20];
190  bc1 = st[21];
191  bc2 = st[22];
192  bc3 = st[23];
193  bc4 = st[24];
194  st[20] = bc0 ^ (~bc1 & bc2);
195  st[21] = bc1 ^ (~bc2 & bc3);
196  st[22] = bc2 ^ (~bc3 & bc4);
197  st[23] = bc3 ^ (~bc4 & bc0);
198  st[24] = bc4 ^ (~bc0 & bc1);
199  }
200 }
201 
203  if (m_bufsize && m_bufsize + data.size() >= sizeof(m_buffer)) {
204  // Fill the buffer and process it.
205  std::copy(data.begin(), data.begin() + sizeof(m_buffer) - m_bufsize,
206  m_buffer + m_bufsize);
207  data = data.subspan(sizeof(m_buffer) - m_bufsize);
209  m_bufsize = 0;
210  if (m_pos == RATE_BUFFERS) {
211  KeccakF(m_state);
212  m_pos = 0;
213  }
214  }
215  while (data.size() >= sizeof(m_buffer)) {
216  // Process chunks directly from the buffer.
217  m_state[m_pos++] ^= ReadLE64(data.data());
218  data = data.subspan(8);
219  if (m_pos == RATE_BUFFERS) {
220  KeccakF(m_state);
221  m_pos = 0;
222  }
223  }
224  if (data.size()) {
225  // Keep the remainder in the buffer.
226  std::copy(data.begin(), data.end(), m_buffer + m_bufsize);
227  m_bufsize += data.size();
228  }
229  return *this;
230 }
231 
233  assert(output.size() == OUTPUT_SIZE);
234  std::fill(m_buffer + m_bufsize, m_buffer + sizeof(m_buffer), 0);
235  m_buffer[m_bufsize] ^= 0x06;
237  m_state[RATE_BUFFERS - 1] ^= 0x8000000000000000;
238  KeccakF(m_state);
239  for (unsigned i = 0; i < 4; ++i) {
240  WriteLE64(output.data() + 8 * i, m_state[i]);
241  }
242  return *this;
243 }
244 
246  m_bufsize = 0;
247  m_pos = 0;
248  std::fill(std::begin(m_state), std::end(m_state), 0);
249  return *this;
250 }
SHA3_256::OUTPUT_SIZE
static constexpr size_t OUTPUT_SIZE
Definition: sha3.h:33
SHA3_256::Finalize
SHA3_256 & Finalize(Span< uint8_t > output)
Definition: sha3.cpp:232
SHA3_256::m_bufsize
unsigned m_bufsize
Definition: sha3.h:20
SHA3_256::m_buffer
uint8_t m_buffer[8]
Definition: sha3.h:19
SHA3_256
Definition: sha3.h:16
ReadLE64
static uint64_t ReadLE64(const uint8_t *ptr)
Definition: common.h:29
KeccakF
void KeccakF(uint64_t(&st)[25])
The Keccak-f[1600] transform.
Definition: sha3.cpp:23
SHA3_256::Reset
SHA3_256 & Reset()
Definition: sha3.cpp:245
Span::size
constexpr std::size_t size() const noexcept
Definition: span.h:179
Span
A Span is an object that can refer to a contiguous sequence of objects.
Definition: span.h:83
SHA3_256::m_state
uint64_t m_state[25]
Definition: sha3.h:18
SHA3_256::m_pos
unsigned m_pos
Definition: sha3.h:21
WriteLE64
static void WriteLE64(uint8_t *ptr, uint64_t x)
Definition: common.h:45
span.h
Span::begin
constexpr C * begin() const noexcept
Definition: span.h:169
SHA3_256::RATE_BUFFERS
static constexpr unsigned RATE_BUFFERS
Sponge rate expressed as a multiple of the buffer size.
Definition: sha3.h:27
Span::data
constexpr C * data() const noexcept
Definition: span.h:168
common.h
sha3.h
Span::end
constexpr C * end() const noexcept
Definition: span.h:170
Span::subspan
CONSTEXPR_IF_NOT_DEBUG Span< C > subspan(std::size_t offset) const noexcept
Definition: span.h:185
SHA3_256::Write
SHA3_256 & Write(Span< const uint8_t > data)
Definition: sha3.cpp:202