Anshel–Anshel–Goldfeld 密钥交换体系(Anshel–Anshel–Goldfeld key exchange)

原理（代数密钥建立协议，The algebraic key establishment protocol）

​ We now present an algebraic key establishment protocol which, in its most general form consists of a five–tuple

$$(U, V,\beta,\gamma_1, \gamma_2)$$

where $U$ and $V$ are feasibly computable monoids, and

$$\beta:U× U\rightarrow V,\ \ \ \gamma_i:U× V\rightarrow V\ \ (i=1,2)$$

are feasibly computable functions satisfying the following properties.

​ (i) For all elements $x, y_1, y_2 \in U$ ,

$$\beta(x,y_1\cdot y_2)=\beta(x,y_1)\cdot \beta(x,y_2)$$

​ (ii) For all elements $x, y \in U$ ,

$$\gamma_1(x,\beta(y,x))=\gamma_2(x,\beta(x,y))$$

​ (iii) Suppose $y_1, y_2, \cdots ,y_k \in U$ and $\beta(x, y_1), \beta(x, y_2), \cdots ,\beta(x, y_k)$ are publicly known for some secret element $x \in U$. Then, in general, it is infeasible to determine the secret element $x$ .

​ The users $A$ and $B$ are publicly assigned submonoids, $S_A, T_B \subseteq U$, respectively. Suppose that $S_A$ is generated by the elements

$$\{s_1,\cdots ,s_m\}$$

and $S_B$ is generated by $\{t_1,\cdots,t_n\}$.The protocol begins with user A choosing a secret element a in $S_A$ and transmitting the elements

$$\beta(a,t_i)\ \ \ \ \ \ i=1,\cdots,n.$$

Likewise, user $B$ chooses a secret element $b$ in $T$, transmits

$$\beta(b,s_i)\ \ \ \ \ \ i=1,\cdots,m.$$

It follows from property (iii) that even though the transmission is over a public channel, the secret elements $a$ and $b$ are secure. Property (i) above insures that user $A$ can compute the element

$$\beta(b,a),$$

and

$$\gamma_1(a,\beta(b,a)).$$

Likewise user $B$ can compute $\beta(a, b)$ and $\gamma_2(b, \beta(a, b))$. Recalling property (ii) above we see that

$$\kappa=\gamma_1(a,\beta(b,a))=\gamma_2(b,\beta(a,b))$$

can serve as an established key.

具体例子（群论协议，A group theoretic protocol）

In this illustration the monoid $U = V$ is a group, denoted $G$, and the users $A$ and $B$ are publicly assigned subgroups

$$S_A=\langle s_1,s_2,\cdots ,s_m\rangle,\ \ \ \ S_B=\langle t_1,t_2,\cdots ,t_n\rangle.$$

Here the function $\beta:G× G\rightarrow G$ is chosen to be conjugation,

$$\gamma_1(u,v)=u^{-1}v,\ \ \ \ \ \ \gamma_2(u,v)=v^{-1}u.$$

Users A and B choose secret elements $a \in S_A$ and $b \in S_B$ respectively, and user $A$ begins the protocol by computing, rewriting, and transmitting the collection of elements

$$a^{-1}t_1a,a^{-1}t_2a,\cdots ,a^{-1}t_na.$$

Similarly, user $B$ computes, rewrites, and transmits

$$b^{-1}s_1b,b^{-1}s_2b,\cdots,b^{-1}s_mb.$$

An adversary observing these transmissions is unable to determine $a$ or $b$ unless $(s)$ he can solve a set of simultaneous conjugacy equations over the base group.

​ Multiplying two elements in the group can be accomplished by simply concatenating the two expressions representing the elements. The process of rewriting, while not unique, must be chosen so that no adversary can determine the conjugating element from viewing the publicly transmitted conjugates.

​ Recalling that the conjugate of the product of two elements is the product of the conjugates of those elements (i.e., property (i) of $\beta$), users $A$ and $B$ are now in a position to compute, respectively, the elements

$$\beta(b,a)=b^{-1}ab,\ \ \ \ \ \ \ \ \beta(a,b)=a^{-1}ba.$$

In order to attain a common key, user $A$ computes

$$\kappa=\gamma_1(a,\beta(b,a))=a^{-1}b^{-1}ab=[a,b],$$

and user $B$ computes

$$\kappa=\gamma_2(a,\beta(b,a))=[a,b].$$

（上文摘自Mathematical Research Letters 6, 287–291 (1999),AN ALGEBRAIC METHOD FOR PUBLIC-KEY CRYPTOGRAPHY,Iris Anshel, Michael Anshel, and Dorian Goldfeld著）

应用例

[UTCTF2020]Cube Crypto

Mr. Anshel and Mr. Goldfeld were trying to exchange some asymmetric keys to get a shared key. They aren’t very good at math, so they decided to use a Rubik’s Cube instead to do the crypto. I don’t think it’s very secure though, I think you might be able to guess some of their keys :hmm:

Mr. A public key: [B' U', F B F, R' D, B D']
Mr. G public key: [R D L', D U' B, U F', L' F]

Mr. A sends: [B D' R' D R D L' D' R D B', B D' R' D D U' B D' R D B', B D' R' D U F' D' R D B', B D' R' D L' F D' R D B']
Mr. G sends: [U F' R D L' B' U' L D' R' F U', U F' R D L' F B F L D' R' F U', U F' R D L' R' D L D' R' F U', U F' R D L' B D' L D' R' F U']

NOTE: The flag is the shared key that they generate, so it is NOT in utflag{} format

显然的，这道题需要应用Anshel–Anshel–Goldfeld 密钥交换体系，在这里，密钥是由魔方转动记号呈现的，而我们知道，魔方的转动操作群是非阿贝尔群，在这里，我们可以从Mr.A和Mr.G提供的公钥中提取出：

$$S_A=\langle s_1,s_2,s_3,s_4\rangle\ \ \ \ \ \ \ S_G=\langle t_1,t_2,t_3,t_4\rangle$$

其中：

s_1=B' U'
s_2=F B F
s_3=R' D
s_4=B D'
t_1=R D L'
t_2=D U' B
t_3=U F'
t_4=L' F

又设在交换后得出的密文的集合分别为：

$$C_G=\langle s_1',s_2',s_3',s_4'\rangle\ \ \ \ \ \ \ C_A=\langle t_1',t_2',t_3',t_4'\rangle$$

其中：

s_1'=U F' R D L' B' U' L D' R' F U'
s_2'=U F' R D L' F B F L D' R' F U'
s_3'=U F' R D L' R' D L D' R' F U'
s_4'=U F' R D L' B D' L D' R' F U'
t_1'=B D' R' D R D L' D' R D B'
t_2'=B D' R' D D U' B D' R D B'
t_3'=B D' R' D U F' D' R D B'
t_4'=B D' R' D L' F D' R D B'

我们假设共享密钥为$a^{-1}g^{-1}ag$，所以我们有：

$$a^{-1}t_ia=t_i'\ \ \ \ \ g^{-1}s_ig=s_i'\ \ \ \ \ (i=1,2,3,4)$$

通过观察我们很容易可以得到：

$$a=D' R D B'\\ g=L D' R' F U'$$

所以我们可以得出共享密钥：

$$a^{-1}g^{-1}ag=B D' R' DU F' R D L'D' R D B'L D' R' F U'$$

这样我们就得到了flag：

utflag{B D’ R’ D U F’ R D L’ D’ R D B’ L D’ R’ F U’}

至此，对于Anshel–Anshel–Goldfeld 密钥交换体系的介绍就到此结束了。