Да, это надо
А зачем надо шифроваться вообще? Есть ли что скрывать обычному законопослушному гражданину от "всесильных" спецслужб (или разных тёмных личностей)? Представляет ли ценность для кого-нибудь банальная личная жизнь обычных людей?
Думаю лишний раз трогать хакеров и кракеров не надо, это наверно всем порядком поднадоело, а вот вспомнить недавний скандал в Европарламенте, связанный с системой тотального электронного шпионажа «Эшелон», стоит (статья в одном из номеров журнала «Эхо Планеты» за этот год). В Европарламенте обсуждался вопрос, о том, что же всё-таки делать дальше, ведь никто не собирался выкидывать «Эшелон» на свалку только из-за того, что Европарламенту это не понравилось! И одним из выходов было признание необходимости тотального использования криптосистем.
А насчёт того, интересна ли жизнь обычных людей спецслужбам, стоит вспомнить статью, промелькнувшую на страницах одной из компьютерных газет (автора не помню, извиняйте ;). В ней высказывалось предположение о том что личная переписка и тому подобное запоминается и хранится в архивах спецслужб, и когда этот человек становится чем-то интересен, анализируется вся его личная жизнь от и до, и становятся понятными особенности его психики, поведения, выбор оптимальных воздействий, чтобы вынудить человека совершить нужный поступок. Не сомневаюсь, доля истины в таком предположении есть.
В локальных сетях прослушать весь трафик своего сегмента сможет даже начинающий ламер ;).
Да, ещё. Про существование всяких средств перехвата излучения мониторов и т.п. читал много, а вот про реальное их использование для отлова преступников не слышал. Всё сводилось к банальному взводу ОМОНА (или что у них там) и «Руки от клавы !» с выносом сервера. Да и то, насколько помню, проваливались такие преступники из-за своей жадности, а не из-за того что кто-то что-то у них подслушал. Вполне может быть что такие случаи не афишируются, и поэтому информации минимум.
Литература
1. Баpичев Сеpгей Kpиптогpафия без секpетов (где искать не знаю, у самого только электронный вариант)
2. Ярмолик В. Н. Контроль и диагностика цифровых узлов ЭВМ - Минск : Наука и техника, 1988. - 240 с.
3. Ярмолик В. Н., Демиденко С. Н. Генерирование и применение псевдослучайных сигналов в системах испытаний и контроля – Минск : Наука и техника, 1986. – 200 с.
М-последовательности
Одним из наиболее широко применяемых способов формирования псевдослучайных последовательностей является способ, основанный на использовании соотношения:
(2.1)
где k - номер такта; akÎ{0, 1}-символы последовательности;
aiÎ{0, 1}-постоянные коэффициенты;
- операция суммирования по модулю два m логических переменных.
При соответствующем выборе коэффициентов ai, на основании характеристического полинома j(x)=1Åa1x1Åa2x2a3x3…am-1xm-1amxm, который должен быть примитивным, последовательность бит {ak} имеет максимальную длину, равную 2m-1. Такая последовательность называется M-последовательностью.
Главное преимущество метода формирования псевдослучайных последовательностей по соотношению (2.1) - простота его реализации, как программной, так и аппаратурной.
Некоторыми из наиболее важных для нас свойств М-последовательностей являются:
- максимальная близость М-последовательности по характеристикам к случайной;
- период последовательности, формируемой по выражению (2.1), определяется старшей степенью порождающего полинома j(x) и равен L = 2m-1;
- для заданного полинома j(х) существует L различных
M-последовательностей, отличающихся фазовым сдвигом.
Немного теории
Одними из этапов шифрования в симметричных криптосистемах является гаммирование и гаммирование с обратной связью.
Гаммирование – наложение гаммы (обычно псевдослучайной последовательности) на текст обратимым образом.
Гаммирование с обратной связью – значение зашифрованного символа зависит не только от гаммы, но и от предыдущих символов.
Остальные этапы рассматривать не будем, поскольку для них ничего нового предложено не будет, и их без проблем можно будет добавить к предлагаемому алгоритму.
Наша задача состоит в том, чтобы обеспечить такое гаммирование с обратной связью, которое бы приводило к полному изменению текста на выходе даже при несущественном изменении входного. Рассмотрим немного теории (излагается сокращенно по [2]).
Общий вид алгоритма
Для того чтобы изменение одного бита (или группы битов) воздействовало на все остальные, поступим следующим образом: будем вычислять сигнатуру двоичной последовательности и одновременно некоторой функцией преобразовывать биты, сигнатура для которых уже рассчитана. Естественно, эта функция должна иметь соответствующую ей обратную функцию для восстановления исходного текста. Преобразовывать можно как один бит, так сразу и группу битов. Шаг алгоритма может быть длиной как в один бит, так и в несколько бит.
Для простоты понимания рассмотрим алгоритм, с функцией, преобразующий один бит, и шагом в один бит.
k – длина последовательности, бит;
m – старшая степень полинома для расчёта сигнатуры, а также количество бит в элементах памяти (prev и next), хранящих сигнатуру;
сигнатура(предыдущая сигнатура, новый бит) – функция, осуществляющая сжатие последовательности в сигнатуру;
f(x, ai) – функция, осуществляющая преобразование бита ai некоторым числом x;
ai – i-ый бит последовательности.
Базовое преобразование (прямой ход) будет выглядеть так:
(3.1)
prev = 0;
для i от 1 до k
{
next = сигнатура(prev, ai);
ai = f(prev, ai);
prev = next;
}
Обратное преобразование (прямой ход) будет выглядеть так:
(3.2)
prev = 0;
для i от 1 до k
{
ai = f
-1(prev, ai);
prev = сигнатура(prev, ai);
}
Как видим, изменение бита ai воздействует на все последующие биты, и вероятность того, что изменение этого бита отразиться на последующих, очень близка к единице. А что же делать с битами, предшествующими ai, ведь изменение их не затронет? Поступим просто – совершим такое же преобразование повторно, но в обратном направлении.
Базовое преобразование, обратный ход:
(3.3)
prev = 0;
для i от k до 1
{
next = сигнатура(prev, ai);
ai = f(prev, ai);
prev = next;
}
Обратное преобразование, обратный ход:
(3.4)
prev = 0;
для i от k до 1
{
ai = f
-1(prev, ai);
prev = сигнатура(prev, ai);
}
Преобразования (3.1) и (3.3) разносят изменения в любой точке последовательности на всю последовательность целиком таким образом, что каждый бит становится связанным со всеми остальными, и его изменение повлечёт изменение остальных битов с вероятностью, очень близкой к единице. Для восстановления исходного текста надо применить последовательно преобразования (3.2) и (3.4).
Но вышеописанное обеспечивает полноценное воздействие изменений только при преобразовании исходного текста в зашифрованный, при обратном преобразовании воздействие изменений в зашифрованном тексте на восстанавливаемый исходный будет слабо. Решается это просто – вводим дополнительно после (3.1) и (3.3) преобразования, аналогичные (3.2) и (3.4), только используем не f –1(x, y), а f(x, y).
Выглядеть это будет так:
Основная идея
Некоторыми из требований, предъявляемых к криптосистемам, являются [1]:
- число операций, необходимых для определения использованного ключа шифрования по фрагменту шифрованного сообщения и соответствующего ему открытого текста, должно быть не меньше общего числа возможных ключей;
- незначительное изменение ключа должно приводить к существенному изменению вида зашифрованного сообщения даже при использовании одного и того же ключа.
То есть криптоалгоритм должен обеспечить невозможность анализа зашифрованного текста. Задачи криптоанализа, в частности, состоят в установлении зависимостей между зашифрованным и исходным текстом (или его фрагментом) без знания ключа. Криптоалгоритм же надо строить таким образом, чтобы трудоёмкость анализа была не ниже полного перебора всего множества возможных ключей.
Идея такова: обеспечить влияние любого бита текста на все остальные таким образом, чтобы имея два одинаковых исходных текста, изменив любой бит (или группу битов) одного текста, на выходе получить два совершенно различных текста (в идеале отличающихся между собой как две случайные последовательности). Аналогичные требования предъявляются к обратному преобразованию и к изменению ключа.
P.S.
На данный момент в программе-примере доступной на моей страничке используется примитивный полином 1Åx502Åx607, так же исходный код по сравнению с приводимым здесь улучшен и оптимизирован, и работает на порядок быстрее.
Маленькое замечание: если для генерирования гаммы используется примитивный полином, то плохих паролей не существует. Точнее существует, но он единственный – полностью нулевой.
Второе замечание: для лучшей стойкости начальное значение сигнатуры лучше инициализировать на основе ключа или гаммы, особенно для потоковой версии.
Подход к созданию трудноанализируемых шифров
Брилюк Дмитрий Витальевич
bdv78@newmail.ru
http://bdv78.newmail.ru
Программная реализация (язык С)
Примечание: предполагается что типы int и unsigned имеют размер 4 байта.
Пример функции, генерирующей побитно псевдослучайную последовательность:
// примитивный неприводимый полином для формирования
// М-последовательности с периодом (2^11)-1
// fi(x) = 1(+)x^2(+)x^11
unsigned NextMValue(unsigned prev)
{
register unsigned c = 0;
if(prev & (1<<1))
c++;
if(prev & (1<<10))
c++;
return (prev<<1)|(c&1);
}
Начальное значение параметра prev может быть любым, отличным от нуля, новый бит последовательности хранится в нулевом бите возвращаемого значения.
Пример функции, побитно сжимающей двоичную последовательность в сигнатуру:
// примитивный неприводимый полином
// для вычисления 32-битной сигнатуры
// fi(x) = 1(+)x^1(+)x^27(+)x^28(+)x^32
unsigned NextSignature32
(unsigned prev, unsigned newbit)
{
if(prev&(1<<0))
newbit++;
if(prev&(1<<26))
newbit++;
if(prev&(1<<27))
newbit++;
if(prev&(1<<31))
newbit++;
return (prev<<1)|(newbit&1);
}
Для генерации гаммы на основании ключа будем применять следующую функцию:
unsigned char * generate_gamma(unsigned char *pw, unsigned pwlen, unsigned gamma_len, unsigned char * gamma = NULL)
{
const
gb_len = 256;
static int
polynomial[] = { 1, 5, 23, 171, 243, 1057, 2047, -1 };
//polynomial[] = { 1, 18, 20, 39, -1 }; // период 2^40 - 1
static unsigned char
buf[gb_len+1];
memset(buf, 0, sizeof(buf));
if(pwlen)
for(int i = 0; i < gb_len; i++)
buf[i+1] = pw[i%pwlen];
else
яяяяяяяяяяяяяяяяяяяяяяя buf[1] = 1;
яяяяяяяяяяя if(!gamma)
яяяяяяяяяяяяяяяяяяяяяяя gamma = new unsigned char [gamma_len];
яяяяяяяяяяя for(int i = 0; i < gamma_len; i++) {
яяяяяяяяяяяяяяяяяяяяяяя buf[0] = 0;
яяяяяяяяяяяяяяяяяяяяяяя for(int j = 0; j < 8; j++) {
яяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяя register unsigned char newbit = 0;
яяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяя for(int k = 0; polynomial[k] >= 0; k++) {
яяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяя register unsigned bit = (polynomial[k]+8-j);
яяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяя if(buf[bit>>3]&(1<<(bit&7)))
яяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяя newbit++;
яяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяя }
яяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяя buf[0] |= (newbit&1)<<(7-j);
яяяяяяяяяяяяяяяяяяяяяяя }
яяяяяяяяяяяяяяяяяяяяяяя memmove(buf+1, buf, gb_len);
яяяяяяяяяяяяяяяяяяяяяяя gamma[i] = buf[0];
яяяяяяяяяяя }
яяяяяяяяяяя return gamma;
}
ќв дгЄжЁп ¬®¦Ґв ®ЇҐаЁа®ў вм «оЎл¬ Ї®«Ё®¬®¬. ЏаЁўҐ¤с Ї®«Ё®¬ б⥯ҐЁ 2048, Ё«Ё 256 Ў ©в. ‡ ¤ ў вм Ї а®«м ¤«ЁҐҐ 256 Ў ©в Ґ Ё¬ҐҐв б¬лб« , Ї®бЄ®«мЄг нв® ЁЄ Є Ґ ®ва §Ёвбп ЈҐҐаЁа㥬®© Ј ¬¬Ґ. Љ®Ґз® ¬®¦® ЇаҐ¤ў аЁвҐ«м® Ї®¤ўҐаЈгвм Ї а®«м бўсавЄҐ, ® ўҐ¤м в®Ј¤ ¤«п ўбЄалвЁп ¬®¦® Ўг¤Ґв ЇҐаҐЎЁа вм в®«мЄ® 256 Ў ©в Ё§ бўсавЄЁ, Є®в®алҐ Ё ЁбЇ®«м§говбп ¤«п ЈҐҐа жЁЁ Ј ¬¬л. Џ®«Ё®¬ ў§пв <б Ї®в®«Є >, Ї®н⮬㠤«п ¤с¦®© ЈҐҐа жЁЁ Ј ¬¬л б«Ґ¤гҐв ЁбЇ®«м§®ў вм ЇаЁ¬ЁвЁўл© ҐЇаЁў®¤Ё¬л© Ї®«Ё®¬. ‚ Є®¬¬Ґв аЁпе гЄ § ЇаЁ¬ЁвЁўл© Ї®«Ё®¬ б⥯ҐЁ 40, ¤«п Є®в®а®Ј® ўагзго Ўл« Їа®ўҐаҐ Їа ўЁ«м®бвм а Ў®вл Їа®жҐ¤гал. Џа ў¤ ¬ ЄбЁ¬ «м п ¤«Ё Є«оз ¤«п ҐЈ® ўбҐЈ® «Ёим Їпвм Ў ©в L.
‚ [1] гЄ §лў «Ёбм Ґ¤®бв вЄЁ ў ЇаЁ¬ҐҐЁЁ Њ-Ї®б«Ґ¤®ў ⥫м®б⥩ ¤«п ЈҐҐа жЁЁ Ј ¬¬л, Ё ЇаҐ¤« Ј «®бм ЁбЇ®«м§®ў вм Ї®б«Ґ¤®ў ⥫м®бвЁ ѓ®«¤ , ®Ўа §гойЁҐбп б㬬Ёа®ў ЁҐ¬ ҐбЄ®«мЄЁе Њ-Ї®б«Ґ¤®ў ⥫м®б⥩.
„«п Їа®бв®вл и «Ј®аЁв¬ Ўг¤Ґв а Ў®в вм б Ў ©в ¬Ё, Ё бЁЈ вга Ўг¤Ґв ўлзЁб«пвмбп ба §г ¤«п ўбҐЈ® Ў ©в .
„«п б¦ вЁп Ї®б«Ґ¤®ў ⥫м®бвЁ ў бЁЈ вгаг ЁбЇ®«м§гҐ¬ Ё§ўҐбвго Ё ®ЇвЁ¬Ё§Ёа®ў го дгЄжЁо crc32я (ЇаЁ« Ј Ґвбп б Ёб室묨 ⥪бв ¬Ё):
unsigned crc32tab[] = {
яяяяяяяяяяя 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba,
яяяяяяяяяяя 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,
яяяяяяяяяяя 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
яяяяяяяяяяя 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,
яяяяяяяяяяя 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
яяяяяяяяяяя 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
яяяяяяяяяяя 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,
яяяяяяяяяяя 0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,
яяяяяяяяяяя 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
яяяяяяяяяяя 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
яяяяяяяяяяя 0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940,
яяяяяяяяяяя 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
яяяяяяяяяяя 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116,
яяяяяяяяяяя 0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,
яяяяяяяяяяя 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
яяяяяяяяяяя 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,
яяяяяяяяяяя 0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a,
яяяяяяяяяяя 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
яяяяяяяяяяя 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818,
яяяяяяяяяяя 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
яяяяяяяяяяя 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
яяяяяяяяяяя 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457,
яяяяяяяяяяя 0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c,
яяяяяяяяяяя 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
яяяяяяяяяяя 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
яяяяяяяяяяя 0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb,
яяяяяяяяяяя 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
яяяяяяяяяяя 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,
яяяяяяяяяяя 0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086,
яяяяяяяяяяя 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
яяяяяяяяяяя 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4,
яяяяяяяяяяя 0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,
яяяяяяяяяяя 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
яяяяяяяяяяя 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683,
яяяяяяяяяяя 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
яяяяяяяяяяя 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
яяяяяяяяяяя 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe,
яяяяяяяяяяя 0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7,
яяяяяяяяяяя 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
яяяяяяяяяяя 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
яяяяяяяяяяя 0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252,
яяяяяяяяяяя 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
яяяяяяяяяяя 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60,
яяяяяяяяяяя 0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,
яяяяяяяяяяя 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
яяяяяяяяяяя 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f,
яяяяяяяяяяя 0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04,
яяяяяяяяяяя 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
яяяяяяяяяяя 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a,
яяяяяяяяяяя 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
яяяяяяяяяяя 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
яяяяяяяяяяя 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,
яяяяяяяяяяя 0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e,
яяяяяяяяяяя 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
яяяяяяяяяяя 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
яяяяяяяяяяя 0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,
яяяяяяяяяяя 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
яяяяяяяяяяя 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db,
яяяяяяяяяяя 0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0,
яяяяяяяяяяя 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
яяяяяяяяяяя 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6,
яяяяяяяяяяя 0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf,
яяяяяяяяяяя 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
яяяяяяяяяяя 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
};
// polynomial is
// X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X^1+X^0
unsigned crc32( unsigned crc, unsigned char *buf, unsigned buflen)
{
яяяяяяяяяяя for(unsigned i = 0; i < buflen; i++)
яяяяяяяяяяяяяяяяяяяяяяя crc = crc32tab[(unsigned char)(crc ^ unsigned(buf[i]))] ^ ((crc >> 8) & 0x00ffffff);
яяяяяяяяяяя return crc;
}
”гЄжЁЁ § иЁда®ўЄЁ/а биЁда®ўЄЁ:
void encrypt(unsigned char * buf, unsigned buflen, unsigned char * gamma)
{
яяяяяяяяяяя unsigned prev, next;
яяяяяяяяяяя unsigned char * pgamma;
яяяяяяяяяяя // д § 1
яяяяяяяяяяя // § йЁв ®в Ё§¬ҐҐЁ© ў Ёб室®¬ ⥪бвҐ
яяяяяяяяяяя // бўсавЄ 1 - Їаאַ© 室
яяяяяяяяяяя prev = 0xffffffff;
яяяяяяяяяяя pgamma = gamma;
яяяяяяяяяяя for(int i = 0; i < buflen; i++) {
яяяяяяяяяяяяяяяяяяяяяяя next = crc32(prev, buf+i, 1);
яяяяяяяяяяяяяяяяяяяяяяя next = crc32(next, pgamma+i, 1);яяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяя // Ј ¬¬Ёа®ў ЁҐ
яяяяяяяяяяяяяяяяяяяяяяя buf[i] += prev;
яяяяяяяяяяяяяяяяяяяяяяя prev = next;
яяяяяяяяяяя }
яяяяяяяяяяя // бўсавЄ 2 - ®Ўа вл© е®¤
яяяяяяяяяяя prev = 0xffffffff;
яяяяяяяяяяя pgamma = gamma+buflen;
яяяяяяяяяяя for(int i = buflen-1; i >= 0; i--) {
яяяяяяяяяяяяяяяяяяяяяяя next = crc32(prev, buf+i, 1);
яяяяяяяяяяяяяяяяяяяяяяя next = crc32(next, pgamma+i, 1);яяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяя // Ј ¬¬Ёа®ў ЁҐ
яяяяяяяяяяяяяяяяяяяяяяя buf[i] += prev;
яяяяяяяяяяяяяяяяяяяяяяя prev = next;
яяяяяяяяяяя }
яяяяяяяяяяя // д § 2
яяяяяяяяяяя // § йЁв ®в Ё§¬ҐҐЁ© ў иЁда®ў ®¬ ⥪бвҐ
яяяяяяяяяяя // бўсавЄ 3 - Їаאַ© 室
яяяяяяяяяяя prev = 0xffffffff;
яяяяяяяяяяя pgamma = gamma+(buflen<<1);
яяяяяяяяяяя for(int i = 0; i < buflen; i++) {
яяяяяяяяяяяяяяяяяяяяяяя buf[i] += prev;
яяяяяяяяяяяяяяяяяяяяяяя prev = crc32(prev, buf+i, 1);
яяяяяяяяяяяяяяяяяяяяяяя prev = crc32(prev, pgamma+i, 1);яяяяяяяяяяяяяяяяяяяяяяяяяяяяяяя // Ј ¬¬Ёа®ў ЁҐ
яяяяяяяяяяя }
яяяяяяяяяяя // бўсавЄ 4 - ®Ўа вл© е®¤
яяяяяяяяяяя prev = 0xffffffff;
яяяяяяяяяяя pgamma = gamma+(buflen<<1)+buflen;
яяяяяяяяяяя for(int i = buflen-1; i >= 0; i--) {
яяяяяяяяяяяяяяяяяяяяяяя buf[i] += prev;
яяяяяяяяяяяяяяяяяяяяяяя prev = crc32(prev, buf+i, 1);
яяяяяяяяяяяяяяяяяяяяяяя prev = crc32(prev, pgamma+i, 1);яяяяяяяяяяяяяяяяяяяяяяяяяяяяяяя // Ј ¬¬Ёа®ў ЁҐ
яяяяяяяяяяя }
}
void decrypt(unsigned char * buf, unsigned buflen, unsigned char * gamma)
{
яяяяяяяяяяя unsigned prev, next;
яяяяяяяяяяя unsigned char * pgamma;
яяяяяяяяяяя // а §ўсавЄ 4 - ®Ўа вл© е®¤
яяяяяяяяяяя prev = 0xffffffff;
яяяяяяяяяяя pgamma = gamma+(buflen<<1)+buflen;
яяяяяяяяяяя for(int i = buflen-1; i >= 0; i--) {
яяяяяяяяяяяяяяяяяяяяяяя next = crc32(prev, buf+i, 1);
яяяяяяяяяяяяяяяяяяяяяяя next = crc32(next, pgamma+i, 1);яяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяя // Ј ¬¬Ёа®ў ЁҐ
яяяяяяяяяяяяяяяяяяяяяяя buf[i] -= prev;
яяяяяяяяяяяяяяяяяяяяяяя prev = next;
яяяяяяяяяяя }
яяяяяяяяяяя // а §ўсавЄ 3 - Їаאַ© 室
яяяяяяяяяяя prev = 0xffffffff;
яяяяяяяяяяя pgamma = gamma+(buflen<<1);
яяяяяяяяяяя for(int i = 0; i < buflen; i++) {
яяяяяяяяяяяяяяяяяяяяяяя next = crc32(prev, buf+i, 1);
яяяяяяяяяяяяяяяяяяяяяяя next = crc32(next, pgamma+i, 1);яяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяя // Ј ¬¬Ёа®ў ЁҐ
яяяяяяяяяяяяяяяяяяяяяяя buf[i] -= prev;
яяяяяяяяяяяяяяяяяяяяяяя prev = next;
яяяяяяяяяяя }
яяяяяяяяяяя // а §ўсавЄ 2 - ®Ўа вл© е®¤
яяяяяяяяяяя prev = 0xffffffff;
яяяяяяяяяяя pgamma = gamma+buflen;
яяяяяяяяяяя for(int i = buflen-1; i >= 0; i--) {
яяяяяяяяяяяяяяяяяяяяяяя buf[i] -= prev;
яяяяяяяяяяяяяяяяяяяяяяя prev = crc32(prev, buf+i, 1);
яяяяяяяяяяяяяяяяяяяяяяя prev = crc32(prev, pgamma+i, 1);яяяяяяяяяяяяяяяяяяяяяяяяяяяяяяя // Ј ¬¬Ёа®ў ЁҐ
яяяяяяяяяяя }
яяяяяяяяяяя // а §ўсавЄ 1 - Їаאַ© 室
яяяяяяяяяяя prev = 0xffffffff;
яяяяяяяяяяя pgamma = gamma;
яяяяяяяяяяя for(int i = 0; i < buflen; i++) {
яяяяяяяяяяяяяяяяяяяяяяя buf[i] -= prev;
яяяяяяяяяяяяяяяяяяяяяяя prev = crc32(prev, buf+i, 1);
яяяяяяяяяяяяяяяяяяяяяяя prev = crc32(prev, pgamma+i, 1);яяяяяяяяяяяяяяяяяяяяяяяяяяяяяяя // Ј ¬¬Ёа®ў ЁҐ
яяяяяяяяяяя }
}
”гЄжЁп иЁда®ў Ёп д ©« :
int cryptfile(int encrypt, char *fn, unsigned char *pw, unsigned pwlen)
{
яяяяяяяяяяя FILE * f = fopen(fn, "r+b");
яяяяяяяяяяя unsigned char * buf, * gamma;
яяяяяяяяяяя unsigned buflen;
яяяяяяяяяяя if(!f)
яяяяяяяяяяяяяяяяяяяяяяя return -1;
яяяяяяяяяяя buflen = filelength(f->fd);
яяяяяяяяяяя buf = new char[buflen];
яяяяяяяяяяя gamma = generate_gamma(pw, pwlen, buflen<<2);
яяяяяяяяяяя fread(buf, buflen, 1, f);
яяяяяяяяяяя if(encrypt)
яяяяяяяяяяяяяяяяяяяяяяя encrypt(buf, buflen, gamma);
яяяяяяяяяяя else
яяяяяяяяяяяяяяяяяяяяяяя decrypt(buf, buflen, gamma);
яяяяяяяяяяя rewind(f);
яяяяяяяяяяя fwrite(buf, buflen, 1, f);
яяяяяяяяяяя memset(buf, 0xff, buflen);
яяяяяяяяяяя memset(buf, 0, buflen);
яяяяяяяяяяя memset(gamma, 0xff, buflen<<2);
яяяяяяяяяяя memset(gamma, 0, buflen<<2);
яяяяяяяяяяя delete buf;
яяяяяяяяяяя delete gamma;
яяяяяяяяяяя fclose(f);
яяяяяяяяяяя return 0;
}
Џа®ў®¤Ё«бп ҐЎ®«ми®© «Ё§ б®ўЇ ¤ҐЁҐ Ў ©в ў ЇаҐ®Ўа §®ў ле в ЄЁ¬ ®Ўа §®¬ д ©« е. „«п зҐвласе д ©«®ў, Ёб室®Ј®, б Ё§¬Ґсл¬ ®¤Ё¬ ЎЁв®¬ ў з «Ґ, Є®жҐ Ё бҐаҐ¤ЁҐ д ©« , б®ўЇ ¤ҐЁҐ Ў ©в (Ї®Ї а®, Є ¦¤л© б Є ¦¤л¬) б®бв ўЁ«® ¬ҐҐҐ 0.5%. Џ®б«Ґ б¦ вЁп аеЁў в®а®¬ RAR ўбҐе зҐвласе д ©«®ў ў ®¤Ё solid- аеЁў а §¬Ґа Є ¦¤®Ј® д ©« 㢥«ЁзЁ«бп (ў®в в Є ;). ‚ ЇаЁ« Ј Ґ¬®© Їа®Ја ¬¬Ґ ¬®¦® б ¬®бв®пвҐ«м® Ї®нЄбЇҐаЁ¬ҐвЁа®ў вм б иЁда®ўЄ®© а §«Ёзле д ©«®ў. €¬ҐҐвбп Є®¬ ¤ ба ўҐЁп ¤ўге д ©«®ў. ЏаЁ ЇаҐ®Ўа §®ў ЁЁ ¤ўге д ©«®ў ®Ё ўв®¬ вЁзҐбЄЁ ба ўЁў овбп. Џ®Їа®Ўг©вҐ Ё§¬ҐЁвм ҐбЄ®«мЄ® ЎЁв, Ї®б¬®ваЁвҐ зв® Ўг¤Ґв. Љ®¬г ¬ «®, ¬®¦Ґв гб®ўҐаиҐбвў®ў вм Ёбе®¤лҐ вҐЄбвл Ё нЄбЇҐаЁ¬ҐвЁа®ў вм ¤ «миҐ.
Расшифровка
// обратный ход (3.8)-1
prev = 0;
для i от k до 1
{
next = сигнатура(prev, ai);
ai = f
-1(prev, ai);
prev = next;
}
// прямой ход (3.7)-1
prev = 0;
для i от 1 до k
{
next = сигнатура(prev, ai);
ai = f
-1(prev, ai);
prev = next;
}
// обратный ход (3.6)-1
prev = 0;
для i от k до 1
{
ai = f
-1(prev, ai);
prev = сигнатура(prev, ai);
}
// прямой ход (3.5)-1
prev = 0;
для i от 1 до k
{
ai = f
-1(prev, ai);
prev = сигнатура(prev, ai);
}
Одной из ранних идей преобразований подобного рода была такая: текст разбивается на две половинки, вычисляется сигнатура первой половины и с помощью этой сигнатуры преобразуется вторая половина, затем наоборот. Каждая из этих половинок опять разбивается на две, и преобразование повторяется рекурсивно, пока длина половинки не станет меньше одного бита (или байта). Время такого преобразования – порядка двоичного логарифма от длины последовательности.
Следует отметить, что для каждого из четырёх базовых преобразований можно использовать различные функции преобразования и полиномы для расчёта сигнатур, что может повысить криптостойкость.
Как можно было заметить, преобразование осуществляется без какого-либо привлечения ключа, и имеет место однозначное соответствие исходной и преобразованной последовательности. Изменив вид функции на f(сигнатураi, gi, ai), где g – псевдослучайная последовательность, сгенерированная на основе ключа (или сам ключ, но это снизит криптостойкость), получим зависимость преобразованной последовательности от ключа. Для каждого из преобразований можно использовать различные участки гаммы. Причём из вышеописанного следует то, что малейшее изменение ключа приведёт к глобальному изменению всей преобразованной последовательности.
По криптостойкости прямое и обратное преобразование симметричны, поэтому можно пользоваться обратным преобразованием для зашифровки и прямым для расшифровки.
Такое преобразование уже не назовёшь гаммированием с обратной связью, как это описано в [1], это уже скорее свёртка.
Итак, данный алгоритм обеспечивает следующие возможности: если взять две идентичные последовательности, два идентичных ключа, и внести изменение (даже очень малое) в ключ или в исходную или в преобразованную последовательности, то после соответствующего преобразования, две полученные последовательности будут различаться между собой как две случайные. Соответственно анализ зашифрованного и соответствующего ему исходного текста с целью определить ключ мало что даст.
Данный алгоритм можно применить для потокового шифрования данных. Поскольку конечная часть последовательности в реальном времени недоступна, преобразования (3.6) и (3.8) следует исключить, а преобразования (3.5) и (3.7) объеденить. С одной стороны это повлияет на криптостойкость, поскольку нет влияния последующих битов на предыдущие, но с другой стороны конечная часть последовательности также недоступна для криптоанализа. Если процесс передачи данных допускает буферизацию хотя бы нескольких бит, то преобразования (3.6) и (3.8) можно модифицировать таким образом, чтобы они осуществлялись в пределах буфера. Следует предусмотреть процесс восстановления сигнатур в случае утери или искажения части сообщения, но это уже выходит за рамки статьи. Простейший способ – установка сигнатур в начальные (константные или определяемые по некоторому закону) значения после прохождения определённых объёмов данных и вставка синхронизирующей метки в последовательность. Выглядеть всё это будет приблизительно так:
// зашифровка
prev = prev2 = 0;
пока(не конец последовательности)
{
next = сигнатура(prev, ai);
ai = f(prev, gi, ai);
prev = next;
ai = f(prev2, g’i, ai);
prev2 = сигнатура(prev2, ai);
}
// расшифровка
prev = prev2 = 0;
пока(не конец последовательности)
{
next2 = сигнатура(prev2, ai);
ai = f
-1(prev2, g’i, ai);
prev2 = next2;
ai = f
-1(prev, gi, ai);
prev = сигнатура(prev, ai);
}
Сжатие двоичной последовательности в сигнатуру
Сигнатура – это небольшой объём информации, максимально характеризующей длинную двоичную последовательность. Сущность сигнатуры в том, что для двух различных последовательностей , сигнатуры, характеризующие их, с очень большой вероятностью различаются.
Для сжатия двоичной последовательности в сигнатуру используем следующее соотношение:
где y(k) Î {0,1} – k-й символ сжимаемой последовательности {y(k)}, k = 1..l; aiÎ{0,1} – коэффициенты порождающего полинома j(x); ai(k-1)Î{0,1} – содержимое i-го элемента памяти в k-1-й такт. Процедура сдвига информации описывается соотношением
aj(k) = aj-1(k-1), j = 2..m.
Для описания процедуры сжатия информации, основанной на применении примитивных полиномов, используются различные математические модели и алгоритмы. Одной из наиболее часто применяемых является модель, реализующая идею представления процедуры сжатия информации как операцию деления полиномов над полем GF(2). При этом в качестве делимого используется поток сжимаемых данных, описываемых полиномом c(x) степени l-1, где l-количество бит в последовательности. Так, например, последовательность 10011 имеет вид полинома c(х) = x4ÅxÅ1. Делителем служит примитивный полином y(х), в результате деления на который получается частное q(х) и остаток S(х), связанные классическим соотношением вида
c(x) = q(x)y(x) Å S(x), (2.3)
где остаток S(х), представляющий собой полином степени, меньшей, чем
m = deg y(x), называется сигнатурой.
Результат сжатия C(x) (m-разрядное число, содержащееся в a1..am), получающийся по выражению (2.2), не совпадает с S(x), C(x)¹S(x), но линейно с ним связан.
Каковы же вероятности того, что сигнатуры различаются для двух различных последовательностей? Сигнатуры различаются для двух последовательностей любой длины l, отличающихся на один бит, и для всех последовательностей длиной l£2m-1, отличающихся на два любых бита [2]. Для n-кратных изменений (l=2m-2), при достаточно большом m, сигнатуры различаются с вероятностью » 1-1/2m, что при m>7 практически равно единице. Единственный параметр, влияющий на значения вероятности - старшая степень m полинома j(х). Дальнейшие упоминания о таких вероятностях будут менее точны, поэтому когда надо будет уточнить, обращайтесь к этому абзацу.
В данной статье рассматривается подход
В данной статье рассматривается подход к созданию криптоалгоритмов, преобразующих исходный текст таким образом, чтобы трудоёмкость его анализа была не ниже полного перебора всего множества ключей, а также невозможно осмысленная модификация зашифрованного сообщения без точного знания ключа.
В отличие от некоторых других статей, описывающих «доисторические» криптоалгоритмы, единственное достоинство которых в том, что их использование не надо лицензировать у спецслужб, рассматриваемый симметричный криптоалгоритм базируется на современной теории двоичных полиномов и обеспечивает невозможность анализа шифрованного текста существующими технологиями. Тут уже никакой «хакер» не сможет взломать шифр ни на бумажке, ни на своём энном пентиуме, а при выборе соответствующей длины ключа, шифр невозможно будет взломать всеми вычислительными средствами планеты в разумные сроки. Описываемый алгоритм прост и легко реализуем, работает достаточно быстро, поскольку не использует трудоёмких операций вроде умножения и деления, время его выполнения линейно зависит от объёма текста и несущественно зависит от длины ключа (но существенно зависит от вида полинома). Алгоритм легко реализуем аппаратно.
в серьёзных целях необходимо строгое
Описанный алгоритм достигает поставленные цели.
Для использования описанного алгоритма в серьёзных целях необходимо строгое доказательство того, что любой анализ зашифрованного таким образом текста по трудоёмкости будет не ниже перебора всего множества ключей, а также оценка зависимости времени перебора от длины ключа. Как уже упоминалось, для генерации гаммы необходимо выбрать примитивный неприводимый полином соответствующей степени.
Сама программа и исходные тексты прилагаются.
Спасибо за внимание. Ваше мнение ?
Зашифровка
фаза 1 – защита от изменений в исходном тексте
// прямой ход (3.5)
prev = 0;
для i от 1 до k
{
next = сигнатура(prev, ai);
ai = f(prev, ai);
prev = next;
}
// обратный ход (3.6)
prev = 0;
для i от k до 1
{
next = сигнатура(prev, ai);
ai = f(prev, ai);
prev = next;
}
фаза 2 – защита от изменений в зашифрованном тексте
// прямой ход (3.7)
prev = 0;
для i от 1 до k
{
ai = f(prev, ai);
prev = сигнатура(prev, ai);
}
// обратный ход (3.8)
prev = 0;
для i от k до 1
{
ai = f(prev, ai);
prev = сигнатура(prev, ai);
}
