Справочная информация:
ФУНКЦИИ:
Функция copy(S,Pos,N) – выделяет из строки S подстроку длиной в N символов, начиная с позиции Pos , где Pos – цифра;
Пример: s1:=‘пРОГресс’ ; s2:=copy(s1,2,3) ; Результат s2=’рог’
Функция concat(S1,S2,..,SN) – выполняет сцепление строк S1,S2,..,SN в одну строку
Пример: k:=Concat(‘До-’,’Ре-’,’Ми’); Результат k=‘До-Ре-Ми’
Функция Length(S) – определяет текущую длину строки S.
Пример: S:=’День космонавтики’; k:=Length(S); Результат k=17
Функция Pos(S1,S2) – обнаруживает ПЕРВОЕ появление в строке S2 подстроки S1.
Результат – целое число. Пример: S2:=’комната’; k:= Pos(‘а’, S2); Результат k=5
Функция Ord(s1) - возвращает номер символьной переменой S1
Пример: S1:=’Д’; k:=Ord(S1); Результат k=196
Функция Chr(n)- возвращает номер символьной переменой S1
Пример: n:=196; S1:=Chr(n); Результат S1=’Д’
ПРОЦЕДУРЫ:
Процедура Delete(S,S2,N) –выполняет удаление N символов из строки S, начиная с позиции S2.
Пример: S:=’Победа’ ; Delete(S,1,2); Результат S=’беда’
Процедура Insert(S1,S2,n) –выполняет вставку строки S1 в строку S2, начиная с позиции n.
Пример: S2:=’Учиться интересно’; Insert(‘-очень-‘,S2,8);
Результат S2=’Учиться-очень- интересно’
Процедура Str(x:2, s) преобразовывает число в строку. Пример: x:=2.73284 s='2.73'
Процедура Val(s, x, Osh) преобразовывает строку в число. Параметр Osh должен иметь тип Integer. Пример: s='2.73' x:=2.73
Справочный материал по хэш-функциям |
http://cryptowiki.net/index.php?title=%D0%9A%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D1%85%D1%8D%D1%88-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B8
Проверка пароля В большинстве случаев парольные фразы не хранятся на целевых объектах, хранятся лишь их хэш-значения. Xранение самих паролей нецелесообразно, так как в случае несанкционированного доступа к файлу с паролями злоумышленник получает их в открытом и сразу готовом к использованию виде, а при хранении хэш-значений он узнает лишь хэши, которые не обратимы в исходные данные. В ходе процедуры аутентификации вычисляется хэш-значение введённого пароля, и сравнивается с хранимым.
http://www.securitylab.ru/blog/personal/shaurojen/22829.php Что такое хеш? Хеш-функцией называется математическое преобразование информации в короткую, определенной длины строку. Какими характеристиками должна обладать хеш-функция? - должна уметь выполнять преобразования данных произвольной длины в фиксированную; - должна иметь открытый алгоритм, чтобы можно было исследовать её криптостойкость; - должна быть односторонней, то есть не должно быть математической возможности по результату определить исходные данные; - должна «сопротивляться» коллизиям, то есть не должна выдавать одинаковых значений при разных входных данных; - не должна требовать больших вычислительных ресурсов; - при малейшем изменении входных данных результат должен существенно изменяться. Какие популярные алгоритмы хеширования? В настоящее время используются следующие хеш-функции: CRC– циклический избыточный код или контрольная сумма. Алгоритм весьма прост, имеет большое количество вариаций в зависимости от необходимой выходной длины. Не является криптографическим! MD5 – очень популярный алгоритм. Как и его предыдущая версия MD4 является криптографической функцией. Размер хеша 128 бит. SHA-1 – также очень популярная криптографическая функция. Размер хеша 160 бит. ГОСТ Р 34.11-94 – российский криптографический стандарт вычисления хеш-функции. Размер хеша 256 бит. http://edu.nstu.ru/courses/saod/hash_table.htm#Функция хеширования
Функция хеширования При выборе хеш-функций пользуются различными эвристиками, основанными на специфике задачи. Например, компилятор языка программирования хранит таблицу символов, в которой ключами являются идентификаторы программы. Часто в программе встречаются похожие идентификаторы (например, pt и pts). Хорошая хеш-функция будет стараться, чтобы хеш-значения у таких похожих идентификаторов были различны. Хеш-функцию стараются подобрать так, чтобы её поведение не коррелировало с различными закономерностями в хешируемых данных. Но на практике заранее неизвестно, какие именно значения ключей будут храниться в хеш-таблице. На всякий случай хеш-функцию разумно сделать “случайной”, обеспечивающей равномерное хеширование, т.е. для любого ключа все m хеш - значений должны быть равновероятны. Но случайная функция должна при повторных вызовах с одним и тем же ключом возвращать одно и то же хеш-значение. Существует много способов создания функций хеширования, использующих преобразование произвольного натурального числа к натуральному индексу, лежащему в заданном диапазоне 0 .. m. Например, последовательности ASCII-символов можно интерпретировать как целые числа, записанные в системе счисления с основанием 256. Метод деления с остатком (модульное хеширование) даёт простые и эффективные хеш-функции. Ключу k ставится в соответствие остаток от деления k на m. Хеш-функция вычисляется, как уравнение h(k) = k mod m. Например, если m=13, k=100, то h(k)=9. Плохо, если m – кратно 2, в этом случае h(k) четных k – четные, а нечетных k – нечетные. Плохо, если m кратно 3 для символьных и десятичных ключей, т. к. 10P/3 = 4P/3 =1, а 4P – основание символьных ключей. Можно поэкспериментировать с реальными данными для исследования того, насколько равномерно будут распределены их хеш-значения. Пример: плохого и хорошего значений m: М1=100, h1(k)=k mod 100 М2=101, h2(k)=k mod 101 k | 99 | 199 | 1099 | 4399 | 200199 | 303 | 707 | 100 | 200 | h1 | 99 | 99 | 99 | 99 | 99 | 3 | 7 | 0 | 0 | h2 | 99 | 98 | 89 | 56 | 8 | 0 | 0 | 100 | 99 | Значения, дающие коллизии при любом М – числа, кратные m, m + 1, . . . , m + m-1. Метод хорошо работает, если в качестве m выбирать простые числа, близкие к степени двойки. Ниже приведены рекомендуемые размеры хеш-таблиц (числа Мерсенне) для модульного хеширования: n | d | 2n - d | 8 | 5 | 251 | 9 | 3 | 509 | 10 | 3 | 1 021 | 11 | 9 | 2 039 | 12 | 3 | 4 093 | 13 | 1 | 8 191 | 14 | 3 | 16 381 | 15 | 19 | 32 749 | 16 | 15 | 65 521 | 17 | 1 | 131 071 | 18 | 5 | 262 139 | 19 | 1 | 524 287 | 20 | 3 | 1 048 573 | 21 | 9 | 2 097 143 | 22 | 3 | 4 194 301 | 23 | 15 | 8 388 593 | 24 | 3 | 16 777 213 | 25 | 39 | 33 554 393 | Метод выбора цифр Хеш-функция, основанная на выборе цифр, формирует хеш-значение, как комбинацию отдельных цифр ключа. Например, для хеш-таблицы с размером m = 1000 из 12-значного ключа 12376945012310 можно выбрать первую, шестую и двенадцатую цифры и сформировать индекс 14310 или 34110 , если выбирать цифры в обратном порядке. Для уменьшения вероятности коллизий рекомендуется также учитывать номера позиций, из которых выбираются цифры. Для этого значение выбранной цифры можно складывать с номером позиции по модулю основания системы счисления. Например для ключа 7777777777710 с учетом номеров позиций цифр получается индекс 72710 , а для ключа 7777710 - 19710 . Запись цифр в позиционной десятичной системе и будет представлять хеш-значение, лежащее в диапазоне от 0 до 99910. Но такой способ хеширования оправдывает себя, если ключи элементов, вставляемых в таблицу, равномерно распределены на всём диапазоне значений. Метод свёртки Метод свёртки группирует цифры ключа и складывает группы цифр по модулю m. Например, для m = 1000 ключ 12376945012310 можно преобразовать по схеме: (12310 + 76910 + 45010 + 12310 ) mod 1000 = 46510 . Для уменьшения вероятности коллизий рекомендуется также учитывать номера групп, которые выбираются из ключа. Для этого значение цифр в выбранной группе можно складывать с номером группы по модулю основания системы счисления. Например, без учета номеров групп ключи 987123456 и 456987123 дадут одинаковое хеш - значение по методу свертки: (98710 + 12310 + 45610) mod 1000 = 56610 (45610 + 98710 + 12310) mod 1000 = 56610 Если с каждой цифрой сложит номер ее позиции по модулю 10, то получатся хеш - значения: (10910 + 23410 + 45610) mod 1000 =79910 (67810 + 09810 + 12310) mod 1000 = 89910 Можно применять свёртку, комбинированную с выбором цифр. Например, сначала выполняется простое суммирование групп цифр ключа, а из полученной суммы выбирается нужное количество цифр. |
|
Вариант 1
Составить программы на ПК и заполнить таблицу результатов
Уровень А.
1. Составить логин для каждого кадета из списка по следующему правилу: первые пять букв фамилии и первая буква имени. Фамилия и имя кадета вводятся с помощью клавиатуры.
2. Определить хэш-код логина через простейшую хэш-функцию: сумма кодов ASCII букв логина. Записать в таблицу хэш-коды.
3. Подсчитать количество коллизий.
4. Сделать вывод о криптоустойчивости хэш-функции ________________________________________
_______________________________________________________________________________________
№ | Фамилия | Имя | логин | Хэш-код 1 | Коллизии |
1 | Иванов | Иван | | | |
2 | Иванчиков | Илья | | |
3 | Ивановских | Иннокентий | | |
4 | Иванова | Ирина | | |
5 | Иванников | Ильдар | | |
Уровень В.
1. В предыдущей программе изменить простейшую хэш-функцию на собственную. Для этого составить логин для каждого кадета из списка по собственному правилу, хэш-функция – сумма кодов ASCII букв логина. Записать в таблицу хэш-коды.
3. Подсчитать количество коллизий.
4. Сделать вывод о криптоустойчивости хэш-функции. _______________________________________
_______________________________________________________________________________________
№ | Фамилия | Имя | логин | Хэш-код 2 | Коллизии |
1 | Иванов | Иван | | | |
2 | Иванчиков | Илья | | |
3 | Ивановских | Иннокентий | | |
4 | Иванова | Ирина | | |
5 | Иванников | Ильдар | | |
Уровень С.
1. Добавить в программу возможность создавать случайный трехзначный числовой пароль.
2. Добавьте хэш-функцию, преобразующую этот пароль в десятичный 8-значный код (например, пароль – 123, хэш-код – 80147801).
2. Составить программу подбора числового пароля и хэш-кода методом перебора.
3. Добавить в программу счетчик попыток. В таблице указать количество попыток для взлома каждого пароля.
4. Сделайте вывод о криптоустойчивости пароля и хэш-кода: __________________________________
__________________________________________________________________________________
№ | Пароль | Хэш-код | Количество попыток |
Пароль | Хэш-код |
1 | | | | |
2 | | | | |
3 | | | | |
4 | | | | |
5 | | | | |
Вариант 2
Составить программы на ПК и заполнить таблицу результатов
Уровень А.
1. Составить логин для каждого кадета из списка по следующему правилу: первые пять букв фамилии и первая буква имени. Фамилия и имя кадета вводятся с помощью клавиатуры.
2. Определить хэш-код логина через простейшую хэш-функцию: сумма кодов ASCII букв логина. Записать в таблицу хэш-коды.
3. Подсчитать количество коллизий.
4. Сделать вывод о криптоустойчивости хэш-функции ________________________________________
_______________________________________________________________________________________
№ | Фамилия | Имя | логин | Хэш-код 1 | Коллизии |
1 | Сергеев | Александр | | | |
2 | Сергеичев | Антон | | |
3 | Сергеев | Иван | | |
4 | Серёгин | Алексей | | |
5 | Серёгина | Анастасия | | |
Уровень В.
1. В предыдущей программе изменить простейшую хэш-функцию на собственную. Для этого составить логин для каждого кадета из списка по собственному правилу, хэш-функция – сумма кодов ASCII букв логина. Записать в таблицу хэш-коды.
3. Подсчитать количество коллизий.
4. Сделать вывод о криптоустойчивости хэш-функции. _______________________________________
_______________________________________________________________________________________
№ | Фамилия | Имя | логин | Хэш-код 2 | Коллизии |
1 | Сергеев | Александр | | | |
2 | Сергеичев | Антон | | |
3 | Сергеев | Иван | | |
4 | Серёгин | Алексей | | |
5 | Серёгина | Анастасия | | |
Уровень С.
1. Добавить в программу возможность создавать случайный трехзначный числовой пароль.
2. Добавьте хэш-функцию, преобразующую этот пароль в десятичный 8-значный код (например, пароль – 123, хэш-код – 80147801).
2. Составить программу подбора числового пароля и хэш-кода методом перебора.
3. Добавить в программу счетчик попыток. В таблице указать количество попыток для взлома каждого пароля.
4. Сделайте вывод о криптоустойчивости пароля и хэш-кода: _________________________________
__________________________________________________________________________________
№ | Пароль | Хэш-код | Количество попыток |
Пароль | Хэш-код |
1 | | | | |
2 | | | | |
3 | | | | |
4 | | | | |
5 | | | | |
Вариант 3
Составить программы на ПК и заполнить таблицу результатов
Уровень А.
1. Составить логин для каждого кадета из списка по следующему правилу: первые пять букв фамилии и первая буква имени. Фамилия и имя кадета вводятся с помощью клавиатуры.
2. Определить хэш-код логина через простейшую хэш-функцию: сумма кодов ASCII букв логина. Записать в таблицу хэш-коды.
3. Подсчитать количество коллизий.
4. Сделать вывод о криптоустойчивости хэш-функции ________________________________________
_______________________________________________________________________________________
№ | Фамилия | Имя | логин | Хэш-код 1 | Коллизии |
1 | Костин | Павел | | | |
2 | Костиков | Петр | | |
3 | Костичев | Глеб | | |
4 | Костичев | Платон | | |
5 | Костиков | Геннадий | | |
Уровень В.
1. В предыдущей программе изменить простейшую хэш-функцию на собственную. Для этого составить логин для каждого кадета из списка по собственному правилу, хэш-функция – сумма кодов ASCII букв логина. Записать в таблицу хэш-коды.
3. Подсчитать количество коллизий.
4. Сделать вывод о криптоустойчивости хэш-функции. _______________________________________
_______________________________________________________________________________________
№ | Фамилия | Имя | логин | Хэш-код 2 | Коллизии |
1 | Костин | Павел | | | |
2 | Костиков | Петр | | |
3 | Костичев | Глеб | | |
4 | Костичев | Платон | | |
5 | Костиков | Геннадий | | |
Уровень С.
1. Добавить в программу возможность создавать случайный трехзначный числовой пароль.
2. Добавьте хэш-функцию, преобразующую этот пароль в десятичный 8-значный код (например, пароль – 123, хэш-код – 80147801).
2. Составить программу подбора числового пароля и хэш-кода методом перебора.
3. Добавить в программу счетчик попыток. В таблице указать количество попыток для взлома каждого пароля.
4. Сделайте вывод о криптоустойчивости пароля и хэш-кода: __________________________________
__________________________________________________________________________________
№ | Пароль | Хэш-код | Количество попыток |
Пароль | Хэш-код |
1 | | | | |
2 | | | | |
3 | | | | |
4 | | | | |
5 | | | | |
Вариант 4
Составить программы на ПК и заполнить таблицу результатов
Уровень А.
1. Составить логин для каждого кадета из списка по следующему правилу: первые пять букв фамилии и первая буква имени. Фамилия и имя кадета вводятся с помощью клавиатуры.
2. Определить хэш-код логина через простейшую хэш-функцию: сумма кодов ASCII букв логина. Записать в таблицу хэш-коды.
3. Подсчитать количество коллизий.
4. Сделать вывод о криптоустойчивости хэш-функции ________________________________________
_______________________________________________________________________________________
№ | Фамилия | Имя | логин | Хэш-код 1 | Коллизии |
1 | Добров | Никита | | | |
2 | Добряков | Николай | | |
3 | Добряков | Сергей | | |
4 | Добрянский | Сергей | | |
5 | Добровский | Наум | | |
Уровень В.
1. В предыдущей программе изменить простейшую хэш-функцию на собственную. Для этого составить логин для каждого кадета из списка по собственному правилу, хэш-функция – сумма кодов ASCII букв логина. Записать в таблицу хэш-коды.
3. Подсчитать количество коллизий.
4. Сделать вывод о криптоустойчивости хэш-функции. _______________________________________
_______________________________________________________________________________________
№ | Фамилия | Имя | логин | Хэш-код 2 | Коллизии |
1 | Добров | Никита | | | |
2 | Добряков | Николай | | |
3 | Добряков | Сергей | | |
4 | Добрянский | Сергей | | |
5 | Добровский | Наум | | |
Уровень С.
1. Добавить в программу возможность создавать случайный трехзначный числовой пароль.
2. Добавьте хэш-функцию, преобразующую этот пароль в десятичный 8-значный код (например, пароль – 123, хэш-код – 80147801).
2. Составить программу подбора числового пароля и хэш-кода методом перебора.
3. Добавить в программу счетчик попыток. В таблице указать количество попыток для взлома каждого пароля.
4. Сделайте вывод о криптоустойчивости пароля и хэш-кода: _______________________________________
__________________________________________________________________________________
№ | Пароль | Хэш-код | Количество попыток |
Пароль | Хэш-код |
1 | | | | |
2 | | | | |
3 | | | | |
4 | | | | |
5 | | | | |
Вариант 5
Составить программы на ПК и заполнить таблицу результатов
Уровень А.
1. Составить логин для каждого кадета из списка по следующему правилу: первые пять букв фамилии и первая буква имени. Фамилия и имя кадета вводятся с помощью клавиатуры.
2. Определить хэш-код логина через простейшую хэш-функцию: сумма кодов ASCII букв логина. Записать в таблицу хэш-коды.
3. Подсчитать количество коллизий.
4. Сделать вывод о криптоустойчивости хэш-функции ________________________________________
_______________________________________________________________________________________
№ | Фамилия | Имя | логин | Хэш-код 1 | Коллизии |
1 | Борисова | Елена | | | |
2 | Борисов | Евгений | | |
3 | Борисевич | Елисей | | |
4 | Борсинов | Елисей | | |
5 | Борсинова | Елизавета | | |
Уровень В.
1. В предыдущей программе изменить простейшую хэш-функцию на собственную. Для этого составить логин для каждого кадета из списка по собственному правилу, хэш-функция – сумма кодов ASCII букв логина. Записать в таблицу хэш-коды.
3. Подсчитать количество коллизий.
4. Сделать вывод о криптоустойчивости хэш-функции. _______________________________________
_______________________________________________________________________________________
№ | Фамилия | Имя | логин | Хэш-код 2 | Коллизии |
1 | Борисова | Елена | | | |
2 | Борисов | Евгений | | |
3 | Борисевич | Елисей | | |
4 | Борсинов | Елисей | | |
5 | Борсинова | Елизавета | | |
Уровень С.
1. Добавить в программу возможность создавать случайный трехзначный числовой пароль.
2. Добавьте хэш-функцию, преобразующую этот пароль в десятичный 8-значный код (например, пароль – 123, хэш-код – 80147801).
2. Составить программу подбора числового пароля и хэш-кода методом перебора.
3. Добавить в программу счетчик попыток. В таблице указать количество попыток для взлома каждого пароля.
4. Сделайте вывод о криптоустойчивости пароля и хэш-кода: _______________________________________
__________________________________________________________________________________
№ | Пароль | Хэш-код | Количество попыток |
Пароль | Хэш-код |
1 | | | | |
2 | | | | |
3 | | | | |
4 | | | | |
5 | | | | |