-
-
Save AlexanderKud/dcddea4330a608ee10a8978bf8d8f206 to your computer and use it in GitHub Desktop.
ECC intro
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import random | |
| import math | |
| from field import Fp | |
| class ClockPointFp: | |
| def __init__(self, x, y, p): | |
| self.x = Fp(x, p) | |
| self.y = Fp(y, p) | |
| pass | |
| def __str__(self): | |
| return "({}, {})".format(self.x, self.y) | |
| def __eq__(self, other): | |
| return self.x == other.x and self.y == other.y | |
| def __add__(self, other): | |
| (x1, y1) = (self.x, self.y) | |
| (x2, y2) = (other.x, other.y) | |
| x3 = x1*y2 + y1*x2 | |
| y3 = y1*y2 - x1*x2 | |
| return ClockPointFp(x3.val, y3.val, x3.mod) | |
| def __mul__(self, scalar): | |
| # Naive point*scalar multiplication. | |
| # Better approach would be double and add algorithm. | |
| res = ClockPointFp(0, 1, self.x.mod) | |
| for i in range(scalar): | |
| res = res + self | |
| return res | |
| def identity(p): | |
| return ClockPointFp(0, 1, p) | |
| __reps__ = __str__ | |
| class ClockPointF7(ClockPointFp): | |
| def __init__(self, x, y): | |
| super().__init__(x, y, 7) | |
| def get_random_point(p): | |
| ''' | |
| Get a random point int the group | |
| ''' | |
| while True: | |
| x = random.randint(0, p) | |
| y = random.randint(0, p) | |
| if (x**2 + y**2) % p == 1: | |
| return ClockPointFp(x, y, p) | |
| def is_generator(pt, p): | |
| ''' | |
| Check if the point is a generator of the group | |
| ''' | |
| # Per Hasse's theorem | |
| max_order = p + 1 + 2*math.ceil(math.sqrt(p)) | |
| min_order = p + 1 - 2*math.floor(math.sqrt(p)) | |
| ident = ClockPointFp.identity(p) | |
| for i in range(1, max_order + 1): | |
| print("RES: ", pt*i) | |
| if pt * i == ident: | |
| if i >= min_order: | |
| print("Found probable generator {} (order {})".format(pt, i)) | |
| return True | |
| else: | |
| return False | |
| print("Should never happen") | |
| return False | |
| def find_generator(): | |
| p = 1511 | |
| while True: | |
| pt = get_random_point(p) | |
| print("Point on curve: {}".format(pt)) | |
| if is_generator(pt, p): | |
| return pt | |
| def clock_dh(): | |
| ''' | |
| Clock diffie-hellman protocol | |
| ''' | |
| # Clock field modulus | |
| p = 1511 | |
| # Generator | |
| g = ClockPointFp(1459, 452, p) | |
| # Clock generator order | |
| n = 1512 | |
| # Random Alice's keypair | |
| a_sec = random.randint(0, n) | |
| a_pub = g * a_sec | |
| print("Alice keypair: sec = {}, pub = {}".format(a_sec, a_pub)) | |
| # Random Bob's keypair | |
| b_sec = random.randint(0, n) | |
| b_pub = g * b_sec | |
| print("Bob keypair: sec = {}, pub = {}".format(b_sec, b_pub)) | |
| # Compute shared key | |
| k1 = b_pub * a_sec | |
| k2 = a_pub * b_sec | |
| assert k1 == k2, f"Unexpected error while computing shared secret" | |
| print("Shared secret: ", k1) | |
| def main(): | |
| # (0, 1) has order 1 (identity) | |
| # (0, 6) have order 2 | |
| # (1, 0), (6, 0) have order 4 | |
| # (2, 2), (2, 5), (5, 2), (5, 5) have order 8 (generators) | |
| p = ClockPointF7(2, 5) | |
| p1 = p | |
| for i in range(8): | |
| res = p1 + p | |
| print("{} + {} = {}".format(p, p1, res)) | |
| p1 = res | |
| print("Scalar multiplication") | |
| p = ClockPointF7(2, 5) | |
| for i in range(8): | |
| print("{} * {} = {}".format(p, i, p * i)) | |
| clock_dh() | |
| if __name__ == '__main__': | |
| main() |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import random | |
| import math | |
| from field import Fp | |
| class EcPoint: | |
| def __init__(self, x, y, p, d): | |
| self.x = Fp(x, p) | |
| self.y = Fp(y, p) | |
| self.d = Fp(d, p) | |
| pass | |
| def __str__(self): | |
| return "({}, {})".format(self.x, self.y) | |
| def __eq__(self, other): | |
| return self.x == other.x and self.y == other.y | |
| def __add__(self, other): | |
| (x1, y1) = (self.x, self.y) | |
| (x2, y2) = (other.x, other.y) | |
| p = x1.mod | |
| den = self.d*x1*x2*y1*y2 | |
| x3 = (x1*y2 + y1*x2) / (Fp(1, p) + den) | |
| y3 = (y1*y2 - x1*x2) / (Fp(1, p) - den) | |
| return EcPoint(x3.val, y3.val, p, self.d.val) | |
| def __mul__(self, scalar): | |
| # Naive point*scalar multiplication. | |
| # Better approach would be double and add algorithm. | |
| res = EcPoint(0, 1, self.x.mod, self.d.val) | |
| for i in range(scalar): | |
| res = res + self | |
| return res | |
| def identity(p, d): | |
| return EcPoint(0, 1, p, d) | |
| __reps__ = __str__ | |
| def is_generator(pt, p, d): | |
| ''' | |
| Check if the point is a generator of the group | |
| ''' | |
| # Per Hasse's theorem | |
| max_order = p + 1 + 2*math.ceil(math.sqrt(p)) | |
| min_order = p + 1 - 2*math.floor(math.sqrt(p)) | |
| ident = EcPoint(0, 1, p, d) | |
| for i in range(1, max_order + 1): | |
| print("RES: ", pt*i) | |
| if pt * i == ident: | |
| if i >= min_order: | |
| print("Found probable generator {} (order {})".format(pt, i)) | |
| return True | |
| else: | |
| return False | |
| print("Should never happen") | |
| return False | |
| def get_random_point(p, d): | |
| ''' | |
| Get a random point int the group | |
| ''' | |
| while True: | |
| x = random.randint(0, p) | |
| y = random.randint(0, p) | |
| xx = x**2 | |
| yy = y**2 | |
| if (xx + yy - d*xx*yy) % p == 1: | |
| return EcPoint(x, y, p, d) | |
| def find_generator(): | |
| # Ec params | |
| p = 179 | |
| d = 30 | |
| while True: | |
| pt = get_random_point(p, d) | |
| print("Point on curve: {}".format(pt)) | |
| if is_generator(pt, p, d): | |
| return pt | |
| def ecdh(): | |
| ''' | |
| Ec diffie-hellman protocol | |
| ''' | |
| # Ec field modulus | |
| p = 179 | |
| # Ec d parameter | |
| d = 30 | |
| # Generator | |
| g = EcPoint(95, 77, p, d) | |
| # Generator order | |
| n = 196 | |
| # Random Alice's keypair | |
| a_sec = random.randint(0, n) | |
| a_pub = g * a_sec | |
| print("Alice keypair: sec = {}, pub = {}".format(a_sec, a_pub)) | |
| # Random Bob's keypair | |
| b_sec = random.randint(0, n) | |
| b_pub = g * b_sec | |
| print("Bob keypair: sec = {}, pub = {}".format(b_sec, b_pub)) | |
| # Compute shared key | |
| k1 = b_pub * a_sec | |
| k2 = a_pub * b_sec | |
| assert k1 == k2, f"Unexpected error while computing shared secret" | |
| print("Shared secret: ", k1) | |
| def main(): | |
| # (0, 1) has order 1 (identity) | |
| p = EcPoint(2, 5, 179, 30) | |
| p1 = p | |
| for i in range(8): | |
| res = p1 + p | |
| print("{} + {} = {}".format(p, p1, res)) | |
| p1 = res | |
| print("Scalar multiplication") | |
| p = EcPoint(2, 5, 179, 30) | |
| for i in range(8): | |
| print("{} * {} = {}".format(p, i, p * i)) | |
| #find_generator() | |
| ecdh() | |
| if __name__ == '__main__': | |
| main() |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import random | |
| import math | |
| class Fp: | |
| ''' | |
| Class defining the finite field Fp. | |
| The field is used to construct the Clock(Fp) group. | |
| ''' | |
| def __init__(self, x, p): | |
| self.mod = p | |
| self.val = x % self.mod | |
| def __str__(self): | |
| return str(self.val) | |
| def __eq__(self, other): | |
| if self.mod != other.mod: | |
| raise ValueError("Different modulus") | |
| return self.val == other.val | |
| def __add__(self, other): | |
| if self.mod != other.mod: | |
| raise ValueError("Different modulus") | |
| return Fp(self.val + other.val, self.mod) | |
| def __sub__(self, other): | |
| if self.mod != other.mod: | |
| raise ValueError("Different modulus") | |
| return Fp(self.val - other.val, self.mod) | |
| def __mul__(self, other): | |
| if self.mod != other.mod: | |
| raise ValueError("Different modulus") | |
| return Fp(self.val * other.val, self.mod) | |
| def __div__(self, other): | |
| other_inv = pow(other.val, -1, self.mod) | |
| return Fp(self.val * other_inv, self.mod) | |
| def __truediv__(self, other): | |
| return self.__div__(other) | |
| __reps__ = __str__ | |
| class F7(Fp): | |
| def __init__(self, x): | |
| super().__init__(x, 7) | |
| class F13(Fp): | |
| def __init__(self, x): | |
| super().__init__(x, 13) | |
| def main(): | |
| a = F7(3) | |
| b = F7(6) | |
| # Check inv | |
| print("{} * {}^-1 = {}".format(a, a, a / a)) | |
| print("{} + {} = {}".format(a, b, a + b)) | |
| print("{} - {} = {}".format(a, b, a - b)) | |
| print("{} * {} = {}".format(a, b, a * b)) | |
| print("{} / {} = {}".format(a, b, a / b)) | |
| if __name__ == '__main__': | |
| main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment