Рабочая программа по дисциплине «Теоретико-числовые методы в криптографии» для студентов специальности «Компьютерная безопасность» ТюмГУ, и задания для самостоятельного выполнения с ответами к ним

§6. Первообразные корни и индексы. Порождающий элемент и дискретный логарифм.

В этом параграфе рассмотрены теоретико-числовые основы, ведущие к задачам дискретного логарифмирования над конечным полем, а также приведены некоторые приложения теории конечных групп к таким вопросам как тесты на простоту и построение простых чисел.

1. 6.1. Основные понятия и теоремы.

При (a,m)=1 существуют положительные γ с условием a^γ≡1(mod m). Наименьшее из таких γ называется показатель, которому a принадлежит по модулю m.

В том, что такие γ существуют, можно убедиться, вспомнив теорему Эйлера (γ=φ(m)).

Возвращаясь к основам общей алгебры, в частности, к теории конечных групп, можно сказать, что показатель, которому которому a принадлежит по модулю m есть то же самое, что порядок элемента a в конечной мультипликативной группе m, · mod m>. Далее будем обозначать его O_m(a).

Поскольку дальнейшие построения будут тесно связаны с группой m, · mod m>, то на протяжении текущего параграфа для краткости будем обозначать эту группу как U_m.

Докажем несколько важных теорем, описывающих свойства O_m(a):

Теорема 1.

Числа 1=a⁰, a¹, a², … , несравнимы между собой по модулю m.

Доказательство:

Действительно, из того, что a^l≡a^k(mod m), 0 ≤ k < l < O_m(a) следовало бы, что a^l—k≡1(mod m), 0 < k—l < O_m(a), что противоречит определению O_m(a).

 

Теорема 2.

Пусть δ= O_m(a). Тогда a^γ≡a^β (mod m) γ≡β(mod δ).

Доказательство:

Из теоремы 1 следует, что если a^γ≡a^β (mod m) , то γ≡β(mod δ).

Пусть теперь γ≡β(mod δ) Тогда, по теореме делимости, найдутся такие числа q, w, r: 0 ≤ r < δ, что γ=δ·q+r, β=δ·w+r. Тогда из того, что a^δ≡1(mod m) следует, что

a^γ≡a^δq+r≡(a^q)^δa^r≡a^r(mod m)

a^β≡a^δw+r≡(a^w)^δa^r≡a^r(mod m)

Что и требовалось доказать.

 

Теорема 3.

O_m(a)\φ(m).

Доказательство:

Следует из Теоремы 2 при β=0 и из теоремы Эйлера (a^φ(m)≡1(mod m)).

 

Последняя теорема также может быть доказана как следствие из теоремы Лагранжа (порядок любого элемента в группе делит порядок группы) применительно к группе U_m.

Числа, принадлежащие показателю φ(m) (если они существуют), называются первообразными корнями по модулю m.

Если a – первообразный корень по модулю m, то согласно Теореме 1, числа 1=a⁰, a¹, a², … , a^φ(m)-1 несравнимы между собой по модулю m, а раз их φ(m) штук, то они образуют приведенную систему вычетов по модулю m. Тогда a есть ни что иное как порождающий элемент группы U_m.

Утверждение

Если существует первообразный корень по модулю m, то мультипликативная группа U_m является циклической группой.

Доказательство очевидным образом следует из вышесказанного.

Пример 1.

Рассмотрим группу U₁₁=<{1,2,3,4,5,6,7,8,9,10},· mod m>. Порядок этой группы равен φ(11)=10. Найдем порядки всех элементов в этой группе и отыщем порождающий элемент этой группы, если он существует. Для краткости вместо a^b mod 11 будем писать просто a^b.

1: 1⁰=1, 1¹=1. O₁₁(1)=1.

2: 2⁰=1, 2¹=2, 2²=4, 2³=8, 2⁴=5, 2⁵=10, 2⁶=9, 2⁷=7, 2⁸=3, 2⁹=6, 2¹⁰=1. O₁₁(2)=10.

3: 3⁰=1, 3¹=3, 3²=9, 3³=5, 3⁴=4, 3⁵=1. O₁₁(3)=5.

4: 4⁰=1, 4¹=4, 4²=5, 4³=9, 4⁴=3, 4⁵=1. O₁₁(4)=5.

5: 5⁰=1, 5¹=5, 5²=3, 5³=4, 5⁴=9, 5⁵=1. O₁₁(5)=5.

6: 6⁰=1, 6¹=6, 6²=3, 6³=7, 6⁴=9, 6⁵=10, 6⁶=5, 6⁷=8, 6⁸=4, 6⁹=2, 6¹⁰=1. O₁₁(6)=10.

7: 7⁰=1, 7¹=7, 7²=5, 7³=2, 7⁴=3, 7⁵=10, 7⁶=4, 7⁷=6, 7⁸=9, 7⁹=8, 7¹⁰=1. O₁₁(7)=10.

8: 8⁰=1, 8¹=8, 8²=9, 8³=6, 8⁴=4, 8⁵=10, 8⁶=3, 8⁷=2, 8⁸=5, 8⁹=7, 8¹⁰=1. O₁₁(8)=10.

9: 9⁰=1, 9¹=9, 9²=4, 9³=3, 9⁴=5, 9⁵=1. O₁₁(9)=5.

10: 10⁰=1, 10¹=10, 10²=1. O₁₁(10)=2.

Действительно, порядки всех элементов делят порядок группы. При этом в группе U₁₁ нашлись порождающие элементы, причем не один, а четыре. Это 2, 6, 7 и 8. Однако не во всех группах U_m существуют порождающие элементы, убедимся в этом на следующем примере:

Пример 2.

Рассмотрим группу U₈=<{1,3,5,7},· mod 8>, φ(8)=4.

1: 1⁰=1, 1¹=1. O₈(1)=1.

3: 3⁰=1, 3¹=3, 3²=1. O₈(3)=2.

5: 5⁰=1, 5¹=5, 5²=1. O₈(5)=2.

7: 7⁰=1, 7¹=7, 7²=1. O₈(7)=2.

Итак, в группе U₈ нет порождающего элемента.

Возникает вопрос – в каких группах U_m порождающий элемент существует, а в каких – нет, и как найти порождающий элемент? На этот вопрос ответим в следующих пунктах данного параграфа.

1. 6.2. Существование первообразных корней по модулю p.

Лемма 1.

O_m(x)=ab O_m(x^a)=b.
Лемма 2.

O_m(x)=a, O_m(y)=b, (a,b)=1 O_m(xy)=ab.

Доказательства этих лемм не представляют принципиальной сложности, поэтому предоставляются читателю в качестве упражнения.
Теорема 1 (Критерий Люка).

В группе U_p , p – простое число, существуют порождающие элементы.

Доказательство:

Действительно, пусть δ₁, δ₂, … , δ_r – все различные показатели, которым по модулю p принадлежат числа 1,2,…,p—1 (то есть порядки этих чисел в U_p). Пусть τ=НОК(δ₁,δ₂,… ,δ_r), и τ= - каноническое разложение. Каждый множитель этого разложения делит хотя бы одно из чисел δ₁,…,δ_r. Поэтому можем представить одно из таких чисел как δ_j=a . Пусть ξ_j – одно из чисел ряда 1, 2, … , p—1: O_p(ξ_j)=δ_j.

Тогда, согласно Лемме 1, O_p(η)= , где η= .

Согласно Лемме 2, O_p(g)=τ= , где g=η₁η₂…η_k.

Поэтому, согласно Теореме 3, п.1, τ\(p—1).

Но поскольку числа δ₁, δ₂, … , δ_r делят τ, то любое из чисел ряда 1, 2, … , p—1 является решением сравнения x^τ≡1(mod p), согласно Теореме 2, п.1.

Пользуясь Теоремой 1, §4, п.4, получаем p—1≤τ. Но τ как порядок элемента g не может быть больше, чем p—1, поэтому p—1=τ, а значит g – первообразный корень, или порождающий элемент группы U_p .

 

1. 6.3. Первообразные корни по модулям p^α, 2p^α.

Теорема (о существовании первообразного корня по модулю p^α)

Пусть g – первообразный корень по модулю p, тогда существуют такое число t, что u= не делится на p, и тогда g+pt – первообразный корень по модулю p^α α>1.

Замечание

Число u, заданное условием, является целым в силу теоремы Ферма. Действительно, поскольку g U_p, то (g,p)=1 (g+pt,p)=1 по теореме Ферма, (g+pt)^p—1≡1(mod p) p\((g+pt)^p—1 –1).

Доказательство:

Имеем:

g^p—1=1+pT₀

(g+pt)^p—1=1+p(T₀—g^p—2t+pT)=1+pu *

где если t пробегает Z_p, то и u пробегает Z_p (полную систему вычетов по модулю р). Поэтому существует такое t Z_p, для которого u не делится на p. При таком t из (*) получаем:

(g+pt)^p(p—1)=(1+pu)^p=1+p²u₂



………………………… **



где все u_i, i=2,3,…α—1 не делятся на р.

Пусть . Тогда (g+pt)^δ≡1(mod p^α), откуда g^δ≡1(mod p) (р—1)\δ , и δ\φ(р^α)=р^α—1(р—1) . Тогда δ имеет вид δ=р^r—1(р—1), где 1≤ r ≤ α.

Но (*) и (**) показывают, что сравнение верно при r = α и неверно при r < α, то согласно Теореме 3 п.1., δ=р^α—1(р—1) =φ(р^α), и (g+pt) – первообразный корень по модулю р^α.

 

Теорема 2.

Пусть g – первообразный корень по модулю р^α, α≥1. Нечетное g₀ из чисел g, g+р^α будет первообразным корнем по модулю 2р^α .

Доказательство:

Заметим, что g+р^α будет являться первообразным корнем по модулю р^α, а также φ(р^α)=φ(2р^α)=с. Нетрудно проверить, что сравнения g₀^r≡1(mod р^α) и g₀^r≡1(mod 2р^α) могут выполняться лишь одновременно. Первое сравнение выполняется при r=c и не выполняется при r<c (так как g₀ – первообразный корень по модулю р^α), следовательно второе сравнение верно при r=c и неверно при r<c. Значит g₀ – первообразный корень по модулю 2р^α.

 

Доказанные теоремы вкупе с теоремой о существовании первообразных корней по модулю p позволяют сделать следующий

Вывод: Существуют первообразные корни по модулям р^α, 2р^α для всех α. Если известен первообразный корень по модулю р, то, пользуясь Теоремами 1 и 2 настоящего пункта, можно найти первообразный корень по модулям р^α, 2р^α.

Пример.

p=71, наименьший первообразный корень по модулю 71 есть 7.

Найти первообразный корень по модулю 71^α и 2·71^α для всех α.

Согласно Теореме 1, нужно найти такое t, чтобы (g+pt)^p—1—1 0(modp²).

Будем перебирать t:

t=0. g+pt=g=7.

7⁷⁰—1 mod 5041 = (7¹⁰)⁷ –1 mod 5041 = 2814⁷—1 mod 5041 =

= (2814²)³ ·2814—1 mod 5041 = 4226²·4226·2814—1 mod 5041=

= 3854·4226·2814 –1 mod 5041 = 1562 ≠ 0.

Итак, 7 – первообразный корень по модулю 71^α для всех α.

Поскольку 7 – нечетное число, то, согласно Теореме 2, 7 - первообразный корень по модулю 2·71^α для всех α.
Вообще говоря, нам повезло, первое же испытанное число t подошло. В другом случае, возможно, пришлось бы перебирать несколько t, прежде чем отыскали бы первообразный корень.

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

1. 6.4. Нахождение первообразных корней по простому модулю.

В настоящем пункте будем рассматривать число n, причем n—1= * - каноническое разложение на простые сомножители.

Теорема

O_n(a)=n—1 1) a^n—1≡1(mod n);

2) , 1(mod n).

Доказательство:

Пусть O_n(a)=n—1. Тогда (1) выполняется в силу определения порядка элемента в группе. Кроме того, , 1 ≤ < n—1= O_n(a), откуда в силу определения порядка элемента, выполняется (2).

Пусть теперь выполнены (1) и (2). Покажем, что O_n(a)=n—1.

В силу (1), O_n(a)\(n—1). В силу (2), O_n(a) не делит . Значит, O_n(a)=n—1.

 

Результатами только что доказанной теоремы можно пользоваться для нахождения порождающего элемента группы U_p, причем проверять стоит только второй пункт, так как первый для простого модуля выполняется автоматически согласно теореме Ферма. Кроме того, можно вывести правило: если a₁, a₂ не являются порождающими элементами группы U_p, то a₁a₂ также не является порождающим элементом U_p. Отсюда делаем вывод о том, что наименьший порождающий элемент группы U_p – простое число.

Пример

p=71. p—1=70=2·5·7.

Для того чтобы a являлся порождающим элементом, необходимо и достаточно, чтобы выполнялись условия: a¹⁰ 1(mod n), a¹⁴ 1(mod n), a³⁵ 1(mod n).

Будем испытывать числа из U₇₁. Вместо a^b mod 71 для краткости будем писать a^b.

2: 2¹⁰ =30, 2¹⁴ =54, 2³⁵=1. 2 не является порождающим элементом.

3: 3¹⁰ =48, 3¹⁴ =54, 3³⁵=1. 3 не является порождающим элементом.

5: 5¹⁰ = 1. 5 не является порождающим элементом.

7: 7¹⁰ =45, 7¹⁴ =54, 7³⁵=70. 7 – порождающий элемент.

Итак, наименьший порождающий элемент группы U₇₁ (или первообразный корень по модулю 71) есть 7.

1. 6.5. Существование и количество первообразных корней.

Первообразные корни существуют не для всякого модуля. Действительно, как было показано в Примере 2 п.1, не существует первообразных корней по модулю 8.
Теорема 1

Первообразные корни по модулю m существуют m=2, 4, p^α или 2p^α, где p – простое нечетное число.
Теорема 2

