Printable View
This algorithm is known as the Son of the Tsars Algorithm and is donated into the public domain.
Chose any 2 primes such that a=b=5 mod 12. Let n= a mod b and x=plaintext and c=cyphertext.
c=x^3 mod n and x=c^((a+1)/6) mod n=c^((b+1)/6) mod n. This algorithm is faster than the Rabin and could compete with the RSA.
This algorithm is known as the Son of the Tsars Algorithm and is donated into the public domain.
Chose any 2 primes such that a=b=5 mod 12. Let n= a mod b and x=plaintext and c=cyphertext.
c=x^3 mod n and x=c^((a+1)/6) mod n=c^((b+1)/6) mod n. This algorithm is faster than the Rabin and could compete with the RSA.
have you got a link with more info,
I can't seem to google anything usefull..
I'd like to read more..
have you got a link with more info,
I can't seem to google anything usefull..
I'd like to read more..
Found this:
http://groups.google.de/group/sci.cr...800c8dc742c2d7
It's a joke.
explainify or tip me off to a good site on algorithms etc cause sa=sdaf3f=23fw^69 is too nerdy for me right now
No tests have been done as far as I can tell on the strengths of this system, at the moment it has just been subbmitted by some guy on a google group. Until serious study has been done or at least some proper documentation written about how it works then no one would bother taking it up.
P.S. I'm running it through MAPLE with the same scripting that i would use for RSA testing so I will post results
Can you shed some insight to those of us not mathematically gifted? Or explain how you know it's a joke, and let us in on said joke...I mean, besides Luc the Perverse at sci.crypt said so?!?Quote:
Originally posted here by bAgZ
Found this:
http://groups.google.de/group/sci.cr...800c8dc742c2d7
It's a joke.
There's a lot of discussion further on that, to someone who is *not* in that level of the math, looks like these folks are clearly debating a serious point. Anyone got any info that's relevant?
Whenever you see the term mod it means the remainder you were taught in school. For example, 6 divided by 7 equals 0 remainder 6. SO let us choose primes 137 and 89. Both have remainder 5 when divided by twelve. The modulo of 137 to 89 is 48.
Let us choose plaintext value 13. Take 15 to the 15 power (89+1)/6=15. (I switched the encryption and decryption algorithms, sorry.) and take the remainder of that divided by 48. You get 32. Take 32^3 mod 48 and you get 15.
I think the concern here is that people are not going to use the algorithm you supplied because it is free. What proof is there that this is a good algorithm?Quote:
Originally posted here by Overlord_77520
Whenever you see the term mod it means the remainder you were taught in school. For example, 6 divided by 7 equals 0 remainder 6. SO let us choose primes 137 and 89. Both have remainder 5 when divided by twelve. The modulo of 137 to 89 is 48.
Let us choose plaintext value 13. Take 15 to the 15 power (89+1)/6=15. (I switched the encryption and decryption algorithms, sorry.) and take the remainder of that divided by 48. You get 32. Take 32^3 mod 48 and you get 15.
I am not going to say it isn't, just prove to us it is using more than that.
-Deeboe
I erred in one of my assumptions and I apologize for that. Take 2 integers (need Not be primes) such that both are congruent to 5 mod 12 and the mod equals 12 . c=x^3 mod 12 and x=c^(((number 1 or 2) +1)/6) mod 12. Again sorry for the error.
NOT a good algorithm. The reason that block algorithms work so well is that they take a BLOCK of values and essentially split up the values around based on the key. Only if you have a key can you put the block back together into its original values. Encrypting character by character allows for logical deduction of the original values. Do you know how hard it is to create a bruteforce cracker of this algorithm? Probably half an hour once i analyze it better. Sorry buddy, but thanks but no thanks.
And to be blunt, you might just be barking up the wrong tree here. We have perhaps a handful of folks who could carry on a meaningful debate about the mathematical aspects of this algorithm, but I for one am more interested in the practical application of said algorithm, after I've been given the go-ahead by People Smarter Than Me (TM) that it is acceptable to use. The focus here is probably more on implementation, not theory.
Sci.Crypt might be a better place to discuss this. I'm not chasing you away, but it's like trying to sell a microwave oven to a starving family in Ethiopia...some of us'll just look at you, drool, and nod appreciatively from time to time.
/* Note: I am *NOT* speaking for the community here, just offering my personal perspective on the group. */
Even with my admittedly limited mathematic skills, this just doesn't work AT ALL. Okay so say the two numbers chosen are... 221 and 65.
a= 221
b=65
so n is 221%65(don't use 17 with 221, produces a modulo of 0) is 26
n=26
and lets say that we encrypt the value of 'A' which is 65.
x=65
since c is (x^3)%12 so c will be: 5
c=5
now lets try decoding it:
since x = (c^((a OR b +1)/6))%12
so x will be: (c^11)%12 OR (c^37)%12
x=5
is it me or is this not working?
Locked, the problem with your analysis is you've chosen an a and b such that your n turns out to be less than your x. Because your x is greater than the modulus it is impossible to revert back to it from the ciphertext because the only unique values are the class representatives of the modulus. Everything else is simply x + n*k and there's no way to know what k is, hence why the modulus NEEDS to be greater than any x you apply it to.
On to the algorithm...
This resembles RSA almost identically, obviously the d, e, and p/q are chosen differently. The fact that your public exponent is static is troublesome though, this means any a & b that give that modulus n could be used to decrypt your message assuming they meet your 5 mod 12 requirements. I'm not in a position to prove how hard that would be, I can't think of a proof off the top of my head and I'm running short on time at the moment. However the strength in RSA is that the exponent is generated from phi(p*q) and the decryption exponent relies on the encryption exponent through this value which is only computable if you know p & q which should be near impossible to factor from the public n if you've chosen them correctly. You make no statement on the size of your n and you also make no proof that a & b are primes, meaning n may be easily factorable which in turn means you could find the d that would work for your n by finding the inverse of 3 mod phi(n) if no little catches show up from the a & b chosen.
This is also unbelievably vunerable to a broacast attack. Send your message to 3 different people using their public keys, assuming they're each unique, and this is broken. You can simply build the message back from the ciphertext using the same technique used on the toy RSA model that first brought about the idea.
You could argue that this isn't meant for public/private key systems and it might be acceptable depending on the size of your a & b but unless you can prove that the 5 mod 12 actually ensures the decryption method works ONLY for those two numbers then your system is even weaker.
For example.. somehow you get a mod of 26 like Locked came up with. If I can come up with numbers such as 56 and 30 that give me the same n and they work, then you have a problem. I'm not saying those numbers work, I doubt they do, I just added 30 to 26. But if a situation like this exists then it might be quite feasible to just solve for a smaller a & b than were actually used, making brute forcing the key even easier.
Ah thank you for the correction. With that new stipulation, you add a new round of calculations and thus a new method of cracking. i'm going to work up a quick script that will look for patterns in series of known cipher text and the results. If two different numbers match another set of numbers then its crackable. Hmm, I should run it overnight cuz it could take awhile. I'll let you guys know the result tomorrow.
As Pecosian mention, this looks to be a standard assymetric encryption algorithm in the one-way function family:
"Fy,n(X) =Y^X mod N"
As most are probably aware, RSA and Diffie Hellman algorithms are just two in this family, and current cryptographic research is in much more advanced mathmatical formulas. The important thing about these algorithms that hasn't been mentioned is that their strength relies on selecting your variables such that they are very large random primes. Obviously the use of "1" and "2" as primes makes breaking trivial. Even primes like "327" and "611" (I have no idea if these are actually prime, but you get the idea) are trivial to break. You need MUCH larger primes to make factoring computationally infeasible.
The most difficult part of implementing assymetric algorithms such as these is the multiplication (an raising to powers) of HUGE numbers. We are talking dozens to hundreds of digits. Unless you are very familiar with things like Karatsuba multiplication, chinese rendering, and Montgomery multiplication, you will not be able to implement such an encryption that is at all usable.
Im no cryptographer, but since it is based on a well known one-way function family, I would guess that the mathmatics are fairly secure. Its not cutting edge, but probably fine. Implementation is another story.
Organ, just a heads up but if you see the flashing date on the thread that means its old and really shouldnt be replied too as the person who started it has prolly moved on or got their answer. Take a look at the AO FAQ and enjoy your stay here!
Ah crap. Don't I feel stupid replying to a 4 month old post. Sorry.