curve-py/curve.py

import random, sympy
from point import Point

'''
'secp256k1',
p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f,
a=0,
b=7,
g=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8),
# Subgroup order.
n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141,
# Subgroup cofactor.
h=1,
'''

# y2 = x3 + ax + b
class Curve:
    
    def __init__(self, p, a, b, gx, gy, n, h):
        # размер конечного поля
        self.p = p
        # коэффиценты уравнения a и b
        self.a = a
        self.b = b
        # базовая точка
        self.g = Point(
            curve = self,
            x = gx,
            y = gy
        )
        # порядок подруппы
        self.n = n
        # кофактор подгруппы
        self.h = h

    def isSingular(self):
        res = 4 * self.a ** 3 + 27 * self.b ** 2 == 0
        return res

    def setupN(self):
        for self.n in range(self.p - 1, 1, -1):
            if sympy.isprime(self.n):
                return

    def setupG(self, processCallback = None):
        percent = 0
        for x in range(self.n, 0, -1):
            if processCallback is not None:
                dPercent = round(100 - x * 100 / self.n, 5)
                if dPercent != percent:
                    percent = dPercent
                    processCallback(percent)
            p1, p2 = self.pointsCurve(x)
            if p1.isInCurve():
                self.g = p1
                #print(p1.coords(), p1.isInCurve())
                #print(p2.coords(), p2.isInCurve())

                return

    def point(self, x = None, y = None):
        return Point(
            curve = self,
            x = x,
            y = y
        )

    # Определение координат пары зеркальных точек через координату x
    def pointsCurve(self, dx):
        # Инициализируем результирующие точки пустыми
        p1, p2 = self.point(), self.point()
        dy = None
        # Операции, обратной делению по модулю, не существует, поэтому
        # для определения координаты по y, необходимо, путем перебора с подстановкой y,
        # проверить равенство левой части уравнения, разделенного по модулю на p с 
        # правой частью, так же разделенной по модулю на p
        for i in range(0, self.p):
            if i ** 2 % self.p == (dx **3 + self.a * dx + self.b) % self.p:
                dy = i
                break
        # Если dy не найден, точки не существуют, возвращаем нулевые точки
        if dy is None:
            return p1, p2
        # Точка найдена
        p1.x, p1.y = dx, dy
        # Расчет зеркальной точки
        p2.x = p1.x
        p2.y = -1 * p1.y % self.p
        return p1, p2

    # Обратное деление по модулю p кривой
    def inverseMod(self, k, point):
        if k == 0:
            raise ZeroDivisionError('division by zero')
        if k < 0:
            # k ** -1 = p - (-k) ** -1  (mod p)
            return point - self.inverseMod(-k, point)
        # Расширенный алгоритм Евклида
        s, old_s = 0, 1
        t, old_t = 1, 0
        r, old_r = point, k
        while r != 0:
            quotient = old_r // r
            old_r, r = r, old_r - quotient * r
            old_s, s = s, old_s - quotient * s
            old_t, t = t, old_t - quotient * t
        gcd, x, y = old_r, old_s, old_t
        #assert gcd == 1
        #assert (k * x) % p == 1
        return x % point

    def randomKeypair(self):
        keyPriv = random.randrange(1, self.n)
        keyPub = self.g * keyPriv
        return keyPriv, keyPub

    def keyPub(self, keyPriv):
        return self.g * keyPriv

#################################
'''
c = Curve(
    p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f,
    a = 0,
    b = 7,
    gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
    gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8,
    n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141,
    h = 1
)

c = Curve(
    p = 6277101735386680763835789423207666416083908700390324961279,
    a = -3,
    b = 2455155546008943817740293915197451784769108058161191238065,
    gx = 602046282375688656758213480587526111916698976636884684818,
    gy = 174050332293622031404857552280219410364023488927386650641,
    n = 6277101735386680763835789423176059013767194773182842284081,
    h = 1
)
'''

c = Curve(
    p = 2 ** 20,
    a = 5,
    b = 4,
    gx = 2,
    gy = 2,
    n = 54534432,
    h = 1
)

if c.isSingular():
    print('Кривая сингулярна')
    exit(0)

def process(percent):
    print(percent)

c.setupN()
c.setupG(process)
print(c.n)

aPriv, aPub = c.randomKeypair()
bPriv, bPub = c.randomKeypair()

print(hex(aPriv))
print(aPub.show())

#aS = scalar_mult(alice_private_key, bob_public_key)
aS = bPub * aPriv
bS = aPub * bPriv

print(aS.show())
print(bS.show())