Решение
Рассмотрим исходный код программы, написанный на языке C. Для удобства пронумеруем строки рассматриваемой функции:
int HASH(char *text)
{
int k=0, H; //1
char temp[6], letter = 'G'; //2
for(;(k
if (k < 6) for(;k<6;k++) temp[k]= letter; //4
H = ((temp[0]+temp[1]+temp[2])&7)*64; //5
H += ((temp[0]+temp[2]+temp[4])&7)*8; //6
H += ((temp[1]+temp[3]+temp[5])&7); //7 return H; //8
}
в программе использованы следующие переменные:
text – входной параметр функции, в которой передается строка, для которой будет вычислено значение функции.
k – вспомогательная переменная;
temp – символьный массив из 6 элементов, используемый для хранения промежуточных данных при вычислениях;
H – целое число типа int (для хранения результата используются младшие 9 бит, предназначенное для хранения результирующего значения.
В цикле, реализованном в строках 3, происходит выборка первых6 символов из входной строки.В строке 4 происходит проверка на длину строки temp. Если полученная в результате работы предыдущего цикла строка меньше 6, то она дополняется символами «G». Это преобразование существенно при подборе пароля. Таким образом, после выполнения этой части программы (с учетом того, что по условию задачи преобразуется пароль «КОНФИДЕНЦИАЛЬНОСТЬ») переменная tempбудет имеет заполнение «КОНФИД».
В строке с номером 5 начинает формироваться выходное значение: ASCII-коды нулевого, первого и второго символов буфера temp складываются (по модулю 8), а результата записывается в 6,7,8 биты переменной H. В результате выполнения строки 6 аналогично заполняются 3, 4, 5 биты H, а в строке 7 – биты с номерами от 0, 1, 2.Таким образом, после выполнения функции, в которой преобразуется пароль «КОНФИДЕНЦИАЛЬНОСТЬ», возвращаемый результат равен 38210 = 101 111 1102.
Для решения задачи необходимо предложить такой пароль, образ, которого полученный в результате работы функции будет равен 382. Заметим, что из-за процедуры составление строки temp, описанной выше, достаточно рассмотреть только пароли длинной менее 7 символов.
Запишем искомый пароль в виде a1a2a3a4a5a6. Учитывая описанный алгоритм построения образа и представление в двоичном виде образ пароля «КОНФИДЕНЦИАЛЬНОСТЬ», запишем систему уравнений, который должен удовлетворять искомый пароль:
Решение будем проводить перебором по размеру пароля.
Предположим, длина искомого пароля 0 или 1, тогда третье уравнение системы принимает вид 5 = 8 (mod 8). Таким образом, длина пароля должна быть больше 1.
Пусть длина искомого пароля равна 2, тогда temp[6] = “a1a2GGGG” и система принимает вид:
Данная система несовместна, а значит длина пароля больше 2. Аналогичный результата получается при рассмотрении пароля из трех символов (temp[6]=”a1a2a3GGGG”).
Пусть длина искомого пароля равна четырем, тогда temp[6] = “a1a2a3a4GGGG” и система принимает вид:
Вычитая из уравнения (1) уравнение (2) получаем a2=5, подставляя это значение в уравнение (3), получаем a4=2. А из уравнения (2) имеем, например, a1=3, a3=5. Таким образом, один из искомых паролей равен CEEB.