<div dir="ltr"><div><div>Enjoy breaking this probably very old crypto system that was probably broken decades ago :)</div><div><br></div></div><div>Here's my dumb idea for the day: public key crypto system based on a set of "reduction rules" applied to polynomials.  It's pretty simple.  I'm using just 2 variables in the polynomials: x, and y, though the technique extends to more.  The polynomials have this form:</div><div><br></div><div>axy + bx + cy + d</div><div><br></div><div>where a, b, c, and d might be 128 bit numbers modulo a 128 bit prime p.  I want to do DH key agreement, so I want to compute </div><div><br></div><div>(axy + bx + cy + d)^x<br></div><div><br></div><div>for some secret x.  Multiplying this out gives larger and larger polynomials.  One technique to keep them small is to take them modulo some fixed polynomial.  Instead, I'm using a couple of simple "reduction rules".  The two rules are:</div><div><br></div><div>    x^2 => x + 3</div><div>    y^2 => 2y</div><div><br></div><div>These rules result in a unique reduction of any polynomial of x and y with integer coefficients to the form axy + bx + cy +d.  The "addition operator", which is really multiplication, is computed this way:</div><div><br></div><div><div>    (a x y + b x + c y + d) (e x y + f x + g y + h)</div><div>    = dexy + bex^2y + cexy^2 + aex^2y^2 + dfx + bfx^2 + cfxy + afx^2y + dgy + bgxy + cgy^2 + agy^2x + dh + bhx + chy + ahxy</div><div>Now apply reductions</div><div>    = dexy + be(x+3)y + 2cexy + 2ae(x+3)y + dfx + bf(x+3) + cfxy + af(x+3)y + dgy + bgxy + 2cgy + 2agyx + dh + bhx + chy + ahxy</div><div>    = dexy + bexy + be3y + 2cexy + 2aexy + 2ae3y + dfx + bfx + bf3 + cfxy + afxy + af3y + dgy + bgxy + 2cgy + 2agyx + dh + bhx + chy + ahxy</div><div>    = dexy + bexy + 3bey + 2cexy + 2aexy + 6aey + dfx + bfx + 3bf + cfxy + afxy + 3afy + dgy + bgxy + 2cgy + 2agyx + dh + bhx + chy + ahxy</div><div>    = xy(de + be + 2ce + 2ae + cf + af + bg + 2ag + ah) + x(df + bf + bh) + y(3be + 6ae + 3af + dg + 2cg + ch) + (3bf + dh)</div></div><div><br></div><div>This gives the formulas for new coefficients A, B, C, and D, in terms of a, b, c, d, e, f, g, and h:</div><div><br></div><div><div>    A = (d*e + b*e + 2*c*e + 2*a*e + c*f + a*f + b*g + 2*a*g + a*h) % p</div><div>    B = (d*f + b*f + b*h) % p<br></div><div>    C = (3*b*e + 6*a*e + 3*a*f + d*g + 2*c*g + c*h) % p<br></div><div>    D = (3*b*f + d*h) % p<br></div></div><div><br></div><div>With this addition rule, I can define multiplication in the usual way, and use it for DH key agreement.  The identity element is (0, 0, 0, 1) meaning a = 0, b = 0, c = 0, and d = 1.</div><div><br></div><div>The resulting groups have cycle lengths up to p^2 - 1.  Are prime power sized groups as secure as groups with prime size?  If so, and with the wildly optimistic assumption that this dumb scheme has bit security equal to sqrt(group size), then just maybe using 128 bit values for A, B, C, and p result in 128-ish bits of security.  Probably not, though :)</div><div><br></div><div>Partially, the motivation here is to include elements of add-xor-rotate hash functions.  The x^2 => (x + 3) reduction rule creates terms that combine with the constant term, sort of simulating right shift  Without it, the constant term is just d^x mod p, which is too easy to break.  The multiplications give an addition-like mixing from lower to higher order terms, while truncating the exponents seems to give me non-linearity like I get with XOR.  If these function as I hope, the output bits (the coefficients a, b, c, and d) should be uniformly pseudo-random and resist analysis.</div><div><br></div><div>I've attached some hacked up Python code.</div><div><br></div><div>Bill<br></div></div>