I was recently doing a calculation involving polynomials when I noticed the following: The function: 1 2 1 y = ( - x + - x + C ) mod P 2 2 where C is any integar constant, and P is any integral exponent of 2, given any positive integer less than P as input in x, will produce a unique positive integer output in the same range, [0,P). Hence we have an encryption technique which works well for binary data. Decrypting this is a bit trickier. It is possible to find the inverse equation for this, (without the modulus) which is: x = SQR(2(y-c) + 1/4) - 1/2 (SQR=Square root) Finding the square root of the modulus is the tricky part, but it is possible, since for every number it is possible to add some multiple of P and find a rational square root (There is a fairly systematic way to do this; I don't want to bore you with the math right now, I'll go into it later if anyone wants. Just trust me for now; it's possible to do without too much computation.) Now, there are some ways to beat this if you were encrypting one byte at a time, such as looking for recurring spaces in ASCII text, but if you were to group 8 bytes together and set p=2^64, it would be fairly difficult to crack. Anyway, in case you're getting bored, here comes the fun part: What happens when we double-encrypt with this technique? Well, obviously you need to use both keys (both values of C) in order to unencrypt it. For encrypting tho, we have a nested function of x: 1 1 2 1 2 1 1 2 1 y = - ( - x + - x + C ) + - ( - x + - x + C ) + D 2 2 2 2 2 2 where D is a second constant. This multiplies out to a fourth degree polynomial which can not be easily factored to find it's orininal components. Adding a third layer of encryption creates an eighth degree polynomial which is hopelessly beyond factoring in any reasonable amount of time. Hence, it is impossible to determine the decryption key if one has the encryption key. Therefore, the multiplied polynomial can be distributed as a public key, and the inverse functions needed to decrypt are kept secret (private key). Has this ever been tried before? Has it been broken? I don't see any way to break this, but I could be overlooking something. If this works it seems like it might be simpler to generate keys for than RSA. I wrote out an example of this on paper here, picking some values for C, and got: 4 3 2 y = .125x + .25x + 63.875x + 63.75x + 8159 and I was able to find values of x for values of y. Go ahead, post a number, I can decode it (can you?). Oh, don't forget to say what P is. :) P.S. In case you're wondering where that function came from, and why it always produces integars, it's a representation of the series 1+2+3+4+5...
Matthew J Ghio wrote:
1 1 2 1 2 1 1 2 1 y = - ( - x + - x + C ) + - ( - x + - x + C ) + D 2 2 2 2 2 2
4 3 2 y = .125x + .25x + 63.875x + 63.75x + 8159
By expanding the equation above (the top one), I got this: y = 1/8*x^4 + 1/4*x^3 + (3/8 + c/2)*x^2 + (1/4 + c/2)*x + (1/2*c + 1/2*c^2 + d) and by matching powers, got the following equations: c/2 + 3/8 = 63.875 1/2*c^2 + 1/2*c + d = 8159 These equations are easily solved for c = 127, d = 31. From there, I can compute the required inverse equations, and so on. I'm not too sure about the security of this method; it seems it boils down to solving simultaneous equations, which yield the constant terms. And you even know how many nested equations there are from the power of the leading term. But, as a test, post a harder one (maybe four or more nestings) and see if I can get it! -- Karl L. Barrus: klbarrus@owlnet.rice.edu keyID: 5AD633 hash: D1 59 9D 48 72 E9 19 D5 3D F3 93 7E 81 B5 CC 32 "One man's mnemonic is another man's cryptography" - my compilers prof discussing file naming in public directories
From what I can tell from your description, you (may) have created a "one-way function." Nest enough terms and you indeed have a function
Matthew, that is difficult to invert. Cellular automata do the same thing...crunch for several generations, and the inverse is very hard to find. (BTW, Steven Wolfram was once touting cellular automata as an ideal encryption scheme. Indeed, running a linear CA on a string can scramble it quite a bit. The problem is that inverses cannot be easily found, and if they can, so can the opponent. Also, someone later showed that CAs are essentially equivalent to linear feedback shift register (LFSR) schemes, which have been analyzed and are not P-K systems. I'm not saying your scheme is the same, though.) But what you need for crypto is a _trapdoor_ one-way function, one for which a very fast (but secret, of course) inverse does exist. In RSA, the knowledge of the originally chosen primes p and q allows the "owner" of the public and private keys to quickly decrypt a message. Anyone who does not know the p and q values cannot compute the inverse in the ring (p -1)(q - 1), and so must try to factor n to find p and q. In your scheme, a message may be easily turned into a jumble (as with a cellular automata, an LFSR, etc.), but how will it be unjumbled easily? If you can compute the inverse, so can anyone else. The RSA scheme allows the owner to compute an inverse in a very clever way, using number theory. I don't see how your systems allows this. I could be missing something basic about your idea. (And, in any case, I really like that you are trying to come up with new schemes.) -Tim May -- .......................................................................... Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@netcom.com | anonymous networks, digital pseudonyms, zero 408-688-5409 | knowledge, reputations, information markets, W.A.S.T.E.: Aptos, CA | black markets, collapse of governments. Higher Power: 2^756839 | Public Key: PGP and MailSafe available. Note: I put time and money into writing this posting. I hope you enjoy it.
Timothy C. May <tcmay@netcom.com> wrote:
But what you need for crypto is a _trapdoor_ one-way function, one for which a very fast (but secret, of course) inverse does exist. In RSA, the knowledge of the originally chosen primes p and q allows the "owner" of the public and private keys to quickly decrypt a message.
Ah... but I do have exactly such a "trapdoor". Consider the output produced by y = 0.5x^2 + 0.5x: (p=2^3) y mod 8 x y in binary - -- --------- 0 0 000 1 1 001 2 3 011 3 6 110 4 10 010 5 15 111 6 21 101 7 28 100 Note that the last digit of the binary number repeats every four numbers. From only the last number, I know that x mod 4 must be only one of two values. By looking at the second to last binary digit of y, I can narrow my list further, by deducing that x mod 8 could only be one of two values. I can then test those two values and determine x. For example: Suppose I am given the value 1101 and p=16. I first try x=0. That gives me zero, so that must be wrong. I try x=1, and I get a 1 for the last digit. That macthes what I have. So next I try x=1 and x=2. x=1 goves me 01, so that's right. Next I try x=1 and x=6. (6 because 2^3-1=7, 7-x=6) x=1 gives me 001, that's not it. 6 gives me 101, which is what I'm looking for. Finally I try 6 and 9. (because 2^4-1=15 and 15-6=9) 6 gives me 0101, which isn't it, so I try 9, which gives me 1101. So the answer is x=9. (and in fact, .5(9)^2 + .5(9) = .5(81) + .5(9) = 45, which in binary is 101101; mod 16 = 1101 , which is what we started with.) So the inverse does exist and can be solved with relativly few calculations. I suppose this is what L. Detweiler was referring to, am I correct? Now, the public key part of the system: Previously, I posted the following sample polynomial: 4 3 2 y = .125x + .25x + 63.875x + 63.75x + 8159 Karl Lui Barrus quickly pointed out how easily he could solve it. (I really only intended it as an example, so I didn't try to make it too difficult.) But since we now have the values, I'll go ahead and use this example again to show how to actually solve it, and point out ways it could not be solved. Since we have C=127, D=31, we can solve for any x, given y and p. I didn't give a value for p earlier, so let's use p=256 (one byte encryption. Of course this could be brute-force attacked, but let's keep the math simple for this demonstration.) Suppose we have y=61. To solve for x, we first subtract D, conevert to binary and solve with the above method. To save space, I won't go into the calculation here, but go ahead and try it yourself if you want. You should come up with 172. This can be checked easily: (172^2)/2 + 172/2 + 31 = 29584/2 + 172/2 + 31 = 14792 + 86 + 31 = 14909 Taking 14909 mod 256, we get 61, so it checks out. Next we do the same step again, starting with y=172. I fairly quickly solved this to get x=9. Nine is, in fact, what was put in originally. This can be shown by: 4 3 2 y = (.125x + .25x + 63.875x + 63.75x + 8159) mod 256 4 3 2 y = (.125(9) + .25(9) + 63.875(9) + 63.75(9) + 8159) mod 256 y = (.125(6561) + .25(729) + 63.875(81) + 63.75(9) + 8159) mod 256 y = (820.125 + 182.25 + 5173.875 + 573.75 + 8159) mod 256 y = 14909 mod 256 y = 61 Note that none of the preceeding could have been done without knowing the values of C and D. So if Karl Barrus can find C and D using his clever factoring technique, does that defeat the system? Actually, Karl's trick is easy to avoid. Since the entire polynomial is mod 256, we can mod each term by 256. Which gives: 4 3 2 y = (.125x + .25x + 63.875x + 63.75x + 223) mod 256 which still produces the same values for y, but the factoring technique fails. One other question which could be asked is, does the technique for calculating roots of moduli work for the entire polynomial? A view of a sample of numbers reveals that it does not: x y binary y - --- -------- 0 223 11011111 1 95 01011111 2 98 01100010 3 238 11101110 4 12 00001100 5 200 11001000 6 49 00110001 7 89 01011001 which reveals no repeating patterns in the last digits (or any digits). In summary, I see no method which would yeild the original input without knowing the values added to the nested polynomials (the private key), and there is no way to determine the private key if the modulus is applied to the resulting function. P.S. I could beat the RSA system too, if the modulus was left out. :)
Matthew J Ghio wrote:
we can mod each term by 256. Which gives:
4 3 2 y = (.125x + .25x + 63.875x + 63.75x + 223) mod 256
which still produces the same values for y, but the factoring technique fails.
I still don't know about that - I think all it does is remove the problem one step from immediately solvable. Is that P term public knowledge (here P = 256)? If so, the revised equations are: c1/2 + 1/4 = 63.75 ===> c1 = 127 c1/2 + 1/4 x1^2 + c2 = 223 + 256k ===> c2 = -7905 + 256k And this will yeild either c2 = -225 or c2 = 31. The computational expense of trying both is small. If it does turn out that the magnitude of the constants must be less than P, I don't think taking the mod of each coefficient obscures the problem very much at all. It still boils down to solving systems of simultaneous equations, which isn't the same complexity as solving discrete logarithms or factoring. -- Karl L. Barrus: klbarrus@owlnet.rice.edu keyID: 5AD633 hash: D1 59 9D 48 72 E9 19 D5 3D F3 93 7E 81 B5 CC 32 "One man's mnemonic is another man's cryptography" - my compilers prof discussing file naming in public directories
Matthew J Ghio wrote:
In summary, I see no method which would yeild the original input without knowing the values added to the nested polynomials (the private key), and there is no way to determine the private key if the modulus is applied to the resulting function.
I've been thinking about this (well, not too much since I'm in the midst of midterms week :-). I beleive the equation leaks information. When you expand the equation symbolically, it is easy to solve for the constants by matching the coefficients of the highest powers and working backwards. If the constants can be negative as well as positive, the signs of some of the terms will reflect this. We know the magnitude of the constants must be less than P, which is public. But can they be negative - will the decoding process still work? Or, will you obtain the correct decoding for the correct choice and an incorrect decoding for the incorrect choice? If it turns out that either choice will decode a number to the same value, or if the decoding won't work with negative numbers, then this method is too easy to invert. If the constants can't be negative, or if they can be but it doesn't make a difference in the decoding, then taking the modulus doesn't obscure anything at all. For example, suppose c = 127 and d = -225. Then y1 = 7903. + 63.75 x + 63.875 x + 0.25 x + 0.125 x which becomes (after mod 256) y1 = 223. + 63.75 x + 63.875 x + 0.25 x + 0.125 x However, if c = 127, d = 31, then y2 = 8159. + 63.75 x + 63.875 x + 0.25 x + 0.125 x which becomes (after mod 256) y2 = 223. + 63.75 x + 63.875 x + 0.25 x + 0.125 x So y1 = y2. Here, d = -225 and d = 31 yeild the same equation (after mod operation). Now I need to try the decoding process to see if d = -225 or d = 31 yeild the same or different answers. -- Karl L. Barrus: klbarrus@owlnet.rice.edu keyID: 5AD633 hash: D1 59 9D 48 72 E9 19 D5 3D F3 93 7E 81 B5 CC 32 "One man's mnemonic is another man's cryptography" - my compilers prof discussing file naming in public directories
Karl Lui Barrus wrote:
I beleive the equation leaks information. When you expand the equation symbolically, it is easy to solve for the constants by matching the coefficients of the highest powers and working backwards. If the constants can be negative as well as positive, the signs of some of the terms will reflect this.
You're right. You know that the x^2 term is (c/2 + 3/8)x^2 so you can just solve for c from there. Once you have c, you can solve for c2. So, if I could prevent you from finding c, then you couldn't solve it. How can I do this? By adding another constant. So far, I have just added a constant after each term. This leaves open the possibility that I could also add one at the beginning. (I'll call the constants A, B and C for simplicity). Therefore I'd have something like the following: F(G(H(x))) where: F(x) = (1/2)x^2 + (1/2)x + C G(x) = (1/2)x^2 + (1/2)x + B H(x) = x + A Expanding this, we have something which begins: (1/8)x^4 + ((A+1/2)/2)x^3 + ((3/2)a^2+(3/2)a+b+3/4) + ... So you can still solve for A, which lets you solve for B, which lets you break my cipher and find my private key. But consider the following: Up to now, I have simply added a constant before and after each nested term. I (or you) can easily reverse this process by subtracting the constant, and then inverting the functions. I can add an additional layer of security by multiplying the result of the function by an odd number and taking the modulus. As long as I multiply by an odd number and take the modulus of a power of 2, the process can be reversed. Now if I do this at the beginning and after each of the functions I get: F(G(H(x))) where: F(x) = (F/2)x^2 + (F/2)x + C G(x) = (E/2)x^2 + (E/2)x + B H(x) = Dx + A Expanding this, I get: (1/8)fe^2d^4x^4 + ((a+1/2)/2)fe^2d^3x^3 + (1/2)((3/2)ea^2+(3/2)ae+b+e/4+1/2)fed^2x^2 + (1/2)(ea^3+(3/2)ea^2+ea/2+2ab+b+a+1/2)fedx + fe^2a^4/8+fe^2a^3/4+fea^2b/2+fe^2a^2/8+feab/2+fb^2/2+fea^2/4+fea/4+fb/2+c Picking some random values for A, B, and C, and picking some random odd numbers for D, E, and F, plugging them into the equation, and then taking mod 256, I came up with the following: 136.375x^4 + 139.25x^3 + 33.625x^2 + 110.75x + 179 So what values for A,B,C,D,E,& F did I use? Have fun factoring! :)
Karl Lui Barrus wrote:
We know the magnitude of the constants must be less than P, which is public. But can they be negative - will the decoding process still work? Or, will you obtain the correct decoding for the correct choice and an incorrect decoding for the incorrect choice? If it turns out that either choice will decode a number to the same value, or if the decoding won't work with negative numbers, then this method is too easy to invert.
If the constants can't be negative, or if they can be but it doesn't make a difference in the decoding, then taking the modulus doesn't obscure anything at all.
Moduli are always positive. It is interesting to note that since x^2 mod y = (-x)^2 mod y, then x^2 mod y = (y-x)^2 mod y. So whenever you have a square root modulus, you have at least two numbers in the domain which will produce the same outcome.
participants (3)
-
Karl Lui Barrus -
Matthew J Ghio -
tcmay＠netcom.com