IV054
Solution of HW 8
1 Hashing and ElGamal signature
See the file signature.xls.
2 Hasse theorem for bounds of EC order; EC with the same order an different group structure
By Vincent Mihalkovic:
SageMath helps me a lot:
maxx, minn = 0, Integer.MAX_VALUE
for a in range(7):
for b in range(7): # We need to check non-singularity (-16(4a**3 + 27b**2) '/, 7 1= 0)
E = EllipticCurve(GF(7), [a,b]) number_of_points = len( E.pointsO ) if number_of_points < minn:
minn = number_of^points
min_curve - E if number_of.points > maxx:
maxx = number_of_points
max_curve = E if number_of_points == 9:
print( E.abelian_group() )
(b) Additive Abelian group isomorphic to Z3 x Z3 embedded in Abelian group of points on Elliptic Curve defined by y1 = x3 + 2 over f7
If we look at the points ([00, {0, 3), {0, 4), {3,1), (3, 6), (5,1), (5, 6), (6,1), (6,6)]) All of them has order 3 (except 00) there is no generator element with order 9.
But additive Abelian group isomorphic to Zg embedded in Abelian group of points on Elliptic Curve defined by y2 = x3 + 3x + 2 over F7, has
oo, (0, 3), (0,4), (2,3), (2,4), (4,1), (4, 6), (5, 3), (5, 4)] points, in which six of them (2,3), (2,4), (4,1),... ] has order 9, thus they are generators of this Abelian group!
printC min_curve, min_ctrrve. points () print( max_curve, max_curve.points 0
(a) First, look at the HasseV theorem on elliptic curves:
|JV-p-l|<2^ |JV-8|<2\/8 S-2v/8<Ar<8 + 2\/8 3 < N < 13
1
3   Proof of theorem and estimating bounds
By Jakub Doczy:
(a) When considering, if i £ Zp; (x = i, y) is ft valid point on a curve, we have to evaluate yl — xli 4 ax2, + b and determine, if x^ 4- aa;* 4- 6 is a quadratic residue. We have 3 possible outcomes.
(i) x^ 4- ax* 4- b = 0 : is a point on a curve,
(ii) x'1 + ax* 4-1 is a quadratic residue : (x,y), [x, —y) are points on a curve (if jj is a prime, we can always find two distinct points because y ^ — y mod p and (—y)^ = y*).
(iii) x'1 + ax2 4- b is not a quadratic residue : there cannot exist any y, such that (s, y) is a point on this elliptic curve,
Since this lists all possible points (x, y) for any x e Zp, we can count the number of points on elliptic curve E as:
jj- 1 f 0    if xli 4- ax2 4- b is not a quadratic residue |£| = 1 4 ^ < 1   if ir3 4- <M;a 4 b = 1
i-o [2    if i'* 4- na-2 4 fc is a quadratic residue
We have to add 1, because of the neutral element (0), And this equation is equivalent to:
w.1+g((^±i)tl)_lt,+g(^±i)
(b) The number of points on elliptic curve is bound by Hesse's theorem
jj -       — l<N<p+       + 1 Substituting N by equation from a) we get:
p-1 /„3 .__2
p-2v/p-l<l +
P-1    y -J
, + £(*±f±!)S, + .v»+.
r=tl ^ * '
/ i-3 4- (IE2 4 fr\
< 2y5
2
4 Factorization
By Daniel Schramm:
We know that the function f(x} = 2T mod 1327 has a period r = 460.
To factorise the number 1927 we will perform a subroutine of the Slior's quantum polynomial time algorithm for integer factorisation.
First, we check whether r = 460 is an even number. Obviously, r is an even number.
Therefore, we continue by checking if 25 = ±1 (mod 1927).
Since 2"5- = 1270 (mod 1927), we know that 1270 is a nontrivial solution of x1 = 1 (mod 1927). This implies that 1927 | ((1270 - 1) ■ (1270 + 1)).
We compute the factors JVi, JV2 of 1927 as follows:
Ni = gcd(1270 - 1,1927) JVS = gcd(1270 + 1,1927)
= 47 =41
The factors of the number 1927 are 41 and 47.
5   Finding order of EC using Hasse's theorem and Langrange's
By Markéta Naušová:
First we can use Hasse's theorem to get some bounds on the number of points on the elliptic curve E. From the assignment we have p = 113. The Hasse's theorem says that ||£| — p — 1| < 2^/p. We can modify the nonequality so that is says that |£?| < p +       + 1 and \E\ > p —       + 1,
\E\ > 113- 2v/Il3+ 1 = 92,7 \E\ < 113 + 2v/113+ 1 = 135,3
'] UiirJwH' \\v Jj.ivr '.hi: Ltiu^rr buiiuds i)3 '.
Let's denote the points on the curve from the assignment as P = (74. 3) and Q = (28,11). Eacli point of the curve generates a cyclic subgroup. For example point P generates a subgroup of order 3 and point Q generates a subgroup of order 14 (the order is the number of points in the subgroup, so that is is the smallest positive integer k st kP — 0).
Lagrange's theorem says that if H is a subgroup of a finite group C\ then the order of H divides the order of G.
We can use this theorem to find number of point of the curve E. We know that {E.+) has subgroup generated by P with order 3 and another subgroup generated by Q with order 14. It must hold (hiii 'A utdvr of ^iou]> formed by E ami J L | ■: ■ I ■■ -j ui '^toup f'oitm'd by Í:'. Sbicr onlt-i ul ^ruiip \-. thr number of elements in the group we can write 3 | \E\ and 14 | (3 and 14 divide |E|). Hence we can say that \E\ — k ■ 3 for some integer k and also \E\ — I • 14 for some integer Í. Together we can say that \E\ = m - 3 - 14 = m - 42 for some integer m. The only m for which also the condition 93 < \E\ = m > 42 < 135 holds is m = 3, which gives us \E\ = 42 - 3 = 126. The number of points of E is therefore 12f>.
3
6   Discovering vulnerability of the established key
By Ales Paroulek: n4P = (55,0)
liy definition uf pfjim ;i<aJhi(j]i. if v. r \\dt[ 1v. u [juhiH /J; and      Midi liial l'\ — !\ and i.J. 1Jjt■
lambda will Lave no solution and in such a case the result will be the infinity point,
Since Bob chose a number n& which will multiply the point tiaP, the only possible keys are (55, 0) and the infinity point, since (55,0) 4- (55,0) = oo and (55,0) + oo = (55,0) and this would again
4