Q: SAC
in [Cryptography]
|
Prev: RSA key size and safety
Next: MBOL AAOT MBCL LUAT MKAT
From: Maaartin on 30 Sep 2009 17:57 On Sep 30, 10:03 pm, g...(a)nope.ucsd.edu (Greg Rose) wrote: > In article <00ff0a4f-83fe-4bf9-b62a-2dd218e64...(a)o41g2000yqb.googlegroups..com>, > > Maaartin <grajc...(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... For the 4x4 matrix you're right, since there's be always a cycle (consider the columns as vertices and the two ones in a row as an edge between them). In general, either you're wrong or my program is buggy (which is quite possible, even the regularity test may be wrong): SIZE 2: 10 01 SIZE 6: 110010 010101 001101 000111 100011 100101 SIZE 10: 1010001101 1110010010 0111010010 0101011100 1011110000 1010010110 1001101001 1011000110 0100100111 0100001111 SIZE 18: 110001000101110101 010011110100111000 001111010000111010 000101111110001001 000011111101100010 010001001011101110 010000100111011110 010000110111111000 000001011110110110 001001100110101101 001010010011011011 000000011101110111 000011101000111101 111011000110010001 100110010010001111 100011010010001111 101111000000100111 110101000100110011 SIZE 14: 11010100011001 01000111010101 00100101001111 01011011100010 00101010100111 00010101100111 10000011111100 00110001001111 11000010111100 01000011010111 00111100001101 10000100110111 01001001010111 00010100110111 SIZE 22: 1001100100101100111001 0111010101101000010110 1010011110100111000010 0001110110010111000110 1000100010010011110111 0011011000001110111001 1001111101100001000110 0000000111111110111000 0011000011011001101101 1010110001000110011011 1010001010111110010100 0111011001010011000101 0100011000011101110101 1100001000000101111111 0000001000011111110111 1000111001000101010111 0000101000011010111111 0100010101110010011110 1001010001010001111101 1100100100111100000111 1100110100101000011011 0000011110110001001111 SIZE 26: 10100011110010000110001111 01000110011011100111011000 01111110101110000001010001 01010000010011101110101101 00001111010101011110000110 10100111001110000010001111 00100010010011110111110010 00001001110111110001001101 10001000111011010011010110 00100000111010111011000111 00010000001111011001110111 00001101011101010011010011 00001001100010101111111100 00010011001101010110011110 00101001100001111000111011 10101010100001011111110000 00001011110000101011011110 00100000001110001101111111 11100101010010000011101110 10001000000101010101111111 00100111110000000110111011 00100001011000110111111010 01100010111101001000001111 01100010001101110001001111 11100000101110011001000111 00101110011011110101000001 SIZE 30: 110001010111000001110000111011 011000011100111101111100000001 001011101111110010000001101001 100100001101100001111111100100 000010101100001101111011011010 000011011001101111001110010001 000000110000011011100101111111 101100010000111011001001011110 000110001001111000011101101011 010000100110110011011100101110 001000110011010011100111101001 000100110001010110101111001101 000010110010111011010001011110 000010010011010110111100010111 101000000001101010110011110111 100010001100010100111100111110 100000000001110011111011101011 101010100101000011101100011101 010100100100000010111011111011 001100010001100001110010111111 100010101000000010011111101111 011000001000110101001111111100 010001001101011010010011110101 000100100101110010010101011111 001100011000001110100101101111 000011110001111111001000011010 110100101000001110010001011111 000110010001100110100110101111 010000110100100111101000111011 110000010101111110101001001001 I implemented something like you proposed, I add ones randomly in a column until the're enough of them while checking bijectivity after each step (in case of a singular matrix I remove the last one and retry). It found the above results but nothing more for sizes up to 32. It looks like it works only for sizes of the form 2+4*n with integer n>=0.
From: Maaartin on 30 Sep 2009 18:06 On Sep 30, 10:13 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > 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? You're right, in his example you can strip it away. But do not forget that his "cipher" was just for demonstrating what he said about SAC. The simplest toy cipher meaningfully using sboxes could look like C = sbox[P xor K1] xor K2 where K1 and K2 are two parts of the key. Here you can't strip it off, can you?
From: Greg Rose on 1 Oct 2009 01:37 In article <ee962a0c-6452-4ec4-9bd9-b62e47b4a484(a)g19g2000yqo.googlegroups.com>, Maaartin <grajcar1(a)seznam.cz> wrote: >On Sep 30, 10:03�pm, g...(a)nope.ucsd.edu (Greg Rose) wrote: >> In article ><00ff0a4f-83fe-4bf9-b62a-2dd218e64...(a)o41g2000yqb.googlegroups.com>, >> >> Maaartin �<grajc...(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... > >For the 4x4 matrix you're right, since there's be always a cycle >(consider the columns as vertices and the two ones in a row as an edge >between them). In general, either you're wrong or my program is buggy >(which is quite possible, even the regularity test may be wrong): > >SIZE 2: >10 >01 >SIZE 6: >110010 >010101 >001101 >000111 >100011 >100101 >SIZE 10: >1010001101 >1110010010 >0111010010 >0101011100 >1011110000 >1010010110 >1001101001 >1011000110 >0100100111 >0100001111 >SIZE 18: >110001000101110101 >010011110100111000 >001111010000111010 >000101111110001001 >000011111101100010 >010001001011101110 >010000100111011110 >010000110111111000 >000001011110110110 >001001100110101101 >001010010011011011 >000000011101110111 >000011101000111101 >111011000110010001 >100110010010001111 >100011010010001111 >101111000000100111 >110101000100110011 >SIZE 14: >11010100011001 >01000111010101 >00100101001111 >01011011100010 >00101010100111 >00010101100111 >10000011111100 >00110001001111 >11000010111100 >01000011010111 >00111100001101 >10000100110111 >01001001010111 >00010100110111 >SIZE 22: >1001100100101100111001 >0111010101101000010110 >1010011110100111000010 >0001110110010111000110 >1000100010010011110111 >0011011000001110111001 >1001111101100001000110 >0000000111111110111000 >0011000011011001101101 >1010110001000110011011 >1010001010111110010100 >0111011001010011000101 >0100011000011101110101 >1100001000000101111111 >0000001000011111110111 >1000111001000101010111 >0000101000011010111111 >0100010101110010011110 >1001010001010001111101 >1100100100111100000111 >1100110100101000011011 >0000011110110001001111 >SIZE 26: >10100011110010000110001111 >01000110011011100111011000 >01111110101110000001010001 >01010000010011101110101101 >00001111010101011110000110 >10100111001110000010001111 >00100010010011110111110010 >00001001110111110001001101 >10001000111011010011010110 >00100000111010111011000111 >00010000001111011001110111 >00001101011101010011010011 >00001001100010101111111100 >00010011001101010110011110 >00101001100001111000111011 >10101010100001011111110000 >00001011110000101011011110 >00100000001110001101111111 >11100101010010000011101110 >10001000000101010101111111 >00100111110000000110111011 >00100001011000110111111010 >01100010111101001000001111 >01100010001101110001001111 >11100000101110011001000111 >00101110011011110101000001 >SIZE 30: >110001010111000001110000111011 >011000011100111101111100000001 >001011101111110010000001101001 >100100001101100001111111100100 >000010101100001101111011011010 >000011011001101111001110010001 >000000110000011011100101111111 >101100010000111011001001011110 >000110001001111000011101101011 >010000100110110011011100101110 >001000110011010011100111101001 >000100110001010110101111001101 >000010110010111011010001011110 >000010010011010110111100010111 >101000000001101010110011110111 >100010001100010100111100111110 >100000000001110011111011101011 >101010100101000011101100011101 >010100100100000010111011111011 >001100010001100001110010111111 >100010101000000010011111101111 >011000001000110101001111111100 >010001001101011010010011110101 >000100100101110010010101011111 >001100011000001110100101101111 >000011110001111111001000011010 >110100101000001110010001011111 >000110010001100110100110101111 >010000110100100111101000111011 >110000010101111110101001001001 > >I implemented something like you proposed, I add ones randomly in a >column until the're enough of them while checking bijectivity after >each step (in case of a singular matrix I remove the last one and >retry). It found the above results but nothing more for sizes up to >32. It looks like it works only for sizes of the form 2+4*n with >integer n>=0. Yes, if n is a multiple of 4, then n/2 is even, which means that the sum of each column is 0, which implies the determinant will be zero, hence not invertible. (My thanks to David Jacobson for this insight.) Greg. -- Greg Rose 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
From: Mok-Kong Shen on 1 Oct 2009 04:45 Maaartin wrote: > On Sep 30, 10:13 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: >> 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? > > You're right, in his example you can strip it away. But do not forget > that his "cipher" was just for demonstrating what he said about SAC. > The simplest toy cipher meaningfully using sboxes could look like > C = sbox[P xor K1] xor K2 > where K1 and K2 are two parts of the key. Here you can't strip it off, > can you? Right. On the other hand, it had been overlooked even by St. Denis himself (for he followed up) that my critique was not about the "use" of Sbox as such but on the fact that he "called" C = Sbox(P xor K) as a "cipher" with a Sbox publically known. My point was, since with his assumption anyone could strip Sbox away, there is no sense for a cipher designer to include that (from crypto consideration entirely redundant) Sbox into his design and hence C = P xor K is an example of a "cipher" but, if Sbox is publically known, then C = Sbox(P xor K) is not an example of a "cipher". Of course, if C = P xor K is a strong encryption, then, with his Sbox, C = Sbox(P xor K) is also a strong encrption, however with "exactly" the same strength, no more nor less. I hope that this has finally cleared the issue. Thanks, M. K. Shen
From: Mok-Kong Shen on 1 Oct 2009 06:05
Greg Rose wrote: > Maaartin <grajcar1(a)seznam.cz> wrote: >> SIZE 2: >> 10 >> 01 >> SIZE 6: >> 110010 >> 010101 >> 001101 >> 000111 >> 100011 >> 100101 >> SIZE 10: >> 1010001101 >> 1110010010 >> 0111010010 >> 0101011100 >> 1011110000 >> 1010010110 >> 1001101001 >> 1011000110 >> 0100100111 >> 0100001111 [snip] >> I implemented something like you proposed, I add ones randomly in a >> column until the're enough of them while checking bijectivity after >> each step (in case of a singular matrix I remove the last one and >> retry). It found the above results but nothing more for sizes up to >> 32. It looks like it works only for sizes of the form 2+4*n with >> integer n>=0. > > Yes, if n is a multiple of 4, then n/2 is even, > which means that the sum of each column is 0, > which implies the determinant will be zero, hence > not invertible. (My thanks to David Jacobson for > this insight.) If I understand correctly, the current state of affairs is as follows: (1) For n = 0 (mod 4) there is no linear bijective function satisfying the condition. (2) For n = 0 (mod 2) n != 0 (mod 4) the existence of such linear bijective functions has been verified up to n = 30 and it seems very plausible that this is indeed a general result. (3) For n = 4, no bijective function at all satisfying the condition exists (assuming that my previous program run is correct). So the following question remains: For n = 0 (mod 4), n > 4, do there exist bijective functions (by necessity nonlinear, see (1) above) which satisfy the condition that flipping any one input bit always causes exactly 2 output bits to flip? Since n=8 seems to be a quite interesting case, I attempted to use my program that had previously processed the n=4 case to investigate. However, it turns out that my program is much too inefficient for that use and would require far too much run time on my PC than I could afford. In my program I employ essentially brute force. I know that I can reduce the search space by 50% through implementing a check. I have however not yet considered even to try out that short-cut, because even with a 50% reduction in run time I'll still have no "practical" chance of successfully running the program for the case n=8 to an end on my poor PC. I should be grateful, if anyone could provide good ideas of really essentially cutting down the processing time in the present case as compared to my naive bruteforcing. Thanks, M. K. Shen |