Elliptic Curve Diffie Hellman

Elliptic Curve Diffie Hellman (ECDH)¶

ECDH Is almost the exact same as regular Diffie-Hellman. But instead of G^a its G*a.
Works on the principle that it is hard to find G*a*b when only knowing G*a and G*b

Implementation¶

from ecc_lib import *


if __name__ == '__main__':

	#### Setup
	#User1 Generates their Private Public KeyPair
	privateKey1, public_point1 = generate_KeyPair(Curve25519_Generator_Point)
	print(privateKey1, public_point1)

	#User2 Generates their Private Public KeyPair
	privateKey2, public_point2 = generate_KeyPair(Curve25519_Generator_Point)
	print(privateKey2, public_point2)

	#### Exchange Data

	# User1 recives User2's Public Key

	# User2 recives User1's Public Key


	#### Key Generation

	#User1 Takes their Private Key and Multiplies it by User2's Public Key
	user1_shared_key = privateKey1 * public_point2


	#User2 Takes their Private Keu and multiplies it by User1's Public Key
	user2_shared_key = privateKey2 * public_point1


	#### Assurange that the shared key is the same

	#print(user2_shared_key, user1_shared_key)
	assert user1_shared_key == user2_shared_key

Protocol Example¶

Source

User1 and User2 use the same Curve parameters:
- Lets use y^2 = x^3 + -3 * x + b
For Example let TODO
User1 chooses a secret integer a (e.g. a = 4) and computes G*a
User2 chooses a secret integer a (e.g. a = 3) and computes G*b
Each User exchanges the output to each other
User1 Computes the shared secret using (G*b)*a
User2 Computes the shared secret using (G*a)*b

Attacks¶

Pollard Rho¶

from ecc_lib import *
from Crypto.Util.number import *

def func_f(X_i, generator_point, shared_secret):
    """
        To calculate X_(i+1) = f(X_i)

        :parameters:
            X_i : sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field
                X_i = (a_i * P) + (b_i * Q)
            P : sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field
                Base point on which ECDLP is defined
            Q : sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field
                Q = x*P, where `x` is the secret key
            E : sage.schemes.elliptic_curves.ell_finite_field.EllipticCurve_finite_field_with_category
                Elliptic Curve defined as y^2 = x^3 + a*x + b mod p
    """
    curve = generator_point.curve

    if X_i.x % 3 == 2:
        # Partition S_1
        return curve.add_point(X_i, shared_secret)
    if X_i.x % 3 == 0:
        # Partition S_2
        return curve.double_point(X_i)
    if X_i.x % 3 == 1:
        # Partition S_3
        return curve.add_point(X_i, generator_point)
    else:
        print("[-] Something's Wrong!")
        return -1

def func_g(a, generator_point, X_i):
    """
    Calculate a_(i+1) = g(a)

    :parameters:
        a : int/long
            Equivalent to a_i in X_i = a_i*P + b_i*Q
        P : sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field
            Base point on which ECDLP is defined
        X_i : sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field
            X_i = a_i*P + b_i*Q
        E : sage.schemes.elliptic_curves.ell_finite_field.EllipticCurve_finite_field_with_category
            Elliptic Curve defined as y^2 = x^3 + a*x + b mod p
    """
    n = generator_point.curve.order
    if X_i.x % 3 == 2:
        # Partition S_1
        return a
    if X_i.x % 3 == 0:
        # Partition S_2
        return 2*a % n
    if X_i.x % 3 == 1:
        # Partition S_3
        return (a + 1) % n
    else:
        print("[-] Something's Wrong!")
        return None

def func_h(b, generator_point, X_i):
    """
    Calculate a_(i+1) = g(a)

    :parameters:
        a : int/long
            Equivalent to a_i in X_i = a_i*P + b_i*Q
        P : sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field
            Base point on which ECDLP is defined
        X_i : sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field
            X_i = a_i*P + b_i*Q
        E : sage.schemes.elliptic_curves.ell_finite_field.EllipticCurve_finite_field_with_category
            Elliptic Curve defined as y^2 = x^3 + a*x + b mod p
    """
    curve = generator_point.curve

    if X_i.x % 3 == 2:
        # Partition S_1
        return (b + 1) % curve.order
    if X_i.x % 3 == 0:
        # Partition S_2
        return 2*b % curve.order
    if X_i.x % 3 == 1:
        # Partition S_3
        return b
    else:
        print("[-] Something's Wrong!")
        return None


def pollardrho(generator_point, shared_secret):
	order = generator_point.curve.order
	curve = generator_point.curve

	for j in range(10):
		a_i = random.randint(2, order-2)
		b_i = random.randint(2, order-2)
		a_2i = random.randint(2, order-2)
		b_2i = random.randint(2, order-2)

		X_i = curve.add_point(curve.mul_point(a_i, generator_point), curve.mul_point(b_i, shared_secret))
		X_2i = curve.add_point(curve.mul_point(a_2i, generator_point), curve.mul_point(b_2i, shared_secret))

		i = 1
		while i <= order:
			# Single Step Calculations
			a_i = func_g(a_i, generator_point, X_i)
			b_i = func_h(b_i, generator_point, X_i)
			X_i = func_f(X_i, generator_point, shared_secret)

			# Double Step Calculations
			a_2i = func_g(func_g(a_2i, generator_point, X_2i), generator_point, func_f(X_2i, generator_point, shared_secret))
			b_2i = func_h(func_h(b_2i, generator_point, X_2i), generator_point, func_f(X_2i, generator_point, shared_secret))
			X_2i = func_f(func_f(X_2i, generator_point, shared_secret), generator_point, shared_secret)

			if X_i == X_2i:
				if b_i == b_2i:
					break
				assert GCD(b_2i - b_i, order) == 1
				return ((a_i - a_2i) * inverse(b_2i - b_i, order)) % order
			else:
				i += 1
			continue



if __name__ == '__main__':
	"""
	Anomalous = ShortWeierstrassCurve(
		name="Anomalous",
		a=1456400922,
		b=2005615003,
		prime_mod=(pow(2,31) - 1),
		order=(pow(2,31) - 1),
		#2^5 * 3^7 * 17 * 19
	)
	x = secure_rand_between(0, Anomalous.order)
	ys = Anomalous.find_points_by_x(x)

	Anomalous_Generator_Point = Point(x, ys[0], Anomalous)

	print(Anomalous_Generator_Point)
	"""
	TinyCurve32 = ShortWeierstrassCurve(
		name="TinyCurve32",
		a=1745322301,
		b=130575212,
		prime_mod=4000001039,
		order=3999907399,
	)
	Tiny32_Generator_Point = Point(2951351449, 2085375757, TinyCurve32)


	TinyCurve36 = ShortWeierstrassCurve(
		name="TinyCurve36",
		a=10730991330,
		b=10461429567,
		prime_mod=50000001637,
		order=49999749391,
	)
	Tiny36_Generator_Point = Point(39948220728, 46724792678, TinyCurve36)

	TinyCurve40 = ShortWeierstrassCurve(
		name="TinyCurve40",
		a=120982395053,
		b=42757531213,
		prime_mod=1000000003571,
		order=999998469709,
	)
	Tiny40_Generator_Point = Point(923179549631, 952583441553, TinyCurve40)

	TinyCurve44 = ShortWeierstrassCurve(
		name="TinyCurve44",
		a=2172373435844,
		b=864878753836,
		prime_mod=9809862296159,
		order=9809858895373,
	)
	Tiny44_Generator_Point = Point(7573089241231, 4438676127758, TinyCurve44)


	TinyCurve48 = ShortWeierstrassCurve(
		name="TinyCurve48",
		a=18424416311620,
		b=2813146810101,
		prime_mod=210548486455921,
		order=210548502757267,
	)
	Tiny48_Generator_Point = Point(91541889026188, 123287677451334, TinyCurve48)

	TinyCurve52 = ShortWeierstrassCurve(
		name="TinyCurve52",
		a=1130104090562190,
		b=961750782982658,
		prime_mod=3093215881333057,
		order=3093215911838831,
	)
	Tiny52_Generator_Point = Point(2730087332105783, 2918974547317441, TinyCurve52)

	TinyCurve56 = ShortWeierstrassCurve(
		name="TinyCurve56",
		a=17387714570041336,
		b=14158762040267516,
		prime_mod=50544702849929377,
		order=50544703140954961,
	)
	Tiny56_Generator_Point = Point(36182928645730553, 5540583353843909, TinyCurve56)


	#### Setup
	#User1 Generates their Private Public KeyPair
	privateKey1, public_point1 = generate_KeyPair(Tiny32_Generator_Point)
	print(privateKey1, public_point1)

	#User2 Generates their Private Public KeyPair
	privateKey2, public_point2 = generate_KeyPair(Tiny32_Generator_Point)
	print(privateKey2, public_point2)

	#### Exchange Data

	# User1 receives User2's Public Key

	# User2 receives User1's Public Key


	#### Key Generation

	#User1 Takes their Private Key and Multiplies it by User2's Public Key
	user1_shared_key = privateKey1 * public_point2


	#User2 Takes their Private Keu and multiplies it by User1's Public Key
	user2_shared_key = privateKey2 * public_point1


	#### Assurance that the shared key is the same

	#print(user2_shared_key, user1_shared_key)
	assert user1_shared_key == user2_shared_key

	data = pollardrho(Tiny32_Generator_Point, public_point1)
	print(data)

#3735087922 TinyCurve32: x=612544702, y=2755544091
#50009172 TinyCurve32: x=2971908904, y=1911617225
#3735087922
#[Finished in 4.1s]

Invalid Curve Point attack¶

Not testing that both points x and y are on the curve can break the protocol

Optimus Anti-Primes¶

Since multiplication is commutative, it’s possible that two unrelated pairs of participants could perform an ECDH step and agree on the same shared secret.

This is true for the same reason that 3\times{8} = 4\times{6}, and because your secret key is a random integer.

For this reason, it’s generally unwise to use raw ECDH outputs as encryption keys. Instead, you want to use a cryptographic hash function over the ECDH output and each participants’ public keys to guarantee your symmetric session key is distinct from other pairs.