Кері байланысы бар регистрлерді ауыстыру. Жұмыстың теориялық негізі Сызықтық кері байланыс
Сызықтық жылжу регистрі c кері байланыс(Linear Feedback Shift Register – LFSR) – екілік биттердің псевдокездейсоқ тізбегін құру механизмі. Регистр (1-сурет) инициализация векторымен (көбінесе құпия кілт) орнатылған ұяшықтар санынан тұрады. Регистрдің жұмысы кері байланысқа әрбір разрядтың қосылуының болуымен немесе болмауымен анықталады. Кері байланыс тіркелімінің түртулері бекітілмеген, бірақ кілттің бөлігі болып табылады. Келесі қадамда регистр ұяшықтарының мазмұны бір орынға оңға жылжытылады және XOR операциясының нәтижесінде бос қалған бір бит сол жақ ұяшыққа орналастырылады.
Күріш. бір. Сызықтық регистркері байланыстың ауысуы
Максималды шифр гамма кезеңіне қол жеткізу үшін цифрлар саны мауысым регистрі Mersenne жай сандарының (2, 3, 5, 7, 13, 17, 31, 61, 89, 107, 127, 521, 607, 1279, 2203 ...) және ішкі сілтемелердің бірі ретінде таңдалған. регистрдің ең жоғары дәрежелі қысқартылмайтын қарабайыр көпмүшеліктерге сәйкес таңдалуы керек м. Бұл жағдайда шифрдың гамма кезеңі (2 м-1).
LFSR бағдарламалық жасақтамада да, аппараттық құралда да жылдам және оңай жүзеге асырылады. Кері байланыс биттерін дұрыс таңдаған кезде жасалған реттіліктер жақсы статистикалық қасиеттерге ие болады. LFSR ретінде пайдаланылады базалық элементжоғары қауіпсіз жүйелерді құруға арналған.
Регистрлер каскады – бір LFSR әрекеті каскадтағы алдыңғы LFSR әрекетіне тәуелді болатындай байланысқан LFSR жиынтығы. Бұл «тәуелді» әрекет әдетте бірінші LFSR арқылы келесі LFSR ауысым есептегішін басқару үшін орнатылады.
Мысалы, егер алдыңғы регистрдің мәні 1 болса, регистр бір қадамға ауыстырылады, ал егер мән 0 болса, онда регистр екі қадамға немесе басқаша жылжиды. Үлкен саныМұндай комбинациялар өте жоғары қауіпсіздікті қамтамасыз етеді.
Ең қауіпсіз тізбектер екі LFSR регистрлерінің нәтижелері арасындағы қарапайым әрекеттесу негізінде кішірейетін генератор арқылы жасалады. Бір нәтиженің биттері екінші нәтиженің сәйкес биттері толық «ағындық кілттің» бөлігі ретінде пайдаланылатынын анықтайды. Сығымдау генераторы қарапайым, масштабталады және жақсы қауіпсіздік қасиеттеріне ие. Оның кемшілігі, кейбір сақтық шаралары қабылданбайынша, «ағындық кілтті» жасау жылдамдығы тұрақты болмайды.
Кешігумен Фибоначчи әдісіКеңінен қолданылатын Фибоначчи генераторларының бірі келесі итеративті формулаға негізделген:
қайда Ы к - нақты сандарауқымнан тыс
Күріш. 2. Айналмалы шифрлау
DES шығыс кері байланыс режимі псевдокездейсоқ сандарды генерациялау үшін пайдаланылуы мүмкін. ағынды шифрлау. Әрбір шифрлау кезеңінің шығысы 64 биттік мән болып табылады, оның тек жоғарғы j биттері шифрлау үшін қайтарылады. 64-биттік шығыстар жақсы статистикалық қасиеттері бар псевдокездейсоқ сандар тізбегін құрайды.
ANSI X9.17 стандартында сипатталған псевдокездейсоқ сандар генераторы криптографиялық қауіпсіз псевдокездейсоқ сандар генераторларының бірі болып табылады. Бұл технологияны пайдаланатын қолданбаларға қаржылық қауіпсіздік және PGP қолданбалары кіреді.
ANSI X9.17 генераторы келесі бөліктерден тұрады (3-сурет):
1. Кіріс: генератор екі псевдокездейсоқ кіріспен басқарылады. Бірінші кіріс ағымдағы күн мен уақыттың 64 биттік көрінісі ( DT i) сан жасалған сайын өзгеретін. Екінші кіріс 64-биттік бастапқы мән болып табылады, ол қандай да бір еркін мәнге инициализацияланады және жалған кездейсоқ сандар тізбегін құру кезінде өзгереді ( Vi).
2. Кілттер: Генератор екі кілт K 1 , K 2 бар үш үштік DES модулін пайдаланады. Үшеуі бірдей 56-биттік кілттер жұбын пайдаланады, ол құпия сақталуы керек және тек жалған кездейсоқ санды жасау үшін ғана пайдаланылады.
| EDE |
| EDE |
| EDE |
| + |
| + |
| K1, K2 |
| DT i |
| Vi |
| R i |
| V i+1 |
3. Шығару: шығыс 64 биттік жалған кездейсоқ саннан R i және келесі санды ( Vi +1) .
Күріш. 3. ANSI X9.17 псевдокездейсоқ сандар генераторы
Кері байланысты ауыстыру тіркеліміекі бөліктен тұрады: ауысым регистрі және кері байланыс функциялары.
Сурет 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 г 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 анықтамасымен ағындық шифр шын мәнінде бұзылған.
Кері байланысты ауыстыру тіркелімі ( 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 кейбір биттерінің функциясы, жақсырақ сызықты емес. Бұл функция деп аталады біріктіру, және жалпы генератор - біріктіруші генератор. Бұл генераторлардың көпшілігі бүгінгі күнге дейін қауіпсіз.
Сызықтық кері байланысты ауыстыру тіркелімі(RSLOS, ағыл. сызықтық кері байланыстың ығысу регистрі, LFSR ) – бит сөзін ауыстыру регистрі, онда кіріс (енгізілген) разрядтың мәні жылжу алдындағы регистрдің қалған биттерінің мәндерінен сызықтық логикалық функцияға тең. Оны бағдарламалық және аппараттық құралдар арқылы ұйымдастыруға болады. Ол, атап айтқанда, криптографияда қолданылатын псевдокездейсоқ тізбектерді биттерді құру үшін қолданылады.
Сипаттама
Аппараттық құралдарды іске асыруда тізілімді басқару ауысым импульсін қолдану арқылы орындалады (басқаша деп аталады сағатталғаннемесе синхрондау импульсі) барлық ұяшықтар үшін. Бағдарламалық қамтамасыз етуді іске асыруда тізілімді басқару циклды орындау арқылы орындалады. Циклдің әрбір итерациясында кері байланыс функциясы есептеледі және сөздегі разрядтар ауыстырылады.
Жұмыс принципі
Сызықтық күрделілік
Корреляциялық тәуелсіздік
Жасалған тізбектің жоғары сызықтық күрделілігін алуға тырысып, криптографтар бірнеше ауысым регистрлерінің шығыстарын сызықты емес біріктіреді. Бұл жағдайда бір немесе бірнеше шығыс тізбегі (немесе тіпті жеке LFSR шығыстары) жалпы ағынмен қосылуы және криптоаналитикпен ашылуы мүмкін. Мұндай осалдыққа негізделген хакерлік деп аталады корреляцияның ашылуы. Мұндай бұзудың негізгі идеясы - генератордың шығысы мен оның шығыстары арасындағы кейбір корреляцияны табу. құрамдас бөліктер. Содан кейін шығу ретін байқау арқылы осы аралық шығыстар туралы ақпаратты алуға болады, осылайша генераторды бұзуға болады. Томас Зигенталер корреляциялық тәуелсіздікті дәл анықтауға болатынын және корреляциялық тәуелсіздік пен сызықтық күрделілік арасында айырбас бар екенін көрсетті.
Бағдарламалық қамтамасыз етуді енгізу
RSLOS бағдарламалық жасақтамасының іске асырылуы айтарлықтай баяу және ассемблерде жазылған болса, жылдамырақ жұмыс істейді. Шешімдердің бірі 16 RLLS (немесе компьютер архитектурасындағы сөз ұзындығына байланысты 32) параллельді қолдану болып табылады. Мұндай схемада көлемі ауысым регистрінің ұзындығына тең сөздер массиві пайдаланылады және сөздің әрбір биті өзінің LFSR-ге сілтеме жасайды. Кран реттілігінің бірдей саны пайдаланылғандықтан, бұл генератордың өнімділігін айтарлықтай арттыруға мүмкіндік береді.
Фибоначчи конфигурациясы
32-разрядты ауыстыру регистрін қарастырайық. Оның қашу реті бар (32 , 31 , 30 , 28 , 26 , 1) (\displaystyle \left(32,\;31,\;30,\;28,\;26,\;1\оң жақ)). Бұл жаңа разрядты генерациялау үшін XOR операциясының көмегімен 31, 30, 29, 27, 25 және 0 биттерді қосу керек дегенді білдіреді. Алынған LFSR максималды кезеңге ие 2 32 − 1 (\displaystyle 2^(32)-1). Си тіліндегі мұндай регистрдің коды келесідей:
int LFSR_Fibonacci (жарамсыз ) ( статикалық таңбасыз ұзын S = 0x00000001 ; S = (((S >> 31 ) ^ (S >> 30 ) ^ (S >> 29 ) ^ (S >> 27 ) ^ (S >> 25) ^ S) & 0x00000001)<< 31 ) | (S >> 1); қайтару S & 0x00000001; )
Галуа конфигурациясы
Бұл генератор үлкен криптографиялық күшке ие емес, бірақ ол өнімділікті арттырады: барлық XOR операцияларын Fibonacci конфигурациясындағыдай бірінен соң бірі бірізді емес, параллелизация арқылы бір операцияда орындауға болады. Бұл схемасондай-ақ аппараттық қамтамасыз етуді енгізуде пайда әкеледі.
Си тіліндегі 32-разрядты ауыстыру регистрінің коды келесідей:
int LFSR_Galois (жарамсыз) ( статикалық қолтаңбасыз ұзын S = 0x00000001 ; егер (S & 0x00000001 ) ( S = (S ^ 0x80000057 >> 1 ) | 0x80000000 ; қайтару S = 1 >> ;) ; басқа қайтару ;) ;) )
Galois конфигурациясындағы LFSR_Galois функциясына қоңыраулардың тіркелген санының циклі Fibonacci конфигурациясындағы LFSR_Fibonacci функциясынан шамамен 2 есе жылдам орындалатынын атап өткен жөн (Intel Core i5 жүйесіндегі MS VS 2010 компиляторы).
Жасалған реттілік мысалы
Фибоначчи конфигурациясы
LFSR сипаттамалық көпмүшелік арқылы берілсін x 3 + x + 1 (\displaystyle x^(3)+x+1). Бұл түрткіш биттердің 2-ші және 0-ші болатынын білдіреді, ал полиномдық формуладағы бірлік 0-ші бит кіріс екенін білдіреді. Кері байланыс функциясының пішіні бар S j = S j - 1 ⊕ S j - 3 (\displaystyle S_(j)=S_(j-1)\oplus S_(j-3)). Ауысым регистрінің бастапқы күйі реттілік болды делік. Тізілімнің қосымша күйлері төмендегі кестеде көрсетілген:
| Қадам нөмірі | Мемлекет | Бит жасалды |
|---|---|---|
| 0 | [ 0 , 0 , 1 ] (\displaystyle \сол жақта) | 1 |
| 1 | 0 | |
| 2 | 0 | |
| 3 | 1 | |
| 4 | 1 | |
| 5 | 1 | |
| 6 | 0 | |
| 7 | [ 0 , 0 , 1 ] (\displaystyle \сол жақта) | 1 |
Жетінші қадамдағы ішкі күй бастапқы күйіне оралғандықтан, келесі қадамнан бастап биттер қайталанады. Сонымен, құрылған реттілік: [ 1 , 0 , 0 , 1 , 1 , 1 , 0 , 1 . . . ] (\дисплей стилі\сол)(разрядтағы биттердің реті олардың LFSR жасаған ретіне сәйкес келеді). Осылайша, тізбектің периоды 7-ге тең, яғни берілген көпмүшенің қарабайырлығына байланысты болған максималды мүмкін мән.
Галуа конфигурациясы
Сол сипаттамалық көпмүшені алайық, яғни c 3 = c 1 = 1 (\displaystyle c_(3)=c_(1)=1), c2 = 0 (\displaystyle c_(2)=0). Шығыс битке тек 1-ші бит қосылады. Бастапқы күйі бірдей. Тізілімнің келесі мемлекеттері:
| Қадам нөмірі | Мемлекет | Бит жасалды |
|---|---|---|
| 0 | [ 0 , 0 , 1 ] (\displaystyle \сол жақта) | - |
| 1 | [ 1 , 0 , 0 ] (\displaystyle \сол жақта) | 0 |
| 2 | [ 0 , 1 , 1 ] (\displaystyle \сол жақта) | 1 |
| 3 | [ 1 , 0 , 1 ] (\displaystyle \сол жақта) | 1 |
| 4 | [ 1 , 1 , 1 ] (\displaystyle \сол жақта) | 1 |
| 5 | [ 1 , 1 , 0 ] (\displaystyle \сол жақта) | 0 |
| 6 | [ 0 , 1 , 0 ] (\displaystyle \сол) | 0 |
| 7 | [ 0 , 0 , 1 ] (\displaystyle \сол жақта) | 1 |
Жетінші қадамдағы регистрдің ішкі күйі бастапқы күйіне оралды, сондықтан оның периоды да 7-ге тең. Фибоначчи конфигурациясынан айырмашылығы, регистрдің ішкі күйлері әртүрлі болып шықты, бірақ құрылған реттілік бірдей. , тек 4 циклге жылжыды: [ 0 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , . . . ] (\дисплей стилі\сол)(разрядтағы биттердің реті олардың LFSR жасаған ретіне сәйкес келеді).
Қарапайым көпмүшелерді құру
| бит, n (\displaystyle n) | Қарапайым көпмүше | кезең, 2 n − 1 (\displaystyle 2^(n)-1) | Қарапайым көпмүшелердің саны |
|---|---|---|---|
| 2 | x 2 + x + 1 (\displaystyle x^(2)+x+1) | 3 | 1 |
| 3 | x 3 + x 2 + 1 (\displaystyle x^(3)+x^(2)+1) | 7 | 2 |
| 4 | x 4 + x 3 + 1 (\displaystyle x^(4)+x^(3)+1) | 15 | 2 |
| 5 | x 5 + x 3 + 1 (\displaystyle x^(5)+x^(3)+1) | 31 | 6 |
| 6 | x 6 + x 5 + 1 (\displaystyle x^(6)+x^(5)+1) | 63 | 6 |
| 7 | x 7 + x 6 + 1 (\displaystyle x^(7)+x^(6)+1) | 127 | 18 |
| 8 | x 8 + x 6 + x 5 + x 4 + 1 (\displaystyle x^(8)+x^(6)+x^(5)+x^(4)+1) | 255 | 16 |
| 9 | x 9 + x 5 + 1 (\displaystyle x^(9)+x^(5)+1) | 511 | 48 |
| 10 | x 10 + x 7 + 1 (\displaystyle x^(10)+x^(7)+1) | 1023 | 60 |
| 11 | x 11 + x 9 + 1 (\displaystyle x^(11)+x^(9)+1) | 2047 | 176 |
| 12 | x 12 + x 11 + x 10 + x 4 + 1 (\displaystyle x^(12)+x^(11)+x^(10)+x^(4)+1) | 4095 | 144 |
| 13 | x 13 + x 12 + x 11 + x 8 + 1 (\displaystyle x^(13)+x^(12)+x^(11)+x^(8)+1) | 8191 | 630 |
| 14 | x 14 + x 13 + x 12 + x 2 + 1 (\displaystyle x^(14)+x^(13)+x^(12)+x^(2)+1) | 16383 | 756 |
| 15 | x 15 + x 14 + 1 (\displaystyle x^(15)+x^(14)+1) | 32767 | 1800 |
| 16 | x 16 + x 14 + x 13 + x 11 + 1 (\displaystyle x^(16)+x^(14)+x^(13)+x^(11)+1) | 65535 | 2048 |
| 17 | x 17 + x 14 + 1 (\displaystyle x^(17)+x^(14)+1) | 131071 | 7710 |
| 18 | x 18 + x 11 + 1 (\displaystyle x^(18)+x^(11)+1) | 262143 | 7776 |
| 19 | x 19 + x 18 + x 17 + x 14 + 1 (\displaystyle x^(19)+x^(18)+x^(17)+x^(14)+1) | 524287 | 27594 |
| 20 - 168 | |||
| 2 - 786, 1024, 2048, 4096 | |||
Артылықшылықтар мен кемшіліктер
Артықшылықтары
- LFSR негізінде құрылған криптографиялық алгоритмдердің жоғары өнімділігі (мысалы, ағындық шифрлар);
- барлық дерлік есептеу құрылғыларында аппараттық құралдарда іске асырылатын қосу және көбейтудің ең қарапайым разрядтық операцияларын ғана пайдалану;
- жақсы криптографиялық қасиеттер (LFSR жақсы статистикалық қасиеттері бар ұзақ мерзімді тізбектерді құра алады);
- құрылымына байланысты LFSR алгебралық әдістерді қолдану арқылы оңай талданады.
кемшіліктері
Жасалған тізбектердің криптографиялық беріктігін жақсарту жолдары
Бірнеше ауысым регистрлері бар генераторлар
Генератордың бұл түрі биттерді генерациялайтын бірнеше сызықтық кері байланысты ауыстыру регистрлерінен тұрады x 1 , i , x 2 , i , … , x M , i (\displaystyle x_(1,i),\;x_(2,i),\;\нүктелер,\;x_(M,i))тиісінше. Әрі қарай, генерацияланған биттер кейбір логикалық функция арқылы түрленеді f (x 1 , i , x 2 , i , … , x M , i) (\displaystyle f(x_(1,i),\;x_(2,i),\;\нүктелер ,\;x_(M) , мен))). Айта кету керек, осы типтегі генераторлардың регистрлік ұзындықтары бар L i (\displaystyle L_(i)), i = 1 , 2 , … , M (\displaystyle i=1,\;2,\;\нүктелер,\;M), бір-бірімен сәйкес келеді.
Бұл генератордың периоды T = (2 L 1 − 1) ⋅ (2 L 2 − 1) ⋯ (2 L M − 1) ≲ 2 L (\displaystyle T=(2^(L_(1))-1)\cdot (2^() L_(2))-1)\cdots (2^(L_(M))-1)\lesssim 2^(L)), қайда L = ∑ i = 1 M L i (\displaystyle L=\сома \шектері _(i=1)^(M)L_(i))- ұяшықтардың жалпы саны. Сондықтан, бірнеше LFSR пайдалану генератордың криптографиялық күшін арттыратын бір регистрмен салыстырғанда генерацияланған реттілік мерзімін арттырады. Ол сондай-ақ берілген генераторға сәйкес келетін сызықтық күрделілікті немесе ең қысқа регистрдің ұзындығын арттырады. Мұндай регистр генерацияланған тізбекті пайдаланып Берлекамп-Масси алгоритмі арқылы табылады. AT ең жақсы жағдайоның ұзындығы генерацияланған реттілік кезеңіне сәйкес келеді.
Сызықты емес түрлендірулері бар генераторлар
Мұндай генератордың құрылымдық схемасы алдыңғы генератордың схемасынан еш айырмашылығы жоқ. Негізгі айырмашылығы - түрлендіру құрылғысы сызықты емес логикалық функция арқылы беріледі f (x 1 , x 2 , … , x M) (\displaystyle f(x_(1),x_(2),\нүктелер,x_(M))). Мысалы, мұндай функция ретінде Жегалкин көпмүшесі алынады (Жегалкин теоремасы бойынша кез келген логикалық функцияЖегалкин көпмүшесімен бірегей түрде ұсынылуы мүмкін).
Сызықты емес генераторды да іске асыруға болады сызықты емес кері байланыс ығысу регистрі. Ол бере алады 2 2 L − 1 − L (\displaystyle 2^(2^(L-1)-L))реттілік нұсқалары максималды период , бұл LFSR-ден көп.
Бұл генератордың криптографиялық күші қолданылатын функцияның сызықты еместігіне байланысты артады. Генерацияланған разряд тізбегі бойынша регистрлердің күйін анықтау күрделі математикалық есеп болып табылады, өйткені бастапқы күйлерді қалпына келтіретін алгоритм белгілі емес.
Бұл әдіс, мысалы, жылы қолданылады генератор Geffжәне жалпыланған Geff генераторы, алайда мұндай генераторлар корреляциялық шабуыл арқылы бұзылуы мүмкін.
Ауысым регистрінің уақыты әртүрлі генераторлар
тоқтау генераторы
тоқтау генераторы(Ағылшынша Stop-and-Go , Both-Piper ) LFOS-1 шығысын LFOS-2 тактілік жиілігін басқару үшін пайдаланады, осылайша LFSR-2 белгілі бір уақытта LFOS-1 шығысы болса ғана өз күйін өзгертеді. ол кезде бірлікке тең болды. Бұл схема корреляцияның ашылуына қарсы тұра алмады.
Криптографиялық күшті арттыру үшін ол ұсынылды тоқтап тұру генераторы. Ол әртүрлі ұзындықтағы үш ауысым регистрлерін пайдаланады. Мұнда LFSR-1 2-ші және 3-ші регистрлердің тактілік жиілігін басқарады, яғни LFSR-1 шығысы бірге тең болғанда LFSR-2 өз күйін өзгертеді, ал LFSR-3 - LFSR-1 шығысы тең болғанда. нөл. Генератордың шығысы RSLOS-2 және RSLOS-3 екі модульді қосу операциясы болып табылады. Бұл генератор үлкен кезеңге және үлкен сызықтық күрделілікке ие. RLOS-1 корреляциялық ашу әдісі бар, бірақ бұл генератордың криптографиялық қасиеттерін айтарлықтай әлсіретпейді.
Күрделі сағаттық схема қолданылады екі жақты тоқтап тұру генераторы, ол бірдей ұзындықтағы 2 ауысым регистрін пайдаланады. Егер белгілі бір уақытта RLOS-1 шығысы t i − 1 (\displaystyle t_(i-1))- бір, содан кейін RLOS-2 бұл уақытта сағатталмаған t i (\displaystyle t_(i)). Егер уақыт мезетінде RLOS-2 шығысы t i − 1 (\displaystyle t_(i-1))нөлге тең және уақытта t i − 2 (\displaystyle t_(i-2))- бір, және егер бұл регистр сол уақытта сағатталған болса t i (\displaystyle t_(i)), содан кейін дәл сол сәтте RLOS-1 сағаты орнатылмайды. Бұл схеманың сызықтық күрделілігі шамамен құрылған реттілік периодына тең.
Өздігінен жойылатын генератор
Ішкі өнімі бар көп жылдамдықты осциллятор
Бұл генератор RSLOS-1 және RSLOS-2 екі ауысым регистрлерін пайдаланады. Сағат жиілігі RSLOS-2 дюйм d (\displaystyle d) RSLOS-1-ге қарағанда есе көп. Бұл регистрлердің белгілі биттері ЖӘНЕ операциясы арқылы бір-бірімен көбейтіледі. Көбейтулердің нәтижелері XOR операциясы арқылы қосылады және шығыс реті алынады. Бұл генератор жоғары сызықтық күрделілікке ие және жақсы статистикалық қасиеттерге ие. Дегенмен, оның күйін ұзындықтың шығыс тізбегі арқылы анықтауға болады L 1 + L 2 + log 2 d (\displaystyle L_(1)+L_(2)+\log _(2)(d)), қайда L 1 (\displaystyle L_(1))және L 2 (\displaystyle L_(2))тиісінше LFOS-1 және LFOS-2 ұзындықтары және d (\displaystyle d)- олардың тактілік жиіліктерінің қатынасы.
Голлман каскады
Бұл схема тоқтау генераторының жетілдірілген нұсқасы болып табылады. Ол LFSR тізбегінен тұрады, олардың әрқайсысының уақыты алдыңғы LFSR арқылы бақыланады. Егер сол кездегі RLOS-1 шығысы t i (\displaystyle t_(i)) 1 болса, онда RLOS-2 сағаты белгіленеді. Егер уақыт мезетінде RLOS-2 шығысы t i (\displaystyle t_(i)) 1 болса, одан кейін RLOS-3 сағатты және т.б. Соңғы LFSR шығысы генератордың шығысы болып табылады. Егер барлық LFSR ұзындығы бірдей және тең болса L (\displaystyle L), содан кейін жүйенің периоды бастап M (\displaystyle M) LFSR тең (2 L − 1) M (\displaystyle (2^(L)-1)^(M)), ал сызықтық күрделілік L (S) = L (2 L - 1) M - 1 (\displaystyle L(S)=L(2^(L)-1)^(M-1)) .
Бұл идея қарапайым және үлкен кезеңдері, үлкен сызықтық күрделілігі және жақсы статистикалық қасиеттері бар тізбектерді құру үшін пайдаланылуы мүмкін. Бірақ, өкінішке орай, олар шақырылған аутопсияға сезімтал құлыптау(ағыл. lock-in) қашан
Кері байланысты ауыстыру тіркеліміекі бөліктен тұрады: ауысым регистрі және кері байланыс функциялары.
Сурет 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 г 2-нің бөлгіштері n– 1. (Көпмүшелерді талқылағанда, термин жай сантерминімен ауыстырылады келтірілмейтін көпмүше). LFSR сипаттамалық полиномы суреттерде көрсетілген:
x 32 + x 7 + x 5 + x 3 + x 2 + x + 1
қарабайыр модуль 2 болып табылады. Мұндай регистрдің периоды максималды болады, олар қайталанғанша барлық 2 32 - 1 мәндер арқылы өтеді. Ең жиі қолданылатындар жіңішкерілген көпмүшелер, яғни. тек кейбір коэффициенттері бар. ең танымал үш мүшелер.
LFSR негізіндегі генератордың маңызды параметрі болып табылады сызықтық күрделілік. Ол ұзындығы ретінде анықталады nгенератордың шығысын имитациялай алатын ең қысқа LFSR. Сызықтық күрделілік маңызды, өйткені қарапайым Берленкамп-Масси алгоритмітек 2-ні тексеру арқылы мұндай LFSR қайта құруға болады nгамма биттері. Қажетті LFSR анықтамасымен ағындық шифр шын мәнінде бұзылған.
LFSR-ден басқа сызықты емес кері байланысы бар ауыспалы регистрлер, тасымалдау кері байланысы және т.б.
Сандық-теориялық тәсіл негізінде бірқатар генераторлар әзірленді (Blum-Micali генераторлары, RSA, BBS, компрессиялық, аддитивті генераторлар және т.б.).
Блоктық криптографиялық алгоритмдермен салыстырғанда ағындық криптографиялық алгоритмдердің синтезінің математикалық қамтамасыз етілуі толық және егжей-тегжейлі әзірленді. Дегенмен, ағындық шифрларды жасау үшін OFB немесе CFB режимдеріндегі блоктық шифрлау алгоритмдері жиі қолданылады.
