Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
2. В группе В из примера 5.1.6 ord(F) = 1, aord(T) = 2.
3. В группе Roots(x3 — 1) из примера 5.1.7 ord(a) = ord(/3) = 3, ord(l) = 1.
4. В группе Zord(l) = со. ?
Следствие 5.2. Пусть G — конечная группа и а Е G — произвольный элемент. Тогда ord(a) | #G.
Доказательство. Для любого а Е G, если а — е, то ord(a) = 1 и условие ord(a) | #С? является тривиальным. Элементы
a,a2,...,aord<a) =е (5.2.1)
должны быть разными. Допустим, что это не так, и аТ = as при некоторых неотрицательных целых числах г и s, удовлетворяющих условию 1 < г < s < ord(a). Применяя аксиому инверсии к обоим частям равенства, получаем, что a8~r = е при 0 < s — г < ord(a). Это противоречит определению порядка ord(a), который должен быть наименьшим положительным целым числом, удовлетворяющим условию aord(a) = е.
Легко проверить, что ord(a) элементов из соотношения (5.2.1) образуют подгруппу группы G. По теореме Лагранжа ord(a) | #G. ?
Следствие 5.2, вытекающее из теоремы Лагранжа, описывает связь между порядком группы и порядками элементов этой группы. Эта взаимосвязь имеет важное приложение в криптографии с открытым ключом: знаменитая криптосистема Ривеста, Шамира и Адлемана (RSA) [246] функционирует на основе группы, порядок которой является секретным и известен только владельцу ключа. Зашифрованный текст можно рассматривать как случайный элемент некоей группы. Зная порядок группы, владелец ключа может использовать зависимость
Глава 5. Алгебраические основы
183
между порядком элемента и порядком группы для преобразования зашифрованного текста в открытый текст (т.е. расшифровать его). Криптосистема RSA изучается в разделе 8.5.
5.2.3 Циклические группы
Пример 5.1.4 означает, что группу ^ можно представить в виде п точек, лежащих на окружности. Эта окружность (или п точек, лежащих на ней) создается путем повторного применения п операций а1, а2,..., ап к некоторому элементу o6Z. Такая конструкция называется циклическим представлением группы Z„. Для операции по модулю п циклическое представление группы Ъп можно получить с помощью элемента а = 1. Читатель может проверить это утверждение, проанализировав пример 5.1.4 для ситуации, когда п = 12. Элементы 5, 7 и 11 также позволяют создать циклическое представление группы Z12.
Неформально говоря, если группа имеет циклическое представление, то она называется циклической (cyclic group). Такие группы обладают весьма полезными свойствами. Они получили широкое применение в криптографии.
Определение 5.10 (Циклическая группа, порождающий элемент группы).
Группа G называется циклической, если существует элемент а ? G, такой что для любого элемента b G G существует целое число г ^ 0, удовлетворяющее условию b = а1. Элемент а называется порождающим элементом группы G, а группа G называется группой, порожденной элементом а. Если группа G порождается элементом а, используется запись G = (а).
Порождающий элемент (generator) циклической группы также называется первообразным корнем (primitive root) нейтрального элемента группы. Смысл этого названия станет ясен в разделе 5.4.3 (теорема 5.11).
Пример 5.8.
1. Для п > 1 аддитивная группа Ъп является циклической, поскольку совершенно очевидно, что ее порождающим элементом является единица.
2. В примере 5.1.6 группа В является циклической и порождается элементом Т.
3. В примере 5.1.7 группа Roots(a;3 — 1) является циклической. Она порождается элементами а и (3.
4. Пусть р — простое число. В этом случае мультипликативная группа Z* является циклической, поскольку она содержит элемент р — 1 = и, следовательно, этот элемент порождает всю группу. В алгоритме 4.6 мы осуществили эмпирическую проверку того, что группа Z* содержит порождающий элемент. Формальное доказательство этого факта содержится в теореме 5.12.
184
Часть II. Математические основы
5. В группе Щ порождающим элементом является число 3 Этот элемент создает циклическое представление группы Щ (групповой операцией является умножение по модулю 7).
Определение 5.11 (Функция Эйлера). Для neN, где п ^ 1, аЬункция Эйлера ф(п) равна количеству целых чисел к, таких что О < k < п и gcd(fc, п) = 1.
Для циклической группы доказано много полезных результатов. Теорема 5.2.
1. Любая подгруппа циклической группы является циклической.
2. При каждом положительном делителе d числа #(а) группа (а) содержит' только одну подгруппу, имеющую порядок d.
3. Если #(а) = т, mo #(afc) = ord(afc) = т/ gcd(fc, m).
4. При каждом положительном делителе d числа #(а) группа (а) содержит ф(п) элементов, имеющих порядок d.
5. Пусть #(а) = т. Тогда группа (а) содержит ф(т) порождающих элементов. Они являются элементами оТ, такими что gcd(r, т) = 1.
Доказательство.
1. Пусть НС. (а). Если Н = (е) или Н — (а), то совершенно очевидно, что группа Н является циклической. Рассмотрим другие варианты. Пусть d > 1 — наименьшее целое число, такое что ad G Н, и as G Н при некотором s > d. Разделим число s на число d: s = dq + г, где 0 < г < d. Поскольку adq € Н, то оТ = as~dg € Н. Из минимальности числа d и неравенства Н ф (а) следует, что г = 0. Следовательно, число s кратно числу d. Итак, группа Н содержит только степени ad и является циклической.
