PS
Решил поделиться своими заметками по разным тематикам. Сразу предупреждаю, что они могут быть малого объёма и не раскрывать тему полностью (какие-то базовые/начальные вещи). Я писал их для себя, чтобы быстрее въехать в какой-либо материал, либо когда понадобиться - открыть и вспомнить, что и как (короче, использую как шпаргалки).
Настоящая статья описывает некоторые из базовых криптографических шифров + для некоторых расписан способ взлома.
Шифры
Съешь еще этих мягких французских булок, да выпей же чаю - панграмма, в этой фразе весь русский алфавит. (не знаю почему, но она была у меня в заметках, поэтому оставил ее, мб кто-то не знал)
Криптосистемы:
- асимметричные
- симметричные (блочные, потоковые)
блочные: сцепления блоков (CBC), простой замены (ECB)
потоковые: асинхронные, синхронные
Шифр Цезаря
1. Расписываем алфавит (0.а 1.б 2.в и тд)
2. Ключ k = n-1 (для русского алфавита n = 33)
3. Каждой букве открытого текста сопоставляем букву на k порядка больше
- Ищем одно слово и вычитаем поочередно числа начиная с 1, найдя адекватное, расшифровываем весь текст
Шифр простой замены
1. Расписываем алфавит в стандартном порядке
2. Расписываем алфавит в рандомном порядке
3. Каждой букве текста сопоставляем соответствующую букву из второго алфавита
- Атака по маске: анализируем текст, находя маленькие слова или повторяющиеся сочетания букв
- Частотный анализ: находим наиболее используемые буквы и предполагаем, что они соответствуют наиболее используемым буквам в нашем алфавите (о,е,а,и и тд)
Полиалфавитные шифры
1. Расписываем алфавит рандомно в две или более таблицы
2. Например, первую букву шифруем соответствующей ей цифрой из первой таблицы, вторую из второй, потом опять из первой и тд
Шифр Гронсфельда
1. Расписываем алфавит
2. Ключ k - любое число
3. Например k = 134, тогда первая буква увеличивается на 1, вторая на 3, третья на 4, четвертая снова на 1 и тд
Шифр Виженера
1. Составляем квадратную таблицу n*n (по вертикали и горизонтали располагаются буквы алфавита по порядку)
2. Подставляем на рандоме буквы в клетки, по диагонале буквы одинаковые
3. Получаем картину
а б в
а п г ж
б г ж
в ж
4. Когда дойдем до "я", то начинаем диагонали заполнять с первой буквы (в нашем случаи это "п", потом "г")
5. Ключ - слово или сочетание букв
6. Например k = шина, текст - текст, первая буква зашифрованного текста будет на пересечении букв "ш" и "т", вторая "и" и "е" и тд
- Индекс совпадений = 0,0553
Необходимо определить длину ключа, начинаем с двух (далее будем увеличивать на один), выписываем каждую вторую букву начиная с первой. Считаем количество букв l в общем и количество появлений каждой буквы n в отдельности. Далее считаем ИС для каждой буквы, он равен n(n-1)/l(l-1). Складываем все значения и сравниваем с константой. Если сумма ~ или > константы, то ключ данной длинны.
Например мы получили, что k = 4, тогда формируем 4 группы букв (каждую 4 букву начиная с первой, каждую 4 букву начиная со второй и тд), по методу частотного анализа, находим самую популярную букву (в реальном алфавите это буква "о"), следовательно как в шифре Цезаря находим наш ключ для каждой группы (самая популярная "щ", тогда "щ"-"о"=ключ к данной группе), дешифруем и возвращаем буквы на место.
- Автокорреляционный метод
Выписываем весь текст в одну линию и под ней пишем текст еще раз. Во второй строчке переносим первые 2 буквы в конец (2 - предполагаемая длина ключа, далее будет 3,4,5 и тд). Ищем количество совпадающих букв n первой строки со второй. Y = n\l - похож на индекс совпадений, поэтому далее действуем по предыдущему методу
Шифр RSA
Ассиметричная криптосистема
Есть две стороны Alice и Max + хакер Eva
1. Alice придумывает два простых приблизительно равных числа p = 29 и q = 31, n = pq = 899, f(n) = (p-1)(q-1) = 840 - функция Эйлера, e = 11 - открытая экспонента, необходимо подобрать так, чтобы оно было нечетным натуральным числом не имеющим общий делителей с f(n)
2. {n,e} - открытый ключ
3. d = (k*f(n)+1)/e = 611 при k = 8 - должно быть целым (k - подбирается)
4. {n,d} - закрытый ключ
5. У Max есть {899,11} и некое сообщение для Alice m = 60
6. зашифрованное сообщение c = m^e mod n = 308
7. Alice получает c = 308 и находит m = c^d mod n = 60
Протокол Диффи-Хеллмана
Путем выполнения данного алгоритма Alice и Max владеют ключом шифрования через открытые каналы (то есть Eva видит все, что они пересылают)
1. Alice генерирует p - случайное простое число и подбирает g, чтобы оно удовлетворяло g^(p-1) mod p = 1 (например p = 17 и g = 3)
2. Max получил {p,g}, придумал случайное натурально число b = 31 и рассчитал открытый ключ B = g^b mod p = 6
3. Alice также придумывает случайное натурально число a = 23 и рассчитывает открытый ключ A = g^a mod p = 11
4. Они обмениваются A и B
5. Далее рассчитывают K = B^a mod p = 14 или K = A^b mod p = 14
6. Тем временем Eva владеет только двумя парами чисел p,g и A,B, и никак не может рассчитать секретный ключ
- Человек по середине: Eva перехватывает {p;g} вместо A и B отправляет в обе стороны свое полученное число C, тем самым в итоге имея два ключа (один с Alice, другой с Max)
Хеш-функция
Алгоритм, который приводит любое сообщение к новому определенной заранее длины.
Используется для подтверждения пароля: сервер отправляет клиенту некую строку (например номер клиента в списке на основании логина), далее считается хеш функция от (пароль+строка), отправляется серверу и он сравнивает с такой же хеш функцией
MAC (Эм Эй Си)
Проверка целостности сообщений
1. Max и Alice договариваются о секретном ключе заранее
2. Alice в конце сообщения добавляет ключ и хеширует
3. Alice печатает сообщение и добавляет в конце хеш
4. Max получает сообщение добавляет к основной части сообщения ключ
5. Сравнивает хеши
Блочные шифры
Разбиваем весь текст на блоки фиксированной длины и работаем с каждым блоком как с отдельным текстом, шифруя его ключом.
Если длина последнего блока не совпадает с фиксированной длиной, необходимо дополнить его некоторыми символами.
ECB - в режиме простой замены блок никак не влияет на шифрование последующего
CBC - в режиме сцепления блоков - каждый блок шифруется ключом + задействуется предыдущий зашифрованный блок, то есть при изменение лишь одной буквы, поменяется весь последующий зашифрованный текст (лавинный эффект). Зашифрованный блок, который влияет на шифрование последующего называется - вектором инициализации. Для первого блока вектором инициализации является заранее заданный код (также как и ключ задаются заранее)
Потоковые шифры
1. Исходный текст переводится в биты (например 800 бит)
2. Ключ переводится в биты подается на ГПСЧ
3. Снимаем с ГПСЧ 800 бит
4. XOR
Шифр Тритемиуса
1. Расписываем алфавит
2. Расписываем порядок символов в сообщение (начиная с 0)
3. С = (m + s(p)) mod N, где m - порядок в алфавите, p - порядок в сообщении, s - любая функция от зависящая от p, N - количество символов в алфавите
4. s() - ключ-функция, которая должна возвращать только целые натуральные числа, например s(p) = 2p + 15
5. Обратный расчет m = (C - s(p)) mod N
Электронная подпись
Подтверждает личность автора и целостность сообщения
в RSA:
Alice закрытым ключом подписывает сообщение s = m^d mod n
Max получает сообщение m и подпись s, открытым ключом расшифровывать подпись p = s^e mod n и удостоверяется, что m = p
Шифр Вернама
1. Составляем таблицу алфавита, где каждому символу рандомно выбираем двоичное число (а - 011001, б - 100001 и тд)
2. Длина ключа = длине сообщения, ключ - случайный набор символов, после применения уничтожается
3. складываем сообщение и ключ по модулю 2
4. расшифровка: закрытый текст + ключ по модулю 2