Crypto狂想——通过魔方来进行密钥传递。

发布于 2023-11-21  567 次阅读

研究这题牵扯的概念花了我四天空闲时间....我们打ctf的是这样的。

今晚刷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**

_by balex_

具体意思就是这两个人数学不行又想交换非对称密钥以获得共享密钥，于是就采用了交换魔方的转动顺序。提供的信息包括它们的公钥和它们发送的移动顺序。

为了破译共享密钥，我们需要应用 A 先生和 G 先生相互发送的动作。然而，需要注意的是，提供的魔方动作是用速记符号书写的，其中每个字母代表一个特定的面旋转（U 代表向上，D 代表向下，L 代表左，R 代表右，F 代表前，B 代表后），撇号 （'） 的存在表示逆时针旋转。

我没有魔方，就找了一个在线网站转动了一下。

用Mr.A的顺序转动转出来的是这样的。

用Mr.G的顺序转出来是这样的

好，我们已经知道他们在干嘛了。虽然我拧完了才发现这几张图好像派不上用场。

然后我们需要考虑一个问题，那就是密钥传递的安全性。毕竟密码学的诞生就是源于人们对于信息安全的追求。这就要提到密钥交换协议了（还好前几天刚了解到😁），密钥交换协议在生活中很常用，当然这是题外话，不多赘述。（密钥交换协议也可以拿来水一篇文章，lucky~）

据我所知进行密钥交换的几个算法有Diffie-Hellman (DHKE) 和 Elliptic-Curve Diffie-Hellman (ECDH)以及Anshel-Anshel-Goldfeld（AAG） 。

从他们交换的内容就可以看出来这显然是AAG（你们不要小看这个，这东西理论上可抗量子攻击），毕竟这是肉眼可见的组，而且符合下图的形式。

然后我们可以了解一下AAG

“AAG协议的主要思想是使用非对称群的概念，其中两个实体可以使用相同的群元素进行密钥交换”

AAG 密钥交换是一种基于群论的密钥交换协议，用于安全地共享密钥，防止第三方窃听或破解。让我们用简单的步骤来解释：

  1. 选择群和非对称生成器： 首先，通信的双方要选择一个特殊的群（数学结构）以及一个非对称生成器。这个生成器是群中的一个特殊元素，可以生成整个群。
  2. 选择公共元素： 接下来，通信的双方共同选择一个公共元素，这个元素属于之前选择的群。这个元素是协议的起点。
  3. 生成私钥： 双方使用非对称生成器和公共元素，通过一些数学运算生成各自的私钥。这个私钥是他们保密的信息。
  4. 交换信息： 双方将生成的群元素交换，但不透露他们的私钥。这个步骤是在不泄露实际私密信息的情况下分享信息。
  5. 计算共享密钥： 双方使用对方提供的群元素和自己的私钥进行一系列数学运算，最终生成一个共享的密钥。这个密钥是他们之间的共同秘密。
  6. 验证： 最后，他们可以执行一些附加步骤，确保没有人监听或篡改了他们的通信。这个验证过程增加了协议的安全性。

接下来我们将题目的内容与AAG对应起来。

首先是对群的选择，魔方的旋转用啥表示来着？没错！就那几个字母！你们自己翻上去看（￣︶￣）↗　

A先生的公钥是[B' U'。F B F。R' D。B D']

G先生的公钥是 [R D L'。D U' B。U F'。L' F]

A发给G这个序列：[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']

G发给A这个序列：[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']

A先生的公钥是（a1，a2，a3，a4）= [B' U', F B F, R' D, B D']，

他发给G的是他的共轭公钥(A-1 g1 A,A-1 g2 A,A-1 g3 A,A-1 g4 A) = [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']。

G先生的公钥是（g1，g2，g3，g4）= [R D L', D U' B, U F', L' F]，

他发给A的是他的共轭公钥(G-1 a1 G,G-1 a2 G,G-1 a3 G,G-1 a4 G）= [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']

显然

A先生和G先生得到的共享密钥K是相同的，而且魔方这东西也比较好理解，你顺着拧一个顺序组X={U,F,L,D',U',R}，那么X‘肯定是反着来的{R’，U，D，L‘，F’，U‘}。还是想象不出来的话可以找个在线网站拧一下。所以咱们就可以开始解了。

请观察一下题目：

g1=[R D L'],

(A-1 g1 A)=[B D' R' D R D L' D' R D B']

朋友们告诉我！A-1是多少！是B D' R' D啊！也能看出A是D' R D B'！

同理：

a1=[B' U'],

(G-1 a1 G)=[U F' R D L' B' U' L D' R' F U']

可得G-1=[U F' R D L'],G=[L D' R' F U']

然后我们知道共享密钥K可由K=A-1 G-1 AG计算得出

K=B D’ R’ D U F’ R D L’ D’ R D B’ L D’ R’ F U’

得出flag{B D’ R’ D U F’ R D L’ D’ R D B’ L D’ R’ F U’}

这场由做题而起的知识探寻之旅就以做出来这道题结束啦。

嗯.......第一次感觉Crypto还蛮有意思的。

可以说用魔方来进行AAG密钥交换是一种非常有意思的变种，因为几乎AAG中每一个特征都可以用魔方来表现出来。比如AAG中逆运算和魔方的”逆旋转“。在AAG中，每个参与者有一个公钥（一组群元素）和一个私钥（基于公钥的某种操作序列）。在魔方的版本中，公钥和私钥可以被视为不同的旋转序列。非常有趣。

而这一题的难度主要在于对于AAG算法的识别上，只要认出来这是AAG，就可以做到一把梭，连程序都不用写的那种

技术号