
January 31st, 2006, 06:13 PM
#11
Junior Member
Faulty Algorithm
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.

January 31st, 2006, 10:03 PM
#12
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.

January 31st, 2006, 10:23 PM
#13
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 goahead 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. */
"Data is not necessarily information. Information does not necessarily lead to knowledge. And knowledge is not always sufficient to discover truth and breed wisdom." Spaf
Anyone who is capable of getting themselves made president should on no account be allowed to do the job. Douglas Adams (19522001)
"...people find it far easier to forgive others for being wrong than being right."  Albus Percival Wulfric Brian Dumbledore

February 1st, 2006, 04:30 AM
#14
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?

February 1st, 2006, 08:52 PM
#15
Senior Member
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.
Reality is the one who has it wrong, not you

February 1st, 2006, 10:51 PM
#16
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.

June 19th, 2006, 08:07 PM
#17
Junior Member
As Pecosian mention, this looks to be a standard assymetric encryption algorithm in the oneway 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 oneway function family, I would guess that the mathmatics are fairly secure. Its not cutting edge, but probably fine. Implementation is another story.

June 19th, 2006, 10:05 PM
#18
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!

June 19th, 2006, 10:18 PM
#19
Junior Member
Ah crap. Don't I feel stupid replying to a 4 month old post. Sorry.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

