The computations that went into a SHA256 Vigenere

 **************************************

*    SHA-256 is 256 bytes long     *

***************************************


This is not intended to be competitive with other algorithms - Rijndael, Blowfish, IDEA, etc.


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

*  Vigenere is x1 Time Pad secure up to the length of the Unicity distance by Mathematical proof*. It is not a Matrix "Group"

*  The thesis that Vigenere is not a "Group" is that there is no equivalence class of grids such that A = A and IF A = B  then B = A and IF A = B and B = C then A = C                                                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

127 + 113 + 3 + 5 + 7 = 255

127 * 113 * 3 * 5 * 7 = 1,506,855 bytes unicity distance for an x5 encrypted Vigenere

1,506,855 bytes

Believable for Vigenere!

x5 encrypted is slow. Develop password slow, encrypt/decrypt fast.

127 + 113 + 3 + 5 + 7 = 255  (product is 1,506,855)

127 + 113 + 13 = 253 127 * 113 * 13 = 186,563

109 + 127 + 19 = 255 109 * 127 * 19 = 263,017

117 + 139 = 256 117 * 139 = 16,263

109 + 107 + 37 = 253 109 * 107 * 37 = 431,531

31 + 43 + 47 + 131 = 252 

31 * 43 * 47 * 131 = 8,207,281 bytes !!!!!!!!!!!!!!!!!


31 * 43 * 47 * 131 = 8,207,281 bytes is Unicity distance for an x4 Vigenere - faster and more powerful than the x5 one above.


This is better than Love letters and Text messages need to be.


107 + 37 + 43 + 47 + 19 = 253 

107 * 37 * 43 * 47 * 19 = 152,021,641 bytes


152,021,641  (x1 Time Pad secure by Mathematical proof.)

For the sacrifice in time from x4 to x5, this is a substantial improvement.


103 + 37 + 43 + 47 + 23 = 253 

103 * 37 * 43 * 47 * 23 = 177,146,713

177,146,713 bytes


97 + 37 + 43 + 47 + 29 = 253 

97 * 37 * 43 * 47 * 29 = 210,347,701

210,347,701  bytes

89 + 37 + 43 + 47 + 31 = 247

 89 * 37 * 43 * 47 * 31 = 6,655,153

6,655,153 bytes


97 * 37 * 43 *47 * 29 is the most I can get out of x5


Do I want to go for x6?

23 + 73 + 37 + 43 + 47 + 31 = 254 23 * 73 * 37 * 43 * 47 * 31 = 3,892,068,073

3,892,068,073 bytes


**********************************************************************************

*  29 + 31 + 37 + 43 + 47 + 67 = 254 29 * 31 * 37 * 43 * 47 * 67 = 4,504,043,041 

*  4,504,043,041bytes                                                         

**********************************************************************************


29 + 37 + 41 + 43 + 47 + 59 = 256 29 * 37 * 41 * 43 * 59 = 111,610,241 bytes

I don't think I can do better with a SHA256 Hash!


Going for a 7th "round."


23 + 29 + 31 + 37 + 41 + 43 + 47 = 251 23 * 29 * 31 * 37 * 41 * 43 * 47 = 63,392,725,189

63,392,725,189 bytes

23 + 29 + 31 + 41 + 43 + 47 + 53 = 267

23 + 29 + 37 + 41 + 43 + 47 + 53 = 273

19 + 29 + 31 + 41 + 43 + 47 + 53 = 263

19 + 23 + 27 + 41 + 43 + 47 + 53 = 253 19 * 23 * 27 * 41 * 43 * 47 * 53 = 51,816,877,767 ( < 63,392,725,189)

19 + 23 + 27 + 37 + 43 + 47 + 59 = 255 19 * 23 * 27 * 37 * 43 * 47 * 59 = 52,055,335,557 ( still < )


**********************************************************************************************

*   23 + 29 + 31 + 37 + 41 + 43 + 47 = 251 23 * 29 * 31 * 37 * 41 * 43 * 47 = 63,392,725,189 *

*  63,392,725,189 bytes                                                                      *

*  This is the best I can do with 7 rounds.                                                  *

**********************************************************************************************


Going for an eighth round.


13 + 17 + 19 + 23 + 29 + 41 + 43 + 47 = 232 

13 * 17 * 19 * 23 * 29 * 41 * 43 * 47 = 232,071,537,100


17 + 19 + 23 + 29 + 41 + 43 + 47 + 53 = 272

17 + 19 + 23 + 29 + 31 + 43 + 47 + 53 = 262

17 + 19 + 23 + 29 + 31 + 41 + 47 + 59 = 266

17 + 19 + 23 + 29 + 31 + 41 + 47 + 53 = 260


17 + 19 + 23 + 29 + 31 + 41 + 43 + 53 = 256 

17 * 19 * 23 * 29 * 31 * 41 * 43 * 53 = 624,048,339,569

624,048,339,569 bytes


***********************************************************************************************

17 + 19 + 23 + 29 + 31 + 41 + 43 + 53 = 256  

17 * 19 * 23 * 29 * 31 * 41 * 43 * 53 = 624,048,339,569      

*  624,048,339,569 Bytes                                                                                     

*  This is the best I can do with 8 rounds.                                                                  

***********************************************************************************************

Going for 9 rounds.


11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 = 221

13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 53 = 263


11 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 47 = 255 

11 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 47 = 5,238,008,199,919

5,238,008,199,919 bytes


7 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 53 = 257

7 + 13 + 19 + 23 + 29 + 31 + 37 + 41 + 59 = 259


7 + 13 + 19 + 23 + 29 + 31 + 37 + 43 + 53 = 255 

7 * 13 * 19 * 23 * 29 * 31 * 37 * 43 * 53 = 3,014,592,194,159


***********************************************************************************************

11 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 47 = 255

11 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 47 = 5,238,008,199,919       5,238,008,199,919 bytes                                                                                             This is the best I can do with 9 rounds                                                                        

***********************************************************************************************

Checking 10 rounds 256 / 10 = 25.6 numbers have to average less than 26 characters in length. There are only 9 primes less than 25, so 10 rounds is not possible.

***********************************************************************************

In testing that statement, I found an error:

 

11 + 13 + 17 + 19 + 23 = 83 (These are the five primes just less than 26)

29 + 37 + 41 + 43 + 47 = 197 (These are the five primes just more than 26)

83 + 197 = 280

This averages 280/10 or ten 28 character sub-keys.

This also exceeds the length of the hash.

7 + 11 + 13 + 17 + 19 = 67

23 + 29 + 37 + 41 + 43 = 173

67 + 173 = 240

This averages 240/10 = 240 and is also only 240 chars of hash material - possible....

7 * 11 * 13 * 17 * 19 * 23 * 29 * 37 * 41 * 43 = 14,067,485,302,871 bytes.

dropping the leading 7, adds 40 (prime 47 - 7 chars) chars. 240 + 40 is 280... not possible.

**********************************************************************************************

7 + 11 + 13 + 17 + 19 + 23 + 29 + 37 + 41 + 43 = 240 

7 * 11 * 13 * 17 * 19 * 23 * 29 * 37 * 41 * 43 = 14,067,485,302,871     

14,067,485,302,871 bytes                                                                                             Ten rounds actually improved it!!!!!!!!!!!!!!!!!!!!!!!!!!                                                        

***********************************************************************************************

Eleven rounds amounts to:

2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 = 160

2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 = 200,560,490,130


5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 = 233

5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 = 50,708,377,254,535


7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 = 271

This exceeds the 256 bytes of key material.

11 rounds can develop a Unicity distance of 50,708,377,254,535 bytes.


***********************************************************************************************

5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 = 233 

5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 = 50,708,377,254,535        

 50,708,377,254,535 bytes                                                                                           Eleven rounds bettered THAT!         

**********************************************************************************************


2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 = 197 

2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 = 7,420,738,134,810


5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 = 276


3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 = 236 

3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 = 152,125,131,763,605


**********************************************************************************************3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 = 236

3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 = 152,125,131,763,605    

152,125,131,763,605 bytes                                                                                           12 rounds was yet another surprise   

********************************************************************************************

2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 = 238 

2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 = 304,250,263,527,210


7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 = 371

3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 = 279


2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 = 238 

2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 = 304,250,263,527,210 

304,250,263,527,210 bytes.                                                                                      13 rounds is bound to be getting unwieldy

***********************************************************************************************

The first 14 primes add up to

2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 = 281.

Dropping even the leading 2, adds 45 chars (47 chars - 2 chars,) so 14 rounds are not possible, with a 256 byte hash.

---------------------------------------------------------------------------------------------------------------

13 Rounds of Vigenere may to be too slow to compete with modern algorithms, but it's Unicity distance is 304,250,263,527,210 bytes.

If it stands the scrutiny of experts, it may be a curiosity.

* Proof of equivalence class by Dr. Nowell of Auburn University at Montgomery (AL.) AUM.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Amended 12/02/2021:

I didn't make an organized start to my computations for SHA256 Vigenere.
I SHOULD have started with a three round version, then a four round version, and THEN come to a five round version.
Below, you can see that a four round Vigenere can do better than 8,207,281 bytes

47 + 43 + 73 + 97 = 260
79 + 83 + 89 + 97 = 348
53 + 59 + 61 + 67 = 240
53 + 61 + 67 + 71 = 252  53 * 61 * 67 * 71 = 15,379,381 bytes
53 + 63 + 67 + 73 = 256  53 * 63 * 67 * 73 = 16,331,049 bytes
47 + 63 + 71 + 79 = 260
47 + 59 + 71 + 79 = 256  47 * 59 * 71 * 79 = 15,553,757 bytes

Four "round" Vigenere is capable of a unicity distance of 16,331,049 bytes
 

Comments

Post a Comment

Popular posts from this blog

A Question About Erasthmus' Sieve

Students of Mathematics are familiar with Erasthmus' Sieve. 2     x 3          x                4       x 5               x 6     x     x 7 8     x 9          x 10       x          x 11 12     x     x 13 14     x 15          x     x 16     x 17 18     x     x 19 20     x          x 21          x 22     x 23 First, we strike all multiples of 2 up to the square root (5.) Then all multiples of 3, then all multiples of 5, etc. I wrote a digital implementation of the Sieve, and used the index cr...
Read more

Notice of corrupted results: Vigenere may yet be found to be a "group."

Retraction: It is with regret that I do not delete the previous post. I am an individual, not an organization, and I failed to adequately double-check my results, but I am leaving the post to maintain some accountability. I am able to definitively say that the script for 2chars_from_file.py DOES NOT yield an exhaustive list. It develops the ciphertext for all 2 Char combinations of the FIRST 10, three character ciphertexts. This is not due to a logic error, but rather there is a virus that corrupts the indentation of the two write statements.  This may be verified by downloading the relevant code, and examining it, and running it if needed, against the relevant datafile. It is difficult to be exhaustively correct about ALL of the scripts. This calls ALL of my results in question, with regard to the qualification of a mathematical group. If Vigenere IS a group, the resulting substitution is still valid, but there exist 6 Char passwords that will accomplish the same encryption in ONE...
Read more

A Simple Rule for the Stock Market

The Stock Market is where the wealth of America is stored. As such, it is best when the stock market faithfully reflects the ups and downs of the economy. Stock market corrections are how the stock market reflects setbacks to the economy. This is good, as far as it goes, but in fact, when a stock market correction occurs, it is not well understood where the value of labor, goods and services stored in the stock market goes.  The whole idea that rising stock prices reflect improvements in the economy, is that this is the result of good investments. Investing is an act of devoting time, effort, or energy to a particular undertaking with the expectation of a worthwhile result. An investment is proven to be a good one, when it pays off after a duration of time. If you buy a stock, you wait for it to rise in price, and sell it at the appropriate time. "Buy low, Sell high," is how stock brokers explain their craft. How long should you hold a stock? This has always been up to the ow...
Read more