Long ago, I imagined an encryption algorihtm based on the factor decomposition of each byte.

The idea is to get the prime factors of a number (and their power for primes <= 16). This gives an array 63 bits, mostly filled with zeros. When the shuffle this array based on a key (there are 63! possible shufflings)

It goes roughly as follows :

var key = [0-63!]

FOR EACH byte in string:

var factors = FACTOR(byte)

var shuffled = shuffle(factors, key)

END

It would be easy to break as is. However, another step is taken :

Once the factors are computed and shuffled, we check when we can truncate the array so it takes less space.

Here is an example (with factors from 2 to 16 in the array for simplicity) :

FACTORS = [ 2, 3, 4, 5, 7, 9, 11, 13, 16 ]

FACTORS_SHUFFLED = [ 5, 7, 3, 11, 13, 2, 4, 16 ]

BYTE = 65 = 13 * 5

OUTPUT_PRE_TRUNCATE = [ 1, 0, 0, 0, 1, 0, 0, 0 ]

// Since 65 * 4 and 65 * 16 > 256, they can’t be equal to 1.

// However, 65 * 2 = 130 > 256, so we need to keep it

// This gives the final output :

OUTPUT = [ 1, 0, 0, 0, 1, 0 ]

The outputs for each byte are then merged together, which gives the final string.

I always wondered how it could be broken. I really don’t believe that this is a strong cypher, but I never found an efficient way to break it.

Also, I wondered if some puzzle based on this could be created.

What do you think ?

[Edit] Moved to General Category