Algorithmic Algebra - A Classical Introduction to Cryptography: Applications for Communications Security - page 176

An elliptic curve is singular if its discriminant

is zero. We can prove that this
is equivalent to the fact that the algebraic equation which defines the elliptic
curve has a singular point. We notice that this is excluded by our definitions.
An elliptic curve is supersingular if its trace of Frobenius is multiple of the
characteristic of the field. For the characteristic two case, we can prove that it is
equivalent to j = 0, which is excluded by our definition. For a characteristic p >

1.
An elliptic curve is anomalous if its trace of Frobenius is one. This implies that
# E

3, we can prove that it is equivalent to t = 0, which implies that # E = # K +

= # K .

According to the state of the art of research, these special curves (except anomalous
curves of characteristic two) should be avoided for cryptographic use.

6.6 Exercises

Exercise 6.1. Show that the Caesar cipher is “isomorphic” to the addition of 3 in Z 26 .
Similarly, what is ROT13?

Exercise 6.2. Show that the Vigenere cipher can be considered as a block cipher in
ECB mode defined by addition in Z 26 .

2 − 1 .Prove Exercise 6.3. Let a, b, and n be three integers of at most bits and n ≥

2 ) .

that we can compute a × b mod n within a time complexity of O (

Exercise 6.4. Let a and b be two integers of at most bits. Prove that we can perform

2 ) .

an Euclidean division a = bq + r within a complexity of O (

Exercise 6.5. We define a new cipher. The message space is Z 26 (we encrypt arbitrary
long alphabetical messages in ECB mode). The key space is Z 26 ×

Z 26 with a uniform

distribution. Given a key K = ( a , b ) , we define C ( x ) = ax + b mod 26 .

How many possible keys do we have?
Show that we have perfect secrecy.
How can we break it with a known plaintext attack?

Exercise 6.6 (Hill cipher). We define a new cipher. The message space is Z 26 . The key
space is the set of all m

× m invertible matrices in Z 26 .

How many keys do we have?
How can we break it with a known plaintext attack?

Exercise 6.7. Let p be an odd prime number. Prove that the algorithm in Fig. 6.7
computes square roots in Z p .