Exercise 1¶

In [3]:
# Define the finite field over which this exercise occurs
p = 2^31 - 1
Fp = GF(p)
Fp
Out[3]:
Finite Field of size 2147483647
In [4]:
# Define the parameters of the twisted Edwards curve
a = p-1
d = 1095662487 # note to self: watch out with plus/minus signs!
In [5]:
x = Fp(2091944770)
y = Fp(562635014)
In [6]:
# When defining the point P,
# we need to make sure to assign numbers from the finite field!
P = (Fp(x), Fp(y))
P
Out[6]:
(2091944770, 562635014)
In [7]:
# A function which sums two points on an Edwards curve.
# It assumes that the points are defined in terms of finite field elements.
def edwards_add(P1, P2, a=a, d=d):
    x1 = P1[0]
    x2 = P2[0]
    y1 = P1[1]
    y2 = P2[1]
    
    sum_x = (x1*y2 + y1*x2)/(1 + d*x1*x2*y1*y2)
    sum_y = (y1*y2 - a*x1*x2)/(1 - d*x1*x2*y1*y2)
    return (sum_x, sum_y)
In [8]:
# A recursive function which computes multiplication on a twisted Edwards curve.
# It recursively calls the addition function to obtain the solution to multiplication with (c-1)P, then adds P to obtain cP.
def edwards_multiply(P, c, a=a, d=d):
    assert c >= 0
    if c == 0:
        return (Fp(0), Fp(0))
    if c == 1:
        return P
    return edwards_add(edwards_multiply(P, c-1, a, d), P, a, d)
In [19]:
Ptimes2 = edwards_multiply(P, 2)
Ptimes2
Out[19]:
(1938333618, 33580178)

Exercise 1cd¶

In [31]:
A = Mod(2*(a+d)/(a-d), p)
# Mod(A, p)
A
Out[31]:
1070703670
In [32]:
B = Mod(4/(a-d), p)
# Mod(B, p)
B
Out[32]:
1076779975

Exercise 1efgh¶

Computing the image of P¶

In [15]:
u = (1+y)/(1-y)
u
Out[15]:
1289259024
In [18]:
# To check whether the finite field is the same as the integers mod p
Mod((1+562635014)/(1-562635014), p)
Out[18]:
1289259024
In [21]:
v = u/x
v
Out[21]:
145720979

Computing the image of 2P¶

In [25]:
x_2 = Ptimes2[0]
y_2 = Ptimes2[1]
x_2, y_2
Out[25]:
(1938333618, 33580178)
In [28]:
u_2 = (1+y_2)/(1-y_2)
u_2
Out[28]:
2033106699
In [29]:
v_2 = u_2/x_2
v_2
Out[29]:
1400545835

Exercise 1ij¶

In [33]:
lambda_slope = (3*u^2 + 2*A*u + 1)/(2*B*v)
lambda_slope
Out[33]:
1485477951
In [35]:
u_3 = B*lambda_slope^2 - A - u - u
v_3 = lambda_slope*(u-u_3) - v
u_3, v_3
Out[35]:
(2033106699, 1400545835)