Vis enkel innførsel

dc.contributor.authorTrontveit, Jan Inge
dc.date.accessioned2008-03-28T09:01:59Z
dc.date.issued2006
dc.identifier.urihttp://hdl.handle.net/11250/143880
dc.description.abstractNORSK: "Shrinking" generatoren er en populær representant for pseudotilfeldige sekvens generatorer (PTSG) som anvender såkalt uregelmessig klokking. Det karakteristiske ved denne familien av PTSG er at de har en eller flere lineært tilbakekoblede skift registre(LTSR) hvis klokking blir kontrollert av sekvensen til en av subgeneratorene. Denne sekvensen kalles klokke-kontroll sekvensen. I denne rapporten presenterer vi en algoritme som rekonstruerer klokke-kontroll sekvensen til en generalisert "shrinking" generator med tilstedeværelse av støy. "Shrinking" generatoren blir først redusert til en step1-stepE generator (en annen klasse av PTSG med uregelmessig klokking), hvor E avhenger av den maksimale lengden på etterfølgende nuller i ut-sekvevnsen til den klokkende delen av generatoren. Deretter utføres det et retningsstyrt søk for optimale og suboptimale stier i "edit-distance" matrisen som samsvarer med generatoren. Det tillatte vekt-avviket fra det optimale bestemmes av støy-nivået i den statistiske modellen av generatoren. Innvirkningen som utilstrekkelig estimering av lengden på ut-sekvensen fra den klokkede LTSR uten uregelmessig klokking har på nivået tilsvarende støy, diskuteres. Forsøksresultane som presenteres viser at totalt antall klokke-kontroll sekvens kandidater øker moderat etter hvert som den nødvendige klokke-kontroll sekvens lengden øker. Fordelen med dette angrepet i forhold til andre angrep rapportert i litteraturen, er at dette angrepet er effektivt selv om støy-nivået er relativt høyt og at løsningen garantert vil bli funnet.no
dc.description.abstractENGELSK: The shrinking generator is a popular representation of pseudorandom sequence generators (PRSGs) that employ so-called irregular clocking. This familiy of PRSGs is characterized by having one or more linear feedback shift registers (LFSRs), whose clocking is controlled by the output sequence of one of the subgenerators. Such a sequence is called clock-control sequence. In this thesis, an algorithm is presented that reconstructs the clock-control sequence in the generalized shrinking generator in the presence of noise. The shrinking generator is first reduced to a step1-stepE generator (another class of PRSGs with irregular clocking), where E depends on the maximum length of runs of zeros in the output sequence of the clocking part of the generator. Then a directed depth-first like search for optimal and suboptimal paths in the edit distance matrix corresponding to the generator is performed. The permitted path weight deviation from the optimum is determined by the noise level in the statistical model of the generator. Influence of inadequate estimation of the length of the output sequence of the clocked LFSR without irregular clocking on the level of equivalent noise is discussed. The experimental results that are presented show that the total number of candidate clock-control sequences increases moderately as the necessary clock-control sequence length increases. The advantage of this attack over the other attacks reported in the litterature is that this attack is effective even if the noise level is relatively high and that the solution is guaranteed to be found.en
dc.format.extent665223 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoengen
dc.subjectPTSGen
dc.subjectLTSRen
dc.subjectklokke-kontrollen
dc.subjectklokkingen
dc.subjectgeneratoren
dc.titleClock control sequence reconstruction in the generalized shrinking generatoren
dc.typeMaster thesisen
dc.subject.nsiVDP::Mathematics and natural science: 400::Information and communication science: 420::Algorithms and computability theory processing: 422en


Tilhørende fil(er)

Thumbnail

Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel