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.
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
8
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).
-
6$\begingroup$ I believe $Ch$ actually stands for "Choose"; the $x$ input chooses whether to take the input from $y$ or from $z$ $\endgroup$– ponchoCommented Nov 13, 2012 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$– user991Commented Nov 13, 2012 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 ♦Commented Nov 14, 2012 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 ♦Commented Nov 14, 2012 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$– ponchoCommented Oct 30, 2017 at 14:51