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:

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.

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.

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.

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.1 2 3 41 1 2 3 42 2 4 1 33 3 1 4 24 4 3 2 1

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.

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

ReplyDeleteAnonymous,

ReplyDeleteI'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