Q: SAC
in [Cryptography]
|
Prev: RSA key size and safety
Next: MBOL AAOT MBCL LUAT MKAT
From: Mok-Kong Shen on 22 Sep 2009 13:05 Maaartin wrote: > Mok-Kong Shen wrote: >> Greg Rose wrote: >> I understand that in evaluating Ap 'mul' and 'add' are replaced >> by 'and' and 'xor'. > > Yes. But you can still call it mul and add, they are multiplication > and addition (just in a different field). You are right. One can compute with mul and add mod 2. >> But with the random assigment described >> above, would A be always invertible, i.e. would the function be >> guaranteed bijective? Sorry for this layman's question. > > Surely not. Can you compute the determinant? Or better, can you > transform a matrix to a triangular form? > > To your next question ( :D ): You can make it bijective, too. Yes. But after the random assignment one has to check that the matrix is not singular and in the singular case to redo the assignment till one finally succeeds. If the size of the matrix is fairly large, say 1024, one has some practical trouble, I would think. Thanks, M. K. Shen
From: Maaartin on 23 Sep 2009 05:44 On Sep 22, 7:05 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > Yes. But after the random assignment one has to check that > the matrix is not singular and in the singular case to redo > the assignment till one finally succeeds. If the size of the > matrix is fairly large, say 1024, one has some practical trouble, > I would think. Yes, but the main problem is that such a sbox is useless as Greg wrote. What you need is non-linearity. Moreover I've never seen sboxes larger then a couple of bits. Did you tried it? What's the probability of such a matrix being regular? I'd guess, quite low, but I'm not sure. Nonetheless, designing an algorithm making regular matrices should be very easy.
From: Tom St Denis on 23 Sep 2009 08:59 On Sep 21, 8:57 pm, g...(a)nope.ucsd.edu (Greg Rose) wrote: > SAC is an interesting criterion, since it is > provably not sufficient and not provably > necessary. I'll second that. To add a bit to the discussion ... SAC was deemed a "good idea" when ciphers were still built on the DES like property of just re-wiring bits around to "diffuse things." In a cipher like AES for example, the MDS/Square transforms provide the branch required to ensure that small changes explode into huge changes as one would expect from a PRP. The "randomness" requirements from the output though really should come from the key schedule. For example, take a simple cipher C = sbox[P xor K] Where K is random. Even if sbox[] were known [and bijective] the output would still be "random" provided that K is random. In the case of AES you get the random part of the PRP from the fact that from an attackers point of view the round keys are random values. Of course this has fallen under attack lately because the round keys are highly related to one another, leading to the attacks on AES-192/256 with related keys. But as a cipher without the possibility of a related key avenue the round keys are still sufficiently random for the purposes of the cipher, Tom
From: Mok-Kong Shen on 23 Sep 2009 09:23 Tom St Denis wrote: > ..... For example, take a > simple cipher > > C = sbox[P xor K] > > Where K is random. Even if sbox[] were known [and bijective] the > output would still be "random" provided that K is random. That seems to be fairly clear. But if the sbox is known, there seems to be no purpose to use it at all (for crypto), isn't it? Thanks, M. K. Shen
From: Mok-Kong Shen on 23 Sep 2009 09:32
Maaartin wrote: > Did you tried it? What's the probability of such a matrix being > regular? I'd guess, quite low, but I'm not sure. > Nonetheless, designing an algorithm making regular matrices should be > very easy. I am not sure that one could have an algorithm that gives a non-singular matrix having columns with 50% 0 and 50% 1 (quite randomly) and yet without having to go through an iteration process (i.e. here trial and error). Simply getting an arbitrarily quite random appearing non-singular matrix is of course entirely trivial. Thanks, M. K. Shen |