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

-
Welcome to Crypto.SE! Maj and Ch are defined in the specification of SHA-256; that should answer your question. For future reference, on this site we do expect folks to do some research on their own before asking, so you might want to make sure to do that in the future -- and let me also point you to the FAQ, which has lots of useful information! –  D.W. Nov 14 '12 at 3:45
@D.W.: the question has the redeeming value that finding what the abbreviations Maj and Ch (especially) stand for is not quite trivial, and nowhere to be found in the standard. OTOH it is homework in poor disguise, with no indication of attempt to start doing something about it. –  fgrieu Nov 14 '12 at 12:54

The definitions given in FIPS 180-4 are $$\mathtt{Maj}(x, y, z)=(x∧y)⊕(x∧z)⊕(y∧z)$$ $$\mathtt{Ch}(x,y,z)=(x∧y)⊕(¬x∧z)$$ where $∧$ is bitwise AND, $⊕$ is bitwise exclusive-OR, and $¬$ is bitwise negation. The functions are defined for bit vectors (of 32 bits in case fo SHA-256).

I'm positive $\mathtt{Maj}$ stands for majority: the result is set according to the majority of the 3 inputs.

As of $\mathtt{Ch}$, I'm left guessing that's for channel multiplexer told by poncho that stands for choose, as the $x$ input chooses if the output is from $y$ or $z$.

-
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
I think any of those xors could be replaced with (i)ors without changing any outputs. $\hspace{.6 in}$ –  Ricky Demer Nov 13 '12 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 '12 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 '12 at 12:47

@fgrieu Thanks for sticking up for us noobs! Here's my contribution to that part of the discussion: http://xkcd.com/1053/

As to the original question, I joined SE today when this thread was the second link I clicked when trying to research the same question myself after wanting more than I've found in the FIPS so far.

I haven't gone deeper than Wikipedia yet, but I'm satisfied till I find reason to doubt that the Majority function is defined thusly:

"A majority gate is a logical gate used in circuit complexity and other applications of Boolean circuits. A majority gate returns true if and only if more than 50% of its inputs are true."

http://en.wikipedia.org/wiki/Majority_function

We still haven't found an authoritative sounding answer on ch yet that I see, (I didn't dig more then ten minutes because all my new search terms started returning more and more purple links. But it looks like a ternary-if else statement written using basic logic gates... I've got some time on a bus right now to see if I can demonstrate equivalence. Hopefully I'll BRB.

Yup, it's me again. I'm back.

I was glancing at Maj instead of Ch, when I said ternary. Ch looks like a nested if then statement to me. Here's a quick pseudocode that I worked up.

I'm on a mobile so I'm going to change the left and right terms of the Ch XOR expression to L and R, respectively for ease of typing. XOR returning true when exactly one of its inputs is true, and false otherwise, of course. I'd bet dollars to donuts that the Ch function represents the simplest Boolean computational function of all the required comparisons to be able to choose x, y or z, because that can be used as a direct template for the most efficient (based on lowest number of gates needed to complete the computational circuit). And since we know hashing can be time consulting for a stack machine, an efficient ASCIC FOR hashing is very desirable.

Here's what a pseudo code would look like to compute the same results. Sorry. Too laborious to put in all the brackets on my mobile, but I think the logic is sound if you can follow it. If you're super new and getting tripped up on the code (like I certainly would have this time last year) let me know, I,ll try a slower walk through.

If R If L Return false Else Return true

Else If !L Return false Else Return true

I expect that extending this presses further to get back to the original variables x, y, z will allow a similar nested if then else structure that allows the comparison of three values in such a way that which ever value is returns the truth value first is the letter selected,

That's my working hypothesis, what's yours?

-MJJ

-
How is this an answer to the original question? Also, a guess "I'd bet dollars to donuts that the Ch function represents the simplest Boolean computational function..." isn't that useful, when the definitions are sitting in FIPS 180-4 (just as fgrieu pointed out last year) –  poncho 2 days ago
Perhaps you don't understand Stack Exchange. It's not designed to be a discussion forum, or somewhere where you work out ideas out loud. Instead, it's strictly a Question&Answer forum; questions get asked, and if someone knows the answer, they answer. If you don't know the answer, it's better to leave that question to someone else. If you are looking for a crypto-related discussion forum, might I suggest the Usenet group sci.crypt –  poncho 2 days ago