''' El-Gamal solution ''' import sys import string username = sys.argv[1].upper() # Coefficient group zg = [0, 1, 2] # Generate the dictionary chars = list(string.ascii_uppercase) dictionary = {} def polystr(coeffs): s = "" for i in xrange(0, len(coeffs)): if coeffs[i] > 0: if len(s) > 0: s += " + " if i == 0: s += "%d" % coeffs[i] elif i == 1: s += "%dx" % coeffs[i] else: s += "%dx^%d" % (coeffs[i], i) s = s.replace("1x", "x") # print c, s return s k = 0 for third in xrange(0, 3): for second in xrange(0, 3): for first in xrange(0, 3): if (first + second + third > 0): coeffs = [zg[first], zg[second], zg[third], 0] print chars[k], " = ", polystr(coeffs) dictionary[chars[k]] = coeffs k += 1 def degree(p): for i in xrange(len(p) - 1, -1, -1): if p[i] > 0: return i assert(False) # Zero def trim(poly): return poly[: 1+degree(poly)] def polymul(a, b, zp): c = [0 for i in range(0, 1 + len(a) + len(b))] for i in xrange(0, len(a)): for j in xrange(0, len(b)): c[i + j] = (c[i + j] + (a[i] * b[j])) % zp return trim(c) def monomial(deg, a): poly = [0 for i in range(0, deg + 1)] poly[deg] = a return poly def extend(poly, deg): if len(poly) > deg: return poly else: return poly + [0 for a in range(0, deg - len(poly))] def polyminus(a, b, zp): c = [0 for i in range(0, 1 + max(len(a), len(b)))] a = extend(a, len(c)) b = extend(b, len(c)) for i in range(0, len(c)): c[i] = (a[i] - b[i]) % zp return c def polyplus(a, b, zp): c = [0 for i in range(0, 1 + max(len(a), len(b)))] a = extend(a, len(c)) b = extend(a, len(c)) for i in range(0, len(c)): c[i] = (a[i] + b[i]) % zp return c def polymod(p, q, zp): # p / q with Z_p qh = degree(q) ph = degree(p) if qh > ph or (ph == qh and q[qh] > p[ph]): return p divisor = monomial(ph - qh, p[ph] / q[qh]) res = polymul(q, divisor, zp) rem = polyminus(p, res, zp) return polymod(rem, q, zp) def polypow(p, power, modulo, zp): a = p[:] if power == 0: return monomial(0, 1) for d in xrange(0, power - 1): a = polymod(polymul(a, p, zp), modulo, zp) return a # Encode s = "GALOISFIELD" irreduc = [1, 0, 2, 1] aalist = [117,131,121] secretword = ['VERYMUCH','PROGRAMMING','ENCRYPTION', 'DECRYPTION'] a = aalist[abs(username.__hash__()) % len(aalist)] gen = [0, 1, 0, 0] #printpoly("div", polydiv([3, 0, 4, 1], [1, 0, 1]) strs = [polystr(p) for p in dictionary.values()] inverses = {} p = gen[:] seen = [] for i in xrange(0, 26): seen.append(p) p = polypow(gen, i, irreduc, 3) found = False pstr = polystr(p) # find inverse for p for q in dictionary.values(): pq = polymod(polymul(p, q, 3), irreduc, 3) if degree(pq) == 0 and pq[0] == 1: inverses[pstr] = q print "Inverse of %s is %s" % (pstr, polystr(q)) found = True break if not found: print "Could not find inverse for %s" % polystr(pq) #print pstr assert(strs.count(pstr) == 1) assert(seen.count(pstr) == 0) #print inverses # Now encoding encodestr = "%sLIKESGALOISFIELDS%s" % (username, secretword[abs(username.__hash__()) % len(secretword)]) enc = [] import random beta = polypow(gen, a, irreduc, 3) rev = {} for d in dictionary.keys(): rev[polystr(dictionary[d])] = d random.seed(abs(username.__hash__())) for c in encodestr: m = dictionary[c] k = 1 + int(random.random() * 21) y1 = polypow(gen, k, irreduc, 3) y2 = polymod(polymul(m, polypow(beta, k, irreduc, 3), 3), irreduc, 3) y1c = rev[polystr(y1)] y2c = rev[polystr(y2)] enc.append((y1c, y2c)) print '''El-Gamal: Decode following string with a=%d (private key), generator "x" and group over irreducible polynomial %s, coefficients modulo %d ''' % (a, polystr(irreduc), 3) for (yy1, yy2) in enc: print "(%s, %s)" % (yy1, yy2) # DECODER dec = "" for (y1c, y2c) in enc: y1 = dictionary[y1c] y2 = dictionary[y2c] y1a = polypow(y1, a, irreduc, 3) mpoly = polymod(polymul(y2, inverses[polystr(y1a)], 3), irreduc, 3) m = rev[polystr(mpoly)] dec += m print y1c, y2c, polystr(y1),"y2=", polystr(y2), "-->", polystr(y1a), "inv:", polystr(inverses[polystr(y1a)]) assert(dec == encodestr) for p in dictionary.values(): pa = polypow(p, a, irreduc, 3) print polystr(p), " ---> p^a ==> ", polystr(pa) p = [2, 0, 2] print polystr(p) for i in xrange(2, 10): print "(%s)^%d" % (polystr(p), i), '=', polystr(polypow(p, i, irreduc, 3)) q = [1,0,1] print polystr(q) print polystr( polymul([1,2,1],[1,0,2] , 3) )