1
$\begingroup$

I want to know if there exists an algorithm i can use where the input is a string of data and the output is a scrambled version of the same but in a 2 D array
ie given something like:


|1 2 3 4 5 6 7 8 9|


I want an output somewhat like:


|2 8 * 3 |


|7 9 4 1 |


|* 5 * 6 |


The scrambling would ideally be on the basis of a key and the same key or its pair can be used to unscramble the message.

$\endgroup$
  • $\begingroup$ Do you need a classical, hand based algorithm or a modern computer based one? In either case you can always re-format the output. You can always write a string as a 2D grid if you wish to. $\endgroup$ – SEJPM Dec 11 '15 at 18:05
  • $\begingroup$ a modern computer based one would be preferred, thank you! $\endgroup$ – Josh Kurien Dec 11 '15 at 19:33
  • $\begingroup$ Would generating a 2d matrix and then encoding & encrypring it suffice? $\endgroup$ – Maarten - reinstate Monica Dec 11 '15 at 23:35
  • $\begingroup$ Not really, I wanted to scramble a known message, also; just somehow changing the order of the data would suffice, i do not really need to add an encryption algorithm in the traditional sense, i.e. the text as such need not change $\endgroup$ – Josh Kurien Dec 12 '15 at 2:29
1
$\begingroup$

It seems like you just want to permute a string. E.g., transform the string "123456789"+ 3 blanks into the string "28_37941_5_6". Putting it into a 2-d array is just formatting (e.g., agree its to be a 4x3 array and then after every 4 characters add a line break).

There are plenty of algorithms to randomly permute a string. For example, the Knuth shuffle (aka Fisher-Yates shuffle) requires you to go through each element of a list and randomly swap it with itself or an earlier item in the list. (That is for the i-th position in the list do a swap with the i-th position and the j-th position where j is a random number between 0 and i inclusive). For example, this shuffle is implemented in python below:

import random

def knuth_shuffle(to_shuffle):
    for i in range(1, len(to_shuffle)):
        j = random.randint(0, i)
        to_shuffle[i], to_shuffle[j] = to_shuffle[j], to_shuffle[i]
    return to_shuffle

We can slightly modify this to take the random numbers as a "key" which tells us what permutation to do:

import random

def generate_key(input_length):
    key = []
    for i in range(1, input_length):
        j = random.randint(0, i)
        key.append(j)
    return key

def knuth_keyed_shuffle(to_shuffle, key):
    shuffled = to_shuffle[:] # create a copy of input to modify
    for i, j in zip(range(1, len(shuffled)), key):
        shuffled[i], shuffled[j] = shuffled[j], shuffled[i]
    return shuffled


def knuth_keyed_unshuffle(to_unshuffle, key):
    unshuffled = to_unshuffle[:] # create a copy of input to modify
    for i, j in reversed(zip(range(1, len(unshuffled)), key)):
        unshuffled[i], unshuffled[j] = unshuffled[j], unshuffled[i]
    return unshuffled

For example in python (after defining the functions above)

In [3]: text = list("123456789***")

In [4]: print text
['1', '2', '3', '4', '5', '6', '7', '8', '9', '*', '*', '*']

In [5]: key = generate_key(len(text))

In [6]: print key
[0, 0, 2, 2, 1, 1, 1, 6, 8, 2, 11]

In [7]: shuffled_text = knuth_keyed_shuffle(text, key)

In [8]: print shuffled_text
['3', '8', '*', '2', '4', '1', '9', '7', '*', '6', '5', '*']

In [9]: knuth_keyed_unshuffle(shuffled_text, key)
Out[9]: ['1', '2', '3', '4', '5', '6', '7', '8', '9', '*', '*', '*']

Some notes: first this will not be particularly secure.

Also, if you aren't particularly fond of using a list of integers as your key, you can encode it to a single integer between 0 and (n!-1) by using the factorial number system (factoriadic). The key is essentially a number written in base factorial with the least significant digit first -- the first digit is 0 or 1; second digit 0,1, or 2; third digit 0, 1, 2, or 3, ... n-th digit is an integer from 0 to n inclusive.

$\endgroup$
  • $\begingroup$ This will do quite well... but what do you mean by not particularly secure? other than the fact that it is all just plain text? $\endgroup$ – Josh Kurien Dec 13 '15 at 7:25
  • $\begingroup$ Thank you for your help, sort of got something more appropriate for me here your answer guided me to it though, thanks! $\endgroup$ – Josh Kurien Dec 13 '15 at 17:24
  • $\begingroup$ @JoshKurien By not particularly secure, I'm stating that if you have a scrambled message, it may be possible to unscramble it (by searching for valid english words and letter counts) as well as modify the scramble message. (E.g., if the message was ATTACK AT DUSK scrambled to CTA TSAK*K DATU* someone can put it in an anagram finder and decipher the message, figure out what permutations could have been used to recover the key (unique up to repeated letters) and then change the message.) $\endgroup$ – dr jimbob Dec 13 '15 at 19:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.