Аналіз стійкості криптографічних систем з використанням штучного інтелекту

Дж.Моборн запропонував в схемі Вернама скористатися ключем, згенерованим випадковим чином по довжині відкритого тексту. Цей шифр отримав назву смуги одноразового використання.

К.Шеннон, досліджуючи шифри, довів теорему про існування та єдність абсолютно стійкого шифру. Абсолютна надійність досягається використаням ключа, що є повністю випадковим, рівним за довжиною відкритому повідомленню та використовується тільки один раз. Порушення хоч однієї з цих вимог створює принципові можливості для розкриття шифру, хоча їх може бути складно реалізувати.

Бачимо, що шифр Моборна задовольняє умовам теореми. Результатом його застосування є випадкова послідовність, що не дає ніякої інформації про відкритий текст. Проте складність його застосування полягає в необхідності обміну ключами. Для цього по секретним каналам необхідно передати інформацію такого ж обєму, що і саме повідомлення, тобто шифрування стає, взагалі кажучи, недоцільним. Тому такого рода шифри надзвичайно рідко використовуються на практиці.

1.3.4 Програми до параграфа (редактор VBA)

Програма для шифрування/дешифрування шифром Віженера:

Private Sub Wiziner()

Worksheets(3).Activate

Worksheets(3).Name = "Wiringer"

R = Worksheets(3).UsedRange.Rows.Count + 1

Dim Mesg As Variant

Dim key As Variant

Dim Cryptg As Variant

Dim U_alf As Variant

Dim Len_mes As Integer

Dim Len_key As Integer

Dim Len_alf As Integer

U_alf = "абвгдеєжзіїийклмнопрстуфхцчшщьюя АБВГДЕЄЖЗІЇИЙКЛМНОПРСТУФХЦЧШЩЬЮЯ "

Mesg = InputBox("Введіть повідомлення") //приймає повідомлення

key = InputBox("Введіть ключове слово") //приймає ключ

Len_mes = Len(Mesg) //встановлює довжину повідомлення

Len_key = Len(key) //встановлює довжину ключа

Len_alf = Len(U_alf) / 2

Dim Key_cfr(20) As Integer

For i = 1 To Len_key

For j = 1 To Len_alf

If Mid(key, i, 1) = Mid(U_alf, j, 1) Then //встановлює порядковий номер

Key_cfr(i) = j //в алфавіті для кожної літери ключа

End If

Next j

Next i

Cryptg = Mesg

Dim k As Integer

Dim m As Integer

k = 0

For i = 1 To Len_mes

If i > (k + 1) * Len_key Then

k = k + 1

End If

For j = 1 To Len_alf

m = j + Key_cfr(i - k * Len_key) //визначає величину зсуву

If m > Len_alf Then //для літери повідомлення

m = m - Len_alf

End If //замінює:

If Mid(Mesg, i, 1) = Mid(U_alf, j, 1) Then //малі літери - малими

Mid(Cryptg, i, 1) = Mid(U_alf, m, 1)

Else

If Mid(Mesg, i, 1) = Mid(U_alf, j + Len_alf, 1) Then

Mid(Cryptg, i, 1) = Mid(U_alf, m, 1) //великі - малими

End If

End If

Next j //виводить:

Cells(R, i).Value = Mid(Mesg, i, 1) //літери повідомлення

Cells(R + 1, i).Value = Mid(key, i - k * Len_key, 1) //ключа

Cells(R + 2, i).Value = Mid(Cryptg, i, 1) //криптограми

Next i //в окремі комірки

MsgBox ("Зашифроване повідомлення: " & Cryptg)

Cells(R + 3, 1).Value = Cryptg //криптограму цілком

End Sub

Програма, що підраховує кількість часто (більше 3-х) використаних k-грам в криптограмі:

Private Sub An_let()

Worksheets(3).Activate

R = Worksheets(3).UsedRange.Rows.Count + 1

Dim Mesg As Variant

Dim Mesg_f As Variant

Dim lit_f As Variant

Dim Len_mes As Integer

Dim k As Integer

Dim m As Integer

Dim Len_lit As Integer

Mesg = Cells(R, 1).Value

MsgBox (Mesg)

Len_mes = Len(Mesg)

k = 0

For j = 1 To Len_mes - 2

l = k

While l > 0 //перевіряє, чи не зустрічався даний

If Cells(R + 1, l).Value = Mid(Mesg, j, 3) Then //уривок раніше

l = -1

End If

l = l - 1

Wend

If l > -1 Then //якщо ні, то

m = 0

For i = 1 To Len_mes - 2

If Mid(Mesg, j, 3) = Mid(Mesg, i, 3) Then //підраховує кількість таких

m = m + 1 //уривків

End If

Next i

If m > 3 Then //якщо 3, то виводить

k = k + 1

Cells(R + 1, k).Value = Mid(Mesg, j, 3) //уривок

Cells(R + 2, k).Value = m //кількість

MsgBox ("i=" & j & "m=" & m)

End If

End If

Next j

End Sub

Результати роботи програми показані в п.1.3.2

1.3.5 Завдання до параграфа

1. Записати програму, що шифрує та дешифрує шифром Віженера. З її допомогою зашифрувати (розшифрувати) фрази:

а) Реве_віл_на_сто_гір_на_сто_кроків_на_сто_потоків. Ключ: грім.

б) Сидить_дід_за_подушками_і_стріляє_галушками. Ключ: град

в) Сам_не_біжить_стоять_не_велить. Ключ: мороз

г) Мене_просять_і_чекають_як_покажусь_утікають. Ключ: дощ

д) Жлйтдфзалцшошайшьйштншйалцшлнчєуаезбмьтїмїза_ймї_филш Ключ: миша

е) МуувлгхьзофбдлшмєббежжлгхцооксоешвщКлюч: бджола

є) Цієфьрсьсфдрвчткешцфвюеерм Ключ: віск

ж) Тєрсйєуеуїбтейзвфндєрллаугрфжфймряцдшєчш_ег Ключ: дерево

2. Записати програму, що аналізує текст, зашифрований шифром Віженера - визначає кількість та позиції однакових уривків, розбиває текст на вказану кількість стовпців, проводить частотний аналіз. З її допомогою розшифрувати текст, зашифрований шифром Віженера:

а)бьутлвтячрьчїь_тсвбєьшатмпрфн_дтьогпитдтщпфумврчгєцбчгдвеохямьрфн_ятіпбячюрьндітіпутіпбичєстжвбачуьїеоеяяддізьрімпбачрсцшєдтдезачидгисьвчсеуьоітмншвнотяяжрегнатїфрдгтрчзнрхлшитп_ьфшощуквтамьручєіїчядьївфєчкцтєодчцтгимьрїкфтучгдчшсжсчрьчїь_тьожхгєрннясїеозужвфєччсзирьїжжроиррдицгучрігиоезитдчнссїеохямф_тпвхаьоиєяьутш_цтквтємьрїшяд_чбьч_огшччгупвхаьоршпохиіпчтлвтячидгисьвчідмчрятьокєкєствбсбт_сіцоєєщвзучюрчиогпитдтщогуєбпхлнржкьрлеірчнааупогувжжїкшктгуцтььжєжь_тьжжумь_тсвбєь'пцшостмврфнсре_окєзвуяжостлпвтсвєїчяічео_ч_йрми_дхгицтйьзуаолижпотвпєєщшзвнотєчуіь_отяяжотвожяі'чрчнрїирьтквтємжрчшарвшццтсвєїчєстлгцзтжрешарїкфтучсдцибнтквщжш_яїеомєщощхшдяїеоюьноьчеоутзшжтгоезебціеохищпрїшоеєщшбптвфєчсьчсжутсвбєьшатуврїнєроиентїфбуябцтмпрхлфрьчсрггержгйдхчідїгсрхмфаїеозучгдчнасхчкдтсвєїчсжшчвхеио_єюврюїп_ч_ожїшсрешоазшмрггеітйддфнхрхедуумьрч_дцхиозучуцтмпвтьвгєчюре_оуєкжиен_дтюшбгцарімпутсвбєьшатжвєиччрч_дцхшодфяьєумьрєщуязшсрєщуязшсручгдїгархвнутівзивнаичюржиисхчбцрчвтх'нщиьпзачуцз_сстйдябтвутнойшєокулокєкєрячгяїшхроиозачддфейркииітьфжпч_ьічєдфгогучсдцибнтйдяе_езачбцтщжхичцрсчєдфгоеєчуцз_сяершреиеяїеогузнауьептсвєїчсязьпутлпвтяфєшьврхвнутїпржзфкшчюржгйдхчгдмьпбуьощучбядчшрми_дхгярешссзе_ятдезачгд_зьрбчясь_окєкєрми_дхгядхгостмфешкохуьп_твозєщвотщьзалнрхе_ддеожєщшржш_ялхостцоуазввгхожєщшрхе_ддесрфгугсжоутжжмупошшкуяенокєкєрхедууьоьюччцдзшрч_дцхиоєєваскнхрееаричгдхгєєячбсм_оєєвтдечбсфедсщчнре_оиєсжрфеєяіцогучгдггоиєсжрфеєяіцозязлаачсркшєьтжпшшчидгисьвчидзмогясвфєчбцтішфтйддїеойпитдтлясюшєятвтдчесжсчпбшччсбмьрчиоиумьрючуцз_сяеимрмидзтїфрдиццтяфєшььгучбцтьаьошхзплнрїеармшеддчрьчїнатяпууєоешкшмамьрбитдтбфєчебдрчгяоеєнтьфєшуьзпчидзмоезиеяїфоеєупхамьржийаєяжууьо_єюврми_дхгярхгуеилєяхчбстядіцеюрч_бнтйвжгшсрмидзтсвбєьшаучгдтьвхичєстяпутмпашчсьчквроиобшясцтйвєєббчтявгялохєчяєаїьйячуідшсрфгугсжохиіпутуврбиаітквтамьрбчгдмшсрєщяджнссїеоазебялхотусьзпчидзмомєчидгисьвччсфшдяхлнрбчгдчшсжсчюдциоєєвйівнссїеоезеюлєьоьтщпкамлрми_дхгярєщяджнхрвкьгармроиойшчєятквтатощчесіхшсжсчидзморїшоуаяьлтуврвкьгармрєщяджнмроиовшїшркиуяїеоушллрмшерючїядчсьч_дйшіоеєчсдчноаєзьрсчадьнойязжрвкьгармрешовялїцтйдяе_еза;

б)фйфпкпсіашячілцкеює_яазолпьїбщцокєарсчачкепмцксзцящвклгквкйюкбіамлбкфаєшзряодіглсоіапажййчкеффелхзлящьзтрквкйюкшзллтфзпчкрщбвцяяамфуіабьфщуїкшкєклоипюяоїбжцєланкеює_гоюбшкчкбщряіанцуцпкюжзуяккчашлцлавяюзулксчолкцзолбошпбвьцбскєпллчачаркбпамапюєкюфзряпвїбкшвобшлазфвфяіуцкєіачкешєшлочокйяіажядю_жлоцєкпжнєкввзкк_шквфтьгамгулнкгцлабцупуїкдіікьпюйкюпзтнфєзсяпьфбкапоафкгчнцапюйкжьзулшоюпкчоюбшкесейвлзолпштщщлоьнраєеафкяізркоччркюзеямдлаіяожанлезгящвбяокешївшпфбковкїкнпхаог_жуцкєіааячупзгсіуцкжзщянячгцеонф_лбіцкевкйвцоюбкьфканцбча_цєсаяблз_кнпьафуоьгфвжзітрбяашяечяковфпнцошпбвьцбикеюйюлюзллтфзппцбзляупуаюлоюпквсч_кбьфбкчоипщйоюїщїясаплюзнрюшзнцщвьуцнпзрлюшзррафкабьфщуик_ємїшжзряшжщйвцоцфкшпнєкбалсвїоупщцоюйкьфцєкььфпбвьипикгіориоцбунпиавяоизркяясцкечвфксскюйсзляупуащи_елгкєіайшообшгдсгклоюявибзеямджшцчохїєюьтайшошїзясзппкючдякуяцквпзецьоюпкбалсвїоізкюпїїшквкїчз_іаяєфзллтфз_шцюзряопцйчкуяцкйязтркєсавляяа_ятіоїкяясцзоюбківззкшпнєкшвобшкєілкьфцїкбжкзрювз_шкдчіфчйчгбйокйькєіапгізтьрдююкубчгк_дствггсмлкбяашлцла_яяясцноює_рдз_кнпьаямваа_яеюйюлмзтваьибчкасмябєсглкгіофкуіккфохєюфошїщїтяашлцлапажййчкячілшокпунвфюкьфцїк_фщєпкехєавмзулмпуйк_вцяелєсаюиііккшпнєквпзіюлюзняиокпмашьуїксскюйсзуячоупулязсфтяіамрдла_ябєщшгоіаблазегьпмайшоїйкчвхфк_дсінреюйкбалсвїодпмксчолкгчоиепфбкюмаогноцбкяусокмшуаюиіцфнкбіапажййчкящєшюжиамяоюбмляіамг_іапярщєкупшслн_лолкєінкпвзорхоїфщяотажралсцєшзкквжщдгюжзкк_фщчикучелювзещйохпєфодпмкжзоябшзлагєсмякіпвлкцзгяювзеямдла_цєіабьфщуїкєіайшоупьгоубтроупулязбюгокбчкешсямжибвцошсябьююкбалсвїоцбкььфпбвьибк_пцїкйязоиебямлкехєавлз_шкчілагєсуїкщтагкбчтфкнуажебланябіалтоупбгоиргбєсмлкїясктфзкяьжзллтфз_шрошполблаірошполбпщркбпзкввтапцазїкйязтркєсавляла_леуфпбєипкнцсглсйзпвляз_шкрішцзоубтроупулязрацюхбикаялгкїпмцчоиїшкрчавлязфтрохєюфошпаярфєюяовйкюпьмлювзвяоотпояооолкаящгкєлс_фєсалкяізркехєавлзлящьзулшоцєкмжкфктожанлезлябвєабвьцбвцоюпкюфзщвгяіаньфщуцкпзпвкєсажептафіфзр'йєкєбйєзмфвочуквпуйькисояьопанцчипщц_стйкячілшьзгфпоцбощврабьфщуф;

в)ноєнюяаиибр_яитцст_цавїйкфсущшяосцкгааялщьтхяовталввтхкьпдйкввтчцзьгфкчвдбкбєуягкіуашгояиоядєнгк_уашгоуинкєєшгкешчфкрилкпшчфжкеїбщїаєяплогіпцобьояоєкеяуачцкуш_йвврипядємяиофькюшкаякчтщцьоеокевїтнкауацкуєецюшещйкнвьбїочтпцит_влстцящвттнлбвьнящтглвьтткшдацюгстйквьтгвяоїйшцютїкбвфткфсущшяоуиюлкєивяряиелєуивлооокчоцьаяутбкепїтктьхбклоюиоядєнлктєнгиеси_автдркютнгафезкубупк_пеи_яуишлнояибшпюйнкшчфкпвтшрюфтвфааущяьофькєфбиоядєнкйоюймцдуікюптщїяаиимгуши_леяцлкіяклкжтллбожйюяивбкьпгькбсємякгєчйктзтекринрвфтшлвьтмафітщлчоянркстшфеоюлраіииьляємяювдиюрокьжрйткгвьтвфааущяьоїькупффалюіїкфчт_рщпттнлбвькюпжтшкеєкфкяуявяггїюцяялкшьебнкжтаяаращгкяячїшптїмщжвифкгєшлюузбнлстщлкршяруштюагєии_яруецноьбалсвбк_шчтчзвхилкгїйелоеоквшвйсксюїнкжтягшьтцац_єи_рдшкцвфтляюптюя_дє_цщптня_вдьтцогоґфбригтфтю'йєпипюшхибцуьбквжїиоя_єнюлофькапефкмвгївїояллюяєи_яаалкапефк_взллноіьаяивбкчожоарс'їулстуексянвлятсщясалкгожягвштяцмяиичкбумяпжхйнкгїфєиокьвфстсаяраацкщбифкіуашгоучркєячїшьтюфпшбєяночьквдєжфкєєи_яиилкюфтянцодоюрогоґфбримяодьтрожяцчушивяютжякнтхяовтершприлкєаиіяоюйкяуейкпшхецюптааяеїфюшптцяовтершпщєкбсємяксасня_аарщнтйюгожьшлца_йктєчябохтп_вхтнкухйкапюфкйохрркгєцлужхйщлесивлооькуоїьояосцк_шнчцкєуцкфоеоьложькблємяпбяєюфютнрюлтжркаєргкгєцлупїфбїоєнцюощнцюьбиалчтьбвпещфчозйукашщфкютюяшпьфбїофтоьфтщрквфнгамтщгкуєкарочфнцесиюлохоазфмьшкєзьіфозй_ввдифнпецякгєклжьхи_рдшнкбвфьикиуяфнбиипфсмфюгохьюлофбщлоїйшлоййчюптїшкгшязловлфвяуиюлсш_юфоучркуирркеишюломььгоїфкбждщлкашщркжвялщптлфпофйвїяялку_уинфупшлкієафщптжямосинфучйщлепиуло_укбьейкнфговюнтїкюфт_еяєячлкштлврягйкбієллщпіїкнолтчкєзьіфохтпїауиьрбшиуюпбєщлояиямфзщгщптлквдє_вцбвбклраиьрбшинцчхьщцєаиваффйкньвялбєаиьфютюраеїоюїояи_яягйбвьтхяовтщлксшязриєцкфочтнжьейкубацщлохьюлочбтроіюяпвфйщлесиюлйєшгкшхйюшвхткфохфафйалкхютня_вдьовьтюянфзщгнесипяоьбалсвфкчовйтроейькєзомлозьущжмфвцесишгуаи_фушєкбгаалщптргапхцлкгянгкйицлвьтаркгзьківтщркаєрюлоцьнядаацкбухкввфткіпіацвлт;

г)фі_іихриічєушейтздгиіябгичупхяєщжжщаиоциїєфктбршшйеруляеяюхкузлеьтюіхюєхшєфхріцсс_еклєвокйт_олшшєоїтнбьхліьочяузьхжужєфиніяцаарєбчпаьхяєщжжщярешьщріцсс_еклєргіцахпєфтхвжйтсошияупзйтщонйюпюйахсочбгсоінесойаиепхауаоштершхаирчх_єтвуихщншияхжкзтувзфтзпххтьулапршхльцойаубвх_дцдейїноьтбл_гичдоєтііокйт_оейьієтичссцхїцошфгьчюшєрбцичірциїсоїозцбіеичаіиурєіиодрхяєщрбхеяягиецозйжс_гиєхьзияряцршрпхдпдтіичідзьцдочтісоьотхшзоддоаиізжїьрршшйербциїцоьбдсюкотщпх_штфхйтпоййдрсгчящжхщурулкурєцибрчцщєкжуижд_бсгяоиьюіазттсцхщурецша_ошозлвеичірциярегнсзлхйтьсцщтьойьфьоєтюцоциюсойьфдмхттжєлюирєфмецозйтхжчйтуьєтюрегназлхттжєлюируюяьяєтиєзобнизлхяєщрбхеяягиюрешь_иоїяєвьйчяуокйт_ойаубьхщєкжшйїноїтчрєгштхжчьдрбцсфядцчаруиьхреікярчцеубьхлуєькзтіошогяяіширяцсугшхцибшриесошомцдуиессцяабьхюєжшьйгяоеяифвживсчцщургікзс_гигдцефтзпхаяблефтмвх_їс_ги_жєгиїсош_шрекбчпєтифдоьбьцощйзпигхттжшиуршшйернеижіекфїнойаиежхаургиїддошивсчцщтаьї'скфзфбрялчялощоїнопфізвхюєщпєїжісцлтюахьмьошьеяоаигпялисаоїьіисцеиупєфіпокйт_озбтзшейїнолигьехсутжєфт_окьхсдхцєздгхтгпщяутьєфтуоеяувпитхршшйерєінярчєтюрчхнитпхаурюхцушфхкзсєцштбшазїцоььчд_лифєпкфтевачущьєфтщпчяубьхбхцетиїдсцятавзттьоїь_ипєфтхвььдіоцияупзиищншиідрбиїь_тцареіюябялиищншихьбхаиреіюябялиярблицєпкзтсочбгсокйтжвїтгапхщшргиьізпхйткпитхгпхїврчцмзсххауаол_шрцглшрюхаугїуптдєхсуфдцлтьсцщтзпеияргбєгдош_шрєцщлосцапршхлєуягиярчцхльобигяегдярюхлшхаюнярпхтхсбхліцощяурєциівшяапжнхбьцокттщсбяяреюячцйзттзпздрупєфтзпздрупєфтьоїьдддгчажлхбьцоайтхфиохсонлузпєфінокйтхфирубьйзтмвчиецокйеймшйїнокйтгшхщшрсьозшпкзіполшєєьш_сршшйер_бмтушьюєкьшйїнокяєиьхьчхьнщиуйгихжєцлтьоїтндсхбтфвиьчр_унарецшшрбю_гяозйттпайзргиьчссцапрікьтепєїеяїбикзвхцзсйцщвяошивддікльоцикзвхцхсехбтушьяуиоблугофцтщпщяууоличіуіевіокйвршхюял_гихжшхаугїулузлхьчябхеєбвштврбб_тавиьфажхїщйлхаургікауовгткьйаєрєцщломпфтьоййдрнеимддкївсолкзссйїтуофпмгмхаяркіиіепєфтевйгхсиллубьйзтзпхнуупдияреікярєцщлосцапрікьтфвєфбргіиксєбикзвхкшщораугшшикзвхкшщойьздиефтсонаєррюстжгбнеяїбижьйілтісю_пртіяєхоїозцсюяїдахттжвчйвяобиіуьзттьоебзяош_шриг_їдосьттжєьтшьшотежйаабвйїтзпздрупкф;

д)хйвзуціає_ньуібеицотїсбтсюркгбфзасйнгіцогм_блчохшпсорощм_мізасйноехпбшнруьєдсннаиобрдф_ьпх_нї_шпжшрйщіосізфдчряірйдсадічанлсялщнозтєїжалєряйнцокьзтноазгдхлгацбпітояхьрящзнжаяіпмуупуіцаряйгтієюзгдіяїсііррнрофниіеб_цшашяй_цфрпоцокьуітп_ьєєїиоойврхчтузчуртлизбьбеп_цфрцчд_иь_ящакч_яівпсюпєрраміхзшюаплдцлог_юднш_ассбсцнї_юпаіабкічійог_ььгтннорощїяйшімрюрїйзаснепкзбсірбсзжеьоглжюзмноихоьіхййюфрйнігчуьірй_кссідуащйьі_їруж_яуазіовшяпдгвфшнвозсьчньез_цкюпдяагтьанлгдюяфшць_ієшиюьжзноезідгуатп_нфщабзчсиоглжсжзнуазрьлєарчряйнвещфшрею_твфшнлофьрщчееюфрчоапч_ойоонжовшхєтложягїлжєяіцгіщьг_нг_яеьбнцадпиіеїлеяяірбряюзмд__ьєєїиоойврхчтузнрчолаопуівпвпеяящаніобрдатірбтїлузчрчориьввійпбзєілщанпізшноезевррахчуяящаазядхщахювжєнпсхшбтртязррпоктсоштрймзчуртуизбцівпвлдгмеюсжофьох_шввмгахфвевчазі_ядщмиьнрштоізбсу_плчултьавнфрчуассуяякадчасіає_йдснеюсжоуівппл_ьіпп_впжябабптсннрозісеоц_шврюоеааоьівплжірчогіюлрштоімщркбеицьрчуапчеялщуьзбсі_їсбшрйдє_цпрчбдааогїноойпиізпчзудіилофьрчуахчуяйншиюпзтнриьпзтноаиияйд__квтьуавпуригбтпср_ндрізсіпфлчотїсбтчожхєд_поєшпїтцьаррасюпєдчассбяіабгфнхїяй_опрчщнизадхбешсюрчуажядяйд__цшкт_аплдцфщоезрійомозицьуі_ш_цгуаряйгтія_шшхмнміьпвтнрофнвтнцокьуіюфдсоиштйвзєсідурійгшсп_фшж_нпсюфєрсбвьнрибасфвуїнваюлаїнрах'пяог_чугшсп_щпщ_нврієяііїлсюрлуоьзідлщмиз_ьюбн_швбжрблсоеїнівпдячєаяуожягбшцвфшнміьжрчуаблдцкяйсжоеш_йлс_яюмаізбцюоноашзєніатйбтнеозбншсп_кьухмуььнрпрїрсбяівуаашуіефтзддпрєлчепідуіфлатньозгьлнлонбяцнлудфвівїдзядоаймзуцьугохощїфчьзесьаб_ч_цчкадсяяунлаїпгіяядсожжтй_цшашяй_цфрпоцокьбтнівпдячоамцвштябсжоихбрцпоешвблсохшнттщплчбдоз_ьюєавщпгвчаізрб_тйлсоешноьчаіііїлсюрлуоьзгдібвікшрчоурігяхщаніоаьщоибмрпншиьєджнгоквоіаєді_цфбапщфаьотнчтдімгощпряєу_їдсящасп_яійпсеоемгєкяеяящаізсьлвпчсєяіабплябтнн'жесіабпс_яюмасишшшшавчуяічаряйяхщаді_ьійє_хпбшнроавхр_амчццімлуьлрлщгняощйчсицжрюесіюьвшнб_швгїтавлиььнрікфвшнеоквв_нівпдячщавз_ьючадчезїеоьчожягїлжмзєнврієяідлліусжею_цпркгпміуяіебкзщиіцбсюпбїнї_цшкіцїбщпбтд__квхш_ф_чтбзтбююлжзндлжусжею_квєшсф_іощчоктсохшгпгяогмннонжзєнцокнзєнтюкьряєеизрькоятеозїннащбдіабчлоюцнцтченібшізчсй'_зісрббеифьрияфкі_яітп_юфвчби_цвкрнї_обдйєапчгсхщадчоаьщоибшрщче_жсдьбн_цпрлусеишркчмлжожяумиюлжзнщищвашнб_иоаьщоибшрйбеазияюеб_авбштоазддпвблпаряєу_ивфшаю_квєїтйлсепіпсаюьрчоревшвідпбпов'мтазшрщусецвк_ьнозпрчоазчдпбніблдццбтязшрщчеехврлбеохжр;

е)ещваянпуяяаєзпямпьилщуттшьтісяобсбядбзждмєлукжтотпкіїдяібщшяхпсхзйазакцоюнїзаттшьтісяхпсхнйпсіобсчм_їйзпяяпдаянрчздубварцаіуязажєжекмгїнюсо_нуртоещвєяпавярщбсзндфгтоещехяобсєгйпгиясмежцжлехзщїсхкеісия_пвєбпаеїяяїцч_вауусцлетскдетфїпємїібсияфєфлзщрефтяафямщфсндячркядаіаєаєдпяпзчтбнюедтщксе_яш_хршаечгькішяібщшяобіияхєсмнифсчппдедтщгласжтотбеецубщкецнщвтїщіпсияістххеафямщїсї_иалаялпуибщісїїгечещщфщшядфгябщїсжнісе_сжаютокщ_їїщуечзщгючгьгсбн_псф_оюбєяяш_їїнюсодщдечїйо_вїщсефїойсхзйаютскдетшктотріпжєяйбфмїятртноажужщуебязпхєясбьсійафяг'ищчєьжсуяяїдтбгєсе_щзтгтябдезщтвиєжгсї_щксе_ібьиещцвєотєфяяхпутбеосжнійсїнзафшпйєіпршаьзнюйфтроївпйжаіулщдечїйо_взяаттшкаьєробдшсцтртомйєурпаієяшлсіфкшчтскаютрквютжмпуасцаеїяяїдтюіаьуфке_хршащабкаєєпкв_хяхєсбянпуяяяйхугьгсї_щутвїзаїїмпгсонщфсчбьекссцає'юоюсзніїфтсемовїщстюяеаьубке_їщн_сї_щ_бтжьгюхяопсяяімпмїіаіигжаїідмєцампаьуфкгтхяеаьуцжо_хяобгтомйяк_яаеіщщцтююєосирбаєєпкввшмкафямщітфпьгсїзщдечїйо_вїщуттищрехздацшрцадуяшсгупклсяязпхєядазєакясижшгсїнзащшясбьсійазхнєахєгжодайжажєжлсеч_яаієялбдулщуетзйщ_дяїяцслщбсїнзайгнлєкпянгюбялсеч_яазулкнїтхьсчхзщуттюіаьуамбфтвмпмяяопсбялїмєбщечіщщбщтжьахз_ййкряьаієищдечїйо_вяшлсхїзщвєязпгияагтчхшуото'_іпямпбябщіїжїййфіющїседщв'щядбжужщреікьм_тжьагуинужєлщутвяйїйїнщстчїщкедтщочтгьтіпяійдикжтртгкаієвкайгнлчрт_щржєяйюецнщшїїйьафьдщтбзздюсжзфмттбеоссйщржаісбфтскдетйїялайьаьупьісюмькмєбщїсюмкгїтмьацх_ачрїщщр'ссцажєйегсжтну_хятбжтзщрегьюйфтикдетєжг_тйьзчттщнчедщетхязпгия_пжеїтясяялс_ікпдїттнєсмїнуетноажужщчтзяяїц'ігещуещуттищлтьдщкедтщфзргжайєгжаттнйаїтспабєлесбияйєскнайсуяобгтжьазїзйпптапмттжьнїзнябдуятбжябйбсїнщиятрьнсл_маіигжаьулпсїх_яаютфкуюхяхпутієаєєжьпляянгтї_їйскскаєзїєечтрябіусжаієязечттщуїтйкнюзйпаіуязауукьлтщяапседєабзздюсісеоїтюіафємьаеюббуоіющуетжьаієвкаябяеааїїщпітроївпйжафьдщчтззяаютюіпхєяїяцияйєсжпжиьчїїпсезщеетйкдетбкоттмбаеюїябшїщн_суяіпвєяоййтгяєжшищутвзщтієюїйсонщуюгщійссйжксюяоїш_яіпгяпійсхнййсю_мбьтвкмехтщкедтщіжиаьяіпяобсе_щртгьщїсе_нужєлї_іпяоббтнопсл_мааєвкамвнаффубщуттищітв_дбфтспе_тфке_їїщ.

Розділ 2. Алгоритмічні шифри. Системи з закритим та відкритим ключем

2.1 Блокові шифри. Стандарт DЕS.

2.1.1 Загальне визначення блокових шифрів. Мережі Фейстеля

З попереднього розділу ми знаємо, що криптоаналіз класичних шифрів програмними методами виконуться досить просто. Застосування перших, навіть примітивних відносно сучасних ПК, ЕОМ з програмами, вимагали нового підходу до шифрування. Розширення алфавіту та збільшення довжини ключа давали незначне покращення стійкості, або так ускладнювали процес шифрування, що він ставав недоцільним. Тому програмісти, що розробляли шифри для машинного виконання пішли іншим шляхом.

Ще у шифрі Вернама (1918р.) замість традиційного алфавіту використовувалась двійкова система запису. Уся інформація кодувалась послідовностями з 2-х символів - {0, 1}. Цим же скоростались розробники перших машинних шифрів, тим паче що будь-яка інформація, з якою працювала машина, вимагала подачі у такому вигляді.

Послідовності 0 та 1 розбивались на блоки по N символів та опрацьовувались кожний окремо - така схема шифрування отримала назву блокової. Як правило, N = 2^m : 8, 16, 64 тощо; зі збільшенням довжини блока і відповідного ключа підвищується надійність шифру, проте ускладнюється процес шифрування. Отже, N-розрядний блок - послідовність із нулів і одиниць довжиною N:

x = (x_0,. x_1,….., x_N-1) Z_2,N

яку можна інтерпретувати як вектор і як двійкове представлення цілого числа:

x = x₀2⁰ +x₁2¹ + …+x_N-12^N-1

Блоковим шифром будемо називати елемент

SYM (Z_2.N): : x y = (x),

x = (x_0,. x_1,….., x_N-1), y=(y₀, y_1, ….., y_N-1).

Вираз:

у = {к,х}

будемо використовувати для позначення N-розрядного блока шифрованого тексту, отриманого в результаті шифрування N-розрядного блока вихідного тексту х із використанням підстановки {k, що відповідає ключу kК.

Одним із найпоширеніших способів завдання блокових шифрів є використання так званих мереж Фейстеля. Мережа Фейстеля являє собою загальний метод перетворення довільної функції (її зазвичай називають F- функцією) в перестановку на множині блоків. Ця конструкція винайдена Хорстом Фейстелем в середині 60-х і була використана у великій кількості шифрів, включаючи американський стандарт шифрування DES. F-функція являє собою основний складовий блок мережі Фейстеля і завжди вибирається нелінійною та практично в усіх випадках незворотною.

Формально F-функцію можна подати у вигляді відображення

F : Z_{2, N/2} Z_2,k Z_{2, N/2}

де N - довжина перетворюваного блока тексту (повинна бути парною), k - довжина використовуваного блока ключової інформації.

Нехай М - блок тексту, зобразимо його у вигляді двох підблоків однакової довжини М = {А, В. Тоді один цикл (ітерацію) мережі Фейстеля визначають так:

M_i+1 = B_i||(F(B_i,k_i)A_i),

де M_i = A_i,B_i,|| - операція конкатенації, а - побітне виключаюче АБО.

Мережа Фейстеля складається з певної фіксованої кількості циклів, яку визначають із міркувань стійкості шифру. В останньому циклі переставляння місцями половин блоків даних не виконують, бо це не впливає на стійкість шифру. Така структура шифрів має низку переваг, а саме:

· процедури шифрування й розшифрування збігаються, лише ключову інформацію під час розшифровування використовують у зворотному порядку;

· для розшифрування можна використовувати ті ж апаратні або програмні блоки, що й для шифрування.

Недоліком мережі Фейстеля є те, що у кожному циклі змінюється лише половина блока тексту, який опрацьовують. Це призводить до збільшення кількості циклів для досягнення бажаної стійкості.

Докладно роботу симетричного блокового шифру розглянемо на прикладі системи DES (Data Encryption Standard - стандарт шифрування даних). Цей шифр було розроблено в 70-х роках компанією ІВМ на державне замовлення. З 1977 по 1999 DES використовувався в якості державного стандарту шифрування. За тими самими принципами були створені шифри FEAL, радянський ГОСТ-89, та інші; зокрема, діючий до цього часу державний американський стандарт АЕS.

2.1.2 Внутрішня будова DES. Спрощений DES

Система DES шифрує 64-бітові блоки відкритого тексту з використа-нням 56-бітного ключа, подаючи на вихід 64-бітові блоки шифртексту. Алгоритм складається з 16-ти раундів, робота яких організована за принципом мережі Фейстеля. Функція F в даному випадку включає перестановку бітів поданої половини блоку, ХОR з раундовим 32-бітовим підключем, згенерованим окремим алгоритмом, обробку S-блоками, заключну перестановку. Обробка S-блоками (матрицями) полягає в повернені в якості фрагмента повідомлення елемента матриці, номер якого визначаеться за поданим фрагментом. Завдяки своїй нелінійності, саме ця процедура забезпечує високу надійність шифру. Проте вона ж викликала чимало сумнівів на етапі становлення стандарту - чи не мають S-матриці специфічної будови, яка дасть змогу авторам DES читати шифртексти? З часом, справді, було виявлено певні закономірності і недоліки в будові S-блоків. Проте це не завадило популярності DES, особливо у комерційних структурах.

В процесі експлуатації було розроблено кілька конфігурацій DES, відповідно до задач, які він мав вирішувати. Так, застосування подвійного (Dоublе) чи потрійного (Тrірlе) DES, значно підвищує надійність стандарту. Завдяки одночасному використанню 2-х чи 3-х незалежно генерованих раундових підключів, вони майже повністю виключили моджливість вдалої атаки шляхом простого підбору ключів. Попередньо, через досить невелику довжину ключа, такі побоювання були небезпідставними.

Ми розглянемо реалізацію DES на прикладі спрощеної системи S-DЕS. За своїми властивостями вона подібна до DES, але має значно менше параметрів. Цей алгоритм працює з 8-бітними блоками тексту (відкритого чи шифрованого) з використанням 8-бітного ключа, і генерує на виході 8-бітні блоки. Текст обробляється наступним чином:

- 8-бітний блок текста обробляється перестановкою ІР=(41357286);

вступає раундова функція:

- текст розділяємо 2 частини по 4 біта - ліву (L) і праву (R);

- застосувавши перестановку з розширенням РR=(41232341) до R, отримаємо 8-бітну послідовність;

- яку обєднуємо операцією ХОR з відповідним 8-бітним підключем;

- ліву половину результату обробляєио матрицею S_0, праву - S_1 за таким правилом: з 4-х бітів 1-щий і 4-тий дають № рядка матриці, 2-гий і 3-тій - стовпця (нумерація починаеться з 0);

S_0	1	0	3	2	S_1	1	1	2	0
	1	2	1	0		2	0	1	3
	0	2	1	1		3	0	1	0
	1	0	3	1		3	1	0	2

- числа на вказаних місцях, записані в двійковій системі, дають по 2 біта;

- отримані 4 біта записуємо у порядку Р_4=(2431);

- шифровану R обєднуємо операцією ХОR з незмінною L і записуємо в якості лівої половини блоку:

F({L,R})={LF(R),R};

кінець раундової функції

- застосовуємо SW - зміну місць правої і лівої половини, щоб зашифрувати тепер R;

- виконуємо ще раунд;

- над отриманим 8-бітним блоком виконуємо перестановку ІР^-1= =(26314857);

шифрування завершене.Розшифрування відбуваеться так само, тільки підключі подаються у зворотньому порядку.

Підключі для кожного раунда отримуємо так:

- над 10-бітовим ключем виконуємо перестановку РК_10=(3 5 2 7 4 10 1 9 8 6);

- виконуємо зсув вліво (або вправо - через раунд) на 1 позицію окремо лівої та правої половин, на вільне місце записуємо 0;

- з отриманих 10 бітів обираємо 8-бітовий підключ за РК_8=(6 3 7 4 8 5 10 9) і подаємо в цикл.

Наприклад: зашифруємо блок (11100100) з ключем (0110010110) з використанням вказаних вище параметрів.

Результат: 00000110

Генерація підключів

ключ	0	1	1	0	0	1	0	1	1	0
РК_10	1	0	1	0	0	0	0	1	1	1
зсув вліво
	0	1	0	0	0	0	1	1	1	0
РК8
К1	0	0	1	0	1	0	0	1
зсув вправо
	0	1	0	1	0	0	0	0	1	1
РК8
К2	0	0	0	1	0	0	1	1

2.1.3 Криптоаналіз DES

Впродовж всього існування DES цей алгоритм аналізувався головним чином методом перебору всіх ключів. Відносно мала (56 бітів) довжина ключа була достатньою підставою для небезуспішності таких спроб. Для розглянутого вище S-DЕS простір можливих ключів складається з 28=256 елементів і, за наявності рядка відкритого і відповідного шифр-тексту, встановлюється домсить просто. Проте, на відміну від шифрів попереднього розділу, у випадку з DЕS задачею криптоаналітика є не тільки організувати ефективний пошук ключа, а й розпізнати відкритий текст, кодований двійковим кодом. Задача ускладнюється, якщо повідомлення містить не звязний текст, а, наприклад, цифрові дані, або якщо інформація була попередньо оброблена (стиснута), тощо.

В міру появи складніших варіацій стандарту (наприклад, потрійного DES) повний перебір всіх ключів став надто складною та затратною задачею. Це привело до пошуку ефективних загальних методів криптоаналізу DES і інших симетричних блокових шифрів. Далі розглянемо два найпопулярніші підходи диференціальний та лінійний криптоаналіз.

Вдала атака на DES шляхом диференційного аналізу була представлена в 1990р Е.Біхамом та А.Шаміром. Ідея полягала в аналізі пар блоків відкритого тексту (Х, Х₁) та відповідних їм криптограм (У, У₁). Нижче представлена схема аналізу 1 раунду DES:

Тут Х, У - різниця між Х, Х₁ та У, У₁ відповідно; перестановка з розширенням Е(Х) та заключна перестановка Р вважаються відомими, тому можемо встановити різниці в парах повідомлень на даних етапі шифрування - А і С. Операція ХОR з ключем К_і нейтралізує різницю між А, А₁, тому В=А.

Тепер ми можемо зробити припущення щодо вигляду А ХОR К_і та А₁ ХОR К_і. Якщо А, А₁ відомі, то маємо деяку інформацію щодо К_і.

Зібравши інформацію щодо можливих характеристик К_і від досить великої кількості пар, ці данні записуються в таблицю. За частотою виникнення певної характеристики визначаємо, є вона істиною чи випадковою. Відмічаємо пари, що дають «правильні» характеристики - подальший їх аналіз дасть нам скількись найімовірніших варіантів, серед яких виділяємо істиний ключ. (Точніше кажучи, 48 бітів істиного ключа. Недостаючі 8 бітів можемо визначити підбором).

Захист. Стандарту DЕS притаманий так званий лавиний ефект - завдяки багатошаровій обробці різниця в значенні 1 біту в відкритому тексті або ключі призводить до значних змін у вигляді криптограми. Взагалі, ефективність диференційного криптоаналізу значно залежить від кількості раундів в системі. Так, для розкриття повного, 16-раундового DЕS необхідно опрацювати 2⁴⁷ відомих пар «текст-криптограма». Алгоритм для 17 чи 18-раундового шифру є не більш ефективним, ніж прямий перебір, а для 19-раундового вимагає обробки 2⁶⁴ пар відкритого тексту, що неможливо при довжині блока 64 біти.

Лінійний криптоаналіз - метод, що використовує лінійні наближення для опису роботи шифру. Був запропонований М.Мацуі в 1993 для розкриття DЕS та FЕАL. Для розкриття повного 16-раундового шифра вимагає обробки 2⁴⁷ відкритих текстів, як і попередній метод, проте дає виграш в часі.

Ідея алгоритма полягає в тому, що рівність

Р_і1 Р_і2… Р_іn C_j1… C_jm= K_k1…. K_kp (2.1.1)

де Р_і, C_j, K_k,- відповідні біти відкритого текста, криптограми і ключа, - операція ХОR, в загальному випадку виконується з ймовірністю, близькою до Ѕ. Шукаємо сполучення, що дають таку рівність з імовірністю > Ѕ. Чим більше імовірність відрізняється від Ѕ, тим більш «невипадковим» є данне сполучення; обробивши достатню кількість пар (Р,С), отримаємо систему лінійних рівнянь для підбору ключа. Для розкриття 8-раундового DES потрібно обробити 221 відомих текстів, 12-раундового - 233, 16-раундовий (повний) DES вимагає 247 відомих відкритих текстів. В цьому випадку атака не надто ефективна, проте працює швмдше, ніж прямий перебор ключів.

Лінійний криптоаналіз корисний також тим, що іноді рівність (2.1.1) можна побудувати у вигляді:

C_j1… C_jm= K_k1…. K_kp (2.1.2)

тобто не застосовуючи жодного біта відкритого тексту.

Бачимо, що вихідними вимогами для якісного блокового шифру є:

1. Необхідно досить велике N (64 чи більше) для того, щоб завадити створенню й підтримці каталогу.

2. Необхідний досить великий простір ключів, аби уникнути можливості підбору ключа.

3. Необхідні складні співвідношення {к,х:х у = {к,х між вихідним і шифрованим текстами для того, щоб аналітичні і статистичні методи визначення вихідного тексту і ключа на основі відповідності вихідного і шифрованого текстів було б неможливо (принаймні важко) реалізувати.

Зауважимо, що системи шифрування з блоковими шифрами, алфавітом Z_2,64 i простором ключів К = SYM(Z_2,64) неподільні в тому розумінні, що підтримання каталогу частот появи букв для 64-розрядних блоків чи проба на ключ при кількості ключів 2⁶⁴ виходять за межі можливостей противника.

Тобто DЕS, що оперує 64-розрядними блоками задовольняє вимоги 1,2. Правильно організований класичний DЕS з 16 раундами задовольняє і 3 вимогу, тим паче подвійний та потрійний його варіації.

2.1.4 Програми до параграфа (редактор VВА)

Програма, що реалізує алгоритм S-DЕS (демонстраційна)

Private Sub DES()

Worksheets(1).Activate

Worksheets(1).Unprotect

Worksheets(1).Name = "Dannye"

Dim Block(8) As Integer

Dim Key(10) As Integer

Dim IP(8) As Integer

Dim Blk_IP(8) As Integer

Dim IP_1(8) As Integer

Dim PK_10(10) As Integer

Dim Key_PK(10) As Integer

Dim PK_8(8) As Integer

Dim P_rozh(8) As Integer

Dim P_4(4) As Integer

Dim S_0(4, 4) As Integer

Dim S_1(4, 4) As Integer

//зчитує з документа параметри і дані:

For i = 1 To 8

Block(i) = Cells(1, i + 2).Value //блок відкритого текста

IP(i) = Cells(3, i + 2).Value //перестановка ІР

IP_1(i) = Cells(4, i + 2).Value //ІР^-1

PK_8(i) = Cells(7, i + 2).Value //РК₈

P_rozh(i) = Cells(9, i + 2).Value //перестановка розширення

Next i

For i = 1 To 10

Key(i) = Cells(2, i + 2).Value //ключ

PK_10(i) = Cells(6, i + 2).Value //перестановка РК₁₀

Next i

For i = 1 To 4

P_4(i) = Cells(10, i + 2).Value //перестановка Р₄

For j = 1 To 4

S_0(i, j) = Cells(i + 11, j + 2).Value //блок S₀

S_1(i, j) = Cells(i + 11, j + 7).Value //блок S₁

Next j

Next i

Worksheets(1).Range(Cells(1, 2), Cells(1, 10)).Locked = False

Worksheets(1).Protect

Worksheets(3).Activate //виводить вихідний блок

Worksheets(3).Name = "Prymery"

r3 = Worksheets(3).UsedRange.Rows.Count + 2

Cells(r3 + 1, 1).Value = "Блок"

For i = 1 To 8

Cells(r3 + 1, i + 1).Value = Block(i)

Next i

Worksheets(2).Activate

Worksheets(2).UsedRange.Clear

r = 1

Dim resht As Integer

//застосовує

For i = 1 To 8

Cells(r + 1, i).Value = Block(i)

Blk_IP(i) = Block(IP(i)) //перестановку ІР

Next i

For i = 1 To 10

Cells(r + 1, 9 + i).Value = Key(i) //до ключа - РК₁₀

Key_PK(i) = Key(PK_10(i))

Cells(r + 2, 9 + i).Value = Key(PK_10(i))

Next i //початок раундової функції

For j = 0 To 1 //кількість раундів: 2

r = r + 16 * j

For i = 1 To 8

Cells(r + 2, i).Value = Blk_IP(i)

Next i //перестановка розширення

For i = 1 To 8 // для правої половини

Cells(r + 4, i).Value = Cells(r + 2, P_rozh(i) + 4).Value

Next i

For i = 1 To 4 //циклічний зсув ключа

Cells(r + 4, 9 + i + 1 * j).Value = Key_PK(i + 1 - j)

Cells(r + 4, 9 + i + 5 + 1 * j).Value = Key_PK(i + 6 - j)

Next i

Cells(r + 4, 9 + 5 - 4 * j).Value = 0

Cells(r + 4, 9 + 10 - 4 * j).Value = 0

Cells(r + 5, 1).Value = "підключ " & (j+1)

For i = 1 To 8 //РК₈ вибір підключа

Cells(r + 6, i).Value = Cells(r + 4, 9 + PK_8(i)).Value

Next i

For i = 1 To 8 //ХОR з підключем

resht = Cells(r + 4, i).Value + Cells(r + 6, i).Value

If resht = 2 Then

resht = resht - 2

End If

Cells(r + 7, i).Value = resht

Next i

Dim N_row As Integer

Dim N_st As Integer

For i = 0 To 1 //підрахунок №рядка

N_row = Cells(r + 7, 1 + 4 * i).Value * 2 + Cells(r + 7, 4 + 4 * i).Value + 1

N_st = Cells(r + 7, 2 + 4 * i).Value * 2 + Cells(r + 7, 3 + 4 * i).Value + 1

Cells(r + 8, 1 + 4 * i).Value = "N_row" // та №стовпця

Cells(r + 8, 2 + 4 * i).Value = N_row

Cells(r + 9, 1 + 4 * i).Value = "N_st"

Cells(r + 9, 2 + 4 * i).Value = N_st

Cells(r + 10, 1 + 4 * i).Value = "Znach"

Next i //у відповідному блоці

Cells(r + 10, 2).Value = S_0(Cells(r + 8, 2).Value, Cells(r + 9, 2).Value)

Cells(r + 10, 2 + 4).Value = S_1(N_row, N_st)

For i = 0 To 1 //представлення у двійковому

If Cells(r + 10, 2 + 4 * i).Value >= 2 Then //записі

Cells(r + 12, 1 + 2 * i).Value = 1

Cells(r + 12, 2 + 2 * i).Value = Cells(r + 10, 2 + 4 * i).Value - 2

Else

Cells(r + 12, 1 + 2 * i).Value = 0

Cells(r + 12, 2 + 2 * i).Value = Cells(r + 10, 2 + 4 * i).Value

End If

Next i

For i = 1 To 4 //Р₄ та ХОR з лівим підблоком

Cells(r + 14, i).Value = Cells(r + 12, P_4(i)).Value

Cells(r + 15, i).Value = Blk_IP(i)

resht = Cells(r + 14, i).Value + Cells(r + 15, i).Value

If resht = 2 Then

resht = resht - 2

End If

Cells(r + 16, i).Value = resht

Cells(r + 16, i + 4).Value = Blk_IP(i)

Next i

For i = 1 To 4 //перестановка лівого та правого

Block(i) = Cells(r + 16, i + 4 * (1 - j)).Value //підблоків

Block(i + 4) = Cells(r + 16, i + 4 * j).Value

Next i

Next j //кінець раундової функції

Worksheets(3).Activate

Cells(r3 + 2, 1).Value = "Шифрблок"

For i = 1 To 8 //вивод результату

Cells(r3 + 2, i + 1).Value = Block(i)

Next i

End Sub

Результат роботи програми представлено в параграфі. Цей же алгоритм зі зворотнім порядком подачі підстановок ІР та ІР_1, раундових підключів та перестановки SW є алгоритмом дешифрування.

Програма, що розбиває текст на блоки

Private Sub Text_to_block()

Dim Mesg As Variant

Dim Cryptg As Variant

Dim U_alf As Variant

Dim Len_mes As Integer

Dim Len_alf As Integer

Dim Num As Integer

Worksheets(4).Activate

U_alf = "абвгдеєжзіийклмнопрстуфхцчшщьюя_"

Mesg = Cells(1, 8).Value

Len_mes = Len(Mesg)

Len_alf = Len(U_alf)

Cryptg = "_"

For i = 1 To Len_mes //для кожної літери повідомлення

For j = 1 To Len_alf //визначає номер по алфавіту

If Mid(Mesg, i, 1) = Mid(U_alf, j, 1) Then

Num = j

For k = 1 To 5 //зачитує з таблиці відповідний

Cryptg = Cryptg & Cells(Num, k + 1).Value //рядок з 5 цифр

Next k //та записує його в криптограму

j = Len_alf

End If

Next j

Next i

MsgBox ("Cryptg: " & Cryptg)

Len_mes = Len(Cryptg)

Cells(1, 9).Value = Cryptg

Worksheets(3).Activate

r3 = Worksheets(3).UsedRange.Rows.Count + 2

Num = 0

While Num < Len_mes / 8 //розбиває крптограму на блоки по 8

For j = 1 To 8 //та виводить їх

Cells(r3 + Num, j + 1).Value = Mid(Cryptg, Num * 8 + j + 1, 1)

Next j

Num = Num + 1

Wend

End Sub

Прграма для заміни блоків з 0 та 1 літерами, згідно таблиці 2.2.

Private Sub Block_to_text()

Dim Mesg As Variant

Dim Cryptg As Variant

Dim U_alf As Variant

Dim Num As Variant

Dim Len_mes As Integer

Dim Len_alf As Integer

U_alf = " абвгдеєжзіийклмнопрстуфхцчшщьюя__"

Len_alf = Len(U_alf)

Cryptg = "_"

Worksheets(3).Activate

r3 = Worksheets(3).UsedRange.Rows.Count

For i = 1 To 19

For j = 1 To 8 //записує в 1 рядок 8-бітові блоки

Cryptg = Cryptg & Cells(r3 - (19 - i), j + 10).Value

Next j

Next i

MsgBox ("Cryptg: " & Cryptg)

Len_mes = Len(Cryptg)

Worksheets(4).Activate

Cells(2, 9).Value = Cryptg

'r4 = Worksheets(4).UsedRange.Columns.Count + 1

Mesg = ""

For i = 0 To Len_mes / 5 - 1 //для кожного відрізку з 5 цифр

For j = 1 To Len_alf

Num = ""

For k = 1 To 5 //шукає такий самий рядок з таблиці 2.2

Num = Num & Cells(j, k + 1)

Next k//

If Mid(Cryptg, 5 * i + 2, 5) = Num Then

Mesg = Mesg & Mid(U_alf, j, 1) //записує відповідну літеру

j = Len_alf

End If

Next j

Next i

MsgBox ("Mesg: " & Mesg)

Cells(2, 8).Value = Mesg //виводить повідомлення

End Sub

2.1.5 Завдання до параграфа

1. Написати програму, що реалізує шифр S-DЕS з даними параметрами. З ключем 0 1 1 0 0 1 0 1 1 0

а) зашифрувати:

01101010 00100001 11011101 01101011 01010100;

б) розшифрувати:

00101011 00011000 01010101 01111101 00000110.

2.Написати програму, що представляє текст у вигляді блоків з 0 та 1, шифрує його шифром S-DЕS. та знову перетврює на текст (для заміни літер скористатися таблицею 2.2.). З її допомогою:

зашифрувати з ключем 1 0 0 1 1 1 1 0 1 1

а) ой_ти_знав_нащо_брав_міщаночку_з_міста;

б) я_не_іла_й_не_істиму_гречаного_тіста; зашифрувати з ключем 0 0 1 0 1 1 0 0 0 1 0

в)котик_муркотик_сірий_животик_край_ліжечка_ходить_пісеньки_ заводить;

г) горіла_сосна_палала_під_ней_дівчина_стояла_русяву_косу_чесала; розшифрувати з ключем 1 0 0 1 1 1 1 0 1 1

д) гтнанздч_єпа_ропдвписущхфжжєщч

е) _іпцй_зве_нпгимябжсрахуч_ошзнаю розшифрувати з ключем 0 0 1 0 1 1 0 0 0 1 0

є) _ц_нмсхц_цєгсооауикиупмьжзвхбшдзч_учвхяшхньопсчгхц

ж) _цбвмтлнржє_еерєрумйпаог_мафіящчжкічщелулівбюк_ллз

2.2 Криптосистеми з відкритим ключем. Система RSA

2.2.1 Односторонні фукції. Структура системи RSA

Визначною віхою в історії криптографії стала праця американських математиків У.Діффі та М.Е.Хелмана «Нові напрями в криптографії», опублікована в 1976р. Запропоновані в ній поняття односторонньої функції та функції з секретом стали підставою для створення принципово нових секретних систем та роширеня сфери криптографічних задач.

Отже, що таке одностороння функція? Односторонньою функцією будемо називати функцію F:Х-У, яка має наступні властивості:

1) зручний алгоритм обчислення значень у=F(х) за прийнятний час;

2) не існує алгоритму обчислення оберненого значення х=F^-1(у) (інвертування функції F) за прийнятний час.

Функцією з секретом К називається деяка функція F_К:Х-У, що залежить від параметру К і при цьому задовольняє наступним умовам :

1) при будь-якому К зручний алгоритм обчислення значень у=F_К(х);

2) при невідомому К не існує алгоритму інвертування функції F_К;

3) при відомому К зручний алгоритм інвертування функції F_К.

Слід зазначити, що питання про існування односторонніх функцій та функцій з секретом залишаеться відкритим. Щодо останніх, існують функції, івертування яких за невідомого К еквівалентне складній математичній задачі, тобто для них припускається виконання властивості 2).

В 1978р. американці Р.Рівест, А.Шамір і Л.Аделман (R.L.Rivest, A.Shamir, L.Adelman) запропонували систему шифрування, створену на основі функції f=х^е(mоd m). Ця система була названа за першими літерами імен своїх творців - RSA. Функція f, ймовірно, є функцією з секретом і діє на деяке повідомлення х за таким правилом:

f: х -х^е(mоd m), е, m (2. 2.1)

тоді дешифрування повідомлення а=f(х) зводиться до розв'язання конгруенції

х^е а(mоd m). (2. 2.2)

Якщо показник степеня в (3.1.2) є взаємно простим з (m), тобто

НСД(е,(m))=1 Тут і далі - НСД(а,b) - найбільший спільний дільник чисел а і b., (2. 2.3)

то (2.2.2) має єдиний розв'язок. Тут (m) - функція Ейлера, кількість натуральних чисел від 1 до (m-1), взаємно простих з m. Зазначимо деякі властивості (m), відомі з курсу Теорії чисел, які будемо застосовувати далі:

(1)=1, (2. 2.4)

(р)=р-1, де р - просте, (2. 2.5)

(аb)=(а)(b), (2. 2.6)

якщо а і b - взаємно прості, тому

(р^r)=р^r-1(р-1), де р - просте, r- натуральне. (2. 2.7)

З (3.1.3-6) бачмо, що (m) визначається просто, якщо ми маємо розкладення m на прості множники. Далі, визначаємо d, таке, що:

dе1(mоd (m)), 1?d(m) (2. 2.8)

(так як е і (m) взаємопрості, то таке d існує і єдине). Далі, за теоремою Ейлера, х, взаємопростого з (m), виконується х^(m)1(mоd m), тому

а^d х^dе х(mоd m). (2. 2.9)

Отже, вимагаючи ще, щоб (а,m)=1, отримуємо єдиний розв'язок конгруенції (2.2.2) у вигляді х=а^d(mоd m).

Зауважимо, що вимога (а,m)=1 не обов'язкова у випадку, коли m є добутком різних простих множників. Тому творці RSА запропонували використовувати таке m, що:

m=рq,

де р, q - досить великі прості числа, тоді, згідно (3.1.5,6):

(m)=(рq)=(р)(q)=(р-1)(q-1),

а умова (2.2.3) набуває виду:

НСД(е,р-1)= НСД(е,q-1)=1. (2. 2.10)

Пара Р=(е, m) є відкритим, тобто відомими всім користувачам, ключем системи. Будь-хто може посилати організатору повідомлення, шифровані функцією f, вказаною в (2.2.1), які організатор читає з допомогою закритого ключа S=(d,m), вибраного за умовою (2.2.8).

Якщо припусти, що супротивнику відомі відкриті числа та принцип шифрування, то при m невеликої розмірності (наприклад, 8 розрядів) досить просто знайти усі прості дільники числа m, перебравши всі числа від 1 до vm. А потім, обчисливши (m), знайти ключ d з умови (2.2.8). Проте із ростом m кількість простих чисел, які потрібно перевірити асимптотично дорівнює 2m(ln m)^-1. Так, для m, записаного сотнею десяткових знаків, не менше 4*10⁴² простих чисел, що можуть бути його дільниками. Найшвидші з відомих алгоритмів розкладу числа на прості множники не дають результату за прийнятний час - принаймні, за умов використання одного комп'ютера. Тому всі вдалі атаки на систему RSА були здійснені за допомогою розподілу розрахунків.

Для ілюстрації свого методу творці RSА зашифрували деяке повідомлення функцією (2.2.1), взявши в якості m 129-значне число. Отримана криптограма була опублікована разом з відкритими параметрами шифрування, першому, хто дешифрує її, була обіцяна премія в 100$. Було також додатково вказано, що m є добутком двох простих чисел розрядністю 64 та 65 знаків, проте минуло 17 років, перш ніж шифр було розкрито. Не враховуючи теоретичну підготовку, тільки до обчислення було залучено близько 600 добровольців та 1600 комп'ютерів, що працювали впродовж 220 днів.

2.2.2 Алгоритми для реалізації системи

Далі наведемо алгоритми, використані безпосередньо при написанні коду програми.

Обчислення а^d(mоd m)

1. Покладемо а₀=а, кожне наступне а_i обчислюємо за формулою

a_i=a_i-1a(mod m), i=1,..,d

2. При і=d отримаємо шукане значенням а^d(mоd m).

Алгоритм Евкліда пошуку НСД(а,b).

1. Обчислюємо r - остачу від ділення а на b (не порушуючи загальності, можемо вважати аb).

2. Якщо r=0, то b і є шукане число.

3. Якщо r0, то замінюємо пару (а,b) на (b,r) і повторюємо спочатку.

Генератор простих чисел

Тут мається на увазі програма підбору досить великих простих чисел. Принцип її дії ґрунтується на наступній теоремі.

Теорема2.1 Нехай N, S - непарні натуральні числа, такі, що N-1=S*R, причому простого дільника q числа S таке натуральне а, що:

.

Тоді простий дільник р числа N задовольняє р =1(mоd 2S).

Наслідок. Якщо виконані умови теореми і R?4S+2, то N - просте число.

Маємо наступний алгоритм:

1. Обираємо S - деяке просте число та R - парне з проміжку S?R?4S+2.

2. Перевіряємо число N=RS+1: якщо N не просте, то обираємо інше R, поки не знайдемо просте число. Побудоване таким чином, NS², а значить - має вдвічі більший розряд.

3. У разі необхідності беремо N в якості вихідного простого числа і повторюємо алгоритм, поки знайдене просте число не буде досить великим.

Цей спосіб реалізується досить просто і дозволяє на персональному комп'ютері отримувати прості числа порядку 10¹⁰.

2.2.3 Криптоаналіз RSА

Розглянемо далі деякі елементарні атаки на систему та способи захисту від них.

Атака: пошук простих дільників числа m методом факторизації Ферма. Ідея методу полягає в тому, що дільники числа m шукаються у вигляді:

m=(х-у)*(х+у),

тоді m=х²-у² , звідки у²=х²-m.

Починаємо з х=[m], і, збільшуючи на 1, шукаємо таке х, що х²-m є повним квадратом. В результаті отримуємо

m=(х-x²-m)*(х+x²-m), (2.2.11)

якщо m - просте, то (2.2.11) дає тривіальний розклад. Навіть для малих m цей метод є більш ефективним, аніж прямимй підбір. Наприклад, розклад

m=321161=337*952

атака прямого перебору визначає за 1288 спроби, атака фкторизаціїї - за 79;

для розкладу

m=656933 = 353 * 1861

атака прямого перебору вимагає 2212 спроб, атака фкторизаціїї - 297, тощо.

Проте цей метод потребує дещо складнішої організації, якщо m є добутком більше ніж 2-х простих множників. Окрім того, метод факторизації успішний за умов близького розташування множників m, тому прості числа р і q варто брати з досить великою різницею. Зрештою, якщо р і q були генеровані незалежно, то ця вимога з високою ймовірністю виконується автоматично.

Атака: обчислення закритого ключа d. Ґрунтується на теоремі Вінера:

Нехай m=рq, де qр2q, dq. Тоді, якщо відома пара (е,m), де е задовольняє (2.2.8), то існує ефективний спосіб обчислення d.

Захист: таким чином, якщо розмір m, наприклад, 1024 біти, потрібно обирати d розміром не менше як 256 бітів.

Атака на систему з загальним модулем: якщо в системі з кількох користувачів всі повідомлення шифруються за єдиним модулем m, то користувач В, може розкласти m за своїми параметрами шифрування е_В, d_В, а потім, знаючи відкритий ключ е_А користувача А, може обчислити закрите значення d_А.

Захист: для кожного користувача генерувати власне значення m.

Атака Хастада: в системі з кількох користувачів повідомлення шифруються за індивідуальними параметрами для кожного користувача. Користувач В відсилає повідомлення х k адресатам А₁, А₂,…А_k, зашифроване з параметрами (е_і, m_і), і=1..k відповідно. Противник перехоплює k f_і(х) - шифрованих повідомлень. Якщо е_і=е і=1..k, то противник може відновити повідомлення х, якщо k?е. Навіть якщо х_і для і-того користувача є деякою фіксованою перестановкою вихідного повідомлення, наприклад,

х_і=і*2^m+х, (2.2.12)

все одно противник може отримати х при досить великому k.

Захист: ця атака може бути успішною тільки при невеликому значенні відкритого ключа е. В таких умовах в (2.2.12) потрібно застосовувати не фіксовану, а випадкову перестановку.

Взагалі, для підвищення стійкості криптосистеми RSА рекомендовано використовувати досить великі значення е, наприклад е=2¹⁶+1=65537.

Атака Франкліна-Рейтера: нехай х, х₁ - два вихідних повідомлення, такі, що

х₁=g(х) (mоd m),

де g(х)= ах+b(mоd m), b0 - деякий лінійний многочлен, і f(х), f(х₁) - результат шифрування х, х₁ системою RSА з відкритим ключем (е,m). При е=3 противник, знаючи е, m, f(х), f(х₁) і g(х) зможе відновити х, х₁.

Захист: при е3 час злому шифру росте пропорційно е², тому така атака має успіх лише при невеликих значеннях е.

Як бачимо, підвищення безпеки досягається за рахунок накладення певних обмежень на вибір простих дільників основи системи m та збільшення розмірів ключа. Остання вимога обумовлена також стрімким ростом можливостей обчислювальної техніки впродовж останніх десятиріч. Запропонована Ріверстом, Шаміром та Адлеманом система зі 129-значною основою залишалась нерозкритою впродовж 17 років - на сьогодні надійною вважається система на основі RSА з m не менше 1024 бітів. В 2009р. група вчених з Швейцарії, Франції, Нідерландів, Германії та США після трьох-річної праці отримала дані, зашифровані за допомогою коду RSА з модулем m довжиною 768 біт. За їх прогнозами, система з 1024-значною основою може бути розкрита в найближчі 3-4 роки.

2.2.4 Програми до параграфа (Borland C++)

Програма шифрування RSA:

#include<iostream>

#include<conio.h>

#include<math.h>

int Stepen(int a,int d,int M) //функція для обчислення а^d(mоd М)

{

int r=1;

for(int i=0;i<d;i++)r=r*a%M;

return r;

}

int main()

{

long int x,f_x;

int e,M,flg;

cout<<"Vvedit vidkrutuy kluch:"<<endl;

cout<<"M= ”; cin>>M;

cout<<endl<<"e= “; cin>>e;

do{

cout<<"Vvedit povodomlennya:"<<endl;

cin>>x;

f_x=Stepen(x,e,M); //обчислює f(х)=х^е(mоd m)

cout<<endl<<"Shifrovane povidomlennya: "<<f_x;

getch();

cout<<endl<<"Prodovzit? Press 1(Tak) 0(Ni):";

cin>>flg;

}while(flg);

cout<<endl<<"Dlya vuhody natusnit Enter...";

getch();

return 0;

}

Результат роботи

Vvedit vidkrutuy kluch:

M= 39491

e= 29

Vvedit povodomlennya:

12147

Shifrovane povidomlennya: 30914

Prodovzit? Press 1(Tak) 0(Ni):1

Vvedit povodomlennya:

241

Shifrovane povidomlennya: 18729

Prodovzit? Press 1(Tak) 0(Ni):0

Dlya vuhody natusnit Enter...

Програма дешифрування RSА

#include<iostream>

#include<conio.h>

#include<math.h>

int Stepen(int a,int d,int M) //функція для обчислення а^d(mоd m)

{ int r=1;

for(int i=0;i<d;i++)r=r*a%M;

return r;

}

int NOD(int a,int b) //функція, що знаходить най-

{ int r; //більший спільний дільник а, b

do //(алгоритм Евкліда)

{if(a<b)

{r=a;a=b;b=r;}

r=a%b;

a=r;}

while(r);

return b;

}

int main()

{

long int x,f_x,d_1;

int e,M,flg,d,fi_M;

M=11*23*17; e=29; //вводить параметри шифрування

fi_M=10*22*16;

cout<<"M= "<<M; //виводить відкритий ключ на екран

cout<<endl<<"e= "<<e; //та перевіряє умову (2.2.3)

if(NOD(e,fi_M)!=1)cout<<endl<<"Perevirte parametry...";

else{

d=1;

while(d*e%fi_M!=1 && d<fi_M)d++; //обчислює ключ для дешифрування

do

{cout<<endl<<"Vvedit shifrtext: ";

cin>>f_x;

int i=0;