Криптография

Что такое криптография?

Если перевести слово «криптография» с греческого языка, то получится «секретный шифр». Если же посмотреть определение в интернете, то можно узнать, что криптография-это наука, занимающаяся шифрованием текстов, чтобы предотвратить несанкционированный доступ к ним. То есть нам необходимо зашифровать информацию, чтобы никто, кроме человека, которому она адресована, не мог получить к ней доступ.

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

На этом сайте я бы хотела рассказать Вам о способах шифрования. Но для того, чтобы перейти к современным способам шифрования, я бы для начала хотела рассказать Вам о том, как люди шифровали информацию в древности.

Древние способы шифрования

Необходимость шифровать информацию была и в древние времена. Одним из первых методов шифрования был атбаш. Правило шифрования состоит в замене i-й буквы алфавита из n букв на букву с номером n-i+1. Так, если мы возьмём за основу русский текст, то каждую букву а в этом тексте мы должны будем поменять на я, каждую букву б-на ю и т.д. Этот способ шифрования очень прост как в использовании, так и дешифровке, т.е. не является надёжным.

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

Впоследствии в древности были разработаны ещё многие способы шифрования, такие как диск Энея, квадрат Полибия, шифр Цезаря и другие. Здесь я предлагаю Вам расшифровать послание, которое было зашифровано при помощи одного из перечисленных шифров.

Срйётвднба, дэ уствдкнкую у йвёвпкжо!

Нажмите, чтобы увидеть правильный ответ

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

Попытки сделать шифрование более надёжным

Позже стали широко распространены шифры, в которых каждой букве сопоставляется какой-нибудь символ. Такой способ шифрования использовался в рассказе Артура Конан Дойля «Пляшущие человечки».

Этот способ шифрования кажется уже гораздо более надёжным, ведь если у нас есть некоторый алфавит, состоящий, допустим, из 30 букв (знаки препинания шифровать в данном случае мы не будем). Для первой буквы алфавита есть 30 возможных символов, для второй все, кроме того, который обозначает первую букву, то есть 29, для третьей аналогично 28 и так далее. Таким образом всего различных вариантов сопоставления каждой букве какого-то символа 30*29*28…*3*2*1, то есть 30!. И тут, казалось бы, можно было остановиться, ведь 30! -число очень большое, однако нетрудно заметить, что есть буквы, которые используются чаще, а есть те, которые используются реже. Оказалось, что если взять довольно большой текст, то процентное содержание там определённой буквы можно предсказать с достаточно хорошей точностью, обладая соответствующей статистикой. Таким образом, перебрать нужно будет не 30! вариантов, а гораздо меньше, что делает этот способ шифрования ненадёжным. Можно, конечно, пробовать сопоставлять какой-то символ не каждой букве, а паре букв, но тогда символов будет уже не 30, а 30^2=900, что уже не так удобно в использовании, ведь процесс шифрования становится долгим, да и статистику и в этом случае никто не отменял, так что злоумышленник получить доступ к информации всё равно сможет. Так как же зашифровать информацию так, чтобы даже с помощью компьютера нельзя было злоумышленнику доступ к этой информации получить? Для того, чтобы ответить на этот вопрос, обратимся к современным методам шифрования.

Современное шифрование

Современное шифрование основано на некоторых теоремах из теории чисел (это такой раздел математики). И хоть теоремы, знание которых необходимо, чтобы понять основные принципы современного шифрования, и не такие уж и сложные, но рассказать здесь тут их доказательства я не смогу, а то статья получится слишком длинной. Однако для любителей математики или людей, которых заинтересовала эта статья, я оставлю ссылку на сайт, на котором можно скачать книжку, по которой я сама выучила эти теоремы (не обращайте внимание на то, что в конце книжка становится очень сложной, все используемые тут теоремы содержатся в первых 19 параграфах).

Теперь давайте перейдём к самому способу шифрования. Пусть мы знаем, что нам хотят передать какую-то информацию, но не хотим, чтобы кто-то другой мог получить к ней доступ. Тогда мы должны взять какое-то натуральное число n, такое, что оно является произведением 2 простых чисел p и q (p и q обязательно должны быть различны), а также является очень большим (как правило, используются числа, содержащие в себе приблизительно 700 знаков в десятичной системе исчисления). Тогда φ(n) (число чисел, взаимно простых с n и не превосходящих n)=(p-1)*(q-1). Для удобства обозначим (p-1)*(q-1) как N. Теперь возьмём какие-то натуральные числа a и b, такие что a*b=k*N+1, где k-любое натуральное число. Заметим, что компьютер воспринимает информацию как какое-то число, так что когда перед нами стоит задача передать информацию с помощью компьютера, то на самом деле целью является передать число. Итак, нам хотят передать некоторое число, обозначим его за I (тут стоит заметить, что для последующих далее рассуждений важно, чтобы I было меньше n, однако это не проблема, ведь n мы можем брать сколь угодно большим). Для этого мы сообщаем человеку, который хочет ним передать сообщение, числа n и a. Заметим, что числа эти можно разместить хоть в открытом доступе, потому что если даже злоумышленник узнает их, ничего страшного не произойдёт (это ведь просто случайно выбранные числа). Теперь мы попросим его возвести I в степень a и сообщить нам остаток при делении числа I^a на n. Пусть это какое-то число J. Мы же в свою очередь возведём J в степень b и посмотрим на остаток при делении на n. Покажем, что это и есть наше число I, которое нам хотели передать. Так как I^a имеет остаток J при делении на n, то J^b имеет такой же остаток, что и I^(a*b) при делении на n. Но a*b=k*N+1, то есть I^(k*N+1)=((I^N)^k)*I имеет такой же остаток, что и J^b, при делении на n. Также I^N имеет остаток 1 при делении на n (по обобщённой малой теореме Ферма). Таким образом, ((I^N)^k)*I имеет остаток I*1^k, то есть просто I делении на n. Значит J^b действительно имеет остаток I при делении на n. Итак, после долгих мучений мы получили некий алгоритм шифрования и расшифровки информации. Но почему же этот алгоритм работает? Почему злоумышленник не сможет узнать число I так же, как его узнали мы? Дело в том, что для того, чтобы узнать число I, злоумышленнику нужно знать число b (здесь я предполагаю, что злоумышленник получил все данные, которыми мы обменивались, то есть он знает числа n, a и J). Но для того, чтобы узнать число b, ему нужно хотя бы узнать число N (конечно же, ему нужно узнать ещё и k, но я пока это учитывать не буду), то есть ему нужно узнать φ(n). Но для того, чтобы узнать φ(n), злоумышленнику нужно разложить число n на простые множители (так как очевидно, что считать даже с помощью компьютера число всех чисел, взаимно простых с числом, состоящим из приблизительно 700 знаков, не вариант). Однако даже сейчас не существует программы, которая могла бы достаточно быстро (в данном случае это хотя бы за несколько месяцев) разложить такое большое число на простые множители. Даже если такие программы появятся, то можно буде просто брать ещё большие p и q и, соответственно, получать большее n. Таким образом, такой способ шифрования остаётся надёжным даже в нынешнее время, а это значит, что задача выполнена. Однако на этом история шифрования не заканчивается, ведь со временем компьютеры смогут быстро раскладывать на простые множители даже очень большие числа, и тогда придётся придумывать новые способы шифрования.

Это вся информация, которую я хотела Вам рассказать, надеюсь, что эта статья была для Вас интересной. Спасибо за внимание!