keccak_f1600
stdlib/keccak/keccak_f1600.nbv
keccak_f1600(state)
Keccak-f[1600] permutation on a vector of 1600 bits.
Lane (x, y) occupies bits 64 * (x + 5 * y) .. 64 * (x + 5 * y) + 64, least significant bit first. This matches the byte order used by SHA-3/SHAKE, so the first rate bits of the state are the rate portion of the sponge.
Inputs must be bits. Outputs are bits.
- Calls
bits/and_bits,calloc,slice,valloc,bits/xor_bits,bits/xor_bits_vec- Precompiles
assert_eq!,clone!,concat!,constrain_mul!,div_floor!,len!,loop!,loop_flat_map!,modulo!,wtns!- Used by
keccak/keccak_sponge_shake
Source
# Keccak-f[1600] permutation on a vector of 1600 bits.
#
# Lane (x, y) occupies bits 64 * (x + 5 * y) .. 64 * (x + 5 * y) + 64, least
# significant bit first. This matches the byte order used by SHA-3/SHAKE, so
# the first `rate` bits of the state are the rate portion of the sponge.
#
# Inputs must be bits. Outputs are bits.
(state)
assert_eq! 1600, len! state
# rotation offsets indexed by x + 5 * y
static RHO = [0 1 62 28 27 36 44 6 55 20 3 10 43 25 39 41 45 15 21 8 18 2 61 56 14]
# round constants: bit j of round i (lane bit 2^j - 1) is RC[7 * i + j]
static RC = [
1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 1 1 1 1 0 1 0 0 0 0 1 1 1
1 1 1 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 1 1 1 0 1 0 1 0 1
0 1 1 1 0 0 0 0 0 1 1 0 0 0 1 0 1 0 1 1 0 0 1 1 0 0 1 0
1 1 1 1 1 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 1 0 1
0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 1 1 0 0 1 1
1 0 0 1 1 1 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 0 0 1 0 1 1 1
]
let mut a = state
static ones = valloc(1600, 1)
# the field inverse of 2, not integer division
static half = 1 / 2
loop! 24, round {
# theta: column parities c[64 * x + z] of the 5 planes. The planes are bits,
# so the parity is the sum s in [0, 5] reduced mod 2. c = s mod 2 and
# q1 = floor(s / 4) are bit hints, q0 = (s - c - 4 q1) * half with half the
# field inverse of 2 is a linear combination, and constraining all three to
# bits gives s = c + 2 q0 + 4 q1 over the integers.
# Three booleanity rows and two witness entries per column, all of them
# binary, against four xors and a materialization.
let s = slice((clone! a), 0, 320) + slice((clone! a), 320, 320) + slice((clone! a), 640, 320) + slice((clone! a), 960, 320) + slice((clone! a), 1280, 320)
let c = modulo! (clone! s), valloc(320, 2)
let q1 = div_floor! (clone! s), valloc(320, 4)
let q0 = (s - (clone! c) - valloc(320, 4) * (clone! q1)) * valloc(320, half)
constrain_mul! (clone! c), valloc(320, 1) - (clone! c), calloc(320)
constrain_mul! (clone! q1), valloc(320, 1) - q1, calloc(320)
constrain_mul! (clone! q0), valloc(320, 1) - q0, calloc(320)
# d[x] = c[x - 1] ^ rot(c[x + 1], 1), rotations as slices of a doubled lane
let c_prev = concat! slice((clone! c), 256, 64), slice((clone! c), 0, 256)
let c_next = loop_flat_map! 5, x {
static lane = 64 * (modulo! x + 1, 5)
slice((concat! slice((clone! c), lane, 64), slice((clone! c), lane, 64)), 63, 64)
}
let d = xor_bits_vec(c_prev, c_next)
let t = xor_bits_vec((clone! a), loop_flat_map! 5, y {
clone! d
})
# rho and pi: lane (X, Y) = rot(t[x][y], RHO[x][y]) with X = y and
# Y = 2x + 3y, so x = 3 (Y - 3 X) mod 5
let b = loop_flat_map! 25, dest {
static y = modulo! dest, 5
static x = modulo! 3 * (div_floor! dest, 5) + 45 - 9 * y, 5
static lane = 64 * (x + 5 * y)
static rot = RHO[x + 5 * y]
slice((concat! slice((clone! t), lane, 64), slice((clone! t), lane, 64)), 64 - rot, 64)
}
# chi: a[x][y] = b[x][y] ^ (!b[x + 1][y] & b[x + 2][y]) with the lanes of
# each plane shifted by one and two
let b1 = loop_flat_map! 5, y {
concat! slice((clone! b), 320 * y + 64, 256), slice((clone! b), 320 * y, 64)
}
let b2 = loop_flat_map! 5, y {
concat! slice((clone! b), 320 * y + 128, 192), slice((clone! b), 320 * y, 128)
}
# the xor outputs stay linear combinations of the products, they grow by a
# few terms per round and only the parities above are materialized
a = xor_bits_vec(b, and_bits((clone! ones) - b1, b2))
# iota
static mut bit = 1
loop! 7, j {
a[bit - 1] = xor_bits(a[bit - 1], RC[7 * round + j])
bit = bit * 2
}
}
# materialize the output state so the linear combinations do not keep growing
# across permutations, 1600 rows against the 38400 a per-round materialization
# would cost
wtns! a