Skip to content

SM3中的FF2和GG2函数

Jump to bottom
Sun Yimin edited this page Sep 26, 2023 · 29 revisions

定义

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

相关知识：

Clone this wiki locally