I've had some time to mess around a bit more with the Sawtooth 'thing' that I created a couple of weeks ago. In looking at it and re-reading my post I realized that there were some boo boo's in it that I should have seen right away but I was to pre-ocupied with the programming. Anyway HERE is a link to the post with all the pretty pictures. You can click on any of them for a bigger view or just trust me that there were some problems. Before i go any farther you should at least look at This Picture from that post. In this picture you get the basic idea of where I am going with this line of thought and why I decided to call this Sawtooth.

In the picture you can see the upper row labeled Saw Forward with the numbers 1, 2, 3 going off to the right etc... Below that is another row labeled Saw Reverse and on top of both of them is a bunch of blue arrows. In the picture the blue arrows pointing to the right (mostly) in the Saw Forward row are representing modular addition of two values plus 1 with a modulus of 257. Below that in the Saw Reverse row the same thing is happening but in the opposite direction (right to left). Finally the very last row of numbers was copied down to the Output but taken mod 256 to make them 8 bits. A quick and preliminary look at this as I mentioned in the first post seemed encouraging.

But... while thinking about it shortly after posting I realized that there were some serious and obvious problems with doing this. First of all there are a whole bunch of "equivalent inputs" that is, inputs that give the same output. Here are a few for your enjoyment:

All of these inputs make an output of all 0's | ||||||||

Input 1 | 8 | 231 | 30 | 224 | 31 | 225 | 25 | 241 |

Input 2 | 255 | 255 | 5 | 241 | 19 | 241 | 5 | 255 |

Input 3 | 245 | 24 | 225 | 31 | 224 | 31 | 226 | 19 |

Input 3 | 3 | 246 | 10 | 240 | 19 | 241 | 5 | 255 |

Input 4 | 8 | 231 | 30 | 225 | 25 | 240 | 5 | 255 |

Input 5 | 8 | 231 | 30 | 225 | 24 | 246 | 248 | 12 |

Input 6 | 8 | 232 | 24 | 240 | 4 | 4 | 242 | 13 |

Input 7 | 3 | 241 | 19 | 241 | 4 | 4 | 242 | 13 |

Input 8 | 254 | 5 | 241 | 19 | 240 | 11 | 241 | 13 |

This should have been obvious with very little thought but anyway... I wrote an inverse of the math that is in the picture and created a whole bunch of equivalent inputs which If I am thinking right means that there a whole bunch of outputs that are not valid. In other words no matter what the input is you can't get the output to certain 8 byte strings. Although I didn't specifically mention it in the original post this isn't what I am going for. What I do want is a direct and unique (1 to 1) mapping from any input string to an output string. So here are the original Design Goals with a new addition:

a) If you change any one of the Input bytes by even 1 bit, all the Output bytes should change

b) In addition to all the Output bytes changing about half of the 64 Output bits should change

c) In addition to that ideally about half of the bits in each Output byte should change (4 bits of the 8 bits in each byte)

d) If all the Input bytes are 0's then the Output bytes should not all be 0's

e) Keep it really simple because I want to do all the tricky stuff in Microsoft Excelf) That stuff I said above about 1 to 1 mapping

One thing that bothered me was I did do a "walking 1" through an input of all 0's as I mentioned in the origional post but didn't see any problems. Then I started thinking a bit more about what I was doing and decided that in addition to walking a 1 across all 0's I should also walk a 0 across all 1' in the input. If you are wondering what I am talking about with the 'walking 1' talk look at THIS picture. Specifically look to the right where there is a column of a bunch of 00000000 values under the heading of I' * I" . If you look very carefully in that column you can see on the far right (of that column) a value of 00000001 and right under it: 00000010 followed by 00001000 and so on. In other words the input difference (I' * I") is 1 bit and that bit is moving or "walking" from right to left.

Anyway before I went any farther into this I modified the Microsoft Excel Visual Basic code a bit to make the "walking 1" task a bit easier to try with more input values. The original code in the first post literally walked a 1 across an input of all 0's. Now the code walks a difference of 1 bit across any input values I choose to put in the spreadsheet. So I can test all 0's as the input or all 1' as the input or all random numbers as the input.

Here is the Visual Basic Code for your personal enjoyment:

Sub Walk_Dif_Bit()

'

' Set up a loop then exclusive or a "walking 1" through the Input range

' After Xor into the Input range, paste values to Output range from Formula range

' Go back and change Input range and paste new Output values into NEXT row of Output range

' November 2009 http://ottobelden.blogspot.com

'

' Input to Change C9, D9, E9, F9, G9, H9, I9, J9

' Input Diff to Copy C2, D2, E2, F2, G2, H2, I2, J2

' Output Diff to Copy C5, D5, E5, F5, G5, H5, I5, J5

Dim Multi As Long ' This is the walking 1 valut to Xor

