DEVELOPMENT OF THE SEARCH METHOD FOR NON-LINEAR SHIFT REGISTERS USING HARDWARE, IMPLEMENTED ON FIELD PROGRAMMABLE GATE ARRAYS

Nikolay Poluyanenko

Abstract


The nonlinear feedback shift registers of the second order inare considered, because based on them it can be developed a generator of stream ciphers with enhanced cryptographic strength.

Feasibility of nonlinear feedback shift register search is analyzed. These registers form a maximal length sequence, using programmable logic devices.

Performance evaluation of programmable logic devices in the generation of pseudo-random sequence by nonlinear feedback shift registers is given. Recommendations to increase this performance are given. The dependence of the maximum generation rate (clock frequency), programmable logic devices on the number of concurrent nonlinear registers is analyzed.

A comparison of the generation rate of the sequences that are generated by nonlinear feedback shift registers is done using hardware and software.

The author suggests, describes and explores the search method of nonlinear feedback shift registers, generating a sequence with a maximum period. As the main result are found non-linear 26, 27, 28 and 29 degrees polynomials.


Keywords


stream ciphers; random number generators; M-sequence; search of nonlinear shift registers; non-linear polynomials

Full Text:

PDF

References


Horbenko, Yu. (2015). Pobuduvannia ta analiz system, protokoliv i zasobiv kryptohrafichnoho zakhystu informatsii. Chastyna 1: Metody pobuduvannia ta analizu, standartyzatsiia ta zastosuvannia kryptohrafichnykh system. Kharkiv: Fort, 960.

Biham, E., Dunkelman, O. (2000). Cryptanalysis of the A5/1 GSM Stream Cipher. Progress in Cryptology – INDOCRYPT 2000, 43–51. doi: 10.1007/3-540-44495-5_5

Shaked, Y., Wool, A. (2006). Cryptanalysis of the Bluetooth E 0 Cipher Using OBDD’s. Information Security, 187–202. doi: 10.1007/11836810_14

Schneier, B. (2000). A self-study course in block-cipher cryptanalysis. Cryptologia, 24 (1), 18–33. doi:10.1080/0161-110091888754

Gammel, B. M., Gottfert, R., Kniffler, O. (2007). Achterbahn-128/80: Design and analysis. Workshop Record of The State of the Art of Stream Ciphers – SASC 2007, 152–165.

Chen, K., Henricksen, M., Millan, W., Fuller, J., Simpson, L., Dawson, E., Lee, H., Moon, S. (2005). Dragon: A Fast Word Based Stream Cipher. Information Security and Cryptology – ICISC 2004, 33–50. doi:10.1007/11496618_5

Hell, M., Johansson, T., Meier, W. (2007). Grain: a stream cipher for constrained environments. International Journal of Wireless and Mobile Computing, 2 (1), 86. doi: 10.1504/ijwmc.2007.013798

Canniere, C., Preneel, B. (2006). TRIVIUM specifications. eSTREAM, ECRYPT Stream Cipher Project. Available at: https://citeseer.ist.psu.edu/myciteseer/login

Gittins, B., Landman, H., O’Neil, S., Kelson, R. (2005). A presentation on VEST hardware performance, chip area measurements, power consumption estimates and benchmarking in relation to the aes, sha-256 and sha-512. IACR Cryptology ePrint Archive, 415.

Canteaut, A. (2006). Open Problems Related to Algebraic Attacks on Stream Ciphers. Lecture Notes in Computer Science, 3969, 120–134. doi: 10.1007/11779360_10

Dubrova, E., Teslenko, M., Tenhunen, H. (2008). On Analysis and Synthesis of (n, k)-Non-Linear Feedback Shift Registers. 2008 Design, Automation and Test in Europe, 133–137. doi: 10.1109/date.2008.4484856

Kuznetsov, O., Svatovskyi, I. (2016). Analiz ta porivnialni doslidzhennia symetrychnykh kryptohrafichnykh peretvoren na postkvantovyi period. Kharkiv: KhNU im. V. N. Karazina, 119.

Dubrova, E. (2013). A Scalable Method for Constructing Galois NLFSRs With Period 2n – 1 Using Cross-Join Pairs. IEEE Transactions on Information Theory, 59 (1), 703–709. doi: 10.1109/tit.2012.2214204

Janicka-Lipska, I., Stokłosa, J. (2004). Boolean feedback functions for full-length nonlinear shift registers. Journal of Telecommunications and Informatioin Technology, 4, 28–30.

Golomb, S. W. (1982). Shift Register Sequences. Aegean Park Press, 119.

Dubrova, E. (2014). Generation of full cycles by a composition of NLFSRs. Designs, Codes and Cryptography, 73 (2), 469–486. doi: 10.1007/s10623-014-9947-3

Dubrova, E. (2012). A list of maximum – period NLFSRs. IACR Cryptology ePrint Archive, 166.

Schneier, B. (1995). Applied cryptography (2nd ed.): protocols, algorithms, and source code in C. New York: John Wiley & Sons, Inc., 758.

Kulikova, A. S., Lysenko, I. V. (2012). Realization of diverse stream data encryption with keyless hash functions on the basis of programmable logic. Information processing systems, 7 (105), 22–26.

Kulanov, V., Kharchenko, V., Perepelitsyn, A. (2010). Parameterized IP Infrastructures for fault-tolerant FPGA-based systems: Development, assessment, case-study. 2010 East-West Design & Test Symposium (EWDTS), 452–455. doi: 10.1109/ewdts.2010.5742075

Rachwalik, T., Szmidt, J., Wicik, R., Zabłocki, J. (2012). Generation of Nonlinear Feedback Shift Registers with special – purpose hardware. In Communications and Information Systems Conference, 1–4.

Perepelitsyn, A. E. (2016). Usage of parametrizable ip infrastructures for fpga-based fault-tolerant onboard systems development. Electronic and computer systems, 5 (79), 104–112.

Kolesnyk, I. N., Kulanov, V. O., Perepelitsyn, A. E. (2016). Analysis of fpga technologies application as a part of cloud infrastructure. Electronic and computer systems, 6 (80), 130–135.

Perepelitsyn, A., Shulga, D. (2013). FPGA technologies in medical equipment: Electrical impedance tomography. East-West Design & Test Symposium, 1–4. doi: 10.1109/ewdts.2013.6673157

Potii, A. V., Poluyanenko, N. A. (2008). Analyz svojstv reghystrov sdvygha s nelynejnoj obratnoj svjazjju vtorogho porjadka, gheneryrujushhykh posledovateljnostj s maksymaljnim peryodom. Prykladnaja radyoelektronyka, 3, 282–290.

Potii, A., Poluyanenko, N. (2016). The selection of forming polynomials for shift register with nonlinear feedback second order that generates the sequence with maximum period. Computer science and cybersecurity, 2 (2), 22–30. Available at: http://periodicals.karazin.ua/cscs/article/view/6209/5747

Poluyanenko, N., Potii, A. (2016). Sravnenye ob’ema ansamblia M-RSLOS y M-RSNOS, skorosty heneratsyy na ykh osnove, dlia GF(2) y v rasshyrenyiakh polia GF(22). Radyotekhnyka, 186 (216), 153–160.

Kliucharev, P. G. (2013). Proyzvodytelnost y effektyvnost apparatnoi realyzatsyy potochnikh shyfrov, osnovannikh na obobshchennikh kletochnikh avtomatakh. Nauka i obrazovanye, 10, 299–314. Available at: http://technomag.bmstu.ru/file/669391.html?__s=1




DOI: http://dx.doi.org/10.21303/2461-4262.2017.00271

Refbacks

  • There are currently no refbacks.


Bookmark and Share


Copyright (c) 2017 Nikolay Poluyanenko

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

ISSN 2461-4262 (Online), ISSN 2461-4254 (Print)