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

[blah]

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]

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]

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]

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]

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

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]

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

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]

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]

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]

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

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

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

1) U
2) F

UF != FU

 

[Cyber]

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...