Liczby losowe, a kryptografia - referat.pdf - Kryptografia - sir_matin

Liczbylosowe,akryptogra a

Pawe“D¡browski

18czerwca2001

http://ving.edunet.pl/projects

1Liczbylosowe

1.1Cotos¡generatoryliczblosowych?

Istotagenerator ó wliczblosowychjestdo–¢prosta.Poprzezlosowyci¡gmo»emy,

naprzyk“ad,uwa»a¢ci¡gbit ó wgenerowanychpoprzezrzucaniemonet¡:wyrzuce-

niereszkidaje1,or“aza–0.Takipojedynczyrzutmonet¡jestniezale»ny

odpozosta“ychrzut ó w.Dodatkowomusimyza“orzy¢,»emonetajestdobrze

wywa»onacooznacza,»eotrzymanieor“awjednymrzuciejesttaksamopraw-

dopodobnejakwyrzuceniereszki.

Liczbylosowes¡niezbƒdnymelementemwielualgorytm ó w.Wykorzystuje

siƒjemiƒdzyinnymiwalgorytmachsymulacyjnychczyrandomizowanychoraz

wnajbardziejnasinteresuj¡cej-kryptogra i.S“awnyDonaldE.Knuthpisze:

Therearereportsthatmanyexecutivesmaketheirdecisionsby ippingacoin

orbythrowingdarts,etc.Itisalsorumoredthatsomecollegeprofessorsprepare

theirgradesonsuchabasis.Sometimesitisimportanttomakeacompletely

"unbiased"decision;thisabilityisoccasionallyusefulincomputeralgorithms,

forexampleinsituationswherea xeddecisionmadeeachtimewouldcause

thealgorithmtorunmoreslowly .

Wpraktycegeneratoryliczblosowych,pr ó bujesiƒtworzy¢wykorzystu-

j¡czdarzenialosowewkomputerze.Zdarzeniatepochodz¡zjegourz¡dze«

zewnƒtrznych,awszczeg ó lno–cizklawiaturyorazmyszyitp.Zdarzeniatakie

s¡gromadzone,wceluuzyskaniacorazwiƒkszejliczbylosowychbit ó w.Niestety,

tylkobardzoniewielk¡czƒ–¢otrzymanychodurz¡dze«danychmo»nauzna¢za

losow¡.Np.naci–niƒcieklawiszaodanymkodziejestbardzoma“olosowym

zdarzeniem:zwykles¡tokodyASCIIma“ychliter,akorelacjamiƒdzynimijest

bardzodu»a.Tworz¡cgeneratorliczblosowychbudujesiƒgotak,»ebydodanie

ca“kowiciedeterministycznychci¡g ó w,np.100000bajt ó wotejsamejwarto–ci,

niezmniejszy“olosowo–cizawartejwgeneratorze.Generatorliczblosowych

mo»eutrzymywa¢specjalnylicznik,kt ó ryliczy,ilejestjeszczelosowychbit ó w

wgeneratorze.Implementacjatakiegolicznikajestjednakbardzotrudna,dlat-

egostosujesiƒraczejliczenie"naoko"itrudnopowiedzie¢,czyztychoblicze«

otrzymujesiƒsensownewyniki.Dodatkow¡cech¡generatoras“u»¡cegodocel ó w

kryptogra cznychpowinnoby¢,»enawetznaj¡ckodgeneratoraiodczytuj¡cz

niegokolejnetworzoneprzezniegoliczbylosowe,nawetje»eliniedostajeon

»adnychkolejnychlosowychbit ó w,niepowinnosiƒda¢przewidzie¢,jakajest

nastƒpnaliczba.

1.2Liczbypseudolosowe

Dotychczasniemadostƒpnychnarynkutanichiefektywnychurz¡dze«generuj¡-

cychlosoweci¡gi.Decyduj¡cympowodemjestto,i»taniomo»nauzyska¢tzw.

ci¡gipseudolosowezapomoc¡specjalnychalgorytm ó w.Ci¡gipseudolosowe

maj¡wszystkiew“asno–cici¡g ó wlosowych,jakieefektywniemoznaprzetestowa¢,

alejednocze–niemog¡by¢wygenerowanewdeterministycznyspos ó b.Jedynym

losowymelementemtakiegoci¡gujestzarodek.Ci¡gpseudolosowyjesttwor-

zonytak,»ei-tyelements i jestwyznaczonyprzezpewiendeterministyczny

algorytmzzarodkax,indeksuiorazwarto–cis 1 ,...,s j−1 .Zarodekjestzwykle

stosunkowokr ó tkimci¡giem,wiƒcmo»nagowygenerowa¢takimimetodami,jak

poprzezmierzenieodstƒp ó wczasupomiƒdzyuderzeniamipalc ó wwklawiaturƒ.

Zdrugiejstrony,zarodekmusiby¢natyled“ugi,bywykluczy¢mo»liwo–¢odt-

worzeniazarodkapoprzezprzegl¡daniewszystkichzarodk ó wici¡g ó wprzeznich

generowanych.

Ci¡gipseudolosowes¡wykorzystywane,naprzyk“ad,wdziedziniealgoryt-

m ó wzrandomizowanych,symulacjachproces ó wstochastycznychitp.Metody

generowaniaci¡g ó wpseudolosowychu»ywanewtychdziedzinachniemog¡by¢

stosowanedocel ó wkryptogra cznych,gdy»wkryptogra i»¡damyodnichdo-

datkowoabynieby“yrozr ó »nialneodprawdziwychlosowychci¡g ó wprzyu»yciu

»adnychpraktycznychmetod.

1.3W“asno–cici¡g ó wpseudolosowych

1.3.1Nierozr ó »nialno–¢

Je»elici¡gbit ó wd“ugo–cilwygenerujemywspos ó bnaprawdƒlosowy,toka»dy

ci¡gjestgenerowanyztymsamymprawdopodobie«stem 1 2 l .Natomiastje»eli

ci¡gid“ugo–cilgenerujemyzapomoc¡zarodk ó wd“ugo–cik(k<l),tomo»emy

otrzyma¢conajwy»ej2 k r ó »nychci¡g ó wd“ugo–cil.Tymsamym,przyza-

“o»eniu,»er ó »nezarodkidaj¡r ó »neci¡gipseudolosoweorazka»dyzarodek

jestjednakowoprawdodobny,niekt ó reci¡giotrzymujemyzprawdopodobie«st-

wem0,aniekt ó rezprawdopodobie«stwem 1 2 l .Wynikast¡d,i»rozk“adypraw-

dopodobie«stwaci¡g ó wlosowychipseudolosowychod“ugo–cilr ó »ni¡siƒmiƒdzy

sob¡.Pytaniejednak,czynapodstawiekilkuwygenerowanychci¡g ó wlbit ó w

jeste–mywstaniestwierdzi¢,czymamydoczynieniazgeneratoremliczblosowych

czypseudolosowych.Wprzypadkuci¡guprzedstawionychprzypomocygener-

atorapseudolosowegoniemo»emyzdoby¢stuprocentowejpewno–ci,gdy»ka»dy

ci¡gmo»eby¢wygenerowanyprzypomocygeneratoraliczblosowych.Dlatego

te»rozr ó »nianiegenerator ó wjestprocedur¡,wkt ó rejmo»nam ó wi¢jedynieo

prawdopodobie«stwieprawid“owejodpowiedzi.

Formalnie,niechg 1 ig 2 bƒd¡dwomageneratoramici¡g ó wod“ugo–cil.Dla

ci¡guxd“ugo–cilii2{0,1},niechp i (x)bƒdzieprawdopodobie«stwem

wygenerowaniaxprzezg i .NiechAbƒdziealgorytme.Wtedyde niujemy

E A (p i )= X

x2{0,1}l

p i (x)Pr(A(x)=1)

M ó wimy,»eg 1 ig 2 s¡-rozr ó »nialnezapomoc¡algorytmuAje–li

|E A (p 1 )−E A (p 2 )|>.W“asno–¢jak¡chcieliby–myosi¡gn¡¢abym ó c

wykorzysta¢generatorpseudolosowychci¡g ó wg 1 wkryptogra i,tojego

nierozr ó »nialno–¢odgeneratoralosowegog 2 :dlaka»degowystarczaj¡cego

du»ego.

1.3.2Nieprzewidywalno–¢

Jesttow“asno–¢m ó wi¡ca,»ebezznajomo–cizarodkaxniedasiƒobliczy¢w

praktyces i ,i-tegobituci¡gupseudolosowego,zbit ó ws 1 ,...,s i−1 .Wrzeczy-

