Если Вы чувствуете, что, все чаще в окружающем Вас контенте, мелькают слова “безопасность данных”, “конфиденциальность”, “шифрование”, если Вы в курсе ситуации со Сноуденом или заявлениями британских премьер-министров о запрете прозрачного шифрования, то можете читать ниже.
Если что-либо будет вызывать вопросы, в эпоху присутствия интернета можно обращаться в google, wikipedia, etc. Или написать в комменты, личку, на гитхаб, на почту. Для дальнейшего осознания нужны базовые представления о computer science.
Эту статью можно считать средством систематизации, складирования знаний и борьбы с прокрастинацией.
Если вы программируете уже н-лет, месяцев дней, то должны понимать, что ОЗУ, ПЗУ вычеслительного устройства хранит данные только в сериализированном виде, т.е. плюньте в лицо человеку, который говорит, что если нельзя сериализировать данные, но можно с ними работать (всегда можно абстрагировать и сериализировать). Данные это всего лишь набор нулей и единиц, которые составляют октеты (байты далее), из 8-ми бит. Т.е. бит имеет два состояния 1, и 0. А байт, 256 состояний от 00000000 до 11111111. Это все к тому, что криптография, в традиционном еe понимании работает только с целыми числами, в более узком понятии только с элементами поля Галуа. Забудьте про дроби, т.к. float – тоже сериализируется в порядок бит, а в криптографии важен только он.
Для шифрования данных используется много наборов из обратимых операций, над двумя переменными, одной из которых является сообщение, а второй ключ шифрования. Обычно это элементы поля Галуа(2^x), где x — некоторая степень.
Рассмотрим список элементарных криптографических операций:
1) Самый популярный операция простого шифрования – XOR, (Exclusive disjunction or exclusive or).
Он же “сложение по модулю два”. Обратная оперция – сам себе обратная операция, т.е. XOR(XOR(x,a),a) = x.
Таблица возможных значений доступна, в wiki.
Самый простой шифр образован применением операции xor ко всем битам сообщения битами ключа циклически, т.е. как только закончился ключ начинаем сначала ключа.
Пример данных, в кодировке ASCII: message — “Hello world!”, key — “Key”,
Hex Plain text - 48 65 6C 6C 6F 20 77 6F 72 6C 64 21 00 Key - 4B 65 79 Chiper text - 03 00 15 27 0A 59 3C 0A 0B 27 01 58 4B Bin Plain text - 00000000 00100001 01100100 01101100 01110010 01101111 01110111 00100000 01101111 01101100 01101100 01100101 01001000 key - 01111001 01100101 01001011 Chiper text - 01001011 01011000 00000001 00100111 00001011 00001010 00111100 01011001 00001010 00100111 00010101 00000000 00000011 На схемах обычно отображается в виде знака “плюса” в круге.
Недостатки – если ключ малой длинны – возможен брутфорс, частотный анализ, если достаточно большой и достаточно случайный – образует идеальный шифр одноразовых блокнотов, с доказанной неустойчивостью к взлому.
2) Сложение по модулю 2^8, ^16, ^32, ^64 – элементарное сложение в поле Галуа.
Обратная операция – отнимание по соответствующему модулю, или сложение с обратным числом (что собственно одно и то же).
Таблица возможных значений зависит от разрядности поля.
Пример, data = 24, key = 11, mod – 2^8, тогда 24 + 11 = 35; data = 255, key = 1, mod – 2^8, тогда 255 + 1 = 0; - так называемое “переполнение ячейки памяти” data = 65535, key = 140, mod – 2^32, тогда 65535 + 140 = 65675; Обратные операции:
a)сложение с обратным элементом 35 + (255 – 11 + 1) = 24, где 255 – 11 + 1 – обратный элемент, т.е. ~key + 1, где ~ - побитовое отрицание. 65675 + (4294967295 – 140 + 1) = 65535 б) отнимание по соответствующему модулю 35 – 11 = 24; 65675 – 140 = 65535. На схемах обычно отображается в виде знака “плюса” в квадрате, легенда схемы уточняет модульность сложения. Слабые и сильные стороны аналогично предыдущему варианту.
3) Циклические битовые сдвиги (вращение по модулю)
Вращение бит на n, влево или вправо. Обратная операция – вращение в другую сторону на тоже число бит, или “докручивание” на обратное количество бит.
По модулю 2^64 1481245 << 25 = 49702334627840 исходное : 00000000 00000000 00000000 00000000 00000000 00010110 10011010 00011101 полученное: 00000000 00000000 00101101 00110100 00111010 00000000 00000000 00000000 1481245 >> 25 = 814323050542530560 исходное : 00000000 00000000 00000000 00000000 00000000 00010110 10011010 00011101 полученное: 00001011 01001101 00001110 10000000 00000000 00000000 00000000 00000000 Обратное количество бит в “докручивании” зависит от разрядности ячейки (или степени двойки в поле Галуа), т.е.
64 – 25 = 39, 1481245 << 25 = 49702334627840 49702334627840 << 39 = 1481245. На схемах обычно отображается в виде знака “>>” повернутых в одну или другую сторону с указанием на сколько разрядов нужно повернуть. Ну еще следует понимать x << 64 – бессмысленная операция в GF(2^64).
4) Перестановки бит (байтов, машинных слов, и т.д.)
Пример перестановка второго бита на место четвертого, четвертого на место третьего третьего на место второго.
1101 = 0101 (little endian)
Могут быть различных вариаций, фантазия не ограничивает.
Обратная операция – обратная перестановка.
5) Подстановка (обычной от тетрад, октетов и выше).
Обычно используются таблицы, в которых все возможные элементы переходят в другие элементы (без потерь).
static const uint8_t purgeSubstitutionBlock[256] = { 0x68, 0x59, 0xB5, 0x76, 0x0F, 0x94, 0x80, 0x1F, 0x63, 0xE8, 0x21, 0x33, 0x74, 0x41, 0x55, 0x16, 0x4D, 0x88, 0x72, 0x50, 0xCE, 0x69, 0xD2, 0x22, 0xF0, 0x6F, 0xDC, 0x56, 0xD8, 0x90, 0x17, 0x2E, 0x54, 0x7C, 0xF1, 0x89, 0x6A, 0xDF, 0xDD, 0xD4, 0xBC, 0xE6, 0x91, 0x29, 0xAE, 0x1A, 0x08, 0x77, 0x49, 0x19, 0x67, 0x1C, 0xAA, 0xB1, 0x10, 0xF2, 0x34, 0x5B, 0xED, 0x31, 0x35, 0x3C, 0xAF, 0x3D, 0x7E, 0x18, 0xA0, 0xE5, 0xCD, 0xF7, 0x1D, 0x02, 0xCC, 0x8B, 0x36, 0xEC, 0xB6, 0x43, 0x44, 0xA8, 0x00, 0x0A, 0x4E, 0xFE, 0x0D, 0x66, 0x4B, 0x9F, 0x23, 0xC4, 0xC6, 0x15, 0x53, 0xD1, 0x32, 0xBD, 0xA3, 0x60, 0x95, 0x1E, 0x85, 0x45, 0xD3, 0xFD, 0x12, 0xA9, 0xE4, 0x8A, 0xB0, 0x73, 0x83, 0x11, 0x2A, 0xBB, 0x9A, 0x07, 0x8E, 0x6E, 0x8C, 0xC5, 0x37, 0xC0, 0xE9, 0x92, 0xC1, 0xFF, 0xE3, 0xF3, 0xCB, 0xAB, 0x7F, 0xC8, 0x24, 0x58, 0x6D, 0xBA, 0x7B, 0x79, 0xC2, 0x86, 0xEF, 0x06, 0xCF, 0x4A, 0x81, 0xA7, 0x40, 0xE7, 0x9B, 0x48, 0x71, 0xDA, 0x3F, 0xE2, 0xAD, 0x84, 0x47, 0xCA, 0xB8, 0x2D, 0x87, 0x1B, 0x97, 0x05, 0x13, 0x0C, 0xA4, 0xD6, 0xC9, 0xA2, 0x52, 0x99, 0x6C, 0x3E, 0x26, 0xD5, 0x42, 0x61, 0x14, 0xF9, 0x38, 0x5D, 0x4F, 0x01, 0xB4, 0xE0, 0xC3, 0x03, 0x5A, 0xAC, 0x93, 0xB9, 0xFA, 0x98, 0xEE, 0xEB, 0x0E, 0xBF, 0x2B, 0x0B, 0xA6, 0xD7, 0x46, 0xBE, 0x2F, 0xEA, 0x3B, 0x7D, 0xDE, 0x82, 0xD9, 0x62, 0x25, 0x3A, 0x78, 0x96, 0x65, 0x9E, 0x8D, 0x8F, 0xFC, 0x39, 0xB7, 0x4C, 0x7A, 0xA1, 0x27, 0x04, 0xD0, 0x57, 0x30, 0x51, 0xF5, 0xB3, 0xFB, 0xA5, 0x75, 0x20, 0xE1, 0x6B, 0xF4, 0xDB, 0xF8, 0x5C, 0x28, 0x64, 0xC7, 0x2C, 0x09, 0xB2, 0x9C, 0x9D, 0x5F, 0x70, 0x5E, 0xF6, }; static const uint8_t purgeReverseSubstitutionBlock[256] = { 0x50, 0xB7, 0x47, 0xBB, 0xE3, 0xA3, 0x8D, 0x73, 0x2E, 0xF8, 0x51, 0xC7, 0xA5, 0x54, 0xC4, 0x04, 0x36, 0x6F, 0x68, 0xA4, 0xB2, 0x5B, 0x0F, 0x1E, 0x41, 0x31, 0x2D, 0xA1, 0x33, 0x46, 0x63, 0x07, 0xED, 0x0A, 0x17, 0x58, 0x84, 0xD4, 0xAE, 0xE2, 0xF4, 0x2B, 0x70, 0xC6, 0xF7, 0x9F, 0x1F, 0xCC, 0xE6, 0x3B, 0x5E, 0x0B, 0x38, 0x3C, 0x4A, 0x78, 0xB4, 0xDD, 0xD5, 0xCE, 0x3D, 0x3F, 0xAD, 0x98, 0x92, 0x0D, 0xB0, 0x4D, 0x4E, 0x65, 0xCA, 0x9C, 0x95, 0x30, 0x8F, 0x56, 0xDF, 0x10, 0x52, 0xB6, 0x13, 0xE7, 0xAA, 0x5C, 0x20, 0x0E, 0x1B, 0xE5, 0x85, 0x01, 0xBC, 0x39, 0xF3, 0xB5, 0xFE, 0xFC, 0x61, 0xB1, 0xD3, 0x08, 0xF5, 0xD8, 0x55, 0x32, 0x00, 0x15, 0x24, 0xEF, 0xAC, 0x86, 0x75, 0x19, 0xFD, 0x96, 0x12, 0x6D, 0x0C, 0xEC, 0x03, 0x2F, 0xD6, 0x89, 0xE0, 0x88, 0x21, 0xCF, 0x40, 0x82, 0x06, 0x90, 0xD1, 0x6E, 0x9B, 0x64, 0x8B, 0xA0, 0x11, 0x23, 0x6B, 0x49, 0x76, 0xDA, 0x74, 0xDB, 0x1D, 0x2A, 0x7B, 0xBE, 0x05, 0x62, 0xD7, 0xA2, 0xC1, 0xAB, 0x72, 0x94, 0xFA, 0xFB, 0xD9, 0x57, 0x42, 0xE1, 0xA9, 0x60, 0xA6, 0xEB, 0xC8, 0x91, 0x4F, 0x69, 0x34, 0x81, 0xBD, 0x9A, 0x2C, 0x3E, 0x6C, 0x35, 0xF9, 0xE9, 0xB8, 0x02, 0x4C, 0xDE, 0x9E, 0xBF, 0x87, 0x71, 0x28, 0x5F, 0xCB, 0xC5, 0x79, 0x7C, 0x8A, 0xBA, 0x59, 0x77, 0x5A, 0xF6, 0x83, 0xA8, 0x9D, 0x80, 0x48, 0x44, 0x14, 0x8E, 0xE4, 0x5D, 0x16, 0x66, 0x27, 0xAF, 0xA7, 0xC9, 0x1C, 0xD2, 0x97, 0xF1, 0x1A, 0x26, 0xD0, 0x25, 0xB9, 0xEE, 0x99, 0x7E, 0x6A, 0x43, 0x29, 0x93, 0x09, 0x7A, 0xCD, 0xC3, 0x4B, 0x3A, 0xC2, 0x8C, 0x18, 0x22, 0x37, 0x7F, 0xF0, 0xE8, 0xFF, 0x45, 0xF2, 0xB3, 0xC0, 0xEA, 0xDC, 0x67, 0x53, 0x7D, };
т.е. вместо 0 всегда будет подставлятся 0x68, вместо 0x1 – 0x59 и т.д. соответственно. Для обратного преобразования нужно, чтобы на месте 0x68 – 104 стоял 0, а на месте 0x59 – 89 стояла единица. Для обратной подстановки используется, внезапно, таблица обратной подстановки:
т.е. reverseKeyTable[keyTable[x]] = x.
6) Для построения более-менее стойкого шифра
Из этой комбинации элементов используются обычно два паттерна – сеть Фейстеля, и подстановочно-перестановочная сеть. Обычно их все равно смешивают, т.е. подстановки-перестановки-генерация ключа-гаммирование. Исторически сложилось, что гаммированием – называют xor с ключем. А еще иногда добавляют xor-add-константы, которые немного увеличивают энтропию входных данных.
Такой подход используется для того, чтобы получить наиболее равномерный выход шифра, при очень низком качестве входных данных, т.к. обычно входные данные не являются достаточно случайными (достаточно случайными данными можно считать белый шум). А большое количество раундов повторения – для устойчивости к прямому подбору.
Комбинация простых операций может быть разнообразна. Вот например, 512-битный криптоалгоритм, построенный на элементарных операциях описанных выше. Количество раундов — 31.
Исходные коды и реализация.
Примеры данных:
Data: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 Key: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 Ciphered: B8 FF E8 11 EB 46 0F FE 12 AE 7F 34 E7 7A 03 49 18 B8 F8 AA EA F4 D6 3D 1F A8 98 35 35 C7 5C 42 91 42 7E 4C CF EA E4 30 56 6E 4B 28 19 4D D0 FA 72 55 FE DB 48 D5 79 FA 5A 1D 9B 47 10 9D E1 7E Data: 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 Key: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 Ciphered 2: 15 AA B4 16 EE 34 33 A1 E2 BA 5C C6 C8 52 98 D3 17 66 EB 16 00 B1 32 26 34 14 18 30 15 48 C9 71 A6 03 F0 1E 19 2A AF 6C 71 14 30 19 8E EB 8A 29 2E C8 99 DD 47 62 13 3C F9 7E D1 08 C9 4F E2 D3 Можно увидеть, как при изменении одного бита полностью меняется шифр-текст.
ссылка на оригинал статьи http://habrahabr.ru/post/260321/
Добавить комментарий