Q: SAC
in [Cryptography]
|
Prev: RSA key size and safety
Next: MBOL AAOT MBCL LUAT MKAT
From: Mok-Kong Shen on 24 Sep 2009 20:16 Unruh wrote: > Mok-Kong Shen writes: > >> Tom St Denis wrote: >>> On Sep 23, 9:23 am, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: >>>> 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? >>> That's a stupid question, even from you. >>> >>> The sbox is a design principle of the cipher, it's ASSUMED to be >>> public knowledge. I can't say this in any more stressful fashion so >>> I'll cruise on caps... >>> >>> ALL OF MODERN CRYPTOGRAPHY'S SECURITY IS [IDEALLY] BASED ON THE >>> PREMISE THAT THE CIPHER OR ALGORITHM IS PUBLICLY DISCLOSED AND THAT >>> THE KEY(S) REMAIN SECRET. > >> No. I was criticizing your stating that's a cipher. I mean, since the >> opponent knows the Sbox, he can strip it right away, so the "existence" >> of the sbox in the cipher serves no purpose (no designer would >> add an absolutely redundant component). Saying C = P xor K is a an >> example of a simple cipher is o.k. Do you get it? > > No, you cannot strip it away. You maybe could IF it were "bijective" Ie > a simple permuation, but and Sbox is a non-linear many to one map. You > cannot undo it. For every output there are many inputs. The cypher as a > whole is one to one, but the subsets of it are not. Ie, given the > outputs of the sbox, you do not know what the inputs are. > Thus you cannot strip it away. I was answering to St. Denis in the context of his statement. He explicitly mentioned there that his Sbox is bijective and publically known. See what is quoted from his post above. Thanks, M. K. Shen
From: Maaartin on 30 Sep 2009 15:49 On Sep 24, 8:39 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > I am fairly sure that that wouldn't work. In the following, > I started with a 4*4 identity matrix. I did 3 steps to achieve > 50% 0 and 50% 1 in the first 3 columns, but then I am stuck. > There is evidently no way to get the 4-th column to satisfy > the required condition. > > 1000 1000 1000 1000 > 0100 1100 1100 1100 > 0010 0010 0110 0110 > 0001 0001 0001 0011 For a 4x4 matrix, there's no solution at all (prove it). But for larger matrixes it seems to work (just try it for 6x6). On Sep 25, 2:16 am, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > I was answering to St. Denis in the context of his statement. He > explicitly mentioned there that his Sbox is bijective and publically > known. See what is quoted from his post above. There're bijective sboxes (as in AES) and there're non-bijective (as in DES). But stripping them away makes no sense as they're mixing the key and the data. Before you ask again, habe a look at http://en.wikipedia.org/wiki/Advanced_Encryption_Standard an tell me how to strip them there.
From: Greg Rose on 30 Sep 2009 16:03 In article <00ff0a4f-83fe-4bf9-b62a-2dd218e64f4d(a)o41g2000yqb.googlegroups.com>, Maaartin <grajcar1(a)seznam.cz> wrote: >On Sep 24, 8:39�pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: >> I am fairly sure that that wouldn't work. In the following, >> I started with a 4*4 identity matrix. I did 3 steps to achieve >> 50% 0 and 50% 1 in the first 3 columns, but then I am stuck. >> There is evidently no way to get the 4-th column to satisfy >> the required condition. >> >> � � 1000 �1000 �1000 �1000 >> � � 0100 �1100 �1100 �1100 >> � � 0010 �0010 �0110 �0110 >> � � 0001 �0001 �0001 �0011 > >For a 4x4 matrix, there's no solution at all (prove it). >But for larger matrixes it seems to work (just try it for 6x6). Indeed my algorithm fails for the small case. But: 1110 1001 0101 0010 seems to work. I've subsequently concluded that no such exactly balanced matrix can be invertible though... Greg. -- Greg Rose 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
From: Mok-Kong Shen on 30 Sep 2009 16:13 Maaartin wrote: > For a 4x4 matrix, there's no solution at all (prove it). I used a program to show that. But you might not accept that as equivalent to a math proof and anyway there is no proof of my program correctness. What could I do? > But for larger matrixes it seems to work (just try it for 6x6). > > On Sep 25, 2:16 am, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: >> I was answering to St. Denis in the context of his statement. He >> explicitly mentioned there that his Sbox is bijective and publically >> known. See what is quoted from his post above. > > There're bijective sboxes (as in AES) and there're non-bijective (as > in DES). > But stripping them away makes no sense as they're mixing the key and > the data. > Before you ask again, habe a look at > http://en.wikipedia.org/wiki/Advanced_Encryption_Standard > an tell me how to strip them there. I suppose there is a misunderstanding here. St. Denis's post had C = Sbox( P xor K ) as a cipher. Now how is the proper recipient of the encrypted message to recover P? He has certainly to strip off Sbox, right? Since Sbox is in public knowledge, as St. Denis assumed, anybody else could do the same as the proper recipient. Or is there any logical fault in my reasoning? M. K. Shen
From: Mok-Kong Shen on 30 Sep 2009 16:28
Greg Rose wrote: > Indeed my algorithm fails for the small case. > But: > > 1110 > 1001 > 0101 > 0010 > > seems to work. > > I've subsequently concluded that no such exactly > balanced matrix can be invertible though... Do you mean that for n=4 there is no linear bijective function satisfying the condition that flipping one input bit always causes exactly 2 output bits to flip? I have verified that with a program in order to exclude my hand computation mistakes. Using another program I found that there is in this case no bijective function at all (i.e. linear or nonlinear) satisfying that condition. But that's unfortunately only a 'proof' with a program, not a proof in the classical mathematical sense. If you could show that with math, I should be very grateful to know the details. M. K. Shen |