Shift registrlarini fikr-mulohazalar bilan. Shift registrlarining fikr-mulohazalari tarixi bilan chiziqli siljish registri

Fikr-mulohazalarni almashtirish registri ( FSR ) ikki qismdan iborat: siljish registri Va qayta aloqa funksiyalari .

Shishish registri (Xato: mos yozuvlar manbai topilmadi) bitlar ketma-ketligidir. Bitni olish kerak bo'lganda, siljish registrining barcha bitlari 1 pozitsiyaga o'ngga siljiydi. Yangi eng chap bit - registrning qolgan bitlaridan qayta aloqa funksiyasining qiymati. Davr Shift registri - natijada paydo bo'lgan ketma-ketlikning takrorlashni boshlashdan oldingi uzunligi.

Teskari aloqani almashtirish registrining eng oddiy turi Teskari aloqa bilan chiziqli siljish registrlari (LFSR – Chapga Fikr-mulohaza Shift Roʻyxatdan oʻtish) (Xato: mos yozuvlar manbasi topilmadi). Fikr-mulohaza shunchaki ba'zi p bitlarning XORidir registr, bu bitlarning ro'yxati chaqiriladi teginish ketma-ketligi.

n-bit LFSR birida bo'lishi mumkin 2 n -1 ichki davlatlar. Bu shuni anglatadiki, nazariy jihatdan bunday registr nuqta bilan psevdo-tasodifiy ketma-ketlikni yaratishi mumkin. 2 n -1 bitlar Ichki holatlar soni va davr tengdir, chunki registrni nollar bilan to'ldirish u nollarning cheksiz ketma-ketligini keltirib chiqaradi, bu mutlaqo foydasizdir. Faqat ma'lum bir bosish ketma-ketligi bilan LFSR hammasi bo'ylab aylanadi 2 n -1 ichki davlatlar. Ushbu LFSRlar deyiladi LFSRmaksimal muddat bilan.

Muayyan LFSR maksimal davrga ega bo'lishi uchun teginish ketma-ketligi va doimiydan hosil bo'lgan ko'phad hosil bo'ladi. 1 ibtidoiy modul bo'lishi kerak 2 .

Polinomning ibtidoiyligini hisoblash ancha murakkab matematik muammodir. Shuning uchun, generatorning maksimal davrini ta'minlaydigan kran ketma-ketliklarining raqamlarini ko'rsatadigan tayyor jadvallar mavjud. Masalan, 32 bitli siljish registrida quyidagi yozuvni topishingiz mumkin: (32,7,5,3,2,1,0) . Bu shuni anglatadiki, yangi bit yaratish uchun XOR funksiyasidan foydalangan holda o'ttiz ikkinchi, ettinchi, beshinchi, uchinchi, ikkinchi va birinchi bitlarni yig'ish kerak.

C++ da bunday LFSR uchun kod quyidagicha bo'ladi:

// Noldan boshqa har qanday qiymat

ShiftRegister = ((((ShiftRegister >> 31)

^ (ShiftRegister >> 6)

^ (ShiftRegister >> 4)

^ (ShiftRegister >> 2)

^ (ShiftRegister >> 1)

^ ShiftRegister)

& 0x00000001)<<31)

| (ShiftRegister >> 1);

qaytish ShiftRegister & 0x00000001;

LFSR dasturiy ta'minotini amalga oshirish juda sekin va agar ular C emas, balki assembler tilida yozilgan bo'lsa, tezroq ishlaydi. Bitta yechim 16 LFSRni parallel ravishda ishlatishdir (yoki kompyuterning o'ziga xos arxitekturasida so'z uzunligiga qarab 32 ta). Ushbu sxema hajmi LFSR uzunligiga teng bo'lgan so'zlar qatoridan foydalanadi va massivdagi so'zning har bir birligi o'zining LFSR ga ishora qiladi. Agar bir xil bosish tartib raqamlari ishlatilsa, bu sezilarli samaradorlikni ta'minlashi mumkin.

BILAN Teskari aloqa sxemasi ham o'zgartirilishi mumkin. Bunday holda, generator katta kriptografik kuchga ega bo'lmaydi, lekin uni dasturiy ta'minotda amalga oshirish osonroq bo'ladi. Yangi eng chap bitni yaratish uchun teginish ketma-ketligining eng chap qismidan foydalanish o'rniga, u har bir kran ketma-ketligini generatorning chiqishi bilan XOR qiladi va uni ushbu harakat natijasi bilan almashtiradi, keyin generatorning natijasi yangi bo'ladi. eng chap bit (Xato: mos yozuvlar manbai topilmadi).

Ushbu modifikatsiya deyiladi Galois konfiguratsiyasi. C da bu shunday ko'rinadi:

statik imzosiz uzun ShiftRegister = 1;

void seed_LFSR (imzosiz uzun urug')

ShiftRegister = urug';

int Galua_LFSR (yaroqsiz)

agar (ShiftRegister va 0x00000001) (

ShiftRegister = (ShiftRegister ^ niqob >> 1) | 0x8000000;

ShiftRegister >>= 1;

Foyda shundaki, barcha XORlar bitta operatsiyada amalga oshiriladi. Ushbu sxemani parallellashtirish ham mumkin.

LFSRlarning o'zlari yaxshi psevdo-tasodifiy ketma-ketlik generatorlaridir, ammo ular ba'zi nomaqbul tasodifiy xususiyatlarga ega. Ketma-ket bitlar chiziqli bo'lib, ularni shifrlash uchun foydasiz qiladi. LFSR uzunligi uchun n ichki holat oldingi holatni ifodalaydi n generatorning chiqish bitlari. Fikr-mulohaza namunasi sir saqlansa ham, uni aniqlash mumkin 2 n maxsus algoritmlar yordamida generatorning chiqish bitlari. Bundan tashqari, ushbu ketma-ketlikning ketma-ket bitlari yordamida yaratilgan katta tasodifiy sonlar yuqori darajada korrelyatsiya qilinadi va ba'zi turdagi ilovalar uchun tasodifiy emas. Shunga qaramay, LFSR ko'pincha shifrlash algoritmlarini yaratish uchun ishlatiladi. Shu maqsadda bir nechta LFSR ishlatiladi, odatda turli uzunliklar va musluklar tartib raqamlari. Kalit registrlarning dastlabki holatidir. Har safar yangi bit kerak bo'lganda, barcha registrlar o'zgartiriladi. Ushbu operatsiya deyiladi soatlash. Chiqish biti ba'zi LFSR bitlarining funksiyasi, yaxshisi chiziqli bo'lmagan. Bu funksiya deyiladi birlashtirish, va umuman generator - birlashtiruvchi generator. Ushbu generatorlarning aksariyati hali ham xavfsizdir.

Ta'lim va fan vazirligi

ROSSIYA DAVLAT IJTIMOIY UNIVERSITETI

AXBOROT TEXNOLOGIYASI FAKULTETI

AXBOROTNI HIMOYA QILISH BO'LIMI

Axborot xavfsizligini ta'minlashning kriptografik usullari va vositalari

Kurs ishi

“R psevdor tasodifiy sonlar generatorlari sifatida chiziqli fikrga ega siljish registrlari"

Bajarildi:

3-kurs talabasi

guruh KZOI-D-3

Larionov I.P.

Tekshirildi:

Dots. Baranova E.K.

Moskva 2011 yil
MAZMUNI

Kirish ……………………………..…………………………………….3

1. Ishning nazariy asoslari…………………………………………4
   1. Teskari aloqani o'zgartirish registrlari haqida umumiy ma'lumot............4
      1. RgSsLOS asosidagi oqim shifrlari haqida……………….………10
      2. Yaratilgan psevdo-tasodifiy ketma-ketlikning chiziqli murakkabligi haqida RgCsLOC……………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………12
      3. Psevdo-tasodifiy raqamlarning hosil qilingan ketma-ketligining korrelyatsiya mustaqilligi to'g'risida PrCsLOC………..….13
      4. PrCsLOC psevdotasodifiy raqamlarning hosil qilingan ketma-ketligini ochishning boshqa usullari haqida……………………………………………………..14
2. PrCsLOS ning psevdo-tasodifiy ketma-ketlik generatori sifatida dasturiy ta'minoti….…………………………….15
   1. Algoritmning umumlashtirilgan diagrammasi………………………………15
   2. Dasturiy ta'minot modullari va interfeysining tavsifi.……………….16
   3. Foydalanuvchi ko'rsatmalari…………………………………………20

Xulosa ………………………………………………………………22

Adabiyotlar ro'yxati………………………………………………….....23

Ilova A ….………………………………………………………..24

KIRISH

Ushbu ishning maqsadi teskari aloqa bilan siljish registrlari yordamida psevdor tasodifiy sonlar generatorining ishlashini amalga oshiradigan dasturiy ta'minotni ishlab chiqishdir. Grafik interfeysga ega ushbu ilovani ishlab chiqish tilda amalga oshiriladi Windows OS uchun C++.

Yigirmanchi asrda kriptografiyaning rivojlanishi bilan kriptograflar oldida xabarlarni tez va ishonchli shifrlash va shifrlash imkonini beruvchi shifrlash qurilmalari va mashinalarini yaratish vazifasi turardi. O'sha paytda allaqachon ochilgan simmetrik shifrlash tizimlari bu talabga javob berdi, ammo ularning zaif tomoni kalitga kuchli bog'liqlik va uning maxfiyligi edi. Buning uchun ishlatilishi mumkin bo'lgan eng qulay shifrlar sinfi gamma shifrlardir. Muammo xabarni parolini ochishda aniqlanmaydigan gamma hosil qilishda paydo bo'ldi. Nazariy jihatdan, agar har safar gamma tasodifiy bo'lsa va vaqt o'tishi bilan o'zgarib tursa, bu mumkin edi. Biroq, butunlay tasodifiy o'zgaruvchan gammadan foydalanganda, xabarning ishonchli shifrlanishi va shifrlanishini ta'minlash qiyin bo'ladi. Kriptograflar ushbu muammoni hal qilishga kirishdilar, uning maqsadi ma'lum bir qoida bo'yicha tasodifiy gamma yaratishni amalga oshiradigan algoritmni topish edi, bunday ketma-ketlikda "go'yo" tasodifiy pozitsiyalarda nollar va birlar bo'lishi kerak; va nollar taxminan bir xil bo'lishi kerak. Bu tasodifiy ketma-ketlik chaqirildisoxta tasodifiy,chunki u tasodifiy emas, balki ma'lum bir qoidaga muvofiq yaratilgan.

Tez orada yechim topildi. Shifrlash registrlarining xususiyatlarini o'rganish, qayta aloqa almashinuvi registrlari ichki tuzilishiga ko'ra shifrni ochishga etarlicha chidamli bo'lgan psevdo-tasodifiy ketma-ketliklarni yaratishga qodir ekanligini aniqlashga imkon berdi.

1.Mehnatning nazariy asoslari

1.1.Chiziqli aloqaga ega siljish registrlari haqida umumiy ma'lumot

Shift registrlari ketma-ketligi kriptografiyada ham, kodlash nazariyasida ham qo'llaniladi. Ularning nazariyasi yaxshi rivojlangan, smenali registrga asoslangan oqim shifrlari elektronika paydo bo'lishidan ancha oldin harbiy kriptografiyaning ish kuchi edi.

Yopiq tsiklli siljish registri (bundan buyon matnda RGSSOC deb yuritiladi) ikki qismdan iborat: siljish registrlari va qayta aloqa funksiyasi.Shishish registri - bu bitlar ketma-ketligi. Bitlar soni aniqlanadisiljish registrining uzunligi, agar uzunlik n bit bo'lsa, u holda registr chaqiriladin-bitli siljish registri. Bitni olish kerak bo'lganda, siljish registridagi barcha bitlar 1 pozitsiyaga o'ngga siljiydi. Yangi eng chap bit registrdagi barcha boshqa bitlarning funktsiyasidir. Shift registrining chiqishi bitta, odatda eng kam ahamiyatli bitdir.Shiftni ro'yxatga olish davri- natijada olingan ketma-ketlikning takrorlanishi boshlanishidan oldingi uzunligi.

Shakl Shift Fikr bilan ro'yxatdan o'ting

Shift registrlari tezda oqim shifrlarida foydalanishni topdi, chunki ular raqamli apparat yordamida osonlik bilan amalga oshirildi. 1965 yilda Norvegiya hukumatining bosh kriptografi Ernst Selmer siljish registrlari ketma-ketligi nazariyasini ishlab chiqdi. NSA matematiki Solomon Golomb o'zining va Selmerning ba'zi natijalarini taqdim etgan kitob yozdi. Teskari aloqani almashtirish registrining eng oddiy turichiziqli fikr almashish registr ( chiziqli fikr almashish registrlari, bundan keyin LFSR yoki RgSsLOS) . Bunday registrlarning fikr-mulohazalari shunchaki ba'zi registr bitlarining XOR (modul ikki qo'shilishi), bu bitlarning ro'yxati tegish ketma-ketligi deb ataladi. Ba'zan bunday registr Fibbonachchi konfiguratsiyasi deb ataladi. Teskari aloqa ketma-ketligining soddaligi tufayli PrCsVOCni tahlil qilish uchun ancha rivojlangan matematik nazariyadan foydalanish mumkin. Olingan chiqish ketma-ketliklarini tahlil qilib, ketma-ketliklar xavfsiz bo'lish uchun tasodifiy ekanligini tekshirishingiz mumkin. RGCCLOS kriptografiyada boshqa siljish registrlariga qaraganda tez-tez ishlatiladi.

PrCsLOS Fibbonachchi rasmi

Umuman olganda, n -bit PrCsLOS birida bo'lishi mumkin N=2n -1 ta ichki holat. Bu shuni anglatadiki, nazariy jihatdan bunday registr T=2 davriga ega psevdotasodifiy ketma-ketlikni hosil qilishi mumkin. n -1 bit. (Ichki holatlar soni va davr tengdir N = T max =2 n -1, chunki PrCcLOS-ni nol bilan to'ldirish siljish registrida nollarning cheksiz ketma-ketligini hosil qiladi, bu mutlaqo foydasiz). Faqat ma'lum bir tarmoqli ketma-ketliklar uchun PrCsLOS tsiklik ravishda barcha 2 orqali o'tadi n -1 ichki holatlar, bunday PrCsLOSMaksimal davr bilan RgSsLOS. Olingan natija chaqiriladiM-ketma-ket.

