RSA и криптография на эллиптических кривых

Кодирование и шифрование лежат в основе современных цифровых коммуникаций. Два наиболее известных метода обеспечения безопасности связи — RSA и криптография на эллиптических кривых (ECC) — основаны на принципах дискретной математики. Эта статья более подробно рассмотрит эти криптографические системы и поможет прояснить, как мы используем математические принципы для шифрования данных, чтобы они оставались в безопасности от любопытных глаз.

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

RSA названа в честь ее разработчиков — Рона Ривеста, Ади Шамира и Леонарда Адлемана, которые представили ее в 1977 году. Это форма криптографии с открытым ключом, которая использует два ключа: открытый ключ для шифрования и закрытый ключ для дешифрования.

Основные принципы RSA

Безопасность RSA зависит от сложности факторизации больших целых чисел. Это работает так:

1. Создание ключей:
   • Выберите два разных простых числа p и q.
   • Рассчитайте n = p * q. Число n используется как модуль для обоих ключей. Его длина, обычно выражаемая в битах, составляет длину ключа.
   • Рассчитайте φ(n) = (p-1)(q-1).
   • Выберите целое число e так, чтобы 1 < e < φ(n) и gcd(e, φ(n)) = 1. Число e — это открытая экспонента.
   • Определите d как d ≡ e -1 (mod φ(n)), что означает, что d — это мультипликативная обратная модульная к e по модулю φ(n).
   Открытый ключ — это (e, n), а закрытый ключ — (d, n).
2. Шифрование:
   • Сообщение M шифруется с помощью открытого ключа получателя: C ≡ M e (mod n), где C — это шифротекст.
3. Дешифрование:
   • Шифротекст C дешифруется с помощью закрытого ключа: M ≡ C d (mod n), возвращая исходное сообщение M.

Иллюстративные примеры

Предположим, мы выберем простые числа p = 61 и q = 53, тогда n = 61 * 53 = 3233.

В результате получаем φ(n) = (61-1)(53-1) = 3120.

Выберите e = 17, которое взаимно просто с 3120.

Чтобы найти d, расширенный алгоритм Евклида дает d = 2753.

Шифрование сообщения

Пусть M = 65 зашифрованное сообщение C:

C = 65 17 mod 3233

С помощью быстрого возведения в степень получаем C = 2790.

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

Чтобы извлечь M:

M = 2790 2753 mod 3233

Снова используя эффективные вычисления, мы возвращаемся к M = 65.

Безопасность RSA

Сила RSA заключается в размере модуля n. Чем больше значение, тем сложнее разделить n на простые составляющие p и q. Эта вычислительная сложность обеспечивает безопасность закрытого ключа. Кроме того, выбор достаточно большой экспоненты e играет роль в обеспечении устойчивости RSA к определенным видам атак.

Криптография на эллиптических кривых (ECC)

Криптография на эллиптических кривых — это современный метод криптографии. Он использует свойства эллиптических кривых над конечными полями. ECC ценится за свою эффективность, так как обеспечивает безопасность, эквивалентную RSA, но с гораздо меньшими размерами ключей.

Понимание эллиптических кривых

Эллиптическая кривая определяется следующим уравнением:

y 2 = x 3 + ax + b

Для криптографических целей мы сосредотачиваемся на эллиптических кривых над конечными полями, особенно полями простого порядка.

y 2 = x 3 + ax + b над конечными полями

Рассмотрим конечное поле F p, где p — простое число. Тогда эллиптическая кривая состоит из точек (x, y), которые удовлетворяют уравнению кривой, включая специальную точку на бесконечности, обозначаемую как O

Операции с точками на эллиптических кривых

Операции на эллиптических кривых управляются правилами сложения точек и скалярного умножения. Эти операции выполняются по модульной арифметике конечных полей.

Сложение чисел

Учитывая две точки P = (x 1 , y 1) и Q = (x 2 , y 2), их сумма R = P + Q = (x 3 , y 3) рассчитывается следующим образом:

• Если P ≠ Q, то используйте:

  λ = (y 2 - y 1) / (x 2 - x 1) mod px 3 = λ 2 - x 1 - x 2 mod py 3 = λ(x 1 - x 3) - y 1 mod p

• Если P = Q, то используйте:

  λ = (3x 1 2 + a) / 2y 1 mod px 3 = λ 2 - 2x 1 mod py 3 = λ(x 1 - x 3) - y 1 mod p

Скалярное умножение

Эта операция важна в ECC. Если k — скаляр, а P — точка на кривой, то kP — это результат, полученный путем сложения P с собой k раз.

Генерация ключей ECC

ECC использует скалярное умножение для генерации ключей. Вот простой план генерации пары ключей на эллиптической кривой:

1. Выберите простое число p и параметры a и b для определения кривой.
2. Выберите базовую точку G на кривой.
3. Выберите случайное целое число d в качестве закрытого ключа.
4. Рассчитайте Q = dG, где Q — это открытый ключ.

Пример генерации открытого ключа ECC

Рассмотрим эллиптическую кривую в F p, где p = 17, a = 2 и b = 2. Выберем G = (5,1).

Предположим, d = 7, тогда мы рассчитываем:

Q = 7G = G + G + G + G + G + G + G

Повторно складывая точки, получаем Q

Безопасность ECC

Безопасность ECC основывается на проблеме дискретного логарифмирования на эллиптической кривой (ECDLP). Учитывая две точки P и kP, определить k вычислительно невозможно. Это похоже на проблему факторизации больших простых чисел в RSA.

Сравнение между RSA и ECC

Хотя RSA и ECC преследуют одну и ту же цель в отношении шифрования, подписи и верификации данных, они делают это с помощью разных математических принципов. Вот некоторые ключевые различия:

• Размер ключа: ECC предлагает большую устойчивость к шифрованию на бит по сравнению с RSA, что означает меньшие ключи для обеспечения того же уровня безопасности.
• Производительность: ECC может быть более эффективной с точки зрения вычислительной стоимости, особенно для мобильных устройств и ограниченных ресурсов.
• Долговечность: Поскольку RSA будет требовать больших размеров ключей для поддержания безопасности в будущем, ECC является более перспективным кандидатом на долгосрочную криптографическую безопасность.

Визуальное представление

Рассмотрим, как эти принципы работают в графическом представлении эллиптической кривой.

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

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

комментарии