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)