Графика

Кері байланысты ауыстыру тіркелімі. Кері байланысы бар сызықты жылжу регистрлері

шифрды шешу - p i = D (k i , c i) , суретте көрсетілгендей. 7.21.

Күріш. 7.21.

Ағындық шифрлар блоктық шифрларға қарағанда жылдамырақ. Ағындық шифрдің аппараттық орындалуы да оңайырақ. Екілік ағындарды шифрлау және оларды тұрақты жылдамдықпен жіберу керек болғанда, ең жақсы таңдау- ағындық шифрды қолдану. Ағындық шифрлар тасымалдау кезінде биттердің бүлінуінен көбірек қорғанысқа ие.

Заманауи ағындық шифрда әрқайсысы r -ашық мәтін ағынындағы бит сөзі арқылы шифрланады r Сәйкесті жасау үшін кілттер ағынындағы -бит сөзі r -шифрлық мәтін ағынындағы биттік сөз.

Күріш. 7.22.

Бір реттік тақта – тамаша шифр. Ол мінсіз. Қарсыласқа шифр мен ашық мәтіннің кілтін немесе статистикасын тану мүмкіндігін беретін әдіс жоқ. Түпнұсқа мен шифрланған мәтіндер арасында ешқандай байланыс жоқ. Басқаша айтқанда, егер сіз ашық мәтіннің кейбір үлгілерін алсаңыз да, шифрленген мәтін шынайы кездейсоқ биттік ағын болып табылады. Егер ашық мәтін өлшемі n-бит болса, 2n болатын барлық ықтимал кездейсоқ кілттер ағындарын қолданбайынша, Хауа шифрды бұза алмайды. Дегенмен, бұл мәселеде мәселе бар. Таратқыш пен қабылдағыш бір реттік пернелер тақтасын ортақ пайдалану үшін ақпарат алмасқысы келген сайын байланыс орнатуы керек. Олар қандай да бір түрде кездейсоқ кілт туралы келісуі керек. Сондықтан бұл тамаша және идеалды шифрды жүзеге асыру өте қиын.

7.17-мысал

Төмендегі жағдайлардың әрқайсысында бір реттік блоктық шифрды пайдаланған кезде шифрленген мәтіннің пішіні қандай?

а. Түпнұсқа мәтін n нөлден тұрады.

б. Бастапқы мәтін n бірліктен тұрады.

v. Түпнұсқа мәтін ауыспалы нөлдер мен бірліктерден тұрады.

d) Түпнұсқа мәтін биттердің кездейсоқ тізбегі болып табылады.

Шешім

а. Қаншалықты , содан кейін шифрлық мәтін ағыны кілттер ағынына сәйкес келеді. Егер кілт кездейсоқ болса, шифрлық мәтін де кездейсоқ болады. Шифрленген мәтінде түпнұсқа мәтіннің фрагменттері сақталмайды.

б. Қаншалықты , толтыру қайда, шифрлық мәтін ағыны кілттер ағынының толтырылуы болып табылады. Егер кілттер ағыны кездейсоқ болса, онда шифрленген мәтін де кездейсоқ болады, ашық мәтіннің биттері шифрлық мәтінде сақталмайды.

в. Бұл жағдайда шифрлық мәтін ағынындағы әрбір бит не кілттік ағынмен бірдей, не оның толықтаушысы болады. Сондықтан кілттер ағыны кездейсоқ болса, нәтиже де кездейсоқ болады.

г. Бұл жағдайда шифрлы мәтін анық кездейсоқ болады, себебі екі кездейсоқ биттерді XOR-ге келтіру биттердің кездейсоқ ағынына әкеледі.

Кері байланысты ауыстыру тіркелімі

Бір реттік тақтаны жақсартудың бірі (FSR - Feedback Shift Register). FSR екіде де жүзеге асырылуы мүмкін бағдарламалық қамтамасыз ету, немесе аппараттық құралда, бірақ қарапайымдылық үшін біз аппараттық қамтамасыз етуді іске асыруды қарастырамыз. Кері байланысты ауыстыру тіркелімітұрады ауыстыру регистрі және кері байланыс функциялары, суретте көрсетілгендей. 7.23.

Күріш. 7.23.

Ауысым регистрі b 0-ден b m-1-ге дейінгі m ұяшықтардың тізбегі болып табылады, мұнда әрбір ұяшық бір битті сақтауға арналған. Ұяшықтар басында «тұқымдық мән» немесе деп аталатын n -биттік сөз ретінде қарастырылады көзі. Шығуда бит қабылдау қажет болған кезде (мысалы, кіріс сигналында белгілі бір уақыт), әрбір бит бір ұяшық оңға жылжытылады. Бұл әрбір ұяшықтың мәні оң жақ көрші ұяшыққа тағайындалып, сол жақ ұяшықтың мәнін қабылдайтынын білдіреді. Ең оң жақ b 0 ұяшығы шығыс болып саналады және шығыс мәнін береді (k i ). Ең сол жақ ұяшық, b m-1, кері байланыс функциясының ақпарат мәніне сәйкес өз мәнін алады. Функцияның шығысын кері байланыс ақпаратымен белгілейміз b m . Кері байланыс ақпараты функциясы b m есептеу үшін ұяшықтардың қандай мәндері бар екенін анықтайды. Кері байланыс ақпаратының ығысу регистрі сызықты немесе сызықты емес болуы мүмкін.

Сызықтық кері байланысты ауыстыру тіркелімі (LFSR). b m сызықтық функция b 0 , b 1 ,…..., b m-1 деп алайық, ол үшін

Сызықтық кері байланысты ауыстыру регистрі екілік сандармен жұмыс істейді, сондықтан көбейту және қосу GF(2) өрісінде болады, сондықтан C i мәні не 1, не 0 болады, бірақ шығыста кері байланыс ақпаратын алу үшін C 0 1 болуы керек. Қосу операциясы ЭКСКЛЮЗИВ НЕМЕСЕ операция болып табылады. Басқа сөзбен,

7.18 мысал

5 ұяшықтан тұратын сызықтық кері байланыстың ығысу регистрін құрастырайық, онда .

Шешім

Егер C i = 0 болса, b i b m есептеуінде рөл атқармаса, онда бұл b i кері байланыс ақпараты функциясымен байланысты емес дегенді білдіреді. Егер c i = 1 болса, b i b m есебіне кіреді. Бұл мысалда c 1 және c 3 - нөлдер, яғни бізде тек үш байланыс бар. 7.24-суретте кері байланыстың сызықтық ауысу регистрінің сұлбасы көрсетілген.

Күріш. 7.24.

7.19-мысал

4 ұяшықтан тұратын сызықтық кері байланыстың ауысу регистрін құрастырайық, онда . 20-дан кейінгі регистр мәнін көрсетіңіз операциялар (ауысымдар) егер бастапқы мән (0001) 2 болса.

Шешім

7.25-суретте шифрлау үшін сызықтық кері байланысты ауыстыру регистрін құрастыру және пайдалану көрсетілген.

Күріш. 7.25.

7.6-кесте. кілттер ағынының мәнін көрсетеді. Әрбір өту үшін b 4 бірінші мәні есептеледі, содан кейін әрбір бит бір ұяшық оңға жылжытылады.

7.6-кесте.

ағымдағы құн	б 4	б 3	б 2	б 1	b 0	k i
Бастапқы мән	1	0	0	0	1
1	0	1	0	0	0	1
2	0	0	1	0	0	0
3	1	0	0	1	0	0
4	1	1	0	0	1	0
5	0	1	1	0	0	1
6	1	0	1	1	0	0
7	0	1	0	1	1	0
8	1	0	1	0	1	1
9	1	1	0	1	0	1
10	1	1	1	0	1	0
11	1	1	1	1	0	1
12	0	1	1	1	1	0
13	0	0	1	1	1	1
14	0	0	0	1	1	1
15	1	0	0	0	1	1
16	0	1	0	0	0	1
17	0	0	1	0	0	0
18	1	0	0	1	0	0
19	1	1	0	0	1	0
20	1	1	1	0	0	1

