= (111) + (001) + (101) = (011).

Clearly, this is equal to h (001), (000001) , and Bob will accept the signature as

valid.

3.5.3 Cryptanalyzing the modi¬ed Alabbadi“Wicker scheme

Since the error vector f is not revealed to Bob, and thus also remains hidden

from Eve, the recovery of H is no longer feasible. However, a universal forgery is

˜

still possible. Eve should ¬rst construct an analogous (non-degenerate) matrix R

by ¬nding a solution to the equation

˜

RW = W ’R .

˜ ˜

Then she should ¬nd analogous matrices W and Y as described in Section 3.5.2.

Suppose Eve wants to forge a signature of the message m. To that end, she picks

a random e of weight w(e) = t , and then calculates a solution f to the equation

˜

T

eH“ = f RH directly. Note that a solution always exists, since all syndromes are

taken by the vectors in Fn . Since this means solving a system of k linear equations

2

for n variables, it is possible to do this e¬ectively. Note that H“ is e¬ectively public,

since both G(z) and the order of coordinates {γi } of F2m are public. She then sets

˜ ˜

x = (e + f + h(m, e)W + xY )R.

˜ ˜

s = (e + h(m, e)W + xY )R.

Bob will accept this pair as a valid signature of m, since it passes the second step

of the veri¬cation procedure:

˜ ˜ ˜

(x + s)H = (e + f + h(m, e)W + xY + e + h(m, e)W + xY )RH

˜ T

= f RH = eH“ ,

as well as the last step of the veri¬cation:

˜ ˜

sW + xW + eW ’R = (e + h(m, e)W + xY )RW + xW + eW ’R

˜

= eW ’R + h(m, e)W W ’R + xY W ’R + xW + eW ’R

= h(m, e) + xW + xW = h(m, e).

3.6 Discussion 35

Thus Eve can construct a signature for any message m. Note that this (second)

universal forgery can be slightly adapted to apply to the unmodi¬ed Alabbadi“

Wicker scheme as well, given that the decoding step in the veri¬cation is made

possible.

3.6 Discussion

˜˜

The above universal forgery makes use of analogous matrices such as G, W and

˜

Y . There are other possible drawbacks of the Alabbadi“Wicker scheme which shall

not be discussed here. The aim of this discussion is to ¬nd the reason behind the

above universal forgery. This may help to improve the Alabbadi“Wicker scheme or

design new signature schemes using error“correcting codes.

From the description of the universal forgery attack, it seems very di¬cult to

prevent this kind of forgery. The designers of the scheme were hoping to hide the

real secret key G between its analogous matrices using the simple fact that there are

many analogous matrices. Thus it will be infeasible for Eve to ¬nd the original map

between the message and signature, which is de¬ned by the secret key G. However,

they did not realize that Bob does not have the ability to check this original map

˜˜

between the message and its signature. Even though the analogous matrices G, W

˜

and Y de¬ne a di¬erent map, Bob cannot detect it because he does not know the

secret key.

In addition, the universal forgery in Section 3.5.2 also shows that neither the

Alabbadi“Wicker scheme nor the Xinmei scheme have the important property that it

should be infeasible for Eve to ¬nd a signature algorithm that passes the veri¬cation

step given only this veri¬cation algorithm and the public keys. In fact, there are

many such signature algorithms she can come up with. It is very di¬cult for the

designer to defeat them when he designs a digital signature scheme using the same

method as the Xinmei scheme.

Up to now all attempts to design a secure digital signature scheme based in

this way on error“correcting codes have failed. Why is it so hard to design such

a scheme? This is because these signature schemes do not really depend on the

hardness of the decoding problem of general error“correcting codes.

Van Tilburg [Til94] showed that signature schemes, where the security is based

only on the bounded, hard“decision decoding problem for linear codes, do not exist.

However Kabatianskii, Krouk and Smeets proposed a digital signature scheme based

on random error“correcting codes in 1997 [KKS97]. They exploited a hardly known

fact that for every linear code the set of its correctable syndromes contains a linear

subspace of relatively large dimension L. Unfortunately their scheme can only be

used once. Even so, it does give some new ideas to further explore the use of this

intractability feature of the decoding problem.

36 Digital signature schemes based on error“correcting codes

3.7 Conclusion

In this chapter the security of digital signature schemes based on error“correcting

codes was discussed and some existing weaknesses in the Xinmei scheme were sur-

veyed. Potential threats from matrices that have the same properties as some of the

secret matrices, so“called analogous matrices, were explored as well. As an example

a universal forgery of the Alabbadi“Wicker scheme was presented.

Chapter 4

Two families of Mersenne“like

primes

Summary. 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. This chapter

is based on joint work with Peter Beelen [BD03].

4.1 Introduction

Two families of prime numbers, not unlike the Mersenne primes, for which an

e¬cient primality test exists, will be studied in this chapter. For one of these families

a primality test which is as fast as the test for Mersenne numbers is presented. For

Mersenne numbers this test has led to the discovery of very big primes. In fact, the

largest explicitly known prime number at this moment (April 2003) is a Mersenne

prime. For a list of large known prime numbers see [YC03].

4.2 Testing for primality

In this section some known results concerning primality testing will be reviewed.

For an exposition of these and other tests see e.g. [Rib96].

Proposition 4.2.1 (Proth) Let n be√ odd natural number and suppose that n ’

an

1 = 2 R, where R is odd and less than n. If a number a exists such that a(n’1)/2 ≡

e

’1 (mod n), then n is a prime.

Proof: Let p be the smallest prime divisor of n and let b be the order of a (mod p).

Thus b is a divisor of p ’ 1. Since a(n’1)/2 ≡ ’1 (mod n) the greatest common

divisor of n and a(n’1)/2 ’ 1 is equal to one. Thus the greatest common divisor

of p and a(n’1)/2 ’ 1 must also be equal to one. But ab ≡ 1 (mod p), and since

37

38 Two families of Mersenne“like primes

a(n’1)/2 ≡ 1 (mod n), b cannot divide (n ’ 1)/2 = 2e’1 R. Since an’1 ≡ 1 (mod n),

b divides n ’ 1 = 2e R. The conclusion is that 2e divides b and hence that 2e divides

√

p ’ 1. Thus p ≥ 2e + 1 > n and a contradiction arises. So one can conclude that

n has no prime factors.

Proth™s test can be extended: