Математика для блондинок
Страницы
среда, 13 июня 2012 г.
Математический фокус с номером телефона
Этот математический фокус с номером телефона мне показала брюнетка. Её реакция была довольно эмоциональной: «Вынос мозга! Как такое может быть?!». Действительно, впечатление такое, что вокруг калькулятора пляшут шаманы с бубнами. Вот описание этого математического фокуса с номером телефона. Уточню сразу, что фокус рассчитан на городской семизначный номер телефона.
Ну, как человек опытный, я знаю, что у каждого фокуса есть секрет. Если фокус проделывается на калькуляторе, значит шаманы используют математику, а не ловкость рук. Читал я умные книжки про такие фокусы.
В мусоре на столе я с трудом отыскал не исписанный клочек бумаги, взял ручку и удалился разгадывать великую тайну телефонных шаманов. Я тоже иногда в школу ходил и на уроках математики не только воробьям дули показывал.
Вы спросите, зачем такие сложности? Ведь вместо своего номера телефона можно записать любые цифры. Делаем мы это для того, чтобы наблюдать пляску шаманов в чистом виде, без всяких помех. Помните? Все их телодвижения имеют конкретное числовое выражение. Теперь цифры нашего номера телефона обозначены буквами и не будут отвлекать наше внимание от шаманских чисел.
Теперь несколько слов о тех жертвах невинного обмана, на которых этот фокус рассчитан. Судя по количеству цифр в номере телефона, этот фокус рассчитан на жителей крупных, семизначных городов. Оно и понятно. Именно в таких городах наибольшая концентрация богатых буратино на душу населения. Именно они, как магнитом, притягивают в эти города разного рода проходимцев и шаманов. Как быть жителям более мелких городов, тех, которые в своем историческом развитии не достигли семизначного уровня? Не переживайте! Владея главным секретом этого математического фокуса с номером телефона, вы можете переделать его под любое количество цифр в номере.
Для шестизначного номера достаточно разбить номер на первые две цифры и последние четыре. Работать будет безотказно, даже инструкцию особо изменять не придется. Если же вы хотите блеснуть своей эрудицией, можете разбить шестизначный номер на три и три цифры, при этом инструкцию нужно переделать так, чтобы первые цифры умножались не на 10000, а на 1000. Надеюсь, вы не зря в школу ходили и кое-что ещё знаете. Помните главный принцип этого фокуса? В конце должно появиться столько нулей, сколько цифр будет во второй части телефонного номера.
Мораль сей басни (о математическом фокусе с номером телефона) такова: если хотите докопаться до истины, не стоит тупо следовать установленным правилам. Прежде всего, включайте собственные мозги.
Математические основы кодирования и шифрования
Информационное взаимодействие абонентов в компьютерных и связных сетях подвергается возмущениям, которые приводят к возникновению ошибок и возмущений разного рода. Помимо возникновения ошибок в передаваемых сообщениях возможен несанкционированный доступ к содержанию сообщений нарушителя. Борьба с этими нежелательными явлениями ведется тысячелетиями, но с переменным успехом. Создатели Интернета задумывали его совсем не таким, каким он стал сейчас. О хакерах тогда и не думали.
Основные теоретические проблемы информационного противостояния, задачи по их решению возлагаются на теории кодологии, криптологии и стеганологии, в которых во всем мире интенсивно развиваются направления кодоанализа, криптоанализа и стегоанализа. Практические аспекты также не остаются в стороне, но замечу, что в РФ активность не очень-то высока, сказывается инертность молодых (сам я разменял уже 9-й десяток, но администрация Хабра ограничила возрастной ценз 1950 г). Мое мнение, конечно, ограничено наблюдением потомства (вплоть до правнуков) и общением в интернете, а также с обучаемыми и сотрудниками фирмы, где подрабатываю. СМИ тоже добавляют негатива. Кто из молодежи чуть поумнел, уходят за бугор. Поведение остальных видите сами.
Экскурс по публикациям
Разработка (синтез) технических устройств требует от разработчика определенных знаний, умений ими пользоваться и других навыков подобного рода. Существенная составляющая таких знаний — математическая. Это, как правило, алгебра, дискретная математика, геометрия, физика, математическая логика и др. Здесь в статье будем рассматривать алгебраические структуры не совсем в классическом изложении, но с достаточными уровнем строгости и точностью. Главной моей задачей является обеспечение доступности и понятности изложения вещей, которые я использую в своих текстах и изысканиях.
Например, здесь используется поле расширения GF (2 8 ) и, если обойтись без него, ничего стоящего изложить не удается. Мои критерии оценки просты. Каждый семестр 2, а то и 3 экзамена и зачеты в разных учебных группах. Там слышу и вижу, что я излагал, выносил на практику, и что мне возвращают в ответах по экзаменационным билетам. Очень полезен анализ экзаменационных ответов, вижу, что следовало бы излагать кое-что по-другому, лучше.
А здесь свойства ZN конечного числового кольца вычетов по составному модулю N =pq используются для поиска решения задачи факторизации больших чисел в рамках нового оригинального подхода. Понятно, что в каждой из последующих публикаций переносить часть стандартных математических средств было бы неразумно, посему принято решение собрать все в одном месте и при необходимости адресовать сюда читателей.
Здесь же рассматривается и используется группа точек эллиптической кривой на плоскости. Операция суммирования в группе очень специального вида, вызывающая недоуменные вопросы, типа как это Вам удается складывать точки кривой, даже от членов ГЭК.
Группы
Предварительно введем ряд необходимых определений.
Определение. Конечное множество А-набор, совокупность любых n объектов 
, перечисляемых в любом порядке, но среди которых нет повторяющихся. Множества бывают структурированные, над элементами которых задана одна (или более) операция и отношений и неструктурированные, когда операции не заданы.
Ниже, как напоминание, приводится таблица действий (операций) с конечными дискретными множествами, а на диаграммах для наглядности показаны и непрерывные множества А и В.
Таблица операций с множествами
Определение. Группа — это множество G элементов (любой природы), над которыми задана единственная операция, но она может быть сложением (+) и группа называется аддитивной, ее нейтральный элемент (0) или умножением (◦) — называется мультипликативной, ее нейтральный элемент (1), но как правило, операции эти не обычные арифметические, а специальные. Обозначается группа часто символом (G,◦), среди всех групп важное место отводится симметрическим группам 
перестановок степени n.
Определение.Части элементов группы, сохраняющие свойства и операцию группы называются подгруппами. В сущности это такие же группы, только меньше исходной. Это неформальное определение группы, формальное будет приведено чуть позже.
Примером аддитивной группы является набор слов кода Хемминга (см.здесь). Операция в этой группе 16 порядка — суммирование слов по (mod2). С этой группой выполнялась операция разложения в смежные классы группы из 128 слов по подгруппе кода, а также строилась таблица Кели, элементы группы используются в кодере (базис пространства размерности 4) и декодере. Одним словом этот пример наглядно демонстрирует как может использоваться даже маленькая группа для решения очень важной практической задачи (связь).
Очень важными в теории групп являются симметрические группы подстановок (перестановок). Эта важность определяется теоремой, в которой говорится, что для любой группы, возникающей в произвольной предметной области, существует изоморфная ей симметрическая группа (подгруппа) на перестановках. Тогда исследователю новой открытой группы задача ее изучения упрощается. Почти все свойства изоморфной группы перестановок имеют место и в новой группе.
Начнем с простого примера. Заданы n элементов (обозначим их цифрами 1,2,3. n) и образуем из них перестановки, число которых n! = 1·2·3·. ·n. Ограничимся значением n=3, тогда 3! = 6.
Определение. Порядок группы — число элементов в группе называется ее порядком. В примере число 6 — это порядок группы.
В группе каждый элемент также имеет порядок, который является делителем порядка группы.
Определение. Порядок элемента группы — это наименьший показатель степени элемента в мультипликативной группе (кратности в аддитивной b+b+b+b+. b =nb = 0, порядок =n), при котором он обращается в нейтральный элемент, например (
) 3 =1, порядок ord() = 3.
В симметрической группе операцией является умножение перестановок. Это умножение аналогично матричному умножению, так как каждой перестановке степени n ставится в соответствие квадратная перестановочная матрица размерности n×n, в которой каждая строка и столбец содержат единственную единицу. Ниже это показано для симметрической группы
.
Для удобства работы с группой и ее элементами математиком Кели предложена таблица операций группы (ограниченного размера). В клетке на пересечении строки и столбца ставится результат операции с элементами, которые их обозначают. Результат (как и обозначение строк/столбцов) в таблице представляется десятичными номерами элементов, что экономит место.
Таблица умножения элементов (перестановок) группы
Заполнение 36 клеток таблицы умножения упрощается, если воспользоваться свойствами таблицы Кели.
— Все строки и столбцы содержат элементы всей группы.
— Крайние столбцы лексикографически упорядочены и встречно направлены (1-й сверху/вниз — последний наоборот)
— На главной диагонали таблицы стоят квадраты элементов, если там стоит 1, то элемент ей соответствующий — инволюция; инволюциями в являются 
— Относительно диагоналей матрицы выполняется симметрия положений элементов.
Свойства таблицы позволяют при ее заполнении ограничиться вычислениями только 13 пар элементов (выше они показаны).
Симметрическая группа 
Группа имеет маленький порядок (6) и для иллюстрации свойств не очень удобна. Далее будут приводится примеры с симметрической группой 24 порядка. Все четные перестановки степени n образуют знакопеременную подгруппу в симметрической группе, обозначаемую символом Аn.
Таблица 2 может использоваться для нахождения произведений любой пары элементов или для их целой цепочки, но находятся последовательным умножением результата на следующий элемент. Переставлять местами элементы в произведении нельзя. Операция умножения перестановок не коммутативна, как и умножение матриц. Один элемент при многократном умножении на себя, пока не получится 1, образует циклическую группу из всех промежуточных результатов. Порядок такой циклической подгруппы является порядком порождающего элемента, он должен делить порядок исходной большой группы.
По таблице умножения находятся подгруппы в составе большой группы. Необходимо помнить, что порядок меньшей подгруппы должен делить порядок большей.
Построим циклическую группу с порождающим р14 элементом. Входим в таблицу 2. В строке 14 находим на пересечении с р14 столбцом элемент р24; в строке 24 находим в клетке пересечения с 14 столбцом элемент р11 и наконец в клетке строки 11 на пересечении со столбцом 14 находим элемент р1, т.е. нейтральный элемент 1. Итак, р14·р14·р14·р14 = р1, это элементы подгруппы 4-го порядка, значение которого нацело делит порядок 24:4 = 6. Для нее можно построить таблицу Кели и в ней не будут появляться никакие элементы кроме найденных.В этой подгруппе элементы р14 и р11 имеют 4-й порядок, а р24 второй — это инволюция.
Морфизмы групп
Элементы образа с операцией над ними (+), а в прообразе элементы связаны операцией (◦) умножения. Гомоморфный образ группы есть группа (подгруппа), т.е., если f-гомоморфизм G на G’ и G — группа, то и G’ — группа. Гомоморфизм — обобщение изоморфизма групп: если f — взаимно однозначное гомоморфное отображение G на G’, то оно изоморфно, что обозначается так G≈G’.
Две группы G и G’ с операциями (·) и (*) называются изоморфными, если существует отображение f: G → G’ такое, что (отображение f сохраняет групповую операцию) образа;
Теорема. Пусть Н — нормальная подгруппа группы G и G=G/H. Тогда отображение f группы G на G, заданное формулой f(a) =a является гомоморфизмом. Ядро этого гомоморфизма есть Н. Этот гомоморфизм часто называют естественным (каноническим).
Гомоморфизмы группы по существу исчерпываются каноническими гомоморфизмами.
Выполним разложение группы G 24-го порядка по ее подгруппе H = <1,8, 17,24>в смежные классы и построим для этого разложения факторгруппу по подгруппе Н. С этой целью выпишем в столбцы левые и правые произведения элементов подгруппы Н.
В таблице разложения группы G порядка 24 на классы смежности по подгруппе Н обозначены столбцы л1, л2, л3, л4, л5 имена левых и п1, п2, п3, п4, п5 — правых смежных классов, ведущие представители классов по одному на столбец выписаны в следующей строке.
Средний столбец Н — группа 4-го порядка (ядро гомоморфизма). Столбцы заполняются произведениями ведущих представителей классов на элементы группы Н. После заполнения столбцов выполняется сравнение классов. Если составы левых и правых классов совпадают, то говорят просто о классах смежности и обозначают Н = К0, К1, К2, К3, К4, К5. При этом подгруппа Н называется нормальной. Ведущим представителем очередного класса при заполнении таблицы выбирается наименьший элемент G, из не вошедших в уже построенные классы.
Полученные классы смежности далее рассматриваются как элементы новой группы, называемой факторгруппой группы G по подгруппе Н (обозначается факторгруппа G =G/H). Операцией в этой новой группе является умножение классов: для каждой пары классов, например, К3×К5 = К2 строится таблица 4×4, в которой строки помечаются элементами первого сомножителя, а столбцы — второго. Далее выполняют умножение как в группе G. Результат такого умножения дает 16 элементов, но все они принадлежат одному классу, в нашем случае классу К2.
Кроме отображений изоморфизмов гомоморфизмами являются эндоморфизмы и автоморфизмы. Гомоморфизм группы G в себя называется эндоморфизмом, а изоморфизм группы G на себя- автоморфизмом. Эти понятия сопоставимы с понятиями отображений неструктурированных множеств инъекцией, сюръекцией и биекцией.
Коммутант
Группа G называется разрешимой, если цепочка G ⊇ G’ ⊇ G» ⊇… ⊇ G (i) ⊇. где каждая подгруппа G (i) является коммутантом предыдущей, обрывается после конечного числа шагов на единичной подгруппе, например, G (е) = 1.
В таблице 4 знакопеременная подгруппа G’ =А4 порядка 12 — нормальная, из G = порядка 24, так как левый и правый смежные классы по этой подгруппе совпадают (классы это одно и тоже дополнение до полной группы ). Таблица 4 при этом сворачивается в меньшую 4×4 таблицу (коммутант), содержащую элементы G» = <1,8,17,24>новой подгруппы, коммутант которой равен 1. Таблица 4 иллюстрирует разрешимость группы .
Заключение
В статье рассмотрены некоторые основные положения теории групп, которые часто используются в публикациях технического (не теоретико-математического) характера. Понимание текста таких публикаций во многом определяется владением математическим инструментарием.
Для группы приводится пример и техника гомоморфного отображения её в факторгруппу.
Числовые примеры призваны служить обеспечению доступности излагаемого материала и в большой мере помогают его пониманию и усвоению, при внимательном их разборе или даже повторении с карандашом в руках. Что в классических руководствах просто отсутствует. Часто объясняют это экономией места и времени.
Ожидаю реакции читателей, по которой станет понятно, продолжать ли в этом стиле или нет.
Математический гений в криптографии: от сцитала до RSA
Красота математики в современном шифровании выражается в том, что когда у вас есть зашифрованное сообщение и открытый ключ, которым его шифровали, на расшифровку современными вычислительными мощностями может уйти бесконечность. При этом расшифровка со вторым (секретным) ключом пройдет практически мгновенно. Но эта революция произошла относительно недавно, а до этого столетиями использовали другие принципы.
Под катом несколько исторических примеров систем шифрования, а также математические принципы, заложенные в современных алгоритмах с открытым и закрытым ключом. А поскольку все гениальное просто, в статье не будет сложных формул и чрезмерного занудства.
Этот пост — адаптация лекции Евгения Бережного, доктора физико-математических наук и профессора математического факультета ярославского Демидовского университета, которая прошла в Точке кипения ЯрГУ.
Давайте на примерах рассмотрим общие принципы криптографии, существовавшие до эпохи вычислительных машин.
Шифрование в древности: несколько примеров
Натан Ротшильд когда-то сказал легендарную фразу, что тот, кто владеет информацией — владеет миром.
И хотя с тех пор никто нам внятно так и не объяснил, зачем нужно этим миром владеть, информация в цене только растет.
Когда у человека появились ценные сведения, возникла потребность в ограничении доступа к ним. Это означает, что одна группа людей должна понимать сообщение, а для другой группы эта информация должна быть закрытой.
Первые попытки закрыть информацию были, по теперешним меркам, наивно-примитивны: часть информации просто писали на другом языке.
Например, вместо греческого языка текст писали на латинском. Это делали для той части греков, которые не знали латынь.
Пример текста диалога Платона и Евтифрона на греческом и латинском языках под редакцией Роберта Этьена (репринт 1578 года)
Современная криптография работает по похожему принципу — изобретается некий «язык», который недоступен основной массе.
Сцитала — первый механический шифр
Одна из первых криптографических систем и первых попыток изобрести свой секретный язык — шифросистема сцитала (другое название — скитала).
Главная деталь такой системы — стержень или конус определенного диаметра. На него наматывали длинную полоску бумаги, на витках которой записывали текст. Затем бумагу снимали и отправляли, скажем, в другой город, где получатель имел цилиндр или конус аналогичной формы. Намотав такую бумагу на такой стержень, человек мог прочитать послание.
Чтобы такая система работала, необходимо, чтобы и на передаче, и на приёме для восстановления информации использовали один и тот же цилиндр. Это был один из самых первых известных нам механических шифров. И, если говорить современным языком, он был не очень криптостойким.
Шифр Цезаря
Следующие шифросистемы были более хитрыми. Например, стоит упомянуть так называемый «шифр Цезаря». Суть шифра состояла в подмене значений. Предположим, у нас есть алфавит, неважно какой — латинский, русский, цифровой. И есть цифры — от единицы до пяти. Каждой цифре соответствует другая цифра, например, единице — тройка, двойке — пятерка, тройке — четверка, четверке — двойка, пятерке — единица. Таким образом, если необходимо было передать сообщение в виде последовательности цифр 1, 2, 3, 4, 5, информацию кодируют как 3, 5, 4, 2, 1. Для восстановления исходной информации на приеме используют табличку с теми же соответствиями символов.
Подмену символов делали разными способами. Например, одному символу могли соответствовать сразу несколько символов алфавита. Для упрощения дешифровки использовали сдвиг алфавита на заданное число символов. Все эти типы шифров — вариации шифра Цезаря. В каждом таком случае для шифрования информации на передаче и дешифровки на приеме использовали один и тот же ключ — табличку с сопоставленными исходными и подменяемыми символами.
Поворотная решетка: надежный механический шифр
Совершенствуя навыки тайнописи, человек создавал все более экзотические шифры. Один из них — поворотная решетка. Как и в случае со сциталой, это механический шифр. Для него необходим специальный инструмент: некий квадратный трафарет с вырезанными отверстиями-окошечками. В этих отверстиях писали текст сообщения. Далее решетку поворачивали на 90 градусов относительно центра, и отверстия попадали на чистые поля бумаги, где можно было продолжать текст. Потом решётку поворачивали еще два раза. Когда текст сообщения заканчивался, оставшиеся пустые места заполняли случайными буквами.
В результате написанный текст образовывал некий массив бессвязных символов. Для восстановления информации, то есть на приеме, использовали аналогичную поворотную решетку с тем же набором отверстий. Криптостойкость такой системы зависила от числа ячеек в решетке. Чем больше окошечек, тем выше стойкость шифрования поворотной решеткой.
Обычно под криптостойкостью понимают количество идентичных шифров, похожих на данный. Если вернуться к шифру Цезаря и нашему примеру с цифрами от единицы до пяти, то всего количество перестановок будет 5!. Поэтому криптостойкость нашего примера шифрования будет 1/5!. Это, конечно, не очень большое число, но если у нас 32 элемента в алфавите, то вероятность того, что мы угадаем шифр, уже будет 1/32!.
По мере развития криптографии появлялось все больше и больше «секретов», в то время как главный принцип — замещения — оставался неизменным.
Криптографические приемы нашли место во многих литературных произведениях, особенно в детективах. В рассказе «Пляшущие человечки» Конан Дойл описал шифр, где использовали принцип замещения — каждой букве присваивали свой рисунок человечка. Шерлок Холмс блестяще справился с разгадкой этого шифра, используя простую логику и принципы построения фраз.
Оригинальный шифр из книги Артура Конан Дойла. Человечки с флагами работают пробелами
Переход в эпоху вычислительной техники и создание несимметричного шифра
Промышленные криптосистемы появились позже, когда возникла необходимость скрывать большие объемы данных и ограничивать доступ к информации государственной важности. Во вторую мировую войну наибольшую известность обрела немецкая шифровальная машина «Энигма», историю которой все знают по фильмам «U-571», «Игра в имитацию» и других. В легендарной немецкой шифровальной машине тоже использовали шифр, основанный на шифре Цезаря, многократно усложненный.
Подробнее об алгоритме работе «Энигмы» можно узнать из этого ролика (eng.)
С появлением электроники криптографические системы заметно изменились. Метод закрытия информации стал иным: передаваемое сообщение в виде последовательного набора цифр 1, 2, 3, 4, 5 складывали с так называемой псевдослучайной последовательностью, генерируемой вычислительными машинами. На приеме для получения исходного сообщения эту избыточную информацию вычитали с помощью тех же вычислительных машин.
Еще лет пятьдесят назад подобные способы закрытия данных считали относительно надежными: их, например, широко использовали вооруженные силы. Ключевой момент таких систем шифрования в том, что и на передаче сообщения, и на приеме используют, грубо говоря, одну «перфокарту», которая содержит псевдослучайную последовательность — один пароль.
RSA — имея зашифрованное сообщение и шифровальный ключ, расшифровать практически нереально
К середине восьмидесятых годов прошлого века никаких новых методов закрытия информации не появилось, и многие сочли криптографию устаревшей наукой.
Даже в опубликованной в 1988 году советской брошюре по криптографии было написано, что эта тема себя исчерпала и не может содержать ничего нового.
Автор брошюры ошибался. В это же время в Массачусетском технологическом институте трое сотрудников — Рональд Ривест, Ади Шамир и Леонард Адлеман — придумали новую шифросистему с высокой криптостойкостью, которая базировалась на принципах, отличных от тех, что использовались ранее.
Ади Шамир, Рональд Ривест и Леонард Адлеман — создатели алгоритма несимметричного шифрования
Для взлома этой системы на то время понадобилось бы примерно 10 тысяч лет.
До ее изобретения все шифровальные методы основывались на целочисленной арифметике и использовали все множество целых чисел. Уникальность нового метода в том, что он использовал также и арифметику остатков.
Предположим, у нас есть произвольное целое число n. И давайте возьмем m=5. Произвольное число n можно поделить на пять, в результате чего получится частное плюс остаток. Остаток может принимать значение 0, 1, 2, 3, 4. Оказывается, эти остатки могут вести себя как обычные числа. Запишем две таблицы — таблицу сложения для остатков и таблицу умножения для остатков.
Таблицы остатков от сложения и деления (плюс в карму тому, кто первый найдет у лектора ошибку, сделанную по невнимательности)
Имея на руках такие таблицы, можно опять получить новую арифметику. Объекты с такой новой арифметикой обозначаются как Z(m). Остаток от деления числа a на m записывается следующим образом: a mod m = b. Мы записали таблицы для числа пять — Z(5). Аналогичным образом можно записать такие таблицы для любого натурального числа Z(m).
Пример
Предположим, мы имеем исходное сообщение, которое необходимо закрыть — x. Нам необходимо придумать некоторое число m — основание для создания Z(m), а также придумать число a. Эти два числа находятся в открытом доступе, известны всем. Кроме того известно, что m=m0 × m1, где m1 и m0 — простые числа (которые делятся только на себя и единицу).
Далее согласно алгоритму шифрования создаем уравнение: x a mod m = b, где b (остаток от деления x a на m) — наше зашифрованное сообщение. Таким образом, a,b,m — известны, и необходимо вычислить x. Для решения этой задачи нужно найти разложение m = m0 × m1. Как только m1и m0 будут найдены, расшифровать сообщение можно будет достаточно быстро через специальную систему уравнений.
Изобретатели нового шифра зашифровали фразу, где в качестве a было взято число 1007, m0 и m1 содержали примерно по 65 знаков в десятичной системе. Математики озвучили публичные а, зашифрованную фразу и m, предлагая всем желающим расшифровать секретную фразу. Также был опубликован алгоритм, как взломать эту систему. Вся криптостойкость определялась разложением m = m0 × m1.
История длилась 17 лет, пока с появлением интернета у пользователей не появилась возможность задействовать сеть компьютеров с распределенными вычислениями. За 220 дней около 1600 компьютеров смогли восстановить исходную информацию, разложив m на два простых числа. Это событие показало, что криптография как наука жива.
Также это доказало непостижимую эффективность математики при решении реальных задач. Сама же система получила название RSA — по именам своих создателей.
Практическое применение криптографии
С появлением интернета возник целый класс задач, для решения которых снова и снова приходится прибегать к математике. В частности, речь идет об удаленных и защищенных действиях. Используя интернет и инструменты для закрытия информации можно, скажем, открыть счет в банке, провести платеж без личного присутствия человека. Требования к таким криптосистемам отличаются от классических, присутствовавших в жизни человека раньше.
Если при зарождении криптографии на передаче и на приеме была одна и та же шифросистема — поворотная решетка, сцитала и т. д., — то теперь ситуация кардинально иная. На передаче и приеме в новых криптосистемах применяют совершенно разные методы обработки информации.
На передаче используют простые алгоритмы, чтобы закрыть информацию (в нашем случае — возвести x в степень a), а на приеме происходит быстрое восстановление (если вам заранее известно разложение m на m0 и m1). Получается несимметричная система шифрования, которая удобна и надежна.
По сравнению с симметричными системами шифрования, предложенный вариант не годится для передачи данных сверхбольшого объема ввиду ресурсоемкости операций. Зато в случае несимметричного шифра отпадает необходимость в передаче секретного ключа, что весьма удобно, если необходимо использовать сеансовый пароль.
Новые принципы криптографии привели к созданию цифровой подписи — механизму, который подтверждает аутентификацию пользователя.
Им можно подписывать документы и заверять свою личность — например, в финансовых документах.
Наш ГОСТ и американский стандарт цифровой подписи основаны на эллиптических кривых и решении логарифмических уравнений. Математика, которую там используют, очень сложна, и сегодня мы опустим эти математические выкладки.
Иногда криптографию применяют в неожиданных сферах, где требуется подтверждение достоверности информации. Например, если вы, расслабившись в конце рабочего дня, сядете играть в карты, то вы можете быть уверены в честной игре, даже не имея на руках реальных карт. Скрытую информацию с помощью описанных алгоритмов всегда можно восстановить и проверить. Тем же способом же можно организовывать честное голосование без необходимости физического присутствия человека на избирательном участке.
Математика позволяет решать самые разные и сложные задачи обеспечения информационной безопасности. И по мере развития вычислительных систем алгоритмы будут только усложняться.