0

Below 2 formulas are used for SM3 algorithm, first one is FF2 & second one is GG2.

  1. FF2(X,Y,Z) = $(X \land Y) \lor (X \land Z) \lor (Y \land Z)$
  2. GG2(X,Y,Z) = $(X \land Y) \lor (\lnot X \land Z)$

And I also found some implementations used below alternatives:

  1. FF2(X,Y,Z) = $(X \land Y) \bigoplus (X \land Z) \bigoplus (Y \land Z)$
  2. GG2(X,Y,Z) = $(Y \bigoplus Z) \land X \bigoplus Z$

I can verify them with X,Y,Z value table, but I can't derive them from known formulas, for example:
$X\bigoplus Y$ = $(\lnot X \land Y) \lor (X \land \lnot Y)$

For second one, I can only get:
$(X \land Y) \lor (\lnot X \land Z)$ = $(X \land Y) \lor ((X \land Z) \bigoplus Z)$
$(Y \bigoplus Z) \land X \bigoplus Z$ = $(X \land Y) \bigoplus (X \land Z) \bigoplus Z$

For GG2, I can prove $(X \land Y) \lor (\lnot X \land Z)$ = $(X \land Y) \bigoplus (\lnot X \land Z)$ now.
$(X \land Y) \bigoplus (\lnot X \land Z)$
= $(\lnot (X \land Y) \land (\lnot X \land Z)) \lor ((X \land Y) \land (\lnot (\lnot X \land Z)))$
= $((\lnot X \lor \lnot Y) \land (\lnot X \land Z)) \lor ((X \land Y) \land (X \lor \lnot Z))$
= $(\lnot X \land Z) \lor (\lnot X \land \lnot Y \land Z) \lor (X \land Y) \lor (X \land Y \land \lnot Z) $
= $((\lnot X \land Z) \lor (\lnot X \land Z \land \lnot Y)) \lor ((X \land Y) \lor (X \land Y \land \lnot Z))$
= $((X \land Y) \land (1 \lor \lnot Z)) \lor ((\lnot X \land Z) \land (1 \lor \lnot Y))$
= $(X \land Y) \lor (\lnot X \land Z)$

For FF2, $FF2(X, Y, Z) = (X \land Y) \bigoplus (X \land Z) \bigoplus (Y \land Z)$
$(X \land Y) \bigoplus (X \land Z) $
= $X \land (Y \bigoplus Z)$
= $X \land ((Y \land \lnot Z) \lor (\lnot Y \land Z))$
= $(X \land Y \land \lnot Z) \lor (X \land Z \land \lnot Y)$

$(X \land Y) \bigoplus (X \land Z) \bigoplus (Y \land Z)$
= $(\lnot((X \land Y \land \lnot Z) \lor (X \land Z \land \lnot Y)) \land (Y \land Z)) \lor (((X \land Y \land \lnot Z) \lor (X \land Z \land \lnot Y)) \land (\lnot Y \lor \lnot Z))$

$\lnot((X \land Y \land \lnot Z) \lor (X \land Z \land \lnot Y)) \land (Y \land Z)$
= $\lnot(X \land Y \land \lnot Z) \land \lnot(X \land Z \land \lnot Y) \land (Y \land Z)$
= $(\lnot X \lor \lnot Y \lor Z) \land (\lnot X \lor \lnot Z \lor Y) \land (Y \land Z)$
= $(Y \land Z)$

$((X \land Y \land \lnot Z) \lor (X \land Z \land \lnot Y)) \land (\lnot Y \lor \lnot Z)$
= $(X \land Y \land \lnot Z) \lor (X \land Z \land \lnot Y)$

$(X \land Y \land \lnot Z) \lor (X \land Z \land \lnot Y) \lor (Y \land Z)$
= $(X \land Y \land \lnot Z) \lor (X \land Z \land \lnot Y) \lor (Y \land Z) \lor (X \land Y \land Z) \lor (X \land Y \land Z)$
= $(X \land Y \land \lnot Z) \lor (X \land Y \land Z) \lor (X \land Z \land \lnot Y) \lor (X \land Y \land Z) \lor (Y \land Z)$
= $(X \land Y) \lor (X \land Z) \lor (Y \land Z)$

Emman Sun
  • 101
  • 1
    Hi! To avoid down-votes and close-votes, please provide us some context for this question, such as: (a) Is this homework? (b) If so, what course are you taking? (c) What specific topic are you covering at the moment? (d) What do you know that you think might be connected? (e) If you're stuck, what are you stuck on? For example, do you know what to apply, but don't know how to apply it, or do you not know what to apply? Please put these facts in your original post, not as responses to this comment, as comments may be deleted without warning. – Brian Tung Sep 25 '23 at 03:10
  • For instance, you might add what transformation rules you know to apply, and how they justify your current attempts. Thanks! – Brian Tung Sep 25 '23 at 03:11
  • 1
    There are 8 possible assignments to $X,Y,Z$. – copper.hat Sep 25 '23 at 03:13

0 Answers0