# What does Maj and Ch mean in SHA-256 algorithm?

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.

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

• I believe $Ch$ actually stands for "Choose"; the $x$ input chooses whether to take the input from $y$ or from $z$ Nov 13, 2012 at 19:03
• I think any of those xors could be replaced with (i)ors without changing any outputs. $\hspace{.6 in}$
– user991
Nov 13, 2012 at 19:30
• @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.
– fgrieu
Nov 14, 2012 at 9:56
• @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, 2012 at 12:47
• @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$. Oct 30, 2017 at 14:51