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

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.


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
Full Text: DOI


[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)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.