Dim Orig As Long ' This will be the Origional value of cell before Xor

Dim Row As Long ' This keeps track of what row the output goes to

Dim Col As Long ' This keeps track of the column that Multi will change

Col = 10 ' Start in Column "J" 10th letter

Multi = 1 ' Value to start Xor'ing with

Orig = 0 ' Set to 0 in case I have to initialize variables

Row = 201 ' Row to start pasting

For ColCount = 1 To 8

For Counter = 1 To 8

'Copy and Paste Input Values Only to Output range

Orig = Cells(9, Col) ' Set the current value of the cell to Orig

Cells(9, Col) = Cells(9, Col) Xor Multi ' Xor Cells(ROW=9, COL) with Multi

Range("C2:J2").Select ' Select Input Diff range to copy

Selection.Copy

Range(Cells(Row, 12), Cells(Row, 19)).Select

Selection.PasteSpecial Paste:=xlPasteValues, Operation:=xlNone, SkipBlanks _

:=False, Transpose:=False

'Copy and Paste Output Values Only to Output range

Range("C5:J5").Select ' Select Input Diff range to copy

Selection.Copy

Range(Cells(Row, 21), Cells(Row, 28)).Select

Selection.PasteSpecial Paste:=xlPasteValues, Operation:=xlNone, SkipBlanks _

:=False, Transpose:=False

Row = Row + 1

Multi = Multi * 2

Cells(9, Col) = Orig

Next Counter

Multi = 1 ' Reset Multi for next input byte

Cells(9, Col) = Orig ' Set current input cell to Col

Col = Col - 1 ' Move back one column

Next ColCount

End Sub

'

' Set up a loop then exclusive or a "walking 1" through the Input range

' After Xor into the Input range, paste values to Output range from Formula range

' Go back and change Input range and paste new Output values into NEXT row of Output range

' November 2009 http://ottobelden.blogspot.com

'

' Input to Change C9, D9, E9, F9, G9, H9, I9, J9

' Input Diff to Copy C2, D2, E2, F2, G2, H2, I2, J2

' Output Diff to Copy C5, D5, E5, F5, G5, H5, I5, J5

Dim Multi As Long ' This is the walking 1 valut to Xor

Dim Orig As Long ' This will be the Origional value of cell before Xor

Dim Row As Long ' This keeps track of what row the output goes to

Dim Col As Long ' This keeps track of the column that Multi will change

Col = 10 ' Start in Column "J" 10th letter

Multi = 1 ' Value to start Xor'ing with

Orig = 0 ' Set to 0 in case I have to initialize variables

Row = 201 ' Row to start pasting

For ColCount = 1 To 8

For Counter = 1 To 8

'Copy and Paste Input Values Only to Output range

Orig = Cells(9, Col) ' Set the current value of the cell to Orig

Cells(9, Col) = Cells(9, Col) Xor Multi ' Xor Cells(ROW=9, COL) with Multi

Range("C2:J2").Select ' Select Input Diff range to copy

Selection.Copy

Range(Cells(Row, 12), Cells(Row, 19)).Select

Selection.PasteSpecial Paste:=xlPasteValues, Operation:=xlNone, SkipBlanks _

:=False, Transpose:=False

'Copy and Paste Output Values Only to Output range

Range("C5:J5").Select ' Select Input Diff range to copy

Selection.Copy

Range(Cells(Row, 21), Cells(Row, 28)).Select

Selection.PasteSpecial Paste:=xlPasteValues, Operation:=xlNone, SkipBlanks _

:=False, Transpose:=False

Row = Row + 1

Multi = Multi * 2

Cells(9, Col) = Orig

Next Counter

Multi = 1 ' Reset Multi for next input byte

Cells(9, Col) = Orig ' Set current input cell to Col

Col = Col - 1 ' Move back one column

Next ColCount

End Sub

Anyway enough of that. I posted it because someone might want to know how to do it (like me for instance when I forget how I did it).

So I tried several different variations (3 total) of the Sawtooth idea using different math to avoid the pesky "equivalent inputs" problem. For each of these three all I did was change the formulas for the Saw Forward and Saw Reverse parts. Refer to this picture for a refresher of what those are. For each of the three I ran a total of 8 different input strings and 'walked the one' across each of them giving a total of 512 unique input - output differences. Of the 8 different input strings one was all 0's, another was all 1's and the remaining 6 were random bytes selected by Excel.

The first thing I tried was a Saw Forward with simple addition mod 257 and a Saw Reverse with simple addition mod 256. Here is a table of the the number of bits/byte differences:

Bytes | Diff | # Bits Diff | Tot # Bytes | |||||||

3 | 3 | 1 | 1 | 4 | 2 | 2 | 2 | 8 | 18 | |

