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