Liczby losowe, a kryptografia - referat.pdf
(
182 KB
)
Pobierz
3971264 UNPDF
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«
1
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
2
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
3
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
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.
5
Plik z chomika:
sir_matin
Inne pliki z tego folderu:
Liczby losowe, a kryptografia - referat.pdf
(182 KB)
kryptografia i generatory pseudolosowe.pdf
(266 KB)
Kryptografia--Teoria I Praktyka Zabezpieczania-97--Kutylowski-p37.pdf
(569 KB)
Inne foldery tego chomika:
agh
Algebra
Algebra liniowa
Analiza
ksiazki aktywne
Zgłoś jeśli
naruszono regulamin