Количество первообразных корней по модулю m, если они существуют, есть φ(φ(m)).
Пример:

Определить количество первообразных корней по модулю 10.

10 = 2·5=2р. Первообразные корни существуют. Найдем их количество.

φ(φ(10))=φ(4)=2.

Проверим результат. U₁₀={1, 3, 7, 9}

O₁₀(1)=1;

3²=9, 3³=7, 3⁴=1. O₁₀(3)=4=φ(10). 3 – первообразный корень.

7²=9, 7³=3, 7⁴=1. O₁₀(7)=4=φ(10). 7 – первообразный корень.

9²=1. O₁₀(9)=2.

Действительно, нашлись два первообразных корня по модулю 10.
Теорема 3

Пусть с=φ(m), q₁, q₂, … , q_k – различные простые делители с. Тогда g: (g,m)=1 – первообразный корень по модулю m не выполняется ни одно из сравнений , i=1,2,…,k.

■

Теорема, доказанная в предыдущем пункте, является частным случаем данной теоремы при простом n.

1. 6.6. Дискретные логарифмы.

Если g – первообразный корень по модулю m (порождающий элемент U_m), то, если γ пробегает полную систему вычетов по модулю φ(m), то g^γ пробегает приведенную систему вычетов по модулю m.

Для чисел a: (a,m)=1 введем понятие об индексе, или о дискретном логарифме.

Если a≡g^γ (mod m), то γ называется индексом, или дискретным логарифмом числа а по основанию g по модулю m.

В теории чисел принято употреблять слово «индекс» и писать γ=ind_ga, но в криптографии применяют сочетание «дискретный логарифм» и пишут γ=log_ga. Поскольку на протяжении настоящего пособия не раз встретится упоминание о так называемой задаче дискретного логарифмирования, будем употреблять последний вариант названия и написания. Тем более, что дискретные логарифмы обладают некоторыми свойствами логарифмов непрерывных:

Свойство 1: Дискретный логарифм разнозначен в полной системе вычетов по модулю φ(m).

Свойство 2: log_gab…h≡log_ga+log_gb+…+log_gh (mod φ(m)).

Свойство 3: log_gaⁿ≡nlog_ga(mod φ(m)).

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

1. 6.7. Проблема Диффи-Хеллмана.

Пусть даны простое число р и g - первообразный корень по модулю р. Существует полиномиальный алгоритм возведения числа в степень по любому модулю, поэтому задача вычисления x=g^y mod p считается легкой задачей. Вычисление же обратной функции y=log_gx mod (p—1) считают сложной задачей, поскольку на данный момент не найдено полиномиальных алгоритмов ее решения. Впрочем, не доказано и принципиальной невозможности построить такой алгоритм.

Проблема Диффи-Хеллмана – это формализация проблемы дискретного логарифмирования. Звучит она следующим образом:

Пусть известны p, α, δ, γ, где p – простое число, α – порождающий элемент группы U_p, δ,γ U_p.

Требуется найти: mod p.

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

1. 6.8. Условная стойкость шифра Эль Гамаля.

Шифр ElGamal – симметричный шифр, основанный на теоретико-числовой проблематике. Напомним его конструкцию.

Параметры системы: p – простое число, α– порождающий элемент группы U_p;

Закрытый ключ для расшифрования: a – целое число, 1 ≤ a < p—1;

Открытый ключ для шифрования: β = α^a mod p.

Пусть имеется открытый тест x U_p. Для шифрования берут случайное число k Z_p—1 и вычисляются y₁=α^k mod p, y₂=xβ^k mod p. Затем пара (y₁,y₂) пересылается обладателю секретного ключа, а k уничтожается.

Для расшифрования необходимо вычислить x=y₂(y₁^a)^-1mod p.

Действительно, в результате расшифрования получим открытый текст:

y₂(y₁^a)^-1mod p=xβ^k(α^ka) ^-1 mod p= xα^ak(α^ka) ^-1mod p=xα⁰ mod p=x.

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

Теорема

Проблема дешифрования для шифра ElGamal и проблема Диффи-Хеллмана вычислительно эквивалентны.

Доказательство:

Действительно, пусть A есть алгоритм решения проблемы Диффи-Хеллмана,

A(p, α, δ, γ)= mod p.

Тогда дешифрование для шифра ElGamal осуществляется следующим образом:

x=y₂A(p, α, y₁, β)^-1

(поскольку A(p, α, y₁, β)= A(p, α, α^k, α^a)= mod p=α^ak mod p=β mod p).

Обратно, пусть B есть алгоритм дешифрования для шифра ElGamal, то есть

B(p, α, β, y₁, y₂)=x=y₂(y₁ )^-1 mod p.

Тогда проблема Диффи-Хеллмана решается следующим образом:

δ =B(p, α, γ, δ, 1)^-1