蒙特卡罗树搜索与三子集划分属性在密码分析中的应用

### 蒙特卡罗树搜索与三子集划分属性在密码分析中的应用 #### 1. 蒙特卡罗树搜索在差分特征搜索中的应用 在密码分析领域，寻找差分特征是一项重要的工作。蒙特卡罗树搜索（MCTS）被用于自动搜索SPECK密码的差分特征。以下是不同版本SPECK密码在该算法下的表现： - **SPECK64**：该算法在SPECK64上表现出一定的局限性，仅能找到最多13轮的良好差分特征。推测是因为树的深度增加，使得MCTS的搜索难度增大，通常对于超过12轮的特征搜索较为困难。 - **SPECK96**：在10轮的情况下，能在不到一分半的时间内找到最优解，显著优于最接近的基于图的方法所需的48小时。对于13轮，在12分钟内找到了非最优结果，可与之前基于蒙特卡罗的方法进行对比。不过，基于求解器的方法在SPECK96上仍然具有明显优势。 - **SPECK128**：在轮数较少（最多9轮）时，该方法表现出色，但与其他基于图的方法类似，在扩展到更多轮数方面不如基于求解器的方法。 表1展示了SPECK32所有权重为30的差分特征： | r | ΔL | ΔR | -log₂p | r | ΔL | ΔR | -log₂p | r | ΔL | ΔR | -log₂p | |----|----|----|----|----|----|----|----|----|----|----|----| | - | 0211 | 0a04 | – | - | 7448 | b0f8 | – | - | 8054 | a900 | – | | 1 | 2800 | 0010 | 4 | 1 | 01e0 | c202 | 5 | 1 | 0000 | a402 | 3 | | 2 | 0040 | 0000 | 2 | 2 | 020f | 0a04 | 5 | 2 | a402 | 3408 | 3 | | 3 | 8000 | 8000 | 0 | 3 | 2800 | 0010 | 5 | 3 | 50c0 | 80e0 | 8 | | 4 | 8100 | 8102 | 1 | 4 | 0040 | 0000 | 2 | 4 | 0181 | 0203 | 4 | | 5 | 8004 | 840e | 3 | 5 | 8000 | 8000 | 0 | 5 | 000c | 0800 | 5 | | 6 | 8532 | 9508 | 8 | 6 | 8100 | 8102 | 1 | 6 | 2000 | 0000 | 3 | | 7 | 5002 | 0420 | 7 | 7 | 8000 | 840a | 2 | 7 | 0040 | 0040 | 1 | | 8 | 0080 | 1000 | 3 | 8 | 850a | 9520 | 4 | 8 | 8040 | 8140 | 1 | | 9 | 1001 | 5001 | 2 | 9 | 802a | d4a8 | 6 | 9 | 0040 | 0542 | 2 | 以下是MCTS搜索最优差分特征的伪代码： ```python # MCTS search for optimal differential characteristics for SPECK # Require: a bit-size n ≥1, the number of forward rounds and backward rounds for # the search, all the parameters specified in Section 5. # Ensure: Differential characteristics of decreasing weights. class Node: visits, children, payout = 0, [], [] class Cached: path, path weights, best weight = [], [], float('inf') # Build the initial tree from the pDDT as a collection of Node # Initialize cache as a collection of Cached def mcts iteration(ΔL, ΔR, num rounds): path, path weights = [(ΔL, ΔR)], [] tree[(ΔL, ΔR)].visits += 1 for i in range(1, num rounds + 1): if (ΔL, ΔR) in tree: if tree[(ΔL, ΔR)].visits <= k: ΔL,new, ΔR,new, p = random.choice(tree[(ΔL, ΔR)].children) else: # node with max UCT in tree[(ΔL, ΔR)].children pass else: possible children = δ - optimal(ΔL, ΔR, δ) for child in possible children: if xdp+(child) > expand threshold: tree[(ΔL, ΔR)].children.append(child) ΔL,new, ΔR,new, p = random.choice(tree[(ΔL, ΔR)].children) path.append((ΔL,new, ΔR,new)) path weights.append(-math.log2(p)) ```