Формирование системы RSA

Теорема Эйлера

Определение

Функция Эйлера определяется равенством

.

Иными словами, — это число целых чисел между 0 и, которые взаимно просты с.

Также применение в криптографии нашла теорема Эйлера.

Пусть и — натуральные числа. Тогда

(9.1)

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

(9.2)

Это можно проверить с помощью функций GCD и EulerPhi пакета "Mathematica".

n=1999; a=1234;

GCD[a, n]

ph = EulerPhi[n]

PowerMod[a, ph, n]

|| 1

|| 1998

|| 1

□ Шаг 1; вычисление модуля

Каждый пользователь системы выбирает два простых числа и. В первоначальном предложении была рекомендована длина этих чисел порядка 100 (десятичных) цифр.

Пусть. Из равенства (9.2) следует, что

(9.3)

Это можно увидеть и непосредственно. Из целых чисел от 1 до все числа взаимно просты с, кроме чисел, кратных (именно) и чисел, кратных (именно). При подсчете нужно лишь осознать, что число отбрасывалось слишком часто.

Пример 9.1 (часть 1)

Чтобы пример был "управляемым", участник Боб выбирает простые числа разумно малыми. Он использует функции Prime и EulerPhi из пакета "Mathematica".

рВ = Prime[1200]

qB = Prime[1250]

nВ = рВ * qB

phiB = EulerPhi[nВ]

|| 9733

|| 10177

|| 99052741

|| 99032832

□ Шаг 2: Вычисление показателейи

Пользователь выбирает такое натуральное число, что, т.е. взаимно простое. Затем он вычисляет единственное, удовлетворяющее условиям

(9.4)

Условие (9.4) можно записать иначе для некоего целого:

(9.4.1)

К примеру, может использовать расширенный алгоритм Эвклида, чтобы найти менее чем за операций, где.

Пример 9.1 (часть 2)

Случайный выбор числа и вычисление можно выполнить с помощью функций Random, While и ExtendedGCD пакета "Mathematica"

eB = Random[Integer, {1, nВ}];

While[GCD[eB, phiB]!= 1, eB = Random[Integer, {1, nВ}]];

eB

{g, {a, b}} = ExtendedGCD[eB, phiB]

eB*a + phiB*b == g

if[a < 0, dB = b, dB = a];

|| 81119923

|| {1, {17089915, -13998717}}

Таким образом, Боб имеет и. Это можно проверить, вычисляя функцию Mod:

dB = 17089915;

Mod[eB*dB,phiB]

|| 1

□ Шаг 3: публикацияи

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

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

Обычно в литературе

· пара называется публичным ключом, а

· пара (или одно число) ‑ секретным ключом, пользователя.

Дата добавления: 2013-12-12