Иллюстрация работы RSA на примере
Вокруг алгоритмов шифрования с отрытым и закрытым ключом существует множество недопониманий и мистификаций. Здесь я хотел бы предельно коротко и наглядно, с конкретными числами и минимумом формул, показать, как это работает.
Я не вдаюсь в теорию (не очень понятно, на какой уровень подготовки читателя следует рассчитывать), но я уверен, что прочитав эту короткую иллюстрацию, любому человеку будет проще разобраться в формулах и строгих доказательствах.
Итак. Допустим, я хочу получить от вас некие данные. Мы с вам не хотим, чтобы эти данные узнал кто-то, кроме нас. И у нас нет никакой уверенности в надёжности канала передачи данных. Приступим.
Шаг первый. Подготовка ключей
Я должен проделать предварительные действия: сгенерировать публичный и приватный ключ.
- Выбираю два простых числа. Пусть это будет p=3 и q=7 .
- Вычисляем модуль — произведение наших p и q : n=p×q=3×7=21 .
- Вычисляем функцию Эйлера: φ=(p-1)×(q-1)=2×6=12 .
- Выбираем число e , отвечающее следующим критериям: (i) оно должно быть простое, (ii) оно должно быть меньше φ — остаются варианты: 3, 5, 7, 11, (iii) оно должно быть взаимно простое с φ ; остаются варианты 5, 7, 11. Выберем e=5 . Это, так называемая, открытая экспонента.
Теперь пара чисел
Мне нужно вычислить число d , обратное е по модулю φ . То есть остаток от деления по модулю φ произведения d×e должен быть равен 1. Запишем это в обозначениях, принятых во многих языках программирования: (d×е)%φ=1 . Или (d×5)%12=1 . d может быть равно 5 ( (5×5)%12=25%12=1 ), но чтобы оно не путалось с e в дальнейшем повествовании, давайте возьмём его равным 17. Можете проверить сами, что (17×5)%12 действительно равно 1 ( 17×5-12×7=1 ). Итак d=17 . Пара
Шаг второй. Шифрование
Теперь пришла ваша очередь шифровать ваше сообщение. Допустим, ваше сообщение это число 19. Обозначим его P=19 . Кроме него у вас уже есть мой открытый ключ:
- Возводите ваше сообщение в степень e по модулю n . То есть, вычисляете 19 в степени 5 (2476099) и берёте остаток от деления на 21. Получается 10 — это ваши закодированные данные.
Строго говоря, вам вовсе незачем вычислять огромное число «19 в степени 5». При каждом умножении достаточно вычислять не полное произведение, а только остаток от деления на 21. Но это уже детали реализации вычислений, давайте не будем в них углубляться.
Полученные данные E=10 , вы отправляете мне.
Здесь надо заметить, что сообщение P=19 не должно быть больше n=21 . иначе ничего не получится.
Шаг третий. Расшифровка
Я получил ваши данные ( E=10 ), и у меня имеется закрытый ключ
Обратите внимание на то, что открытый ключ не может расшифровать сообщение. А закрытый ключ я никому не говорил. В этом вся прелесть асимметричного шифрования.
- Я делаю операцию, очень похожую на вашу, но вместо e использую d . Возвожу E в степень d : получаю 10 в степени 17 (позвольте, я не буду писать единичку с семнадцатью нулями). Вычисляю остаток от деления на 21 и получаю 19 — ваше сообщение.
Заметьте, никто, кроме меня (даже вы!) не может расшифровать ваше сообщение ( E=10 ), так как ни у кого нет закрытого ключа.
В чём гарантия надёжности шифрования
Надёжность шифрования обеспечивается тем, что третьему лицу (старающемуся взломать шифр) очень трудно вычислить закрытый ключ по открытому. Оба ключа вычисляются из одной пары простых чисел ( p и q ). То есть ключи связаны между собой. Но установить эту связь очень сложно. Основной загвоздкой является декомпозиция модуля n на простые сомножители p и q . Если число является произведением двух очень больших простых чисел, то его очень трудно разложить на множители.
Постараюсь это показать на примере. Давайте разложим на множители число 360:
- сразу ясно, что оно делится на два (получили 2)
- оставшееся 180 тоже, очевидно чётное (ещё 2)
- 90 — тоже чётное (ещё двойка)
- 45 не делится на 2, но следующая же попытка оказывается успешной — оно делится на три (получили 3)
- 15 тоже делится на 3
- 5 — простое.
Мы на каждом шагу, практически без перебора, получали всё новые и новые множители, легко получив полное разложение 360=2×2×2×3×3×5
Давайте теперь возьмём число 361. Тут нам придётся помучиться.
- оно не чётное
- три — нет, не делится
- пять (допустим, мы поступаем умно и перебираем только простые числа, хотя, на практике, поиск больших простых чисел, сам по себе, является сложной задачей) — не подходит
- семь? — нет.
- …
- и только 19 даст нам ответ: 361=19×19.
При использовании больших чисел, задача становится очень сложной. Это позволяет надеяться, что у взломщика просто не хватит вычислительных ресурсов, чтобы сломать ваш шифр за обозримое время.
А как это всё работает на практике?
Многие читатели спрашивают, как всё это применяется на практике. Давайте рассмотрим чуть более приближенный к жизни пример. Зашифруем и расшифруем слово «КРОТ», предложенное одним из читателей. А заодно, бегло рассмотрим, какие проблемы при этом встречаются и как они решаются.
Сперва сгенерируем ключи с чуть бо́льшими числами. Они не так наглядны, но позволят нам шифровать не только числа от нуля до 20.
Оттолкнёмся от пары простых чисел
Мы готовы к шифрованию. Переведём наше слово в цифровое представление. Мы можем взять просто номера букв в алфавите. У нас получится последовательность чисел: 11, 17, 15, 19.
Мы можем зашифровать каждое из этих чисел открытым ключом
Немного о сложностях
На самом деле, изложенный способ шифрования очень слаб и никогда не используется. Причина проста — шифрование по буквам. Одна и та же буква будет шифроваться одним и тем же числом. Если злоумышленник перехватит достаточно большое сообщение, он сможет догадаться о его содержимом. Сперва он обратит внимание на частые коды пробелов и разделит шифровку на слова. Потом он заметит однобуквенные слова и догадается, как кодируются буквы «a», «и», «o», «в», «к»… Путём недолгого перебора, он вычислит дополнительные буквы по коротким словам, типа «но», «не», «по». И по более длинным словам без труда восстановит все оставшиеся буквы.
Таким образом, злоумышленнику не придётся отгадывать ваши секретные ключи. Он взломает ваше сообщение, не зная их.
Чтобы этого не происходило, используются специальные дополнительные алгоритмы, суть которых в том, что каждая предыдущая часть сообщения начинает влиять на следующую.
Упрощённо, это выглядит так. Перед шифрованием, мы применяем к сообщению правило: b := (b + a) % n . Где a — предыдущая часть сообщения, а b — следующая. То есть наше сообщение (11, 17, 15, 19) изменяется. 11 остаётся без изменений. 17 превращается в (11 + 17) % 323 = 28 . 15 становится (15 + 28) % 323 = 43 . A 19 превращается в 62.
Последовательность (11, 28, 43, 62) получается «запутанной». Все буквы в ней как бы перемешаны, в том смысле, что на каждый код влияет не одна буква, а все предыдущие.
Тот, кто получит ваше сообщение, должен будет проделать обратную операцию, со знаком «минус»: b := (b — a) % n . И только тогда он получит коды букв.
На практике, в исходное сообщение специально добавляются случайные и бессмысленные буквы в начало. Чтобы даже по первому коду было невозможно ничего понять. Получатель просто отбрасывает начало сообщения.
То есть мы можем добавить случайное число в начало и получить (299, 11, 17, 15, 19). После перемешивания получится: 299, 310, 4, 19, 38. После шифрования уже невозможно будет догадаться где была какая буква.
В реальной жизни всё ещё немного сложнее. Блоки, на которые бьётся сообщение длиннее одной буквы. Поэтому, сперва применяются алгоритмы выравнивания, потом алгоритмы разбиения на блоки с перепутыванием, и только потом применяется само RSA-шифрование.
Получатель делает всё в обратном порядке: расшифровывает, «распутывает» блоки и отбрасывает ненужную информацию, добавленную просто для выравнивания (чтобы сообщение можно было разбить на целое число блоков).
Детали и принципы формирования блоков можно почитать тут. Я же в этой заметке хотел рассказать только про RSA. Надесь, удалось.
10 популярных кодов и шифров
Коды и шифры — это не одно и то же: в коде каждое слово заменяется другим, в то время как в шифре заменяются все символы сообщения.
В данной статье мы рассмотрим наиболее популярные виды шифров, методы шифрования, а следующим шагом будет изучение основ криптографии.
Стандартные шифры
Этот шифр известен многим детям. Ключ прост: каждая буква заменяется на следующую за ней в алфавите. Так, А заменяется на Б, Б — на В, и т. д. Фраза «Уйрйшоьк Рспдсбннйту» — это «Типичный Программист».
Попробуйте расшифровать сообщение:
Поняли, как работает это шифрование? Напишите в комментариях, что у вас получилось.
Шифр транспонирования
В транспозиционном шифре буквы переставляются по заранее определённому правилу. Например, если каждое слово пишется задом наперед, то из hello world получается dlrow olleh. Другой пример — менять местами каждые две буквы. Таким образом, предыдущее сообщение станет eh ll wo ro dl.
Ещё можно использовать столбчатый шифр транспонирования, в котором каждый символ написан горизонтально с заданной шириной алфавита, а шифр создаётся из символов по вертикали. Пример:
Из этого способа мы получим шифр holewdlo lr. А вот столбчатая транспозиция, реализованная программно:
Азбука Морзе
В азбуке Морзе каждая буква алфавита, цифры и наиболее важные знаки препинания имеют свой код, состоящий из череды коротких и длинных сигналов:
Чаще всего это шифрование передаётся световыми или звуковыми сигналами.
Сможете расшифровать сообщение, используя картинку?
Шифр Цезаря
Это не один шифр, а целых 26, использующих один принцип. Так, ROT1 — лишь один из вариантов шифра Цезаря. Получателю нужно просто сообщить, какой шаг использовался при шифровании: если ROT2, тогда А заменяется на В, Б на Г и т. д.
А здесь использован шифр Цезаря с шагом 5:
Моноалфавитная замена
Коды и шифры также делятся на подгруппы. Например, ROT1, азбука Морзе, шифр Цезаря относятся к моноалфавитной замене: каждая буква заменяется на одну и только одну букву или символ. Такие шифры очень легко расшифровываются с помощью частотного анализа.
Например, наиболее часто встречающаяся буква в английском алфавите — «E». Таким образом, в тексте, зашифрованном моноалфавитным шрифтом, наиболее часто встречающейся буквой будет буква, соответствующая «E». Вторая наиболее часто встречающаяся буква — это «T», а третья — «А».
Однако этот принцип работает только для длинных сообщений. Короткие просто не содержат в себе достаточно слов.
Шифр Виженера
Представим, что есть таблица по типу той, что на картинке, и ключевое слово «CHAIR». Шифр Виженера использует принцип шифра Цезаря, только каждая буква меняется в соответствии с кодовым словом.
В нашем случае первая буква послания будет зашифрована согласно шифровальному алфавиту для первой буквы кодового слова «С», вторая буква — для «H», etc. Если послание длиннее кодового слова, то для (k*n+1)-ой буквы, где n — длина кодового слова, вновь будет использован алфавит для первой буквы кодового слова.
Чтобы расшифровать шифр Виженера, для начала угадывают длину кодового слова и применяют частотный анализ к каждой n-ной букве послания.
Попробуйте расшифровать эту фразу самостоятельно:
Подсказка длина кодового слова — 4.
Шифр Энигмы
Энигма — это машина, которая использовалась нацистами во времена Второй Мировой для шифрования сообщений.
Есть несколько колёс и клавиатура. На экране оператору показывалась буква, которой шифровалась соответствующая буква на клавиатуре. То, какой будет зашифрованная буква, зависело от начальной конфигурации колес.
Существовало более ста триллионов возможных комбинаций колёс, и со временем набора текста колеса сдвигались сами, так что шифр менялся на протяжении всего сообщения.
Цифровые шифры
В отличие от шифровки текста алфавитом и символами, здесь используются цифры. Грубо говоря, шифр слова цифрами. Рассказываем о способах и о том, как расшифровать цифровой код.
Двоичный код
Текстовые данные вполне можно хранить и передавать в двоичном коде. В этом случае по таблице символов (чаще всего ASCII) каждое простое число из предыдущего шага сопоставляется с буквой: 01100001 = 97 = «a», 01100010 = 98 = «b», etc. При этом важно соблюдение регистра.
Расшифруйте следующее сообщение, в котором использована кириллица:
Шифр A1Z26
Алфавит по цифрам. Это простая подстановка, где каждая буква заменена её порядковым номером в алфавите. Только нижний регистр.
Попробуйте определить, что здесь написано:
Шифрование публичным ключом
Алгоритм шифрования, применяющийся сегодня буквально во всех компьютерных системах. Есть два ключа: открытый и секретный. Открытый ключ — это большое число, имеющее только два делителя, помимо единицы и самого себя. Эти два делителя являются секретным ключом, и при перемножении дают публичный ключ. Например, публичный ключ — это 1961, а секретный — 37 и 53.
Открытый ключ используется, чтобы зашифровать текст сообщения, а секретный — чтобы расшифровать текст.
Как-то RSA выделила 1000 $ в качестве приза тому, кто найдет два пятидесятизначных делителя числа:
Как расшифровать код или шифр?
Для расшифровки шифров онлайн применяются специальные сервисы. Это может быть расшифровка цифр в буквы и наоборот, расшифровка кода и многое другое. Выбор такого инструмента зависит от того, что за код предстоит расшифровать. Примеры шифраторов, с которыми вы подробнее узнаете, как зашифровать слово, и дешифраторов:
10. Стеганография
Стеганография — это искусство скрытого письма. Этой технике даже больше лет, чем кодам и шифрованию. Например, сообщение может быть написано на бумаге, покрыто ваксой и проглочено с той целью, чтобы незаметно доставить его получателю. Другой способ — нанести сообщение на бритую голову курьера, подождать, пока волосы вырастут заново и скроют послание. Лучше всего для стеганографии использовать повседневные объекты. Когда-то в Англии использовался такой метод: под некоторыми буквами на первой странице газеты стояли крохотные точки, почти невидимые невооруженным глазом. Если читать только помеченные буквы, то получится секретное сообщение! Некоторые писали сообщение первыми буквами составляющих его слов или использовали невидимые чернила. Была распространена практика уменьшения целых страниц текста до размера буквально одного пикселя, так что их было легко пропустить при чтении чего-то относительно безобидного. Стеганографию лучше всего использовать в сочетании с другими методами шифрования, так как всегда есть шанс, что ваше скрытое послание обнаружат и прочитают.
9. ROT1
Этот шифр известен многим детям. Ключ прост: каждая буква заменяется на следующую за ней в алфавите. Так, A заменяется на B, B на C, и т.д. «ROT1» значит «ROTate 1 letter forward through the alphabet» (англ. «сдвиньте алфавит на одну букву вперед»). Сообщение «I know what you did last summer» станет «J lopx xibu zpv eje mbtu tvnnfs». Этот шифр весело использовать, потому что его легко понять и применять, но его так же легко и расшифровать. Из-за этого его нельзя использовать для серьезных нужд, но дети с радостью «играют» с его помощью. Попробуйте расшифровать сообщение «XBT JU B DBU J TBX?».
8. Транспозиция
В транспозирующих шифрах буквы переставляются по заранее определенному правилу. Например, если каждое слово пишется задом наперед, то из «all the better to see you with» получается «lla eht retteb ot ees joy htiw». Другой пример — менять местами каждые две буквы. Таким образом, предыдущее сообщение станет «la tl eh eb tt re ot es ye uo iw ht». Подобные шифры использовались в Первую Мировую и Американскую Гражданскую Войну, чтобы посылать важные сообщения. Сложные ключи могут сделать такой шифр довольно сложным на первый взгляд, но многие сообщения, закодированные подобным образом, могут быть расшифрованы простым перебором ключей на компьютере. Попробуйте расшифровать «THGINYMROTSDNAKRADASAWTI».
7. Азбука Морзе
В азбуке Морзе каждая буква алфавита, все цифры и наиболее важные знаки препинания имеют свой код, состоящий из череды коротких и длинных сигналов, часто называемых «точками и тире». Так, A — это «•–», B — «–•••», и т.д. В отличие от большинства шифров, азбука Морзе используется не для затруднения чтения сообщений, а наоборот, для облегчения их передачи (с помощью телеграфа). Длинные и короткие сигналы посылаются с помощью включения и выключения электрического тока. Телеграф и азбука Морзе навсегда изменили мир, сделав возможной молниеносную передачу информации между разными странами, а также сильно повлияли на стратегию ведения войны, ведь теперь можно было можно осуществлять почти мгновенную коммуникацию между войсками.
6. Шифр Цезаря
Шифр Цезаря называется так, как ни странно, потому что его использовал сам Юлий Цезарь. На самом деле шифр Цезаря — это не один шифр, а целых двадцать шесть, использующих один и тот же принцип! Так, ROT1 — всего один из них. Получателю нужно сказать, какой из шифров используется. Если используется шифр «G», тогда А заменяется на G, B на H, C на I и т.д. Если используется шифр «Y», тогда А заменяется на Y, B на Z, C на A и т.д. На шифре Цезаря базируется огромное число других, более сложных шифров, но сам по себе он не представляет из себя интереса из-за легкости дешифровки. Перебор 26 возможных ключей не займет много времени. Li bra ghflskhu wklv dqg bra nqrz lw, fods brxu kdqgv.
5. Моноалфавитная замена
ROT1, азбука Морзе, шифр(ы) Цезаря относятся к одному и тому же типу шифров — моноалфавитной замене. Это значит, что каждая буква заменяется на одну и только одну другую букву или символ. Такие шифры очень легко расшифровать даже без знания ключа. Делается это при помощи частотного анализа. Например, наиболее часто встречающаяся буква в английском алфавите — «E». Таким образом, в тексте, зашифрованном моноалфавитным шрифтом, наиболее часто встречающейся буквой будет буква, соответствующая «E». Вторая наиболее часто встречающаяся буква — это «T», а третья — «А». Человек, расшифровывающий моноалфавитный шифр, может смотреть на частоту встречающихся букв и почти законченные слова. Так, «T_E» с большой долей вероятности окажется «ТНЕ». К сожалению, этот принцип работает только для длинных сообщений. Короткие просто не содержат в себе достаточно слов, чтобы с достаточной достоверностью выявить соответствие наиболее часто встречающихся символов буквам из обычного алфавита. Мария Стюарт использовала невероятно сложный моноалфавитный шифр с несколькими вариациями, но когда его наконец-то взломали, прочитанные сообщения дали ее врагам достаточно поводов, чтобы приговорить ее к смерти. Ptbndcb ymdptmq bnw yew, bnwzw raw rkbcriie wrze bd owktxnwa.
4. Шифр Виженера
Этот шифр сложнее, чем моноалфавитные. Представим, что у нас есть таблица, построенная по тому же принципу, что и приведенная выше, и ключевое слово, допустим, «CHAIR». Шифр Виженера использует тот же принцип, что и шифр Цезаря, за тем исключением, что каждая буква меняется в соответствии с кодовым словом. В нашем случае первая буква послания будет зашифрована согласно шифровальному алфавиту для первой буквы кодового слова (в нашем случае «С»), вторая буква — согласно алфавиту для второй буквы кодового слова («H»), и так далее. В случае, если послание длиннее кодового слова, то для (k*n+1)-ой буквы (где n — это длина кодового слова) вновь будет использован алфавит для первой буквы кодового слова, и так далее. Очень долгое время шифр Виженера считался невзламываемым. Чтобы его расшифровать, для начала угадывают длину кодового слова и применяют частотный анализ к каждой n-ной букве послания, где n — предполагаемая длина кодового слова. Если длина была угадана верно, то и сам шифр вскроется с большей или меньшей долей вероятности. Если предполагаемая длина не дает верных результатов, то пробуют другую длину кодового слова, и так далее до победного конца. Eoaqiu hs net hs byg lym tcu smv dot vfv h petrel tw jka.
3. Настоящие коды
В настоящих кодах каждое слово заменяется на другое. Расшифровывается такое послание с помощью кодовой книги, где записано соответствие всех настоящих слов кодовым, прямо как в словаре. Преимущества такого способа в том, что сообщению необходимо быть ЧРЕЗВЫЧАЙНО длинным, чтобы можно было его взломать с помощью частотного анализа, так что коды полезнее некоторых шифров. Многие страны использовали коды, периодически их меняя, чтобы защититься от частотного анализа. Тем не менее, есть и минус: кодовая книга становится критическим предметом, и в случае, если она будет украдена, то с ее помощью больше будет невозможно что-либо зашифровать, и придется придумывать новый код, что требует огромных усилий и затрат времени. Обычно коды используют только богатые и влиятельные люди, которые могут поручить работу по их составлению другим.
2. Шифр Энигмы
Энигма — это шифровальная машина, использовавшаяся нацистами во времена Второй Мировой. Принцип ее работы таков: есть несколько колес и клавиатура. На экране оператору показывалась буква, которой шифровалась соответствующая буква на клавиатуре. То, какой будет зашифрованная буква, зависело от начальной конфигурации колес. Соль в том, что существовало более ста триллионов возможных комбинаций колес, и со временем набора текста колеса сдвигались сами, так что шифр менялся на протяжении всего сообщения. Все Энигмы были идентичными, так что при одинаковом начальном положении колес на двух разных машинах и текст выходил одинаковый. У немецкого командования были Энигмы и список положений колес на каждый день, так что они могли с легкостью расшифровывать сообщения друг друга, но враги без знания положений послания прочесть не могли. Когда Энигма попала в руки к союзникам, они все равно сперва не могли ничего с ней сделать, потому что не знали положений-ключей. Дело по взлому шифра Энигмы было начато в польской разведке и доведено до конца в британской с помощью ученых и специальных машин (например, Turing Bombe, чья работа заключалась в том, чтобы моделировать одновременно работу сразу нескольких десятков Энигм). Отслеживание коммуникаций нацистов дало армии союзников важное преимущество в войне, а машины, использовавшиеся для его взлома, стали прообразом современных компьютеров.
1. Шифрование публичным ключом
Алгоритм шифрования, применяющийся сегодня в различных модификациях буквально во всех компьютерных системах. Есть два ключа: открытый и секретный. Открытый ключ — это некое очень большое число, имеющее только два делителя, помимо единицы и самого себя. Эти два делителя являются секретным ключом, и при перемножении дают публичный ключ. Например, публичный ключ — это 1961, а секретный — 37 и 53. Открытый ключ используется для того, чтобы зашифровать сообщение, а секретный — чтобы расшифровать. Без секретного ключа расшифровать сообщение невозможно. Когда вы отправляете свои личные данные, допустим, банку, или ваша банковская карточка считывается банкоматом, то все данные шифруются открытым ключом, а расшифровать их может только банк с соотвествующим секретным ключом. Суть в том, что математически очень трудно найти делители очень большого числа.
Криптографическая защита информации
Рассмотрим конкретный пример. Пусть директор фирмы А отправляет директору фирмы В важный документ по электронной почте (рис. 1). Какие возникают проблемы с точки зрения безопасности коммуникации?
Получая письмо, директор фирмы В задается следующими вопросами. Действительно ли данный документ был отправлен директором А (идентификация отправителя). Ведь есть вероятность, что письмо пришло от другого лица, которое выдает себя за директора фирмы А. Не был ли документ перехвачен и изменен на пути доставки (аутентификация послания). Не был ли документ прочитан кем-либо кроме получателя (сохранение тайны)
Известно, что сохранения тайны (конфиденциальности послания) можно достичь путем шифрования данных. Оказывается, на базе шифрования можно решить все три перечисленные задачи, и занимается этими вопросами криптография.
Криптография (от греч. «cryptos» — тайный) — это наука и технология шифрования важной информации для защиты ее от изменений и неавторизованного доступа. Криптография служит не только для перевода текстов в нечитаемую зашифрованную форму, но позволяет также решить задачи аутентификации и идентификации пользователей при работе их в Сети.
Криптография является основой безопасных коммуникаций. На рис. 1 мы привели пример переписки двух корреспондентов. Следует отметить, что в Сети мы общаемся не только с людьми, но и с различными службами. Например, когда мы собираемся скачать с какого-либо сервера программу, нам тоже важно знать, что данный сервер принадлежит именно фирме-разработчику, а не фирме-пирату, который незаконно распространяет пиратское ПО.
Шифрование с помощью ключа
Процесс шифрования с помощью ключа заключается в том, что открытый текст комбинируется с цепочкой чисел (ключом) по правилам некоторого алгоритма (криптографического алгоритма) с целью получения зашифрованного сообщения.
Предположим, что мы хотим зашифровать открытый текст «Привет Вася» с помощью простейшего алгоритма — замены букв их номерами в алфавите. В результате мы получим зашифрованный текст вида: 17 18 10 3 6 20 3 1 19 33. Очевидно, что если посторонний узнает алгоритм шифрования, то использовать его в дальнейшем невозможно.
Избежать данного недостатка возможно используя шифрование с ключом. Для того, чтобы пояснить суть процесса шифрования с ключом, приведем простой пример (рис. 3).
Выпишем буквы текста и под ними запишем их номера в алфавите. Третей строчкой запишем буквы ключа, повторяя это слово на всю строку. Под буквами ключа запишем их номера в алфавите, а в четвертой строчке запишем сумму, которая и будет зашифрованным сообщением: 20 19 29 36 и т.д.
Зная ключ и алгоритм, легко расшифровать сообщение: 20 — 3 = 17, а семнадцатая буква алфавита это «П» и т.д. Даже если злоумышленнику известен алгоритм, но не известен ключ, сообщение прочитать без длительной процедуры подбора ключа невозможно. Таким образом, один алгоритм можно использовать со многими ключами для разных каналов связи, закрепив за каждым корреспондентом отдельный ключ.
Очевидно, что чем длиннее ключ шифра, тем больше необходимо переборов различных комбинаций при расшифровке и тем соответственно сложнее раскодировать сообщение. Шифры с ключами длиной более 128 бит называют сильными.
Шифрование с симметричным ключом
Рассмотрим конкретный пример: пусть корреспонденты А и В пишут друг другу письмо (рис. 4). Каждый имеет свой секретный ключ (определенный секретный код), который можно использовать для шифрования данных, перед отправкой в Сеть. Для того, чтобы нагляднее изобразить схему шифрования, будем пользоваться пиктограммами (рис. 2), то есть изображать ключ в виде обычного ключа, а зашифрованное сообщение в виде документа заклеенного в конверт. Тогда процесс шифрования и расшифровки можно представить в виде рис. 3.
Пользователь А зашифровывает сообщение своим секретным ключом, отсылает сообщение по Сети, а получатель В (пользуясь таким же секретным ключом) расшифровывает сообщение. Если посмотреть на рисунок, нетрудно убедиться, что схема симметрична. Левый и правый пользователь пользуются одинаковыми (симметричными) ключами, поэтому данный вид шифрования получил название шифрования с симметричным ключом.
Проблема шифрования с секретным ключом имеет определенные недостатки. Прежде всего, симметричное шифрование не позволяет решить проблему аутентификации. Например, А может написать письмо некоему третьему лицу С и заявить, что это сделал В.
Симметричный ключ должен быть установлен на компьютер отправителя и получателя до обмена секретными сообщениями. То есть заранее необходимо знать какие именно два компьютера будут «разговаривать» между собой. Очевидно, что шифрование для безопасного общения в Интернет имеет смысл в том случае, когда корреспондентам не нужно встречаться лично. Проблема возникает при передаче секретного ключа. Действительно. Если А передаст В секретный ключ в незашифрованном виде, то его могут перехватить. Если ключ послать в зашифрованном виде, то В не сможет его получить. Для переписки с несколькими корреспондентами необходимо иметь по одному ключу на каждого корреспондента, что неудобно. Для того, чтобы решить вышеуказанные проблемы, была предложена схема асимметричного шифрования (шифрования с публичным ключом).
Шифрование с публичным ключом
Шифрование с помощью публичного ключа основано на использовании пары ключей: закрытого (частного) и открытого (публичного) ключей.
Послание можно зашифровать и частным, и публичным ключом, а расшифровать только вторым ключом из пары. То есть послание, зашифрованное частным ключом можно расшифровать только публичным и наоборот. Частный ключ известен только владельцу, и его нельзя никому передавать, в то время как публичный ключ распространяется открыто всем корреспондентам.
Пару ключей — частный и публичный — можно использовать как для решения задач аутентификации (рис. 4), так и секретности (конфиденциальности) (рис. 6).
Согласно первой схеме (рис. 4): пользователь А заранее отсылает публичный ключ своим корреспондентам В и С, а затем отправляет им сообщение, зашифрованное своим частным ключом.
Схема, обеспечивающая секретность (конфиденциальность), представлена на рис. 6.
Для того чтобы обеспечить конфиденциальный обмен сообщениями в переписке двух лиц необходимо иметь две пары ключей рис 5.
При шифровании с помощью ключевой пары у Вас нет необходимости рассылать свой публичный ключ всем корреспондентам. Гораздо удобнее выложить этот ключ в Сети на некоем сервере с открытым доступом. Тогда каждый, может скачать данный ключ и послать Вам секретное сообщение, которое не прочтет никто кроме Вас.
Шифрование с симметричным и асимметричным ключом
Следует отметить, что алгоритм асимметричного шифрования сильно проигрывает симметричным в плане шифрования и расшифровки данных, поэтому многие существующие системы шифрования используют комбинацию асимметричной и традиционной симметричной систем шифрования. Шифрование с открытым ключом используется для передачи симметричного ключа, который служит непосредственно для шифрования передаваемой информации. Для того чтобы разобраться, какова логика работы данной схемы обратимся к рис. 8.
Цифровая подпись
Когда кто-то получает от Вас сообщение, зашифрованное Вашим частным ключом, то он уверен в аутентичности послания. То есть в данном случае шифрование эквивалентно поставленной подписи. Однако процесс шифрования на основе алгоритмов с открытым ключом — это достаточно длительный вычислительный процесс и для широкого использования цифровой подписи, нужны схемы, требующие менее длительных вычислений. Подобные схемы существуют. Для того, чтобы объяснить, как они функционируют необходимо ввести понятие односторонней хеш-функции. Односторонняя хеш-функция — это функция, которая преобразует исходное послание любой длины в строку символов ограниченной длины, так называемый дайджест послания. При использовании 16-байтной хеш-функции Вы на выходе получите запись длиной 16 байт.
Хеширование — это одностороннее, то есть необратимое, в отличие от шифрования, преобразование. По дайджесту послания нельзя восстановить исходное сообщение, но можно его однозначно идентифицировать.
Рассмотрим конкретный пример. Пусть А, применив хеш-функцию, получил дайджест в виде некоего кода, который на рис.8 обозначен как код1. Затем, используя свой личный ключ, А зашифровывает дайджест, который и становится аналогом подписи данного документа. Далее А отправляет открытый текст послания и цифровую подпись В. Абонент В расшифровывает подпись публичным ключом, который он получил от А и убеждается, что письмо действительно от А. Таким образом, аутентификация состоялась. Затем необходимо удостовериться, что послание не было изменено в процессе доставки.
В результате расшифровки В получает дайджест послания — код1. Затем В, используя ту же хеш-функцию, что и А, хеширует текст послания и получает дайджест в виде некоторого кода2. Если код1 и код2 совпадают, то В делает вывод о том, что текст послания не был изменен на этапе доставки.
Таким образом, цифровая подпись или электронная подпись — это метод аутентификации отправителя или автора подписи, подтверждающий, что содержание документа не было изменено. Цифровая подпись может быть поставлена как в зашифрованном, так и в открытом послании.
Фрагмент из книги Александра Прохорова «Интернет: Как это работает», информацию о книге можно найти по адресу.