|
Реферат: Криптография
Реферат: Криптография
Содержание
Введение. 3
1.. Простые шифры.. 4
1.1. Шифр Цезаря. 4
1.2. Простой подстановочный шифр. 5
2.. Шифрование с секретным ключом.. 8
2.1. Стандарт Data Encryption Stantart (DES). 8
2.2. Методы шифрования. 8
2.3. Алгоритм DESede. 9
2.4. Алгоритм Blowfish. 10
3.. Шифрование с открытым ключом.. 11
3.1. Алгоритм Ривеста-Шамира-Эдлемана. 11
3.2. Алгоритм AlGamal 12
6. Дайджесты сообщений. 13
7. Цифровые подписи и цифровые сертификаты.. 14
Заключение. 16
Список использованной литературы.. 17
Криптография (что в переводе с греческого означает “тайнопись”) издавна
использовалась при обмене самой разнообразной информацией. Самые ранние
упоминания об использовании криптографии: Египет – 1900 г. до н.э.,
Месопотамия – 1500 г. до н.э., при написании Библии – 500 г. до н.э.
Одним из наиболее известных в древней истории деятелей, постоянно пользовавшийся
тайнописью, был Юлий Цезарь. Он придумал шифр, носящий название шифр
Цезаря (Caesar cipher).
Тайнописью пользовались на протяжении средних веков в Европе, на Ближнем
Востоке и в Северной Америке.
Во время гражданской войны в США тайнопись использовалась и северянами и
южанами. С тех пор она использовалась в каждой значительной войне.
Во время Второй мировой войны польские и британские дешифровальщики раскрыли
секрет немецкой шифровальной машины Энигма. В результате было уничтожено
множество немецких подводных лодок, потоплен линкор Бисмарк, и вооруженные
силы Германии понесли тяжелые потери в ряде операций.
Теперь, к началу XXI века, вследствие огромной популярности Web и
использование ее в электронной коммерции, технология шифрования и
сопутствующие ей алгоритмы шифрования стали доступны массовому потребителю. В
сетевом бизнесе для защиты безопасности финансовых сделок, сетевых услуг и
потребительской информации основной упор делается на цифровые сертификаты и
технологии шифрования как с открытым так и с секретным ключами.
Значение криптографии сегодня на самых различных уровнях обмена информации
трудно переоценить. В своем реферате я постараюсь описать несколько простых
алгоритмов шифрования, дать математическую основу нескольких сложных
алгоритмов, а также описать такие понятия, как дайджест сообщения, цифровая
подпись и сертификат.
Простые шифры
В этой главе приводился два простых метода шифрования: уже упоминавшийся шифр
Цезаря и подстановочный шифр.
Шифрование представляет собой процесс превращения открытого текста в
зашифрованный, а расшифровка – процесс обратного преобразования, при котором
восстанавливается исходный текст. Управление шифрованием и расшифровкой часто
осуществляется с использованием ключей, которые расширяют многообразие путей
превращения открытого текста в зашифрованный (и обратно).
Шифр Цезаря основан на фиксированном смещении по кругу букв алфавита. Буквы
сдвигаются по кругу, так что после последней буквы алфавита идет его первая
буква. В следующем листинге (на языке java) приводится алгоритм шифрования на
основе шифра Цезаря.
Листинг 1. класс CaesarCipher
package ru.festu.u031.asanov.security.ref1;
public class CaesarCipher {
/** Зашифровать строку */
public static String encrypt(String s, int key) {
String result = "";
for(int i = 0; i < s.length(); i++) {
// зашифровать каждый символ в строке
result += encrypt(s.charAt(i), key);
}
return result;
}
/** Зашифровать отдельный символ */
public static char encrypt(char c, int key) {
// преобразовать строчные буквы в прописные
if(c >= 'а' && c <= 'я') c = Character.toUpperCase(c);
// "повертуть" букву
if(c >= 'А' && c <= 'Я') c = rotate(c, key);
return c;
}
/** Расшифровать строку */
public static String decrypt(String s, int key) {
// выполнить шифрование с "обратным" ключем
return encrypt(s, -key);
}
/** Расшифровать отдельный символ */
public static char decrypt(char c, int key) c > 'Я') return c;
/** "Поворот" символа */
private static char rotate(char c, int key) {
int l = 'Я' - 'А';
c += key % l;
if(c < 'А') c += l;
if(c > 'Я') c -= l;
return c;
}
}
При шифровании с ключом алгоритмы шифрования и расшифровки могут быть хорошо
известны. Но дешифровальный и (иногда) шифровальный ключи строго секретны.
Зашифрованный текст, полученный в результате шифрования открытого текста с
помощью конкретного шифровального ключа, может быть расшифрован только с
помощью дешифровального ключа, связанного с шифровальным ключом.
В шифре Цезаря ключи представляют собой число символов, на которое сдвигаются
буквы алфавита. При шифровании вместо каждой буквы открытого текста ставится
буква отстоящая от нее вправо на число букв задаваемое значением
ключа. Расшифровка заключается в смещении каждой буквы влево на число
букв, задаваемое тем же значением ключа, которое использовалось при шифровании.
(То есть decryptKey = -encrypKey)
Не нужно быть опытным дешифровальщиком, чтобы понять, что Шифр Цезаря
обладает низкой стойкостью. В нем (в случае русского алфавита) возможны всего
32 различных кличей, один из которых отображает открытый текст в тот же
открытый текст.
Это дает представление о размере пространства ключей. Пространство ключей шифра
– это набор всех возможных ключей, которые работаю с этим шифром. Чтобы шифр
был эффективным, пространство ключей должно быть большим. Размер пространства
ключей обычно измеряется числом двоичных разрядов ключа. В n-битном
пространстве ключей возможны 2n разных ключа. Для 32-х-битного ключа
это число составляет 4 294 967 296 разных ключей. Хотя такое число может
показаться большим, на самом деле оно достаточно мало. Средней мощности
компьютер может за день “перепробовать” 4 миллиарда ключей.
Еще одним видом простого шифра являются подстановочные шифры. Они были одними
из наиболее популярных шифров со Средних веков до 19-го столетия. В простых
подстановочных шифрах вместо одной буквы алфавита подставляется другая. В
более сложных подстановочных шифрах вместо одной группы букв подставляется
другая.
Даже простые подстановочные шифры сложнее шифра Цезаря. Если вы сможете
расшифровать одну букву в шифре Цезаря, то после этого расшифруете любую
букву в нем. Но в случае с простым подстановочным шифром так не происходит.
Ключом к простому подстановочному шифру является таблица соответствия буквам
открытого текста букв зашифрованного текста. Этот ключ может быть представлен
в виде 32-х-буквенной строки. Например: НАФЧЫРИЦЛЙЯДМЗСЪЖЩТПОКЭЬГЮЕУШВБХ
Число ключей для простого подстановочного шифра составляет 32!, а это больше чем
2,6*1035.
Алгоритм шифрования с использованием подстановочного шифра представлен в
следующем листинге.
Листинг 2. класс SubstitutionCipher
package ru.festu.u031.asanov.security.ref1;
public class SubstitutionCipher {
/** Зашифровать строку */
public static String encrypt(String s, String key) {
String r = "";
for(int i = 0; i < s.length(); i++) {
r += encrypt(s.charAt(i), key);
}
return r;
}
/** Зашифровать отдельный символ */
public static char encrypt(char c, String key) {
// преобразовать строчные символы в заглвные
if(c >= 'а' && c <= 'я') c = Character.toUpperCase(c);
if(c >= 'А' && c <= 'Я') return key.charAt(c-'А');
else return c;
}
/** Расшифровать строку */
public static String decrypt(String s, String key) {
String r = "";
for(int i = 0; i < s.length(); i++) {
r += decrypt(s.charAt(i), key);
}
return r;
}
/** Расшифровать отдельный символ */
public static char decrypt(char c, String key) {
if(c >= 'А' && c <= 'Я') return (char)(key.indexOf(c)+'А');
else return c;
}
/** Создать ключ */
public static String createKey() {
int length = 'Я'-'А'+1;
char[] alphabet = new char[length];
for(int i = 0; i < alphabet.length; i++) alphabet[i] += i+'А';
for(int i = 0; i < alphabet.length; i++) {
int n1 = i; //(int)(Math.random()*length);
int n2 = (int)(Math.random()*length);
char c = alphabet[n1];
alphabet[n1] = alphabet[n2];
alphabet[n2] = c;
}
return new String(alphabet);
}
}
На первый взгляд может показаться, что простой подстановочный шифр обладает
высокой стойкостью, особенно потому, что у него огромное пространство ключей.
Однако, он легко раскрывается методом, в котором применяются буквенные
шаблоны, присущие конкретному языку.
В русском языке буквы О и Е встречаются значительно чаще других букв, таких,
например, как Ъ и Ф. В таблице 1 приведены относительные частоты
использования букв от А до Я, т.е. Ожидаемые числа использования этих букв в
последовательности из 100 букв осмысленного текста. Это не означает, что
среди 100 букв любого текста на русском языке буква В встретится всегда ровно
2 раза, а Ъ вообще не встретится. Но в среднем это действительно так.
Таблица 1. относительные частоты букв.
| А | 5,7 | И | 4,8 | Р | 2,9 | Ш | 0,5 | | Б | 1,3 | Й | 0,7 | С | 3,7 | Щ | 0,3 | | В | 3,0 | К | 2,1 | Т | 4,4 | Ъ | 0,0 | | Г | 1,3 | Л | 3,4 | У | 1,9 | Ы | 1,4 | | Д | 2,2 | М | 2,2 | Ф | 0,1 | Ь | 1,3 | | Е | 5,8 | Н | 4,7 | Х | 0,6 | Э | 0,3 | | Ж | 0,8 | О | 7,8 | Ц | 0,2 | Ю | 0,4 | | З | 1,2 | П | 1,9 | Ч | 0,9 | Я | 1,4 |
Подобное распределение частот может быть найдено для диграфов (двухбуквенных
комбинаций), триграфов (трехбуквенных комбинаций) и n-графов (n-буквенных
комбинаций).
Это распределение частоты дает дешифровальщикам громадную информацию. Кроме
распределения частот может быть использован словарь русской лексики, для
автоматической проверки подстановочного отображения конкретной буквы. Например,
однобуквенными словами в русском языке являются а, в,
и, к и с. Дополнительно в распоряжении специалистов по
криптоанализу имеется дополнительная информация, такая как частота слов и
основные правила русской грамматики. Этого обычно оказывается достаточно для
того, чтобы раскрыть простой подстановочный шифр.
Не всегда криптография и криптоанализ так просты, как в примерах из этой
главы. Криптоанализ более сложных шифров требует более основательных знаний в
области математики и теории передачи данных.
В некоторых алгоритмах шифрования для шифрования и расшифровки используется
один и тот же ключ, или дешифровальный ключ может быть вычислен по
шифровальному ключу за небольшое время. Такие алгоритмы называются
алгоритмами с секретным ключом, алгоритмами с закрытым ключом или
симметричными алгоритмами. Ключ используемый в таких алгоритмах должен
храниться в тайне. Примером алгоритма с секретным ключом является алгоритм
Data Encryption Stantart (DES).
2.1. Стандарт Data Encryption Stantart (DES).
В 1997 г. в США Национальным Институтом Стандартов и Технологий (NIST) в
качестве стандартного алгоритма шифрования для защиты несекретной информации
был принят алгоритм DES. Этот алгоритм вполне уверенно противостоял открытым
попыткам взлома вплоть до середины 90-х годов, когда были отмечены попытки
взлома с использованием методов дифференциального и линейного криптоанализа.
К январю 1999 г. фонду Electronic Frontier Foundation уже удавалось
взламывать сообщения, зашифрованные с помощью алгоритма DES, не более чем за
сутки.
Несмотря на свою уязвимость, этот алгоритм все еще используется в некоторых
приложениях и обеспечивает достаточно высокий уровень защиты в тех случаях,
когда затраты на расшифровку информации превышают ее ценность. Например
расшифровка информации, содержащейся в моей кредитной карточке, будь она
зашифрована по алгоритму DES, обойдется намного дороже, чем сумма, которую
можно будет извлечь в результате этого. К тому же, DES уже используется в
нескольких более сложных алгоритмов шифрования, таких, например, как
TripleDES.
В алгоритме DES используется 64-х-разрядный ключ – 8 битов применяются для
исправления ошибок (контроля четности). В результате эффективная длина ключа
составляет 56 бит. Шифрование и расшифровка в алгоритме DES осуществляется
блоками по 64 бита (8 байтов), и из 64 битов открытого текста получается 64
бита зашифрованного текста. Алгоритм заключается в не зависящей от ключа
перестановке входных данных с последующим шифрованием их с помощью открытого
ключа, после чего осуществляется обратная перестановка данных.
Алгоритм DES может быть использован в различных методах шифрования, в
зависимости от назначения. Вот несколько примеров методов шифрования:
· Метод ECB (Electronic Codebook – Электронная шифровальная книга) –
шифрование осуществляется 8-и-байтовыми блоками, причем последующий блок
зашифрованного текста не зависит от предыдущих блоков как зашифрованного, так
и открытого текста.
· Метод CBC (Cipher Block Changing – Сцепление зашифрованных блоков) –
n-ный блок шифруемого текста получается в результате выполнения операции XOR
(исключающего или) над (n-1)-м блоком защифрованного текста и n-ным блоком
открытого текста.
· Метод CFB (Cipher Feedback – Обратная связь по шифру) – предыдущая
порция зашифрованного текста объединяется со следующей порцией открытого
текста.
· Метод OFB (Output Feedback – Обратная связь по выходу) – алгоритм
DES используется для создания псевдослучайного потока битов, который
объединяется с открытым текстом, в результате чего создается поток
зашифрованного текста.
· Метод PCBC (Propagating Cipher Block Changing – Сцепление
зашифрованных блоков с множественной связью) – Отличается от метода CBC тем,
что с n-ным блоком зашифрованного текста объединяется как (n-1)-й блок
зашифрованного текста, так и (n-1)-й блок открытого текста.
Когда требуется зашифровать не 8-и-байтовый, а более короткий блок открытого
текста (например, последние байты файла или сообщения), он дополняется до
заполнения 64-х-разрядного регистра. В связи с этим возникает проблема – как
при расшифровке отличить исходный текст от дополняющих байтов. Для решения
этой проблемы компанией RSA Data Encryption, Inc. Был разработан стандарт под
названием “Public Key Cryptography Standart #5 padding ” (“Дополнение к
стандарту шифрования с открытым ключом #5”). Это дополнение заключается в
следующем: “Если n – число байтов, которыми нужно дополнить блок, то значение
каждого дополняющего байта устанавливается в n. Если дополнение не требуется,
то добавляется один блок, в котором значение каждого байта устанавливается в
8”
Методы шифрования и дополнения блоков, используемые с алгоритмом DES, по
своей природе, универсальны и могут быть использованы с другими шифрами,
такими, например, как DESede или Blowfish
В связи с популярностью алгоритма DES и его недостатками, выявленными во
второй половине 90-х годов, криптографы искали способы повышения его
стойкости, при одновременном сохранении его в качестве базового алгоритма
шифрования. В алгоритмах DESede выполняется троекратное шифрование по
алгоритму DES, что приводит к эффективной длине ключа в 168 разрядов. В одном
из вариантов DESede третий ключ равен первому, эффективная длина ключа в
таком случае составляет 112 разрядов.
Blowfish – это шифр с секретным ключом, разработанный Брюсом Шейнером,
ведущим специалистом-криптографом, автором нашумевшей книги Applied
Cryptography (Прикладная криптография). Этот алгоритм на запатентован, он
бесплатный и беспошлинный, и на его использование не требуется лицензии.
Blowfish является 64-х-разрядным блочным шифром, предназначенным для
встраиваемой замены алгоритма DES. Он превосходит DES по скорости шифрования
и намного – по стойкости. Длина его ключа варьируется от 32-х до 448-и
разрядов.
В предыдущих главах рассматривались методы шифрования с закрытым ключом. Но
шифрование с секретным ключом – это не единственный способ шифрования данных.
Одним из наиболее значительных прорывов в криптографии двадцатого столетия
была разработка шифрования с открытым ключом.
Алгоритмы с открытым ключом, или асимметричные алгоритмы, базируются
на использовании отдельных шифровального (открытого – public) и дешифровального
(закрытого – private) ключей. В алгоритмах с открытым ключом требуется, чтобы
закрытый ключ было невозможно вычислить по открытому ключу. Исходя из этого
требования шифровальный ключ может быть доступным кому угодно без какого-либо
ущерба безопасности алгоритма шифрования.
Этот алгоритм известен как RSA и носит инициалы его изобретателей. Этот
алгоритм имеет важное значение, поскольку может быть использован как для
шифрования, так и для цифровых подписей.
Стойкость алгоритма RSA определяется сложностью разложения больших чисел на
множители. (Наверное, криптоанализ шифра RSA возможен и без использования
операции разложения на множители, но никто до сих пор не доказал этого).
Ниже кратко описан принцип действия алгоритма RSA:
1.Генерируется два простых числа p и q (100 цифр и более), причем n=pq.
2.В качестве открытого ключа выбирается целое число e, взаимно простое
с числом (p-1)(q-1).
3.Закрытый ключ d вычисляется из условия ed mod (p-1)(q-1) = 1.
4.Шифрование открытого числа m (где m < n),
осуществляется путем вычисления mc mod n.
5.Расшифровка зашифрованного числа c осуществляется путем вычисления cd mod m.
Основным недостатком шифра RSA и других алгоритмов с открытым ключом,
является их низкая производительность, по сравнению с алгоритмами с секретным
ключом. Алгоритм RSA уступает по скорости сопоставимым реализациям алгоритма
DES в 100, а то и в 1000 раз.
Хотя шифр RSA еще никому не удалось раскрыть, прогресс в математике может
сделать этот шифр устаревшим. При наличии эффективного способе разложения
больших чисел на множители шифр RSA можно легко раскрыть. К тому же алгоритм
RSA и другие алгоритмы с открытым ключом не защищены от множества атак,
которые определяются способами использования этих алгоритмов.
Хотя RSA и является одним из самых популярных алгоритмов шифрования с
открытым ключом, имеется также множество других алгоритмов. Один из них –
алгоритм AlGamal, разработанный в 1984 г. Тэгером Эль-Гамалом. Он не
запатентован и может использоваться свободно.
Защищенность алгоритма AlGamal базируется на сложности вычисления дискретного
логарифма в конечном поле. А заключается алгоритм в следующем:
1.Выбирается простое число p и два случайных числа, g и x, меньших чем p.
2.Открытый ключ состоит из чисел g, p, и y, где
y=gx mod p. Закрытым ключом является число x.
3.Для шифрования блока сообщения m, выбирается случайное чтило k
, такое, что k и (p-1) взаимно простые числа, и вычисляется
a=gk mod p. Зашифрованным блоком являются оба числа – a
и b.
4.Для расшифровки a и b вычисляется m=(b/ax) mod p.
Область применения криптографических методов не ограничивается только защитой
тайны сообщений. Они также используются в следующих областях:
1. Целостность – для обнаружения фактов изменения или подмены сообщения
2. Аутентификация – для проверки того, что сообщение действительно
создано лицом или организацией, от имени которой они поступили.
3. Неаннулируемость – для недопущения того, чтобы тот, кто послал
сообщение или выполнил некоторую операцию над объектом, мог отрицать тот
факт, что именно он сделал это.
Перечисленные задачи решаются с помощью дайджестов сообщений и цифровых
подписей.
Дайджест сообщения – это особый вид функции, носящей название односторонней
функции или функции хеширования. Одностороннюю функцию легко вычислить, но
сложно обращать. Функции дайджеста сообщения должны обладать следующими
свойствами:
· По конкретному значению дайджеста сообщения невозможно численными
методами установить сообщение, по которому функция дайджеста сообщения
вычислила это значение.
· Невозможно численными методами найти два различных сообщения, по
которым функция дайджеста сообщения вычислила совпадающие значения.
Заметьте, в самой функции дайджеста сообщений никакого секрета нет – она
общедоступна и не использует ключей. Примерами алгоритма дайджеста сообщения
являются алгоритмы MD5 и SHA-1.
Цифровые подписи обеспечивают замечательную возможность узнавать то, было ли
сообщение (или иной объект) случайно или преднамеренно изменено. Цифровые
сертификаты позволяют установить было ли сообщение действительно создано
конкретным лицом или организацией.
Цифровая подпись – это значение, которое вычисляется из последовательности
байтов с использованием секретного ключа. Она свидетельствует о том, что
владелец этого секретного ключа подтвердил корректность и подлинность
содержимого сообщения. В методах цифровой подписи часто используются
алгоритмы шифрования с открытым ключом, но несколько иначе, чем обычно, а
именно: закрытый ключ применяется для шифрования, а открытый – для
расшифровки. На практике это выглядит следующим образом:
1. Создается цифровая подпись
1.1. Вычисляется дайджест сообщения
1.2. Дайджест сообщения зашифровывается с помощью закрытого ключа из пары
“открытый/закрытый ключ”, в результате чего получается цифровая подпись.
2. Производится верификация цифровой подписи
2.1. Подпись расшифровывается с помощью открытого ключа из вышеупомянутой
пары “открытый/закрытый ключ ”, в результате чего восстанавливается дайджест
сообщения.
2.2. Значение расшифрованного дайджеста сообщения расшифровывается и
сравнивается со значением дайджеста сообщения вычисленного из исходного
сообщения
Если оба значения дайджеста сообщения совпадают, то подпись подлинная. В
противном случае или подпись, или сообщение были изменены.
Описанный выше подход к созданию и проверке подписей несет в себе как
характерные черты реальных подписей, так и другие особенности, которые
обеспечивают следующие возможности:
· Подпись нельзя подделать – подписавшее лицо использует для подписи
закрытый ключ, а он является секретным.
· Подлинность подписи всегда можно проверить – поскольку открытый ключ
подписавшего лица общедоступен, любое лицо, имеющее в руках сообщение и
цифровую подпись может проверить, что сообщение было подписано данным лицом и
что ни оно, ни подпись не были изменены.
· Подпись неповторима – каждому сообщению соответствует своя,
неповторимая подпись. Невозможно численными методами использовать подписи
вместе с другим сообщением.
· Факт подписи невозможно отрицать – после того как сообщение
подписано и отослано вместе с подписью, лицо, сделавшее это не может
отрицать, что оно сделало это (если только не докажет, это закрытый ключ был
похищен)
Как видно, цифровые подписи – это прекрасный способ подтверждения того, что
сообщение (или объект) было создано или проверено конкретным лицом или
организацией. Но есть одна каверза – вам нужно каким-то образом определить,
что открытый ключ, который вы получили от имени кого-то, - это действительно
его открытый ключ. Вот где в дело вступают цифровые сертификаты.
Цифровые сертификаты – это сообщения, подписанные полномочным органом
сертификации (Certificate Aythory – CA), который заверяет значение открытого
ключа, принадлежащего кому-либо, и использование конкретного алгоритма
шифрования. Чтобы получить сертификат полномочного органа сертификации,
обычно нужно представить в него документы, подтверждающие личность заявителя.
В больших сетях, таких как Internet, может оказаться необходимой
многоуровневая структура сертификации. В таком случае орган высшего уровня,
например компания VeriSign, Inc., могут выдавать сертификаты полномочным
органам второго уровня. Органы второго уровня могут, в свою очередь, выдавать
сертификаты другим компаниям. В результате возникает иерархическая структура
сертификации. Сертификация лиц находящихся в конце ветвей этой структуры
зависит от лиц занимающих более высокий уровень иерархии. Такие связи
называют цепочками сертификации.
Сертификаты X.509 ISO являются популярным видом цифровых сертификатов. X.509
означает определенный формат и содержание цифрового сертификата. Этот формат
стал популярным благодаря протоколу защищенных сокетов (SSL) компании
Netscape, формату архивных файлов Java (JAR), а также ряду других новых
стандартов безопасности Internet.
Значение криптографии в современном информационном обществе трудно
переоценить. Новая информационная инфраструктура создает новые опасности для
информации. Открытые каналы Internet могут стать серьезной угрозой
безопасности передачи данных. Однако и криптография не стоит на месте. Теперь
она стала доступна широким массам пользователей. При помощи широкодоступных
алгоритмов шифрования, а также цифровых подписей и сертификатов, пользователи
могут добиться безопасности и скрытности передачи своих данных. Нужно только
уметь всем этим пользоваться.
1.Джим Яворски, Пол Дж. Перроун Система безопасности Java. Спб 2001 г.
2.М. Холл Сервлеты и Java Server Pages. Спб 2001 г.
3.М. Холл, Л Браун Программирование для Web. Спб 2002 г.
|
|
|
