Роль численных методов в криптографии и анализе данных - Студенческий научный форум

XVII Международная студенческая научная конференция Студенческий научный форум - 2025

Роль численных методов в криптографии и анализе данных

Тиликина Е.В. 1, Балабан Е.И. 1
1Коломенский институт (филиал) Московского политехнического университета
 Комментарии
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF

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

Численные методы в криптографии

Представьте, что вы отправляете личное сообщение через мессенджер. Вам важно, чтобы его никто не прочитал — кроме того, кому оно предназначено. Вот тут и приходит на помощь криптография. Но это не магия — за надёжным шифрованием стоят серьёзные математические расчёты [1].

1. Генерация простых чисел

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

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

Этот алгоритм шифрования используется повсюду — от банковских транзакций до защиты ваших переписок. Его основа — простые числа. Конечно, не просто числа, а очень огромные. Найти их вручную нет шансов! Поэтому математика выручает.

Например, есть такой алгоритм — Миллера-Рабина. Это как детектор простоты числа: он проверяет, является ли огромное число подходящим для шифрования. Представьте, что этот метод работает даже с числами длиной в сотни цифр! Вот только стопроцентной уверенности он не даёт, но вероятность ошибки настолько мала, что ей можно пренебречь [4].

2. Решение задач дискретного логарифма

Теперь давайте заглянем в мир Диффи—Хеллмана или электронной подписи [1]. Здесь нас ждёт головоломка — задача дискретного логарифма. Дискретное логарифмирование (DLOG) — задача обращения функции g^x в некоторой конечной мультипликативной группе G.

Наиболее часто задачу дискретного логарифмирования рассматривают в мультипликативной группе кольца вычетов или конечного поля, а также в группе точек эллиптической кривой над конечным полем. По сути, это как искать иголку в стоге сена, только этот "стог" состоит из миллионов вариантов. Чтобы задача не превратилась в пытку, математики придумали алгоритмы, которые сокращают поиски. Например, методы на основе быстрых преобразований помогают найти результат без лишнего шума [1].

3. Эллиптические кривые

Эллиптическая кривая — это неособая кубическая кривая на проективной плоскости, задаваемая уравнением 3-й степени с коэффициентами из поля и «точкой на бесконечности». Геометрически это значит, что график не должен иметь острых точек, самопересечений или изолированных точек [5].

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

4. Методы факторизации

И последний пример — факторизация. Представьте, что у вас есть число 391 и вам нужно разложить его на простые множители. Да, 17 × 23. Справились? Теперь представьте число с 200 цифрами. Здесь человек бессилен, а вот такие методы, как решето числового поля, справляются на ура [3].

Общий метод решета числового поля — метод факторизации целых чисел. Является наиболее эффективным алгоритмом факторизации чисел длиной более 110 десятичных знаков.

Суть метода в том, что вместо перебора чисел и проверки, делятся ли их квадраты по модулю n на простые числа из факторной базы, перебираются простые числа из базы и сразу для всех чисел вида x² - n проверяется, делятся ли они на это простое число или его степень.

Именно поэтому стойкость RSA и других шифров измеряется не только временем, но и ресурсами для взлома.

Численные методы в анализе данных

Теперь представьте другую ситуацию. Вы — маркетолог, который хочет узнать, что покупатели ищут перед праздниками. Или вы учёный, который анализирует, как вирус распространяется в популяции. В обоих случаях вы имеете дело с миллионами строк данных. И чтобы найти в этом хаосе закономерности, нужны численные методы [2].

1. Интерполяция и аппроксимация

Допустим, у вас есть данные о продажах за прошлый месяц, но они неравномерные: где-то есть пробелы. Как восстановить картину? В этом поможет интерполяция [7].

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

2. Методы оптимизации

Когда данные у вас есть, вы хотите найти что-то лучшее. Например, как настроить рекламу так, чтобы клиенты с большей вероятностью кликнули на баннер. Здесь вступает в игру оптимизация [2]. Метод градиентного спуска, словно умный навигатор, помогает находить минимумы или максимумы функции, шаг за шагом приближая вас к ответу [9].

3. Линейная алгебра и матрицы

Большинство современных алгоритмов анализа данных — это математика в чистом виде. Например, Google использует сингулярное разложение (SVD), чтобы понять, какие сайты заслуживают быть первыми в результатах поиска [2].

Сингулярное разложение (SVD) — это метод матричной факторизации, который представляет любую матрицу (вещественную или комплексную) в виде произведения трёх матриц:

U — унитарная матрица порядка m.

Σ — матрица размера m × n, на главной диагонали которой лежат неотрицательные числа, называющиеся сингулярными (элементы вне главной диагонали равны нулю).

V* — эрмитово-сопряжённая к V матрица порядка n.

Цель этого разложения — упростить некоторые вычисления, которые будут осуществляться над матрицей. Это похоже на упрощение головоломки: SVD уменьшает размеры данных, оставляя только самое важное.

4. Методы Монте-Карло

А если задача слишком сложная? Например, вы хотите смоделировать, как распределяются вероятности выигрыша в лотерее. Или вам нужно проанализировать финансовые риски. В таких случаях приходят на помощь методы Монте-Карло [6].

Методы Монте-Карло — группа численных методов для изучения случайных процессов. Суть метода заключается в следующем: процесс описывается математической моделью с использованием генератора случайных величин, модель многократно обсчитывается, на основе полученных данных вычисляются вероятностные характеристики рассматриваемого процесса. Это как многократное подбрасывание монетки — вы повторяете процесс тысячи раз и получаете примерный результат.

Когда криптография и анализ данных идут рука об руку

Эти две области пересекаются чаще, чем кажется. Например, представьте, что вы хотите анализировать данные клиентов, но без нарушения их конфиденциальности. Как это сделать? С помощью гомоморфного шифрования [8]. Этот метод позволяет анализировать зашифрованные данные, не раскрывая их содержимого. Например, исследователь может изучать, как распределяются доходы в обществе, не зная конкретных цифр о каждом человеке. Это сложно, но благодаря численным методам возможно.

Заключение

Численные методы — это не просто цифры. Это то, что делает наш мир безопасным и удобным. Они защищают наши деньги в банках, сохраняют конфиденциальность сообщений и помогают находить скрытые закономерности в данных. Сегодня без них мы не могли бы представить ни криптовалюты, ни искусственный интеллект, ни те же самые мессенджеры. В будущем их роль станет ещё больше. Как именно? Время покажет. Но ясно одно: математические методы останутся сердцем технологий.

Список литературы

  1. Стинсон, Д.Р. Криптография: теория и практика. Пер. с англ. — Москва: Техносфера, 2021.

  2. Бак, Дж. Численные методы и приложения в анализе данных. — Boston: Academic Press, 2017.

  3. Ривест, Р., Шамир, А., Адлеман, Л. Алгоритмы RSA и факторизация больших чисел. // Communications of the ACM, 1978.

  4. Миллер, Г., Рабин, М. Простота и сложность чисел: Алгоритм Миллера—Рабина // Journal of Algorithms. 1976.

  5. Криспин, С. Методы эллиптических кривых в современной криптографии. IEEE Spectrum. 2021.

  6. Монте-Карло, С. Принципы статистического моделирования и их применение в данных. Springer, 2017.

  7. Бишоп, К.М. Машинное обучение и интерполяция данных. Пер. с англ. Москва: Диалектика, 2018.

  8. Таненбаум, Э.С., Везерс, К. Криптография и защита информации в XXI веке. Пер. с англ. Санкт-Петербург: Питер, 2020.

  9. Стэнфорд, Р. Оптимизация в анализе данных: от градиентного спуска до современных подходов. Pearson, 2022.

Просмотров работы: 22