made, d divides 3. So the period of the resulting binary sequence is either the full

period of the sequence of points on the elliptic curve, or a third of that.

5.7 Conclusion

Sequences obtained by using elliptic curves, as described in this section, certainly

appear to be pseudorandom. When one generates such sequences in practice, all

important statistical properties are well within the ranges one would expect a ran-

dom sequence to have (they pass the FIPS 140-1 statistical tests for randomness).

66 Pseudorandom sequences from elliptic curves

However, only a few statistical properties are proven to hold. The balance and au-

tocorrelation of these sequences are within the range that would be expected for a

random sequence. The question of whether or not these sequences satisfy the expec-

tation of other statistical tests (such as the next-bit test), remains open. Especially

in the area of using linear recurrencies on elliptic curves, more research is needed to

determine the cryptographic strength of sequences generated in this way.

References

[AW92a] M. Alabbadi and S. B. Wicker, Cryptoanalysis of the Harn and Wang

modi¬cation of the Xinmei digital signature scheme, Electronic Letters

28 (1992), no. 18, 1756“1758.

[AW92b] M. Alabbadi and S. B. Wicker, Security of Xinmei digital signature

scheme, Electronic Letters 28 (1992), no. 9, 890“891.

[AW93] M. Alabbadi and S. B. Wicker, Digital signature scheme based on error“

correcting codes, Proceedings of 1993 IEEE International Symposium on

Information Theory, 1993, p. 199.

[AW94] M. Alabbadi and S. B. Wicker, Susceptibility of digital signature schemes

based on error-correcting codes to universal forgery, Error control, cryp-

tology, and speech compression (Moscow, 1993), Springer, Berlin, 1994,

pp. 6“12.

[AW95] M. Alabbadi and S. B. Wicker, A digital signature scheme based on linear

error-correcting block codes, Advances in cryptology”ASIACRYPT ™94

(Wollongong, 1994), Springer, Berlin, 1995, pp. 238“248.

[Bar97] A. Barg, A large family of sequences with low periodic correlation, Dis-

crete Math. 176 (1997), no. 1-3, 21“27.

[BD02] P. H. T. Beelen and J. M. Doumen, Pseudorandom sequences from elliptic

curves, Finite Fields with Applications to Coding Theory, Cryptography

and Related Areas, Springer Verlag, 2002, pp. 37“52.

[BD03] P. H. T. Beelen and J. M. Doumen, Two Mersenne-like families of prime

numbers, Manuscript, 2003.

[BDL97] D. Boneh, R. A. DeMillo, and R. J. Lipton, On the importance of

checking cryptographic protocols for faults (extended abstract), Advances

in cryptology”EUROCRYPT ™97 (Konstanz), Springer, Berlin, 1997,

pp. 37“51.

[Bee01] P. H. T. Beelen, Algebraic geometry and coding theory, Ph.D. thesis, Eind-

hoven University of Technology, 2001.

[Ber97] T. A. Berson, Failure of the McEliece public-key cryptosystem under

message“resend and related“message attack, Advances in Cryptology “

67

68 REFERENCES

CRYPTO ™97, Lecture Notes in Computer Science 1294 (B. S. Kaliski Jr.,

ed.), Springer-Verlag, 1997, pp. 213“220.

[BKT99] A. Barg, E. Krouk, and H. C. A. v. Tilborg, On the complexity of mini-

mum distance decoding of long linear codes, IEEE Trans. Inform. Theory

45 (1999), no. 5, 1392“1405.

[Ble98] D. Bleichenbacher, Chosen ciphertext attacks against protocols based

on the RSA encryption standard PKCS #1, Advances in Cryptology -

CRYPTO 1998, Springer-Verlag, 1998, pp. 1“12.

[BMT78] E. R. Berlekamp, R. J. McEliece, and H. C. A. v. Tilborg, On the inherent

intractability of certain coding problems, IEEE Trans. Information Theory

IT-24 (1978), no. 3, 384“386.

[Bom66] E. Bombieri, On exponential sums in ¬nite ¬elds, Amer. J. Math. 88

(1966), 71“105.

[Bre89] D. Bressoud, Factorization and primality testing, Springer-Verlag, New

York, 1989.

[BS93] E. Biham and A. Shamir, Di¬erential cryptanalysis of the data encryption

standard, Springer-Verlag, New York, 1993.

[BS96] E. Bach and J. Shallit, Algorithmic number theory. Vol. 1, MIT Press,

Cambridge, MA, 1996, E¬cient algorithms.

[BS97] E. Biham and A. Shamir, Di¬erential fault analysis of secret key cryp-

tosystems, Lecture Notes in Computer Science 1294 (1997), 513“522.

[CFS01] N. Courtois, M. Finiasz, and N. Sendrier, How to achieve a McEliece-

based digital signature scheme, Advances in Cryptology - ASIACRYPT

2001, Springer-Verlag, 2001, pp. 157“174.

[Cha95] F. Chabaud, On the security of some cryptosystems based on error-

correcting codes, Advances in cryptology”EUROCRYPT ™94 (Perugia),

Springer, Berlin, 1995, pp. 131“139.

D. Cox, Primes of the form x2 + ny 2 , John Wiley & Sons Inc., New York,

[Cox89]

1989, Fermat, class ¬eld theory and complex multiplication.

[CS98] A. Canteaut and N. Sendrier, Cryptanalysis of the original McEliece cryp-

tosystem, Advances in cryptology”ASIACRYPT™98 (Beijing), Springer,

Berlin, 1998, pp. 187“199.

[DH82] W. Di¬e and M. E. Hellman, New directions in cryptography, Secure

communications and asymmetric cryptosystems, Westview, Boulder, CO,

1982, pp. 143“180.

[DR98] J. Daemen and V. Rijmen, Aes proposal: Rijndael, 1998,

www.esat.kuleuven.ac.be/˜rijmen/rijndael/.

[Dum96] I. Dumer, Suboptimal decoding of linear codes: partition technique, IEEE

Trans. Inform. Theory 42 (1996), no. 6, part 1, 1971“1986, Codes and

complexity.

REFERENCES 69

[ElG85] T. ElGamal, A public key cryptosystem and a signature scheme based on

discrete logarithms, Advances in cryptology (Santa Barbara, Calif., 1984),

Springer, Berlin, 1985, pp. 10“18.

[FO99] E. Fujisaki and T. Okamoto, How to enhance the security of public-key

encryption at minimum cost, Public Key Cryptography, 1999, pp. 53“68.

[GBS00] G. Gong, T. Berson, and D. Stinson, Elliptic curve pseudorandom se-

quence generators, Selected areas in cryptography (Kingston, ON, 1999)

(Berlin), Springer, 2000, pp. 34“48.

[GL02] G. Gong and C. C. Y. Lam, Recursive sequences over elliptic curves,

Sequences and their Applications - SETA ™01, Springer, London, 2002,

pp. 182“196.

[GMT82] S. Goldwasser, S. Micali, and P. Tong, Why and how to establish a private

code on a public network, 23rd annual symposium on foundations of com-

puter science (Chicago, Ill., 1982), IEEE, New York, 1982, pp. 134“144.

[Gra01] J. Grantham, Frobenius pseudoprimes, Math. Comp. 70 (2001), no. 234,

873“891.

[Hal94] S. Hallgren, Linear congruential generators over elliptic curves, Tech.

Report CS-94-143, Dept. of Comp. Sc., Carnegie Mellon Univ., 1994.

[Ham50] R. W. Hamming, Error detecting and error correcting codes, Bell System

Technical Journal 29 (1950), 147“160.

[HGS99] C. Hall, I. Goldberg, and B. Schneier, Reaction attacks against several

public-key cryptosystems, Proceedings of Information and Communica-

tion Security, ICICS™99, Springer-Verlag, 1999, pp. 2“12.

[HW79] G. H. Hardy and E. M. Wright, An introduction to the theory of numbers,

¬fth ed., The Clarendon Press Oxford University Press, New York, 1979.

[HW92] L. Harn and D. C. Wang, Cryptoanalysis and modi¬cation of digital signa-

ture scheme based on error“correcting codes, Electronic Letters 28 (1992),

no. 2, 157“159.

[Kah67] D. Kahn, The codebreakers: the story of secret writing, MacMillan Pub-

lishing Company, New York, NY, USA, 1967.

[KFL85] T. Kasami, T. Fujiwara, and S. Lin, An approximation to the weight dis-

tribution of binary linear codes, IEEE Trans. Inform. Theory 31 (1985),

no. 6, 769“780.

[KJJ99] P. Kocher, J. Ja¬e, and B. Jun, Di¬erential power analysis, Advances in

Cryptology - CRYPTO 1999, Springer-Verlag, 1999, pp. 388“397.

[KKS97] G. Kabatianskii, E. Krouk, and B. Smeets, A digital signature scheme

based on random error-correcting codes, Cryptography and coding

(Cirencester, 1997), Springer, Berlin, 1997, pp. 161“167.

70 REFERENCES

[KL95] I. Krasikov and S. Litsyn, On the accuracy of the binomial approximation

to the distance distribution of codes, IEEE Trans. Inform. Theory 41

(1995), no. 5, 1472“1474.

[Kob01] N. Koblitz, Almost primality of group orders of elliptic curves de¬ned

over small ¬nite ¬elds, Experiment. Math. 10 (2001), no. 4, 553“558.

[Koc96] P. C. Kocher, Timing attacks on implementations of Di¬e-Hellman,

RSA, DSS, and other systems, Lecture Notes in Computer Science 1109

(1996), 104“113.