МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» Кафедра ЗІ
Лабороторна робота №3 з курсу «Методи і засоби криптологічних перетворень» на тему: «Конгруентні генератори. Регістри зсуву» Мета роботи: ознайомитися з конгруентними генераторами псевдовипадкових послідовностей бітів, регістрами зсуву з зворотним зв’язком. Завдання Написати програму шифрування і розшифрування на мові програмування С/С++ для реалізації регістра зсуву з лінійним зворотним зв’язком на основі регістру Фібоначчі 8-го порядку. Коротокі теоретичні відомості Лінійним конгруентним генератором (ЛКГ) з параметрами (x0, a, c, N) називається програмний генератор, утворюючий псевдовипадкову послідовність x1,x2,…є А, A ={0,1,…,N-1} за допомогою рекурентного відношення:
(1.1) Параметри цього генератора (1.1) мають наступний зміст:
- початкове, або стартове, значення;
- ненульовий множник;
- приріст,
- модуль, рівний потужності алфавіту
. Якщо приріст
, то генератор (1.1) називається мультиплікативним конгруентним генератором (МКГ), а якщо
, то змішаним конгруентним генератором (ЗКГ). Лінійним регістром зсуву з зворотним зв’язком (Linear Feedback Shift Register, скорочено РЗЛЗЗ) називається логічний прилад. РЗЛЗЗ складається з
комірок пам’яті, двійкові стани яких в момент часу
характеризуються значеннями
. Виходи комірок пам’яті зв’язані не тільки послідовно один з одним, але й з суматорами в відповідності з коефіцієнтами передачі
якщо
, то значення
і-ї комірки передається на один із виходів і-го суматора; якщо
, то така передача відсутня. Припускаємо
. Стан РЗЛЗЗ в даний момент часу
задається двійковим n-вектор-стовпцем
. Загальний вид рекурентного співвідношення, що визначає генератор Фібоначчі, задається рівнянням
Рис.1.2. Регістр зсуву з лінійним зворотнім зв’язком

,
(1.9) де
- параметри генератора; елемент
представляє собою двійковий k-вектор і дія виконується покомпонентно. РЗЛЗЗ в програмній реалізації працюють досить повільно, і швидкість можна збільшити застосуванням для програмування мови Асемблер замість Сі. Ще одне можливе рішення - запускати 16 РЗЛЗЗ (або 32, залежно від розміру слова в комп'ютері) у паралельному режимі. Така схема використовує масив слів, так що кожна бітова комірка регістру представлена окремим РЗЛЗЗ. При умові, що всі вони мають один і той же поліном зворотного зв'язку, така схема працює досить швидко. У загальному випадку найкращий спосіб оновлювати стани регістрів зсуву - це множити поточний стан на відповідні двійкові матриці. У даному прикладі розглянемо поліном вигляду:
Схема матиме такий вигляд: Текст програми шифрування #include <stdio.h> #include <string.h> #include <stdlib.h> #include <conio.h> #include <math.h> const size_t small_buff = 20; const size_t big_buff = 102400; void main() { clrscr(); char text[small_buff]; char bigtext[big_buff]; FILE *infile = fopen( "f:\\ot.txt", "r" ); size_t read_len = 0; size_t file_len = 0; while( read_len = fread(text, 1, small_buff, infile ) ) { memcpy( bigtext + file_len, text, read_len ); file_len += read_len; } int j,n,j1,i,n1,pzr;int k[10000];int kl[10000]; j1=0;int b[10000]; for(n=0;n<file_len*8;n++) {kl[n]=0; k[n]=0;b[n]=0;} /*zadaemo pochatkove znachennya registru*/ printf("vvedit chyslo="); scanf("%d",&pzr); for(n=7;n>=0;n--) { if (pzr -pow(2,n)<0) b[n]=0; else {b[n]=1;pzr = pzr-pow(2,n);} } /*generuemo poslidovnist psevdovypadkovyh bitiv*/ for(i=0;i<(file_len*8);i++) { b[i+8]=(((b[i+5])^b[i+4])^b[i+2]); } /*generuemo kluch*/ for(n=0;n<file_len;n++) { for(j=0;j<=7;j++,j1++) { {if (1==b[j1]) k[j]=pow(2,j); else continue;} kl[n]=kl[n]+k[j]; } } /*zdiusnuemo operaciu xor*/ for(n1=0;n1<file_len;n1++) { bigtext[n1]=bigtext[n1]^kl[n1];} FILE *outfile = fopen( "f:\\ct.txt", "w" ); fwrite( bigtext, 1, file_len, outfile ); fclose( infile ); fclose( outfile ); } Результат виконання програми yY•xJсѕ|moѓг¬Ф.ў: Блок-схема алгоритму програми шифрування  - + - Текст програми розшифрування #include <stdio.h> #include <string.h> #include <stdlib.h> #include <conio.h> #include <math.h> const size_t small_buff = 20; const size_t big_buff = 102400; void main() { clrscr(); char text[small_buff]; char bigtext[big_buff]; FILE *infile = fopen( "f:\\ct.txt", "r" ); size_t read_len = 0; size_t file_len = 0; while( read_len = fread(text, 1, small_buff, infile ) ) { memcpy( bigtext + file_len, text, read_len ); file_len += read_len; } int j,n,j1,pzr,i,n1;int k[10000];int kl[1000]; j1=0;int b[1000]; for(n=0;n<file_len*8;n++) {kl[n]=0; k[n]=0;b[n]=0;} printf("vvedit chyslo="); scanf("%d",& pzr); for(n=7;n>=0;n--) { if ((pzr-pow(2,n))<0) b[n]=0; else {b[n]=1; pzr = pzr -pow(2,n);} } for(i=0;i<(file_len*8);i++) { b[i+8]=(((b[i+5])^b[i+4])^b[i+2]); } for(n=0;n<file_len;n++) { for(j=0;j<=7;j++,j1++) { {if (1==b[j1]) k[j]=pow(2,j); else continue;} kl[n]=kl[n]+k[j]; } } for(n1=0;n1<file_len;n1++) { bigtext[n1]=bigtext[n1]^kl[n1];} FILE *outfile = fopen( "f:\\ot2.txt", "w" ); fwrite( bigtext, 1, file_len, outfile ); fclose( infile ); fclose( outfile ); } Результат виконання програми розшифрування sonce sxodyt na sxodi Блок-схема алгоритму програми розшифрування  - + - Висновок: на даній лабораторній роботі я ознайомилася з регістром зсуву Фібоначчі; якщо використовується елементна база з швидкою реалізацією зсуву, то слід звернутися до регістрів Фібоначчі, але в програмній реалізації цей регістр працює досить повільно; для зламу шифру використовують кореляційний аналіз.