[Kah67]. From the second world war onward, this rapidly became less of an art

form and more and more a serious branch of mathematics.

Both coding theory and cryptography have been already proven to be essential

in our information age. While they may seem to achieve opposite goals at ¬rst sight,

they share much more than that. This thesis aims to reveal at least part of that

vii

viii PREFACE

relation: how coding theory can be applied in cryptography. In the ¬rst chapter, a

more detailed introduction to the objectives of cryptography will be given. Also, a

short description of the basics of coding theory will be given there.

In Chapter 2 attacks on the McEliece public“key cryptosystem are introduced

in which a malicious sender, or an adaptive eavesdropper, has a method available

to ¬nd out whether a ciphertext decrypts properly or not. From this information

she can then extract the plaintext that was encrypted. In this chapter it is shown

that the McEliece public“key cryptosystem is indeed susceptible to these kinds of

attacks and a detailed algorithm for such an attack is given and analyzed. Thus

care should be taken when implementing this scheme, and possible countermeasures

are discussed which thwart this attack.

Chapter 3 deals with the security of digital signature schemes based on error“

correcting codes. Several attacks against the Xinmei scheme, the ¬rst such scheme,

are surveyed and reasons for the failure of the Xinmei scheme are given. Another

weakness is found in another such scheme, proposed by Alabbadi and Wicker, which

leads to an attacker being able to forge signatures at will. Further analysis shows

that this new weakness also applies to the original Xinmei scheme.

Then, in Chapter 4, work of a more theoretical nature will be discussed. In

this chapter two families of numbers are introduced which can e¬ciently be tested

for primality. These families naturally extend the Mersenne numbers to the area of

elliptic curves. The ¬rst few primes in these families are also presented and compared

to the generalized Wagsta¬ conjecture. However, results from this chapter will turn

out to be useful in the last chapter.

Lastly, Chapter 5 will employ algebraic geometry to produce pseudorandom

sequences. Some known constructions to produce pseudorandom sequences with

the aid of elliptic curves will be generalized there. Both additive and multiplicative

characters on elliptic curves will be used for this purpose. Finally, the use of linear

recurrencies on elliptic curves will be studied.

Chapter 1

Preliminaries and notation

1.1 Cryptography

The aim of cryptography is to provide secure transmission of messages, in the

sense that two or more persons can communicate in a way that guarantees that the

desired subset of the following four primitives is met:

(i). Con¬dentiality. This primitive is usually perceived to be the main focus of

cryptography, providing a way such that the information can only be viewed

by those people authorized to see it.

(ii). Data integrity. This service will provide a means to check if the transmitted

information was altered in any way, including but not limited to things like

insertion, deletion and substitution of messages.

(iii). Authentication. This service will establish some identity pertaining to the

message. Thus, this primitive can (among others) be used to guarantee the

identity of the sender, guarantee the identity of the receiver, or guarantee the

time the message was sent.

(iv). Non-repudiation. This serves to prevent someone from denying previous com-

mitments. It is needed in cases where disputes might have to be resolved, for

instance in E-commerce.

While cryptography is often thought of as a tool to provide con¬dentiality, the

other three primitives are actually much more important in daily life.

In order to build cryptographic protocols supplying one or more of the above

primitives, some building blocks are needed. For instance, one often uses a one-way

function, of which the values should be easy to compute, but the inverse should

be impossible to compute for most values. In practice, one is often content with a

function for which it is computationally infeasible to compute inverses from. When

a one-way function is de¬ned on arbitrary inputs (i.e. on bitstrings of arbitrary

length), it will be called a hash function. If a one-way function can be (e¬ciently)

inverted given some additional information, it is called a trapdoor one-way function.

1

2 Preliminaries and notation

In a cryptographic protocol, the users are often called Alice and Bob (instead of

A and B). An eavesdropper or adversary will be denoted by Eve. This terminology

will be used throughout this thesis. The initiator of the protocol will be called Alice

(so usually she will be the sender), and the intended recipient will be called Bob.

Cryptographic protocols include such things as encryption schemes, also called

cryptosystems, which aim to achieve con¬dentiality. A description of such a scheme,

called the McEliece cryptosystem, which is based on coding theory, will be given

in Section 2.2. Other well-known cryptosystems are, among others, DES [MOV97,

Section 7.4], AES [DR98], RSA [RSA78] (which can be used for digital signatures

as well) and Di¬e-Hellman [DH82], which is used for key agreement. Other ex-

amples of cryptographic protocols include digital signature schemes, which try to

establish authentication and data integrity of a certain message. A history of sig-

nature schemes based on error“correcting codes will be given is Section 3.1. Others

include RSA [RSA78] and DSA [MOV97, Section 11.5]. For a more complete list

of cryptographic protocols, as well as descriptions of those only mentioned here, see

[MOV97].

1.2 Coding Theory

The aim of coding theory is to provide secure transmission of messages, in the

sense that (up to a certain number of) errors that occurred during the transmission

can be corrected. However, for this capability a price must be paid, in the form

of redundancy of the transmitted data. In this thesis only linear codes will be

considered.

First the alphabet Fq is chosen. In practice, this usually is the ¬eld of binary

numbers, but any prime power q is allowed. Let Fn denote a n“dimensional vector

q

space over the ¬nite ¬eld Fq . A linear [n, k] code C is a k“dimensional linear subspace

of Fn . The elements of C are similarly called codewords. A generator matrix G for

q

C is a k — n (q“ary) matrix whose rows span C. This means that each codeword c

can be written as c = mG (in C) with m ∈ Fk . One can formulate this by saying

q

that the message vector m is encoded in the codeword c. The quantity n ’ k is

the redundancy of C. It gives the number of excess symbols in c, compared to the

message vector m.

Now c is sent over an (unreliable) channel and certain errors may be in¬‚icted

on c: the received vector is y = c + e where e is a so called error vector. Let

the Hamming weight wH (x) of a vector x simply count the number of non“zero

coordinates of x. If the weight of e is not too large, the received vector y coincides

on many coordinates with c and c can be recovered.

With a code C one can associate its dual code C ⊥ , which is the (n’k)“dimensional

subspace orthogonal to C. In other words, the dual code consists of all vectors of Fn q

that are orthogonal to all codewords of C. A generator matrix H of the dual code

C ⊥ is also called a parity check matrix of C, since it has the property that cH T = 0

for each codeword c ∈ C and vice versa.

1.2 Coding Theory 3

The (Hamming) distance dH (x, y) between vectors x and y is de¬ned as the

number of coordinates where x and y di¬er. Note that dH (x, y) = wH (x ’ y).

The minimum distance d of a code C is de¬ned as the minimum Hamming distance

between di¬erent codewords in C. Since C is linear, an equivalent de¬nition would

be that d is the minimum non“zero weight of a codeword in C. A [n, k] code with

minimum distance d will be denoted as a [n, k, d] code. In general, determining

the minimum distance d of a certain code (given e.g. by a generator matrix) is

not an easy problem. However, some bounds on the minimum distance are known,

one of which is Singleton™s bound d ¤ n ’ k + 1. Let Aw denote the number of

codewords in C of Hamming weight w. The numbers A0 , A1 , . . . , An are called the

weight distribution of C.

The number t = d’1 is called the error“correcting capability of C. It follows

2

from the triangle inequality that for each element y in Fn there can be at most one

q

element c in C at Hamming distance ¤ t to it. So, in principle, one can correct up

to t errors in¬‚icted to an element in C by ¬nding the nearest point in C. However, in

practice the process of determining the nearest point (called decoding) is often very

complex. To illustrate, the problem for general linear codes on deciding on whether

there exists a point in C at a given distance of a given point x ∈ Fn is known to be

q

in the class NP“complete [BMT78]. Fortunately there are certain classes of linear

codes where decoding can be done quite e¬ectively. As an example of this, Goppa