Generation of pseudorandom sequence over elliptic curve group and their properties. (English) Zbl 1154.11045

Sathyanarayana, S. V.; Ashwatha Kumar, M.; Hari Bhat, K. N.

J. Discrete Math. Sci. Cryptography 10, No. 6, 731-747 (2007).

The authors propose a pseudorandom sequence generator over elliptic curves in a quite direct way: Pick an element of higher order in an elliptic curve, choose a prime number greater than that order, and, using a linear feedback shift register (LFSR), generate a sequence of random integers in the primitive field of that prime characteristic; then the pseudorandom sequence consists of the multiples of the higher order element by those random integers.
For instance for \(m=8\), \(\mathbb F_{2^8}\) can be realized as \(\mathbb F_{2}[X]/(X^8+X^4+X^3+X^2+1)\) and for a primitive element \(g\in\mathbb F_{2^8}\) consider the elliptic curve \(E\): \([Y^2+XY =X^3+g^4X^2+1]\). The order of \(E\) is \(288 = 2^5 3^2 = 3\cdot 96\). The element \(x=(g^{11},g^{25})\in E\) has order \(n=96 = 2^5 3\). Let \(p=97=n+1\). The polynomial \(C(X)=X^4+X+23\) is irreducible over \(\mathbb F_p\) and it is taken as a “connection polynomial”. A LFSR \((k_j)_j\) is built through the recurrence \(k_j+k_{j-3}+23=0\,\text{mod}\,p\), hence \(k_j=(96\,k_{j-3}+74)\,\text{mod}\,p\), and its period is \(p^4-1 = 88\,529\,280\). Then the random sequence in the elliptic curve \(E\) is \(((x_j,y_j)=k_j(g^{11},g^{25}))_j\).
The authors show that such pseudorandom sequences succeed to pass the FIPS criteria for randomness. They also apply such sequences in well known image encryption procedures [S. Lin, An introduction to error-correcting codes, Prentice-Hall (1970)]. English could be improved (for instance there is a continuous lack of articles), hence reading is difficult in some parts of the paper.

Reviewer: Guillermo Morales-Luna (Mexico)

MSC:

11T71	Algebraic coding theory; cryptography (number-theoretic aspects)
11G05	Elliptic curves over global fields
94A55	Shift register sequences and sequences over finite alphabets in information and communication theory

Keywords:

pseudorandom generators; elliptic curves

References:

[1]	Menezes A., Elliptic Curve Public Key Cryptosystems (1993)
[2]	Schneier B., Applied Cryptography, 2. ed. (1996) · Zbl 0883.94001
[3]	Zeng K. C., IEEE Trans. on Computers 24 (2) pp 8– (1991)
[4]	Koblitz N., A Course in Number Theory and Cryptography (1994) · Zbl 0819.11001
[5]	Lee L. P., Computers and Mathematics with Applications 47 pp 217– (2004) · Zbl 1048.65002
[6]	Robshaw M. J. B., RSA Lab. Technical Report, TR-701 (1995)
[7]	Koblitz N., Advances in Cryptology–CRYPTO’91, Lecture Notes in Computer Science 576 pp 156– (1992)
[8]	Koblitz N., Mathematics of Computations 48 pp 203– (1987)
[9]	Mita, R., Paumba, G., Pennisi, S. and Poli, M. 2002. A novel pseudo random bit generator for cryptography applications. 9th International Conference. September15–182002. Vol. 2, pp.489–492. in, on
[10]	Sathyanarayana, S. V., Kumar, M. A. and Haribhat, K. N. 2005. Study of elliptic curve based pseudo random sequence generator. 5th National Workshop on Cryptology. August12–142005. Shimoga: JNNCE.
[11]	Sathyanarayana, S. V., Kumar, M. A. and Bhat, K. N. H. 2004. Some elliptic curve based stream cipher systems. National Conference CCIS 2004. January23–242004. pp.99–105. Goa Government College of Engineering. on
[12]	Lin S., An Introduction to Error Correcting Codes (1970)
[13]	Hansen T., Mathematics of Computation 59 (200) pp 639– (1992)