Mod n cryptanalysis: Difference between revisions

Revision as of 14:49, 8 June 2004

Revision as of 10:05, 11 June 2004

Line 2:

==Mod 3 analysis of RC5P==

For RC5P, analysis was conducted modulo 3. It was observed that for the operations in the cipher (rotation and addition, both on 32-bit words) were somewhat biased over congruence classes mod 3. AsTo anillustrate examplethe approach, consider left rotation by a single bit. :

<math>X <<< 1=\left\{\begin{matrix} 2X, & \mbox{if } X < 2^{23} \\ 2X + 1 - 2^{32}, & \mbox{if } X \geq 2^{32}\end{matrix}\right.</math> <!-- would prefer "\lll" or "\ll" to "<<<", but gives error (June 8, 2004) -->

Then, because

Because

<math>2^{32} \equiv 1\pmod 3</math>,

Line 11 ⟶ 12:

we can deduce that

<math>X <<< 1 \equiv 2X\pmod 3</math>.

Thus left rotation by a single bit has a simple description modulo 3. Analysis of other operations (data dependent rotation and modular addition) reveals similar, notable biases. Although there are some theoretical problems analysing the operations in combination, the bias can be detected experimentally for the entire cipher. In (Kelsey et. al, 1999), experiments were conducted up to seven rounds, and based on this they conjecture that as many as nineteen or twenty rounds of RC5P can be distinguished from random using this attack. There is also a corresponding method for recovering the secret [[key (cryptography)|key]].