Информационная емкость позиционных систем счисления

Исторически сложилось так, что наиболее распространенной системой счисления является десятичная. Это, вероятнее всего, связано с количеством пальцев на руках, которые изначально применялись для простейших математических вычислений. Данная система счисления является позиционной, то есть системой, в которой один и тот же знак имеет различные значения в зависимости от места, где он расположен. В компьютерной среде наибольшее распространение получили двоичная (бинарная) система счисления с основанием 2 и более компактная шестнадцатеричная система счисления с основанием 16.

Интерес автора к информационной емкости систем счисления вызван необходимостью кодирования и передачи информации через сеть интернет, а именно для генерации ключей активации к программным продуктам. Разработчики программ встают перед проблемой кодирования информации с максимумом информации и минимально конечной длиной, что вызвано недовольством пользователей при вводе длинных цепочек символов для активации программы. Обычно цепочка символов разбивается на группы и адекватно воспринимается пользователями при длине до 20-25 символов. Чем меньше длина цепочки, тем меньше проблем с поддержкой пользователей из за возможных ошибок при вводе ключа, но при этом стойкость ключа уменьшается, да и количество дополнительной служебной информации существенно ограничено. Чаще всего для кодирования таких последовательностей используют шестнадцатеричную систему счисления.

В используемых для разработки программ языках программирования для работы с данной системой счисления уже есть достаточно много встроенных функций. Но так как шестнадцатеричная система счисления использует лишь арабские цифры (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) и буквы латинского алфавита (A, B, C, D, E, F), мы теряем возможность передавать максимум информации при кодировании. Так как ключи пользователям обычно высылаются посредством электронной почты, было бы более целесообразным использовать остальные символы латинского алфавита. Существует стандарт на такую систему счисления с основанием 36 (base 36), который базируется на арабских цифрах (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) и буквах латинского алфавита (A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z). При этом, например, цепочка длиной в три символа позволит закодировать число ZZZ36 = 4665510, а в шестнадцатеричной системе — только FFF16 = 409510, что позволит закодировать информацию, например, о 46655 / 365 = 127.8 годах триального срока вместо 4095 / 365 = 11.2, что с лихвой покрывает жизненный цикл типового программного продукта. Для демонстрации различий систем счислений автором разработана простая программа преобразования из одной системы счисления в другую. Пример работы с ней показан на рис. 1.

Рис. 1. Программа преобразования из одной системы счисления в другую

В данной программе для кодирования и раскодирования используются следующие функции (использовался Turbo Delphi):

unit uConvertLib;
// Copyright (C) 2007 Berdachuk Siarhei
// сайт
interface

uses
SysUtils;

const
BASE_36 = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';

{**
* Преобразование десятичного целого числа в строку числа по основанию base.
* @param num — целое десятичное число
* @param base — основание системы счисления
**}
function convertNum2Base(const num: longint; const base: word): string;

{**
* Преобразование строкового представления числа по основанию base в целое десятичное число.
* @param numStr — строковое представление числа по основанию base
* @param base — основание системы счисления
**}
function convertBase2Num(const numStr: string; const base: word): longint;

implementation

function convertNum2Base(const num: longint; const base: word): string;
var
n, rest: longint;
tmpStr: string;
begin
n := num;
tmpStr := '';
repeat
rest := n mod base;
n := n div base;
tmpStr := BASE_36[rest + 1] + tmpStr;
until n = 0;
result := tmpStr;
end;

function convertBase2Num(const numStr: string; const base: word): longint;
var
i: integer;
ext: longint;
tmpStr: string;
k: byte;
begin
tmpStr := UpperCase(numStr);
result := 0;
ext := 1;
for i := length(tmpStr) downto 1 do
begin
k := pos(tmpStr[i], BASE_36) — 1;
result := result + k * ext;
ext := ext * base;
end;
end;

end.

Еще одной интересной возможностью кода по основанию 36 является возможность шифрования коротких сообщений. Например, число 2923465210 можно интерпретировать как "HELLO", что можно использовать для сокрытия текстовой информации от банального поиска взломщиками по ресурсам или бинарному коду программы.

Примечание

На практике можно пожертвовать информационной емкостью кода в целях обеспечения более высокой помехозащищенности, изъяв неоднозначно интерпретируемые символы — например, символ "I" может быть воспринят как "1", а "O" — как цифра "0". Дополнительно можно переставить символы в произвольном порядке, что позволяет повысить устойчивость кода к взлому.

Практические тесты кода c основанием 32, для более высокой защищенности ограниченного символами "0123456789ABCDEFGHJKLMNPRTUVWXYZ" и автоматическим программным маппингом исключенных символов — например, O,Q -> 0 — показали, что его использование позволяет ужать состоящий из пяти секций по 6 символов ключ активации в аналог из пяти секций по 5 символов (секция не должна начинаться с нуля). Таким образом можно получить 5 дополнительных символов для служебной информации при длине ключа активации 25 символов.

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

Рекомендуемые ресурсы

Сайт проекта Numeric Converter: сайт

Сергей Бердачук, сайт