MITM variant No.OnE (partial matching)

在进行经典 MITM 时，大多数情况不能在中间匹配到等于分组长度的状态，即 $n=sn=s$ 往往不能满足。

所以更多情况下，往往只对分组长的部分比特进行匹配，也即部分匹配。

这是一种匹配的技巧，在中间相遇攻击中都会用到，如经典 MITM 的 MITM stage 中，步骤 2. 的得到的 $UandVU\backslash \; and\backslash \; V$ 的长度往往比分组长度小，但这样部分匹配也引发了一定的问题：

见经典 MITM NOTE 1. 匹配到的概率会变小，如果状态长度为 那么匹配到的概率就是 $2^{-s}2^\{-s\}$ ，留下的密钥数量就是$2^{\mathrm{\mid }{K}_1\mathrm{\mid }+\mathrm{\mid }{K}_2\mathrm{\mid }-s}2^\{|K\_1|+|K\_2|-s\}$ ，在后面测试阶段就需要更多的明密文对来筛选候选密钥集。当然也可以利用并行搜索的办法，减少留下的候选密钥数量，并行 $NN$ 个明密文对来进行 MITM ，留下的密钥数量就是$2^{\mathrm{\mid }{K}_1\mathrm{\mid }+\mathrm{\mid }{K}_2\mathrm{\mid }-N\ast s}2^\{|K\_1|+|K\_2|-N*s\}$ ，MITM 阶段和测试阶段的操作没有实质性的变换，但复杂度需要重新考虑：

复杂度分析：

时间复杂度：并行 N 个明密文对，所以时间复杂度变为：

空间复杂度：同样的，并行 N 个明密文对，所以空间复杂度变为：

数据复杂度：MITM 阶段和测试阶段都使用了多个明密文对，取较大的作为数据复杂度量级：