Негізгі ағын 1000100110101111 1001…… екенін ескеріңіз. Бұл бір қарағанда кездейсоқ реттілік сияқты көрінеді, бірақ транзакциялардың (ауысымдардың) үлкен санын қарасақ, тізбектердің мерзімді болатынын көреміз. 15 биттен тұратын бұл қайталау төменде көрсетілген.

Сызықтық кері байланысты ауыстыру регистрінің көмегімен ағындық кілт жасайды псевдокездейсоқ реттілік, онда N ұзындықтағы тізбектер қайталанады. Ағын периодты. Ол генератор тізбегіне және бастапқы ақпаратқа байланысты және 2 м - 1 артық емес болуы мүмкін. Әрбір схема барлық нөлдерді қамтитыннан барлығын қамтитынға дейін m -биттік тізбектерді жасайды. Дегенмен, егер бастапқы реттілік тек нөлдерден тұрса, нәтиже пайдасыз - түпнұсқа мәтін барлық нөлдердің ағыны болар еді. Сондықтан мұндай бастапқы реттілік алынып тасталады.

Білім және ғылым министрлігі

РЕСЕЙ МЕМЛЕКЕТТІК ӘЛЕУМЕТТІК УНИВЕРСИТЕТІ

АҚПАРАТТЫҚ ТЕХНОЛОГИЯЛАР ФАКУЛЬТЕТІ

АҚПАРАТТЫ ҚОРҒАУ БӨЛІМІ

Криптографиялық әдістер мен қамтамасыз ету құралдары ақпараттық қауіпсіздік

Курстық жұмыс

«Р псевдокездейсоқ сандар генераторы ретінде сызықтық кері байланысы бар ауыспалы регистрлер»

Аяқталды:

3 курс студенті

KZOI-D-3 тобы

Ларионов И.П.

Тексерілді:

доц. Баранова Е.Қ.

Мәскеу 2011 ж
МАЗМҰНЫ

Кіріспе ……………………………..…………………………………….3

Жұмыстың теориялық негіздері…………………………………………4
1. Негізгі ақпаратКері байланысты ауыстыру регистрлері туралы………..4
  1. RgCsLOS негізіндегі ағындық шифрлар туралы……………….………10
  2. жинақталатын псевдо-кездейсоқ реттілігі PgCsLOS сызықтық күрделілігіне ........................................... ...... 12
  3. PrCsLOS псевдокездейсоқ сандардың құрылған тізбегінің корреляциялық тәуелсіздігі туралы………..….13
  4. RgCsLOS жалған кездейсоқ сандардың генерацияланған тізбегін ашудың басқа әдістері бойынша……………………………………..14
Pseudo-кездейсоқ реттілік генераторы ретінде RgCsLOS бағдарламалық қамтамасыз етуді жүзеге асыру….…………………………….15
1. Алгоритмнің жалпыланған сұлбасы…………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………15
2. Бағдарламалық модульдер мен интерфейстің сипаттамасы.……………….16
3. Пайдаланушы нұсқаулығы…………………………………………20

Қорытынды ………………………………………………………………22

Әдебиеттер тізімі………………………………………………….....23

Қосымша А ….………………………………………………………..24

КІРІСПЕ

Бұл жұмыстың мақсаты кері байланысы бар ауысымдық регистрлер негізінде жалған кездейсоқ сандар генераторының жұмысын жүзеге асыратын бағдарламалық қосымшаны әзірлеу болып табылады. Даму бұл қолданбабірге GUIтілінде жүзеге асырылады Windows ОЖ үшін C++.

20 ғасырда криптографияның дамуымен криптографтардың алдында хабарламаларды тез және сенімді түрде шифрлайтын және шифрлай алатын шифрлау құрылғылары мен машиналарын жасау міндеті тұрды. Сол кезде ашылған симметриялық шифрлау жүйелері бұл талапқа жауап берді, бірақ олардың әлсіз жері кілтке және оның құпиялығына қатты тәуелділік болды. Осы мақсатта қолдануға болатын шифрлардың ең қолайлы класы ойын шифрлары болып табылады. Мәселе хабарлама шифрын шешкен кезде анықталмайтын гамманы жасауда туындады. Теориялық тұрғыдан, бұл гамма әр жолы кездейсоқ болса және уақыт өте өзгерсе мүмкін болды. Дегенмен, толығымен кездейсоқ өзгеретін гамманы пайдаланған кезде, хабарламаның сенімді шифрлау-дешифрлеуін қамтамасыз ету қиын болады. Криптографтар бұл мәселені шешу міндетін алды, оның мақсаты белгілі бір ережеге сәйкес кездейсоқ диапазонды генерациялауды жүзеге асыратын алгоритмді табу болды, мұндай реттілікте «болжам» кездейсоқ позицияларда нөлдер мен бірліктер болуы керек, ал бір және нөл саны шамамен бірдей болуы керек. Бұл кездейсоқ реттілік деп аталадыпсевдокездейсоқөйткені ол кездейсоқ емес, белгілі бір ережеге сәйкес жасалған.

Шешім көп ұзамай табылды. Ауысым регистрлерінің қасиеттерін зерттеу кері байланыстың ауысу регистрлерінің ішкі құрылымына байланысты декодтауға жеткілікті төзімді жалған кездейсоқ тізбектерді құруға қабілетті екенін анықтауға мүмкіндік берді.

1.Жұмыстың теориялық негіздері

1.1 Сызықтық кері байланысы бар ауысым регистрлері туралы жалпы мәліметтер

Жылжыту регистрлерінің реттілігі криптографияда да, кодтау теориясында да қолданылады. Олардың теориясы жақсы дамыған, ауысымдық регистр негізіндегі ағындық шифрлар электроника пайда болғанға дейін әскери криптографияның жұмыс күші болды.

Кері байланысты ауыстыру регистрі (бұдан әрі – PgCsOS) екі бөліктен тұрады: ауысу регистрі және кері байланыс функциясы.Ауыстыру регистрі биттердің тізбегі болып табылады. Биттер саны анықталадыауыстыру регистрінің ұзындығы, ұзындығы n бит болса, онда регистр шақырыладыn-разрядты ауыстыру регистрі. Битті шығару қажет болғанда, ауыстыру регистрінің барлық биттері 1 позицияға оңға жылжиды. Жаңа сол жақ бит регистрдегі барлық басқа биттердің функциясы болып табылады. Ауысым регистрінің шығысы бір, әдетте ең аз маңызды бит болып табылады.Ауысым регистрінің кезеңі- нәтиже ретінің қайталана бастағанға дейінгі ұзындығы.

Сурет Кері байланыс ауысым тіркелімі

Ауыстыру регистрлері ағындық шифрларда тез қолданылды, өйткені оларды пайдалану оңай жүзеге асырылды сандық жабдық. 1965 жылы Норвегия үкіметінің бас криптографы Эрнст Селмер ауысым регистрінің реттілік теориясын жасады. NSA математигі Соломон Голомб өзінің және Селмердің кейбір нәтижелерін сипаттайтын кітап жазды. Кері байланысты ауыстыру регистрінің қарапайым түрі болып табыладысызықтық кері байланыс ығысу тіркелімі (сызықтық кері байланыс ығысу тіркелімі , бұдан әрі LFSR немесе RgCsLOS) . Мұндай регистрлердің кері байланысы регистрдің кейбір биттерінің жай ғана XOR (модульді екі қосу) болып табылады, бұл биттердің тізімі түрту тізбегі деп аталады. Кейде мұндай регистрді Фибоначчи конфигурациясы деп атайды. Кері байланыс реттілігінің қарапайымдылығына байланысты PgCsLOC талдау үшін жеткілікті дамыған математикалық теорияны қолдануға болады. Алынған шығыс тізбектерін талдау арқылы бұл реттіліктердің қауіпсіз болуы үшін жеткілікті кездейсоқ екенін тексеруге болады. Ауысым регистрлері криптографияда басқа ауысым регистрлеріне қарағанда жиі қолданылады.

PgCsLOS Фиббоначчи суреті

Жалпы, Н -бит PrCsLOS бірінде болуы мүмкін N=2n -1 ішкі күй. Бұл теориялық тұрғыдан мұндай регистр периоды T=2 болатын псевдокездейсоқ тізбекті құра алады дегенді білдіреді. n -1 бит. (Ішкі күйлердің саны мен период тең N=Tmax=2n -1, себебі PrCsLOC-ті нөлдермен толтыру ауысым регистрінің нөлдердің шексіз тізбегін шығаруына әкеледі, бұл мүлдем пайдасыз). Тек белгілі бір түрту ретімен PrCsLOS циклді түрде барлық 2 арқылы өтеді n -1 ішкі күйлер, мұндай RgCsLOSМаксималды кезеңмен RgSsLOS. Алынған нәтиже шақырыладыM-тізбегі.

Мысал . Төмендегі суретте бірінші және төртінші биттердің түртуі бар 4-биттік PrCsLOS көрсетілген. Егер ол 1111 мәнімен инициализацияланса, онда регистр қайталамас бұрын келесі ішкі күйлерді қабылдайды:

Жылжыту белгісінің нөмірі (ішкі күй)	Тіркелу күйі	шығыс биті
Жылжыту белгісінің нөмірі (ішкі күй)		шығыс биті
Бастапқы мән














15 (бастапқы күйге оралу)
16 (қайталау күйі)

Шығару тізбегі ең аз маңызды биттердің жолы болады: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 период T=15, мүмкін болатын ішкі күйлердің жалпы саны (нөлден басқа), N=2 4 -1=16-1=15= Tmax , демек, шығу реті боладыМ -жүйелі.

Белгілі бір PgCsLOS максималды периодқа ие болуы үшін түрткі тізбегінен құрылған көпмүше және 1 тұрақтысы қарабайыр модуль 2 болуы керек. Көпмүше дәрежелердің қосындысы ретінде көрсетіледі, мысалы, дәрежелі көпмүше. n келесідей көрінеді:

anxn +a n-1 x n-1 +…+a 1 x 1 +a 0 x 0 =anxn +a n-1 x n-1 +…+a 1 x+a 0 , мұндағы a i =(0, 1 ) i=1…n үшін, ось – битті көрсетеді.

Көпмүшенің дәрежесі - жылжу регистрінің ұзындығы. n дәрежелі қарабайыр көпмүше х-тің бөлгіші болатын азайтылмайтын көпмүше. 2n−1 +1 бірақ х-тің бөлгіші емес d Барлық d 2-ге бөлгіштер үшін +1 n -бір. Сәйкес математикалық теорияны мына жерден табуға болады.

Жалпы, жоқ оңай жолБерілген дәрежедегі қарабайыр көпмүшелерді генерациялау модулі 2. Ең оңай жолы – көпмүшені кездейсоқ таңдау және оның қарабайыр екенін тексеру. Бұл оңай емес және кездейсоқ таңдалған санның жай емес екенін тексеру сияқты, бірақ көптеген математикалық бағдарламалық қамтамасыз ету пакеттері бұл мәселені шеше алады.

Кейбір, бірақ барлығы емес, әртүрлі дәрежедегі көпмүшеліктер, қарабайыр модуль 2, төменде келтірілген. Мысалы, кіріс

(32, 7, 5, 3, 2, 1, 0) мына көпмүшенің 2-қарабайыр модуль екенін білдіреді: x 32 + x 7 + x 5 + x 3 + x 2 + x + 1.

Мұны PrCcLOC үшін максималды кезеңмен оңай жалпылауға болады. Бірінші сан PrCsLOS ұзындығы. Соңғы сан әрқашан 0 болады және оны өткізіп жіберуге болады. 0-ден басқа барлық сандар жылжу регистрінің сол жақ жиегінен есептелетін түрту ретін көрсетеді. Яғни, төмен дәрежелі көпмүшенің мүшелері регистрдің оң жақ шетіне жақын орналасқан орындарға сәйкес келеді.

Мысалды жалғастыра отырып, жазу (32, 7, 5, 3, 2, 1, 0) берілген 32-разрядты регистр үшін отыз екінші, жетінші, бесінші, үшінші, екінші XORing арқылы жаңа бит жасалатынын білдіреді. , және бірінші биттерде алынған RgCsLOS максималды ұзындыққа ие болады, 2-ден кейін қайталанғанша цикл жүреді. 32 -1 мәндер.

4-сурет Максималды ұзындығы бар 32-биттік PrCsLOS

Қарастырыңыз бағдарламалау коды PgCsLOS, оның түрту тізбегі полиноммен сипатталады (32, 7, 5, 3, 2, 1, 0). Си тілінде ол келесідей көрінеді:

int LFSR()(

статикалық қолтаңбасыз ұзын ShiftRegister = 1;

/* 0-ден басқа барлығы. */

ShiftRegister = ((((ShiftRegister >> 31)

^(ShiftRegister >> 6)

^(ShiftRegister >> 4)

^(ShiftRegister >> 2)

^(ShiftRegister >> 1)

^ShiftRegister))

& 0x00000001)

<<31)

| (ShiftRegister >> 1) ;

ShiftRegister қайтару & 0 x 00000001;)

Ауысым регистрі компьютер сөзінен ұзағырақ болса, код күрделене түседі, бірақ көп емес. ҚолданбадаБ кейбір қарабайыр көпмүшелердің кестесі 2 модулі берілген, біз оны болашақта осы көпмүшелердің кейбір қасиеттерін анықтау үшін пайдаланамыз, сонымен қатар бағдарламалық қамтамасыз етуді енгізутүрту ретін орнату үшін.

Кестенің барлық элементтерінде коэффициенттердің тақ саны бар екенін атап өткен жөн. Мұндай ұзын кесте PrCfLOC-пен әрі қарай жұмыс істеу үшін қарастырылған, өйткені PrCfLOC көбінесе ағындық шифрлары бар криптография үшін және жалған кездейсоқ сандар генераторларында қолданылады. Біздің жағдайда біз жетіден аспайтын ең жоғары дәрежелі көпмүшелерді пайдалана аламыз.

Егер p(x) қарабайыр болса, онда х n p(1/x), сондықтан кестенің әрбір элементі шын мәнінде екі қарабайыр көпмүшені анықтайды. Мысалы, егер (a, b, 0) қарабайыр болса, онда (a, a-b, 0). Егер (a, b, c, d, 0) қарабайыр болса, онда (a, a-d, a-c, a-b, 0). Математикалық:

егер x қарабайыр болса a+xb +1, онда ол қарабайыр және x a+x a-b+1,

егер x қарабайыр болса a + x b + x c + x d +1, онда ол қарабайыр және x a + x a-d + x a-c + x a-b +1. Қарапайым үш мүшелер бағдарламалы түрде ең жылдам орындалады, өйткені жаңа разрядты генерациялау үшін ауысым регистрінің екі биті ғана XOR керек (нөлдік термин ескерілмейді, яғни x 0 =1, жоғарыдағы мысалды қараңыз). Шынында да, кестеде келтірілген кері байланыс көпмүшелерінің барлығы сирек, яғни олардың коэффициенттері аз. Сиректік әрқашан әлсіздік көзі болып табылады, бұл кейде алгоритмді ашу үшін жеткілікті. Криптографиялық алгоритмдер үшін коэффициенттері көп тығыз қарабайыр көпмүшелерді қолданған әлдеқайда тиімді. Тығыз көпмүшелерді пайдалану арқылы, әсіресе кілттің бөлігі ретінде, әлдеқайда қысқа PrCcLOC пайдалануға болады.

Тығыз қарабайыр көпмүшелердің модулі 2 құру оңай емес. Жалпы жағдайда k дәрежелі қарабайыр көпмүшелерді құру үшін 2 санының көбейткіштерге жіктелуін білу қажет. k-1.

Өздігінен PgCsLOS жақсы псевдокездейсоқ реттілік генераторлары болып табылады, бірақ олардың кейбір жағымсыз кездейсоқ емес (детерминирленген) қасиеттері бар. Тізбектелген биттер сызықты, сондықтан оларды шифрлау үшін жарамсыз етеді. Ұзындығы n PgCsLOS үшін ішкі күй генератордың алдыңғы n шығыс разряды болып табылады. Кері байланыс схемасы құпия сақталса да, оны жоғары тиімді Берлекамп-Масси алгоритмі арқылы генератордың 2n шығыс разрядтарынан анықтауға болады.

Сонымен қатар, үлкен кездейсоқ сандаросы дәйектіліктің дәйекті биттерін пайдаланып жасалған жоғары корреляциялық және қолданбалардың кейбір түрлері үшін мүлдем кездейсоқ емес. Осыған қарамастан, PrCsLOS шифрлау алгоритмдерін жасау үшін жиі пайдаланылады құрамдас бөліктершифрлау жүйелері мен алгоритмдері.

1.2.RgCsLOS негізіндегі ағындық шифрлар туралы

PrCsLOS негізіндегі кілттер ағыны генераторын жобалаудың негізгі тәсілі қарапайым. Алдымен бір немесе бірнеше PrCsLOS алынады, әдетте ұзындығы әртүрлі және кері байланыс көпмүшелері әртүрлі. (Егер ұзындықтар қос қарапайым және барлық кері байланыс көпмүшелері қарабайыр болса, онда құрылған генератор максималды ұзындыққа ие болады.) Кілт PrCcLOC регистрлерінің бастапқы күйі болып табылады. Жаңа бит қажет болған сайын PrCsLOS регистрлерін бит (кейде сағат деп те аталады) ауыстырыңыз. Шығыс разряд PrCsLOC регистрлерінің кейбір биттерінің функциясы, жақсырақ сызықты емес. Бұл функция біріктіруші функция деп аталады, ал генератор тұтастай комбинациялық генератор деп аталады. (Егер шығыс бит бір PgCsLOS функциясы болса, онда осциллятор сүзгі осцилляторы деп аталады.) Мұндай құрылғылардың артындағы теорияның көпшілігін Селмер және Нил Зиерлер әзірлеген. Сіз бірқатар асқынуларды енгізе аласыз. Кейбір генераторларда әртүрлі PgCsLOS үшін әртүрлі тактілік жиіліктер қолданылады, кейде бір генератордың жиілігі екіншісінің шығысына байланысты болады. Бұл басқарылатын генераторлар деп аталатын Екінші дүниежүзілік соғысқа дейінгі шифрлық машина идеяларының электронды нұсқалары. тактілік жиілік (сағатпен басқарылатын генераторлар ). Сағатты басқару бір PgSsLOS шығысы басқа PgSsLOS тактілік жылдамдығын басқаратын алға бағытталуы немесе бір PgSsLOS шығысы өз сағатын басқаратын жабық цикл болуы мүмкін. Бұл генераторлардың барлығы, кем дегенде, теориялық тұрғыдан, ұя салу шабуылдарына және ықтимал корреляцияға сезімтал болғанымен, олардың көпшілігі әлі де қауіпсіз.

Бұрынғы Кембридждегі таза математика кафедрасының меңгерушісі және Блетчли Паркте криптоаналитик болған Ян Касселс «криптография математика мен шатасудың қоспасы, ал шатаспай математика сізге қарсы қолданылуы мүмкін» деді. Оның айтқысы келгені: ағындық шифрларда PrCcLOC сияқты белгілі бір математикалық құрылымдар максималды ұзындық пен басқа қасиеттерді қамтамасыз ету үшін қажет, бірақ біреудің регистрдің мазмұнын алуына және крекингке жол бермеу үшін кейбір күрделі сызықты емес тәртіпсіздіктер енгізілуі керек. алгоритм. Бұл кеңес блок алгоритмдері үшін де жарамды.

Көптеген нақты ағындық шифрлар PrCsLOS негізінде жасалған. Электрониканың алғашқы күндерінің өзінде оларды құрастыру оңай болды. Ауысым регистрі биттердің массивінен басқа ештеңе емес, ал кері байланыс тізбегі XOR қақпаларының жиынтығы болып табылады. Тіпті VLSI пайдаланған кезде, PrCsLOS негізіндегі ағындық шифр бірнеше логикалық қақпалардың көмегімен айтарлықтай қауіпсіздікті қамтамасыз етеді. PgCsLOS проблемасы олардың бағдарламалық қамтамасыз етуді енгізу өте тиімсіздігінде. Сіз сирек кері байланыс полиномдарынан аулақ болуыңыз керек - олар корреляциялық шабуылдарды жеңілдетеді - және тығыз кері байланыс полиномдары тиімсіз.

Криптографияның бұл саласы қарқынды дамып келеді және мемлекеттің қырағы бақылауында NSA . Көптеген әзірлемелер жіктеледі - бүгінгі күні қолданылатын көптеген әскери шифрлау жүйелері PrCsLOS негізінде жасалған. Шынында да, Cray компьютерлерінің көпшілігінде (Cray 1, Cray X-MP, Cray Y-MP) әдетте «халық саны» деп аталатын өте қызықты нұсқау бар. Ол регистрдегі 1 санының санын есептейді және екі екілік сөз арасындағы Хэмминг қашықтықты тиімді есептеу үшін де, PrCcLOS векторланған нұсқасын жүзеге асыру үшін де пайдаланылуы мүмкін. Бұл нұсқаулық NSA-ның канондық нұсқауы болып саналады және барлық дерлік компьютерлік келісімшарттарда кездеседі.

Екінші жағынан, күрделі болып көрінетін ауысымдық регистр генераторларының таңқаларлық үлкен саны бұзылды. Және, әрине, NSA сияқты әскери криптоаналитикалық институттар бұзған мұндай генераторлардың саны одан да көп.

1.3. PrCsLOS жалған кездейсоқ сандар тізбегінің сызықтық күрделілігі туралы

Блоктық шифрларға қарағанда ағынды шифрларды талдау жиі оңайырақ. Мысалы, PgCsLOC негізіндегі генераторларды талдау үшін пайдаланылатын маңызды параметр сызықтық күрделілік немесе сызықтық интервал болып табылады. Ол генератор шығысын имитациялай алатын ең қысқа PrCsLOS ұзындығы n ретінде анықталады. Ақырлы өрісте соңғы автомат арқылы жасалған кез келген реттілік шекті сызықтық күрделілікке ие. Сызықтық күрделілік маңызды, өйткені Берлекамп-Массей алгоритмі деп аталатын қарапайым алгоритм арқылы кілттер ағынының тек 2n биттерін зерттеу арқылы осы PrCcLOC анықтауға болады. Қажетті PrCsLOS қайта жасау арқылы сіз ағын шифрін бұзасыз.

Бұл идеяны өрістерден сақиналарға дейін және шығыс реті тақ сипаттама өрісіндегі сандар ретінде қарастырылатын жағдайларға дейін кеңейтуге болады. Әрі қарай кеңейту сызықтық күрделілік профилі тұжырымдамасын енгізуге әкеледі, ол ұзарған сайын тізбектің сызықтық күрделілігін анықтайды. Сонымен қатар сфералық және квадраттық күрделілік ұғымдары бар. Кез келген жағдайда, жоғары сызықтық күрделілік генератордың қауіпсіздігіне міндетті түрде кепілдік бермейтінін есте ұстаған жөн, бірақ төмен сызықтық күрделілік генератордың жеткіліксіз қауіпсіздігін көрсетеді.

1.4.Псевдокездейсоқ сандардың құрылған тізбегінің корреляциялық тәуелсіздігі туралы PrCsLOS

Криптографтар кейбір шығыс тізбектерінің нәтижелерін сызықтық емес жолмен біріктіру арқылы жоғары сызықтық күрделілікті алуға тырысады. Мұндағы қауіп мынада, бір немесе бірнеше ішкі шығыс тізбектері – көбінесе жеке PrCsLOC шығыстары – жалпы кілт ағыны арқылы байланыстырылуы және сызықтық алгебра көмегімен ашылуы мүмкін. Көбінесе мұндай жекпе-жек корреляциялық жекпе-жек немесе «бөліп ал және жең» деп аталады. Томас Зигенталер корреляциялық тәуелсіздікті дәл анықтауға болатынын және корреляциялық тәуелсіздік пен сызықтық күрделілік арасында айырбас бар екенін көрсетті.

Корреляцияны ашудың негізгі идеясы - генератордың шығысы мен оның құрамдастарының бірінің шығысы арасындағы кейбір корреляцияны табу. Содан кейін шығыс ретін байқау арқылы осы аралық шығыс туралы ақпаратты алуға болады. Осы ақпаратты және басқа корреляцияларды пайдалана отырып, генератор бұзылғанша басқа аралық шығыстарды жинауға болады.

Корреляциялық шабуылдар және олардың нұсқалары, мысалы, жылдам корреляциялық шабуылдар, көптеген PrCsLOC негізіндегі кілттер ағыны генераторларына қарсы сәтті қолданылды, бұл олардың арасында ымыраға келуді ұсынады. есептеу күрделілігіжәне тиімділік.

1.5.Псевдокездейсоқ сандардың құрылған тізбегін ашудың басқа әдістері туралы PgCsLOS

Негізгі ағын генераторларын бұзудың басқа жолдары бар. Сызықтық сәйкестік сынағы матрицалық әдісті пайдаланып шифрлау кілтінің кейбір ішкі жиынын табуға тырысады. Сондай-ақ, дұрыстыққа сәйкестік шабуылы бар. Сызықтық синдром алгоритмі шығу ретінің фрагментін пішінде жазу мүмкіндігіне негізделген. сызықтық теңдеу. Ең жақсы аффинді жуықтау шабуылы және туынды реттілік шабуылы бар. Дифференциалды және сызықтық криптоталдау әдістерін ағындық шифрларға да қолдануға болады.

2. Псевдокездейсоқ реттілік генераторы ретінде PrCsLOS бағдарламалық қамтамасыз етуді жүзеге асыру сипаттамасы

2.1 Алгоритмнің жалпылама схемасы

2.2 Программалық модульдер мен интерфейстің сипаттамасы

Төмендегі 3-суретте бағдарлама терезесі көрсетілген.

Сурет бағдарламасының интерфейсі

Мәзірде бар келесі мүмкіндіктер:

Файл->Есепті сақтау

Бұл функция есеп файлын жасайды, мұнда PrCsLOS бастапқы күйі, түрту тізбегі, алынған жалған кездейсоқ бит тізбегінің периоды, тізбектің өзі және күй кестесі жазылады. Егер файл сәтті сақталған болса, сәтті сақтау туралы хабарлама көрсетіледі (4-сурет). Есепке ұсынылатын файл кеңейтімі *.жазу.

Сурет салу

Файл->Шығу

Бұл функция қолданбаның жабылуын қамтамасыз етеді.

Шығу ретін орнатыңыз

Бұл функция экран пішінінде пайдаланушы белгілеген ұяшықтардағы мәндерді оқу арқылы түрту тізбегін жасайды. Осыдан кейін ол пайдаланушыны түрту тізбегін құру туралы хабарлайды (5-сурет). Түрту реті қай ауысым регистрінің флип-флоптары кері байланыс алатынын анықтайды. XOR офсеттік бит құру үшін. Әдепкі бойынша, бірінші триггерден кері байланыс әрқашан қосулы болады, басқа қосылымдар болмаған жағдайда, ең аз маңызды биттің ең маңызды позициясына өзгеруімен солға жылжу орындалады.

Сурет салу

Бастапқы мәнді орнатыңыз

Бұл функция терезеден пайдаланушы енгізген регистрдің бастапқы мәнін оқидыӨңдеу 1 және енгізілген мәнді көрсетілген шарттар бойынша тексереді: енгізілген жол бос емес (6-сурет), енгізілген жолдың ұзындығы сегіз (8бит=1байт, 7-сурет), енгізілген жолда тек нөлдер және/немесе бір (8-сурет), енгізілген жол нөлге тең емес (9-сурет). В әйтпесеқате туралы хабарлар көрсетіледі, пайдаланушы оларды түзетіп, түймені қайтадан басу керек. Тексеру сәтті өткен жағдайда бастапқы мән күй кестесіне «Бастапқы» жолында жазылады және хабарлама беріледі (10-сурет).

Сурет салу

Регистрді ауыстыруды орындаңыз

Бұл функция ауысым регистрінің жұмысын эмуляциялайды. Кездейсоқ 256 ауысым жасай отырып, әрбір ауысым жалған кездейсоқ тізбектің шығыс битін және регистрдің жаңа күйін жасайды. Тізілімнің күйі бастапқы күйіне тең болған кезде кезең есептеледі және өрісте көрсетіледіжадынама 1 псевдокездейсоқ реттілік алынды.

Анықтама-> туралы

Бұл функция көрсетіледі қысқаша сипаттамасыбағдарламалар мен нұсқаулар (11-сурет).

Сурет салу

Анықтама-> Автор туралы

Бұл функция бағдарлама авторы туралы ақпаратты көрсетеді (12-сурет).

Сурет салу

2.3 Пайдаланушы нұсқаулығы

Алдымен регистрдің бастапқы күйін орнатыңыз. Ол сегіз екілік таңбадан тұруы керек. Әйтпесе, қате туралы хабар шығады және енгізілген мәнді түзетуге тура келеді. «Бастапқы мәнді орнату» мәзір тармағын басыңыз.
Содан кейін кері байланыстарды тіркеу үшін құсбелгілерді қойыңыз (Тәртіпті түртіңіз). «Түрту ретін орнату» мәзір тармағын басыңыз.
Әрі қарай, «Register Shift» мәзір элементін басыңыз. Мұны істеу алдында 1 және 2-қадамдарды орындағаныңызға көз жеткізіңіз, әйтпесе бағдарламалық құрал қатесі орын алады.
Нәтижелерді алғаннан кейін «Файл->Есепті сақтау» мәзір тармағын басу арқылы оларды сақтауға болады. Мұны істеу алдында 1-3 қадамдарды орындағаныңызға көз жеткізіңіз, әйтпесе бағдарламалық құрал қатесі орын алады.
Анықтама алу үшін «Файл->Туралы», «Файл->Автор туралы» мәзір элементтерін басыңыз.
Регистрдің жұмысын түрту ретінің басқа мәндерімен және тізілімнің бастапқы күйімен көру үшін басқа параметрлерді енгізе отырып, 1-3-қадамдардағы қадамдарды ретімен қайталаңыз.

ҚОРЫТЫНДЫ

Бұл жұмыста RgCsLOS псевдокездейсоқ сандар генераторлары ретінде қарастырылды. Бағдарлама сызықтық кері байланысы бар ауысымдық регистрлердің жұмыс істеу принциптерін көрнекі демонстрациялау ретінде қызмет ете алады XOR . Онда сіз биттердің псевдокездейсоқ тізбегін құру принципін, регистрдің бастапқы мәні мен псевдокездейсоқ тізбектің мәні, түрту тізбегі мен период арасындағы қатынасты зерттей аласыз. Алынған псевдокездейсоқ гамманы басқада қолдануға болады бағдарламалық қосымша(мысалы, гамма-шифрды бағдарламалық қамтамасыз ету).

Бүгінгі күні бұл регистрлер тәуелсіз жалған кездейсоқ сандар генераторлары ретінде пайдаланылмайды, бірақ күрделірек құрылғылардың бөлігі болып табылады. Дегенмен, олар математиканың жаңа бағыттарын ашты (шектік өрістерде қарабайыр көпмүшелерді іздеу, псевдокездейсоқ сандар генераторларын бұзудың математикалық әдістері). RgCsLOS бойынша генераторлардың жұмыс істеу принциптерін білмей, күрделірек құрылғылардың жұмысын түсіну мүмкін емес. Аппараттық қамтамасыз етудің қарапайымдылығына байланысты олар технологияда кеңінен қолданылады. PrCsOS зерттеулері регистрлердің осы түрлеріне (жылжымалы ауыстыру шифры,ТЖД және т.б.; ЭСҚ, хэш функциялары).

Жалпы алғанда, осы саладағы зерттеулер криптография мен криптоаналитиканың, компьютерлер мен құрылғылардың дамуына айтарлықтай түрткі болды, сонымен қатар басқа да бірқатар жобаларды жүзеге асыруға мүмкіндік берді. пайдалы мүмкіндіктер(мысалы, түзетуші циклдік кодтар).

ӘДЕБИЕТТЕР ТІЗІМІ

Шнайер Брюс. Қолданбалы криптография. Си тіліндегі хаттамалар, алгоритмдер, бастапқы мәтіндер. - М .: Триумф, 2002
Бабаш А.В. Қазіргі ақпараттық қауіпсіздіктің криптографиялық және автоматтық-теориялық аспектілері. 1-том – М.: Ред. Орталық EAOI, 2009. - 414 б.
Е.С. Селмер. Монография: «Ақырлы өрістегі сызықтық рекурсия». Берген университеті, Норвегия, 1966 ж.
Н.Цьерлер және Дж.Бриллхарт. «Примитивті триномиялар туралы Modulo 2», Ақпарат және бақылау журналы, 13-том № 6 желтоқсан 1968 ж., 541-544 беттер.
Қ.Х. Мейер және В.Л.Тучман. «Псевдокездейсоқ кодтарды бұзуға болады», Электрондық дизайн журналы, №. 23 қараша 1972 ж.
Дж.Л.Масси. «Ауысу регистрлерін жалпылау және Бозе-Чоудхури-Хоквингем кодының декодтауы»,Ақпарат теориясы бойынша IEEE транзакциялары, v. IT-15, n . 1 қаңтар 1969 жыл, 122-127 б.
С.У. Голомб. Shift Register Sequences, Сан-Франциско, Golden Day, 1967 (Aigean Park Press қайта басып шығарды, 1982).

Қосымша А

Кейбір қарабайыр көпмүшелердің кестесі 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)

Бастапқы күйді енгізу (IS)

енгізуді тексеру

Қате туралы хабарды шығару

Түрту ретін орнату

Күй кестесіне IP жазу

Жазба i -ші күй регистрі және күй кестесіне шығыс бит

IS==Ағымдағы күй

Нәтижелерді сақтау

Псевдокездейсоқ реттілік шығысы

Шығу

іске қосу

Иә

Жоқ

Кері байланысты ауыстыру тіркеліміекі бөліктен тұрады: ауысым регистрі және кері байланыс функциялары.

Сурет 19. Кері байланысты ауыстыру регистрі.

Жалпы алғанда, ауыстыру регистрі сақинаның немесе өрістің кейбір элементтерінің тізбегі болып табылады. Ең жиі қолданылады битауысым регистрлері. Мұндай регистрдің ұзындығы бит санымен өрнектеледі. Битті шығарған сайын регистрдегі барлық бит бір позицияға оңға жылжиды. Жаңа ең маңызды бит регистрдегі барлық басқа биттердің функциясы ретінде есептеледі. Шығару әдетте ең аз маңызды бит болып табылады. Ауысым регистрінің периоды - бұл қайталану басталғанға дейінгі шығыс ретінің ұзақтығы.

Ауысым регистрлерінің ең қарапайым түрі кері байланыстың сызықты ауысу регистрі (LFSR немесе LRS). Кері байланыс – регистрдің кейбір биттері бойынша қарапайым XOR операциясы. Бұл биттердің тізімі анықталған сипаттамалық көпмүшежәне шақырды түрту реті. Кейде бұл схема деп аталады Фибоначчи конфигурациясы.

20-сурет. Fibonacci конфигурациясының LFOS.

LFSR бағдарламалық қамтамасыз етуді іске асыруда модификацияланған схема қолданылады: жаңа маңызды разрядты генерациялау үшін түрткі реттілігінің биттерін пайдаланудың орнына оның әрбір битінде генератордың шығысымен XOR операциясы орындалады, ескісін ауыстырады. түрту реттілігінің бір бөлігі. Бұл модификация кейде деп аталады Галуа конфигурациясы.

21-сурет. Галуа конфигурациясының RLOS.

n-бит LFSR 2-нің біреуінде болуы мүмкін n– 1 ішкі күй. Бұл теориялық тұрғыдан мұндай регистр 2 периоды бар псевдокездейсоқ тізбекті құра алатынын білдіреді. n– 1 бит (нөлдермен толтыру мүлдем пайдасыз). Барлығының өтуі 2 n– 1 ішкі күй белгілі бір түрту ретімен ғана мүмкін. Мұндай регистрлер максималды периоды бар LFSR деп аталады. LFSR максималды периодын қамтамасыз ету үшін оның сипаттамалық көпмүшелік болуы қажет қарапайыммодуль 2. Көпмүшенің дәрежесі - жылжу регистрінің ұзындығы. Қарапайым дәрежелі көпмүше n- осындай азайтылмайтынбөлгіш болып табылатын, бірақ бөлгіш емес көпмүше x dБарлығы үшін + 1 d 2-нің бөлгіштері n– 1. (Көпмүшелерді талқылағанда, термин жай сантерминімен ауыстырылады келтірілмейтін көпмүше). LFSR сипаттамалық полиномы суреттерде көрсетілген:

x 32 + x 7 + x 5 + x 3 + x 2 + x + 1

қарабайыр модуль 2. Мұндай регистрдің периоды максимум болады, олар қайталанғанша барлық 2 32 - 1 мәндер арқылы циклді өтеді. Ең жиі қолданылатындар жіңішкерілген көпмүшелер, яғни. тек кейбір коэффициенттері бар. ең танымал үш мүшелер.

Маңызды параметр RLSS негізіндегі генератор болып табылады сызықтық күрделілік. Ол ұзындығы ретінде анықталады nгенератордың шығысын имитациялай алатын ең қысқа LFSR. Сызықтық күрделілік маңызды, өйткені қарапайым Берленкамп-Масси алгоритмітек 2-ні тексеру арқылы мұндай LFSR қайта құруға болады nгамма биттері. Қажетті LFSR анықтамасымен ағындық шифр шын мәнінде бұзылған.

LFSR-ден басқа сызықты емес кері байланысы бар ауыспалы регистрлер, тасымалдау кері байланысы және т.б.

Сандық-теориялық тәсіл негізінде бірқатар генераторлар жасалды (Блум-Микали генераторлары, RSA, BBS, компрессиялық, аддитивті генераторлар және т.б.).

Блоктық криптографиялық алгоритмдермен салыстырғанда ағындық криптографиялық алгоритмдердің синтезінің математикалық қамтамасыз етілуі толық және егжей-тегжейлі әзірленді. Дегенмен, ағындық шифрларды жасау үшін OFB немесе CFB режимдеріндегі блоктық шифрлау алгоритмдері жиі қолданылады.

Кері байланысты ауыстыру тіркелімі ( FSR ) екі бөліктен тұрады: ауысым тіркеліміжәне кері байланыс функциялары .

Shift регистрі (Қате: Анықтама көзі табылмады) биттердің тізбегі болып табылады. Битті шығару қажет болғанда, ауыстыру регистрінің барлық разрядтары оңға 1 позицияға жылжытылады. Жаңа сол жақ бит регистрдегі қалған биттерден кері байланыс функциясының мәні болып табылады. Кезең Ауысым регистрі - нәтиже ретінің қайталана бастағанға дейінгі ұзындығы.

Кері байланысты ауыстыру регистрінің қарапайым түрі болып табылады Кері байланысы бар сызықтық ығысу регистрі (LFSR – Сол Кері байланыс Shift Тіркелу) (Қате: Анықтама көзі табылмады). Кері байланыс кейбір p биттерінің XOR көрсеткіші болып табылады. регистр, осы биттердің тізімі шақырылады айналып өту реті.

n-бит LFSR бірінде болуы мүмкін 2 n -1 ішкі мемлекеттер. Бұл теориялық тұрғыдан мұндай регистр периодты псевдокездейсоқ тізбекті құра алады дегенді білдіреді. 2 n -1 бит. Ішкі күйлердің саны мен период тең, өйткені регистрді нөлдермен толтыру оның нөлдердің шексіз тізбегін тудыруы мүмкін, бұл мүлдем пайдасыз. Белгілі бір түрту ретімен ғана LFSR барлығын айналдырады 2 n -1 ішкі мемлекеттер. Мұндай LFSR деп аталады LFSRмаксималды кезеңмен.

Белгілі бір LFSR үшін максималды период болуы үшін көпмүше кран тізбегінен және тұрақтыдан құралады 1 қарапайым модуль болуы керек 2 .

Көпмүшенің қарапайымдылығын есептеу өте күрделі математикалық есеп. Сондықтан генератордың максималды кезеңін қамтамасыз ететін кран реттілігінің нөмірлерін тізімдейтін дайын кестелер бар. Мысалы, 32-биттік ауысым регистрі үшін келесі жазбаны таба аласыз: (32,7,5,3,2,1,0) . Бұл жаңа бит генерациялау үшін XOR функциясы арқылы отыз екінші, жетінші, бесінші, үшінші, екінші және бірінші биттерді қосу керек дегенді білдіреді.

C++ тілінде мұндай LFSR коды келесідей болады:

// Нөлден басқа кез келген мән

ShiftRegister = ((((ShiftRegister >> 31)

^(ShiftRegister>>6)

^(ShiftRegister>>4)

^(ShiftRegister>>2)

^(ShiftRegister>>1)

^ShiftRegister)

& 0x00000001)<<31)

| (ShiftRegister >> 1);

ShiftRegister қайтару & 0x00000001;

LFSR бағдарламалық қамтамасыз етуді іске асыру өте баяу және олар C емес, ассемблерде жазылған болса, жылдамырақ жұмыс істейді. Бір шешім - 16 LFSR параллельді пайдалану (немесе белгілі бір компьютердің архитектурасындағы сөз ұзындығына байланысты 32). Бұл схемада көлемі LFSR ұзындығына тең сөздер массиві пайдаланылады және массивтегі сөздің әрбір бірлігі өзінің LFSR-ге сілтеме жасайды. Бірдей түрту реттік нөмірлері пайдаланылған жағдайда, бұл айтарлықтай өнімділікті арттыруы мүмкін.

МЕН кері байланыс схемасын да өзгертуге болады. Бұл жағдайда генератор үлкен криптографиялық күшке ие болмайды, бірақ оны бағдарламалық түрде жүзеге асыру оңайырақ болады. Жаңа битті генерациялау үшін түрту тізбегі биттерінің ең сол жақ битін пайдаланудың орнына генератордың шығысымен түрту тізбегінің әрбір битін XOR және оны осы әрекеттің нәтижесімен ауыстырыңыз, содан кейін генератордың нәтижесі ең жаңа сол жақ бит болады. бит (Қате: сілтеме көзі табылмады).

Бұл модификация деп аталады Галуа конфигурациясы. Си тілінде ол келесідей көрінеді:

статикалық қолтаңбасыз ұзын ShiftRegister = 1;

жарамсыз тұқым_LFSR (қолтаңбасы жоқ ұзын тұқым)

ShiftRegister = тұқым;

int Galua_LFSR(жарамсыз)

егер (ShiftRegister және 0x00000001) (

ShiftRegister = (ShiftRegister ^ маскасы >> 1) | 0x8000000;

ShiftRegister >>= 1;

Төлем - барлық XOR бір операцияда орындалады. Бұл тізбекті параллельдеуге де болады.

Өздігінен LFSR жақсы псевдокездейсоқ реттілік генераторлары болып табылады, бірақ олардың кейбір жағымсыз кездейсоқ емес қасиеттері бар. Тізбектелген биттер сызықты, сондықтан оларды шифрлау үшін жарамсыз етеді. LFSR ұзындығы үшін nішкі күй алдыңғыны білдіреді nгенератордың шығыс биттері. Кері байланыс схемасы құпия сақталса да, оны анықтауға болады 2 nарнайы алгоритмдерді пайдалана отырып, генератордың шығыс биттері. Бұған қоса, осы тізбектің дәйекті биттерін пайдаланып жасалған үлкен кездейсоқ сандар жоғары корреляцияға ие және қолданбалардың кейбір түрлері үшін кездейсоқ емес. Осыған қарамастан, LFSR шифрлау алгоритмдерін жасау үшін жиі қолданылады. Бұл үшін әдетте әртүрлі ұзындықтары мен реттік нөмірлері бар бірнеше LFSR пайдаланылады. Кілт регистрлердің бастапқы күйі болып табылады. Жаңа бит қажет болған сайын барлық регистрлер ауыстырылады. Бұл операция деп аталады сағаттау. Шығыс биті LFSR кейбір биттерінің функциясы, жақсырақ сызықты емес. Бұл функция деп аталады біріктіру, және жалпы генератор - біріктіруші генератор. Бұл генераторлардың көпшілігі бүгінгі күнге дейін қауіпсіз.

Кері байланысты ауыстыру регистрі (бұдан әрі – PgCsOS) екі бөліктен тұрады: ауысу регистрі және кері байланыс функциясы. Ауыстыру регистрі биттердің тізбегі болып табылады. Биттер саны анықталады ауыстыру регистрінің ұзындығы, ұзындығы n бит болса, онда регистр шақырылады n-разрядты ауыстыру регистрі. Битті шығару қажет болғанда, ауыстыру регистрінің барлық биттері 1 позицияға оңға жылжиды. Жаңа сол жақ бит регистрдегі барлық басқа биттердің функциясы болып табылады. Ауысым регистрінің шығысы бір, әдетте ең аз маңызды бит болып табылады. Ауысым регистрінің кезеңі- нәтиже ретінің қайталана бастағанға дейінгі ұзындығы.

Сурет 1. Кері байланысты ауыстыру регистрі

Shift регистрлері ағындық шифрларда тез қолданылды, өйткені олар сандық аппараттық құралдар арқылы оңай жүзеге асырылды. 1965 жылы Норвегия үкіметінің бас криптографы Эрнст Селмер ауысым регистрінің реттілік теориясын жасады. NSA математигі Соломон Голомб өзінің және Селмердің кейбір нәтижелерін сипаттайтын кітап жазды. Кері байланысты ауыстыру регистрінің ең қарапайым түрі – сызықтық кері байланысты ауыстыру регистрі (LFSR немесе PrCsLOS). Мұндай регистрлердің кері байланысы регистрдің кейбір биттерінің жай ғана XOR (модульді екі қосу) болып табылады, бұл биттердің тізімі түрту тізбегі деп аталады. Кейде мұндай регистрді Фибоначчи конфигурациясы деп атайды. Кері байланыс реттілігінің қарапайымдылығына байланысты PgCsLOC талдау үшін жеткілікті дамыған математикалық теорияны қолдануға болады. Алынған шығыс тізбектерін талдау арқылы бұл реттіліктердің қауіпсіз болуы үшін жеткілікті кездейсоқ екенін тексеруге болады. Ауысым регистрлері криптографияда басқа ауысым регистрлеріне қарағанда жиі қолданылады.

2-сурет

Жалпы, n-разрядты PrCsLOS N=2 n -1 ішкі күйлердің бірінде болуы мүмкін. Бұл теориялық тұрғыдан мұндай регистр периоды T=2 n -1 бит псевдокездейсоқ тізбекті құра алады дегенді білдіреді. (Ішкі күйлердің саны және период N=T max =2 n -1, өйткені PrCsLOS-ті нөлдермен толтыру ауысым регистрінен нөлдердің шексіз тізбегін шығарады, бұл мүлдем пайдасыз). Тек белгілі бір түрту реттілігімен PrCsLOS барлық 2 n -1 ішкі күйлер арқылы айналады, мұндай PrCsLOS Максималды кезеңмен RgSsLOS. Алынған нәтиже шақырылады M-тізбегі.

Мысал . Төмендегі суретте бірінші және төртінші биттердің түртуі бар 4-биттік PrCsLOS көрсетілген. Егер ол 1111 мәнімен инициализацияланса, онда регистр қайталамас бұрын келесі ішкі күйлерді қабылдайды:

Жылжыту белгісінің нөмірі (ішкі күй)	Тіркелу күйі	шығыс биті

Бастапқы мән














15 (бастапқы күйге оралу)
16 (қайталау күйі)

Шығару тізбегі ең аз маңызды биттердің жолы болады: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 периодпен T=15, мүмкін болатын ішкі күйлердің жалпы саны (нөлден басқа), N=2 4 -1 =16-1= 15=T max , сондықтан шығыс реті M-тізбегі болып табылады.

Белгілі бір PgCsLOS максималды периодқа ие болуы үшін түрткі тізбегінен жасалған көпмүше және 1 тұрақтысы қарабайыр модуль 2 болуы керек. Көпмүше дәрежелердің қосындысы ретінде көрсетіледі, мысалы, n дәрежелі көпмүшелік ретінде көрсетіледі. мынадай:

а n xn+a n-1 x n-1 + … +a 1 x 1 +a 0 x 0 =a n xn+a n-1 x n-1 + … +a 1 x+a 0 , мұндағы а мен =(0,1) i=1…n үшін, a x i - цифрды көрсетеді.

Көпмүшенің дәрежесі - жылжу регистрінің ұзындығы. n дәрежелі қарабайыр көпмүше x 2n?1 +1 бөлгіші болып табылатын, бірақ 2n -1 бөлгіштері болып табылатын барлық d үшін x d +1 бөлгіші болып табылмайтын азайтылмайтын көпмүше. Сәйкес математикалық теорияны мына жерден табуға болады.

Жалпы алғанда, модуль 2 берілген дәрежедегі қарабайыр көпмүшелерді құрудың оңай жолы жоқ. Ең оңай жолы – көпмүшені кездейсоқ таңдау және оның қарабайыр екенін тексеру. Бұл оңай емес және кездейсоқ таңдалған санның жай емес екенін тексеру сияқты, бірақ көптеген математикалық бағдарламалық қамтамасыз ету пакеттері бұл мәселені шеше алады.

(32, 7, 5, 3, 2, 1, 0) келесі көпмүшеліктің 2-қарабайыр модуль екенін білдіреді: x 32 + x 7 + x 5 + x 3 + x 2 + x + 1.

Мысалды жалғастыра отырып, жазу (32, 7, 5, 3, 2, 1, 0) берілген 32-разрядты регистр үшін отыз екінші, жетінші, бесінші, үшінші, екінші XORing арқылы жаңа бит жасалатынын білдіреді. , және бірінші биттер, нәтижесінде алынған RgCsLOS максималды ұзындыққа ие болады, қайталау үшін 2 32 -1 мәндері арқылы цикл өтеді.

Сурет 4. Максималды ұзындығы бар 32-биттік PrCsLOS

PgCsLOS программалық кодын қарастырайық, онда түрту тізбегі полиноммен сипатталады (32, 7, 5, 3, 2, 1, 0). Си тілінде ол келесідей көрінеді:

статикалық қолтаңбасыз ұзын ShiftRegister = 1;

/* 0-ден басқа кез келген нәрсе. */

ShiftRegister = ((((ShiftRegister >> 31)

^(ShiftRegister >> 6)

^(ShiftRegister >> 4)

^(ShiftRegister >> 2)

^(ShiftRegister >> 1)

^ShiftRegister))

| (ShiftRegister >> 1);

ShiftRegister & 0x00000001 қайтару;)

Ауысым регистрі компьютер сөзінен ұзағырақ болса, код күрделене түседі, бірақ көп емес. В қосымшасында кейбір қарабайыр көпмүшелердің модулі 2 кестесі бар, біз оны кейінірек осы көпмүшелердің кейбір қасиеттерін анықтау үшін, сондай-ақ түрту тізбегін орнату үшін бағдарламалық құралды іске асыруда қолданамыз.

Егер p(x) қарабайыр болса, онда x n p (1/x) солай болады, сондықтан кестенің әрбір элементі шын мәнінде екі қарабайыр көпмүшені анықтайды. Мысалы, егер (a, b, 0) қарабайыр болса, онда (a, a-b, 0). Егер (a, b, c, d, 0) қарабайыр болса, онда (a, a-d, a-c, a-b, 0). Математикалық:

егер x a +x b +1 қарабайыр болса, онда x a +x a-b +1,

егер x a +x b +x c +x d +1 қарабайыр болса, x a +x a-d +x a-c +x a-b +1 де солай болады. Қарапайым үш мүшелер бағдарламалы түрде жүзеге асырылатын ең жылдам болып табылады, өйткені жаңа разрядты генерациялау үшін ауысым регистрінің тек екі битін XOR жасау керек (нөлдік термин ескерілмейді, яғни x 0 \u003d 1, жоғарыдағы мысалды қараңыз). Шынында да, кестеде келтірілген кері байланыс көпмүшелерінің барлығы сирек, яғни олардың коэффициенттері аз. Сиректік әрқашан әлсіздік көзі болып табылады, бұл кейде алгоритмді ашу үшін жеткілікті. Криптографиялық алгоритмдер үшін коэффициенттері көп тығыз қарабайыр көпмүшелерді қолданған әлдеқайда тиімді. Тығыз көпмүшелерді пайдалану арқылы, әсіресе кілттің бөлігі ретінде, әлдеқайда қысқа PrCcLOC пайдалануға болады.

Тығыз қарабайыр көпмүшелердің модулі 2 құру оңай емес. Жалпы, k дәрежелі қарабайыр көпмүшелерді құру үшін 2 k -1 санын көбейткіштерге бөлуді білу керек.

Бұған қоса, осы тізбектің дәйекті биттерін пайдаланып жасалған үлкен кездейсоқ сандар жоғары корреляцияға ие және қолданбалардың кейбір түрлері үшін мүлдем кездейсоқ емес. Осыған қарамастан, PrCsLOS жиі шифрлау алгоритмдерін жүйелердің және шифрлау алгоритмдерінің құрамдас бөліктері ретінде жасау үшін қолданылады.