Links to stuff on this blog

Use the Site Index of Projects page link above for an easier way to find stuff on my blog that you might be looking for!

Sunday, September 12, 2010

Another Cryptographic Idea (continuing a thought)

Another idea and this one starts back with another post that I did a long time ago. It's a short one and you can find it HERE. What I was writing about back in that post relates to multiplication with a prime modulus and how the numbers you get are all the same, just in a mixed up order. For a quick example below is what I am talking about:
     1   2   3   4
1   1   2   3   4
2   2   4   1   3
3   3   1   4   2
4   4   3   2   1
The above little chart is a multiplication table mod 5. The numbers in orange are the numbers that are being multiplied mod 5 and the numbers below them are the results of the multiplication. So if you look at the green 4 in the table it's obliviously the result of 2 x 2 mod 5. If you look at the green 1 right next to it , it's the result of 2 x 3 mod 5. The interesting thing (to me anyway) is that if you look at the chart it's all the same numbers just in a different order.

Back when I wrote the original post about this I didn't have time to figure out anything to do with that but now I think that I have.
  
As long as the multiplication table is built using multiplication mod a prime number the table will never have the same number twice in any row or any column. That doesn't happen if the table is made using a non-prime modulus. To see what I mean go to THIS site and scroll down to the cool interactive  chart they have. You can select it to be a multiplication chart and change the modulus to anything you like.
  
The idea would be to use this to create cryptographic diffusion in blocks of data. Maybe start with something like 8 bytes of data and multiply each one by another, incrementing one of them with each multiplication. Here is a nifty and colorful picture to help explain what I am talking about. Try changing the modulus from a prime number like 11 to a non-prime like 10 and see what happens.
Modular Multiplication with Rotation (shifts)



In the above picture you can see that there are colored boxes below the letters of the alphabet written in reverse order. I wrote them like that just to be interesting and no other reason! Imagine that the top row of colored boxes each contain a byte of data. So in the upper right there is a green box with the letters A and B over them. That green box has the two bytes of data called A and B. Simple!

Now take the value A and multiply it by the value B mod 257 and take the result over to the left and put it under the H (yellow box). Then again take the value A and multiply it by B + 1 mod 257 or more accurately A *(B+1mod257) mod 257 and put that result under the letter G (yellow box).

Keep on multiplying A times B+2, B+3, B+4 etc.. for a total of 6 times and each time move the result over putting it under another value. At that point each of the 6 bytes (H, G, F, E, D, C) will have a number under it.

Now, finally exclusive OR the original 6 bytes with these new numbers that we got from the six multiplications. These newly exclusive OR'd values are the new values of each byte. Once that is done shift each pair of bytes (colored boxes) to the right one location and repeat the multiplications. Keep doing this multiplication and rotation for a total of six times like in the chart.
 
At this point the output will be a total of 8 bytes that are all dependent on each other. At first glance, because of the way the multiplication mod a prime works, the permutation of each number will always be different even if you change any input value. That's because every number in the multiplication chart has to be different like I mentioned above.

To undo all this and get the original data back you can take the output and do the exact same multiplications but rotate the pairs of bytes in the opposite direction. I did just that using Excel in a spreadsheet, the inputs and outputs are in red.
 

H G F E D C B A
INPUTS 1 2 3 4 5 6 7 8
Mult 64 72 80 88 96 104 8 8
XOR 65 74 83 92 101 110







ROTATE 7 8 65 74 83 92 101 110
Mult 169 14 116 218 63 165 102 110
XOR 174 6 53 144 108 249
ROTATE 101 110 174 6 53 144 108 249
Mult 156 8 117 226 78 187 109 249
XOR 249 102 219 228 123 43
ROTATE 108 249 249 102 219 228 123 43
Mult 192 59 183 50 174 41 124 43
XOR 172 194 78 84 117 205
ROTATE 123 43 172 194 78 84 117 205
Mult 32 150 11 129 247 108 118 205
XOR 91 189 167 67 185 56






OUT 91 189 167 67 185 56 117 205






Mult 32 150 11 129 247 108 118 205
XOR 123 43 172 194 78 84 117 205
ROT -1 172 194 78 84 117 205 123 43
Mult 192 59 183 50 174 41 124 43
XOR 108 249 249 102 219 228
ROT -1 249 102 219 228 123 43 108 249
Mult 156 8 117 226 78 187 109 249
XOR 101 110 174 6 53 144
ROT -1 174 6 53 144 108 249 101 110
Mult 169 14 116 218 63 165 102 110
XOR 7 8 65 74 83 92 101 110
ROT -1 65 74 83 92 101 110 7 8
Mult 64 72 80 88 96 104 8 8
OUTPUT 1 2 3 4 5 6 7 8
 
The Exclusive OR function I used is a Visual Basic function I wrote for Excel that you can see in my post HERE if you are interested in doing this yourself. Or email me at ottobelden@yahoo.com and I'll send you the spreadsheet.
   
This is just an idea and I have not really looked into it close enough to see how well it works. Also this obviously isn't a cryptographic algorithm or cipher of any kind. It might work as a small part of one but for now I just think it's something interesting.

2 comments:

  1. This modulo thing is used in the 2D Round Robin switching algorithm !

    ReplyDelete
  2. Anonymous,

    I'm not familiar with the "2D Round Robin switching algorithm" but I googled it and I believe that you are right. Do you play around with this stuff too?

    - Otto

    ReplyDelete