# RSA encryption: Can we use a Rubik's cube for the same purpose?



## blah (Oct 23, 2008)

I just had a random thought today. I dunno much about RSA encryption and decryption (did a module about it but forgot most of the stuff), but I know that it's based on the fact that there's no simple/efficient algorithm to factor a very large number that's a product of 2 large primes. Hence it's easy to encrypt but hard to decrypt. Correct me if I'm wrong.

Same thing goes for a cube. Given a random scramble, you can easily get to a random state. But even better/worse, you can _never_ recover the scramble unless you have it, because there are too many scrambles and lengths of scrambles that can lead to the same scrambled state. So I was wondering if a cube scramble would be an even more secure data encryption system? (I dunno about tediousness or how you're gonna encrypt/decrypt it, it's just the idea that it's extremely easy to get to a scrambled state with a given scramble but extremely hard (in fact, impossible) to recover that exact scramble given the state.)

Note that it _is_ possible to factor a large composite number by brute force and to know that you've got the right answer once you've gotten it, but it's impossible to know which scramble was used to scramble a cube even if your computer churned out a million scrambles to reach that state. In fact, if you use a scramble of length, say, 200, I really don't see how any computer in the world can recover that exact scramble.

Keep in mind after reading all this, that I'm still a high school student and know nothing much about what I'm talking about, I just had a random idea and was wondering if it was feasible, that's all


----------



## Stefan (Oct 23, 2008)

blah said:


> Iit's based on the fact that there's no simple/efficient algorithm to factor a very large number that's a product of 2 large primes. Hence it's easy to encrypt but hard to decrypt.



I'm also no expert but I'd say that's only half of the story. It's also easy to shatter a ming vase and hard to get it back together. Doesn't mean it's good for encryption.

In RSA, the product of the two large primes and the additional numbers have useful properties enabling encryption/decryption. So yes, reconstructing a scramble is hard/impossible, but how are you going to use the knowedge of the scramble for encryption/decryption?

Btw, you don't need to be able to factorize that product of two large primes in order to break RSA, that's only the most obvious/promising approach.


----------



## Lucas Garron (Oct 23, 2008)

StefanPochmann said:


> Btw, you don't need to be able to factorize that product of two large primes in order to break RSA, that's only the most obvious/promising approach.


Hmm, I thought that knowing how to break it was equivalent to factoring, because you can get the factorization from it? Maybe I don't remember enough, and I certainly don't have time to take off from math homework to figure it out...

Oh, and blah: Yeah, it really doesn't make sense. However, you can certainly use cube states as a reasonably large keyspace...


----------



## Stefan (Oct 23, 2008)

Ok I might be wrong about that. But here's some info:
http://en.wikipedia.org/wiki/RSA_problem

Says factoring n and determining d are equivalent, maybe that's what you have in mind. But what you're actually after is to undo the encryption. Encryption computes the e-th power, and decryption computes the e-th root. In RSA the computation of the e-th root is actually done as the d-th power, so finding d (or factoring n) empowers you to decrypt. But I think there could also be a different way to compute e-th roots.


----------



## blah (Oct 23, 2008)

Okay fine, I was just being stupid  Maybe I'll start thinking about using Magic for data encryption 

Edit: @Lucas, would all the legal states of a Megaminx be a large enough keyspace then? 

Edit2: New stupid thought: Pretend every cube state is a "prime number", and "multiply" any two of them to generate a third cube state, which would be the "extremely large number". Oh, wait, is "multiplying" cube states commutative? i.e. does XY = YX?


----------



## cmhardw (Oct 23, 2008)

blah said:


> Okay fine, I was just being stupid  Maybe I'll start thinking about using Magic for data encryption



blah I think I see what you mean. Generate a scramble, say 200 moves long, and turn it into a base 18 number. Base 18 is used because there are 18 possible HTM turns. Let this base 18 number be your encryption code. The hard part for a potential cracker is to figure out how many digits long this number is.

Also, to be interesting you could convert the base 18 number into base 10, but I don't know if this is useful or pointless from a decryption standpoint.

Also, your base 18 number has potential to be divisible by 2, or many other numbers, so it might be a composite or highly composite number. I don't know if this is bad from a decryption standpoint, but my guess is that it might be.



> Edit2: New stupid thought: Pretend every cube state is a "prime number", and "multiply" any two of them to generate a third cube state, which would be the "extremely large number". Oh, wait, is "multiplying" cube states commutative? i.e. does XY = YX?



No, cube states are not necessarily commutative. The super-flip commutes with anything, but these two algorithms do not commute:
1) R' F R' B2 R F' R' B2 R2
2) R U' R D2 R' U R D2 R2

Chris


----------



## rachmaninovian (Oct 23, 2008)

maybe this idea can be used for my research project at school. 
me and my teammates have thought of other ways which doesnt seem feasible in improving the RSA system, like the simplex lock whereby a few people with their own private keys can decrypt a certain message. but then if 2 people have the same keys then the chinese remainder theorem cannot be used to find a unique key. So yea, problems, problems, and more problems.

An external lecturer at NUS thought that it would be a good idea, but he said that the RSA system is already very mature and you would be multi-billionaires to come up with a better system.  or to even improve on the system to start with. after all, the RSA system has been around since..1977? I forgot.


----------



## irinaatcolumbia (Oct 23, 2008)

If you can, check out the following 1992 article:

Mitchell, Douglas W. (1992). "RUBIK'S CUBE" AS A TRANSPOSITION DEVICE. Cryptologia, 16 (3), 250-256.
_
Abstract: This paper points out that the well-known “Rubik's Cube” can be used as a device for implementing a transposition cipher which is simple to operate and which should afford a high level of security. A particular system for using the cube is proposed. The system is secure against brute force attacks; since it permits a different scrambled ordering of letters for each letter block enciphered, it is also secure against multiple anagramming._

I think, this is perhaps what you have in mind. It's interesting, but I never thought of an application in RSA. However, the AES (Advanced Encryption Standard) is a block cipher. The algorithm is based on perumations. It takes the information, which you want to encrypt, and wraps it around a giant rubik's cube, and twists it to scramble. The scrambled cube is sent to the receiving party, which uses the key to read the information. The bigger the key, the bigger the cube. I think that's the gist of it, but I don't know anything about cryptography.

Comprehensive mathematical explanation here: http://www.csrc.nist.gov/publications/fips/fips197/fips-197.pdf


----------



## Swordsman Kirby (Oct 23, 2008)

cmhardw said:


> blah said:
> 
> 
> > Okay fine, I was just being stupid  Maybe I'll start thinking about using Magic for data encryption
> ...



Here's a simpler example of two algorithms that don't commute with each other:

1) U
2) F

UF != FU


----------



## Cyber (Oct 23, 2008)

blah said:


> Iit's based on the fact that there's no simple/efficient algorithm to factor a very large number that's a product of 2 large primes. Hence it's easy to encrypt but hard to decrypt.


Heice would be great for my improve soon...I just dont know how it works...


----------

