slidy.pdf

ElementyKryptogra i

Kryptogra a:naukaometodachstosowaniazabezpiecze«,szyfro-

wania.

Szyfr:metodaprzekszta“caniainformacjiwoparciuoalgorytmy;

proceduryuruchamianezapomoc¡poufnychparametr ó wzwanych

kluczami

Kryptogra ajakonaukadotyczy:

•badaniaitworzeniatechnikmatematycznychpotrzebnychdosze-

rokorozumianegobezpiecze«stwakomunikacji,przekazulubsposo-

b ó wprzechowywaniainformacji(matematyka);

•tworzeniaodpowiednichalgorytm ó wwykorzystuj¡cychtechnikima-

tematyczneis“u»¡cychtymcelom(informatykateoretyczna);

•budowylubwykorzystaniaurz¡dze«realizuj¡cychalgorytmykryp-

togra czneatak»enaw“a–ciwegotrybuichstosowania(informatyka

praktyczna);

•praktycznestosowanietychurz¡dze«dorealizacjicel ó w.

Etapykryptogra i:

•etapmatematyczny;

•etapinformatyczny:teoretyczny(pomys“)ipraktyczny(implemen-

tacja);

•etapwdro»eniowy(protoko“y=przepisystosowania)

Kryptoanaliza:naukao“amaniazabezpiecze«,kt ó rychdostarcza

kryptogra a.Zadaniemkryptoanalizyjestdostarczenie–rodk ó wdo

zapobie»eniacelomkryptogra cznym.

Kryptologia=kryptogra a+kryptoanaliza

Celekryptogra i

•Ochronainformacjiprzedniepowo“anymodczytem;

•Uwierzytelnianiedokument ó w:autoryzacjaicerty kacja;

•Uwierzytelnianieiidenty kacjapodmiot ó w;

•Celespecy czne(wsp ó “dzielenietajemnic,dowodyowiedzyzero-

wej)

Podstawowaterminologiakryptogra czna

•podmiot:nadawca,odbiorca,klient,wery kator,wr ó g;

•kana“przesy“u;kana“bezpieczny,niebezpieczny;

•tekst,dokument:daneprzesy“anelubprzechowywane;tekstmo»e

by¢jawnylubutajniony.

Budowasystemukryptogra cznego

•AlfabetA;

•przestrze«wiadomo–ciM:zbi ó rprostychtekst ó wjawnychzbudo-

wanychzliteralfabetuA,tzw.podstawowychjednostekprzetwarza-

nia;podzbioryzbioruMtoz“o»onetekstyjawne;

•przestrze«kryptogram ó w(szyfr ó w)C:jegoelementytoproste

kryptogramy;zbioryprostychkryptogram ó wtokryptogramy(lub

szyfry)z“o»one;

•przestrze«kluczyK:zbi ó rparametr ó w,dziƒkikt ó rymmo»liwejest

dzia“aniealgorytm ó wszyfruj¡cych;

•proceduraszyfruj¡caE:K×M!C:funkcja,kt ó ratekstowi

m2Mprzyporz¡dkowujekryptogramc=E(e,m)=E e (m)gdzie

e2K;

•proceduradeszyfruj¡caD:K×C!M:funkcja,kt ó rakrypto-

gramowic2Cprzyporz¡dkowujetekstjawnym=D(d,c)=D d (c)

gdzied2K;

•Systemkryptogra czny(kryptosystem):

uk“ad(A,M,C,K,{E k } k2K ,{D k } k2K )taki,»e

8e2K9!d2K8m2MD d (E e (m))=m.

•pasuj¡caparakluczy(e,d).

RolaalfabetuAlfabety:“aci«ski

{A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z}.

A=0,B=1,...,Z=25;A=Z 26

AlfabetbinarnyA={0,1},A=Z 2 ;elementytobity.

PrzestrzenieMwiadomo–ciiCkryptogram ó w

M=A n ,n2N.Wtedym2Mgdym=(a 1 ,...,a n ).

Msk“adasiƒzn-literowychs“ ó wzbudowanychzliteralfabetuA

GdyA={0,1},n=8,toMsk“adasiƒz8-bitowychci¡g ó wbit ó w

(bajt ó w).

ASCII:kodybinarnedladowolnychznak ó wgra cznych(ilo–¢kod ó w

256=2 8 )Literaalfabetu“aci«skiego=bajt

S“owo5-literowe=ci¡g5bajt ó w=40bit ó w.Liczbas“ ó w5litero-

wychwynosi2 40 ;ka»detakies“owaodpowiadaliczbiezzakresuod0

do2 40 −1

Zapisbinarnyliczbdziesiƒtnych

Algorytmkryptogra czny:algorytms“u»¡cydoefektywnejre-

alizacjikryptosystemu;sformalizowanaprocedurasporz¡dzaniapro-

stegoszyfruzprostegotekstujawnego.Algorytmyotwartelubza-

mkniƒte.

Trybdzia“aniaalgorytmu:spos ó bu»yciaalgorytmuwceluspo-

rz¡dzeniakryptogramuzez“o»onegotekstujawnego.

Protok ó “kryptogra czny:sekwencjaczynno–cipraktycznychnie-

zbƒdnychdorealizacjikonkretnegocelukryptogra cznego:

•wyb ó rkryptosystemuijegowery kacja;

•wyb ó r(uzgodnienie)kluczydoaktywacjiprocedurszyfruj¡cejide-

szyfruj¡cej;

•budowaalgorytmuijegoimplementacjaprogramowaisprzƒtowa;

•sporz¡dzenieprotoko“u(przepisuu»ytkowania);

•realizacjacelu.

NiechK=(A,M,C,K,{E e } e2K ,{D d } d2K )bƒdziekryptosystemem.

Klasy kacjakryptosystem ó w

I. Zewzglƒdunaposta¢zbioruM

•Kryptosystemblokowy:M=A n gdzien2N,tzn.m2M

gdym=(a 1 ,...,a n )ia i 2Adlai=1,...,n.Elementym2M

nazywasiƒblokamin-literowymi,n d“ugo–¢bloku.

•Kryptosystemstrumieniowy:elementyzbioruMs¡literami

alfabetuA.S¡toszyfryblokoweod“ugo–cibloku1.

II. Zawzglƒdunazale»no–cimiƒdzypasuj¡cymikluczami

•Kryptosystemsymetryczny:dladanegokluczaszyfruj¡cego

e2K, Š ATWOznale„¢kluczdeszyfruj¡cyd2Kpasuj¡cydo

e.Obakluczemuszaby¢utrzymywanewtajemnicy.Systemz

kluczempoufnym ;

•Kryptosystemasymetryczny:dladanegokluczaszyfruj¡cego

e2K,problemznalezieniakluczad2Kpasuj¡cegodoejest

TRUDNY.Bezutratybezpiecze«stwamo»naupubliczni¢klucze.

Kluczdpozostaje prywatny .Systemz kluczempublicznym lub jawnym .

Rolekluczyjawnegoiprywatnegomog¡zmienione.

•Algorytm:poprawniezde niowanaproceduraobliczeniowa,kt ó ra

przetwarzaargumentwej–ciowy(input)nawarto–¢(output).

Š ATWO,TRUDNO z“o»ono–¢obliczeniowa

•Operacjenabitach(kroki):kopiowaniebit ó w,dodawanie(XOR),

przesuniƒcie.

• Z“o»ono–¢obliczeniow¡ algorytmumierzysiƒczasemdzia“ania,tzn.

liczb¡operacjinabitachniezbƒdnychdojegowykonania.Np.algo-

rytmAwykonuj¡cyobliczenianamliczbachbinarnychmaz“o»o-

no–¢f(n 1 ,...,n m )je–liczaspotrzebnydoobliczeniaA(x 1 ,...,x m ),

gdziex i jestliczb¡binarn¡on i -bitach,jestf(n 1 ,...,n m )(tutajf

jestpewn¡ca“kowito-liczbow¡funkcj¡m-argumentow¡).Np.z“o»o-

no–¢jestwielomianowa,gdyczaswykonaniajestf(n 1 ,...,n m )=

n d 1

Klasy kacjaproblem ó wdecyzyjnych(problem ó wTAK NIE).

•Klasaz“o»ono–ciPsk“adasiƒztychproblem ó wdecyzyjnych,kt ó re

mo»narozwi¡za¢wczasiewielomianowym.

•Klasaz“o»ono–ciNPsk“adasiƒztychproblem ó wdecyzyjnych,dla

kt ó rychodpowied„TAKmo»eby¢zwery kowanawczasiewielomia-

nowymoilezadanyjestcerty kat,tzn.dodatkowainformacja.

PNP.NiewiadomoczyP=NP

•ProblemdecyzyjnyjestNP-zupe“ny,gdynale»ydoNPizza“o-

»enia,»ejestonklasyP,wynika,»eNP=P.

1 ...n d m m dlapewnychd 1 ,...,d m 2N.

Notacja O :M ó wimy,»ez“o»ono–¢AjestO(f(n 1 ,...,n m ),gdy

wykonaniealgorytmuA(x 1 ,...,x m )wymagacf(n 1 ,...,n m ),gdzie

c>0,czasu.

•Problem(obliczeniowy),kt ó rymo»narozwi¡za¢przypomocyalgo-

rytmuoz“o»ono–ciwielomianowejjest “atwy lub podatnyobliczeniowo

lub wydajny ;

•wprzeciwnymrazieproblemjest trudny lub niepodatny lub niewydajny .

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: