Below 2 formulas are used for SM3 algorithm, first one is FF2 & second one is GG2.
- FF2(X,Y,Z) = $(X \land Y) \lor (X \land Z) \lor (Y \land Z)$
- GG2(X,Y,Z) = $(X \land Y) \lor (\lnot X \land Z)$
And I also found some implementations used below alternatives:
- FF2(X,Y,Z) = $(X \land Y) \bigoplus (X \land Z) \bigoplus (Y \land Z)$
- 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)$