АрифметическиеоперациинадэлементамиполяGf(2n), заданнымивстандартномбазисе

Сложениедвухмногочленов^a₀ ^b₀ a₀b₀^a₁ ^b₁ a₁b₁^a₂  ^b₂ a₂b₂

... ... ...

^{AB= ak-1  bk-1 = a}k-1^bk-1

0 b_k b_k

... ... ...

^{0 b}n-1 ^bn-1

Рис.3.4.Сложениедвухполиномов

ПустьмногочленыAиBзаданывекторами

^A(a₀^,a₁^,…,a_k-1^)иB(b₀^,b₁^,…,b_n-1^),

где

^a_i^,b_j^{0,1},

i0,k1,

j0,n1

- двоичные коэффициенты

многочленов A и B, k=deg(A) и n=deg(B). Тогда сложение двухмногочленовможнопредставитьввидеследующейматричнойоперации

_{(рис.3.4):}

AB={a_ib_i}.

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

_{математическому.}

Классическаясхемаумножения

Данныйалгоритмсостоитиздвухосновныхшагов:

1)вначале2полиномаf₁(x)иf₂(x)перемножаются,ссокращениемподобныхчленов(коэффициентыскладываютсяпомодулюдва);

2)отрезультатаберетсяостатокотделениянанеприводимыйполином-

модульP(x),задающийданноеполе.

Пример.ПустьзаданыполеGF(2⁴),примитивныйполином-модуль

P(x)=x⁴⁺x+1 и перемножаемые элементы поля f₁(x)=x³⁺x²⁺1 и

f₂(x)=x²⁺x+1.Найтиf₃(x)=f₁(x)?f₂(x)modP(x).

f₁(x)?f₂(x)=(x³⁺x²⁺1)(x²⁺x+1)=x⁵⁺x⁴⁺x³⁺x⁴⁺x³⁺x²⁺x²⁺x+1

=

=x⁵⁺x+1.

^{Найдемостатокотделенияf}₁^(x)?f₂^(x)наP(x):

_x⁵_

_

x1

x^4x1

^{x5x2x x} _.

_x²_{ 1}

Витоге,результатравенf₃(x)=f₁(x)?f₂(x)modP(x)=x²⁺1.

Проверимрезультат.f₁(x)соответствуетстепенипримитивногоэлементаξ¹³,аf₂(x)-ξ¹⁰.Используяформулу(раздел3.1)умножениядвухпримитивныхэлементов,заданныхвнормальномбазисе,получимвкачестверезультатаэлементξ¹³?ξ¹⁰=ξ^23mod15=ξ⁸.Емусоответствуетполиномx²⁺1(пример3.3,табл.3.1).

Ответ:f₃(x)=x²⁺1.

ОперацияделениянамодульР(х)

Пример.Модуль–примитивныйполиномР(x)=x⁴⁺x+1,ввекторнойформе 10011

Исходныйполиномf(x)=x¹⁰⁺x⁸⁺x⁶⁺x⁵⁺x,ввекторнойформе

10101100010

_{ОперацияделенияполиноманамодульР(х):}

x¹⁰⁺x⁸⁺x⁶⁺x⁵⁺x x⁴⁺x+1x¹⁰⁺x⁷⁺x^{6 x6+}x⁴⁺x³

_x⁸_+x⁷_+x⁵_+x

_x⁸_+x⁷_+x⁴

x⁷⁺x⁴⁺xx⁷⁺x⁴⁺x³

x³⁺x -R(x)

ОперацияделениянамодульР(х)ввекторнойформе(вдвоичномпредставлении)

10101100010 10011

10011 1011

11010

10011

10010

₁₀₀₁₁

1010 -R(x)

Лекция17

ПРИЛОЖЕНИЯТЕОРИИЧИСЕЛ

ИКОНЕЧНЫХПОЛЕЙКАЛГОРИТМАМШИФРОВАНИЯ

АлгоритмасимметричногошифрованияRSA

АлгоритмRSAпредложилив1978г.3автора:Райвест(Rivest),Шамир(Shamir)иАдлеман(Adleman).RSAявляетсяалгоритмомсоткрытымключом,работающимврежимахшифрованияданныхиэлектроннойцифровойподписи.Всистемахсоткрытымключомисключаютявнуюпередачупооткрытымканаламсекретныхпостоянныхданных-секретныхключейдляшифрования.

Надежностьалгоритмаосновываетсянабольшойвычислительнойсложности:

-факторизации(разложениянапростыесомножители)большихчисел

-ивычислениядискретныхлогарифмов.

Сложностьвычислениядискретныхлогарифмовзаключаетсявтом,чтопоизвестномучислуК_о(открытомуключу)изашифрованномутекстуCматематическисложноподобратьсекретныйключK_cиисходныйтекстM,длякоторыхбудетвыполнятьсяравенствоМ=C^KcmodN,гдеC=M^KоmodN.

Асимметричныеалгоритмыприменяютсявосновномвпроцедурах

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

ВалгоритмевыбираютсяслучайныебольшиепростыечислаРиQ,равнойдлины(содинаковымколичествомдвоичныхилидесятичныхразрядов,необходимыхдляхранениячисла),которыеявляютсясекретом.ДанныечислаобразуютмодульN,используемыйдлянормированиярезультатов:N=P?Q.

ОткрытыйключК_овыбираетсяслучайнымобразомтак,чтобыодновременновыполнялисьусловия:

1<K_о≤(N),

^НОД(K_о^,(N))=1,

(N)=(P-1)(Q-1),

_{где(N)-функцияЭйлера(раздел1.6).ФункцияЭйлера(N)указывает}

_{количество положительныхцелыхчиселвинтервале}

_{1,N1,которые}

взаимнопростыесчисломN.Второеусловиеозначает,чтооткрытыйключK_оифункция(N)должныбытьвзаимнопростыми(использованиеалгоритмаЕвклида,раздел1.1).

Далее, используя расширенный алгоритм Евклида (раздел 2.2),вычисляетсясекретныйключK_скакобратныйэлементкK_о,такой,что

_-1

^K_c^?К_о^{≡1mod(N)илиK}_c^=К_о

mod((P-1)(Q-1)).

ДлявычисленияK_cчисла(N)иК_одолжныбытьвзаимнопростыми,тоестьчтобывыполнялосьусловиеНОД((N),К_о)=1.

ОткрытыйключK_оиспользуютдляшифрованияданных,асекретныйключK_c-длярасшифровки.

ОткрытыйтекстMпередшифрованиемразбиваетсяначисловыеблоки

M_i,непревосходящихN.

ПришифрованиивыполняетсяпреобразованиеоткрытоготекстаMсоткрытымключомК_опоследующейформуле(возведениевстепеньснормированиемрезультатапомодулювыполняетсяспомощьюсхемы

Горнера,раздел1.7):

_C=M^Kо_modN.

Задача расшифровки зашифрованного текста С решается сиспользованиемпарычисел-секретногоключаK_cизашифрованноготекста

С-поформуле:

М=C^KcmodN.

ПроцессрасшифровкиможнозаписатькакD(E(M))=M(D-операциярасшифровки,E-операцияшифрования).ТогдаM=(M^Kо)^KcmodN.

Рассмотримвопрос:почемудля целогочислаM,удовлетворяющегонеравенству0≤M≤N-1,выполняетсятождествоD(E(M))=M.

^{УсловиеK}_c^?К_о^{≡1mod(N)можнозаписатьввидеK}_c^?К_о⁼¹⁺

(N)?t,гдеt-некотороецелоечисло.Тогда(M^Kо)^KcmodN=M^1+(N)?tmodN=

=[M?M^(N)?t]modN=M?(M^(N))^tmodN.

ЕсличислаMиNвзаимнопростыми,топотеоремеЭйлера(раздел1.6)

M^(N)≡1modN.Врезультате,M?(M^(N))^tmodN=[(MmodN)?

?(M^(N)tmodN)]modN=M?(1)^tmodN=M?1modN=M.

ДоказательствотождестваD(E(M))=Mдляобщегослучая(когда

NиMнеявляютсявзаимнопростыми).Покажем:почемуработаетRSA.

ЧтобыоднозначнопоставитьвсоответствиеСиМ,требуетсявыполнениеусдовия

_{e·d≡1modφ(m), m=N}

_С=M^e_{modm;m=p·q;M<m.}

С^dmodm=M=M^e·dmodm=M^(1+φ(m)k)modm=M·M^φ(m)kmodm=M

_modm,

таккакe·d≡1modφ(m)

e·d=1+φ(m)·k,

a^φ(m)k≡1^kmodm,(a,m)=1

Необходимодоказать,чтоp·q|(M^ed–M)длялюбыхМ

M^edmodp=Mmodp

M^edmodq=Mmodq

p|(M^ed–M)

q|(M^ed–M)

(M·M^φ(m)k)modp=M·M^(p-1)(q-1)kmodp=Mmodp

(M·M^φ(m)k)modq=M·M^(p-1)(q-1)kmodq=Mmodq

_M·M(p-1)(q-1)k_modp=1

_M·M(p-1)(q-1)k_modq=1

Следовательно,p·q|(M^ed–M).Потеориисравнимости:еслиодноитожечислоделитсянаpинаq,тооноделитсяинаихпроизведение.

^{ВкриптосистемеRSAоткрытыйключК}_о^{исекретныйключК}_с

_{принадлежат множеству целых чисел}

_{2,(N), а сообщение М и}

криптограммаС-множествуцелыхчисел

_{Элементамисистемыявляются:}

0,N1,гдеN-модуль.

-открытые-открытыйключK_o,модульNишифротекстC;

-закрытые-секретныйключK_c,простыечислаPиQ,иисходныйтекстM.

ОсобенностиалгоритмаRSA.

ЧтобыалгоритмRSAимелпрактическуюценность,необходимо:

-генерироватьбольшиепростыечислабезбольшихвременныхзатрат;

-уметьоперативновычислятьзначенияключейК_cиК_o.

ДлянахождениячиселPиQизNпередзлоумышленникомсуществуетзадачаразложениячислаNнамножители.ДляполученияоткрытоготекстаMиззакрытоготекстаC,беззнаниясекретногоключаK_c,возникаетпроблеманахождениядискретногологарифма.Обеэтизадачиимеютвычислительнуюэкспоненциальнуюсложность.

РеализацияRSAпримернов100-1000размедленнеесоответствующейреализациисимметричногоалгоритма.

НедостатокалгоритмаRSA-существуетмалаявероятностьтого,чтошифровкачислаMвозведениемвстепеньК_oпомодулюNможетнеизменитьоткрытыйтекстM,тоестьM^Kо≡MmodN.

Предлагаютсяследующиеоценкидлинключейдляасимметричныхалгоритмов,сучетомпрогрессаразвитиявычислительнойтехники(рис.4.1).

ОписаниеалгоритмаRSA.Рассмотримреализациюданногоалгоритмадлячиселразмерностьювмашинноеслово(до2³²),задаваявкачествеисходногооткрытоготекстабуквырусскогоалфавита,ивыбираямодуль,соизмеримыйсразмеромалфавита(еслимодульбудетменьше,торезультатрасшифровкибудетотличатьсяотисходногооткрытоготекста).

Рис.4.1.Оценкидлинключейдляасимметричныхсистем

ПустьпользовательАхочетпередатьпользователюВсообщениевзашифрованномвиде,используякриптосистемуRSA.ПользовательАвыступаетвролиотправителясообщения,апользовательВ-вролиполучателя.ЭлементыкриптосистемыRSAдолженформироватьполучательсообщения-пользовательВ.РассмотримпоследовательностьдействийпользователяВипользователяА.

ДействияпользователяB.

1.Выбираются2произвольныхбольшихпростыхчислаРиQ.

2.ВычисляетсязначениемодуляN=Р?Q.

3.ВычисляетсяфункцияЭйлера:(N)=(P-1)(Q-1)ивыбираетсяслучайнымобразомзначениеоткрытогоключаК_о,удовлетворяющегоусловиям:

1<K_о≤(N),

^НОД(K_о^{,(N))=1(алгоритмЕвклида,раздел1.1).}

^{4.ВычисляетсязначениесекретногоключаK}_c^{(расширенныйалгоритм}

Евклида,раздел2.2)решениемсравнения

_-1

^K_c^≡К_о

mod(N).

5.ПользователюАпересылаетсяпарачисел(N,К_о)понезащищенномуканалу.

ДействияпользователяA,передающегопользователюВсообщениеМ.

6.ИсходныйоткрытыйтекстМразбиваетсянаnблоковчиселM_i<N,

i0,n1.

^{7.Текст, представленный в виде последовательности чисел М}_i^,

шифруетсяпоформулеС_i=М_i^КomodN,

i0,n1

(схемаГорнера,раздел

1.7);отправляетсякриптограммаC₀,С₁,...,С_n-1пользователюВ.

ДействияпользователяB.

8.РасшифровываетсяполученнаякриптограммаC₀,С₁,...,С_n-1спомощьюсекретногоключаK_cпоформулеM_i=С_i^КcmodN.ВрезультатебудетвосстановленапоследовательностьчиселМ_i,образующихисходноесообщениеМ.

Пример4.1.Проведемшифрованиеирасшифровкусообщения"ЭБФ".Будемиспользоватьрусскиепрописныебуквы(переводбуквалфавитав

_{числапредставленвтабл.4.1).}

_{Таблица4.1.Номерабукврусскогоалфавита}

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
А	Б	В	Г	Д	Е	Ж	З	И	Й	К	Л	М	Н	О	П
17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32
Р	С	Т	У	Ф	Х	Ц	Ч	Ш	Щ	Ъ	Ы	Ь	Э	Ю	Я

ДействияпользователяВ.

1.ВыбираютсянекоторыеР=3иQ=11.

2.ВычисляетсямодульN=P?Q=3?11=33.

3.ВычисляетсязначениефункцииЭйлерадляN=33:

(N)=(33)=(Р-1)(Q-1)=2?10=20.

Выбирается вкачествеоткрытогоключаК_oпроизвольноечисло,удовлетворяющееусловиям:1<К_o≤20, НОД(К_o,20)=1.

ПустьК_o=7.

4.ВычисляетсязначениесекретногоключаК_c(расширенныйалгоритм

_{Евклида,раздел2.2)решениемсравнения}

o

К_с≡К^-1

mod(N)=7^-1

mod20≡3.

5.ПересылаетсяпользователюАпарачисел(N=33,К_o=7).

ДействияпользователяА.

_{6.Шифруемое сообщение представляется как последовательность}

_{целыхчиселвдиапазоне}

_{0,32.Пустьбукве'А'соответствуетчисло1,букве}

'Б'-число2,букве'В'-число3.Тогдасообщение"ЭБФ"можнопредставитькакпоследовательностьчисел300221,тоестьМ₁₌30,М₂₌2,М₃₌21.

^{7.Текст,представленныйввидепоследовательностичисел M}₁^,М₂^и

М₃,шифруетсясиспользованиемключаК_о=7иN=33,поформуле

C_i=М^КоmodN=M^7mod33.

Получается

С₁₌30⁷⁽mod33)=24,C₂₌2⁷⁽mod33)=29,C₃₌21⁷⁽mod33)=21.

ПользователюВотправляетсякриптограммаC₁C₂C₃₌24,29,21.

ДействияпользователяВ.

8.Расшифровывается принятая криптограмма С₁С₂С₃ по формуле

M_i=С_i^KcmodN=C_i^3mod33наосновесекретногоключаK_c=3.

Получается

M₁₌24^3mod33=13824mod33=30,M₂₌29^3mod33=24389mod33=2,M₃₌21^3mod33=9261mod33=21.

Такимобразом,быловосстановленоисходноесообщение:"ЭБФ".Дополнительныепримерыдлярешения.

Зашифруйте и расшифруйте первые буквы своих инициалов с

помощьюалгоритмаRSA,используясвоипараметрыалгоритма.

Вопросыдлясамопроверки.

1.ДлячегопредназначеналгоритмRSA?

_{2.Насложностиразрешениякакихматематическихзадачбазируется}

RSA?

_{3.Какиепараметрыформируетшифрующаясторона?Какиеусловия}

накладываютсянаних?

4.КаквычисляетсясекретныйключвRSA?

5.КакиепараметрыRSAявляютсяоткрытымиисекретными?

6.Какпроизводитсяшифрованиеинформации?

7.Какпроизводитсярасшифровкаинформации?

8.КакимиособенностямиобладаеталгоритмRSA?

9.Пояснитеупрощенныйалгоритмвычисленияобратныхэлементов?

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

11.КакиеалгоритмытеориичиселиконечныхполейиспользуютсявалгоритмеRSA?

12.КакиематематическиеоперациииспользуютсявалгоритмеRSA?

ПриложениетеорииполяGF(2ⁿ)калгоритмушифрованияAES

В1997г.НациональныйинститутстандартовитехнологийСША(NIST)объявилконкурснановыйстандарткриптографическойзащитыдляинформацииправительственногоуровняназаменуалгоритмуDES.

СтандартAES-FIPS-197[5,14,15](варианталгоритмаRIJNDAEL,

авторыJoanDaemenиVincentRijmen,Бельгия)вступилвсилув2002г.

СимметричныйалгоритмRIJNDAELобладает:

-доступностьюдляоткрытогоиспользования(безпатентныхправ);

-низкимитребованиямикпамяти-возможностьреализациивсмарт-

картах;

- простой конструкцией схемы в аппаратной и программной

реализациях;

-возможностьюраспараллеливанияопераций;

-поддержкойлюбыхаппаратныхплатформ-из-заиспользованияпростыхарифметическихопераций;

-быстройпроцедуройформированияключа;

-поддержкойразныхдлинключасшагом32бита,втомчисле128,192и256бит;

-одинаковойалгоритмическойструктуройивременнойсложностьюприпрямомиобратномпреобразовании;

-базируетсянатеорииконечныхполей.

Стойкость-способностьшифрапротивостоятьметодамкриптоанализа.Недостаткомявляетсяуязвимостьканализумощности.

Авторамирешалисьследующиезадачи:

-найтиоптимальноесоотношениемеждускоростьюработыалгоритмаизапасомегостойкости;

-поддержкапростыхидешевыхсмарт-карт;

-аппаратнаяподдержкачиповFPGAиASIC;

-выбратьдополнительныережимыфункционированияалгоритма.

В табл.4.2 представлены сравнительные характеристики двухсимметричныхалгоритмовГОСТ28147-89иRIJNDAEL.

Таблица4.2.ХарактеристикиалгоритмовГОСТ28147-89и

RIJNDAEL

Показатель	ГОСТ28147-89	RIJNDAEL
Размерблока,бит	64	128
Размерключа,бит	256	128,192,256
Архитектура	ОднороднаясетьФейстеля	"Квадрат"(Square)
Числораундов	32	10,12,14
Частьблока,шифруемаяза одинраунд,бит	32	128
Размерключана1раунд,бит	32	128
Используемыенараунде операции	Сложение,подстановкии сдвиги	Использованиеарифметики конечныхполей
Размерузловзамены, вход/выход,бит	4/4	8/8
Способконструирования узловзамены	Закрытаяметодика	Алгебраический подход