SM3中的FF2和GG2函数 - emmansun/gmsm GitHub Wiki
定义
$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)$
等价公式
$FF2(X, Y, Z) = (X \land Y) \bigoplus (X \land Z) \bigoplus (Y \land Z)$
$GG2(X, Y, Z) = (X \land Y) \bigoplus (\lnot X \land Z) = (X \land Y) \bigoplus ((1 \bigoplus X) \land Z) = (X \land Y) \bigoplus (X \land Z) \bigoplus Z = (Y \bigoplus Z) \land X \bigoplus Z$
GG2等价公式初次见于Intel® Integrated Performance Primitives Cryptography
应用
特别是GG2,其等价公式相比原来的公式,因其简单,具有一点点性能优势(不明显),也可以省一个寄存器,还有就是ANDN指令属于BMI1,有些老机器不支持。
原公式:
MOVL f, y3; \
ANDL e, y3; \ // y3 = e AND f
ANDNL g, e, y1; \ // y1 = NOT(e) AND g
ORL y3, y1; \ // y1 = (e AND f) OR (NOT(e) AND g)
等价公式:
MOVL f, y1; \
XORL g, y1; \
ANDL e, y1; \
XORL g, y1; \ // y1 = GG2(e, f, g)
验证
X | Y | Z | $(X \land Y) \lor (X \land Z) \lor (Y \land Z)$ | $(X \land Y) \bigoplus (X \land Z) \bigoplus (Y \land Z)$ | $(X \land Y) \lor (\lnot X \land Z)$ | $(Y \bigoplus Z) \land X \bigoplus Z$ |
---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 | 0 | 1 | 1 |
0 | 1 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 1 | 1 | 0 | 0 |
1 | 1 | 0 | 1 | 1 | 1 | 1 |
1 | 1 | 1 | 1 | 1 | 1 | 1 |
证明
Ask help https://math.stackexchange.com/questions/4775054/how-to-prove-below-two-logic-formulas
$GG2(X,Y,Z)$
= $(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)$
$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)$
= $(\lnot X \lor (\lnot X \land \lnot Z) \lor (\lnot X \land Y) \lor (\lnot X \land \lnot Y) \lor (\lnot Z \land \lnot Y) \lor (Z \land \lnot X) \lor (Z \land Y)) \land (Y \land Z)$
= $(\lnot X \lor (\lnot X \land \lnot Z) \lor (Z \land \lnot X) \lor (\lnot X \land Y) \lor (\lnot X \land \lnot Y) \lor (\lnot Z \land \lnot Y) \lor (Z \land Y)) \land
(Y \land Z) $
= $(\lnot X \lor ((\lnot X \land \lnot Z) \lor (Z \land \lnot X)) \lor ((\lnot X \land Y) \lor (\lnot X \land \lnot Y)) \lor (\lnot Z \land \lnot Y) \lor (Z \land Y)) \land (Y \land Z) $
= $(\lnot X \lor (\lnot Z \land \lnot Y) \lor (Z \land 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)$
相关知识:
- $A \bigoplus B = (\lnot A \land B) \lor (A \land \lnot B) $
- Boolean algebra
- 布尔代数运算律