Misol . Quyidagi rasmda birinchi va to'rtinchi bitlar bosilgan 4 bitli PrCCLOS ko'rsatilgan. Agar u 1111 qiymati bilan ishga tushirilsa, registrni takrorlashdan oldin quyidagi ichki holatlar olinadi:

Shift soat raqami (ichki holat)	Ro'yxatdan o'tish holati				Chiqish biti
Dastlabki qiymat
15 (dastlabki holatga qaytish)
16 (takroriy holatlar)

Chiqish ketma-ketligi eng kam ahamiyatli bitlar qatori bo'ladi: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 davri T=15, mumkin bo'lgan ichki holatlarning umumiy soni (noldan tashqari), N =2 4 -1=16-1=15= T max , shuning uchun chiqish ketma-ketligi M -quyi ketma-ketlik.

Muayyan PrCsLOS maksimal davrga ega bo'lishi uchun teginish ketma-ketligi va doimiy 1 dan hosil bo'lgan polinom ibtidoiy modul 2 bo'lishi kerak. Polinom darajalar yig'indisi sifatida ifodalanadi, masalan, darajali polinom n quyidagicha ko'rinadi:

a n x n +a n-1 x n-1 +…+a 1 x 1 +a 0 x 0 =a n x n +a n-1 x n-1 +…+a 1 x+a 0 , bu yerda a i =(0, 1) ) i=1…n uchun a x i raqamni bildiradi.

Ko'phadning darajasi - siljish registrining uzunligi. n darajali ibtidoiy ko'phad x ning bo'luvchisi bo'lgan qaytarilmas ko'phaddir. 2n−1 +1, lekin x ning bo'luvchisi emas d 2 ga bo'luvchi barcha d uchun +1 n -1. Tegishli matematik nazariyani topish mumkin.

Umuman olganda, berilgan daraja modulining ibtidoiy ko'phadlarini yaratishning oson yo'li yo'q. Eng oson yo'li ko'phadni tasodifiy tanlash va uning ibtidoiy ekanligini tekshirishdir. Bu oson emas va tasodifiy tanlangan son tub ekanligini tekshirishga o'xshaydi - lekin ko'plab matematik dasturiy paketlar bu muammoni hal qilishi mumkin.

Ba'zi, lekin barchasi emas, ibtidoiy modul 2 bo'lgan turli darajadagi polinomlar quyida keltirilgan. Masalan, yozib oling

(32, 7, 5, 3, 2, 1, 0) quyidagi koʻphadning ibtidoiy modul 2 ekanligini bildiradi: x 32 + x 7 + x 5 + x 3 + x 2 + x + 1.

Buni maksimal muddat bilan PrCsVOC ga osongina umumlashtirish mumkin. Birinchi raqam PrCsLOS uzunligi. Oxirgi raqam har doim 0 bo'ladi va uni o'tkazib yuborish mumkin. 0 dan tashqari barcha raqamlar siljish registrining chap chetidan hisoblangan bosish ketma-ketligini bildiradi. Ya'ni, pastki darajali ko'phadning hadlari registrning o'ng chetiga yaqinroq pozitsiyalarga mos keladi.

Misolni davom ettiradigan bo'lsak, yozish (32, 7, 5, 3, 2, 1, 0) ma'lum 32 bitli siljish registrida o'ttiz ikkinchi, ettinchi, beshinchi, uchinchi, XORlash orqali yangi bit hosil bo'lishini anglatadi. ikkinchi va birinchi bitlar natijasida hosil bo'lgan PrCsLOS maksimal uzunlikka ega bo'ladi, 2 dan o'tadi. 32 -1 qiymatlari.

4-rasm Maksimal uzunlikka ega 32-bitli PrCsLOC

Keling, PrCsLOS dastur kodini ko'rib chiqaylik, unda tegishlar ketma-ketligi ko'phad (32, 7, 5, 3, 2, 1, 0) bilan tavsiflanadi. C da bu shunday ko'rinadi:

int LFSR() (

statik imzosiz uzun ShiftRegister = 1;

/* 0 dan tashqari hamma narsa. */

ShiftRegister = ((((ShiftRegister >> 31)

^(ShiftRegister >> 6)

^(ShiftRegister >> 4)

^(ShiftRegister >> 2)

^(ShiftRegister >> 1)

^ShiftRegister))

& 0x00000001)

<<31)

| (ShiftRegister >> 1);

ShiftRegisterni qaytaring & 0 x 00000001;)

Shift registri kompyuter so'zidan uzunroq bo'lsa, kod yanada murakkablashadi, lekin unchalik emas. Ilovada B ba'zi bir ibtidoiy ko'phadlar jadvali 2 moduli berilgan, biz kelajakda bu ko'phadlarning ba'zi xususiyatlarini aniqlash uchun, shuningdek, teginish ketma-ketligini belgilash uchun dasturiy ta'minotni amalga oshirishda foydalanamiz;

Jadvalning barcha elementlari toq sonli koeffitsientlarga ega ekanligini unutmang. Ushbu uzun jadval RgCsLOC bilan keyingi ishlash uchun taqdim etiladi, chunki RgCsLOC ko'pincha oqim shifrlari bilan kriptografiya uchun va psevdo-tasodifiy raqamlar generatorlarida ishlatiladi. Bizning holatlarimizda biz eng yuqori darajasi yettidan oshmaydigan ko'phadlardan foydalanishimiz mumkin.

Agar p(x) ibtidoiy bo'lsa, x ham xuddi shunday n p (1/x), shuning uchun jadvalning har bir elementi aslida ikkita ibtidoiy polinomni belgilaydi. Misol uchun, agar (a, b, 0) ibtidoiy bo'lsa, u holda (a, a-b, 0) ham tubdir. Agar (a, b, c, d, 0) ibtidoiy bo‘lsa, (a, a-d, a-c, a-b, 0) ham tub bo‘ladi. Matematik jihatdan:

agar x ibtidoiy bo'lsa a +x b +1, u holda x ham ibtidoiy a +x a-b +1,

agar x ibtidoiy bo'lsa a +x b +x c +x d +1, u holda x ham ibtidoiy a +x a-d +x a-c +x a-b +1. Ibtidoiy trinomiallar dasturiy ta'minotda eng tez amalga oshiriladi, chunki yangi bit yaratish uchun siz siljish registrining faqat ikkita bitini XOR qilishingiz kerak (nol atama hisobga olinmaydi, ya'ni x. 0 =1, yuqoridagi misolga qarang). Darhaqiqat, jadvalda keltirilgan barcha qayta aloqa polinomlari siyrak, ya'ni ular kam koeffitsientga ega. Siqilish har doim zaiflik manbai bo'lib, ba'zida algoritmni buzish uchun etarli. Kriptografik algoritmlar uchun koeffitsientlari ko'p bo'lgan zich ibtidoiy polinomlardan foydalanish ancha yaxshi. Ayniqsa kalitning bir qismi sifatida zich polinomlardan foydalangan holda, ancha qisqaroq PrCsLOS dan foydalanish mumkin.

Modul 2 zich ibtidoiy polinomlarni yaratish oson emas. Umuman olganda, k darajali ibtidoiy ko'phadlarni yaratish uchun siz 2 raqamini faktorizatsiya qilishni bilishingiz kerak. k -1.

O'z-o'zidan, PrCsLOS psevdo-tasodifiy ketma-ketliklarning yaxshi generatorlari, ammo ular ba'zi bir nomaqbul tasodifiy (deterministik) xususiyatlarga ega. Ketma-ket bitlar chiziqli bo'lib, ularni shifrlash uchun foydasiz qiladi. n uzunlikdagi PrCcLOS uchun ichki holat generatorning oldingi n chiqish bitidir. Teskari aloqa zanjiri sir saqlansa ham, uni yuqori samarali Berlekamp-Massey algoritmi yordamida osilatorning 2n chiqish bitlaridan aniqlash mumkin.

Bundan tashqari, ushbu ketma-ketlikning ketma-ket bitlari yordamida yaratilgan katta tasodifiy sonlar yuqori darajada korrelyatsiya qilinadi va ba'zi turdagi ilovalar uchun umuman tasodifiy emas. Shunga qaramay, RgCCLOS ko'pincha tizimlar va shifrlash algoritmlari komponentlari sifatida shifrlash algoritmlarini yaratish uchun ishlatiladi.

1.2.PrSSLOS asosidagi oqim shifrlari haqida

RgSSLOS asosida asosiy oqim generatorini loyihalashning asosiy yondashuvi oddiy. Birinchidan, bir yoki bir nechta PrCsLOS olinadi, odatda turli uzunliklar va turli xil qayta aloqa polinomlari bilan. (Agar uzunliklar koʻp boʻlsa va barcha qayta aloqa koʻphadlari primitiv boʻlsa, hosil boʻlgan generator maksimal uzunlikka ega boʻladi.) Kalit PrCcLOS registrlarining boshlangʻich holati hisoblanadi. Har safar yangi bit kerak bo'lganda, PrCCLOC registrlarini bir oz o'zgartiring (bu ba'zan soat deb ataladi). Chiqish biti PrCsLOS registrlarining ba'zi bitlarining funksiyasi, afzalroq chiziqli bo'lmagan. Bu funksiya birlashtiruvchi funksiya deb ataladi va generator bir butun sifatida kombinatsiyalangan generator deb ataladi. (Agar chiqish biti bitta PrCCLOS funktsiyasi bo'lsa, u holda osilator filtrli osilator deb ataladi.) Ushbu turdagi qurilmalar uchun nazariyaning katta qismi Selmer va Neal Zierler tomonidan ishlab chiqilgan. Bir qator asoratlarni kiritish mumkin. Ba'zi osilatorlar turli xil RgSsLOS uchun turli xil soat chastotalaridan foydalanadilar, ba'zan bir osilatorning chastotasi boshqasining chiqishiga bog'liq. Bularning barchasi Ikkinchi jahon urushi oldidan soat bilan boshqariladigan osilatorlar deb ataladigan shifrlash mashinasi g'oyalarining elektron versiyalari ( soat bilan boshqariladigan generatorlar ). Soatni boshqarish oldinga yo'naltirilgan bo'lishi mumkin, bu erda bitta PrCcLOC chiqishi boshqa PrCcLOC ning takt chastotasini boshqaradi yoki bir PrCcLOC chiqishi o'z takt chastotasini boshqaradi. Garchi bu generatorlarning barchasi, hech bo'lmaganda, nazariy jihatdan, uyalar va mumkin bo'lgan korrelyatsiya orqali hujumlarga moyil bo'lsa-da, ularning aksariyati hali ham xavfsizdir.

Ilgari Kembrijdagi sof matematikaning rahbari va Bletchly Parkning kriptoanalitiki Ian Kassels "kriptografiya matematika va chalkashlikning aralashmasidir va chalkashliksiz matematika sizga qarshi ishlatilishi mumkin", dedi. U oqim shifrlarida maksimal uzunlik va boshqa xususiyatlarni ta'minlash uchun PrCcLOS kabi ba'zi matematik tuzilmalar kerak, ammo kimdir registr mazmunini olishiga va algoritmni buzishiga yo'l qo'ymaslik uchun ba'zi bir murakkab chiziqli bo'lmagan tartibsizlikni joriy qilish kerakligini nazarda tutgan edi. Ushbu maslahat blokirovka algoritmlariga ham tegishli.

Aksariyat real oqim shifrlari PrCsLOS-ga asoslangan. Hatto elektronikaning dastlabki kunlarida ham ularni qurish qiyin emas edi. Shift registri bitlar massividan boshqa narsa emas va qayta aloqa ketma-ketligi XOR eshiklari to'plamidir. VLSI dan foydalanganda ham, PrCsLOC-ga asoslangan oqim shifrlash bir nechta mantiqiy eshiklar yordamida sezilarli xavfsizlikni ta'minlaydi. PrSSLOS bilan bog'liq muammo shundaki, ularning dasturiy ta'minoti juda samarasiz. Siz siyrak qayta aloqa polinomlaridan qochishingiz kerak - ular korrelyatsiya hujumlarini osonlashtiradi - va zich qayta aloqa polinomlari samarasiz.

Kriptografiyaning ushbu tarmog'i jadal rivojlanmoqda va hukumat nazorati ostida N.S.A. . Ishlanmalarning aksariyati tasniflangan - bugungi kunda ishlatiladigan ko'plab harbiy shifrlash tizimlari RgSSLOS-ga asoslangan. Haqiqatan ham, ko'pchilik Cray kompyuterlari (Cray 1, Cray X-MP, Cray Y-MP) juda qiziqarli ko'rsatmaga ega, odatda "aholi soni" deb ataladi. U registrdagi birlar sonini hisoblaydi va ikkala ikkilik so'zlar orasidagi Hamming masofasini samarali hisoblash va PrCcLOS ning vektorlashtirilgan versiyasini amalga oshirish uchun ishlatilishi mumkin. Ushbu ko'rsatma NSAning kanonik ko'rsatmasi hisoblanadi va kompyuterlar bilan bog'liq deyarli barcha shartnomalarda ko'rsatilishi kerak.

Boshqa tomondan, hayratlanarli darajada murakkab ko'rinadigan siljish registrlari generatorlari buzilgan. Va, albatta, NSA kabi harbiy kriptoanalitik agentliklar tomonidan buzilgan bunday generatorlar soni yanada ko'proq.

1.3.Psevdotasodifiy sonlarning hosil qilingan ketma-ketligining chiziqli murakkabligi to'g'risida PrCsLOC

Oqim shifrlarini tahlil qilish odatda blokli shifrlarga qaraganda osonroq. Masalan, PrCsLOS asosida generatorlarni tahlil qilish uchun ishlatiladigan muhim parametr chiziqli murakkablik yoki chiziqli intervaldir. Bu generatorning chiqishini simulyatsiya qila oladigan eng qisqa PrCsLOS uzunligi n sifatida aniqlanadi. Cheklangan maydonda chekli avtomat tomonidan yaratilgan har qanday ketma-ketlik chekli chiziqli murakkablikka ega. Chiziqli murakkablik muhim, chunki Berlekamp-Massey algoritmi deb ataladigan oddiy algoritmdan foydalanib, kalit oqimining faqat 2n bitini tekshirish orqali ushbu PrCcLOSni aniqlash mumkin. Kerakli PrCsLOSni qayta yaratish orqali siz oqim shifrini buzasiz.

Ushbu g'oya maydonlardan halqalarga va chiqish ketma-ketligi g'alati xarakterli sohadagi raqamlar sifatida ko'rib chiqiladigan holatlarga qadar kengaytirilishi mumkin. Keyingi kengaytma chiziqli murakkablik profili kontseptsiyasining kiritilishiga olib keladi, bu esa ketma-ketlikning chiziqli murakkabligini uning uzaytirilishi bilan belgilaydi. Sferik va kvadratik murakkablik tushunchalari ham mavjud. Qanday bo'lmasin, esda tutingki, yuqori chiziqli murakkablik generatorning xavfsizligini kafolatlamaydi, lekin past chiziqli murakkablik generatorning etarlicha xavfsiz emasligini ko'rsatadi.

1.4.Psevdotasodifiy sonlarning hosil qilingan ketma-ketligining korrelyatsiya mustaqilligi to'g'risida PrCsLOS

Kriptograflar ba'zi chiqish ketma-ketliklarining natijalarini chiziqli bo'lmagan tarzda birlashtirib, yuqori chiziqli murakkablikni olishga harakat qilishadi. Bu erda xavf shundaki, bir yoki bir nechta ichki chiqish ketma-ketligi - ko'pincha individual PrCsLOS chiqishlari - umumiy kalit oqimi orqali ulanishi va chiziqli algebra yordamida ochilishi mumkin. Ushbu otopsiya ko'pincha korrelyatsiya otopsiyasi yoki bo'lin va bo'ysundiruvchi otopsiya deb ataladi. Tomas Siegenthaler korrelyatsiya mustaqilligini aniq belgilash mumkinligini va korrelyatsiya mustaqilligi va chiziqli murakkablik o'rtasida o'zaro bog'liqlik mavjudligini ko'rsatdi.

Korrelyatsiya hujumining asosiy g'oyasi generatorning chiqishi va uning tarkibiy qismlaridan birining chiqishi o'rtasidagi bog'liqlikni aniqlashdir. Keyin chiqish ketma-ketligini kuzatish orqali ushbu oraliq chiqish haqida ma'lumot olish mumkin. Ushbu ma'lumotlardan va boshqa korrelyatsiyalardan foydalanib, generatorning buzilishiga qadar boshqa oraliq chiqishlar bo'yicha ma'lumotlar to'planishi mumkin.

Korrelyatsiya hujumlari va ularning o'zgarishi, masalan, tezkor korrelyatsiya hujumlari, hisoblash murakkabligi va samaradorlik o'rtasidagi muvozanatni taklif qiladi, ko'plab PrCsLOS-ga asoslangan kalit oqimi generatorlariga qarshi muvaffaqiyatli qo'llanilgan.

1.5. PrCsLOS soxta tasodifiy sonlarning hosil qilingan ketma-ketligini ochishning boshqa usullari haqida

Keystream generatorlarini buzishning boshqa usullari mavjud. Chiziqli mustahkamlik testi matritsa texnikasidan foydalangan holda shifrlash kalitining kichik to'plamini topishga harakat qiladi. Bundan tashqari, "o'rtada uchrashadigan mustahkamlik hujumi" mavjud. Chiziqli sindrom algoritmi chiqish ketma-ketligining bir qismini chiziqli tenglama shaklida yozish qobiliyatiga asoslangan. Eng yaxshi affin yaqinlashish hujumi va olingan ketma-ketlik hujumi mavjud. Oqimli shifrlarga differensial va chiziqli kriptoanaliz usullari ham qo'llanilishi mumkin.

2. Psevdo-tasodifiy ketma-ketlik generatori sifatida PrCsLOS dasturini amalga oshirish tavsifi

2.1.Algoritmning umumlashtirilgan sxemasi

2.2.Dasturiy ta'minot modullari va interfeysining tavsifi

Quyidagi 3-rasmda dastur oynasi ko'rsatilgan.

Shakl dasturi interfeysi

Menyuda quyidagi funktsiyalar mavjud:

• Fayl-> Hisobotni saqlash

Bu funksiya PrCsLOS ning dastlabki holatini, teginish ketma-ketligini, qabul qilingan psevdo-tasodifiy bit ketma-ketligi davrini, ketma-ketlikning o'zi va holat jadvalini qayd qiluvchi hisobot faylini yaratadi. Agar fayl muvaffaqiyatli saqlangan bo'lsa, muvaffaqiyatli saqlanganligini bildiruvchi xabar ko'rsatiladi (4-rasm). Tavsiya etilgan hisobot fayl kengaytmasi *. Xabar.

Chizma

• Fayl->Chiqish

Bu xususiyat ilovaning yopilishini ta'minlaydi.

• Tegishlar ketma-ketligini o'rnating

Ushbu funktsiya foydalanuvchi ekran formasida belgilagan katakchalardagi qiymatlarni o'qish orqali tegishlar ketma-ketligini hosil qiladi. Shundan so'ng u foydalanuvchiga teginish ketma-ketligini yaratish haqida xabar beradi (5-rasm). Tegishlar ketma-ketligi qaysi siljish registrining flip-floplari fikr-mulohazalarni taqdim etishini aniqlaydi. XOR ofset bitini yaratish uchun. Odatiy bo'lib, birinchi triggerdan qayta aloqa har doim boshqa ulanishlar bo'lmaganda o'rnatiladi, past tartibli bit yuqori darajali holatga o'tishi bilan chapga siljish amalga oshiriladi;

Chizma

• Dastlabki qiymatni o'rnating

Bu funksiya foydalanuvchi tomonidan taqdim etilgan dastlabki registr qiymatini oynadan o'qiydi Tahrirlash 1 va kiritilgan qiymatni belgilangan shartlarga muvofiq tekshiradi: kiritilgan satr bo'sh emas (6-rasm), kiritilgan satr sakkizta uzunlikka ega (8bit=1 bayt, 7-rasm), kiritilgan satrda faqat nol va/yoki birlar (8-rasm), kiritilgan qator nolga teng emas (9-rasm). Aks holda, xato xabarlari ko'rsatiladi, foydalanuvchi ularni tuzatishi va tugmani yana bosishi kerak. Agar tekshirish muvaffaqiyatli bo'lsa, "Boshlang'ich" qatoridagi holat jadvaliga dastlabki qiymat yoziladi va bildirishnoma beriladi (10-rasm).

Chizma

Chizma

Chizma

Chizma

Chizma

• Shift qutisi

Bu funksiya siljish registrining ishlashiga taqlid qiladi. 256 ta siljishni ketma-ket bajarish orqali har bir siljish psevdo-tasodifiy ketma-ketlik chiqish bitini va yangi registr holatini hosil qiladi. Registr holati dastlabki holatga teng bo'lishi bilan vaqt hisoblab chiqiladi va maydonda ko'rsatiladi Eslatma 1 ta psevdor tasodifiy ketma-ketlik.

• Yordam->Dastur haqida

Bu funksiya dastur va ko'rsatmalarning qisqacha tavsifini ko'rsatadi (11-rasm).

Chizma

• Yordam->Muallif haqida

Bu funksiya dastur muallifi haqidagi ma'lumotlarni ko'rsatadi (12-rasm).

Chizma

2.3.Foydalanuvchi ko'rsatmalari

1. Avval registrni dastlabki holatiga o'rnating. U sakkizta ikkilik belgilarni o'z ichiga olishi kerak. Aks holda, xato xabari ko'rsatiladi va siz kiritilgan qiymatni tuzatishingiz kerak bo'ladi. "Boshlang'ich qiymatni o'rnatish" menyu bandini bosing.
2. Keyin ro'yxatga olish bo'yicha fikr-mulohazalar uchun katakchalarni belgilang (ketma-ket teging). "Tekishlar ketma-ketligini o'rnatish" menyu bandini bosing.
3. Keyin, "Case Shift" menyu bandini bosing. Buni amalga oshirishdan oldin, 1 va 2-bosqichlarni bajarganingizga ishonch hosil qiling, aks holda dasturiy ta'minot xatosi yuzaga keladi.
4. Natijalarni olganingizdan so'ng, ularni "Fayl-> Hisobotni saqlash" menyusini bosish orqali saqlashingiz mumkin. Buni amalga oshirishdan oldin, 1-3-bosqichlarni bajarganingizga ishonch hosil qiling, aks holda dasturiy ta'minot xatosi yuzaga keladi.
5. Yordam olish uchun “Fayl->Dastur haqida”, “Fayl->Muallif haqida” menyu bandlarini bosing.
6. Registrning ishlashini teginish ketma-ketligining boshqa qiymatlari va registrning boshlang'ich holati bilan ko'rish uchun boshqa parametrlarni kiritib, 1-3-bosqichlardagi amallarni takrorlang.

XULOSA

Ushbu ishda PrCsLOS psevdor tasodifiy sonlar generatorlari sifatida ko'rib chiqildi. Dastur chiziqli teskari aloqa bilan siljish registrlarining ishlash tamoyillarining vizual namoyishi bo'lib xizmat qilishi mumkin XOR . Unda siz bitlarning psevdo-tasodifiy ketma-ketligini shakllantirish printsipini, registrning boshlang'ich qiymati va psevdo-tasodifiy ketma-ketlikning qiymati, teginish ketma-ketligi va davr o'rtasidagi munosabatni o'rganishingiz mumkin. Olingan psevdo-tasodifiy gamma boshqa dasturiy ta'minot ilovasida (masalan, gamma-shifrning dasturiy ta'minoti) ishlatilishi mumkin.

Ayni paytda bu registrlar psevdo-tasodifiy raqamlarning mustaqil generatorlari sifatida ishlatilmaydi, balki murakkabroq qurilmalarning bir qismidir. Biroq, ular matematikada yangi yo'nalishlarni ochdilar (cheklangan sohalarda ibtidoiy ko'phadlarni qidirish, psevdo tasodifiy sonlar generatorlarini buzishning matematik usullari). PrSSLOS-ga asoslangan generatorlarning ishlash tamoyillarini bilmasdan, murakkabroq qurilmalarning ishlashini tushunish mumkin emas. Oddiy apparat ta'minoti tufayli ular texnologiyada keng qo'llaniladi. RgCCOS tadqiqotlari ushbu turdagi registrlar (harakatlanuvchi almashtirish shifrlari, DES va h.k.; EDS, xesh funktsiyalari).

Umuman olganda, ushbu sohadagi tadqiqotlar kriptografiya va kriptoanalitika, kompyuterlar va qurilmalarning rivojlanishiga jiddiy turtki berdi, shuningdek, bir qator boshqa foydali funktsiyalarni (masalan, tsiklik kodlarni tuzatish) amalga oshirishga imkon berdi.

ADABIYOTLAR RO'YXATI

1. Shnayer Bryus. Amaliy kriptografiya. Si tilidagi protokollar, algoritmlar, manba matnlar. M.: Triumf, 2002 yil
2. Babash A.V. Zamonaviy axborot xavfsizligining kriptografik va avtomat-nazariy jihatlari. 1-jild M.: nashriyot uyi. EAOI markazi, 2009. 414 b.
3. E.S. Selmer. Monografiya: “Cheklangan sohada chiziqli rekursiya”. Bergen universiteti, Norvegiya, 1966 yil.
4. N. Zierler va J. Brillhart. "Ibtidoiy trinomiallar haqida 2", "Axborot va nazorat" jurnali, 13-jild № 6 dekabr 1968 yil, 541-544-betlar.
5. K.H. Meyer va V. L. Tuchman. "Pseudo-tasodifiy kodlarni buzish mumkin", Elektron Dizayn jurnali, №. 1972 yil 23 noyabr.
6. J. L. Massey. "Smena registrlarini umumlashtirish va Bose-Chowdhury-Hocquenghem kodini dekodlash", Axborot nazariyasi bo'yicha IEEE operatsiyalari, v. IT-15, n . 1 yanvar 1969 yil, 122-127-betlar.
7. S.U. Golomb. Shift Register Sequences, San-Fransisko, Oltin kun, 1967 (Aigean Park Press tomonidan qayta nashr etilgan, 1982).

Ilova A

Ba'zi ibtidoiy polinomlar jadvali moduli 2

(1, 0)

(2, 1, 0)

(3, 1, 0)

(4, 1, 0)

(5, 2, 0)

(6, 1, 0)

(7, 1, 0)

(7, 3, 0)

(8, 4, 3, 2, 0)

(9, 4, 0)

(10, 3, 0)

(11, 2, 0)

(12, 6, 4, 1, 0)

(13, 4, 3, 1, 0)

(14, 5, 3, 1, 0)

(15, 1, 0)

(16, 5, 3.2, 0)

(17, 3, 0)

(17, 5, 0)

(17, 6, 0)

(18, 7, 0)

(18, 5, 2, 1, 0)

(19, 5, 2, 1, 0)

(20, 3, 0)

(21, 2, 0)

(22, 1, 0)

(23, 5, 0)

(24, 4, 3, 1, 0)
(25, 3, 0)

(26, 6, 2, 1, 0)

(27, 5, 2, 1, 0)

(28, 3, 0)

(29, 2, 0)

(30, 6, 4, 1.0)

(31, 3, 0)

(31, 6, 0)

(31, 7, 0)

(31, 13, 0)

(32, 7, 6, 2, 0)

(32, 7, 5, 3, 2, 1, 0)

(33, 13, 0)

(33, 16, 4, 1, 0)

(34, 8, 4, 3, 0)

(34, 7, 6, 5, 2, 1, 0)

(35, 2, 0)

(135, 11, 0)

(135, 16, 0)

(135, 22, 0)

(136, 8, 3, 2, 0)

(137, 21, 0)

(138, 8, 7, 1, 0)

(139, 8, 5, 3, 0)

(140, 29, 0)

(141, 13, 6, 1, 0)

(142, 21, 0)

(143, 5, 3, 2, 0)

(144, 7, 4, 2, 0)

(145, 52, 0)

(145, 69, 0)

(146, 5, 3, 2, 0)

(147, 11, 4, 2, 0)

(148, 27, 0)

(149, 10, 9, 7, 0)

(150, 53, 0)

(151, 3, 0)

(151, 9, 0)

(151, 15, 0)

(151, 31, 0)

(151, 39, 0)

(151, 43, 0)

(151, 46, 0)

(151, 51, 0)

(151, 63, 0)

(151, 66, 0)

(151, 67, 0)

(151, 70, 0)

(36, 11, 0)

(36, 6, 5, 4, 2, 1, 0)

(37, 6, 4, 1, 0)

(37, 5, 4, 3, 2, 1, 0)

(38, 6, 5, 1, 0)

(39, 4, 0)

(40, 5, 4, 3, 0)

(41, 3, 0)

(42, 7, 4, 3, 0)

(42, 5, 4, 3, 2, 1, 0)

(43, 6, 4, 3, 0)

(44, 6, 5, 2, 0)

(45, 4, 3, 1, 0)

(46, 8, 7, 6, 0)

(46, 8, 5, 3, 2, 1, 0)

(47, 5, 0)

(48, 9, 7, 4, 0)

(48, 7, 5, 4, 2, 1, 0)

(49, 9, 0)

(49, 6, 5, 4, 0)

(50, 4, 3, 2, 0)

(51, 6, 3, 1, 0)

(52, 3, 0)

(53, 6, 2, 1, 0)

(54, 8, 6, 3, 0)

(54, 6, 5, 4, 3, 2, 0)

(55, 24, 0)

(55, 6, 2, 1, 0)

(56, 7, 4, 2, 0)

(57, 7, 0)

(57, 5, 3, 2, 0)

(58, 19.0)

(58, 6, 5, 1, 0)

(59, 7, 4, 2, 0)

(59, 6, 5, 4, 3, 1, 0)

(60, 1, 0)

(61, 5, 2, 1, 0)

(62, 6, 5, 3, 0)

(63, 1, 0)

(64, 4, 3, 1, 0)

(65, 18, 0)

(65, 4, 3, 1, 0)

(66, 9, 8, 6, 0)

(66, 8, 6, 5, 3, 2, 0)

(67, 5, 2, 1, 0)

(152, 6, 3, 2, 0)

(153, 1, 0)

(153, 8, 0)

(154, 9, 5, 1, 0)

(155, 7, 5, 4, 0)

(156, 9, 5, 3, 0)

(157, 6, 5, 2, 0)

(158, 8, 6, 5, 0)

(159, 31, 0)

(159, 34, 0)

(159, 40, 0)

(160, 5, 3, 2, 0)

(161, 18, 0)

(161, 39, 0)

(161, 60, 0)

(162, 8, 7, 4, 0)

(163, 7, 6, 3, 0)

(164, 12, 6, 5, 0)

(165, 9, 8, 3, 0)

(166, 10, 3, 2, 0)

(167, 6, 0)

(170, 23, 0)

(172, 2, 0)

(174, 13, 0)

(175, 6, 0)

(175, 16, 0)

(175, 18, 0)

(175, 57, 0)

(177, 8, 0)

(177, 22, 0)

(1 77, 88, 0)

(68, 9, 0)

(68, 7, 5, 1, 0)

(69, 6, 5, 2, 0)

(70, 5, 3, 1, 0)

(71, 6, 0)

(71, 5, 3, 1, 0)

(72, 10, 9, 3, 0)

(72, 6, 4, 3, 2, 1, 0)

(73, 25, 0)

(73, 4, 3, 2, 0)

(74, 7, 4, 3, 0)

(75, 6, 3, 1, 0)

(76, 5, 4, 2, 0)

(77, 6, 5, 2, 0)

(78, 7, 2, 1, 0)

(79, 9, 0)

(79, 4, 3, 2, 0)

(80, 9, 4, 2, 0)

(80, 7, 5, 3, 2, 1, 0)

(81, 4, 0)

(82, 9, 6, 4, 0)

(82, 8, 7, 6, 1, 0)

(83, 7, 4, 2, 0)

(84, 13, 0)

(84, 8, 7, 5, 3, 1, 0)

(85, 8, 2, 1, 0)

(86, 6, 5, 2, 0)

(87, 13, 0)

(87, 7, 5, 1, 0)

(88, 11, 9, 8, 0)

(88, 8, 5, 4, 3, 1, 0)

(89, 38, 0)

(89, 51, 0)

(89, 6, 5, 3, 0)

(90, 5, 3, 2, 0)

(91, 8, 5, 1, 0)

(91, 7, 6, 5, 3, 2, 0)

(92, 6, 5, 2, 0)

(93, 2, 0)

(94, 21, 0)

(94, 6, 5, 1, 0)

(95, 11, 0)

(95, 6, 5, 4, 2, 1, 0)

(96, 10, 9, 6, 0)

(96, 7, 6, 4, 3, 2, 0)

(178, 87, 0)

(183, 56, 0)

(194, 87, 0)

(198, 65, 0)

(201, 14, 0)

(201, 17, 0)

(201, 59, 0)

(201, 79, 0)

(202, 55, 0)

(207, 43, 0)

(212, 105, 0)

(218, 11, 0)

(218, 15, 0)

(218, 71, 0)

(218.83, 0)

(225, 32, 0)

(225, 74, 0)

(225, 88, 0)

(225, 97, 0)

(225, 109, 0)

(231, 26, 0)

(231, 34, 0)

(234, 31, 0)

(234, 103, 0)

(236, 5, 0)

(250, 103, 0)

(255, 52, 0)

(255, 56, 0)

(255, 82, 0)

(258, 83, 0)

(266, 47, 0)

(97, 6, 0)

(98, 11, 0)

(98, 7, 4, 3, 1, 0)

(99, 7, 5, 4, 0)

(100, 37, 0)

(100, 8, 7, 2, 0)

(101, 7, 6, 1, 0)

(102, 6, 5, 3, 0)

(103, 9, 9)

(104, 11, 10, 1, 0)

(105, 16, 0)

(106, 15, 0)

(107, 9, 7, 4, 0)

(108, 31, 0)

(109, 5, 4, 2.0)

(110, 6, 4, 1, 0)

(111, 10, 0)

(111, 49, 0)

(113, 9, 0)

(113, 15, 0)

(113, 30, 0)

(114, 11, 2, 1, 0)

(115, 8, 7, 5, 0)

(116, 6, 5, 2, 0)

(117, 5, 2, 1, 0)

(118, 33, 0)

(119, 8, 0)

(119, 45, 0)

(120, 9, 6, 2, 0)

(121, 18, 0)

(122, 6, 2, 1, 0)

(123, 2, 0)

(124, 37, 0)

(125, 7, 6, 5, 0)

(126, 7, 4, 2, 0)

(127, 1, 0)

(127, 7, 0)

(127, 63, 0)

(128, 7, 2, 1, 0)

(129, 5, 0)

(130, 3, 0)

(131, 8, 3, 2, 0)

(132, 29, 0)

(133, 9, 8, 2, 0)

(134, 57, 0)

(270, 133, 0)

(282, 35, 0)

(282, 43, 0)
(286, 69, 0)

(286, 73, 0)

(294, 61, 0)

(322, 67, 0)

(333, 2, 0)

(350, 53, 0)

(366, 29, 0)

(378, 43, 0)

(378, 107, 0)

(390, 89, 0)

(462, 73, 0)

(521, 32, 0)

(521, 48, 0)

(521, 158, 0)

(521, 168, 0)

(607, 105, 0)

(607, 147, 0)

(607, 273, 0)

(1279, 216, 0)

(1279, 418, 0)

(2281, 715, 0)

(2281, 915, 0)

(2281, 1029, 0)

(3217, 67, 0)

(3217, 576, 0)

(4423, 271, 0)

(9689, 84, 0)

Dastlabki holatga kirish (IS)

kiritish to'g'riligini tekshirish

Xato xabarini chiqarish

Tegishlar ketma-ketligini sozlash

Shtat jadvalida ICni yozish

Yozuv i th registr holati va chiqish biti holat jadvaliga

IS==Hozirgi holat

Natijalarni saqlash

Pseudo-tasodifiy ketma-ketlik chiqishi

Chiqish

Ishga tushirish

Ha

Ha

Yo'q

Shift registrlari ketma-ketligi ko'pincha oqim shifrlarini yaratish uchun ishlatiladi. Teskari aloqani o'zgartirish registri ikki qismdan iborat: o'zgartirish registrlari va teskari aloqa funktsiyasi, rasmda ko'rsatilganidek. 87. O'zgartirish registrining o'zi bitlar ketma-ketligi bo'lib, ularning soni registr uzunligini belgilaydi. Demak, agar registrda n ta bit bo'lsa, u n-bitli siljish registr deyiladi. Har safar bit olinganda, siljish registridagi barcha bitlar bir pozitsiyaga o'ngga, odatda eng kam ahamiyatli bitlar tomon siljiydi. O'zgartirish registrlari davri - hosil bo'lgan ketma-ketlikning takrorlanishi boshlanishidan oldingi uzunligi.

Guruch. 87.

Bitlarda amalni bajaradigan har qanday matematik funktsiya qayta aloqa vazifasini bajarishi mumkin. Teskari aloqani o'zgartirish registrining eng oddiy turi chiziqli qayta aloqa siljish registridir (LFSR). RFLSda fikr-mulohaza shunchaki ba'zi registr bitlarida modul-2 qo'shish (XOR) amalidir; bu bitlarning ro'yxati rasmda ko'rsatilganidek, musluklar ketma-ketligi yoki qabul qilish nuqtalari deb ataladi. 88. Ba'zan bu naqsh Fibonachchi konfiguratsiyasi deb ataladi. Teskari aloqa ketma-ketligining soddaligi tufayli LFSRni tahlil qilish uchun etarlicha rivojlangan matematik nazariyadan foydalanish mumkin. Har qanday holatda, yaratilgan PSP sifati maxsus testlar to'plami yordamida baholanadi.

Guruch. 88.

SFLOlar polinomlar shaklida yoziladi. Bunday holda, ko'phadning birinchi elementining kuchi siljish registridagi bitlar sonini, ko'phadning qolgan a'zolarining quvvat ko'rsatkichlari esa qaysi tanlash nuqtalari ishlatilishini ko'rsatadi. Shunday qilib, masalan, x 4 + x + 1 yozuvi to'rtta elementdan iborat registrdan foydalanishni anglatadi, buning uchun bi va b 0 bitlari qayta aloqani shakllantirishda ishtirok etadi (89-rasm).

Guruch. 89.4

Keling, rasmda ko'rsatilgan registrning ishlashini ko'rib chiqaylik. 89. Biz uni, masalan, 0101 qiymati bilan ishga tushiramiz (dastlabki ishga tushirish har qanday bitlar ketma-ketligi bilan amalga oshirilishi mumkin, faqat nollar ketma-ketligidan tashqari, chunki bu holda teskari aloqa har doim nol qiymatini hosil qiladi va registr kutilgan tarmoqli kengligini yaratmaydi). Shunday qilib, registr bir pozitsiyaga o'ngga siljiydi. 1 ga teng bo'lgan eng kam ahamiyatli bit registrdan chiqarib tashlanadi va xotira o'tkazish qobiliyatining birinchi bitini tashkil qiladi. B va b 0 pozitsiyalarida bo'lgan bitlar siljishdan oldin modulga 2 qo'shiladi va yangi hosil qiladi

registrning eng muhim qismi. Ko'rib chiqilayotgan LFSR ishlashining aniq misoli rasmda ko'rsatilgan. 90.

Guruch. 90.

Shakldan ko'rinib turibdiki. 90, reestrni to'ldirish 16 ta mumkin bo'lgan holatlarning 15 tasining og'irligidan o'tadi (ilgari biz LFSR 0000 bo'lgan o'n oltinchi holatni ko'rib chiqish mumkin emasligini aniqlagan edik). Shundan so'ng, registrni to'ldirish yana 0101 boshlang'ich qiymatiga teng bo'ladi va bit ketma-ketligini yaratish takrorlana boshlaydi. Registrning chiqish ketma-ketligi eng kam ahamiyatli bitlar qatori bo'ladi (90-rasmdagi gorizontal chiziqgacha): 101011110001001. Bitlar ketma-ketligining takrorlanishidan oldingi o'lchami davr deyiladi. Muayyan LFSR ning maksimal davrini ta'minlash uchun (ya'ni, registrning mumkin bo'lgan ichki holatlarning og'irligidan o'tishi uchun) registrning ishlashini belgilovchi polinom ibtidoiy modul bo'lishi kerak 2. Katta tub sonlarda bo'lgani kabi, bu erda ham yo'q. Bunday polinomlarni hosil qilish usuli. Siz faqat polinomni olishingiz va uning kamaytirilmaydigan modul 2 ekanligini yoki yo'qligini tekshirishingiz mumkin. Umumiy holatda, n darajali ibtidoiy ko'ph, x 2 "+1 ning bo'luvchisi bo'lgan, lekin ishda 2" -1 ning bo'luvchisi bo'lgan barcha d uchun x d +1 bo'luvchisi bo'lmagan qaytarilmas ko'phaddir B. Shnayerning 2-modulini qisqartirib bo'lmaydigan ba'zi ko'phadlar jadvali berilgan.

LFSR ning ishlashi misolini ko'rib chiqish natijasida olingan bilimlarni umumlashtirib (90-rasm), shuni aytishimiz mumkinki, n-bitli LFSR 2”-1 ichki holatlardan birida bo'lishi mumkin. Nazariy jihatdan bunday registr 2 n -1 bitli psevdotasodifiy ketma-ketlikni hosil qilishi mumkin. Bunday registrlar maksimal muddatga ega LFSR registrlari deb ataladi. Olingan natija t-ketma-ket deyiladi.

Qayta aloqa funksiyasining eng oddiy turi chiziqli funksiyadir, masalan, ma'lum bitlar tarkibining modul 2 yig'indisi. Bu registr chiziqli fikr almashish registr (LFSR) deb ataladi. Umuman olganda, chiziqli qayta aloqa funktsiyasi formula bilan beriladi. Bu yerga c k= 1 agar k Fikr bildirish funksiyasida th bit ishlatiladi va c k= 0 aks holda. Å belgisi qo'shimcha modul 2ni bildiradi (eksklyuziv OR).

Misol uchun, qayta aloqa funktsiyasi bilan LFSRni ko'rib chiqing (rasmga qarang).

Agar registrning dastlabki holati 1111 bo'lsa, keyingi taktlarda u quyidagi holatlar qatorini qabul qiladi: 1111, 0111, 1011, 0101, 1010, 1101, 0110, 0011, 1001, 0100, 0010, 010, 0101, , 1110, 1111, 1111, 1111 ...

Chiqish ketma-ketligi registrning eng kam ahamiyatli (eng o'ngdagi) bitidan hosil bo'ladi. U quyidagicha ko'rinishga ega bo'ladi: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1. Ko'rinib turibdiki, hosil qilingan bit ketma-ketligi to'liq registrning boshlang'ich holati va qayta aloqa funktsiyasi bilan aniqlanadi. Mumkin bo'lgan registr holatlari soni cheklanganligi sababli (u 2 ga teng L), keyin, ertami-kechmi, kalitlar ketma-ketligi o'zini takrorlay boshlaydi. Kalitlar ketma-ketligining takrorlanmaydigan qismining maksimal uzunligi uning davri deb ataladi T. Davr qayta aloqa funktsiyasiga bog'liq. Maksimal mumkin bo'lgan davr T maksimal = 2 L-1 (reestr 0000...0 dan tashqari barcha mumkin bo'lgan holatlarni qabul qiladi). Maksimal davrga ega bo'lgan LFSR ning chiqish ketma-ketligi deyiladi M-ketma-ket.

LFSR maksimal davrga ega bo'lish shartlarini bilish uchun qayta aloqa funktsiyalari xarakterli polinomni tayinlaydi. Shunday qilib, yuqorida misol tariqasida keltirilgan registr ko'phadga mos keladi. Nazariy tahlil shuni ko'rsatadiki, LFSR, agar polinom bo'lsa, maksimal davrga ega bo'ladi P(x) hisoblanadi ibtidoiy. Quyida amaliyotda foydalanish uchun tavsiya etilgan ba'zi bir ibtidoiy ko'phadlar keltirilgan. Jadvalda o'zgaruvchining kuchlari ko'rsatilgan x polinom yozuvida. Masalan, (31, 3) yozuvi ko'phadga mos keladi.

№	P(x)	№	P(x)	№	P(x)
	(39, 16, 23, 35)		(38, 5, 6, 27)		(32, 2, 7, 16)
	(30, 6, 4, 1)		(31, 6)		(31, 7)
	(31, 13)		(31, 25, 23, 8)		(33, 13)
	(35, 2)		(47, 5)		(48, 9, 7, 4)
	(47, 11, 24, 32)		(46, 18, 31, 40)		(53, 6, 2, 1)
	(55, 24)		(57, 7)		(58, 19)
	(59, 7, 4, 2)		(41, 27, 31, 32)		(61, 5, 2, 1)
	(42, 30, 31, 34)		(51, 15, 24, 46)		(50, 17, 31, 34)

LFSR dastlab raqamli sxemalar to'plami sifatida apparatda amalga oshirish uchun mo'ljallangan. LFSR ning dasturiy ta'minoti odatda apparat ta'minotidan past tezlikda. Ishlash samaradorligini oshirish uchun registr holatini butun son sifatida saqlash foydalidir L-bit soni, uning alohida bitlari registrning ikkilik bitlariga mos keladi. Keyinchalik, alohida bitlarga kirish uchun bitli operatsiyalar (shift, maskalash va boshqalar) ishlatiladi.

Chiziqli fikr almashish registrida ikkita qism (modullar) mavjud: siljish registrining o'zi va surilgan bitning qiymatini hisoblaydigan sxemalar (yoki pastki dasturlar). Registr funktsiya hujayralaridan (yoki mashina so'zining bitlari yoki bir nechta so'zlardan) iborat bo'lib, ularning har biri bir bitning joriy holatini saqlaydi. Hujayralar soni registr uzunligi deb ataladi. Bitlar (hujayralar) odatda raqamlar bilan raqamlanadi, ularning har biri bitni saqlashga qodir va hisoblangan bit hujayra ichiga suriladi va keyingi hosil qilingan bit hujayradan chiqariladi. Turtilishi kerak bo'lgan bitni hisoblash odatda registrni siljitishdan oldin amalga oshiriladi va faqat siljishdan keyin hisoblangan bitning qiymati yacheykaga joylashtiriladi.

Shift registrlari davri - natijada ketma-ketlikning takrorlanish boshlanishidan oldingi minimal uzunligi. Bit hujayralar registrida faqat nolga teng bo'lmagan holatlar mavjud bo'lganligi sababli, registrning davri bu raqamdan oshmasligi kerak. Agar registr davri shu raqamga teng bo'lsa, unda bunday registr maksimal davr registri deyiladi.

LFSR uchun teskari aloqa funksiyasi registr bitlarining hammasi yoki ba'zilari holatlarining chiziqli mantiqiy funktsiyasidir. Misol uchun, modul ikki yig'indisi yoki uning mantiqiy inversiyasi chiziqli mantiqiy funktsiyadir (XOR operatsiyasi, formulalarda sifatida belgilanadi) va ko'pincha bunday registrlarda qo'llaniladi.

Bunday holda, qayta aloqa funktsiyasining o'zgaruvchilari bo'lgan bitlar odatda chaqiriladi egiladilar.

Uskunani amalga oshirishda registrlarni boshqarish siljish pulsini qo'llash orqali amalga oshiriladi (aks holda deyiladi soat yoki pulsni sinxronlash) barcha yacheykalarga, dasturiy ta'minotda - dasturiy ta'minot siklini bajarish orqali, jumladan, qayta aloqa funktsiyasini hisoblash va so'zdagi bitlarni o'zgartirish.

Har bir vaqt bosqichida quyidagi operatsiyalar bajariladi:

Lineer Feedback Shift Registr

Shunday qilib, teskari aloqa funktsiyasi sifatida XOR (eksklyuziv OR) mantiqiy operatsiyasi olinadi, ya'ni:

Tub ko‘phadlarning xossalari

Xususiyatlari

LFSR tomonidan ishlab chiqarilgan ketma-ketlikning xususiyatlari bog'langan polinomning xususiyatlari bilan chambarchas bog'liq. Uning nolga teng bo'lmagan koeffitsientlari deyiladi egiladilar, shuningdek, qayta aloqa funktsiyasi argumentlarining qiymatlarini ta'minlaydigan tegishli registr hujayralari.

Chiziqli murakkablik

Ikkilik ketma-ketlikning chiziqli murakkabligi LFSR ishlashining eng muhim xususiyatlaridan biridir. Keling, quyidagi belgini kiritamiz:

Ta'rif

Cheksiz ikkilik ketma-ketlikning chiziqli murakkabligi raqam deyiladi, u quyidagicha aniqlanadi:

Cheklangan ikkilik ketma-ketlikning chiziqli murakkabligi birinchi shartlariga ega bo'lgan ketma-ketlikni hosil qiluvchi eng qisqa LFSR uzunligiga teng bo'lgan raqam deyiladi.

Chiziqli murakkablikning xossalari

Ikkilik ketma-ketliklar bo'lsin va bo'lsin. Keyin:

Korrelyatsiya mustaqilligi

Yuqori chiziqli murakkablikka erishish uchun kriptograflar bir nechta chiqish ketma-ketligi natijalarini nochiziqli tarzda birlashtirishga harakat qilishadi. Bunday holda, xavf shundaki, bir yoki bir nechta chiqish ketma-ketligi (ko'pincha alohida LFSRlarning chiqishlari) umumiy kalit oqimi orqali ulanishi va chiziqli algebra yordamida ochilishi mumkin. Bunday zaiflikka asoslangan xakerlik deyiladi korrelyatsiya otopsisi. Tomas Siegenthaler korrelyatsiya mustaqilligini aniq belgilash mumkinligini va korrelyatsiya mustaqilligi va chiziqli murakkablik o'rtasida mutanosiblik mavjudligini ko'rsatdi.

Bunday buzishning asosiy g'oyasi generatorning chiqishi va uning tarkibiy qismlaridan birining chiqishi o'rtasidagi bog'liqlikni aniqlashdir. Keyin chiqish ketma-ketligini kuzatish orqali ushbu oraliq chiqish haqida ma'lumot olish mumkin. Ushbu ma'lumot va boshqa korrelyatsiyalardan foydalanib, generatorning buzilishiga qadar boshqa oraliq pinlarda ma'lumotlarni to'plash mumkin.

Korrelyatsiya hujumlari yoki tez korrelyatsiya hujumlari kabi o'zgarishlar hisoblash murakkabligi va samaradorlik o'rtasidagi muvozanatni o'z ichiga olgan ko'plab chiziqli qayta aloqa o'zgartirish registrlari kalit oqimi generatorlariga qarshi muvaffaqiyatli ishlatilgan.

Misol

Bog'langan polinomga ega SFLOS uchun hosil qilingan ketma-ketlik shaklga ega. Aytaylik, jarayon boshlanishidan oldin ketma-ketlik registrga yoziladi, keyin hosil bo'lgan bit oqimining davri quyidagi ketma-ketlikda 7 ga teng bo'ladi:

Qadam raqami	Davlat	Yaratilgan bit
0		-
1		1
2		1
3		0
4		1
5		1
6		1
7		0

Ettinchi bosqichdagi ichki holat asl holatiga qaytganligi sababli, keyingi bosqichdan boshlab, takrorlash sodir bo'ladi. Boshqacha qilib aytganda, ketma-ketlikning davri 7 ga teng bo'lib chiqdi, bu ko'phadning primitivligi tufayli yuzaga keldi.

Primitiv ko'phadlarni hosil qilish algoritmlari

Tayyor jadvallar

Polinomning ibtidoiyligini hisoblash ancha murakkab matematik muammodir. Shuning uchun, generatorning maksimal davrini ta'minlaydigan kran ketma-ketliklarining raqamlarini ko'rsatadigan tayyor jadvallar mavjud. Masalan, 32 bitli siljish registrida ketma-ketlik mavjud. Bu shuni anglatadiki, yangi bitni yaratish uchun XOR funksiyasidan foydalanib 31, 30, 29, 27, 25 va 0-bitlarni qo'shishingiz kerak. C tilida bunday RLOS uchun kod quyidagicha:

Int LFSR (void) ( statik unsigned long S = 1; S = ((( (S>> 31 ) ^ (S>> 30 ) ^ (S>> 29 ) ^ (S>> 27 ) ^ (S>> 25 ) ^ S ) & 1 )<< 31 ) | (S>> 1); qaytish S & 1; )

LFSR generatorlarining dasturiy ta'minoti juda sekin va agar ular C tilida emas, balki assemblerda yozilgan bo'lsa, tezroq ishlaydi. Yechimlardan biri parallel ravishda 16 RLOS (yoki ma'lum bir kompyuter arxitekturasidagi so'z uzunligiga qarab 32) dan foydalanishdir. Bunday sxemada o'lchami LFSR uzunligiga teng bo'lgan so'zlar massivi ishlatiladi va massivdagi so'zning har bir biti o'zining LFSR ga tegishli. Agar bir xil bosish tartib raqamlari ishlatilsa, bu sezilarli samaradorlikni ta'minlashi mumkin. [kod misoli kerak] (Qarang: bit bo'laklari).

Galois konfiguratsiyasi

Chiziqli fikr almashish registrining Galois konfiguratsiyasi

Teskari aloqa sxemasi ham o'zgartirilishi mumkin. Bunday holda, generator katta kriptografik kuchga ega bo'lmaydi, lekin uni dasturiy ta'minotda amalga oshirish osonroq bo'ladi. Yangi eng chap bitni yaratish uchun teginish ketma-ketligining eng chap qismidan foydalanish o'rniga, u har bir kran ketma-ketligini generatorning chiqishi bilan XOR qiladi va uni shu harakat natijasi bilan almashtiradi, keyin generatorning chiqishi yangi bo'ladi. eng chap qism. C da bu shunday ko'rinadi:

Int LFSR (void) (statik belgisiz uzun Q = 1 ; Q = (Q>> 1 ) ^ ( Q& 1 ? 0x80000057 : 0 ) ; Qaytish Q & 1 ; )

Foyda shundaki, barcha XORlar bitta operatsiyada amalga oshiriladi.

• Bu erda birinchi berilgan Fibonachchi konfiguratsiyasi va Galois konfiguratsiyasi bir xil ketma-ketliklarni (uzunligi 2 32 -1) beradi, lekin bir-biridan fazada siljiganligini isbotlash mumkin.
• Galois konfiguratsiyasidagi LFSR funksiyasiga belgilangan miqdordagi qo‘ng‘iroqlar davri Fibonachchi konfiguratsiyasiga qaraganda taxminan ikki baravar tez ishlaydi (Intel Core i5 da MS VS 2010 kompilyatori)
• Galois konfiguratsiyasida fikr-mulohazalarni belgilovchi so'zdagi bitlarning tartibi Fibonachchi konfiguratsiyasiga nisbatan teskari ekanligini unutmang.

Generatorga misollar

To'xtash va o'tish generatorlari

O'zgaruvchan to'xtash generatori

Ushbu osilator boshqa LFSR ning soat chastotasini boshqarish uchun bitta LFSR chiqishidan foydalanadi. RSLOS-2 ning taktli chiqishi RSLOS-1 chiqishi bilan boshqariladi, shuning uchun RSLOS-2 t vaqtidagi holatini faqat t-1 vaqtidagi RSDOS-1 chiqishi bittaga teng bo'lgan taqdirdagina o'zgartirishi mumkin. Ammo bu sxema korrelyatsion dissektsiyaga qarshi tura olmadi.

Shu sababli, xuddi shu g'oyaga asoslangan takomillashtirilgan generator taklif qilindi. U o'zgaruvchan to'xtash generatori deb ataladi. Turli uzunlikdagi uchta LFSR dan foydalanadi. RSLOS-1 ning chiqishi birga teng bo'lganda RSLOS-2, RSLOS-1 chiqishi esa nolga teng bo'lganda RSLOS-3 soatiga to'g'ri keladi. Generatorning chiqishi RSLOS-2 va RSLOS-3 ning modul 2 yig'indisidir. Ushbu generator uzoq muddat va yuqori chiziqli murakkablikka ega. Uning mualliflari RSLOS-1 ning korrelyativ ochilish usulini ham ko'rsatdilar, ammo bu generatorni juda zaiflashtirmaydi.

Gollmann kaskadi

Gollmann kaskadi

Gollmann kaskadi to'xtash generatorining kuchaytirilgan versiyasidir. U LFSR ketma-ketligidan iborat bo'lib, ularning har birining vaqti avvalgi LFSR tomonidan boshqariladi. Agar RSLOS-1 ning t vaqtidagi chiqishi 1 ga teng bo'lsa, u holda RSLOS-2 soatli hisoblanadi. Agar RSLOS-2 ning t vaqtidagi chiqishi 1 ga teng bo'lsa, u holda RSLOS-3 ning taktlisi va hokazo. Oxirgi LFSR ning chiqishi generatorning chiqishi hisoblanadi. Agar barcha LFSR uzunligi bir xil va n ga teng bo'lsa, u holda k LFSR tizimining chiziqli murakkabligi ga teng bo'ladi.

Ushbu g'oya oddiy va katta davrlar, katta chiziqli murakkabliklar va yaxshi statistik xususiyatlarga ega ketma-ketliklarni yaratish uchun ishlatilishi mumkin. Ammo, afsuski, ular "qulflash" deb ataladigan ochilishga sezgir. Kattaroq chidamlilik uchun kamida 15 k dan foydalanish tavsiya etiladi. Bundan tashqari, kamroq uzun LFSRlardan ko'ra ko'proq qisqa LFSRlardan foydalanish yaxshiroqdir.

Eshik generatori

Eshik generatori

Ushbu generator o'zgaruvchan sonli registrlar yordamida oldingi generatorlarga xos bo'lgan xavfsizlik muammolarini bartaraf etishga harakat qiladi. Nazariy jihatdan, ko'proq miqdordagi siljish registrlaridan foydalanganda, shifrning murakkabligi oshadi, bu generatorda bajarilgan.

Bu generator ko'p sonli siljish registrlaridan iborat bo'lib, ularning chiqishlari kattalashtirish funktsiyasiga beriladi. Agar registrlarning chiqishlarida birlar soni yarmidan ko'p bo'lsa, generator bittasini chiqaradi. Agar chiqishlardagi nollar soni yarmidan ko'p bo'lsa, generator nolga teng bo'ladi. Nol va birlar sonini taqqoslash mumkin bo'lishi uchun siljish registrlari soni toq bo'lishi kerak. Barcha registrlarning uzunliklari nisbatan tub bo'lishi kerak, qayta aloqa ko'phadlari esa ibtidoiy bo'lishi kerak, shuning uchun hosil qilingan ketma-ketlikning davri maksimal bo'lishi kerak.

Uch siljish registrlari uchun generatorni quyidagicha ko'rsatish mumkin:

Ushbu generator Geff generatoriga o'xshaydi, faqat chegara generatori ko'proq chiziqli murakkablikka ega. Uning chiziqli murakkabligi:

bu yerda , , birinchi, ikkinchi va uchinchi smenali registrlarning uzunliklari.

Uning kamchiligi shundaki, har bir chiqish biti siljish registrining holati haqida ba'zi ma'lumotlarni beradi. To'g'rirog'i, 0,189 bit. Shuning uchun, bu generator korrelyatsiya hujumiga qarshi tura olmasligi mumkin.

Boshqa turlar

O'z-o'zidan yupqalash

O'z-o'zini yo'q qiladigan generatorlar o'zlarining chastotalarini boshqaradiganlardir. Bunday generatorlarning ikki turi taklif qilingan. Birinchisi, chiziqli qayta aloqa o'zgarishi registridan va siljish registrining chiqish qiymatlari qanday bo'lishiga qarab, ushbu registrni soatlaydigan ba'zi sxemalardan iborat. Agar SFSR ning chiqishi birga teng bo'lsa, u holda registr d marta soatlanadi. Agar chiqish nolga teng bo'lsa, registr k marta soatlanadi. Ikkinchisi deyarli bir xil dizaynga ega, ammo biroz o'zgartirilgan: soat pallasida 0 yoki 1 ni tekshirish uchun kirish chiqish signalining o'zi emas, balki chiziqli qayta aloqa bilan siljish registrining ma'lum bitlarining XORidir. Afsuski, bu turdagi generator xavfsiz emas.

Ichki mahsulotga ega ko'p tezlikli osilator

Ushbu osilator turli xil soat chastotalariga ega ikkita chiziqli qayta aloqa o'zgartirish registrlaridan foydalanadi: RSLOS-1 va RSLOS-2. RSLOS-2 ning soat chastotasi RSLOS-1 dan d marta katta. Bu registrlarning alohida bitlari AND operatsiyasi yordamida birlashtiriladi. Keyin AND operatsiyasining natijalari XORlanadi. Chiqish ketma-ketligi ushbu XOR blokidan olingan. Shunga qaramay, bu generator beg'ubor emas (U chiziqli konsistensiyaning ochilishiga dosh bermadi. Agar - SFLO-1 uzunligi, - SFLO-2 uzunligi va d - taktli chastotalar nisbati bo'lsa, u holda ichki holat. generator uzunlikdagi chiqish ketma-ketligidan olinishi mumkin ), lekin u yuqori chiziqli murakkablik va mukammal statistik ko'rsatkichlarga ega.