Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 3 down vote favorite

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.

share|improve this question
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

1 Answer

up vote 5 down vote accepted

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

share|improve this answer
1  
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
1  
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
1  
@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
1  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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