Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"


by japhy (Canon)
on Oct 02, 2000 at 18:51 UTC ( [id://34913] : perlmeditation . print w/replies, xml ) Need Help??

I'm working on an encryption algorithm (probably not the best in the world) for the fun (or hell) of it. It's called Rubix, and you probably already have a good idea of what it does. It maps a string onto a cube of given proportion (so string lengths are padded to 6, 24, 54, 96, ...), and then allows for rotations on ANY row or column throughout the cube. These rotations ALSO effect the character value of the character on the cube. Rotating something N times will increase the ASCII values of the characters in that segment by N.

I used to use a square for this. It was a whole lot simpler then. Now I have a LOT of things to deal with. Take the simple cube for "this message gets padded.". The string gets padded to 24 characters with a null character, say, "~". Then I map it onto the cube in the following fashion:
+--+ +--+ |AB| |th| |CD| |is| +--+--+--+--+ +--+--+--+--+ |EF|IJ|MN|QR| __\ | g|s |dd|.~| |GH|KL|OP|ST| ~~/ |et|pa|ed|~~| +--+--+--+--+ +--+--+--+--+ |UV| |~~| |WX| |~~| +--+ +--+
If I want to spin segment EFIJMNQR , to the right one notch, then the top face ABCD would get rotated too, and the cube would be (sans character transliteration):
+--+ +--+ |BD| |hs| |AC| |ti| +--+--+--+--+ +--+--+--+--+ |QR|EF|IJ|MN| __\ |.~| g|s |dd| |GH|KL|OP|ST| ~~/ |et|pa|ed|~~| +--+--+--+--+ +--+--+--+--+ |UV| |~~| |WX| |~~| +--+ +--+
Now I want to rotate the segment BAEKUWTN -- if you don't see why it's TN, and not NT, draw it out, and you'll see the loop goes UP the block in the back. In doing this, face QRGH will get rotated to. Let's say I spin the vertical segment down one notch.
+--+ +--+ |TD| |~s| |NC| |di| +--+--+--+--+ +--+--+--+--+ |GQ|BF|IJ|MW| __\ |e.|hg|s |d~| |HR|AL|OP|SU| ~~/ |t~|ta|ed|~~| +--+--+--+--+ +--+--+--+--+ |EV| | ~| |KX| |p~| +--+ +--+
If I restructure the cube into the string now, I go in the same order of the cells that I placed them in. That makes the result "~sdie.t~hgtas edd~~~ ~p~" -- now, the recipient (or interceptor) of this message knows the original characters, he just has a jumbled order (and perhaps some null characters). That's why the value augmentation is used. You can rotate a segment 4 notches, thus returning each character to where it was, but augmenting their values by 4. This makes it imperative that you know the turning sequence.

Which brings me to the turning sequence. Now, obviously, you can't just send the encrypted text. The recipient has to know how to decode it. And you can't send the "key" with the text, because then ANYONE can decode it if they know the algorithm. So how does one send a message and let the recipient know what to do? I'm thinking something not unlike the one-time pass technique. You both have a file holding generic instructions, and the sender determines how many instructions he wants executed, and sends that number as the first line of his transmission (or something).

The problem is that you'd have to have generic instruction sheets for each sized cube. 1x1x1, 2x2x2, 3x3x3, and so on. To me, this sounds less than practical (but then again, maybe Rubix is less than practical too...). Or perhaps it could be used for just keeping your own data obscured.

I appreciate any comments, insights, criticisms, or suggestions (I might end up making this a Filter:: module!).


Replies are listed 'Best First'.
RE: Rubix
by BlaisePascal (Monk) on Oct 02, 2000 at 21:54 UTC
    First, treat key distribution as a separate problem. If you have to go the route of using a one-time-pad to distribute your keys, you might as well go whole-hog and use a one-time-pad as your cipher. So for designing this cipher, pretend that the good guys have the keys and the bad guys don't. Also assume that the bad guys know how your cipher works.

    Along those lines, I'd hazard a guess that Rubix is gonna be a -really- poor cipher, based simply on the mathematics and patterns of the cube. You are going to need -really- long keys to have anything reasonably good.

    Second, Note this: You have 6 faces, let's call them "Up", "Down", "Front", "Back", "Left", "Right", for consistancy with weirdos like me who have done a reasonable amount of study of the Cube. Those names can be unambiguously abbreviated U, D, F, B, L, and R. Second, note that an NxNxN cube has N "slices" parallel to each face, which can be labelled 0-9 (for up to 10x10x10 cubes). Then you could use the following convention: For each turn, use a letter indicating the face, and a number indicating the slice. If the letter is uppercase, turn the slice clockwise; lowercase, counterclockwise. Note that every turn can be notated two ways: U1 is equivilant to d2

    Using this coding, your example could be coded in one of these four ways: U1R2, U1l1, d2R2, or d2r1.

    I would suggest a couple of modifications:

    First, instead of using the cube faces, use the cube cells. For a 2x2x2, this would give you 8 cells to use, rather than the 24 you have now, which is cutting down a bunch, but for a 4x4x4, you'd have 64 instead of 56, and it goes up from there. This helps deal with the issue that in your example, the three cells A,R,E are always going to move together, which helps the cryptographer immensely.

    Second, add to your basic operations a way of reordering the slices -- say by rotation. Take what was slice U0, and make it slice U9 (or whatever), and renumber accordingly. That way, every cell has an opportunity to go to every other cell -- something which doesn't happen with a normal cube. This could be symbolised by a face letter with no number, like in the sequence U0bu0B, which would perform some scrambling on the upper face (but leave the rest of the cube alone, modulo data augmentation).

    I'd also drop the data augmentation, and go with a pure transformation cipher.

      I was under the impression that a more common notation was 'U,D,F,B,L,R for 90° clockwise turns, 'U²,D²,F²,B²,L²,R²' for 90° turns, and either 'U',D',F',B',L',R'' ('prime') or 'U-1,D-1,F-1,B-1,L-1,R-1' for 90° anti-clockwise. The obvious advantage of this system is that U' or U-1 imply the inverse of U.

      I would be inclined to agree with you to the security of the cryptosystem. Istr that a 2x2 cube has only ~107 permutations, which strikes me as a rather small number compared to those people throw around when talking about PGP (but then, i am not a cryptologist). The number of permutations increases exponentially with cube size, so if you a use a bigger one, this may cease to be a problem.

      It would be really cool if you could use the resulting cryptosystem using nothing but a Rubik's cube, some paper, and a lot of free time (à la '<cite>Pontifex</cite>'), but maybe that's a little optimistic.....

      Some interesting cube-related links from my bookmarks:
        Yes, that notation is more common, but the problem is that it doesn't scale well for NxNxN cubes. It fixes the centers for 3x3x3 cubes, and it doesn't handle the inner slices for 4x4x4 or higher order cubes. The notation I described was reasonably compact, and handled cubes up to 9x9x9. That's why I went with it.

        The security really gets worse the larger the cube -- mainly because of key-length. True, the total number of permutations goes up exponentially (and how! one -factor- in the number of permutations is 24!floor((N-1)/2). I don't have time to compute the other factors, but with that exponential base, who cares?), but the number of permutations that can be reached within m quarter-turns is less than 12Nm. If you want to reach anywhere near a decent subset of the permutations, you are going to quickly need huge keys. If you use too small of keys, you get too little mixing, which ruins your cipher. I'd be interested to know when the length of good keys exceeds the length of the datablock (6N2). I suspect it happens quite low -- I know 3x3x3 cubes require at least 22 quarter-turns to reach all permutations, with a datablock size of 24 characters.

RE: Rubix
by extremely (Priest) on Oct 03, 2000 at 05:10 UTC

    Justa thought but maybe you should increment and decrement chars in the slice moved by direction, every time they move. That way when you rotate segment BAEKUWTN four times in one direction it would be the same as +4ing them but every turn would obscure the bast data up or down.

    What a goofy crypt.

    $you = new YOU;
    honk() if $you->love(perl)

      Yeah... that's what I said it does. I didn't do it in the example, but it's in the specification in the code.

RE: Rubix
by OzzyOsbourne (Chaplain) on Oct 03, 2000 at 21:57 UTC
    I ++ you for your endeavor. It made my head hurt like the original Rubix. If I remember correctly, the orignial Rubix instructions were something like, "With your main finger pointing down, rotate the cube topwise...