21. Системы шифрования с открытым ключом rsa

RSA (аббревиатура от фамилий Rivest, Shamir и Adleman) — криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел.

Криптосистема RSA стала первой системой, пригодной и для шифрования, и для цифровой подписи. Алгоритм используется в большом числе криптографических приложений, включая PGP, S/MIME, TLS/SSL, IPSEC/IKE и других/

Криптографические системы с открытым ключом используют так называемые односторонние функции, которые обладают следующим свойством:

Если известно , то вычислить относительно просто

Если известно , то для вычисления нет простого (эффективного) пути.

Под односторонностью понимается не теоретическая однонаправленность, а практическая невозможность вычислить обратное значение, используя современные вычислительные средства, за обозримый интервал времени.

В основу криптографической системы с открытым ключом RSA положена сложность задачи факторизации произведения двух больших простых чисел. Для шифрования используется операция возведения в степень по модулю большого числа. Для дешифрования за разумное время (обратной операции) необходимо уметь вычислять функцию Эйлера от данного большого числа, для чего необходимо знать разложения числа на простые множители.

Наиболее используемым в настоящее время является смешанный алгоритм шифрования, в котором сначала шифруется сеансовый ключ, а потом уже с его помощью участники шифруют свои сообщения симметричными системами. После завершения сеанса сеансовый ключ как правило уничтожается.

Система RSA может использоваться не только для шифрования, но и для цифровой подписи.

истема RSA используется для защиты программного обеспечения и в схемах цифровой подписи.

Также она используется в открытой системе шифрования PGP и иных системах шифрования (к примеру, DarkCryptTC и формат xdc) в сочетании с симметричными алгоритмами.

Из-за низкой скорости шифрования (около 30 кбит/с при 512 битном ключе на процессоре 2 ГГц), сообщения обычно шифруют с помощью более производительных симметричных алгоритмов со случайным ключом (сеансовый ключ), а с помощью RSA шифруют лишь этот ключ, таким образом реализуется гибридная криптосистема. Такой механизм имеет потенциальные уязвимости ввиду необходимости использовать криптостойкий генератор случайных чисел для формирования случайного сеансового ключа симметричного шифрования и эффективно противостоящий атакам симметричный криптоалгоритм (в данное время широкое применение находят AES, IDEA, Serpent, Twofish).

22. Алгоритм кодирования. Примеры кодов.

Один из самых простых методов кодирования — ROT 13. Он заключается в том, что каждой букве присваивается число, например А—1, В—2 и т.д. Если вы пишете HELLO, то присваиваете число каждой букве, затем к каждому из них прибавляете 13, после чего полученные числа снова заменяются буквами. Если это число больше 26, то из него следует вычесть 26, чтобы не превысить количество букв в алфавите (в латинском.— Прим. ред.). Слово HELLO состоит из чисел 8, 5, 12, 12, 15. Теперь прибавляем к каждому числу 13 и получаем 21, 18, 25, 25, 28. 28 больше 26, значит, необходимо вычесть 26 из 28; в конечном виде последовательность чисел будет выглядеть так: 21, 18, 25, 25, 2. Превращаем ее снова в буквы и получаем слово URYYB, которое ничем не напоминает исходное HELLO. Это пример очень простого алгоритма кодирования. Его вполне достаточно, если вы опасаетесь, что в процессе передачи ваше письмо будут просматривать для обнаружения ключевых слов. В письме, зашифрованном таким образом, никакие ключевые слова найти невозможно. Но это не гарантия полной безопасности: если конкуренты включат в программу сканирования простенький алгоритм декодирования, ваши усилия будут мгновенно сведены на нет.

В некоторых странах, например во Франции, шифрование разрешается использовать только в том случае, если копия ключей, применяемых для шифрования, своевременно передана в соответствующие государственные организации. Эта система, которая называется депонированием ключей, позволяет полиции и иным государственным учреждениям расшифровывать закодированные послания. Может быть, идея и неплоха, только на практике она не работает. Пользователи и бизнесмены не доверяют методам шифрования, если знают, что закодированные с их помощью сообщения могут прочитать государственные служащие. К тому же есть основания опасаться, что при такой системе ключами кодирования могут воспользоваться террористы и преступники.

В большинстве стран мира запрещено хранить оружие, однако преступники все равно им пользуются. Объявление шифрования незаконным еще хуже. Деловые операции, осуществляемые в Internet, могут стать всем известными, и этой информацией не преминут воспользоваться конкуренты, чтобы расправиться с вашей компанией. К тому же, даже если во всем мире кодирование будет запрещено законом, преступники все равно будут его применять, поскольку они уже нарушают закон и им плевать, что говорят политики или полицейские.

Идея арифметического кодирования

Стандартный метод сжатия файлов. Хорош для любой информации. Двухпроходной. Лучше Хаффмана, но в чистом виде не используется.

Метод LZW-сжатия данных

LZW-сжатие выделяется среди прочих, когда встречается с потоком данных, содержащим повторяющиеся строки любой структуры ( текст, сжатие видеоформ и копий экранов). Сжатие однопроходное и может быть осуществлено 'на лету'.

Использование алгоритма расширяющегося префикса для кодирования и схожих пpоцессов

Статья дает описание арифметического кодирования с применением 'splay trees' - расширяющихся деревьев. C исходниками..

Сжатие по алгоритму Хаффмана

Старый, добрый двухпроходной Хаффман. Классика кодирования. Исходник прилагается.

RLE (Групповое кодирование)

Старейший двухпроходной алгоритм сжатия информации. Применяется только как дополнение к другим методам. Легок для освоения и реализации.

UUE-кодирование

Основные алгоритмы UUE-кодирования. Описание используемого при UUE CRC-алгоритма. Исходник прилагается.

Huffman - Сначала кажется что создание файла меньших размеров из исходного без кодировки последовательностей или исключения повтора байтов будет невозможной задачей. Но давайте мы заставим себя сделать несколько умственных усилий и понять алгоритм Хаффмана ( Huffman ). Потеряв не так много времени мы приобретем знания и дополнительное место на дисках.

Сжимая файл по алгоритму Хаффмана первое что мы должны сделать - это необходимо прочитать файл полностью и подсчитать сколько раз встречается каждый символ из расширенного набора ASCII. Если мы будем учитывать все 256 символов, то для нас не будет разницы в сжатии текстового и EXE файла.

После подсчета частоты вхождения каждого символа, необходимо просмотреть таблицу кодов ASCII и сформировать мнимую компоновку между кодами по убыванию. То есть не меняя местонахождение каждого символа из таблицы в памяти отсортировать таблицу ссылок на них по убыванию. Каждую ссылку из последней таблицы назовем "узлом". В дальнейшем ( в дереве ) мы будем позже размещать указатели которые будут указывает на этот "узел". Для ясности давайте рассмотрим пример:

Мы имеем файл длинной в 100 байт и имеющий 6 различных символов в себе. Мы подсчитали вхождение каждого из символов в файл и получили следующее :

|-----------------|-----|-----|-----|-----|-----|-----|

| cимвол | A | B | C | D | E | F |

|-----------------|-----|-----|-----|-----|-----|-----|

| число вхождений | 10 | 20 | 30 | 5 | 25 | 10 |

|-----------------|-----|-----|-----|-----|-----|-----|

Теперь мы берем эти числа и будем называть их частотой вхождения для каждого символа. Разместим таблицу как ниже.

|-----------------|-----|-----|-----|-----|-----|-----|

| cимвол | C | E | B | F | A | D |

|-----------------|-----|-----|-----|-----|-----|-----|

| число вхождений | 30 | 25 | 20 | 10 | 10 | 5 |

|-----------------|-----|-----|-----|-----|-----|-----|