close

Вход

Забыли?

вход по аккаунту

?

Аналог системы шифрования RSA на платформе m2(Zn).

код для вставкиСкачать
МАТЕМАТИКА
Вестн. Ом. ун-та. 2009. № 4. С. 66–73.
УДК 517
А.Н. Агеенко
Омский государственный университет им. Ф.М. Достоевского
АНАЛОГ СИСТЕМЫ ШИФРОВАНИЯ RSA НА ПЛАТФОРМЕ M2(Zn)
Строится аналог системы RSA на платформе M2(Zn). Предлагается улучшенный вариант
RSA' системы шифрования RSA', в котором ключ дешифрования определяется не по
функции Эйлера ϕ (n) , а по периоду мультипликативной группы Zn*.
Ключевые слова: система шифрования, криптосистема, дешифрование.
Введение
RSA – криптосистема, основанная на одном из первых алгоритмов
шифрования с открытым ключом. Она была предложена в 1977 г.
Роном Ривестом (Rivest), Ади Шамиром (Shamir) и Леном Адельманом
(Adelman) и названа по первым буквам фамилий своих создателей. На
протяжении уже более 30 лет система RSA остается наиболее популярной среди всех криптосистем с открытым ключом. Дадим её описание.
Алгоритм RSA
Установка. Сначала выбирается два достаточно больших различных простых числа p и q и вычисляется модуль RSA n = pq. Числа p
и q – секретные, модуль n открыт. Далее вычисляется функция Эйлера φ(n) = (q–1)(p–1). Значение φ(n) также держится в секрете.
После этого выбирается произвольное число e є N, для которого
должно быть выполнено свойство НОД(е, φ(n))=1, тогда e є Zφ(n)* принадлежит мультипликативной группе Zφ(n)* кольца вычетов Zφ(n) по модулю φ(n) и существует число d є N, такое, что ed = 1 (mod φ(n)). Элемент е называется ключом шифрования и считается открытым, а элемент d называется ключом дешифрования и является секретным.
Шифрование. В качестве платформы шифрования в RSA используется кольцо вычетов Zn. Само шифрование осуществляется по правилу:
c = me (mod n),
где m – единица исходного текста, с – единица шифрованного текста.
Дешифрование. Для дешифрования необходимо знать значение
секретного ключа d. Тогда исходный текст можно получить следующим образом:
m = cd = med = m (mod n).
Криптостойкость системы RSA обеспечивается сложностью задачи разложения модуля n на множители. В настоящее время не известно ни одного алгоритма, позволяющего эффективно находить
множители p и q в общем случае, однако и не доказано, что его не су-
© А.Н. Агеенко, 2009
67
Аналог системы шифрования RSA на платформе M2(Zn)
ществует. Но если такой алгоритм будет
найден, то использование системы RSA
сразу прекратится. Поскольку знание
множителей p и q позволяет легко вычислить значение функции Эйлера φ(n)=(p–
1)(q–1), а, следовательно, по ключу шифрования e можно будет легко восстановить ключ дешифрования d, и система
будет полностью раскрыта.
В настоящей работе строится аналог
системы RSA на платформе M2(Zn) –
кольце матриц порядка два над кольцом
вычетов Zn, где n=pq – произведение
различных простых чисел. Для этого
вычисляется аналог функции Эйлера
Φ (n), равный порядку группы обратимых
матриц GL2(Zn) – мультипликативной
группы кольца M2(Zn), и определяется,
какие матрицы A ∈ M 2 ( Z n ) могут быть
использованы в качестве единиц текста.
Устанавливается,
что
строящаяся
система, по крайней мере, так же
криптостойка, как и исходная система
RSA.
Кроме того, предлагается улучшенный
вариант RSA' системы шифрования RSA,
в
котором
ключ
дешифрования
определяется не по функции Эйлера ϕ (n) ,
а по периоду мультипликативной группы
Zn*. Соответствующий вариант системы
предлагается также и для платформы
M2(Zn).
Система RSA на платформе M2(Zn)
Следующий результат является простым обобщением известной Китайской
теоремы об остатках.
Лемма 1 (Обобщенная Китайская
теорема об остатках). [2] Пусть A1 ,
..., Ak ∈ M m ( Z ) – произвольные целочисленные матрицы порядка m. Предположим, что целые числа n1, …, nk ≥ 2
попарно взаимно просты, то есть для
любых i ≠ j НОД(ni,nj)=1. Тогда система
матричных сравнений
⎧ X = A1 (mod n1 ),
⎪
⎨ ,
⎪ X = A (mod n )
k
k
⎩
всегда имеет решение, т. е. существует
целочисленная матрица X, удовлетворяющая системе стравнений. Более того,
решением является любая целочисленная
матрица Y, сравнимая с X mod N, где
N = n1 ⋅ ... ⋅ n k , и любое решение системы
имеет такой вид.
Пусть выбрано некоторое n=pq –
произведение двух различных простых
чисел. Рассмотрим кольцо матриц M2(Zn)
порядка два над кольцом вычетов Zn.
Обозначим через G=GL2(Zn) мультипликативную группу кольца M2(Zn), т. е.
группу обратимых матриц порядка два
над кольцом вычетов Zn.
Для группы G определяются её
гомоморфные образы – реплики –
Gp=GL2(Zp) и Gq=GL2(Zq).
Пусть Φ (n) =| GL2 ( Z n ) | – порядок
группы GL2(Zn), тогда для Φ(n) верно
следующее утверждение.
Теорема 2. Пусть задана группа G
обратимых матриц порядка два над
кольцом вычетов Zn, где
n = pq –
произведение двух различных простых
чисел p и q. Тогда порядок группы G
определяется формулой
Φ (n) = nϕ (n) 2 (2(n + 1) − ϕ (n)),
где ϕ (n) = ( p − 1)(q − 1) – значение
функции Эйлера.
Доказательство. Для доказательства
теоремы необходимо посчитать количество обратимых матриц порядка два
над кольцом вычетов Zn.
Из леммы 1 следует, что матрица
A ∈ M 2 ( Z n ) обратима по модулю n тогда и
только тогда, когда её реплики Ap и Aq обратимы по модулям p и q соответственно.
Таким образом, для начала необходимо посчитать количество обратимых
матриц порядка два над полями Zp и Zq.
Пусть A ∈ M 2 ( Z p ) – некоторая матрица порядка два над полем Zp, имеющая
вид
⎛a b ⎞
⎟⎟.
A = ⎜⎜
⎝c d ⎠
Определитель матрицы A :
(1)
det (A) =
= ad − bc.
Над полем Zp матрица необратима
тогда и только тогда, когда её определитель равен 0: det ( A) = 0.
Рассмотрим все возможные варианты, когда определитель обращается в 0, и
68
А.Н. Агеенко
посчитаем количество матриц в каждом
случае.
1. Пусть a ≠ 0 .
Равенство det(A) = ad – bc = 0 (mod p)
эквивалентно ad = bc (mod p).
Поскольку элемент a обратим, то
d = a-1bc (mod p).
Этому условию удовлетворяет ровно
( p − 1) p 2 матриц, так как элементу a
можно присвоить p − 1 различных значений, не равных 0 , a b и c могут
принимать p различных значений.
3
Всего имеется ( p − 1) p матриц, удовлетворяющих условию a ≠ 0 , следовательно, обратимых матриц над полем Zp в
точности
3
2
p ( p − 1) − p ( p − 1) =
2
= p ( p − 1)( p − 1) = p 2 ( p − 1) 2 .
2. Пусть a = 0.
p ( p − 1) 2 матриц, так как элементы b и c
могут
принимать
p −1
различных
значений,
значение
элемента
a
зафиксировано, а для элемента
d
существует p различных значений.
Таким образом, общее количество
матриц, обратимых над полем Zp, равно
p 2 ( p − 1) 2 + p ( p − 1) 2 = p ( p − 1) 2 ( p + 1).
матриц,
q (q − 1) 2 (q + 1).
Поскольку
A∈ M 2 ( Z n )
своими
произвольная
матрица
однозначно
определяется
репликами
A p ∈ M 2 (Z p )
и
Aq ∈ M 2 ( Z q ) и матрица A обратима тогда
и только тогда, когда обратимы обе её
реплики, то общее количество матриц,
обратимых над Zn, можно вычислить
следующим образом
Φ (n) = q(q − 1) 2 (q + 1) ⋅ p ( p − 1) 2 ( p + 1) =
= pq ⋅ (( p − 1)(q − 1)) 2 ⋅ ( p + 1)(q + 1) =
= n ⋅ ϕ 2 (n) ⋅ ( pq + ( p + q ) + 1).
Следовательно,
p + q = pq + 1 − ϕ (n) = n + 1 − ϕ (n).
Тогда формула для Φ (n) принимает
следующий вид
Φ (n) = n ⋅ ϕ 2 (n) ⋅ (n + (n + 1 − ϕ (n)) + 1) =
= n ⋅ ϕ 2 ( n) ⋅ (2(n + 1) − ϕ (n)).
Теорема доказана.
Лемма 3. Для произвольной матрицы
A порядка два и произвольного числа
k > 1 верно следующее равенство
Ak = r ⋅ Ak −1 − γ ⋅ Ak − 2 ,
где r = tr ( A) , γ = det( A).
Доказательство. Рассмотрим произвольную квадратную матрицу A порядка
два. Пусть она имеет вид (1).
Посчитаем значение
2
Тогда формула для определителя
матрицы примет вид det ( A) = −bc . В этом
случае матрица A обратима тогда и
только тогда, когда элемент bc обратим,
т. е. bc ≠ 0 (mod p ) .
Даному
условию
удовлетворяет
Аналогично,
количество
обратимых над полем Zq равно
Заметим, что
ϕ (n) = ( p − 1)(q − 1) = pq − ( p + q ) + 1,
⎛ a b ⎞ ⎛ a 2 + bc ab + bd ⎞
⎟.
⎟⎟ = ⎜⎜
A = ⎜⎜
2⎟
c
d
ac
cd
bc
d
+
+
⎝
⎠ ⎝
⎠
Из формулы для det(A) выразим bc и
2
подставим в матрицу, получим
⎛ a 2 + bc
A2 = ⎜⎜
⎝ ac + cd
⎛ a 2 + ad − γ
= ⎜⎜
⎝ ac + cd
⎛ (a + d )a − γ
= ⎜⎜
⎝ ( a + d )c
ab + bd ⎞
⎟=
bc + d 2 ⎟⎠
ab + bd ⎞
⎟=
ad − γ + d 2 ⎟⎠
(a + d )b
⎞
⎟.
(a + d )d − γ ⎟⎠
Таким образом,
⎛a b ⎞
⎛1 0⎞
⎟⎟ − γ ⋅ ⎜⎜
⎟⎟ =
A 2 = (a + d )⎜⎜
⎝c d ⎠
⎝0 1⎠
= (a + d ) A − γE.
Умножая одновременно левую и правую часть это равенства на
k ≥ 2 , получаем
Ak − 2 , где
Ak = (a + d ) Ak −1 − γAk − 2 .
Лемма доказана.
При построении матричного аналога
системы RSA в качестве платформы
шифрования используется кольцо матриц
M2(Zn), где n=pq – произведение различных
простых чисел. Числа p и q по-прежнему
держаться в секрете, модуль n открыт. В
качестве открытого ключа шифрования берем число e ∈ N e такое, что
69
Аналог системы шифрования RSA на платформе M2(Zn)
НОД (e, Φ (n)) = 1 , а секретный ключ дешифрования
d∈N
определяем
из
равенства ed = 1 (mod Φ (n)).
Процессы
шифрования
и
дешифрования осуществляются так же,
как и в RSA с учетом правил матричного
умножения.
Далее мы определим, какие матрицы
A ∈ M 2 ( Z n ) можно считать единицами
текста.
Теорема 4. Рассмотрим аналог
системы RSA с модулем n = pq на
платформе M2(Zn). Пусть e – открытый
ключ
шифрования
такой,
что
НОД (e, Φ (n)) = 1 , а d – соответствующий
ему ключ дешифрования такой, что
ed = 1 ( mod Φ ( n)) .
Тогда
для
любой
матрицы A ∈ M 2 ( Z n ) , удовлетворяющей
одному из следующих двух условий:
(1) A ∈ GL2 ( Z n ) ,
(2) A ∉ GL2 ( Z n ) и след tr(A) матрицы A
не равен нулю по модулю p и по модулю q;
верно следующее равенство:
A
ed
= A (mod n).
Доказательство.
1.
Пусть
A∈
∈ GL2 ( Z n ) . Тогда AΦ (n ) = 1 , где Φ (n) –
порядок группы GL2(Zn).
По условию теоремы
по лемме 1 матрица A однозначно
определяется своими репликами, верно
следующее равенство:
A ed = A (mod n).
Рассмотрим реплику Ap матрицы A
над полем Zp. Пусть γ p , следовательно,
γ = 0 (mod p ) и матрица A необратима над
полем Zp.
Обозначим det ( Ap ) = γ p = 0 .
Будем считать, что ключ шифрования
так
как
иначе
получаем
тривиальный случай. Тогда к матрице
e ≠ 1,
Aed
p
можно
применить
ed −1
Aed
.
p = ( a + d ) Ap
Далее, применим утверждение леммы
3 к матрице, стоящей в правой части и
получим
2 ed − 2
Aed
.
p = (a + d ) Ap
Проделываем это до тех пор, пока не
получим
ed −1
Aed
Ap .
p = (a + d )
a + d ≠ 0.
(a + d )
= 1,
ed = 1 (mod Φ (n)).
ed = 1 + kΦ (n).
Поскольку
Следовательно,
d ) ∈ Z *p ,
A ed = A1+ kΦ ( n ) = A( AΦ ( n ) ) k = A ⋅ 1k = A.
2. Пусть A∉ GL2 ( Z n ) , т. е. матрица A
необратима над кольцом вычетов Zn.
По-прежнему считаем, что матрица A
имеет вид (1).
Условие необратимости матрицы над
кольцом вычетов Zn означает, что
НОД (n, γ ) ≠ 1.
Следовательно,
варианта:
возможны
три
1 γ p, γ / q
2. γ / p, γ q
3. γ p, γ q
= A p (mod p) и
при
Aqed
= Aq (mod q) , где
что
условии
a + d ≠ 0 (mod p),
следовательно, (a + d )
p −1
Так
как
ed = 1 (mod Φ (n)) ,
эквивалентно ed = 1 + k ⋅ Φ ( n). Тогда
то
= 1.
это
(a + d ) ed −1 = (a + d )1+ k ⋅Φ ( n ) − = (a + d ) k ⋅Φ ( n ) .
Расписывая величину Φ (n) согласно
теореме 2, получим
(a + d ) ed −1 ) = (a + d ) k ⋅n⋅( p −1)( q −1)⋅(2( n +1) −ϕ ( n )) =
= ((a + d ) p −1 ) k ⋅n⋅( q −1)⋅(2( n +1) −ϕ ( n )) .
Так как (a + d ) p −1 = 1, получаем
Таким образом,
γ q и след матрицы r = a + d не равен 0,
A ed
p
(a +
Покажем,
(a + d ) ed −1 = 1k ⋅n⋅( q −1)⋅(2( n +1) −ϕ ( n )) = 1.
Нужно показать, что если γ p и/или
γp =0,
получаем
ed −1
что эквивалентно равенству
утверждение
леммы 3. С учетом того, что
Пусть
ed = 1 (mod Φ (n)),
то
Ap , Aq – реплики матрицы A. Поскольку
ed −1
Aed
Ap = Ap .
p = (a + d )
Если a + d = 0, то по лемме 3
A pk = 0
∀ k ≥ 2.
70
А.Н. Агеенко
То есть в какую бы степень d не была
возведена матрица
A ep ,
e ≥ 2 , будет верно
p ed = p (mod n).
следующее равенство
A ed
p = 0.
Следовательно,
по
значению
Aep
невозможно восстановить матрицу Ap.
C точки зрения криптографии это
означает,
что
произошла
потеря
информации,
что
категорически
запрещено.
Аналогичные рассужения верны и для
поля Zq.
Теорема доказана.
Криптостойкость
Выявленная зависимость между величиной Φ(n) (порядком группы GL2(Zn)) и
значением функции Эйлера φ(n), позволяет сделать вывод о том, что построенный аналог, по крайней мере, так же
криптостоек, как и RSA. Таким образом,
криптостойкость предложенной системы
основана на тех же сложных задачах, что
и криптостойкость исходной системы
RSA.
Система RSA' на платформах Zn и
M2(Zn)
Допустим, рассматривается система
шифрования RSA с параметрами: n=pq –
открытый модуль, e – открытый ключ, d –
секретный ключ. Открытый ключ e ∈ N в
системе выбирается произвольно, но
только
с
выполнением
условия
НОД (e, ϕ (n)) = 1 , где ϕ (n) = ( p − 1)(q − 1) –
значение функции Эйлера. Тогда d ∈ N
вычисляется как единственное решение
1 ≤ d ≤ ϕ ( n) − 1
такое,
что
ed = 1 (mod ϕ (n)) .
m1ed = m1 (mod n) .
Остается
верно
проверить справедливость сравнения
Ключ
d
позволяет
расшифровать любой текст c = m e ( mod n) .
Если НОД ( m, n) = 1 , то по теореме
Эйлера из равенства
ed = 1 + ϕ (n)k , k ∈ Z
получаем равенство
c d = m ed = m(m ϕ ( n ) ) k = m ⋅ 1k = m (mod n).
Так как
n=pq – произведение
различных простых чисел, это сравнение
равносильно системе
⎧ p ed = p (mod p),
⎨ p ed = p (mod q).
⎩
Здесь первое сравнение очевидно, а
второе следует из того, что p и q –
различные простые числа.
Расшифровка конкретного текста
Пусть
m ∈ Z n* , пусть m t = 1 (mod n) ,
причем t ∈ N – минимальное число с
указанным свойством (порядок | m |= t
e
элемента m в группе Zn*). Тогда текст m
может быть расшифрован ключом d1 ,
таким, что ed1 = 1 ( mod t ) . Действительно,
для некоторого l ∈ N
ed1 = 1 + t ⋅ l ,
поэтому
m
ed1
= m( m t ) l = m ⋅ 1l = m (mod n).
Так как группа
ϕ (n) = ( p − 1)(q − 1) ,
элементы порядка
Пример.
Zn* имеет порядок
то в ней есть
t < ϕ ( n) .
n = 3 ⋅ 5 = 15, ϕ (n) = 2 ⋅ 4 = 8 ,
но
группа Z15* не циклическая, её элементы
имеют порядки 2 или 4.
Зададим такой вопрос: существует
ли ключ d ′ для системы RSA, такой, что
d ′ < d , но в то же время d ′ дешифрует
все возможные тексты?
Ответ: да, существует.
Определение. Периодом группы G
называется наименьшее число T, такое,
что g = 1 для любого g ∈ G.
Лемма 5. Период группы Zn*, при
T
n = pq , равен t (n) = НОК ( p − 1, q − 1) .
Доказательство. Пусть для удобства
m p, m q , то m = 0 (mod n) и
t = t(n). Докажем, что для любого m ∈ Z n
равенство m ed = m = 0 очевидно.
Если m p, m / q , то d также дешифрует m . Докажем это.
Доказательство [1, с. 99]. Пусть
m = p t m1 , где НОД (m1 , p ) = 1 . Тогда для m1
верно m t = 1 ( mod n) . Действительно, так
Если
*
как t ( p − 1) , то t = ( p − 1) r и
m t = m ( p −1) r = 1r = 1 (mod p ),
в то же время t ( q − 1), т. е. t = ( q − 1) s,
и, соответственно,
71
Аналог системы шифрования RSA на платформе M2(Zn)
m t = m ( q −1) s = 1s = 1 (mod q ).
Значит, по
НОД ( p, q) = 1 получаем,
t
что m = 1 ( mod pq ) = 1 ( mod n).
Наоборот, докажем, что
найдется
m ∈ Z , такой, что
*
n
| m |= НОК ( p − 1, q − 1) = t .
Действительно, так как группа Zp*
циклическая, в ней есть элемент g
порядка | g |= p − 1 , т. е.
g p −1 = 1 (mod p ),
причем p − 1 – минималная степень с
данным свойством.
Аналогично, существует 1 ≤ f ≤ q − 1 с
условием
f
q −1
= 1 (mod q),
где q − 1 – также минимальная степень с
данным свойством.
Рассмотрим систему сравнений
⎧ x = g (mod p),
⎨ x = f (mod q ),
⎩
которая имеет решение x = h (mod pq) =
= h (m mod n) по Китайской теореме об
остатках.
Порядок t' элемента h в группе Zn*
должен делиться на его порядок в группе
Zp*, т. е. на p − 1 , аналогично t' должен
делиться на q − 1 , т. е. t ' НОК ( p − 1, q − 1) .
Но мы знаем, что t ' ≥ t . Поскольку любой
элемент в степени t равен 1 ( mod n) , в
частности, h t = 1 ( mod n) . Значит в силу
минимальности t ' = t = НОК ( p − 1, q − 1) .
Лемма доказана.
Замечание 6. Число t(n) (период
группы Zn*) заведомо меньше, чем ϕ (n).
Доказательство. Действительно, так
как
p − 1, q − 1 2 ,
имеем
p −1 =
b
b
= 2 a p11 … pl l ,
c
c
q − 1 = 2b p11 … pl l , тогда
max( c1 ,b1 )
НОК( p − 1, q − 1) = 2 max( a,b) p1
а
b + c1
( p − 1)(q − 1) = 2 a + b p11
max( cl ,bl )
… pl
b + cl
… pl l
,
, тогда
a + b строго больше, чем max(a, b) .
Итак,
период
группы
t (n) = НОК ( p − 1, q − 1).
Z n*
равен
При построении системы шифрования RSA' ключ дешифрования d будем
находить по ключу e : НОД (e, ϕ ( n)) = 1 ,
из равенства ed = 1 ( mod t ( n)).
Очевидно, что найденный таким
способом ключ d также позволит расшифровать любой текст c = m (mod n). И
поскольку
для
вычисления
периода
группы Zn* необходимо знание простых
чисел p и q, то можно считать, что
системма RSA' так же криптостойка, как
и исходная система RSA.
Перейдем к рассмотрению матричного аналога RSA'. Пусть по-прежнему,
n = pq – произведение различных простых
чисел. Как и ранее, n – открытый модуль,
p и q – секретные. Шифрование
осуществляется на платформе M2(Zn) –
кольцо квадратных матриц порядка два
над кольцом вычетов Zn. Секретный ключ
e ∈ Z выбирается произвольно, но с выполнением
условия
НОД (e, Φ(n)) = 1.
Ключ дешифрования, как и в численном
случае RSA', будем находить по e в
соответствии с правилом
e
ed = 1 (mod T (n)) ,
где T(n) – период мультипликативной
группы GL2(Zn) кольца M2(Zn).
Легко увидеть, что и при таком
выборе ключа дешифрования также
верна теорема 3.
Для
того,
чтобы
обосновать
криптостойкость
данного
варианта
системы RSA´ необходимо понять, как
можно вычислить порядок
группы
GL2(Zn).
Лемма 7. Пусть α : G → H – гомоморфизм группы G на группу H. Тогда
порядок | g | любого элемента g конечного
порядка группы G делится на порядок его
образа α ( g ) = h ∈ H .
Доказательство. Пусть порядок | g |
элемента g ∈ G равен k, т. е. g k = 1 и k –
наименьшая степень с таким свойством.
Сначала покажем, что если g k = 1 , то
h k = 1.
Распишем h k , и с учетом того, что
g k = 1 получим
h k = α k ( g ) = α ( g k ) = 1.
(2)
Пусть порядок элемента h в группе H
равен t, т. е. t есть наименьшая степень,
для которой h t = 1.
72
А.Н. Агеенко
Заметим, что k ≥ t . Иначе получаем
противоречие тому, что t – порядок
элемента h в группе H.
Докажем, что k делится на t.
Предположим обратное. Пусть k не
делится на t. Тогда разделим k на t с
остатком
k = l ⋅ t + r,
0 ≤ r < t.
r
li =
∏p
для некоторых α ij ≥ 0,
r
mi =
β ij
∏p
для некоторых β ij ≥ 0,
j
j =1
r
ti =
∏p
γ ij
j
для некоторых γ ij ≥ 0,
j =1
Еще раз распишем h :
где { p j } – набор некоторых различных
h k = h l ⋅t + r = (h t ) l ⋅ h r .
Так как h t = 1 и h k = 1 (из равенства
(2)), то 1 = h k = h r .
Следовательно,
простых
чисел,
одинаковый
для
всех
li , mi , t i , т. е. если в разложении какого-
∪{m }∪{t }
либо числа из {l i }
i
i
отсутвует
некоторое p j , то считаем что соответст-
h r = 1.
r
Поскольку r < t и h = 1 , получаем
противоречие минимальности t, как
порядка элемента h в группе H.
Таким образом, порядок любого
элемента g группы G делится на порядок
его образа α ( g ) = h ∈ H , при гомоморфном отображении группы G на группу H
Лемма доказана.
Лемма 8. Пусть α : G → H – гомоморфизм группы G на группу H. Пусть TG
– период группы G, TH – период группы
H. Тогда TG делится на TH .
Доказательство. Так как TG –
период группы G, то по определению
периода группы для него верно утверждение:
∀g ∈ G ,
g
TG
= 1.
(3)
Следовательно, TG должен делиться
на все возможные порядки элементов
группы G и, поскольку период – это
наименьшая степень, обладающая свойством (3), то
TG = НОК (l1 , l 2 , … , l k ),
l1 , l 2 , … , l k
–
все
(4)
возможные
порядки элементов группы G.
Аналогично,
вующая степень равна нулю.
C
учетом
данных
разложений
формулу (4) для нахождения величины TG
можно записать в следующем виде
r
TG =
∏p
maxi =1,…, k (α ij )
.
j
j =1
Аналогично,
r
TH =
∏p
maxi =1,…, k ( β ij )
.
j
j =1
Для того, чтобы TG делилось на TH ,
необходимо, чтобы выполнялось
maxi (α ij ) ≥ maxi ( β ij ),
j = 1, … , r.
Предположим сущетвует j такое, что
maxi (α ij ) = α aj < maxi ( β ij ) = β bj .
(6)
Из равенства (5) следует
α ij = β ij + γ ij ; i = 1, … , k ;
j = 1, … , r.
В частности,
α bj = β bj + γ bj .
C учетом неравенства (6)
α bj = β bj + γ bj > α aj + γ bj ≥ α aj .
Таким образом, получаем
α bj > α aj ,
что противоречит максимальности α aj ,
следо-вательно,
TH = НОК (m1 , m2 , … , m k ),
где
j
j =1
k
где
α ij
maxi (α ij ) ≥ maxi ( β ij )
для
(5)
всех j = 1, … , r.
Лемма доказана.
Теорема 9. Рассмотрим группу
Gn=GL2(Zn) и группы Gp=GL2(Zp), Gq=GL2(Zq),
Пусть T – период группы Gn , T p и Tq –
Распишем все l i , mi , t i по степеням
периоды групп G p , Gq соответственно.
m1 , m2 , …, mk – все возможные
порядки элементов группы H .
Из леммы 7 следует, что
l i = mi ⋅ t i
простых чисел
i = 1,… k .
Тогда верно следующее равенство
Аналог системы шифрования RSA на платформе M2(Zn)
⎧ ATp = E (mod p),
⎪
⎨ T
⎪⎩ Aq = E (mod q).
T = НОК (T p , Tq ).
Доказательство. Группы G p и Gq являются естественными гомоморфными образами группы Gn . Это следует из того, что
поля Zp и Zq являются естественными
гомоморфными образами кольца вычетов Zn.
Через Ap , Aq будем обозначать реп-
Поскольку матрицы Ap ∈ G p и Aq ∈ Gq
являются гомоморфными образами матрицы A∈ Gn , то ATp = ( AT ) p и AqT = ( AT ) q .
Следовательно,
лики матрицы A ∈ Gn .
⎧⎪( AT ) p = E (mod p),
⎨ T
⎪⎩( A ) q = E (mod q ),
Рассмотрим величину T ∈ Z и покажем,
что AT = E для всех A ∈ Gn тогда и только
73
тогда, когда T делится на T p и на Tq .
тогда по Обобщенной Китайской теореме
об остатках получаем
Необходимость.
Пусть AT = E для
всех
A∈ Gn , следовательно, либо T
Так как матрица A∈ Gn произвольная, то
является периодом группы G n , либо T
кратна периоду группы Gn , т. е.
T = k ⋅ TG ,
k = 1, 2, …
n
(7)
По лемме 8 период группы Gn делится
на период любой группы, являющейся
гомоморфным
образом
группы
Gn .
Следовательно, TG делится на T p и Tq .
n
Тогда из равенства (7) следует, что T
также делится на T p и Tq .
Необходимость доказана.
Достаточность. Неоходимо доказать, что если T делится на T p и Tq , то для
AT = E (mod n).
AT = E для всех A∈ Gn .
Достаточность доказана.
Поскольку по определению период
группы – наименьшая степень для
которой AT = E для всех A∈ Gn , то для
того, чтобы T было периодом группы G n ,
необходимо и достаточно, чтобы T было
наименьшим
числом,
обладающим
свойствами
(9)–(10).
Следовательно,
T = НОК (T p , Tq ) есть период группы
Gn .
Так как T T p и T Tq , следовательно,
Теорема доказана.
Только
что
доказанная
теорема
позволяет сделать вывод о том, что
матричный аналог RSA', по крайней мере,
так же криптостоек, как и исходная
система RSA, поскольку для нахождения
периода группы GL2(Zn) необходимо знать
разложение открытого модуля n в
произведение двух различных простых
чисел p и q, а это является сложной
задачей1.
T = x ⋅ T p для некоторого x ∈ Z ,
(9)
ПРИМЕЧАНИЯ
T = y ⋅ Tq для некоторого y ∈ Z .
(10)
1
произвольной матрицы A ∈ Gn из системы
⎧⎪ ATp p = E (mod p),
⎨ Tq
⎪⎩ Aq = E (mod q)
(8)
следует, что AT = E ( mod n).
Вернемся к системе сравнений (8).
Возведем первую строку системы в
степень x , а вторую – в степень y ,
получим
⎧ A pxT p = E x = E (mod p),
⎪
⎨ yTq
y
⎪⎩ Aq = E = E (mod q ),
что эквивалентно
Работа выполнена под руководством профессора
В.А. Романькова.
ЛИТЕРАТУРА
[1] Романьков В.А. Введение в криптографию: курс
лекций. 2-е изд., испр. и доп. Омск: Изд-во Ом. гос.
ун-та, 2009.
[2] Гордиенко В.В. Методы построения «тайных
входов» в криптографии: дипломная работа.
ИМИТ ОмГУ, 2008.
Документ
Категория
Без категории
Просмотров
11
Размер файла
590 Кб
Теги
платформы, шифрование, аналоги, система, rsa
1/--страниц
Пожаловаться на содержимое документа