Пособие «Защита информации» (МФТИ)

Китайская теорема об остатках - Программирование от R.. Page 1 of 3

Китайская теорема об остатках

Пусть m - натуральное число, m1, m2, ..., mt - взаимно простые натуральные числа, произведение которых больше либо равно m.

Теорема

Любое число x: 0 <= x <= m может быть однозначно представлено в виде последовательности r(x) = (r1, r2, ..., rt), где ri = x(mod mi).

Для любых чисел r1 .. rt, таким образом, существует единственное число x(mod m), такое что

x = ri(mod mi), 1 <= i <= t

Более того, любое решение x набора такого сравнений имеет вид

x = r1*e1 + ... + rt*et (mod m), где

ei = m / mi * ( ( m/mi )-1 mod mi ), 1 <= i <= t.

Вышеприведенная формулировка - Китайская Теорема об Остатках в том виде, в котором ее сформулировал в 1247 году нашей эры китаец Jiushao Qin.

Заметим, что число m/mi = m1*...*mi-1*mi+1*...*mt взаимно просто с mi, а значит обратное число в формуле для ei всегда существует. Кроме того, имеют место равенства ei*ei = ei (mod

m)

ei * ej = 0 (mod m), i =/= j.

Знакомым с теорией колец: Zm = Zm1 + ... + Zmt, сумма прямая. ei, как следует из равенств выше - ортогональные идемпотенты в кольце Zm.

Иначе говоря, кольцо R = Zm разлагается в прямую сумму

R = R1 + R2 + ... + Rt ,

где Ri = Rei = {a*ei (mod m): a - целое} ~ Zmi , 1 <= i <= t.

Последовательность ( r1, ..., rt ) называется модульным представлением x. Набор модульных представлений для всех x: 0 <= x <= m называется системой вычетов.

Операции

Сумма представлений - последовательность wi = ri + ui mod mi

Произведение - последовательность zi = ri * ui mod mi.

Как восстановить число по системе вычетов?

Алгоритм Гаусса

Очевидный алгоритм получается, если вычислять x по формуле, данной в теореме:

На входе:

20

http://program.rin.ru/razdel/html/628.html

28.05.2004

Китайская теорема об остатках - Программирование от R.. Page 2 of 3

положительные взаимно простые m1, ..,mt целые r1, .., rt

На выходе:

Целое число x:

x = ri (mod mi), 1 <= i <= t 0 <= x <= m, m = m1*..*mt

1.Вычислить m = m1*..*mt, положить x=0.

2.for i=1, 2, .., t do

вычислить yi = m/mi

вычислить расширенным алгоритмом Евклида si = yi-1 mod mi ci = ri*si mod mi

x = x + ci*yi (mod m)

3.Возвратить x

Алгоритм Гарнера

Пусть все mi > 1, m = m1*..*mt. Тогда любое число 0 <= x < m может быть однозначным образом представлено в виде

x = x0 + x1m1 + x2m1m2 + ... + xt-1m1m2*...*mt-1 ,

где 0 <= xi < mi+1, i = 0, 1, .., t-1.

Для xi верно соотношение

ri+1 - ( x0 + x1m1 + .. + xi-1m1mi-1)

xi =		(mod mi+1)
	m1*..*mi

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

Получившийся алгоритм носит имя Гарнера(Garner). Он также пригоден для аналогичных операций с полиномами (в предыдущем алгоритме требуются некоторые изменения).

1.For i from 2 to t {

1.1Ci := 1;

1.2For j from 1 to (i-1) { u := mj-1 mod mi;

Ci := u*Ci mod mi;

}

}

2.u := r1; x := u;

3.For i from 2 to t {

u:= (ri-x)Ci mod mi;

x := x + u* [ Произведение mj от j=1 до i-1 ];

}

4. return (x);

21

http://program.rin.ru/razdel/html/628.html

28.05.2004

Китайская теорема об остатках - Программирование от R.. Page 3 of 3

Пример: пусть

m1=5, m2=7, m3=11, m4=13,

m = m1*m2*m3*m4 = 5*7*11*13 = 5005, r(x) = (2, 1, 3, 8).

Константы Ci: C2=3, C3=6, C4=5.

Значения (i, u, x), вычисленные на шаге 3: (1, 2, 2); (2, 4, 22); (3, 7, 267) и (4, 5, 2192).

Таким образом модульное представление r(x) отвечает x = 2192.

Примечание Нахождение m-1 - обратного элемента по модулю можно осуществить опять по алгоритму Евклида.

22

http://program.rin.ru/razdel/html/628.html

28.05.2004

Система RSA

В 1977-78 гг. Р.Л. Ривест, А. Шамар и Л. Адлеман предложили новую криптографическую систему с открытым ключом, названную в честь создателей RSA. RSA используется во многих коммерческих системах, на Web-серверах, для цифровой подписи электронной почты, в системах электронных кредитных карт и т.д. Надежность системы RSA основана на сложности задачи факторизации натуральных чисел.

Пусть М — число всевозможных сообщений, каждой из которых является целым числом m, 0≤m<М. Например, при использовании латинского алфавита сообщения, длина которых ограничена сверху числом s, могут рассматриваться как s-значные числа в 26ричной системе счисления. Таким образом, в качестве М можно взять 26s. Типичный размер для М — 300–600 десятичных знаков.

Каждый пользователь А системы RSA выбирает два больших простых числа, так чтобы их произведение N = pg было больше М (например, если N имеет 1024 бит в двоичной записи, то р и g имеют длину в 512 бит).

Затем А выбирает число e, взаимно простое с р-1 и q-1 и имеющее примерно столько же знаков, что и N. Потом вычисляет d, такое, что de ≡ 1(mod p-1), de≡1(mod q-1). Пару чисел (N,e) А публикует в открытом справочнике, а числа p, q, d хранит в секрете. Допустим, абонент В хочет послать абоненту А сообщение х. Чтобы его зашифровать, В находит в справочнике под именем А пару (N,e) и вычисляет y≡хe(mod N). Число у посылается абоненту А по открытому каналу связи. Получив шифрованное послание у, абонент А вычисляет yd(mod N), применяя свой секретный ключ d, и получает yd ≡ (xe)d(mod N) ≡ xed(mod N). Оказывается, что xed ≡ x(mod N), и послание х восстановлено.

Теорема о корректности системы RSA

Пусть N = pq — произведение двух различных чисел, e и d — два натуральных числа,

меньшие (p-1)(q-1), таких, что ed ≡ 1(mod p-1), ed≡ 1(mod q-1). Тогда, для любого х Zn xed ≡ x(mod N).

ДОКАЗАТЕЛЬСТВО

Для N = pq имеем φ(N) = φ(p)φ(q) = (p-1)(q-1) (φ(N) — функция Эйлера — количество натуральных чисел, не превосходящих N и взаимно простых с N). Группа U(Zn) обратимых элементов кольца Zn имеет порядок φ(N). Согласно китайской теореме об остатках отображение ψ: Zn →Zp ×Zq, ψ(x) = (x1, x2), x≡x1(mod p), x ≡ x2(mod q), является изоморфизмом. Поэтому ψ(хed) = ( x1ed , x2ed ). Так как ed = 1+k(p-1), то

x1ed = x11+k ( p−1) = x1 (x1 )k ( p−1) = x1 (x1p−1 )k = x1 в Zp. Здесь использовано то, что для х1≠0 в Zp, x1p−1 =1. Если х1 = 0, то x1ed = 0 = x1 . Аналогично, из условия ed = 1(mod q-1) получаем

x2ed = x2 в Zq. Итак, ψ(хed) = ψ(х) = (x1,x2). Так как ψ — изоморфизм, то хed = х в ZN. Таким образом, yd ≡ xed(mod N) ≡ x(mod N) и А восстанавливает сообщение х.

Если противник С сумеет разложить на простые множители известное число N = pq, то, зная открытый ключ e, он, так же, как А, может вычислить секретный ключ d, такой, что ed ≡ 1(mod p-1), ed ≡ 1(mod q-1), и расшифровать сообщение, посылаемые абоненту А. Следовательно, если задача факторизации может быть эффективно (за полиномиальное время) решена, то система RSA может быть легко взломана. Другой метод взломать систему RSA до сих пор не найден, хотя и не доказано, что для взлома системы RSA необходимо иметь эффективный алгоритм факторизации. Таким образом, связь надежности системы RSA со сложностью задачи факторизации аналогична связи проблемы Диффи-Хеллмана с проблемой дискретного логарифма.

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

23

подписи и для передачи секретного ключа, а затем применяется классическая система

шифрования. Подробнее о криптографии с открытым ключом можно прочитать в книге Яценко В.В.1

Сложность задачи факторизации

Трудоемкость алгоритмов, работающих с большими числами, оценивается количеством битовых операций. Зная количество операций, выполняемых компьютером за 1 секунду, можно оценить машинное время, необходимое для выполнения алгоритма. Оценка трудоемкости наиболее быстрых алгоритмов факторизации натуральных чисел

имеет вид О(exp log n log log n ).

В 1977 г. Ривест, Шамир и Адлеман составили таблицу трудоемкости для задачи факторизации натуральных чисел в зависимости от количества их десятичных цифр:

Число десятичных цифр	Число операций
	1,4 · 1010
50
75	9,0 · 1012
100	2,3 · 1015
200	1,2 · 1023
300	1,5 · 1029
500	1,3 · 1039

Если компьютер выполняет 2*1011 операций в секунду, то для разложения на множители числа, имеющего 300 десятичных знаков, требуются десятки миллионов лет машинного времени.

1 Яценко В.В. Введение в криптографию. М. МЦНМО: «ЧеРо», 1999. — 272с.

24

Цифровая подпись Эль-Гамаля.

Открытый ключ : p, α, β=αamod(p) Секретный ключ : а.

А передаёт В комбинацию (М,S(M)), здесь M-сообщение, S(M) – подпись.

Как формируется подпись : А выбирает число 1=<r=<p-2, вычисляет r-1mod(p) S(M)=(C1, C2)

C1=αrmod(p); C2=[h(M)-aC1]r-1mod(p-1)

B: получает M’, C1’, C2’ и начинает проверять подпись.

Он знает (p, α, β) – открытый ключ, а также хеш-функцию h(*)

Проверка подписи : Z1=[(β)C1’(C1’)C2’]mod(p)	Z2=αh(M’)mod(p).
Если Z1=Z2 то подпись принимается.
Проверка корректности : Предположим M’=M;	C1’=C1; C2’=C2.

Z1=βC1C1C2mod(p)=αaC1αr (h(M)-aC1)r^-(1)mod(p) = {т.к. rr-1=m(p-1)+1} = αaC1α(m(p-1)+1)(h(M)-

aC1)mod(p) =

{ т.к αS(p-1)mod(p)=1} = αaC1αh(M)-aC1 mod(p)=αh(M) mod(p) = Z2

Мы можем подделать М, С1, а С2 – не можем, даже если знаем хеш-функцию, т.к. подобрать 2 аргумента с одинаковым значением хеш-функции есть вычислительно трудная задача.

25

бывайте использовать перед подписанием однонаправленную хэш-функцию . Рабин предложил другой способ защититься от такого вскрытия: к каждому сообщению перед хэшированием и подписанием добавляется ун и- кальная случайная строка. К несчастью, после добавления однонаправленной хэш-функцией тот факт, что си с- тема столь же безопасна, как и разложение на множители, больше не является доказанным [628]. Хотя с практической точки зрения добавление хэширования не может ослабить систему.

Другими вариантами схемы Рабина являются [972, 909, 696, 697, 1439, 989]. Двумерный вариант описан в [866, 889].

19.6 ElGamal

Схему EIGamal [518,519] можно использовать как для цифровых подписей, так и для шифрования, его без о- пасность основана на трудности вычисления дискретных логарифмов в конечном поле .

Для генерации пары ключей сначала выбирается простое число p и два случайных числа, g и x, оба эти числа должны быть меньше p. Затем вычисляется

y = gx mod p

Открытым ключом являются y, g и p. И g, и p можно сделать общими для группы пользователей . Закрытым ключом является x.

Подписи ElGamal

Чтобы подписать сообщение M, сначала выбирается случайное число k, взаимно простое с p-1. Затем вычисляется

a = gk mod p

и с помощью расширенного алгоритма Эвклида находится b в следующем уравнении:

M = (xa + kb) mod (p - 1)

Подписью является пара чисел: a и b. Случайное значение k должно храниться в секрете. Для проверки подписи нужно убедиться, что

yaab mod p = gM mod p

Каждая подпись или шифрование EIGamal требует нового значения k, и это значение должно быть выбрано случайным образом. Если когда-нибудь Ева раскроет k, используемое Алисой, она сможет раскрыть закрытый ключ Алисы x. Если Ева когда-нибудь сможет получить два сообщения, подписанные или зашифрованные с помощью одного и того же k, то она сможет раскрыть x, даже не зная значение k. Описание ElGamal сведено в 14-й.

Табл. 19-5. Подписи ElGamal

Открытый ключ:

pпростое число (может быть общим для группы пользователей)

g<p (может быть общим для группы пользователей)

y=gx mod p

Закрытый ключ:

x<p

Подпись:

kвыбирается случайным образом, взаимно простое с p-1

a(подпись) =gk mod p

b(подпись), такое что M = (xa + kb) mod (p - 1)

Проверка:

Подпись считается правильной, если yaab mod p = gM mod p

Например, выберем p = 11 и g = 2, а закрытый ключ x = 8. Вычислим

26

y = gx mod p = 28 mod 11 = 3

Открытым ключом являются y = 3, g = 2 и p = 11. Чтобы подписать M = 5, сначала выберем случайное число k=9. Убеждаемся, что gcd(9, 10)= 1. Вычисляем

a = gk mod p = 29 mod 11 = 6

и с помощью расширенного алгоритма Эвклида находим b:

M = (xa + kb) mod (p - 1)

5 = (8*6 + 9*b) mod 10

Решение: b = 3, а подпись представляет собой пару: a = 6 и b = 3.

Для проверки подписи убедимся, что

yaab mod p = gM mod p 3663 mod 11 = 25 mod 11

Вариант EIGamal, используемый для подписей, описан в [1377]. Томас Бет (Thomas Beth) изобрел вариант схемы EIGamal, подходящий для доказательства идентичности [146]. Существуют варианты для проверки подлинности пароля [312] и для обмена ключами [773]. И еще тысячи и тысячи других (см. раздел 20.4).

Шифрование ElGamal

Модификация EIGamal позволяет шифровать сообщения. Для шифрования сообщения M сначала выбирается случайное число k, взаимно простое с p - 1. Затем вычисляются

a = gk mod p

b = yk M mod p

Пара (a,b) является шифротекстом. Обратите внимание, что шифротекст в два раза длиннее открытого те к- ста. Для дешифрирования (a,b) вычисляется

M = b/ax mod p

Òàê êàê ax ≡ gkx (mod p) è b/ax ≡ yk M/ax ≡ gxk M/ gkx = M (mod p), то все работает (см. 13-й). По сути это то же самое, что и обмен ключами Диффи-Хеллмана (см. раздел 22.1) за исключением того, что y - это часть ключа, а при шифровании сообщение умножается на yk.

Табл. 19-6. Шифрование ElGamal

Открытый ключ:

pпростое число (может быть общим для группы пользователей)

g<p (может быть общим для группы пользователей)

y=gx mod p

Закрытый ключ:

x<p

Шифрование:

kвыбирается случайным образом, взаимно простое с p-1

a(шифротекст) =gk mod p

b(шифротекст)= yk M mod p

Дешифрирование:

M (открытый текст) = b/ax mod p

Скорость

Некоторые примеры скорости работы программных реализаций EIGamal приведены в 12-й [918].

Òàáë. 19-7.

27

Скорости EIGamal для различных длин модулей при 160-битовом показателе степени (на SPARC II)

	512 битов	768 битов	1024 битов
Шифрование	0.33 ñ	0.80 ñ	1.09 ñ
Дешифрирование	0.24 ñ	0.58 ñ	0.77 ñ
Подпись	0.25 ñ	0.47 ñ	0.63 ñ
Проверка	l.37 ñ	5.12 ñ	9.30 c

Патенты

ElGamal незапатентован. Но, прежде чем двигаться вперед и реализовывать алгоритм, нужно знать, что PKP считает, что этот алгоритм попадает под действие патента Диффи-Хеллмана [718]. Однако срок действия патента Диффи-Хеллмана заканчивается 29 апреля 1997 года , что делает ElGamal первым криптографическим плгоритмом с открытыми ключами, пригодным для шифрования и цифровых подписей и несвязанным в Соедине н- ных Штатах патентами. Я не могу дождаться этого момента.

19.7 McEliece

В 1978 году Роберт МакЭлис (Robert McEliece) разработал криптосистему с открытыми ключами на основе теории алгебраического кодирования [1041]. Этот алгоритм использует существование определенного класса исправляющих ошибки кодов, называемых кодами Гоппа (Goppa). Он предлагал создать код Гоппа и замаск и- ровать его как обычный линейный код . Существует быстрый алгоритм декодирования кодов Гоппа , но общая проблема найти слово кода по данному весу в линейном двоичном коде является NP-полной. Хорошее описание этого алгоритма можно найти в [1233], см. также [1562]. Ниже приведен только краткий обзор.

Пусть dH(x,y) обозначает расстояние Хэмминга между x и y. Числа n, k и t служат параметрами системы.

Закрытый ключ состоит из трех частей: G' - это матрица генерации года Гоппа, исправляющего t ошибок. P - это матрица перестановок размером n*n. S - это nonsingular матрица размером k*k.

Открытым ключом служит матрица G размером k*n: G = SG'P.

Открытый текст сообщений представляет собой строку k битов в виде k-элементного вектора над полем GF(2).

Для шифрования сообщения случайным образом выбирается n-элементный вектор z над полем GF(2), для которого расстояние Хэмминга меньше или равно t.

c = mG + z

Для дешифрирования сообщения сначала вычисляется c' = cP-1. Затем с помощью декодирующего алгоритма для кодов Гоппа находится m' , для которого dH(m'G,c) меньше или равно t. Наконец вычисляется m = m'S-1.

В своей оригинальной работе МакЭлис предложил значения n = 1024, t = 50 и k = 524. Это минимальные значения, требуемые для безопасности .

Хотя этот алгоритм был одним из первых алгоритмов с открытыми ключами, и вне появлялось публикаций о его успешном криптоаналитическом вскрытии, он не получил широкого признания в криптографическом с о- обществе. Схема на два-три порядка быстрее, чем RSA, но у нее есть ряд недостатков. Открытый ключ огромен: 219 битов. Сильно увеличивается объем данных - шифротекст в два раза длиннее открытого текста .

Ряд попыток криптоанализа этой системы можно найти в [8, 943, 1559, 306]. Ни одна из них не достигла успеха для общего случая, хотя сходство между алгоритмом МакЭлиса и алгоритмом рюкзака немного волнует.

Â1991 два русских криптографа заявили, что взломали систему МакЭлиса с некоторыми параметрами [882].

Âих статье это утверждение не было обосновано , и большинство криптографов не приняли во внимание этот результат. Еще одно выполненное русскими вскрытие, которое нельзя непосредственно использовать против системы МакЭлиса, описано в [1447, 1448]. Расширения McEliece можно найти в [424, 1227, 976].

Другие алгоритмы, основанные на линейных кодах, исправляющих ошибки

Алгоритм Нидеррейтера (Niederreiter) [1167] очень близок к алгоритму МакЭлиса и считает, что открытый ключ - это случайная матрица проверки четности кода, исправляющего ошибки . Закрытым ключом служит эффективный алгоритм декодирования этой матрицы .

Другой алгоритм, используемый для идентификации и цифровых подписей, основан на декодировании

28

Цифровая подпись

Многие из вас слышали о понятии цифровой подписи, но, наверное, не все знают, что под ним подразумевается. Так вот, именно об этом и пойдет речь в данной статье.

Для начала рассмотрим одну из ситуаций, где возможно применение цифровой подписи. Представим себе, что нужно очень быстро провести какую-то финансовую операцию — например, это может быть покупка ценных бумаг. При этом оплату нужно провести из одного банка в другой на протяжении очень короткого промежутка времени, иначе сделка будет считаться несостоявшейся. Легко догадаться, что такого рода финансовые операции протекают с использованием электронных средств связи, поскольку в данном случае невозможно использовать традиционные средства засвидетельствования платежных документов — например, печати и подписей директора и главного бухгалтера. Вот здесь и возникает проблема: а каким же образом обезопаситься? Такого рода задачи успешно решаются с помощью цифровых подписей. Конечно, указанная ситуация не является единственной, где целесообразно использовать цифровые подписи.

Общая схема цифровой подписи

Прежде всего стоит сказать, что система цифровой подписи использует криптоситемы, которые базируются на концепции открытого ключа. О них уже рассказывалось на страницах МК в статьях Владимира (Людена) Ю. Некрасова «Чтоб никто не догадался» и моей собственной «Открытый ключ к закрытой информации», поэтому в дальнейшем будем считать, что криптоситемы, базирующиеся на концепции открытого ключа, нам уже известны, и углубляться в них мы в дальнейшем не будем. Также следует сказать, что основной задачей систем цифровой подписи является обеспечение достоверности и конфиденциальности соответствующего сообщения.

Из чего же состоит такая система?

Вероятностный алгоритм или система генерирования ключей. Каждый абонент А получает пару ключей (КА, КА1), где КА — открытый ключ, а КА1 — тайный.

Алгоритм подписывания SIGN, который, используя сообщение М и тайный ключ КА1, выдает некоторое слово S = SIGN(M, KA1). Слово S называется подписью абонента А на сообщении М. В случае, если абонент А хочет послать сообщение М с заверением того, что оно послано именно им, то он отсылает пару (М, S).

Алгоритм проверки подписи CHECK, которым может воспользоваться любой желающий проверить факт, что подпись S на сообщении М принадлежит именно абоненту А — владельцу открытого ключа КА. Если CHECK(M, S, KA) = 1, то проверка подписи считается успешной.

Следует отметить, что для алгоритмов SIGN и CHECK для любого сообщения М и пары ключей КА и КА1 должно выполнятся условие CHECK(KA, M, SIGN(KA1, M)) = 1. Это соотношение определяет корректность системы цифровой подписи.

Надежность системы цифровой подписи обеспечивается тем, что только законный владелец тайного ключа КА1 может для сообщения М сделать такую подпись S, которая прошла бы проверку.

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

29