wisto–cipojƒcianierozr ó »nialno–ciinieprzewidywalno–cis¡zesob¡powi¡zane.

2Kryptogra a

Kryptogra atojednozwa»niejszychzastawowa«liczblosowych.WPolsce

istniejejejprawnade nicja:

Kryptogra atodziedzinawiedzyzajmuj¡casiƒzasadami,narzƒdziamii

metodamiprzekszta“caniadanychwceluukryciazawartychwnichinforma-

cji,zapobieganiamo»liwo–citajnegoichmody kowanialubeliminacjidostƒpu

donichosobomniepowo“anym.’Kryptogra a’ograniczasiƒdoprzekszta“cania

informacjizapomoc¡jednegolubwiƒcej tajnychparametr ó w"(np.szyfr ó w)

i/lubzwi¡zanegoztymzarz¡dzaniakluczami.Uwaga:’tajnyparametr’:warto–¢

sta“aalboklucztrzymanywtajemnicyprzedosobamipostronnymialboznany

wy“¡czniepewnejgrupieos ó b"(Dz.U.Nr129,poz.598)

Jejzastosowanie:

a)ochronadanychprzedniepowo“anymdostƒpem.

b)uwierzytelnianiedokument ó w.

c)ochronaprywatno–cipocztyelektronicznej.

Naswojepotrzebykryptogra apotrzebujesilnychgenerator ó wliczblosowych,

2.1Historiakryptogra i

Pocz¡tkikryptogra isiƒgaj¡czas ó wstaro»ytno–ci.Oko“o4000lattemustaro»ytni

Egipcjaniepotra liszyfrowa¢swojehieroglify.Tak»estaro»ytniHebrajczycy

szyfrowaliniekt ó res“owawswoichskryptach.Cociekawestopie«skomplikowa-

niatychmetodby“znacz¡coni»szyni»stanwiedzymatematycznejwka»dej

w“a–ciwieepoce.Stosowanew ó wczasmetodyby“yzazwyczajdo–¢prymitywnei

pozwala“ynaz“amanieszyfr ó wdostateczniezdeterminowanemuprzeciwnikowi.

Sytuacjauleg“azmianieju»wpierwszejpo“owedwudziestegowieku,Zbudowano

wtedywieleurz¡dze«mechanicznychiwykorzystywanojepowszechniepodczas

drugiejwojny–wiatowej.Czƒ–¢tychsystem ó wzosta“askuteczniez“amananp.

Enigma.Dopieroprawdziw¡rewolucjƒpodwzglƒdemprojektowaniasystem ó w

szyfruj¡cychprzyni ó s“rozw ó jelektroniki,daj¡cyolbrzymiemo»liwo–cioper-

acjiobliczeniowychniskimkosztem.Rozw ó jkryptogra iodswychpocz¡tk ó w

by“bardzosilniezwi¡zanyzcelamiwojskowymi.Wzwi¡zkuztymwszelkie

pracezdziedzinykryptogra imia“ycharaktertajnyiichrezultatynieby“y

publikowane.Prze“omnast¡pi“wlatachsiedemdziesi¡tychwrazzodkryciem

asymetrycznychalgorytm ó wszyfruj¡cych.

2.2Algorytmyasymetryczne

Algorytmasymetrycznytoalgorytm,wkt ó rym:

•kluczewystƒpuj¡wparach:jedenkluczdoszyfrowaniaijedendodeszyfrowa-

nia.

•opublikowaniejednegozkluczywystƒpuj¡cegowparzepraktycznienie

zdradzadrugiegozkluczy,nawetgdymo»nawtymceluwykona¢do–¢

z“o»oneobliczenia.

•zwyklejedenzkluczywparzejestpowszechniedostƒpny-mo»etoby¢

kluczszyfruj¡cylubdeszyfruj¡cy,wzale»no–ciodzamierzanychzastosowa«

(kluczpubliczny).Drugijestkluczemtrzymanymwtajemnicyprzezjego

posiadacza(kluczprywatny).

2.2.1AlgorytmRSA

RSAjestjednymznajwa»niejszychdlapraktykialgorytm ó wkryptogra cznych.

NazwaRSApochodziodjegoautor ó w:Rivesta,ShamiraiAdlemana.Liczby

losowestosujƒsiƒtudogenerowaniakluczy.Odmomentuprzedstawiania

