Задание состоит в следующем:

Написать программу,
реализующую алгоритм потокового шифрования содержимого
текстового или двоичного файла. Программа должна запрашивать имя
входного и выходного файлов, представление образующего многочлена
и инициализирующее значение. Разрядность РСЛОС должна быть
меньше или равной максимальной разрядности стандартных
целочисленных типов данных (64 бит).

Вот на чём основываюсь (см. прикреплённый документ)..
Как я поняла, основная задача - сгенерировать поток ключей..для этого и применяется РСЛОС (регистр сдвига с линейной обратной связью)..
Есть некоторые вопросы по реализации:
Пусть пользователь ввёл представление образующего многочлена, инициализирующее значение..
Используя эту информацию нужно некоторый n-битный регистр сдвига обинициализировать (и первый вопрос: как это осуществить?? что за инициализирующее значение задавать??)..чтоб в дальнейшем получать новый бит, выполняя XOR над определёнными битами..

Объясните, пожалуйста!

Ну, так у тебя основное-то как раз и не написано... Вот тут лежит более развернутое объяснение, даже с фрагментами кода на С: http://www.ssl.stu.neva.ru/psw/crypto/potok/str_ciph.htm#top (тебе надо смотреть главу 2 - "Строительные блоки для создания криптосхем"). К сожалению, у меня PDF не открываются как положено, кричит, что нет какого-то шрифта в системе. Возможно у тебя с этим все в порядке. Если нет - то в кэше Гугла есть текст этого документа: Здесь

Я надеюсь, это поможет тебе разобраться...

Спасибо за ссылки!

Насколько я поняла, с помощью функции LFSR() мы и будем получать новый бит регистра..

int LFSR()
{
static unsigned long ShiftRegister = 1 ;
/* Все кроме 0 */
ShiftRegister = ( ( ( ( ShiftRegister >> 31)
                     ^ ( ShiftRegister >> 6)
                     ^ ( ShiftRegister >> 4)
                     ^ ( ShiftRegister >> 2)
                     ^ ( ShiftRegister >> 1)
                       ^ ( ShiftRegister ) )
                              & 0x00000001 )
                                      << 31)
                   | ( ShiftRegister >> 1) ;
return ShiftRegister & 0x00000001 ;
}

Т.е. теперь всё готово, чтобы выполнить XOR для бита из открытого текста и этого полученного нового бита регистра?? Я правильно поняла?

Если да, то ещё вопрос: объясните пожалуйста, как получить очерёдный бит из открытого текста для последующего XOR? (причём открытый текст запрашивается из файла)

Может, проще будет забрать сразу 8 бит регистра сдвига, "сложить" их в байт, и потом XOR-ить с очередным байтом из файла (или потока)? Ну, если нет, так нет, можно и побитово сделать, просто мороки чуть больше...

я об этом не подумала..а что имеется в виду под "сложить" их в байт?

Вот это:

unsigned char byte = 0;
for(int i = 0; i < 8; i++) {
  byte <<= 1;
  byte |= (unsigned char)LFSR();
}

В переменной byte получишь 8 бит ключа, записанных слева направо... Если надо справа налево - тогда:

unsigned char byte = 0;
for(int i = 0; i < 8; i++) {
  byte |= ((unsigned char)LFSR() << i);
}

(вроде нигде не накосячил, пишу прямо здесь, так что все проверяй...)

Читаю символ из файла, потом идёт формирование байта ключа.. дальше XOR для получения шифртекста.. Проблема следующая: каким бы не было инициализирующее значение, результат один и тот же: для одного и того же открытого текста, один и тот же шифртекст..

int LFSR(unsigned long ShiftRegister)
{
/* Все кроме 0 */
ShiftRegister = ( ( ( ( ShiftRegister >> 31)
                     ^ ( ShiftRegister >> 6)
                     ^ ( ShiftRegister >> 4)
                     ^ ( ShiftRegister >> 2)
                     ^ ( ShiftRegister >> 1)
                       ^ ( ShiftRegister ) )
                              & 0x00000001 )
                                      << 31)
                   | ( ShiftRegister >> 1) ;
return ShiftRegister & 0x00000001 ;
}

void __fastcall TFormMain::Button1Click(TObject *Sender)
{
unsigned long ShiftRegister;
unsigned char ch;
FILE *INfile, *OUTfile;
char *filenameIn=OpenDialog1->FileName.c_str();
char *filenameOut=SaveDialog1->FileName.c_str();
INfile=fopen(filenameIn, "r");
OUTfile=fopen(filenameOut, "w");
ShiftRegister=StrToInt(LabEdInitial->Text); // считываем инициализирующее значение
unsigned char byte = 0;
while (!feof(INfile))
{
        fread(&ch,sizeof(unsigned char),1,INfile);
        for(int i = 0; i < 8; i++)
        {
                byte |= (unsigned char)LFSR(ShiftRegister);
                byte <<= 1;
        }
        for(int i = 0; i < 8; i++)
        {
                byte ^= ch;
                byte <<= 1;
        }
        int count=fwrite(&byte,sizeof(unsigned char),1,OUTfile);
        Memo1->Lines->Add(byte);
}

}

Объясните пожалуйста, где я не права?

1) зачем понадобилось менять LFSR, да еще таким образом, как ты это сделала?
2) считала 8 бит из LFSR, один байт из файла, отXOR-ила их, и продолжаешь... Не надо XOR-ить 8 раз... Вот это отработало, как ожидалось:

unsigned long ShiftRegister = 1;
int LFSR()
{
/* Все кроме 0 */
ShiftRegister = ( ( ( ( ShiftRegister >> 31)
                     ^ ( ShiftRegister >> 6)
                     ^ ( ShiftRegister >> 4)
                     ^ ( ShiftRegister >> 2)
                     ^ ( ShiftRegister >> 1)
                       ^ ( ShiftRegister ) )
                              & 0x00000001 )
                                      << 31)
                   | ( ShiftRegister >> 1) ;
return ShiftRegister & 0x00000001 ;
}

void __fastcall TForm1::Button6Click(TObject *Sender)
{
	unsigned char ch;
	FILE *INfile, *OUTfile;
	AnsiString filenameIn, filenameOut;
	if(OpenDialog1->Execute()) {
		filenameIn = OpenDialog1->FileName;
	}
	if(SaveDialog1->Execute()) {
		filenameOut = SaveDialog1->FileName;
	}
	INfile = fopen(filenameIn.c_str(), "r");
	OUTfile = fopen(filenameOut.c_str(), "w");
	ShiftRegister = StrToInt(Edit2->Text); // считываем инициализирующее значение

	unsigned char byte = 0;
	while (!feof(INfile))
	{
		fread(&ch,sizeof(unsigned char),1,INfile);
		for(int i = 0; i < 8; i++)
		{
			byte |= (unsigned char)LFSR();
			byte <<= 1;
		}

		byte ^= ch; // <--- Вот XOR который я упустил

		int count = fwrite(&byte, sizeof(unsigned char), 1, OUTfile);
		Memo1->Lines->Add(byte);
	}
}

Спасибо за разъяснение!!
Но один вопрос...
Я не правильно делала XOR между байтом открытого текстом и 8-мью битами LFSR? Просто я не вижу ничего похоже на этот этап в последнем приведённом коде..

Да, я упустил одну строчку... Добавил в программу выше.

В процессе тестирования появился ещё вопрос..
По идее, если с помощью написанной программы мы получили шифртекст, то если запустить снова программу и работать с шифртекстом, то по итогам работы программы в выходном файле мы получим исходный открытый текст (на основе которого получили используемый шифртекст)..
Так оно и есть..почти..всегда в конце файла при таком порядке действий появляются два лишние символа, которых нет в открытом тексте..
Объясните пожалуйста, в чём может быть причина??

Читаешь исходный файл без контроля ошибок. Добавь этот контроль:

	while (!feof(INfile))
	{
		if(fread(&ch,sizeof(unsigned char),1,INfile)) { // вот этот if и делает свое дело ...
			for(int i = 0; i < 8; i++)
			{
				byte |= (unsigned char)LFSR();
				byte <<= 1;
			}
			byte ^= ch;
			int count = fwrite(&byte, sizeof(unsigned char), 1, OUTfile);
			Memo1->Lines->Add(byte);
		}
	}

Теперь из файла будет считываться и обрабатываться ровно столько символов, сколько там есть, а не на 1 больше... При обратном преобразовании - аналогично... Вот тебе и лишние 2 символа...

Большое спасибо!!

Теперь хочу добиться того, чтобы пользователь мог вводить представление многочлена, а не только использовать тот, который прописан на данный момент в функции LFSR..

Вот мои попытки:

int LFSR(TMemo *MemoPolinom)
{
int i=0;
for (int i=0; i<=MemoPolinom->Lines->Count; i++)
{
        ShiftRegister ^=(ShiftRegister>>StrToInt(MemoPolinom->Lines->Strings[i]));
}
ShiftRegister&=0x00000001;
ShiftRegister>>StrToInt(MemoPolinom->Lines->Strings[0]);
ShiftRegister|=( ShiftRegister >> 1);
/*ShiftRegister = ( ( ( ( ShiftRegister >> 31)
                     ^ ( ShiftRegister >> 6)
                     ^ ( ShiftRegister >> 4)
                     ^ ( ShiftRegister >> 2)
                     ^ ( ShiftRegister >> 1)
                       ^ ( ShiftRegister ) )
                              & 0x00000001 )
                                      << 31)
                   | ( ShiftRegister >> 1) ;
*/
return ShiftRegister & 0x00000001 ;
}

В итоге программа вылетает на строчке

byte |= (unsigned char)LFSR(MemoPolinom);

с ошибкой "is not a valid integer value"
(в MemoPolinom вводила:

31
6
4
2
1
0

)

Скажите пожалуйста, как исправить...?

У тебя тут 2 ошибки:
1) неравенство НЕстрогое, элемента с индексом Count в StringList-е нет, есть от 0 до Count - 1...
2) не заметила, что в прежней реализации ВСЕ сдвиги и XOR-ы производились со старым значением ShiftRegister, и только в самом конце ему присваивалось новое значение?... А сейчас ты на каждой итерации меняешь значение? Не пойдет... Вот так надо:

int LFSR(TMemo *MemoPolinom)
{
	int i=0;
	unsigned long uL = StrToInt(MemoPolinom->Lines->Strings[i]);
	for (int i = 1; i < MemoPolinom->Lines->Count; i++) {
		uL ^= (ShiftRegister >> StrToInt(MemoPolinom->Lines->Strings[i]));
	}
	uL &= 0x00000001;
	uL <<= StrToInt(MemoPolinom->Lines->Strings[0]); // Здесь ты вообще непонятно что делала...
	uL |= (ShiftRegister >> 1);

	ShiftRegister = uL;
	return ShiftRegister & 0x00000001 ;
}

Спасибо большое за разъяснение!!

Здравствуйте!
У меня вот такой вопрос:
с помощью OpenDialog пользователь выбрал текстовый файл с исходным сообщением, а можно ли по нажатию кнопки в разрабатываемом приложении открыть выбранный файл для просмотра содержимого?? Пробовала с помощью CreateProcess..не получилось (даже прописав путь ручками, а не взяв из OpenDialog)..наверно этот вариант не подходит..

 STARTUPINFO si = { sizeof(si) };
 PROCESS_INFORMATION pi;

 CreateProcess(NULL,"H:\\files\\1.txt", NULL, NULL, FALSE,NULL, NULL, NULL, & si, & pi);

Зачем здесь CreateProcess? Можно же открыть средствами Shell-а:

	ShellExecute(NULL, "open", OpenDialog1->FileName.c_str(), 0, 0, SW_SHOWNORMAL);

, только надо убедиться, что файл действительно был выбран, иначе результат будет несколько... неожиданным, что-ли... Хотя на самом деле - логичным.

В процессе тестирования наткнулась на ошибки...
Если в качестве исходного сообщения брать текст на русском, то часть букв при расшифровке исчезает...
Например:
Исх. сообщение:

Для того чтобы конкретный РСЛОС имел максимальный период
(т.е. циклически проходил через все 2n-1 внутренних состояний),
многочлен, образованный из отводной последовательности, должен
быть примитивным (неприводимым) – т.е. не раскладываться на
произведение двоичных многочленов меньшей степени. Некоторые
неприводимые двоичные многочлены приведены в табл. 1.1.
Перед запуском РСЛОС при зашифровании или расшифровании,
регистр необходимо инициализировать одним и тем же значением

Закодировала, получила шифртекст. Для раскодирования прогоняю полученный шифртекст через приложение, получаю:

Для того чтобы конкретный РСЛОС имел максимальный перио

и это всё, что осталось...
Брала инициализирующее значение 1, многочлен 32, 7, 5, 3, 2, 1, 0

Скажите пожалуйста, в чём может быть причина происходящего??

Ну, скорее всего в том, что надо открывать файлы, как бинарные:

        INfile=fopen(filenameIn, "rb");
        OUTfile=fopen(filenameOut, "wb");

, все остальное вроде правильно...

Спасибо! Исправила, с тем примером заработало.
Ещё хотела спросить насчёт такого многочлена: 60,1,0..
Брала иниц. значение=1, в итоге шифртекст совпал с открытым (брала разные примеры текстов)..Скажите пожалуйста, это из-за реализации алгоритма или причина в чём-то другом?

Проблема в разрядности... unsigned long - это 32 бита, а ты сдвигаешь на 60... Тогда уж надо использовать int64_t, там по крайней мере есть эти 60 бит...

После такого описания

int64_t uL = StrToInt(MemoPolinom->Lines->Strings[i]);

компилятор перестал узнавать uL.. скажите, для использования этого типа случаем ничего подключать не нужно?

Нет, в Билдере этот тип называется __int64... Менять надо и тип uL и тип ShiftRegister... Но просто замена ничего не даст, LFSR по-прежнему будет возвращать одни нули... Надо инициализировать регистр сдвига другим значением. У меня при ShiftRegister = 134 все нормально закодировалось...

Ясно, спасибо!

Вот ещё с чем хочу разобраться:

...
int i=0;
        __int64 uL = StrToInt(MemoPolinom->Lines->Strings[i]);
	for (int i = 0; i < MemoPolinom->Lines->Count-1; i++) {
		uL ^= (ShiftRegister >> StrToInt(MemoPolinom->Lines->Strings[i]));
	}
...

если в качестве многочлена рассмотреть (32,7,5,3,2,1,0), то по вышеописанному алгоритму, насколько я поняла, XOR будет производиться над всеми битами, включая 32-й...А нам преподаватель объяснял, что XOR-рить нужно биты, исключая разрядность, т.е. в этом примере исключая 32-й бит..
Тогда получается, что у меня должно быть..

for (int i = 1; i < MemoPolinom->Lines->Count-1; i++)

Если придерживаться этого, я права в исправлении? или я чего-то недопонимаю.., скажите пожалуйста!

Стоп, стоп... Если ты используешь __int64, то разрядность у тебя уже не 32, а 64, так что надо XOR-ить и для 32 тоже. Но вот если использовать unsigned long, который имеет размер в 32 бита, то можно и не сдвигать значение на эти самые 32, а все потому, что любое содержимое unsigned long, сдвинутое на 32 бита вправо, будет = 0... То есть, результат не изменится, но будет быстрее не делать ничего, чем прокрутить на 32 бита, а потом сделать XOR, отсюда и это уточнение твоего преподавателя...

Спасибо!! Теперь я поняла!

И наверно последняя трудность в восприятии:

int LFSR(TMemo *MemoPolinom)
{
	int i=0;
        __int64 uL = StrToInt(MemoPolinom->Lines->Strings[i]);
	for (int i = 0; i < MemoPolinom->Lines->Count-1; i++) {
		uL ^= (ShiftRegister >> StrToInt(MemoPolinom->Lines->Strings[i]));
	}
	uL &= 0x00000001;
	uL <<= StrToInt(MemoPolinom->Lines->Strings[0]);
	uL |= (ShiftRegister >> 1);

	ShiftRegister = uL;
	return ShiftRegister & 0x00000001;
}

Почему два раза нужно использовать операцию &? Объясните пожалуйста!

По алгоритму так. Все дело - в том, что первый & используется в процессе составления следующего значения ShiftRegister из предыдущего, а второй - это уже после того, как новое значение ShiftRegister готово, из него берется только последний бит.

вот здесь я до конца и не пойму..
Можете пошагово подробнее объяснить происходящее после цикла..?
Очень хочу во всём разобраться до конца..

Так... Это, похоже, неправильная функция. Правильнее (соответственно тому, что написано в той статье, на которую я давал ссылку выше, и готовой функции LFSR, которая приведена там) будет сделать ее вот так:

int LFSR(TMemo *MemoPolinom)
{
	__int64 uL = 0; // Сначала заносим 0, а не первый сдвиг
	for (int i = 0; i < MemoPolinom->Lines->Count; i++) {
		// XOR-им с предыдущим значением SR, сдвинутым на _все_ заданные сдвиги
		uL ^= (ShiftRegister >> StrToInt(MemoPolinom->Lines->Strings[i]));
	}
	// Оставляем только последний бит от полученного числа
	uL &= 0x0000000000000001;

	// Сдвигаем этот бит влево на _сколько нужно_ (согласно полиному) позиций
	uL <<= StrToInt(MemoPolinom->Lines->Strings[0]);

	// и OR-им со сдвинутым на 1 вправо предыдущим значением SR
	uL |= (ShiftRegister >> 1);

	// Все, у нас теперь в uL получилось новое значение SR, присваиваем его
	ShiftRegister = uL;

	// И возвращаем последний бит этого нового SR как результат функции
	return ShiftRegister & 0x0000000000000001;
}

Теперь функция делает абсолютно то же самое, что и та, готовая, которая приведена в статье... Раньше она делала не совсем то, что требовалось.

а разве операция << это не сдвиг влево..? так куда же всё-таки нужно сдвигать...? и почему маска изменилась на 0x0000000000000001..?

Влево, влево надо сдвигать... Код правильный, в комментариях я ошибся... Исправлю.

Потому что тип ShiftRegister изменился на __int64 у тебя... А это - 64 бита. То есть, в 2 раза длиннее, чем было... Можешь, конечно оставить, как есть, можно вообще сделать

return ShiftRegister & 1;

, но я предпочитаю при работе с битовыми операциями записывать маски полностью.

А это будет последний левый бит?

Это будет младший бит (LSB), почему левый? Ясно же видно, что слева - все нули, а единица - самая правая... (вот поэтому я и предпочитаю писать битовые маски полностью, кстати).

А почему мы должны оставлять последний (младший) бит? Ведь насколько я поняла из статьи, левый бит является функцией всех остальных..а получается мы его не берём..?

В статье написано, что . Ты об этом? Единственное, что мне приходит в голову - это вот что: возможно надо делать

int LFSR(TMemo *MemoPolinom)
{
	__int64 uL = 0;
	for (int i = 0; i < MemoPolinom->Lines->Count; i++) {
		uL ^= (ShiftRegister >> StrToInt(MemoPolinom->Lines->Strings[i]));
	}
	uL &= 0x0000000000000001;
	// Не вот так, как ты делаешь...
	// uL <<= StrToInt(MemoPolinom->Lines->Strings[0]);

	// А вот так вот:
	uL <<= (sizeof(__int64) * 8) - 1; // или просто 63

	uL |= (ShiftRegister >> 1);
	ShiftRegister = uL;
	return ShiftRegister & 0x0000000000000001;
}

Чувствуешь разницу? То есть, если 31 в изначальной функции - это не первый член полинома, а (размерность unsigned long в битах) - 1, и надо было ВСЕГДА сдвигать на 31, а не только тогда, когда полином начинается с этого числа, то все становится на свои места.
Тогда действительно при сдвиге на sizeof(unsigned long)*8 - 1 бит тот самый правый бит, который получен как функция от всех остальных, станет самым левым. Тогда все сходится с описанием...

да..я об этом..
уж лучше оставлю сдвиг в зависимости от вида полинома...т.е.

uL <<= StrToInt(MemoPolinom->Lines->Strings[0]);

и исходя из этого последний вопрос:

uL |= (ShiftRegister >> 1);

перед этим мы результат XOR передвинули на количество позиций, определяемое разрядностью регистра сдвига... тогда для чего нужно сдвигать прежнее значение SR на 1 вправо (что это нам даст?) и что даёт OR c имеющимся в uL значением? Объясните пожалуйста!

Нет уж, ты все-таки сделай так, как надо, а не так, как тебе хочется. А надо - именно сдвигать на sizeof(ShiftRegister)*8 - 1, вот тебе пример:
Wiki: Linear feedback shift register
Видишь, там напрочь нет 15 в полиноме (нет сдвига вправо на 15 бит), однако, чтобы получить тот самый единственный бит САМЫМ ЛЕВЫМ, производится сдвиг влево на 15 (при 16-битном размере регистра).

Ну ты уж будь последовательна... Только что ты сказала, что тебе плевать на разрядность регистра, тебе удобнее передвигать результат XOR-ов в зависимости от первого элемента полинома... Так что все-таки ты решила?

Если принять, что сдвиг производится в зависимости от разрядности, то... Смотри: Допустим, имеем 8-ми разрядный регистр (для простоты, принцип остается тем же для любой разрядности). Тогда:
SR = 00101011 (какое-то значение регистра)
Допустим, после преобразований и отсечения всех старших бит, получили uL = 00000001... Теперь сдвигаем это значение так, чтобы выделенный бит был старшим: uL = 10000000. И "складываем" (OR) с предыдущим значением SR, сдвинутым на 1 позицию вправо (т.е., с 00010101)... Что имеем в результате?
10000000
00010101
--------
10010101, то есть, старшим битом идет бит, только что вычисленный "как функция от остальных бит регистра", а остальные - просто сдвинутые исходные... А теперь сравни: