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