Проблемы хеширования и их решение
Основная проблема хэш-функций – коллизия (от английского collision – столкновение), совпадение сумм у двух символьных строк. Коллизии невозможно избежать, так как при хеширование происходит сжатие символьной строки во много раз. Однако, чем больше символов в исходной строке, например пароле, тем меньше вероятность существования строки с таким же контрольным числом, получаемым после хеширования. Обычно для хранения хэша в различных системах отводится 128, 160 или 256 бит. Один символ в строке в среднем занимает 16 бит, то хэш занимающий 256 бит, может содержать строку длинной до 16 символов. Чем больше размер хэша тем сложнее злоумышленнику подобрать строку с таким же контрольным числом если он смог узнать хэш. На данный момент не существует алгоритма для подбора строки. Подбор проводиться вручную, перебором всех возможных вариантов, этот метод получил название «метод грубой силы» (от английского brute force). Данный метод крайне неэффективен, если исходная строка состояла из 10 символов и включала строчные буквы, символы и цифры, то при скорости 10 млн. паролей в секунду подбор грубой силой займет около 2000 лет.
Для дополнительной надежности хэш-функций к исходным данным добавляются случайные символьные строки, они не являются секретными и хранятся в открытом доступе. Такое добавление символов получило название – Хеширование с солью. Оно усложняет восстановление исходной строки по хэшу, а иногда делает его совсем не возможным.
|
|
|
Вторая наиболее важная проблема хэш-кодов – радужные таблицы. Данные таблицы содержат в себе уже готовые значения хэш-функций, для наиболее распространенных слов и строк символов. Такие таблицы могут содержать тысячи хэшей и значительно упростить взлом информационной системы. Решить эту проблему позволяет «соль», если к строке, которая была занесена в радужную таблицу, добавить соль, то строка не будет найдена. Однако «соль» находится в открытом доступе, символы из которой состоит «соль» может посмотреть любой желающий. Злоумышленнику приходиться изменять таблицу, найдя хэш-сумму «соли» он вставляет ее в таблицу, и тогда нужная сумма может быть найдена. Используя уникальную «соль» для каждого пользователя (например - id) можно исключить вариант добавления хэш-суммы в радужную таблицу. Теперь взломщику придется составлять для каждого хэш-кода отдельную таблицу, учитывая соль этого хэша, что нерационально со стороны злоумышленника.
Алгоритм RSA
Алгоритм RSA Одина из первых криптосистем с открытым ключом, появившаяся в 1997 году и названная в честь ее создателей: Rivest, Shamir, Adleman. Как и в любой системе с открытым ключом для зашифровки информации в данном алгоритме используется односторонняя функция. Для эффективной работы системы необходимо выполнение следующих условий:
|
|
|
1) вычисление значения y=f(x) для любого аргумента x выполняется за реальное время. (понятие реальное время зависит от важности решаемой задачи, мощности используемого процессора и т. п.)
2) нахождение элемента x по известному элементу y так что верно равенство y=f(x) – трудная задача. (трудная задача – задача на решение которой уйдет время за которое зашифрованная информация теряет свою актуальность)
3) существует такой секрет (ключ) с помощью которого получатель зашифрованного сообщения с легкостью находит аргумент x из уравнения f(x)=y.
На первый взгляд условия 2 и 3 противоречат друг другу, так как подходящих функций крайне мало. Функция, отвечающая сразу трем условиям, имеет название односторонней функции с секретом. Например, алгоритма RSA основан на сложности разложения на множители произведения двух больших простых чисел.
Основным преимуществом такой асимметричной криптосистемы является отсутствие необходимости предварительной передачи ключа отправителя с сохранением его секретности.
3.4. Работа и криптостойкость алгоритма RSA:
|
|
|
1) Выбираются два больших простых числа P и Q. Данные числа держатся в секрете.
2) Находится произведение выбранных чисел N=P*Q. N является открытым элементом.
3) Вычисляется функция Эйлера F(N)=(P-1)(Q-1), выбирается такое число E, что НОД (E) и (F(N)) = 1. Значение F(N) секретно.
4) Взаимная простота E и F(N) позволяет вычислить число D, такое, что выполняется равенство E*D=1(mod F(N)).
5) Далее производится шифровка оцифрованного сообщения по формуле y=xE(mod N). x – исходное значение оцифрованного символа, y – зашифрованное значение того же символа.
6) Дешифровка проходит после передачи сообщения по формуле x=yD(mod N). Значение х при правильной передаче данных получается равное исходному.
Команда mod находит остаток от деления А на В.
Выбирая число D как ключ для дешифровки, мы руководствуемся теоремой Лангранжа (французский математик, один из ведущих ученых 19 века), согласно которой для любого x мы имеем равенство xF(N)=1(mod N), создается впечатление, что число D единственный ключ, дешифрирующий все тексты, но это не так. Если элемент x имеет некий порядок g, то есть равенство mg=1(mod N) где g – наименьшее натуральное число с указанным свойством, следовательно расшифровать текст можно путем возведения y в степень f такую, что Ef=1(mod g). При такой операции происходит замена F(N) на g, в таком случае f может оказаться гораздо меньше чем D и подбор такого элемента не займет много времени. Однако при использовании больших исходных чисел, даже подборка элемента f не всегда возможна.
|
|
|
Перейдем к вопросу криптостойкости алгоритма:
Высокая степень надежности данной системы обусловлена тем, что на данный момент нет ни одного эффективного алгоритма позволяющего раскладывать в общем случае произведение на простые множители. Но так же не существует и доказательств невозможности существования такого алгоритма, если алгоритм, удовлетворяющий данным условиям будет найден, то алгоритм RSA моментально потеряет свою секретность, ведь зная исходные числа P и Q для взломщика не составит труда вычислить функцию Эйлера, а затем секретный ключ D.
Таким образом, беря во внимание всю вышесказанную в литературном обзоре информацию, я решила выбрать для практического задания шифр RSA. Так как данный шифр является криптостойким, ассиметричным шифром, который, к тому же, до сих пор применяется некоторыми мессенджерами.
Дата добавления: 2020-04-25; просмотров: 426; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!