[Cryptography] Yet another dumb crypto system

[Bill Cox]

Enjoy breaking this probably very old crypto system that was probably
broken decades ago :)

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:

axy + bx + cy + d

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

(axy + bx + cy + d)^x

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:

    x^2 => x + 3
    y^2 => 2y

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:

    (a x y + b x + c y + d) (e x y + f x + g y + h)
    = dexy + bex^2y + cexy^2 + aex^2y^2 + dfx + bfx^2 + cfxy + afx^2y + dgy
+ bgxy + cgy^2 + agy^2x + dh + bhx + chy + ahxy
Now apply reductions
    = 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
    = dexy + bexy + be3y + 2cexy + 2aexy + 2ae3y + dfx + bfx + bf3 + cfxy +
afxy + af3y + dgy + bgxy + 2cgy + 2agyx + dh + bhx + chy + ahxy
    = dexy + bexy + 3bey + 2cexy + 2aexy + 6aey + dfx + bfx + 3bf + cfxy +
afxy + 3afy + dgy + bgxy + 2cgy + 2agyx + dh + bhx + chy + ahxy
    = xy(de + be + 2ce + 2ae + cf + af + bg + 2ag + ah) + x(df + bf + bh) +
y(3be + 6ae + 3af + dg + 2cg + ch) + (3bf + dh)

This gives the formulas for new coefficients A, B, C, and D, in terms of a,
b, c, d, e, f, g, and h:

    A = (d*e + b*e + 2*c*e + 2*a*e + c*f + a*f + b*g + 2*a*g + a*h) % p
    B = (d*f + b*f + b*h) % p
    C = (3*b*e + 6*a*e + 3*a*f + d*g + 2*c*g + c*h) % p
    D = (3*b*f + d*h) % p

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.

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 :)

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.

I've attached some hacked up Python code.

Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150923/19ec6a9b/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: reduce_dh.py
Type: text/x-python
Size: 1866 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150923/19ec6a9b/attachment.py>