AlexanderKud · October 23, 2024 17:42 · Dec 5, 2011 · Dec 5, 2011 · Dec 5, 2011 · Dec 5, 2011
diff --git a/pn.py b/pn.py
@@ -109,6 +109,6 @@ def jacobi2(a, q):
         a1, e = a1 >> 1, e + 1
         pass
     m8 = q % 8
-    s = 1 if m8 % 1 == 0 or m8 == 1 or m8 == 7 else -1
+    s = -1 if m8 == 3 or m8 == 5 else 1 # m8 = 0,2,4,6 and 1,7
     if q % 4 == 3 and a1 % 4 == 3: s = -s
     return s if a1 == 1 else s * jacobi2(q % a1, a1)
diff --git a/pn.py b/pn.py
@@ -85,16 +85,30 @@ def sqrt2(n, q):
 
 
 def jacobi(a, q):
-    """jacobi symbol: judge existing sqrtmod
+    """jacobi symbol: judge existing sqrtmod (1: exist, -1: not exist)
     - j(a*b,q) = j(a,q)*j(b,q)
     - j(a*q+b, q) = j(b, q)
     - j(a, 1) = 1
     - j(0, q) = 0
     - j(2, q) = -1 ** (q^2 - 1)/8
-    - j(p, q) = -1 ^ {(p - 1)/2} * -1 ^ {(q - 1)/2} * j(q, p)
+    - j(p, q) = -1 ^ {(p - 1)/2 * (q - 1)/2} * j(q, p)
     """
     if q == 1: return 1
     if a == 0: return 0
     if a % 2 == 0: return (-1) ** ((q * q - 1) // 8) * jacobi(a // 2, q)
-    return (-1) ** ((a - 1) // 2) * (-1) ** ((q - 1) // 2) * jacobi(q % a, a)
+    return (-1) ** ((a - 1) // 2 * (q - 1) // 2) * jacobi(q % a, a)
 
+def jacobi2(a, q):
+    """quick jacobi symbol
+    - algorithm 2.149 of http://www.cacr.math.uwaterloo.ca/hac/about/chap2.pdf
+    """
+    if a == 0: return 0
+    if a == 1: return 1
+    a1, e = a, 0
+    while a1 & 1 == 0:
+        a1, e = a1 >> 1, e + 1
+        pass
+    m8 = q % 8
+    s = 1 if m8 % 1 == 0 or m8 == 1 or m8 == 7 else -1
+    if q % 4 == 3 and a1 % 4 == 3: s = -s
+    return s if a1 == 1 else s * jacobi2(q % a1, a1)
diff --git a/pn.py b/pn.py
@@ -59,6 +59,7 @@ def sqrt(n, q):
 
 def sqrt2(n, q):
     """sqrtmod for bigint
+    - Algorithm 3.34 of http://www.cacr.math.uwaterloo.ca/hac/about/chap3.pdf
     """
     import random
     # b: some non-quadratic-residue
@@ -76,8 +77,7 @@ def sqrt2(n, q):
     c = pow(b, t, q)
     r = pow(n, (t + 1) // 2, q)
     for i in range(1, s):
-        e = pow(2, s - i - 1, q)
-        d = pow(pow(r, 2, q) * ni % q, e, q)
+        d = pow(pow(r, 2, q) * ni % q, pow(2, s - i - 1, q), q)
         if d == q - 1: r = r * c % q
         c = pow(c, 2, q)
         pass

diff --git a/pn.py b/pn.py
@@ -61,10 +61,10 @@ def sqrt2(n, q):
     """sqrtmod for bigint
     """
     import random
-    # c: some non-quadratic-residue
-    c = 0 
-    while c == 0 or jacobi(c, q) != -1:
-        c = random.randint(1, q - 1)
+    # b: some non-quadratic-residue
+    b = 0 
+    while b == 0 or jacobi(b, q) != -1:
+        b = random.randint(1, q - 1)
         pass
     # q = t * 2^s + 1, t is odd
     t, s = q - 1, 0 
@@ -73,11 +73,11 @@ def sqrt2(n, q):
         pass
     assert q == t * pow(2, s) + 1 and t % 2 == 1
     ni = inv(n, q)
-    c = pow(c, t, q)
+    c = pow(b, t, q)
     r = pow(n, (t + 1) // 2, q)
     for i in range(1, s):
         e = pow(2, s - i - 1, q)
-        d = pow((r * r % q) * ni % q, e, q)
+        d = pow(pow(r, 2, q) * ni % q, e, q)
         if d == q - 1: r = r * c % q
         c = pow(c, 2, q)
         pass

diff --git a/pn.py b/pn.py
@@ -61,30 +61,27 @@ def sqrt2(n, q):
     """sqrtmod for bigint
     """
     import random
-    m = inv(n, q)
-    p, s = q - 1, 0
-    while p % 2 == 0:
-        p, s = p >> 1, s + 1
+    # c: some non-quadratic-residue
+    c = 0 
+    while c == 0 or jacobi(c, q) != -1:
+        c = random.randint(1, q - 1)
         pass
-    w = 0
-    while w == 0 or jacobi(w, q) != -1:
-        w = random.randint(1, q - 1)
+    # q = t * 2^s + 1, t is odd
+    t, s = q - 1, 0 
+    while t & 1 == 0:
+        t, s = t >> 1, s + 1
         pass
-    v = pow(w, p, q)
-    r = pow(n, (p + 1) // 2, q)
-    while True:
-        i, z = 0, r * r * m % q
-        while i < s and z % q != 1:
-            i, z = i + 1, z * z
-            pass
-        if i == 0:
-            return (r, q - r)
-        p2 = s - i - 1
-        if p2 < 0: raise Exception("not found")
-        r = r * pow(v, 1 << p2, q) % q
+    assert q == t * pow(2, s) + 1 and t % 2 == 1
+    ni = inv(n, q)
+    c = pow(c, t, q)
+    r = pow(n, (t + 1) // 2, q)
+    for i in range(1, s):
+        e = pow(2, s - i - 1, q)
+        d = pow((r * r % q) * ni % q, e, q)
+        if d == q - 1: r = r * c % q
+        c = pow(c, 2, q)
         pass
-    assert False, "unreached"
-    pass
+    return (r, q - r)
 
 
 def jacobi(a, q):

diff --git a/pn.py b/pn.py
@@ -73,19 +73,17 @@ def sqrt2(n, q):
     v = pow(w, p, q)
     r = pow(n, (p + 1) // 2, q)
     while True:
-        i = 0
-        z = r * r * m % q
+        i, z = 0, r * r * m % q
         while i < s and z % q != 1:
-            i = i + 1
-            z = z * z
+            i, z = i + 1, z * z
             pass
         if i == 0:
             return (r, q - r)
         p2 = s - i - 1
         if p2 < 0: raise Exception("not found")
         r = r * pow(v, 1 << p2, q) % q
         pass
-    assert False, "not reached"
+    assert False, "unreached"
     pass
 
 

diff --git a/pn.py b/pn.py
@@ -39,7 +39,7 @@ def inv2(n, q):
     s, p2, p = 1, n, q - 2
     while p > 0:
         if p & 1 == 1: s = s * p2 % q
-        p, p2 = p >> 1, p2 * p2 % q
+        p, p2 = p >> 1, pow(p2, 2, q)
         pass
     return s
 
@@ -51,7 +51,7 @@ def sqrt(n, q):
     """
     assert n < q
     for i in range(1, q):
-        if i * i % q == n:
+        if pow(i, 2, q) == n:
             return (i, q - i)
         pass
     raise Exception("not found")
@@ -70,8 +70,8 @@ def sqrt2(n, q):
     while w == 0 or jacobi(w, q) != -1:
         w = random.randint(1, q - 1)
         pass
-    v = w ** p % q
-    r = n ** ((p + 1) // 2) % q
+    v = pow(w, p, q)
+    r = pow(n, (p + 1) // 2, q)
     while True:
         i = 0
         z = r * r * m % q
@@ -83,7 +83,7 @@ def sqrt2(n, q):
             return (r, q - r)
         p2 = s - i - 1
         if p2 < 0: raise Exception("not found")
-        r = r * (v ** (1 << p2) % q) % q
+        r = r * pow(v, 1 << p2, q) % q
         pass
     assert False, "not reached"
     pass
@@ -102,3 +102,4 @@ def jacobi(a, q):
     if a == 0: return 0
     if a % 2 == 0: return (-1) ** ((q * q - 1) // 8) * jacobi(a // 2, q)
     return (-1) ** ((a - 1) // 2) * (-1) ** ((q - 1) // 2) * jacobi(q % a, a)
+
diff --git a/ecc.py b/ecc.py
@@ -6,32 +6,12 @@ def inv(n, q):
     """div on PN modulo a/b mod q as a * inv(b, q) mod q
     >>> assert n * inv(n, q) % q == 1
     """
-    # n*inv % q = 1 => n*inv = q*m + 1 => n*inv + q*-m = 1
-    # => egcd(n, q) = (inv, -m, 1) => inv = egcd(n, q)[0] (mod q)
-    return egcd(n, q)[0] % q
-    #[ref] naive implementation
-    #for i in range(q):
-    #    if (n * i) % q == 1:
-    #        return i
-    #    pass
-    #assert False, "unreached"
-    #pass
-
-
-def egcd(a, b):
-    """extended GCD
-    returns: (s, t, gcd) as a*s + b*t == gcd
-    >>> s, t, gcd = egcd(a, b)
-    >>> assert a % gcd == 0 and b % gcd == 0
-    >>> assert a * s + b * t == gcd
-    """
-    s0, s1, t0, t1 = 1, 0, 0, 1
-    while b > 0:
-        q, r = divmod(a, b)
-        a, b = b, r
-        s0, s1, t0, t1 = s1, s0 - q * s1, t1, t0 - q * t1
+    for i in range(q):
+        if (n * i) % q == 1:
+            return i
         pass
-    return s0, t0, a
+    assert False, "unreached"
+    pass
 
 
 def sqrt(n, q):

diff --git a/pn.py b/pn.py
@@ -0,0 +1,104 @@
+# Appendix: improved modulo calc
+
+def inv(n, q):
+    """div on PN modulo a/b mod q as a * inv(b, q) mod q
+    >>> assert n * inv(n, q) % q == 1
+    """
+    # n*inv % q = 1 => n*inv = q*m + 1 => n*inv + q*-m = 1
+    # => egcd(n, q) = (inv, -m, 1) => inv = egcd(n, q)[0] (mod q)
+    return egcd(n, q)[0] % q
+    #[ref] naive implementation
+    #for i in range(q):
+    #    if (n * i) % q == 1:
+    #        return i
+    #    pass
+    #assert False, "unreached"
+    #pass
+
+
+def egcd(a, b):
+    """extended GCD
+    returns: (s, t, gcd) as a*s + b*t == gcd
+    >>> s, t, gcd = egcd(a, b)
+    >>> assert a % gcd == 0 and b % gcd == 0
+    >>> assert a * s + b * t == gcd
+    """
+    s0, s1, t0, t1 = 1, 0, 0, 1
+    while b > 0:
+        q, r = divmod(a, b)
+        a, b = b, r
+        s0, s1, t0, t1 = s1, s0 - q * s1, t1, t0 - q * t1
+        pass
+    return s0, t0, a
+
+def inv2(n, q):
+    """another PN invmod: from euler totient function
+    - n ** (q - 1) % q = 1 => n ** (q - 2) % q = n ** -1 % q
+    """
+    assert q > 2
+    s, p2, p = 1, n, q - 2
+    while p > 0:
+        if p & 1 == 1: s = s * p2 % q
+        p, p2 = p >> 1, p2 * p2 % q
+        pass
+    return s
+
+
+def sqrt(n, q):
+    """sqrt on PN modulo: returns two numbers or exception if not exist
+    >>> assert (sqrt(n, q)[0] ** 2) % q == n
+    >>> assert (sqrt(n, q)[1] ** 2) % q == n
+    """
+    assert n < q
+    for i in range(1, q):
+        if i * i % q == n:
+            return (i, q - i)
+        pass
+    raise Exception("not found")
+
+
+def sqrt2(n, q):
+    """sqrtmod for bigint
+    """
+    import random
+    m = inv(n, q)
+    p, s = q - 1, 0
+    while p % 2 == 0:
+        p, s = p >> 1, s + 1
+        pass
+    w = 0
+    while w == 0 or jacobi(w, q) != -1:
+        w = random.randint(1, q - 1)
+        pass
+    v = w ** p % q
+    r = n ** ((p + 1) // 2) % q
+    while True:
+        i = 0
+        z = r * r * m % q
+        while i < s and z % q != 1:
+            i = i + 1
+            z = z * z
+            pass
+        if i == 0:
+            return (r, q - r)
+        p2 = s - i - 1
+        if p2 < 0: raise Exception("not found")
+        r = r * (v ** (1 << p2) % q) % q
+        pass
+    assert False, "not reached"
+    pass
+
+
+def jacobi(a, q):
+    """jacobi symbol: judge existing sqrtmod
+    - j(a*b,q) = j(a,q)*j(b,q)
+    - j(a*q+b, q) = j(b, q)
+    - j(a, 1) = 1
+    - j(0, q) = 0
+    - j(2, q) = -1 ** (q^2 - 1)/8
+    - j(p, q) = -1 ^ {(p - 1)/2} * -1 ^ {(q - 1)/2} * j(q, p)
+    """
+    if q == 1: return 1
+    if a == 0: return 0
+    if a % 2 == 0: return (-1) ** ((q * q - 1) // 8) * jacobi(a // 2, q)
+    return (-1) ** ((a - 1) // 2) * (-1) ** ((q - 1) // 2) * jacobi(q % a, a)
diff --git a/ecc.py b/ecc.py
@@ -6,12 +6,32 @@ def inv(n, q):
     """div on PN modulo a/b mod q as a * inv(b, q) mod q
     >>> assert n * inv(n, q) % q == 1
     """
-    for i in range(q):
-        if (n * i) % q == 1:
-            return i
+    # n*inv % q = 1 => n*inv = q*m + 1 => n*inv + q*-m = 1
+    # => egcd(n, q) = (inv, -m, 1) => inv = egcd(n, q)[0] (mod q)
+    return egcd(n, q)[0] % q
+    #[ref] naive implementation
+    #for i in range(q):
+    #    if (n * i) % q == 1:
+    #        return i
+    #    pass
+    #assert False, "unreached"
+    #pass
+
+
+def egcd(a, b):
+    """extended GCD
+    returns: (s, t, gcd) as a*s + b*t == gcd
+    >>> s, t, gcd = egcd(a, b)
+    >>> assert a % gcd == 0 and b % gcd == 0
+    >>> assert a * s + b * t == gcd
+    """
+    s0, s1, t0, t1 = 1, 0, 0, 1
+    while b > 0:
+        q, r = divmod(a, b)
+        a, b = b, r
+        s0, s1, t0, t1 = s1, s0 - q * s1, t1, t0 - q * t1
         pass
-    assert False, "unreached"
-    pass
+    return s0, t0, a
 
 
 def sqrt(n, q):

diff --git a/ecc.py b/ecc.py
@@ -75,10 +75,12 @@ def neg(self, p):
 
     def add(self, p1, p2):
         """<add> of elliptic curve: negate of 3rd cross point of (p1,p2) line
-        >>>  c = ec.add(a, b)
-        >>> assert ec.is_valid(c)
-        >>> assert ec.add(c, ec.neg(b)) == a
+        >>> d = ec.add(a, b)
+        >>> assert ec.is_valid(d)
+        >>> assert ec.add(d, ec.neg(b)) == a
         >>> assert ec.add(a, ec.neg(a)) == ec.zero
+        >>> assert ec.add(a, b) == ec.add(b, a)
+        >>> assert ec.add(a, ec.add(b, c)) == ec.add(ec.add(a, b), c)
         """
         if p1 == self.zero: return p2
         if p2 == self.zero: return p1
@@ -100,7 +102,7 @@ def mul(self, p, n):
         """n times <mul> of elliptic curve
         >>> m = ec.mul(p, n)
         >>> assert ec.is_valid(m)
-        >>> assert ec.mul(p, ec.q) == ec.zero
+        >>> assert ec.mul(p, 0) == ec.zero
         """
         r = self.zero
         m2 = p

diff --git a/ecc.py b/ecc.py
@@ -118,8 +118,13 @@ def mul(self, p, n):
         return r
 
     def order(self, g):
-        assert self.is_valid(g)
-        for i in range(2, self.q + 1):
+        """order of point g
+        >>> o = ec.order(g)
+        >>> assert ec.is_valid(a) and ec.mul(a, o) == ec.zero
+        >>> assert o <= ec.q
+        """
+        assert self.is_valid(g) and g != self.zero
+        for i in range(1, self.q + 1):
             if self.mul(g, i) == self.zero:
                 return i
             pass
@@ -137,6 +142,7 @@ def __init__(self, ec, g):
         assert ec.is_valid(g)
         self.ec = ec
         self.g = g
+        self.n = ec.order(g)
         pass
 
     def gen(self, priv):
@@ -243,14 +249,14 @@ def validate(self, hashval, sig, pub):
     # shared elliptic curve system of examples
     ec = EC(1, 18, 19)
     g, _ = ec.at(7)
-
+    assert ec.order(g) <= ec.q
 
     # ElGamal enc/dec usage
     eg = ElGamal(ec, g)
     # mapping value to ec point
     # "masking": value k to point ec.mul(g, k)
     # ("imbedding" on proper n:use a point of x as 0 <= n*v <= x < n*(v+1) < q)
-    mapping = [ec.mul(g, i) for i in range(ec.q)]
+    mapping = [ec.mul(g, i) for i in range(eg.n)]
     plain = mapping[7] 
 
     priv = 5

diff --git a/ecc.py b/ecc.py
@@ -116,6 +116,14 @@ def mul(self, p, n):
         #    r = self.add(r, p)
         #    pass
         return r
+
+    def order(self, g):
+        assert self.is_valid(g)
+        for i in range(2, self.q + 1):
+            if self.mul(g, i) == self.zero:
+                return i
+            pass
+        raise Exception("Invalid order")
     pass
 
 
@@ -167,13 +175,14 @@ class DiffieHellman(object):
     - g: a point on ec
     """
     def __init__(self, ec, g):
-        assert ec.is_valid(g)
         self.ec = ec
         self.g = g
+        self.n = ec.order(g)
         pass
 
     def gen(self, priv):
         """generate pub key"""
+        assert 0 < priv and priv < self.n
         return self.ec.mul(self.g, priv)
 
     def secret(self, priv, pub):
@@ -183,23 +192,25 @@ def secret(self, priv, pub):
         - returns: shared secret as a point on ec
         """
         assert self.ec.is_valid(pub)
+        assert self.ec.mul(pub, self.n) == self.ec.zero
         return self.ec.mul(pub, priv)
     pass
 
 
 class DSA(object):
-    """(Simplified) ECDSA
+    """ECDSA
     - ec: elliptic curve
     - g: a point on ec
     """
     def __init__(self, ec, g):
-        assert ec.is_valid(g)
         self.ec = ec
         self.g = g
+        self.n = ec.order(g)
         pass
 
     def gen(self, priv):
         """generate pub key"""
+        assert 0 < priv and priv < self.n
         return self.ec.mul(self.g, priv)
 
     def sign(self, hashval, priv, r):
@@ -209,9 +220,9 @@ def sign(self, hashval, priv, r):
         - r: random int 
         - returns: signature as (int, int)
         """
-        assert 0 < r and r < self.ec.q
+        assert 0 < r and r < self.n
         m = self.ec.mul(self.g, r)
-        return (m.x, inv(r, self.ec.q) * (hashval + m.x * priv) % self.ec.q)
+        return (m.x, inv(r, self.n) * (hashval + m.x * priv) % self.n)
 
     def validate(self, hashval, sig, pub):
         """validate signature
@@ -220,10 +231,11 @@ def validate(self, hashval, sig, pub):
         - pub: pub key as a point on ec
         """
         assert self.ec.is_valid(pub)
-        w = inv(sig[1], self.ec.q)
-        u1, u2 = hashval * w % self.ec.q, sig[0] * w % self.ec.q
+        assert self.ec.mul(pub, self.n) == self.ec.zero
+        w = inv(sig[1], self.n)
+        u1, u2 = hashval * w % self.n, sig[0] * w % self.n
         p = self.ec.add(self.ec.mul(self.g, u1), self.ec.mul(pub, u2))
-        return p.x == sig[0]
+        return p.x % self.n == sig[0]
     pass
 
 
@@ -253,7 +265,7 @@ def validate(self, hashval, sig, pub):
     # ECDH usage
     dh = DiffieHellman(ec, g)
 
-    apriv = 15
+    apriv = 11
     apub = dh.gen(apriv)
 
     bpriv = 3
@@ -278,7 +290,7 @@ def validate(self, hashval, sig, pub):
     priv = 11
     pub = eg.gen(priv)
     hashval = 128
-    r = 17
+    r = 7
 
     sig = dsa.sign(hashval, priv, r)
     assert dsa.validate(hashval, sig, pub)

diff --git a/ecc.py b/ecc.py
@@ -82,7 +82,7 @@ def add(self, p1, p2):
         """
         if p1 == self.zero: return p2
         if p2 == self.zero: return p1
-        if p1.x == p2.x and p1.y != p2.y:
+        if p1.x == p2.x and (p1.y != p2.y or p1.y == 0):
             # p1 + -p1 == 0
             return self.zero
         if p1.x == p2.x:
@@ -222,7 +222,7 @@ def validate(self, hashval, sig, pub):
         assert self.ec.is_valid(pub)
         w = inv(sig[1], self.ec.q)
         u1, u2 = hashval * w % self.ec.q, sig[0] * w % self.ec.q
-        p = self.ec.add(self.ec.mul(g, u1), self.ec.mul(pub, u2))
+        p = self.ec.add(self.ec.mul(self.g, u1), self.ec.mul(pub, u2))
         return p.x == sig[0]
     pass
 

diff --git a/ecc.py b/ecc.py
@@ -76,8 +76,9 @@ def neg(self, p):
     def add(self, p1, p2):
         """<add> of elliptic curve: negate of 3rd cross point of (p1,p2) line
         >>>  c = ec.add(a, b)
-        >>> assert ec.is_valid(a)
+        >>> assert ec.is_valid(c)
         >>> assert ec.add(c, ec.neg(b)) == a
+        >>> assert ec.add(a, ec.neg(a)) == ec.zero
         """
         if p1 == self.zero: return p2
         if p2 == self.zero: return p1
@@ -97,8 +98,9 @@ def add(self, p1, p2):
 
     def mul(self, p, n):
         """n times <mul> of elliptic curve
-        >>> m = ec.mul(n, p)
+        >>> m = ec.mul(p, n)
         >>> assert ec.is_valid(m)
+        >>> assert ec.mul(p, ec.q) == ec.zero
         """
         r = self.zero
         m2 = p
@@ -175,14 +177,20 @@ def gen(self, priv):
         return self.ec.mul(self.g, priv)
 
     def secret(self, priv, pub):
-        """calc shared secret key for the pair"""
+        """calc shared secret key for the pair
+        - priv: my private key as int
+        - pub: partner pub key as a point on ec
+        - returns: shared secret as a point on ec
+        """
         assert self.ec.is_valid(pub)
         return self.ec.mul(pub, priv)
     pass
 
 
 class DSA(object):
     """(Simplified) ECDSA
+    - ec: elliptic curve
+    - g: a point on ec
     """
     def __init__(self, ec, g):
         assert ec.is_valid(g)

diff --git a/ecc.py b/ecc.py
@@ -181,6 +181,44 @@ def secret(self, priv, pub):
     pass
 
 
+class DSA(object):
+    """(Simplified) ECDSA
+    """
+    def __init__(self, ec, g):
+        assert ec.is_valid(g)
+        self.ec = ec
+        self.g = g
+        pass
+
+    def gen(self, priv):
+        """generate pub key"""
+        return self.ec.mul(self.g, priv)
+
+    def sign(self, hashval, priv, r):
+        """generate signature
+        - hashval: hash value of message as int
+        - priv: priv key as int
+        - r: random int 
+        - returns: signature as (int, int)
+        """
+        assert 0 < r and r < self.ec.q
+        m = self.ec.mul(self.g, r)
+        return (m.x, inv(r, self.ec.q) * (hashval + m.x * priv) % self.ec.q)
+
+    def validate(self, hashval, sig, pub):
+        """validate signature
+        - hashval: hash value of message as int
+        - sig: signature as (int, int)
+        - pub: pub key as a point on ec
+        """
+        assert self.ec.is_valid(pub)
+        w = inv(sig[1], self.ec.q)
+        u1, u2 = hashval * w % self.ec.q, sig[0] * w % self.ec.q
+        p = self.ec.add(self.ec.mul(g, u1), self.ec.mul(pub, u2))
+        return p.x == sig[0]
+    pass
+
+
 if __name__ == "__main__":
     # shared elliptic curve system of examples
     ec = EC(1, 18, 19)
@@ -224,4 +262,16 @@ def secret(self, priv, pub):
     assert dh.secret(apriv, cpub) != dh.secret(apriv, bpub)
     assert dh.secret(bpriv, apub) != dh.secret(bpriv, cpub)
     assert dh.secret(cpriv, bpub) != dh.secret(cpriv, apub)
+
+
+    # ECDSA usage
+    dsa = DSA(ec, g)
+
+    priv = 11
+    pub = eg.gen(priv)
+    hashval = 128
+    r = 17
+
+    sig = dsa.sign(hashval, priv, r)
+    assert dsa.validate(hashval, sig, pub)
     pass
diff --git a/ecc.py b/ecc.py
@@ -192,8 +192,8 @@ def secret(self, priv, pub):
     # mapping value to ec point
     # "masking": value k to point ec.mul(g, k)
     # ("imbedding" on proper n:use a point of x as 0 <= n*v <= x < n*(v+1) < q)
-    plains = [ec.mul(g, i) for i in range(ec.q)]
-    plain = plains[7] 
+    mapping = [ec.mul(g, i) for i in range(ec.q)]
+    plain = mapping[7] 
 
     priv = 5
     pub = eg.gen(priv)

diff --git a/ecc.py b/ecc.py
@@ -1,4 +1,4 @@
-# Basics of Elliptic Curve Cryptography
+# Basics of Elliptic Curve Cryptography implementation on Python
 import collections
 
 
@@ -101,9 +101,18 @@ def mul(self, p, n):
         >>> assert ec.is_valid(m)
         """
         r = self.zero
-        for i in range(n):
-            r = self.add(r, p)
+        m2 = p
+        # O(log2(n)) add
+        while 0 < n:
+            if n & 1 == 1:
+                r = self.add(r, m2)
+                pass
+            n, m2 = n >> 1, self.add(m2, m2)
             pass
+        # [ref] O(n) add
+        #for i in range(n):
+        #    r = self.add(r, p)
+        #    pass
         return r
     pass
 
@@ -135,21 +144,22 @@ def enc(self, plain, pub, r):
         - returns: (cipher1, ciper2) as points on ec
         """
         assert self.ec.is_valid(plain)
-        return (self.ec.mul(g, r), 
-                self.ec.add(plain, self.ec.mul(pub, r)))
+        assert self.ec.is_valid(pub)
+        return (self.ec.mul(g, r), self.ec.add(plain, self.ec.mul(pub, r)))
 
     def dec(self, cipher, priv):
         """decrypt
         - chiper: (chiper1, chiper2) as points on ec
         - priv: private key as int < ec.q
         - returns: plain as a point on ec
         """
-        return self.ec.add(cipher[1], 
-                           self.ec.neg(self.ec.mul(cipher[0], priv)))
+        c1, c2 = cipher
+        assert self.ec.is_valid(c1) and ec.is_valid(c2)
+        return self.ec.add(c2, self.ec.neg(self.ec.mul(c1, priv)))
     pass
 
 
-class ECDH(object):
+class DiffieHellman(object):
     """Elliptic Curve Diffie Hellman (Key Agreement)
     - ec: elliptic curve
     - g: a point on ec
@@ -172,42 +182,46 @@ def secret(self, priv, pub):
 
 
 if __name__ == "__main__":
-    # enc/dec usage
+    # shared elliptic curve system of examples
     ec = EC(1, 18, 19)
     g, _ = ec.at(7)
+
+
+    # ElGamal enc/dec usage
     eg = ElGamal(ec, g)
-    priv = 5
     # mapping value to ec point
     # "masking": value k to point ec.mul(g, k)
     # ("imbedding" on proper n:use a point of x as 0 <= n*v <= x < n*(v+1) < q)
     plains = [ec.mul(g, i) for i in range(ec.q)]
     plain = plains[7] 
 
+    priv = 5
     pub = eg.gen(priv)
+
     cipher = eg.enc(plain, pub, 15)
     decoded = eg.dec(cipher, priv)
     assert decoded == plain
     assert cipher != pub
 
 
-    # ecdh usage
-    ecdh = ECDH(ec, g)
+    # ECDH usage
+    dh = DiffieHellman(ec, g)
 
     apriv = 15
-    apub = ecdh.gen(apriv)
+    apub = dh.gen(apriv)
 
     bpriv = 3
-    bpub = ecdh.gen(bpriv)
+    bpub = dh.gen(bpriv)
 
     cpriv = 7
-    cpub = ecdh.gen(cpriv)
+    cpub = dh.gen(cpriv)
     # same secret on each pair
-    assert ecdh.secret(apriv, bpub) == ecdh.secret(bpriv, apub)
-    assert ecdh.secret(apriv, cpub) == ecdh.secret(cpriv, apub)
-    assert ecdh.secret(bpriv, cpub) == ecdh.secret(cpriv, bpub)
+    assert dh.secret(apriv, bpub) == dh.secret(bpriv, apub)
+    assert dh.secret(apriv, cpub) == dh.secret(cpriv, apub)
+    assert dh.secret(bpriv, cpub) == dh.secret(cpriv, bpub)
 
     # not same secret on other pair
-    assert ecdh.secret(apriv, cpub) != ecdh.secret(apriv, bpub)
-    assert ecdh.secret(bpriv, apub) != ecdh.secret(bpriv, cpub)
-    assert ecdh.secret(cpriv, bpub) != ecdh.secret(cpriv, apub)
+    assert dh.secret(apriv, cpub) != dh.secret(apriv, bpub)
+    assert dh.secret(bpriv, apub) != dh.secret(bpriv, cpub)
+    assert dh.secret(cpriv, bpub) != dh.secret(cpriv, apub)
     pass
diff --git a/ecc.py b/ecc.py
@@ -111,30 +111,32 @@ def mul(self, p, n):
 class ElGamal(object):
     """ElGamal Encryption
     pub key encryption as replacing (mulmod, powmod) to (ec.add, ec.mul)
+    - ec: elliptic curve
+    - g: (random) a point on ec
     """
-    def __init__(self, ec):
+    def __init__(self, ec, g):
+        assert ec.is_valid(g)
         self.ec = ec
+        self.g = g
         pass
 
-    def gen(self, priv, pub1):
+    def gen(self, priv):
         """generate pub key
         - priv: priv key as (random) int < ec.q
-        - pub1: (random) a point on ec
-        - returns: pub key as (pub1, pub2) as points on ec
+        - returns: pub key as points on ec
         """
-        assert self.ec.is_valid(pub1)
-        return (pub1, self.ec.mul(pub1, priv))
+        return self.ec.mul(g, priv)
 
     def enc(self, plain, pub, r):
         """encrypt
         - plain: data as a point on ec
-        - pub: pubkey as (pub1, pub2) as points on ec
+        - pub: pub key as points on ec
         - r: randam int < ec.q
         - returns: (cipher1, ciper2) as points on ec
         """
         assert self.ec.is_valid(plain)
-        return (self.ec.mul(pub[0], r), 
-                self.ec.add(plain, self.ec.mul(pub[1], r)))
+        return (self.ec.mul(g, r), 
+                self.ec.add(plain, self.ec.mul(pub, r)))
 
     def dec(self, cipher, priv):
         """decrypt
@@ -149,18 +151,21 @@ def dec(self, cipher, priv):
 
 class ECDH(object):
     """Elliptic Curve Diffie Hellman (Key Agreement)
+    - ec: elliptic curve
+    - g: a point on ec
     """
     def __init__(self, ec, g):
         assert ec.is_valid(g)
         self.ec = ec
+        self.g = g
         pass
 
     def gen(self, priv):
         """generate pub key"""
         return self.ec.mul(self.g, priv)
 
     def secret(self, priv, pub):
-        """calc secret key for the pair"""
+        """calc shared secret key for the pair"""
         assert self.ec.is_valid(pub)
         return self.ec.mul(pub, priv)
     pass
@@ -169,19 +174,23 @@ def secret(self, priv, pub):
 if __name__ == "__main__":
     # enc/dec usage
     ec = EC(1, 18, 19)
-    eg = ElGamal(ec)
+    g, _ = ec.at(7)
+    eg = ElGamal(ec, g)
     priv = 5
-    pub1, _ = ec.at(7)
-    plain, _ = ec.at(1)
+    # mapping value to ec point
+    # "masking": value k to point ec.mul(g, k)
+    # ("imbedding" on proper n:use a point of x as 0 <= n*v <= x < n*(v+1) < q)
+    plains = [ec.mul(g, i) for i in range(ec.q)]
+    plain = plains[7] 
 
-    pub = eg.gen(priv, pub1)
+    pub = eg.gen(priv)
     cipher = eg.enc(plain, pub, 15)
     decoded = eg.dec(cipher, priv)
     assert decoded == plain
     assert cipher != pub
 
+
     # ecdh usage
-    g, _ = ec.at(7) # shared
     ecdh = ECDH(ec, g)
 
     apriv = 15

diff --git a/ecc.py b/ecc.py
@@ -109,7 +109,7 @@ def mul(self, p, n):
 
 
 class ElGamal(object):
-    """El Gamal Encryption
+    """ElGamal Encryption
     pub key encryption as replacing (mulmod, powmod) to (ec.add, ec.mul)
     """
     def __init__(self, ec):
@@ -146,6 +146,7 @@ def dec(self, cipher, priv):
                            self.ec.neg(self.ec.mul(cipher[0], priv)))
     pass
 
+
 class ECDH(object):
     """Elliptic Curve Diffie Hellman (Key Agreement)
     """

diff --git a/ecc.py b/ecc.py
@@ -15,8 +15,9 @@ def inv(n, q):
 
 
 def sqrt(n, q):
-    """sqrt on PN modulo: it may not exist
-    >>> assert (sqrt(n, q) ** 2) % q == n
+    """sqrt on PN modulo: returns two numbers or exception if not exist
+    >>> assert (sqrt(n, q)[0] ** 2) % q == n
+    >>> assert (sqrt(n, q)[1] ** 2) % q == n
     """
     assert n < q
     for i in range(1, q):

diff --git a/ecc.py b/ecc.py
@@ -1,6 +1,5 @@
 # Basics of Elliptic Curve Cryptography
 import collections
-import fractions
 
 
 def inv(n, q):

diff --git a/ecc.py b/ecc.py
@@ -0,0 +1,203 @@
+# Basics of Elliptic Curve Cryptography
+import collections
+import fractions
+
+
+def inv(n, q):
+    """div on PN modulo a/b mod q as a * inv(b, q) mod q
+    >>> assert n * inv(n, q) % q == 1
+    """
+    for i in range(q):
+        if (n * i) % q == 1:
+            return i
+        pass
+    assert False, "unreached"
+    pass
+
+
+def sqrt(n, q):
+    """sqrt on PN modulo: it may not exist
+    >>> assert (sqrt(n, q) ** 2) % q == n
+    """
+    assert n < q
+    for i in range(1, q):
+        if i * i % q == n:
+            return (i, q - i)
+        pass
+    raise Exception("not found")
+
+
+Coord = collections.namedtuple("Coord", ["x", "y"])
+
+
+class EC(object):
+    """System of Elliptic Curve"""
+    def __init__(self, a, b, q):
+        """elliptic curve as: (y**2 = x**3 + a * x + b) mod q
+        - a, b: params of curve formula
+        - q: prime number
+        """
+        assert 0 < a and a < q and 0 < b and b < q and q > 2
+        assert (4 * (a ** 3) + 27 * (b ** 2))  % q != 0
+        self.a = a
+        self.b = b
+        self.q = q
+        # just as unique ZERO value representation for "add": (not on curve)
+        self.zero = Coord(0, 0)
+        pass
+
+    def is_valid(self, p):
+        if p == self.zero: return True
+        l = (p.y ** 2) % self.q
+        r = ((p.x ** 3) + self.a * p.x + self.b) % self.q
+        return l == r
+
+    def at(self, x):
+        """find points on curve at x
+        - x: int < q
+        - returns: ((x, y), (x,-y)) or not found exception
+        >>> a, ma = ec.at(x)
+        >>> assert a.x == ma.x and a.x == x
+        >>> assert a.x == ma.x and a.x == x
+        >>> assert ec.neg(a) == ma
+        >>> assert ec.is_valid(a) and ec.is_valid(ma)
+        """
+        assert x < self.q
+        ysq = (x ** 3 + self.a * x + self.b) % self.q
+        y, my = sqrt(ysq, self.q)
+        return Coord(x, y), Coord(x, my)
+
+    def neg(self, p):
+        """negate p
+        >>> assert ec.is_valid(ec.neg(p))
+        """
+        return Coord(p.x, -p.y % self.q)
+
+    def add(self, p1, p2):
+        """<add> of elliptic curve: negate of 3rd cross point of (p1,p2) line
+        >>>  c = ec.add(a, b)
+        >>> assert ec.is_valid(a)
+        >>> assert ec.add(c, ec.neg(b)) == a
+        """
+        if p1 == self.zero: return p2
+        if p2 == self.zero: return p1
+        if p1.x == p2.x and p1.y != p2.y:
+            # p1 + -p1 == 0
+            return self.zero
+        if p1.x == p2.x:
+            # p1 + p1: use tangent line of p1 as (p1,p1) line
+            l = (3 * p1.x * p1.x + self.a) * inv(2 * p1.y, self.q) % self.q
+            pass
+        else:
+            l = (p2.y - p1.y) * inv(p2.x - p1.x, self.q) % self.q
+            pass
+        x = (l * l - p1.x - p2.x) % self.q
+        y = (l * (p1.x - x) - p1.y) % self.q
+        return Coord(x, y)
+
+    def mul(self, p, n):
+        """n times <mul> of elliptic curve
+        >>> m = ec.mul(n, p)
+        >>> assert ec.is_valid(m)
+        """
+        r = self.zero
+        for i in range(n):
+            r = self.add(r, p)
+            pass
+        return r
+    pass
+
+
+class ElGamal(object):
+    """El Gamal Encryption
+    pub key encryption as replacing (mulmod, powmod) to (ec.add, ec.mul)
+    """
+    def __init__(self, ec):
+        self.ec = ec
+        pass
+
+    def gen(self, priv, pub1):
+        """generate pub key
+        - priv: priv key as (random) int < ec.q
+        - pub1: (random) a point on ec
+        - returns: pub key as (pub1, pub2) as points on ec
+        """
+        assert self.ec.is_valid(pub1)
+        return (pub1, self.ec.mul(pub1, priv))
+
+    def enc(self, plain, pub, r):
+        """encrypt
+        - plain: data as a point on ec
+        - pub: pubkey as (pub1, pub2) as points on ec
+        - r: randam int < ec.q
+        - returns: (cipher1, ciper2) as points on ec
+        """
+        assert self.ec.is_valid(plain)
+        return (self.ec.mul(pub[0], r), 
+                self.ec.add(plain, self.ec.mul(pub[1], r)))
+
+    def dec(self, cipher, priv):
+        """decrypt
+        - chiper: (chiper1, chiper2) as points on ec
+        - priv: private key as int < ec.q
+        - returns: plain as a point on ec
+        """
+        return self.ec.add(cipher[1], 
+                           self.ec.neg(self.ec.mul(cipher[0], priv)))
+    pass
+
+class ECDH(object):
+    """Elliptic Curve Diffie Hellman (Key Agreement)
+    """
+    def __init__(self, ec, g):
+        assert ec.is_valid(g)
+        self.ec = ec
+        pass
+
+    def gen(self, priv):
+        """generate pub key"""
+        return self.ec.mul(self.g, priv)
+
+    def secret(self, priv, pub):
+        """calc secret key for the pair"""
+        assert self.ec.is_valid(pub)
+        return self.ec.mul(pub, priv)
+    pass
+
+
+if __name__ == "__main__":
+    # enc/dec usage
+    ec = EC(1, 18, 19)
+    eg = ElGamal(ec)
+    priv = 5
+    pub1, _ = ec.at(7)
+    plain, _ = ec.at(1)
+
+    pub = eg.gen(priv, pub1)
+    cipher = eg.enc(plain, pub, 15)
+    decoded = eg.dec(cipher, priv)
+    assert decoded == plain
+    assert cipher != pub
+
+    # ecdh usage
+    g, _ = ec.at(7) # shared
+    ecdh = ECDH(ec, g)
+
+    apriv = 15
+    apub = ecdh.gen(apriv)
+
+    bpriv = 3
+    bpub = ecdh.gen(bpriv)
+
+    cpriv = 7
+    cpub = ecdh.gen(cpriv)
+    # same secret on each pair
+    assert ecdh.secret(apriv, bpub) == ecdh.secret(bpriv, apub)
+    assert ecdh.secret(apriv, cpub) == ecdh.secret(cpriv, apub)
+    assert ecdh.secret(bpriv, cpub) == ecdh.secret(cpriv, bpub)
+
+    # not same secret on other pair
+    assert ecdh.secret(apriv, cpub) != ecdh.secret(apriv, bpub)
+    assert ecdh.secret(bpriv, apub) != ecdh.secret(bpriv, cpub)
+    assert ecdh.secret(cpriv, bpub) != ecdh.secret(cpriv, apub)
+    pass
No results found