9
$\begingroup$

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.

$\endgroup$
14
$\begingroup$

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).

$\endgroup$
  • 5
    $\begingroup$ I believe $Ch$ actually stands for "Choose"; the $x$ input chooses whether to take the input from $y$ or from $z$ $\endgroup$ – poncho Nov 13 '12 at 19:03
  • 5
    $\begingroup$ I think any of those xors could be replaced with (i)ors without changing any outputs. $\hspace{.6 in}$ $\endgroup$ – user991 Nov 13 '12 at 19:30
  • 2
    $\begingroup$ @alex: For Ch, shop for a 2-input digital multiplexer; but good luck for Maj, majority gates are a rarity. Seriously, nowadays, this is a job for software, GPUs, programmable logic, ASICs, not discrete logic gates that one purchases as such. $\endgroup$ – fgrieu Nov 14 '12 at 9:56
  • 5
    $\begingroup$ @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. $\endgroup$ – fgrieu Nov 14 '12 at 12:47
  • 2
    $\begingroup$ @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$. $\endgroup$ – poncho Oct 30 '17 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.