curve-py/curve.py

import random, sympy
from point import Point
from crypt import CipherAES
from tools import searchPrime

class Curve:
    
    def __init__(self, p, a, b, gx = None, gy = None, n = None, h = 1):
        # размер конечного поля
        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 clear(self):
        self.g = self.n = None

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

    # Поиск порядка 
    def setupN(self):
        dx, dy = self.g.x, (-1 * self.g.y) % self.p
        tmpG = self.g.copy()
        self.n = 1
        while True:
            self.n += 1
            tmpG = tmpG + self.g
            if tmpG.x == dx and tmpG.y == dy:
                self.n += 1
                return

    # Выбор и установка случайной точки g
    def setupGAuto(self):
        x = random.randrange(1, self.p - 1)
        p1, p2 = self.searchClosePoints(x)
        if p1.isInCurve():
            self.g = p1
        elif p2.isInCurve():
            self.g = p2
    
    # Поиск близлежащих точек по x
    def searchClosePoints(self, x):
        if x >= self.p:
            x = self.p - 1
        if x < 0:
            x = 0
        kx = x
        while True:
            if x >= self.p and kx < 0:
                return self.point()
            # Поиск вправо
            if x <= self.p:
                p1, p2 = self.pointsCurve(x)
                if p1.isInCurve():
                    return p1, p2
                x += 1
            # Поиск влево
            if kx <= 0:
                p1, p2 = self.pointsCurve(kx)
                if p1.isInCurve():
                    return p1, p2
                kx -= 1
        return self.point()


    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('Деление на 0 невозможно!!!')
        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
        return x % point

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

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

    # Создание публичного ключа из приватного
    def keyPub(self, keyPriv):
        # Результат - умножение точки подгруппы на приватный ключ
        return self.g * keyPriv

    # Вычисление общего секретного ключа, по которому производится шифрование и расшифровка сообщений
    def pointSecret(self, myKeyPrivate, friendKeyPublic):
        return friendKeyPublic * myKeyPrivate

    # Шифровка сообщения секретным ключем
    def encodeMessage(self, secretPoint, text):
        cipher = CipherAES(self, secretPoint)
        return cipher.encrypt(text)

    # Расшифровка сообщения секретным ключем
    def decodeMessage(self, secretPoint, encodedText):
        cipher = CipherAES(self, secretPoint)
        return cipher.decrypt(encodedText)
        

#################################

# Тестирование
if __name__ == '__main__':

    # Создание объекта эллиптической кривой (кривая из исходников openssl)
    '''
    cur = Curve(
        # Размер конечного поля
        p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f,
        # Коэффиценты
        a = 0,
        b = 7,
        # Координаты точки, определяющей подгруппу
        gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
        gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8,
        # Размер подгруппы
        n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141,
        # Кофактор подгруппы
        h = 1
    )
    '''
    cur = Curve(
        p = searchPrime(2 ** 18),
        a = 1550,
        b = 7840
    )

    print('setup g')
    cur.setupGAuto()
    print('g', cur.g.coords(), cur.g.isInCurve())
    print('setup n')
    cur.setupN()
    print(cur.p, cur.n)

    print(cur.n, cur.g.coords(), cur.g.isInCurve())

    k1, p1 = cur.keypair(10)
    print(k1, p1.coords())

    k2, p2 = cur.keypair(110)
    print(k2, p2.coords())

    #exit(0)

    # В зашифрованном обмене данными принимают участие 2 пользователя.
    # Далее - п1 (пользователь 1) и п2 (пользователь 2)

    # Каждый из пользовательей должен создать свою пару ключей (приватный и публичный) исходя из параметров одной эллиптической кривой

    # Создание пары ключей п1
    p1KeyPriv, p1KeyPub = cur.randomKeypair()
    # Создание пары ключей п2
    p2KeyPriv, p2KeyPub = cur.randomKeypair()

    # Предположим, что п1 и п2 обменялись публичными ключами
    # Далее каждый из них может рассчитать общий секретный ключ, используя свой приватный ключ и полученный публичный ключ контрагента
    # Секретный ключ идентичен для п1 и п2 и используется в качестве ключа в алгоритме симметричного шифрования, который используется
    # для шифровки и расшифровки сообщений
    
    # Расчет секретного ключа п1
    p1KeySecret = cur.pointSecret(p1KeyPriv, p2KeyPub)
    print(p1KeySecret.coords())

    # Расчет секретного ключа п2
    p2KeySecret = cur.pointSecret(p2KeyPriv, p1KeyPub)
    print(p2KeySecret.coords())

    # Покажем, что полученные секретные ключи идентичны у п1 и п2
    print(p1KeySecret.isEqual(p2KeySecret))

    #exit(0)

    # Далее п1 отправляет зашифрованное сообщение п2
    p1MessageEncrypted = cur.encodeMessage(p1KeySecret, 'Привет, как дела?')
    #Покажем зашифрованное сообщение
    print("п1: ", p1MessageEncrypted)

    # п2 расшифровывает полученное сообщение
    p1MessageDecrypted = cur.decodeMessage(p2KeySecret, p1MessageEncrypted)
    # Покажем расшифрованное сообщение
    print("п1: ", p1MessageDecrypted)

    # п2 отправляет зашифрованным сообщением п1
    p2MessageEncrypted = cur.encodeMessage(p2KeySecret, 'Спасибо, у меня всё хорошо :)')
    #Покажем зашифрованное сообщение
    print("п2: ", p2MessageEncrypted)

    # п1 расшифровывает полученное сообщение
    p2MessageDecrypted = cur.decodeMessage(p1KeySecret, p2MessageEncrypted)
    # Покажем расшифрованное сообщение
    print("п2: ", p2MessageDecrypted)