Kodeteori

Kodeteori er en matematisk spesialitet som omhandler lovene for informasjonskoding. Grovt sett er koding å transformere informasjon til et avtalt signal for kommunikasjon. Dekoding vil være den omvendte og komplementære prosessen av den forrige hvor det kommuniserte signalet blir transformert til den opprinnelige informasjonen. Fremveksten av kommunikasjon fra andre halvdel av det 20. århundre motiverte en sterk utvikling av kodeteori.

Introduksjon og historie

Kronologi [ 1 ]

År	Begivenhet
55 a. c.	Julius Caesar , som invaderer Storbritannia, bruker koder for å sende meldinger til generalene sine.
1750 e.Kr	Leonhard Euler legger grunnlaget for kryptografi med offentlig nøkkel med sitt teorem .
1844	Samuel Morse sender sin første melding ved å bruke koden sin .
1920 -tallet _	Enigma-maskinen er utviklet .
1950	Richard Hamming publiserer en grunnleggende artikkel for å lage kode som oppdager og korrigerer feil.
1970 -tallet _	Utvikling av offentlig nøkkelkryptering.

Siden koder brukes til å kommunisere informasjon , er et av problemene som all kode står overfor systematisk feil og også tilfeldig feil. Redundans er den eneste måten å forhindre feil. Menneskelige språk har en stor redundans som gir dem fleksibilitet på bekostning av, ja, effektivitet. Matematiske koder bruker en mer rasjonell redundans.

Det er koder kalt feildeteksjon , som gjør det mulig å oppdage endringer i en kryptert melding. De brukes mest i miljøer der meldingen kan sendes på nytt så mange ganger som nødvendig. Internett-protokoller, for eksempel, består av en nesting av kodinger fra transportnivået til det fysiske nivået, hvor hvert nivå har sitt eget feildeteksjonssystem.

Denne typen kode er utilstrekkelig i miljøer hvor kommunikasjon ikke kan gjentas og det er nødvendig å sikre til en viss grad at riktig informasjon blir mottatt. Et typisk og fargerikt eksempel er når et romskip sendes til de ytre delene av solsystemet og derfra må sende tilbake en serie bilder før for eksempel batteriene går tomme. Dette er en delikat situasjon, for hvis de elektromagnetiske bølgene som bærer informasjonen kommer forvrengt, mislykkes hele oppdraget. En kode som bare oppdager at informasjonen er feil, ville være ubrukelig. Noe mer er nødvendig, en kode som ikke bare er en feildetektor, men også en korrigerende .

For eksempel kan det enkleste kodesystemet være at en "0" representerer et "nei" og en "1" representerer et ja. I dette tilfellet, hvis jeg ønsker å sende et "ja", og det blir gjort en feil ved å sende en "0" i stedet for en "1", vil mottakeren av meldingen gjøre det motsatte av det som blir bedt om. Men hvis det i stedet blir avtalt at "00" er "nei" og "11" er "ja", så, hvis det er gjort en feil i et siffer, og for eksempel mottakeren mottar en "01", vil den oppdage at det var en feil, selv om du ikke vet hvilken som er den riktige meldingen. På den annen side, hvis konvensjonen er at "000" er "nei" og "111" er ja, og det er kjent at ved overføring av en melding er det bare mulig, på grunn av metoden som brukes, å gjøre en enkeltsifret feil , så, hvis når mottakeren mottar et "001", vil mottakeren vite at det er et "nei". Dermed, hvis vi sender en blokk med nuller, eller en blokk med enere, selv om noen feil er gjort i overføringen av noen sifre, vil det være nesten sikkert hva feilen er i den mottatte meldingen, og rette den. [ 2 ]

For tiden er fremskrittene som finner sted i denne disiplinen rettet mot bruken av Groebner-basene som et verktøy for koding og dekoding av feildeteksjonskoder.

Det effektive kodingsproblemet

Et av hovedproblemene med kodeteori er følgende. Anta at vi har en informasjonskilde som sender ut eller overfører " symboler " fra et visst sett som vi for pedagogiske formål ganske enkelt vil kalle "ord", slik at sannsynligheten for å sende ut et ord er uavhengig av det forrige symbolet , som er . Hvis det er et alfabet med D "bokstaver", hvilken kode skal tilordnes ordet ved å bruke "bokstaver" i alfabetet på en slik måte at man oppnår en så billig koding som mulig? [ 3 ] Formelt sett er en koding en kartlegging av settet med "ord" til settet av endelige sekvenser av "bokstaver" i alfabetet. En melding er en begrenset rekkefølge av ord, hvis en ordkoding er tilgjengelig, utvides den umiddelbart til meldinger ved sammenkobling: $\scriptstyle W=\{w_{1},\dots ,w_{n}\}$ $\scriptstyle P(w^{(t)})=w_{k}|w^{(t-1)}=w_{j}=P(w=w_{k})$ $\scriptstyle p_{i}=P(w=w_{i})$ $\scriptstyle \Sigma$ $\scriptstyle w_{i}$ $\scriptstyle E:W\to {\mathcal {P}}_{0}(\Sigma )$ $\scriptstyle m=w_{i_{1}}\dots w_{i_{n}}$

$E(m)=E(w_{i_{1}})\dots E(w_{i_{n}})$

Noen interessante kodingstyper er:

En koding er unikt dechiffrerbar hvis en endelig sekvens av er bildet av høyst én melding, det vil si når kartet E er injektiv . $\scriptstyle {\mathcal {P}}_{0}(\Sigma )$
En koding kan knekkes umiddelbart , eller prefikslignende, hvis to forskjellige ord ikke eksisterer og slik at det er en innledende sekvens av . $\scriptstyle w_{i}$ $\scriptstyle w_{j}$ $\scriptstyle E(w_{i})$ $\scriptstyle E(w_{j})$

Kraft ulikhet

McMillan ulikhet

Kryptografisk kryptering

Kryptografi eller kryptografisk koding er praksis og studie av sikre kommunikasjonsteknikker i nærvær av tredjeparter (kalt motstandere ). [ 4 ] Mer generelt handler det om å bygge og analysere protokoller som blokkerer motstandere; [ 5 ] ulike aspekter ved informasjonssikkerhet , som konfidensialitet , dataintegritet , autentisering og ikke-avvisning [ 6 ] er sentrale i moderne kryptografi. Moderne kryptografi eksisterer i skjæringspunktet mellom fagene matematikk , informatikk og elektroteknikk . Bruk av kryptografi inkluderer minibankkort , datamaskinpassord og elektronisk handel .

Kryptografi før moderne tid var effektivt synonymt med kryptering , konvertering av informasjon fra en lesbar tilstand til tilsynelatende tull . Forfatteren av en kryptert melding delte dekrypteringsteknikken som er nødvendig for å hente den opprinnelige informasjonen kun med de tiltenkte mottakerne, og forhindret dermed uønskede personer i å gjøre det samme. Siden første verdenskrig og bruken av datamaskinen har metodene som brukes til å utføre kryptologi blitt stadig mer komplekse og deres anvendelse mer utbredt.

Moderne kryptografi er sterkt avhengig av matematisk teori og databehandling; Kryptografiske algoritmer er designet rundt antakelser om beregningsmessig seighet , noe som gjør slike algoritmer vanskelige å knekke i praksis av enhver motstander. Det er teoretisk mulig å bryte et slikt system, men det er ikke mulig å gjøre det med noen kjente praktiske midler. Derfor kalles disse ordningene beregningssikre; Teoretiske fremskritt, for eksempel forbedringer i heltallsfaktoriseringsalgoritmer , og raskere datateknologi krever at disse løsningene kontinuerlig tilpasses. Det finnes informasjonsteoretiske sikkerhetssystemer som sannsynligvis ikke kan knekkes selv med ubegrenset datakraft; ett eksempel er engangsblokken , men disse ordningene er vanskeligere å implementere enn de beste teoretisk brytbare, men beregningsmessig sikre mekanismene.

Referanser

Notater

↑ Basert på "50 ting å vite om matematikk" av Tony Crilly.
↑ Eksempel hentet fra Tony Crillys bok "50 Things to Know About Math".
↑ Dominic Welsh, 1988, s. femten
^ Rivest, Ronald L. (1990). Kryptologi. I J. Van Leeuwen, red. Håndbok i teoretisk informatikk 1 . Elsevier.
↑ Bellare, Mihir; Rogaway, Phillip (21. september 2005). "Introduksjon". Introduksjon til moderne kryptografi . s. 10.
↑ Menezes, AJ; van Oorschot, PC; Vanstone, SA (1997). Håndbok for anvendt kryptografi . ISBN 978-0-8493-8523-0 . (krever registrering) .

Bibliografi

Tony Crilly (2011). 50 ting å vite om matematikk . Red. Ariel. ISBN 978-987-1496-09-9 .
Dominic Welsh (1988): Codes and Cryptography , Clarendon Press, Oxford, ISBN 0-19-853287-3

Se også

informasjonsteori