Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Thu May 27 1999 - 23:44:20
Ian Goldberg (iang@CS.Berkeley.EDU)
4 Apr 1999 19:53:12 GMT
In article <memo.19990403220927.61963A@klockstone.compulink.co.uk>,
Keith Lockstone <klockstone@cix.co.uk> wrote:
>In the first line of RC4:
> i = (i + 1) mod 256
>'i' cycles through 256 values.
>
>If we add in an odd number, 0 < r < 256, ie:
> i = (i + r) mod 256
>'i' also cycles through 256 values - but in a different sequence.
>
>Does these new 127 variants of RC4 behave in a similar way with regard to
>cycle length and precautions regarding the key set-up?
It's fairly easy to see that the byte generation parts of RC4 and your
variant (call it RC4(+r)) are in fact isomorphic:
Suppose after key setup, the array contains values S[0],...,S[255].
Define an array T by T[i] = S[r*i]/r. (All computation mod 256, of course.)
It's easy to see that running RC4(+r) on the array S will give equivalent
results as running RC4 on the array T. (Here, "equivalent" means
"scaled up by the constant factor r"; that is, the nth byte output
from running RC4(+r) on S is x and if the nth byte output from running
RC4 on T is y, then x = r*y (mod 256).)
So with regard to cycle length, RC4(+r) is obviously equivalent to RC4.
Now the key setup depends on whether you change the i+1 in that part of
the code to i+r as well. In any event, it won't be fundamentally different
(but I haven't thought about this part too much).
So if you believe that given a few hundred bytes out output of RC4,
you can recover the initial state of the S array, whatever it happened to
be, then RC4(+r) is of exactly the same strength as RC4.
On the other hand, if you believe that the key-setup part of RC4 is the
weak bit (so that the arrays S that result from RC4's key setup routine
are in some sense easier to break than starting with random permutations
for S), then RC4(+r) may be stronger, since it produces a different (though
related) set of initial arrays S.
- Ian
The following archive was created by hippie-mail 7.98617-22 on Thu May 27 1999 - 23:44:20