RSAdokonywaneby“ylicznepr ó byz“amaniaszyfr ó wgenerowanycht¡metod¡.

Tylkoograniczonesukcesyosi¡gniƒtonatympolu.Ichkonsekwencj¡by“ozwiƒk-

szenied“ugo–cikluczyu»ywanychprzezRSA.AlgorytmRSAprzedstawiasiƒ

nastƒpuj¡co:

1.Losowowybieramydwiedu»eliczbypierwszep,q.

2.Losowowybieramyliczbƒetak,abyei(p−1)(q−1)by“ywzglƒd-

niepierwsze(wybieramyeiprzyu»yciualgorytmuEuklidesaobliczamy

NWD(e,(p−1)(q−1));je–liliczbaezosta“a„lewybranatopowtarzamy

pr ó by,a»znajdziemyw“a–ciwee).

3.Zapomoc¡algorytmuEuklidesaznajdujemydtakie,»e:

ed=1mod(p−1)(q−1)

4.Obliczamyn:=pqikasujemyliczbyp,qtakabyniepozosta“ponich

»aden–lad.

5.[e,n]jestwygenerowanymkluczempublicznym,[d,n]jestkluczempry-

watnym.

Szyfrowanie(szyfrowanemog¡by¢liczbym<n)odbywasiƒnastƒpuj¡co:

E [e,n] (m)=m e modn

Deszyfrujemypodobnie:

D [d,n] (m)=c d modn

Jakwida¢pojawiasiƒwalgorytmieproblemgenerowanialosowychdu»ych

liczbpierwszych.Wydajesiƒtotrudnymzadaniem.Naszczƒ–cieistniejedu»o

liczbpierwszych:dlaka»degoxilo–¢liczbpierwszychwprzedzialemiƒdzyx/2a

xwynosioko“ox/lnx.Nawet,gdyprzypadkowetra enienaliczbƒpierwsz¡jest

do–¢prawdopodobne,stoimywobectegozagadnienia,jakodr ó »ni¢liczbypier-

wszeodliczbz“o»onych.Najprostsz¡metod¡by“obydokona¢rozk“adunaczyn-

nikipierwszeka»dejwylosowanejliczby.Jednakdlaliczbrozwa»anegorozmiaru

jesttopraktycznienieniewykonalnezewzglƒdunazakresbezpiecze«stwa,jaki

maj¡gwarantowa¢szyfryRSAkonstruowanezaichpomoc¡.Wyj–ciemjest

stosowanietest ó wpierwszo–ciliczb.Wszystkieznanetestys¡testamiproba-

bilistycznymi,tzn.dlazadanego(dowolnego)argumentuxmog¡siƒpomyli¢z

pewnymma“ymprawdopodobie«stwem.

2.2.2AlgorytmemElGamala

AlgorytmElGamalabazujenatrudno–ciobliczeniatzw.dyskretnychlogaryt-

m ó w.Szyfrowaniezaka»dymrazemwykorzystujelosowowybran¡liczbƒ,co

powoduje,»etensamtekstjawnymo»eby¢wr ó »nyspos ó bzaszyfrowana.Ten

algorytmokre–lajednoznaczniekt ó ryzparykluczydoczegomas“u»y¢.Klucz

publicznys“u»ydoszyfrowania,natomiastprywatnydodeszyfrowaniadanych.

Nieistniejetuzamienno–¢kluczytakjakby“otowprzypadkualgorytmuRSA.

Cech¡charakterystyczn¡iniekiedywad¡jestto,»ekryptogramyuzyskiwanew

wynikualgorytmuElGamalas¡dwukrotnied“u»szeodtekstujawnego.

Napocz¡tekprzydasiƒwyja–nieniepojƒciadyskretnegologarytmu,awiƒc

wzasadzienajwa»niejszegoelementuca“egoalgorytmu.

Przeprowad„mynastƒpuj¡ceza“o»enia:

Niechpbƒdzieliczb¡pierwsz¡,natomiastgeneratoremZ p (dlaka»dejliczby

xwiƒkszejod0imniejszejodpistniejetakaliczbaidlakt ó rejzachodzi

zale»no–¢x= i modp).Trudno–¢dyskretnegologarytmupolegana

znalezieniudladanegowiƒkszegood0imniejszegoodpliczbyitakiej,»e

a i =modp.

Liczby losowe, a kryptografia - referat.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: