我听说纯粹基于XOR和Rotation的加密本质上很弱。 ARX的旋转密码分析论文说:


也很容易证明省略加法或旋转是毁灭性的,并且这样的系统(XR和AX)总是可以破坏的。 >

但是我找不到有关如何实际执行操作的任何信息。任何人都可以给出提示吗?

(更新:)

@CodesInChaos指出:“您可以将每个输出位描述为一组固定的输入/键位的XOR。这样就产生了几百个线性方程,其模为$ 2 $,可以有效地求解。”对于简单的XR密码,我了解它是如何工作的。但是对于更复杂的问题,我还是有问题。如下所示:假设一个基于玩具XOR /旋转的密码(密码1)使用4位密钥$ K $将4位明文$ P $加密为4位密文$ C $。加密过程如下(示例$ p = 1001 $,$ k = 1000 $和$ c = 1110 $,所有加法都是$ 2 $模的加法运算):


$ E_1 $。向右旋转$ P $ 2位,产生$ M $($ 1001 \ rightarrow 0110 $),
$ E_2 $。将$ M $与$ K $异或,生成$ C $($ 0110 + 1000 = 1110 $)

相应的解密过程:


$ D_1 $。将$ C $与$ K $异或,产生$ M $($ 1110 + 1000 = 0110 $)
$ D_2 $。向左旋转$ M $ 2位,产生$ P $($ 0110 \ rightarrow 1001 $)

按照@CodesInChaos的建议,我可以将解密转换为以下线性方程组:

c1 + k1 = p3       1 + k1 = 1       k3 = 1
c0 + k0 = p2  ==>  0 + k0 = 0  ==>  k2 = 0          (A)
c3 + k3 = p1       1 + k3 = 0       k1 = 0
c2 + k2 = p0       1 + k2 = 1       k0 = 0


到目前为止一切顺利。但是,如果上述步骤$ E_2 $中的旋转位不是常数2,而是随输入明文而变化,该怎么办?例如,让我们对上面的密码进行一些修改(密码2):


$ E_1 $。将$ P $右旋转$ n $位,产生$ M $。其中$ n $ = $ P $的高2位($ 1001 \ rightarrow 0110 $),
$ E_2 $。将$ M $与$ K $进行XOR,产生$ C $($ 0110 + 1000 = 1110 $)

我无法将此密码转换为简单的线性方程组。因为从键和输入位开始,每个输出位都不再具有固定功能。

所以我的问题是:密码2是否仍然可以用作“纯XR”系统?还有打破它的通用方法吗?

评论

en.wikipedia.org/wiki/XOR_cipher这是一个有关如何使用XOR进行加密的简短示例。但这通常是在更复杂的情况下完成的。

您能否进一步扩展您的问题,您要执行什么XOR运算,您要进行哪些运算,何时以及按照什么顺序执行这些操作?

对于旋转,如果您正在寻找凯撒密码之类的东西,请参阅此。.stackoverflow.com/ questions / 2246319 / c-sharp-simple-encryption

您可以将每个输出位描述为一组固定的输入/键位的异或。这样就产生了数百个模2的线性方程,可以有效地求解。

非常感谢您的回答和修改。我会调查的。

#1 楼

XOR操作,固定的位移动(如取两个最高位或连接位等)以及与数据有关的旋转,形成了功能上完整的一组操作。这意味着您可以使用它们在固定长度的二进制字符串(包括所有可能的
分组密码)之间实现任何功能。

为了证明这些操作构成了一个功能完整的集合,表明
可以实现另一个功能完整集的所有操作。例如,
集合{NOT,AND}:


实现NOT运算很容易,因为这只是具有
1常数的XOR运算。 br />实现AND运算需要依赖于数据的旋转。在给定输入$ a $和$ b $的情况下,构造值$ v = RotLeft_ {a}(0b)$。现在,$ v $的最左
位是$ a $和$ b $的AND运算的结果。可以通过查看可能的输入值来验证:如果$ a $为零,则
rotation不执行任何操作,并且最左边的位保持为零。如果$ a $是1,
旋转会将$ b $的值移到最左边,如果$ b $也为1,结果就是
1。

这会将任何可能有效地打破基于这些操作的任何密码的算法转变为一种有效地打破任何任意密码的算法
,这种算法不太可能存在,而且肯定是未知的。

我不认为由这些原语构成的大多数甚至许多密码都是安全的。例如:如果只有
几个与数据无关的旋转,并且可以列举所有可能的
旋转计数组合,则可以通过尝试解决
所得的线性系统来破坏系统。每个组合。

评论


$ \ begingroup $
感谢@jix。您的回答对我来说很有意义。我重新审视了ARX论文,认为作者提到的较弱的XOR / Rotation系统可能与数据无关。
$ \ endgroup $
–耿鹏和
13年2月10日在16:30

$ \ begingroup $
@jix,您好,我们可以对具有模乘法运算的密码使用旋转密码分析吗? (例如,以$ 2 ^ {16} + 1 $为模的乘法,其中全零字(0x0000)被解释为$ 2 ^ {16} $(由带圆圈的点deno表示))
$ \ endgroup $
– meta_warrior
2014年12月9日下午4:35