13 | 15 | 20 | 14 | 14 | 10 | 22 | 16 | 7 | 124 | |

55 | 45 | 63 | 53 | 53 | 50 | 52 | 50 | 6 | 421 | |

120 | 100 | 111 | 114 | 110 | 119 | 119 | 134 | 5 | 927 | |

137 | 151 | 138 | 137 | 136 | 152 | 140 | 147 | 4 | 1138 | |

116 | 106 | 99 | 110 | 124 | 97 | 99 | 94 | 3 | 845 | |

48 | 71 | 65 | 68 | 53 | 61 | 53 | 58 | 2 | 477 | |

19 | 21 | 12 | 14 | 16 | 20 | 24 | 10 | 1 | 136 | |

1 | 0 | 3 | 1 | 2 | 1 | 1 | 1 | 0 | 10 |

This isn't great as there are 10 instances of 0 bit changes in 1 out of 8 output bytes. (see green in chart) In other words changing one bit in the input caused only 7 of the 8 output bytes to change 10 different times. Because of a) in the design goals this is poopie. This also isn't the best because with the Saw Forward and Saw Reverse using no addition of 1's anywhere all 0' in the input creates all 0's in the output. and this is in direct violation of another design goal. Although not really a bad thing I don't want that. So I added a +1 in the first Saw Forward row and got:

Bytes Diff | # Bits Diff | Tot # Bytes | ||||||||

5 | 2 | 1 | 5 | 3 | 3 | 2 | 5 | 8 | 26 | |

7 | 12 | 21 | 16 | 16 | 15 | 16 | 13 | 7 | 116 | |

61 | 60 | 72 | 48 | 51 | 56 | 59 | 65 | 6 | 472 | |

119 | 100 | 109 | 128 | 122 | 119 | 92 | 117 | 5 | 906 | |

125 | 138 | 132 | 151 | 139 | 149 | 142 | 138 | 4 | 1114 | |

116 | 124 | 96 | 98 | 100 | 97 | 110 | 107 | 3 | 848 | |

64 | 61 | 61 | 47 | 62 | 52 | 71 | 58 | 2 | 476 | |

12 | 13 | 18 | 18 | 17 | 19 | 18 | 9 | 1 | 124 | |

3 | 2 | 2 | 1 | 2 | 2 | 2 | 0 | 0 | 14 |

Interesting but the 0 byte difference got worse with a 14 total instances out of the 512 inputs. Note that the random numbers are the same for all three of these tries. They were randomly picked by the Excel random function but I didn't change them with each formula change. If you want to know why email me because I'm getting tired of typing and want to wrap this post up pronto.

So without delay here is the last iteration that I tried.

I tried a Saw Forward addition mod 257 with 2* the second value like this in Excel:

=MOD(C10+(2*D9),$C$8)

and Saw Reverse addition mod 256 with 2* the second value like this in Excel:

=MOD(F11+(2*E10),$C$7)

The multiplication should remove all the 0 bit changes in the output byte differences unless there happens to be a strange occurrence where because of the modular addition there is an equivalent value after the multiplication. What are the odds of that happening you ask? Well here is your answer:

Bytes Diff | # Bits Diff | Tot # Bytes | ||||||||

0 | 1 | 0 | 0 | 0 | 2 | 0 | 0 | 8 | 3 | |

7 | 12 | 9 | 8 | 5 | 8 | 9 | 8 | 7 | 66 | |

21 | 47 | 23 | 24 | 45 | 24 | 26 | 28 | 6 | 238 | |

52 | 49 | 45 | 61 | 51 | 60 | 49 | 51 | 5 | 418 | |

80 | 63 | 76 | 69 | 70 | 70 | 69 | 80 | 4 | 577 | |

57 | 57 | 59 | 61 | 44 | 56 | 50 | 50 | 3 | 434 | |

34 | 21 | 35 | 27 | 32 | 29 | 38 | 30 | 2 | 246 | |

5 | 6 | 8 | 4 | 9 | 7 | 14 | 8 | 1 | 61 | |

0 | 0 | 1 | 2 | 0 | 0 | 1 | 1 | 0 | 5 |

It happened 5 times in the first 256 steps... never with all 0's and once with all 1's then 4 times in the second set of random bytes.

So now that I have a much better idea of what is going on with this I'm wondering what value it has (Ha Ha!) First off it has been fun to write the Visual Basic code and I have learned a lot about Microsoft Excel in that regard. Second I'm not ready to give up on this idea. I have yet to see two bytes of any output string not change at the same time and for awhile I considered leaving it at that. There are some other things to try other than the multiply by 2 idea so I'll try those and see what happens. Adding a substitution table and actually substitute the sum of the values would be neat too. More to come as I get time and feel like messing around with this.

## No comments:

## Post a Comment