Учебники. Программирование для начинающих.
Programm.ws — это сайт, на котором вы можете почитать литературу по языкам программирования , а так-же посмотреть примеры работающих программ на С++, ассемблере, паскале и много другого..
Программирование — в обычном понимании, это процесс создания компьютерных программ.
В узком смысле (так называемое кодирование) под программированием понимается написание инструкций — программ — на конкретном языке программирования (часто по уже имеющемуся алгоритму — плану, методу решения поставленной задачи). Соответственно, люди, которые этим занимаются, называются программистами (на профессиональном жаргоне — кодерами), а те, кто разрабатывает алгоритмы — алгоритмистами, специалистами предметной области, математиками.
В более широком смысле под программированием понимают весь спектр деятельности, связанный с созданием и поддержанием в рабочем состоянии программ — программного обеспечения ЭВМ. Более точен современный термин — «программная инженерия» (также иначе «инженерия ПО»). Сюда входят анализ и постановка задачи, проектирование программы, построение алгоритмов, разработка структур данных, написание текстов программ, отладка и тестирование программы (испытания программы), документирование, настройка (конфигурирование), доработка и сопровождение.
Ассемблер — примеры и задачи
Глава 2. Сложные структуры данных
Обработка коллизий
Для обработки коллизий используются две группы методов:
- закрытые — в качестве резервных используются ячейки самой хэш-таблицы;
- открытые — для хранения элементов с одинаковыми хэш-адресами используется отдельная область памяти.
Видно, что эти группы методов разрешения коллизий соответствуют классификации алгоритмов хэширования — они тоже делятся на открытые и закрытые. Яркий пример открытых методов — метод цепочек, который сам по себе является самостоятельным методом хэширования. Он несложен, и мы рассмотрим его несколько позже.
Закрытые методы разрешения коллизий более сложные. Их основная идея — при возникновении коллизии попытаться отыскать в хэш-таблице свободную ячейку. Процедуру поиска свободной ячейки называют пробитом, или рехэшировани-ем (вторичным хэшированием). При возникновении коллизии к первоначальному хэш-адресу А(К) добавляется некоторое значение р, и вычисляется выражение (2.5). Если новый хэш-адрес А(К) опять вызывает коллизию, то (2.5) вычисляется при р2, и так далее:
А(К) = (A(K)+Pi)mod М (I = 0..М). (2.5)
push ds popes
lea si .buf.len_in
mov cl .buf .lenjn
inccx :длину тоже нужно захватить
add di .lenjd repmovsb
jmp ml displ: :выводим идентификатор, вызвавший коллизию, на экран
рехэширование
;ищем место для идентификатора, вызвавшего коллизию в таблице, путем линейного рехэширования i nc bx mov ax.bx jmp m5
Коллизия хеш-функции
Коллизией хеш-функции 
называется два различных входных блока данных 
и 
таких, что 
Коллизии существуют для большинства хеш-функций, но для «хороших» хеш-функций частота их возникновения близка к теоретическому минимуму. В некоторых частных случаях, когда множество различных входных данных конечно, можно задать инъективную хеш-функцию, по определению не имеющую коллизий. Однако для хеш-функций, принимающих вход переменной длины и возвращающих хеш постоянной длины (таких как MD5), коллизии обязаны существовать, поскольку хотя бы для одного значения хеш-функции соответствующее ему множество входных данных (полный прообраз) будет бесконечно — и любые два набора данных из этого множества образуют коллизию.
Пример
Рассмотрим в качестве примера хеш-функцию , определённую на множестве целых чисел. Её область значений состоит из 19 элементов (кольца вычетов по модулю 19), а область определения — бесконечна. Так как множество прообразов заведомо больше множества значений, коллизии обязаны существовать.
Построим коллизию для этой хеш-функции для входного значения 38, хеш-сумма которого равна нулю. Так как функция — периодическая с периодом 19, то для любого входного значения y, значение y + 19 будет иметь ту же хеш-сумму, что и y. В частности, для входного значения 38 той же хеш-суммой будут обладать входные значения 57, 76, и т. д. Таким образом, пары входных значений (38,57), (38,76) образуют коллизии хеш-функции .
Коллизии криптографических хеш-функций
Так как криптографические хеш-функции используются для подтверждения неизменности исходной информации, то возможность быстрого отыскания коллизии для них обычно равносильна дискредитации. Например, если хеш-функция используется для создания цифровой подписи, то умение находить для неё коллизии фактически равносильно умению подделывать цифровую подпись. Поэтому мерой криптостойкости хеш-функции считается вычислительная сложность нахождения коллизии. В идеале не должно существовать способа отыскания коллизий более быстрого, чем полный перебор. Если для некоторой хеш-функции находится способ получения коллизий существенно более быстрый, чем полный перебор, то эта хеш-функция перестаёт считаться криптостойкой и использоваться для передачи и хранения секретной информации. Теоретические и практические вопросы отыскания и использования коллизий ежегодно обсуждаются в рамках международных конференций (таких как CRYPTO или ASIACRYPT), на большом количестве ресурсов Интернета, а также во множестве публикаций.
Свойства криптографических хеш-функций
Основная статья: Криптографическая хеш-функция
Для того, чтобы хеш-функция H считалась криптографически стойкой, она должна удовлетворять трём основным требованиям, на которых основано большинство применений хеш-функций в криптографии:
- Необратимость: для заданного значения хеш-функции m должно быть практически невозможно найти блок данных
, для которого 
. - Стойкость к коллизиям первого рода: для заданного сообщения M должно быть практически невозможно подобрать другое сообщение N, для которого
. - Стойкость к коллизиям второго рода: должно быть практически невозможно подобрать пару сообщений
, имеющих одинаковый хеш.
Использование коллизий для взлома
В качестве примера можно рассмотреть простую процедуру аутентификации пользователя:
- при регистрации в системе пользователь вводит свой пароль, к которому применяется некоторая хеш-функция, значение которой записывается в базу данных;
- при каждом вводе пароля, к нему применяется та же хеш-функция, а результат сравнивается с тем, который записан в БД.
При таком подходе, даже если злоумышленник получит доступ к базе данных, он не сможет восстановить исходные пароли пользователей (при условии необратимости используемой хеш-функции). Однако, если злоумышленник умеет находить коллизии для используемой хеш-функции, ему не составит труда найти поддельный пароль, который будет иметь ту же хеш-сумму, что и пароль пользователя.
Можно использовать коллизии для подделки сообщений: информация о валютных операциях, к примеру, часто шифруется посредством хеш-функций; злоумышленник, обладая методом нахождения коллизий этой хеш-функции, может заменить сообщение поддельным и тем самым повлиять на ход валютной операции.
Схожим образом можно использовать коллизии для подделки цифровых подписей и сертификатов.
Защита от использования коллизий
Существует ряд методов защиты от взлома, защиты от подделки паролей, подписей и сертификатов, даже если злоумышленнику известны методы построения коллизий для какой-либо хеш-функции.
Одним из методов является метод «salt», применяемый при хранении UNIX-паролей — добавление некоторой последовательности символов перед хешированием. Иногда, эта же последовательность добавляется и к полученному хешу. После такой процедуры итоговые хеш-таблицы значительно сложнее анализировать, а так как эта последовательность секретна, существенно повышается сложность построения коллизий — злоумышленнику должна быть также известна последовательность «salt».
Другим методом является конкатенация хешей, получаемых от двух различных хеш-функций. При этом, чтобы подобрать коллизии к хеш-функции 
, являющейся конкатенацией хеш-функций 
и 
, необходимо знать методы построения коллизий и для , и . Недостатком конкатенации является увеличение размера хеша, что не всегда приемлемо в практических приложениях.
Методы поиска коллизий
Одним из самых простых и универсальных методов поиска коллизий является атака «дней рождения». С помощью этой атаки отыскание коллизии для хеш-функции разрядности 
битов потребует в среднем около 
, можно вычислить 
; которая, для некоторых хеш-функций, работает даже при обеспечении стойкости к коллизиям первого рода, стойкости к коллизиям второго рода, а также свойства необратимости. Подразумевается, что нет необходимости знать , а достаточно знать лишь его хеш. Таким образом можно, например, дописывать дополнительную информацию к чужому сообщению. Для предотвращения этой атаки используют различные методы: добавляют дополнительный раунд при хешировании, отличный от предыдущих; применяют многократное хеширование; или используют комбинацию предыдущих 2х методов.
Но атаку расширения можно рассмотреть и с другой стороны: если у нас есть некоторое сообщение , и хэш-функция уязвима к атаке расширения, то легко можно найти коллизию первого рода: 
, 
, 
, то есть нарушается свойство стойкости к коллизиям первого рода.
Большая часть современных хеш-функций имеют одинаковую структуру, основанную на разбиении входного текста на блоки и последующем итерационном процессе, в котором на каждой итерации используется некоторая функция 
, где x — очередной блок входного текста, а y — результат предыдущей операции. Однако такая схема несовершенна, так как, зная функцию 
, можно проводить анализ данных в промежутках между итерациями, что облегчает поиск коллизий.
Часто нахождению коллизий хеш-функций предшествует нахождение её псевдоколлизий, то есть двух разных значений начального буфера, которые для одного и того же сообщения дают равные значения хеш-функции.
Коллизии хеш-функций MD4 и MD5
Основная статья: MD5#Коллизии MD5
В 1996 году Ганс Доббертин нашёл псевдоколлизии в MD5, используя определённые инициализирующие векторы, отличные от стандартных. Оказалось, что можно для известного сообщения построить второе, такое, что оно будет иметь такой же хеш, как и исходное. C точки зрения математики это означает: MD5(IV,L1) = MD5(IV,L2), где IV — начальное значение буфера, а L1 и L2 — различные сообщения.
В 2004 году китайские исследователи Ван Сяоюнь (Wang Xiaoyun), Фэн Дэнго (Feng Dengguo), Лай Сюэцзя (Lai Xuejia) и Юй Хунбо (Yu Hongbo) объявили об обнаруженной ими уязвимости в алгоритме, позволяющей за небольшое время (1 час на сервере IBM p690 (англ.) русск. ) находить коллизии.
В 2005 году исследователи Ван Сяоюнь и Юй Хунбо из университета Шаньдуна в Китае, опубликовали алгоритм для поиска коллизий в хеш-функции MD5, причём их метод работает для любого инициализирующего вектора, а не только для вектора, используемого по стандарту. Применение этого метода к MD4 позволяет найти коллизию меньше чем за секунду. Он также применим и к другим хеш-функциям, таким как RIPEMD и HAVAL.
В 2008 году Сотиров Александр, Марк Стивенс (Marc Stevens), Якоб Аппельбаум (Jacob Appelbaum) опубликовали на конференции 25th Chaos Communication Congress статью, в которой показали возможность генерирования поддельных цифровых сертификатов, на основе использования коллизий MD5.
Коллизии хеш-функции SHA-1
Основная статья: SHA-1#Криптоанализ
В январе 2005 года Винсент Рэймен и Elisabeth Oswald опубликовали сообщение об атаке на усеченную версию SHA-1 (53 раунда вместо 80), которая позволяет находить коллизии меньше, чем за 2 80 операций.
В феврале 2005 года Ван Сяоюнь, Лиза Инь Ицюнь и Юй Хунбо представили атаку на полноценный SHA-1, которая требует менее 2 69 операций.
В августе 2005 года на CRYPTO 2005 эти же специалисты представили улучшенную версию атаки на полноценный SHA-1, с вычислительной сложностью в 2 63 операций. В декабре 2007 года детали этого улучшения были проверены Мартином Кохраном.
Кристоф де Каньер и Кристиан Рехберг позже представили усовершенствованную версию атаки на SHA-1, за что были удостоены награды за лучшую статью на конференции ASIACRYPT 2006. Ими была представлена двух-блоковая коллизия на 64-раундовый алгоритм с вычислительной сложностью около 2 35 операций.
Ввиду того, что теоретические атаки на SHA-1 оказались успешными, NIST планирует полностью отказаться от использования SHA-1 в цифровых подписях.
Коллизии других хеш-функций
Хеш функции RIPEMD и HAVAL также являются уязвимыми к алгоритму поиска коллизий MD5, опубликованному Ван Сяоюнь (Wang Xiaoyun), Фен Дэнгуо (Feng Dengguo), Лай Сюэцзя (Lai Xuejia) и Юй Хунбо (Yu Hongbo) в 2004 году.
Для второй модификации хеш-функции WHIRLPOOL, называемой Whirlpool-T, на 2009 год не предложено алгоритмов поиска коллизий или псевдоколлизий; существенным ограничением для их нахождения является сложность самой функции и большая длина (512 бит) выходного ключа.
Введение
Хеш-таблицы (HashMap) наравне с динамическими массивами являются самыми популярными структурами данных, применяемыми в production’е. Очень часто можно услышать вопросы на собеседованиях касаемо их предназначения, особенностей их внутреннего устройства, а также связанных с ними алгоритмов. Данная структура данных является классической и встречается не только в Java, но и во многих других языках программирования.
Постановка задачи
Давайте зададимся целью создать структуру данных, которая позволяет:
- contains(Element element) проверять, находится в ней некоторый элемент или нет, за О(1)
- add(Element element) добавлять элемент за О(1)
- delete(Element element) удалять элемент за О(1)
Массив
Попробуем сделать эти операции поверх массива, который является самой простой структурой данных. Договоримся, что будем считать ячейку пустой, если в ней содержится null.
Проверка наличия
Необходимо сделать линейный поиск по массиву, ведь элемент потенциально может находиться в любой ячейке. Асимптотически это можно осуществить за O(n), где n — размер массива.
Добавление
Если нам надо добавить элемент абы куда, то вначале мы должны найти пустую ячейку, а затем записать в нее элемент. Таким образом, мы опять осуществим линейный поиск и получим асимптотику O(n).
Удаление
Чтобы удалить элемент, его нужно сначала найти, а затем в найденную ячейку записать null. Опять линейный поиск приводит нас к O(n).
Простейшее хеш-множество
Обратите внимание, что при каждой операции, мы сначала искали индекс нужной ячейки, а затем осуществляли операцию, и именно поиск портит нам асимптотику! Если бы мы научились получать данный индекс за O(1), то исходная задача была бы решена.
Давайте теперь заменим линейный поиск на следующий алгоритм: будем вычислять значение некоторой фунции — хеш-функции, ставящей в соответствие объекту класса некоторое целое число. После этого будем сопоставлять полученное целое число индексу ячейки массива (это достаточно легко сделать, например, взяв остаток от деления этого числа на размер массива). Если хеш-функция написана так, что она считается за O(1) (а она так обычно и написана), то мы получили самую простейшую реализацию хеш-множества. Ячейка массива в терминах хеш-множества может называться bucket‘ом.
Проблемы простейшей реализации хеш-множества
Как бы ни была написана хеш-функция, число ячеек массива всегда ограничено, тогда как множество элементов, которые мы хотим хранить в структуре данных, неограничено. Ведь мы бы не стали заморачиваться со структурой данных, если бы была потребность в сохранении всего лишь десяти заранее известных элементов, верно? Такое положение дел приводит к неизбежным коллизиям. Под коллизией понимается ситуация, когда при добавлении разных объектов мы попадаем в одну и ту же ячейку массива.
Для разрешения коллизий придумано 2 метода: метод цепочек и метод открытой адресации.
Метод цепочек
Метод цепочек является наиболее простым методом разрешения коллизий. В ячейке массива мы будем хранить не элементы, а связанный список данных элементов. Потому как добавление в начало списка (а нам все равно в какую часть списка добавлять элемент) обладает асимптотикой О(1), мы не испортим общую асимптотику, и она останется равной О(1).
У данной реализации есть проблема: если списки будут очень сильно вырастать (в качестве крайнего случая можно рассмотреть хеш-функцию, которая возвращает константу для любого объекта), то мы получим асимптотику O(m), где m — число элементов во множестве, если размер массива фиксирован. Для избежания таких неприятностей вводится понятие коэффициент заполнения (он может быть равен, например, 1.5). Если при добавлении элемента оказывается, что доля числа элементов, находящихся в структуре данных по отношению к размеру массива, превосходит коэффициент заполнения, то происходит следующее: выделяется новый массив, размер которого превосходит размер старого массива (например в 2 раза), и структура данных перестраивается на новом массиве.
Данный метод разрешения коллизий и применяется в Java, а структура данных называется HashSet.
Метод открытой адресации
В данном методе в ячейках хранятся сами элементы, а в случае коллизии происходит последовательность проб, то есть мы начинаем по некоторому алгоритму перебирать ячейки в надежде найти свободную. Это можно делать разными алгоритмами (линейная / квадратичная последовательности проб, двойное хеширование), каждый из которых обладает своими проблемами (например, возникновение первичных или вторичных кластеров).
От хеш-множества к хеш-таблице (HashMap)
Давайте создадим структуру данных, которая позволяет так же быстро, как и хеш-множество (то есть за O(1)), добавлять, удалять, искать элементы, но уже по некоторому ключу.
Воспользуемся той же структурой данных, что у хеш-множества, но хранить будем не элементы, а пары элементов.
Таким образом, вставка (put(Key key, Value value)) будет осуществляться так: мы посчитаем ячейку массива по объекту типа Key, получим номер bucket’а. Пройдемся по списку в bucket’е, сравнивая ключ с ключом в хранимых парах. Если нашли такой же ключ — просто вытесняем старое значение, если не нашли — добавляем пару.
Как осуществляется получение элемента по ключу? Да по похожему принципу: получаем bucket по ключу, проходимся по парам и возвращаем значение в паре, ключ в которой равен ключу в запросе, если такая пара есть, и null в противном случае.
Данная структура данных и называется хеш-таблицей.
Типичные вопросы на собеседовании
Q: Как устроены HashSet и HashMap? Как осуществляются основные операциии в данных коллекциях? Как применяются методы equals() и hashCode()?
A: Ответы на данные вопросы можно найти выше.
Q: Каков контракт на equals() и hashCode()? Чем он обусловлен?
A: Если объекты равны, то у них должны быть равны hashCode. Таким образом, hashCode должен определяться по подможноству полей, учавствующих в equals. Нарушение данного контракта может приводить к весьма интересным эффектам. Если объекты равны, но hashCode у них разный, то вы можете не достать значение, соответствующее ключу, по которому вы только что добавили объект в HashSet или в HashMap.
Вывод
На собеседованиях очень любят задавать различные кейсы, связанные с этими структурами данных. При этом решение любого из них может быть выведено из понимания принципов их работы без всякой «зубрежки».
На этом все. Если вы дочитали материал до конца, приглашаю на бесплатный урок по теме «Секреты динамического программирования» в рамках урока мой коллега — Евгений Волосатов покажет как решить олимпиадную задачу используя идеи динамического программирования.
- Блог компании OTUS
- Программирование
- Java
- Алгоритмы
- Промышленное программирование