plan wykladu kryptografii.pdf

ElementyKryptografii

WojciechKryszewski

Komunikacjaiwymianainformacji:

•jako–¢no–nik ó winformacji(pismo,zapisanalogowy,cyfrowy);

•jako–¢–rodk ó wprzekazu(poczta,telefon,e-mail);

•wiarygodno–¢przekazu(metodyzapisu,przekazu,kodowanie);

•wiarygodno–¢ipoufno–¢.

Metodyzapewnieniapoufno–ciizapewnieniawiarygodno–ciprzekazu:

•ukrywaniezapisu(steganogra a,atramentsympatyczny);

•specjalnyrodzajzapisu;

•pos“anieclubinnespecjalnemetody;

•wiarygodno–¢osobykomunikuj¡cejsiƒ(podpis,pieczƒ¢);

•poufno–¢poprzezszyfrowanie:zapisinformacjiwprzekszta“conejformie;deszy-

frowanie.

Szyfryjednorazowe(metodyniepowtarzalne).

Szyfrypowtarzalne,powszechnieznane;bezpiecze«stwooparteonieznanyklucz.

Analogiadodrzwizamykanychzklucza.

Szyfr:metodaprzekszta“caniainformacjiwoparciuozalagorytmizowanepostƒ-

powanie;proceduralubszeregprocedururuchomianychprzypomocypoufnych

parametr ó wzwanychkluczami.

Kryptogra a:

•metodymatematyczne;

•informatykateoretyczna;

•informatykapraktyczne(wdro»enie).

Kryptogra a:naukaoteoretycznych,matematycznychmetodachszyfrowania,tech-

nikachzapewnieniabezpiecze«stwaprzekazuinformacji.

Kryptogra a:naukaotechnikachimetodachrealizacjiideiteoretycznychzapew-

nieniaprzekazuinformacji.

Kryptogra a:naukaopraktycznychsposobachwykorzystaniatechnikwykorzystu-

j¡cychideeteoretyczne.

Ideakoperty jejprodukcja jejwykorzystaniepraktyczne.

Ideadrzwi ichprodukcja ichwykorzystaniepraktyczne

Ideak“ ó dki jejprodukcjaiudoskonaleniewynikaj¡cezpraktyki praktyczna

budowaizastosowanie.

Kryptogra a(systemkryptogra czny):

•badanieitworzenienapoziomieteoretycznymmetodmatematycznychpotrzeb-

nychdoszerokorozumianegobezpiecze«stwa;

•tworzeniealgorytm ó wwykorzystuj¡cychtetechnikiteoretyczne;•budowa,wy-

korzystywanieurz¡dze«lubprogram ó wwcelurealizacjicel ó wkryptogra cznych;

•praktycznestosowanietychurz¡dze«dorealizacjicel ó w.

Etapykryptogra i:

•etapmatematyczny(metodymatematyczne);

•etapinformatyczno-teoretyczny(algorytmiprocedury);

•etapinformatyczno-praktyczny(implementacjaprogramowa);

•etapwdro»eniowy(protoko“ystosowania).

Systemkryptogra cznyjesttylewartilewartjestjegonajs“abszeogniwo.

Kryptoanaliza:Naukao“amaniuzabezpiecze«,kt ó rychdostarczakryptogra a.

Kryptoanalizask“adasiƒzpodobnychetap ó wjakkryptogra a.

Kryptologia=krytptogra a+kryptoanaliza.

Celeipodstawowezastosowaniakryptogra i

•Ochronainformacjiprzedniepowo“anymodczytem;

•Uwierzytelnianiedokument ó w;autoryzacjaicerty kacja;

•Uwierzytelnianieiidenty kacjapodmiot ó w

•Celespecy czne(kartyp“atnicze,elektronicznepieni¡dze).

Celemkryptoanalizyjestdostarczenie–rodk ó wzapobiegaj¡cychrealizacjicel ó w

kryptogra cznych.

Podstawowaterminologiakryptogra czna

•Systemyliczbowe;

•Zapispozycyjnyliczbca“kowitychor ó »nychpodstawach;

Ilo–¢cyfrwprzedstawieniuliczbydwsystemieopodstawiebwynosi[log b d]+1

•Algorytmkonwersjidosystemubinarnego;

Operacjenabitach;z“o»ono–¢obliczeniowa.

•kopiowaniebitu,dodawanie(operacjaXOR),przesuniƒcie

•Z“o»ono–¢obliczeniow¡mierzysiƒczasemwykonaniamierzonymilo–ci¡niezbƒd-

nychoperacjinabitach

•AlgorytmAwykonuj¡cyobliczenianamliczbachbinarnychmaz“o»ono–¢f(k 1 ,...,k m )

je–lidladowolnychk i -bitowychargument ó wx i ,i=1,...,m,czaspotrzebnynawy-

liczeniewarto–ciA(x 1 ,...,x m )nieprzekraczawarto–cif(k 1 ,...,k m ).Czastenjest

wielomianowyjeslif(k 1 ,...,k m )=k d 1

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

Z“o»ono–¢problem ó w

Teoriaz“o»ono–ciklasy kujeproblemy:

•Problem,kt ó rymo»narozwi¡za¢przypomocyalgorytmupracuj¡cegowczasie

wielomianowymjestpodatnylub“atwy;

•wprzeciwnymrazieproblemjesttrudny.

Innaklasy kacja:

•KlasaP:problemypodatne;

•KlasaNP:problemyrozwi¡zalnewczasiewielomianowymzpomocametody

niedeterministycznej

Oczywi–ciePNP.NiewiadomoczyP=NP.

•ProblemyNP-zupe“ne.S¡totakieproblemy,»egdybyokaza“osiƒ,»enale»yon

doklasyP,toP=NP

Funkcjaipermutacje

•Podstawowaterminologiafunkcyjna;

•Permutacje.

Terminologiakryptogra czna

•Podmiot,nadawca,odbiorca;

•wr ó g;

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

•tekst,dokument:daneprzechowywanelubprzesy“anewodpowiedniejpostaci;

tekstmo»eby¢jawnylubutajniony.

Opissystemukryptogra cznego

•AlfabetA;

•Przestrze«wiadomo–ciM,jegoelementytopodstawowejednostkiprzetwarzania

lubprostetekstyjawne;zbiorypodstawowychjednostekprzetwarzaniatoz“o»one

tekstyjawne

•Przestrze«kryptogram ó wC;jegoelementytoprostekryptogramy;zbiorypro-

stychkryptogram ó wtoz“o»onekryptogramy;

•Przestrze«kluczy;parametrydziƒkikt ó rymmo»liwejestdzia“aniealgorytm ó w

szyfruj¡cych.

•Systemkryptogra czny(kryptosystem):uk“adz“o»onyzalfabetuA,przestrzeni

M,C,Korazrodzinyprocedur(funkcji)E:M×K!C.D:C×K!M(dla

e2K,E e :=E(·,e):M!C;dlad2D,D d :=D(·,d):C!M)takich,»e

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

•Pasuj¡caparakluczy(e,d).

UwaganatematalfabetuWzasadziewszystkiewsp ó “czesnesystemykrypto-

gra czneprzetwarzaj¡tekstyjawnezapisanenumerycznie.Zkoleinaog ó “doku-

mentyzapisanes¡przypomocyznak ó walfa-numerycznych.Czƒstowiƒcpotrzebna

jestwstƒpnakonwersjatekstualfa-numerycznegodopostaciczystonumerycznej.

Mo»natozrobi¢nawielesposob ó w:naprzyk“adprzypomocykodudziesiƒtnego

lubbinarnegoASCII.Ka»dyznakdrukarskimo»nawtymkodziezapisa¢przy

pomocybajtu(ci¡gu8bit ó w).Zkoleis“owo(tzn.ci¡gznak ó wdrukarskich)sk“a-

daj¡cesiƒnp.z5znak ó wmo»nazapisa¢przypomocy40bit ó w;interpretuj¡ctaki

ci¡g(s“owo)jakozapispewnejliczbyca“kowitejwsystemiebinarnymodpowiada

on(ono)liczbiezzakresuod0do2 40 −1.

•Algorytmkryptogra czny:algorytms“u»¡cydoefektywnejrealizacjikryptosys-

temu,sformalizowanaprocedurasporz¡dzaniakryptogramuprostegozprostego

tekstujawnego;

•Algorytmyotwarteiograniczone;walgorytmachotwartychwszystkiesk“adniki

kryptosystemuibudowaalgorytmusaznane bezpiecze«stwoopierasiƒnapouf-

no–ciu»ywanychkluczy.

•Trybdzia“aniakryptosystemu(lubalgorytmukryptogra cznego):spos ó bu»y-

ciaalgorytmuwcelusporz¡dzaniakryptogram ó wz“o»onychzez“o»onychtekst ó w

jawnych.

•Protok ó “kryptogra czny:sekwencjaczynno–cipraktycznychniezbƒdnychdore-

alizacjiokre–lonegocelukryptogra cznego.

•Wcelurealizacjicelukryptogra cznegonale»ypodj¡¢czynno–ci:

1.Stworzenielubwyb ó rkryptosystemuijegowery kacja;

2.Wyb ó rkluczydoaktywacjiprocedurszyfruj¡cychideszyfruj¡cych;

3.Budowaalgorytmukryptogra cznegorealizuj¡cegokryptosystem;

4.Implementacjaprogramowaisprzƒtowaalgorytmu;

5.Sporz¡dzeniew“a–ciwegoprotoko“ukryptogra cznego;

6.Realizacjacelukryptogra cznegopoprzezu»yciezaimplementowanegoprogra-

mowolubsprzƒtowoalgorytmuidochowanieprotoko“u.

Rolawrogawkryptogra i

•Atak:wrogadzia“alno–¢;•Wr ó gpasywny:pods“uchujeidokonujekryptoana-

lizy;

•Wr ó gaktywny:przeszkadzaprzekazowiinformacjipoprzezprzerwanekomunika-

cji,mody kacjiprzekazuitp.

Ka»dyszyfrmo»naz“ama¢:metodaprzeszukiwaniaprzestrzenikluczy.

Najprostszyprzyk“adsytuacjikryptogra cznej

DwapodmiotyA,B;cel:poufno–¢komunikacji;ustaleniekluczynara»onenaatak

pasywny;atakaktywny.

Klasy kacjakryptosystem ó w

Rozwa»amykryptosystemKsk“adaj¡cysiƒzalfabetuA,przestrzeniwiadomo-

–cijawnychMikryptogram ó wC,zprzestrzenikluczyKorazrodzin{E e } e2K ,

{D d } d2K funkcjiszyfruj¡cychideszyfruj¡cych.

•Klasy kacjazewzglƒdunaposta¢przestrzeniM,tzn.postacipodstawowych

jednostekprzetwarzania,tj.prostychwiadomo–cijawnych.

•Kryptosystemnazywamyblokowymje–liM=A n ,tzn.m2Mwtedyitylko

wtedygdym=(a 1 ,...,a n ),a i 2A,i=1,...,n,awiƒcgdyprostetekstyjawnes¡

s“owami (ci¡gami)sk“adaj¡cymisiƒznliteralfabetu.W ó wczass“owam2M

nazywasiƒte»blokami,za–njestd“ugo–ci¡bloku.Wkryptosystemieblokowym

z“o»onetekstyjawnes¡ zdaniami z“o»onymizesko«czonejliczby s“ ó w .

Wkryptosystemieblokowym,abyokre–li¢dzia“aniefunkcjiszyfruj¡cejnale»yokre-

–li¢warto–¢E e (m)dlam2Mie2K.Wkryptosystemachtakichkryptogramy

s¡naog ó “tak»eblokamiokre–lonejd“ugo–ci

•Kryptosystemnazywamystrumieniowymgdyprostymitekstamijawnymis¡po-

jedynczes“owaalfabetu.Szyfrystrumieniowes¡wobectegoszyframiblokowymio

d“ugo–ci1.

•Klasy kacjazewzglƒduzale»no–cipomiƒdzypasuj¡cymikluczami.

•Wkryptosystemachsymetrycznych,dladanegokluczaszyfruj¡cegoe2K,“a-

twoznale„¢kluczdeszyfruj¡cydtaki,»epara(e,d)jestpasuj¡ca(np.e=d).

Innys“owyproblemznalezieniakluczadeszyfruj¡cegodpasuj¡cegodokluczae

jestproblemempodatnymobliczeniowo.Mowatak»eokryptosystemachzkluczem

poufnym.Obakluczemuszaby¢utrzymywanewtajemnicy.

Przyk“ad:Kryptosystemprzestawieniowy.NiechM=A n ,K=S n zbi ó r

permutacjizbioru{1,...,n}.Dlam=(a , ...,a n ),a i 2A,i=1,...,nie2K,

E e (m)=c=(a e(1) ,...,a e(n) ).Oczywi–cied=e −1 jestkluczemdeszyfruj¡cym

pasuj¡cymdoe.Je–linale»yzaszyfrowa¢tekstz“o»onym 1 ,...,m k ,tomo»nanp.

szyfrowa¢s“owopos“owie.Jesttonajprostszytrybstosowaniategoszyfru.Liczba

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: