Beletsky, A. Ya.Білецький, А. Я.2026-03-262026-03-262019https://eir.zp.edu.ua/handle/123456789/27775Beletsky A. Ya. Synthesis of сryptoresistant generators of pseudorandom numbers based on generalized Galois and Fibonacci matrixes / A. Ya. Beletsky // Радіоелектроніка, інформатика, управління. – 2019. – № 3 (50). – C. 86-98.EN: Context. The problem to form generalized primitive matrixes on the Galois and Fibonacci any order over the field characteristics 2 for the construction by the generators gamma functions for cryptographically stable algorithms of inline data encryption, free from the attack of Berlekamp-Messi (BM). Objective. Development of a way to eliminate the threat an attack using the BM algorithm on LFSR-generators of pseudorandom numbers (PRN) to increase their crypto stability. Method. Linear Feedback Shift Registers (LFSR) are themselves good pseudorandom PRN generators, but they have undesirable properties that reduce the efficiency of their use. For the registers of length shift n their internal state is a function of the previous output bits of the generator. Even if the feedback scheme is kept the secret, it can be determined by 2n output bits of the generator with the help of BM algorithm, which reduces the crypto-resistance of the generator PRN. The basis for single loop feedback circuits, which cover the classical LFSR-generators of PRN, are primitive polynomials. There are various ways to increase the crypto-resistance of LFSR-generators. To their number concern: introduction of nonlinear transformations, use poly register generators (as, for example, in the algorithm of encryption А5) and several others. The transition from classical LFSR-generators to generators basis on the generalized matrixes of Galois and Fibonacci leads to the fact that the algorithm of BM loses the ability to determine the unattainable polynomials generating multi-circuit feedback circuits in LFSR-generators. The reason for this feature is that the series of bits generated by the generalized generator becomes dependent not only on the selected irreducible polynomial but also on the primitive element that participates in the creation of the feedback loop generator. Results. The PRN generators developed by LFSR were used to organize bytes of streaming information encryption. Conclusions. Statistical tests of the proposed PRN generators carried out with the help of NIST STS, and Diehard [16–18] packages have confirmed the high quality of the generated sequences. Moreover, the generators turned out to be cryptographically resistant to BM attacks. The use of these generators in the formation of long keys, necessary, for example, in RSA encryption protocols and other applications is promising. As an area of further researches, development of the generalized generators of PRN above a field of Galois of any characteristic. UK: Актуальність. Розглянуто задачу формування узагальнених примітивних матриць Галуа і Фібоначчі будь-якого порядку над полем характеристики 2 для побудови генераторів гамма-функцій криптографически стійких алгоритмів потокового шифрування даних, вільних від атаки Берлекемпа-Мессі. Метод. Лінійні регістри зсуву з лінійними зворотними зв’язками (РСЛЗЗ) самі по собі є хорошими генераторами псевдовипадкових чисел (ПВЧ), але вони мають небажані властивості, що знижують ефективність їх використання. Для регістрів зсуву довжини n їх внутрішній стан є функцією попередніх вихідних бітів генератора. Навіть якщо схема зворотного зв’язку тримається в секреті, її можна визначити по 2n вихідних бітах генератора за допомогою алгоритму Берлекемпа-Мессі, що зменшує криптостійкість генератора псевдовипадкових чисел. Основу одноконтурних ланцюгів зворотного зв’язку, якими охоплені класичні РСЛЗЗ-генератори ПВЧ, складають примітивні поліноми. Існують різні способи підвищення криптостійкості РСЛЗЗ-генераторів ПВЧ. До їх числа відносяться: введення нелінійних перетворень, використання полірегістрових генераторів (як, наприклад, в алгоритмі поточного шифрування А5) і ряд інших. Перехід від класичних РСЛЗЗ-генераторів до генераторів на основі узагальнених матриць Галуа і Фібоначчі призводить до того, що алгоритм Берлекемпа-Мессі втрачає здатність визначати незвідні поліноми, що породжують багатоконтурні ланцюги зворотного зв’язку в РСЛЗЗ-генераторах ПВЧ. Причина зазначеної особливості полягає в тому, що серія бітів, що породжується узагальненим генератором, стає залежною не лише від обраного незвідного поліному, а й від примітивного елемента, який бере участь у створенні ланцюга зворотного зв’язку генератора. Результати. Розроблені узагальнені РСЛОС-генератори псевдовипадкових чисел можуть знайти широке застосування в системах шифрування потокової інформації. Висновки. Статистичні тестування розроблених узагальнених РЗЛЗЗ-генераторів псевдовипадкових чисел, виконані за допомогою пакетів НІСТ СТС та Діхард, підтвердили високу якість генеруються послідовностей. Більш того, генератори виявилися криптографически стійкими до атак Берлекемпа-Мессі. Перспективним є використання цих генераторів для цілей формування ключів великої розмірності, необхідних, наприклад, в протоколах шифрування RSA і в інших додатках. Як напрямки подальших досліджень передбачається розробка узагальнених РЗЛЗЗ-генераторів псевдовипадкових чисел над полем Галуа довільній характеристики.enirreducible polynomialsprimitive matrixesGalois fieldslinear shift registerspseudorandom number generatorsнезвідні поліномипримітивні матриціполя Галуарегістри лінійних зсувівгенератори псевдовипадкових чиселArticle