13

I'm guessing they're some kind of standard function but what do they do and what do the names mean? A little explaination or link me to an article would be great.

e-sushi
  • 17,617
  • 12
  • 80
  • 223
alex
  • 141
  • 1
  • 4

1 Answers1

17

The definitions given in FIPS 180-4 are $$\begin{align} \operatorname{Maj}(x,y,z)&=(x\wedge y)\oplus(x\wedge z)\oplus(y\wedge z)\\ \operatorname{Ch}(x,y,z)&=(x\wedge y)\oplus(\neg x\wedge z) \end{align}$$ where $\wedge$ is bitwise AND, $\oplus$ is bitwise exclusive-OR, and $\neg $ is bitwise negation. The functions are defined for bit vectors (of 32 bits in case fo SHA-256).

$\operatorname{Maj}$ stands for majority: for each bit index, that result bit is according to the majority of the 3 inputs bits for $x$ $y$ and $z$ at this index.

$\operatorname{Ch}$ stands for choose (source: poncho) or choice, as the $x$ input chooses if the output is from $y$ or from $z$. More precisely, for each bit index, that result bit is according to the bit from $y$ (or respectively $z$ ) at this index, depending on if the bit from $x$ at this index is 1 (or respectively 0).

fgrieu
  • 131,696
  • 12
  • 284
  • 553
  • 6
    I believe $Ch$ actually stands for "Choose"; the $x$ input chooses whether to take the input from $y$ or from $z$ – poncho Nov 13 '12 at 19:03
  • 5
    I think any of those xors could be replaced with (i)ors without changing any outputs. $\hspace{.6 in}$ –  Nov 13 '12 at 19:30
  • 2
    @alex: For Ch, shop for a [2-input digital multiplexer](http://www.nxp.com/products/logic/digital_multiplexers/series/74AUP1G157.html); but good luck for Maj, [majority gates](http://www.datasheetcatalog.org/datasheet/motorola/MC14530.pdf) are a rarity. Seriously, nowadays, this is a job for software, GPUs, programmable logic, ASICs, not discrete logic gates that one purchases as such. – fgrieu Nov 14 '12 at 09:56
  • 5
    @Ricky Demer: Indeed, the three XOR can be replaced by OR. I conjecture FIPS 180-4 uses XOR because in the context, the results are often fed to XOR or the closely-related addition $\bmod 2^{32}$; therefore cancellation of terms (if there was any) would be easier to spot with XOR than with OR. – fgrieu Nov 14 '12 at 12:47
  • @poncho How does $Ch$ work? – Melab Oct 27 '17 at 23:45
  • 2
    @Melab: if bit $i$ of $x$ is 1, then bit $i$ of the output is bit $i$ of $y$. If bit $i$ of $x$ is 0, then the output is bit $i$ of $z$. – poncho Oct 30 '17 at 14:51
  • @fgrieu - I'm working on a SHA-256 impl on Power8, which has hardware acceleration. `vec_sel` intrinsic can be used for *Ch*, but I am looking for something for *Maj*. Are you aware of a Power8 instruction for *Maj*. (Sorry to ask. IBM docs on its in-core crypto don't really exist. I saw you jumped into hardware, and thought you might have an answer). –  Feb 25 '18 at 12:08
  • @Melab In programming parlance, it's the ternary operator `x ? y : z` for each bit. – forest Jan 29 '19 at 04:29