Федотов Валерий Павлович (matholimp) wrote in szip_i4,
Федотов Валерий Павлович
matholimp
szip_i4

Category:

Использование (новых) систем счисления для шифрования информации

Системы счисления можно использовать не только для кодирования информации (обязательного при её записи в памяти компьютера), но и для шифрования с целью последующей передачи по открытым каналам. Высокую эффективность в таком качестве проявляют башенные системы счисления, основаниями которых могут быть любые вещественные числа (большие 1.444668), а единообразная форма записи не позволяет злоумышленнику узнать, какое именно из бесконечно многих возможных оснований было использовано. Например, файл любого формата и назначения можно заменить соответствующим ему номером или дробным числом, перевести это число в одну башенную систему счисления, прочитать полученную последовательность цифр как запись в другой башенной системе счисления, а уже от этой записи перейти к исходной (или любой иной) форме представления файла (в виде текста, рисунка и т.д.).
Ликбез по системам счисления и связанным с ними алгоритмам удобнее всего пройти на сайте http://mashavph.narod.ru .
Задание для лабораторной работы
1. Запишите свою фамилию в кодировке Windows‑1251 и переведите её в 2-чную, 8-чную и 16-чную системы счисления.
2. В тех же системах счисления запишите соответствующее номеру дробное число.
3. Выделите из полученного дробного числа несколько старших аликвот.
4. Выпишите первые цифры записи полученного дробного числа в системе счисления Штерна-Броко.
Пояснительный текст и образец выполнения
1. Как известно, любой файл записывается в памяти компьютера в виде последовательности байтов. Если зафиксировать какую-либо из кодировок, то каждый байт можно рассматривать как цифру в системе счисления с основанием 256. Это позволяет единообразно занумеровать (хотя и запредельно большими числами) не только все тексты, но и все файлы любого типа и назначения.
Поясню на примере собственной фамилии. В кодировке Windows‑1251 (см. таблички в самом конце поста) заглавной букве Ф соответствует код 212, а строчным буквам: е - 229, д - 228, о - 238, т - 242, в - 226. Согласно схеме Горнера, слову Федотов соответствует число
(((((212х256+229)х256+228)х256+238)х256+242)х256+238)х256+226 . Легко видеть, что вычисление с помощью калькулятора или Excel приведет к потере точности. Поэтому нужно использовать специальные процедуры или иные средства, позволяющие сохранить все цифры.
Сравнительно легко переводить числа из одной основной системы счисления в другую в тех случаях, когда оба основания являются степенями одного и того же числа. Например, 256=28, а 8=23. Поэтому для перевода числа из 256-чной системы в 8-чную удобно сначала перевести в двоичную, для чего достаточно вместо каждого байта записать его 8-битовый двоичный код: Ф=212=110101002, е=229=111001012, д=228=111001002, о=238=111011102, т=242=111100102, в=226=111000102. Эти биты нужно записать единой строкой, перегруппировать по три (начиная с конца записи), а затем каждую триаду заменить соответствующей 8-чной цифрой:
Федотов256=
=11010100 11100101 11100100 11101110 11110010 11101110 111000102-256=
=110101001110010111100100111011101111001011101110111000102=
=11 010 100 111 001 011 110 010 011 101 110 111 100 101 110 111 011 100 0102-8=
=32471362356745673428 .
Еще проще перевести число из 256-чной системы в 16-чную. Так как 256=162, то достаточно лишь каждую букву заменить её дампом – парой 16-чных цифр: Федотов256=D4E5E4EEF2EEE216 .
2. Во многих случаях удобнее заменить огромные натуральные числа дробями со значениями от 0 до 1. Для этого достаточно рассматривать ту же последовательность знаков как цифры, следующие в записи числа сразу за запятой (точкой), разделяющей целую и дробную части числа:
.Федотов256=
=.110101001110010111100100111011101111001011101110111000102=
=.32471362356745673428=.D4E5E4EEF2EEE216
(здесь нужно лишь не забывать про передние нули первого байта записи, когда его код меньше 128).
3. Разложение дробного числа в сумму аликвот было известно еще жрецам Древнего Египта в IV тысячелетии до нашей эры. На каждом шаге ищется дробь вида 1/k с наименьшим k , при котором эта дробь не превосходит данного числа. Найденная дробь вычитается из данного числа, а затем то же самое делают с каждым очередным остатком. Например, 2/3 = 1/2 + 1/6 .
Вычисления удобнее проводить в двоичной (8-чной или 16-чной) системе счисления, для чего придется (обычным делением в столбик или на калькуляторе) вычислить в ней нужные дроби вида 1/k :
1/2 =.12
1/3 =.01010101010101010101010101010101010101010101010101…2
1/4 =.012
1/5 =.0011001100110011001100110011001100110011001100110011…2
1/6 =.001010101010101010101010101010101010101010101010101…2
1/7 =.001001001001001001001001001001001001001001001001001…2
1/8 =.0012
1/9 =.000111000111000111000111000111000111000111000111000111…2
1/10 =.00011001100110011001100110011001100110011001100110011…2
и т.д. (многоточиями обозначены периодические двоичные дроби).
В случае моей фамилии, прежде всего, нужно вычесть 1/2 (это можно сделать, так как двоичная запись начинается с цифры 1). Остаток начнется с цифр 010101001. Так как после четвертого нуля идет 0 (а не 1), то этот остаток меньше 1/3 (в записи которой нули и единицы строго чередуются). Значит, второе слагаемое в разложении - 1/4 . Очередной остаток 000101001 меньше 1/12 , но больше 1/13 .
Итак, .Федотов256= 1/2 + 1/4 + 1/13 + … .
4. Базовыми точками системы счисления Штерна-Броко на интервале от 0 до 1 служат дроби, образующие ряды Фарея:
0/1 1/2 1/1
0/1 1/3 1/2 2/3 1/1
0/1 1/4 1/3 2/5 1/2 3/5 2/3 3/4 1/1
(на каждом шаге между любыми двумя соседними дробями предыдущего ряда Фарея вставляется заключенная между ними дробь с наименьшим возможным знаменателем).
Чтобы перевести число из интервала от 0 до 1 в систему счисления Штерна-Броко нужно на каждом шаге сравнивать его подходящей дробью из очередного ряда Фарея, для нахождения которой достаточно по отдельности сложить числители и знаменатели ранее найденных ближайших к этому числу дробей. В зависимости от знака неравенства выбирается 0 или 1 в качестве очередной цифры искомой записи.
Например, .Федотов256 лежит между 1/2 и 1/1 . Сравнив с
2/3 =.101010101010101010101010101010101010101010101010101…2 , переходим на интервал между 2/3 и 1/1 .
Сумма числителей 2+1=3, сумма знаменателей 3+1=4. Сравнив с 3/4 =.112 , переходим на интервал между 3/4 и 1/1 .
Сумма числителей 3+1=4, сумма знаменателей 4+1=5. Сравнив с
4/5 =.11001100110011001100110011001100110011001100110011…2 , переходим на интервал между 4/5 и 1/1 .
Сумма числителей 4+1=5, сумма знаменателей 5+1=6. Сравнив с
5/6 =.1101010101010101010101010101010101010101010101010101…2 , переходим на интервал между 4/5 и 5/6 .
Сумма числителей 4+5=9, сумма знаменателей 5+6=11. Сравнив с
9/11 =.110100010101110100010101110100010101110100010101…2 , переходим на интервал между 9/11 и 5/6 . Следующее сравнения – с 14/17 .
Итак, сравнения с 1/2 , 2/3 , 3/4 и 4/5 дали положительный результат (цифра 1), с 5/6 - отрицательный (цифра 0), а с 9/11 снова положительный (цифра 1). Поэтому .Федотов256=0,111101…Штерна-Броко .
Стандартные кодировки русских букв и других символов
Первая из помещенных чуть ниже таблиц содержит семибитовые коды ASCII. В десятичной системе им соответствуют номера от 32 до 127. Чтобы узнать код символа, достаточно к числу десятков из первого столбца приписать число единиц из первой строки. Самые первые коды (от 0 до 31) – непечатаемые, (перевод строки, возврат каретки, табуляция и т. д.). Они не вошли в таблицу, так как зарезервированы за различными управляющими функциями. Код пробела равен 32. Большинство кодовых страниц Windows рассчитаны на восьмибитовую нумерацию. Поэтому они включают одни и те же коды с номерами от 0 до 127, а различаются только вторыми своими половинами.
Во второй табличке представлены символы с кодами 128—255 для кодировки Windows‑1251, использующейся в последних версиях Windows. В третьей - символы с кодами 128—255 для более ранней кодировки 0866, использовавшейся в ранних версиях Windows и DOS.
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments