Skrift og kryptografi

Kryptografi (Ggr. kryptos – hemmelig; graphein – skrive) er skjuling av innhold i strenger med tekst og tall i en sifferskrift basert på en chiffer-algoritme. Et chiffer er en kodeskrift. I vår tid hvor det meste av kommunikasjon skjer digitalt over internett og data blir lagret på servere over store deler av verden, er det et meget stort behov for å kunne skjule tekst- og tallinnholdet for utenforstående via kryptering. Teksten blir lesbar ved en dekryptering. Kryptologi er læren om hemmelig og sikker kommunikasjon. Kryptografi er læren om hemmelighold av skriftlig informasjon og lydkommunikasjon ved bruk av matematiske metoder. 

Det pågår en kontinuerlig kamp mellom hackere og kodebrytere, og de som er ansvarlige for vår datasikkerhet. Slumptallsgeneratorer er ikke tilfeldige nok til å anvendes innen kryptografi, siden de bare produserer pseudoslumptall. Legg merke til https:// på nettsider, og mange ønsker å kryptografere sine e-poster. Edward Snowden viste hvordan bla. NSA samler informasjon, og det samme gjør diktaturene Kina og Russland, samt mange andre.

Ved kryptering omformes klartekst til kryptert tekst, og ved dekryptering av den krypterte teksten kommer man tilbake til den originale klarteksten. Det er både symmetriske og assymetriske krypteringssystemer, sistnevnte med en kjent offentlig nøkkel og en privat hemmelig nøkkel.

Det er mange algoritmer for kryptografering basert på faktorisering av meget store primtall, eliptiske funksjoner (viste seg ikke å være sikker), og man fabler nå om kvantekryptografering, som nå er på eksperimentstadiet. 

Skrift

Selv om det ikke var skrevet i kode var de egyptiske hieroglyfene lenge en utfordring, var det lydskrift (fonogram) eller bildeskrift (piktogram, semagram) ? Thomas Young, kjent for oppdagelsen av lysets bølgenatur, gjorde noen innledende studier av innrammete hieroglyfer (kartusj), det var lydskrift, og Young kunne identifisere navn som Ptolemaios og Berenike. 

Rosettasteinen fra 196 fvt, med felles tekstinnskript i hieroglyfer, demotisk (en enklere og folkelig utgave av hieroglyfene) og gresk var et viktig hjelpemiddel. Imidlertid var det lingvisten Jean François Champollion som med kunnskaper i gammelkoptisk løste gåten, Précis du système hiéroglyphique (1824).  

En annen utfordring er den eldre skriften Linear A og den yngre Linear B, oppdaget under Arthur Evans utgravninger på Knossos, Kreta. Var skriften minoisk eller gresk ?  Alice Kober fant at Linear B inneholdt gramatikk med kasus, bøyningsformer, bindestavelser og stavelser med konsonanter og vokaler. Det var imidlertid Michael Ventris og John Chadwick som løste gåten, Linear B er arakisk gresk, Evidence for Greek dialect in the Mycenaean archives (1953). Et språk fra Odyssevs og Homers tid.  Jfr. Faistos disken, nå i det Arkeologiske muséet, Heraklion.

QWERTY-tastatur på skrivemaskiner med disse øverst til venstre og de vanligste bokstavene I engelsk plassert lengst fra hverandre slik at bokstavarmene ikke hektet seg I hverandre ved rask skriving. Introdusert av Remington i 1873.

Kryptografi

Kryptografi (gr. kryptos- skjult; graphein-skrive) er hemmelig skrift som går ut på å skjule innholdet i en tekst i form av en tall- eller bokstavkombinasjoner, enten ved transposisjon (bokstavene stokkes og bytter plass i et anagram) eller substitusjon (bokstavene beholder sin plass, men bytter identitet). Betår meldingen av n bokstaver inkludert mellomrom er det n fakultet (n!) mulige kombinasjoner. Et chiffer (siffer) lages ved kryptering (koding, enchiffrering) hos avsender via en klartekst, en kryptoalgoritme og en kodenøkkel. Den chiffrerte meldingen blir dechiffrert (dekodet, dekryptert) hos mottaker vha. en dechiffreringsalgoritme og en kodenøkkel, og den opprinnelige klarteksten kommer tilsyne.

I enkleste form gis hver bokstav i alfabetet et fortløpende heltall med start 1.  Julius Cæsar sendte under Gallerkrigen krypterte meldinger til Cicero. I en Cæsar-forskyvning forskyves alfabetet et bestemt antall plasser,  noe som gir 25 forskjellige chiffer (28 hvis æ,ø og å inkluderes. For eksempel forskyve alfabetet 3 plasser:

bokstav nr V3

1   A   D

2   B   E

3   C   F

4   D  G

5   E  H

6   F   I

7   G  J

8   H  K

9    I   L

10  J  M

11  K  N

12  L  O

13  M  P

14  N  Q

15  O  R

16  P  S

17  Q  T

18  R  U

19  S  V

20   T  W

21   U  X

22    V  Y

23   W  Z

24    X  A

25    Y  B

26    Z  C

For å gjøre det litt vanskeligere tok man hensyn til frekvensen av bokstavene i språket (homofon substitusjon), og kodet hver av de vanligst forekommende bokstavene med flere forskjellige symboler. En annen måte var å starte alfabetet med et nøkkelord, og deretter fortsette med de resterende bokstavene i alfabetet  som ikke inngikk i nøkkelordet. I et bokchiffer startet man nummerering av bokstavene forløpende i teksten i en bok som var avtalt på forhånd. Et Vegienèrkvadrat (tabula recta) består av først et alfabet etter fulgt radvis av 26 (eller 29) alfabet, hver med en trinnvis fra 1 økende Cæsar-forskyvning. Det har fått navn etter Blaise de Vigenère 1523-1596) som bl.a. skrev en avhandling om hemmelig skrift, Traité de chiffres ou secrètes maniéres d´escrive (1586).

Gjennom historien er det laget en lang rekke chiffer: Maria Stuart chiffer; det tyske ADFGVX-chiffer fra 1. verdenskrig som var både et transposisjons- og substitusjonschiffer; de tyske chiffermaskinene Enigma og Lorenz (56 bits nøkler) fra 2. verdenskrig, som ga kodeknekkerne ved Bletchley Park en utfordring, bl.a. Marian Rejevski og Alan Turing. Datamaskinene ga mulighet for digital i stedet for mekanisk kryptografering.

Alan Turing frimerke

Kryptografering og store primtall

Enigma siffermaskinen som ble brukt under andre verdenskrig var en siffermaskin med 26 roterende hjul på samme akse, og på hvert hjul var det et stokket alfabet.

Kryptografi

Bokstaven E er den vanligste og blant annet polske matematikere bidro til å løse enigma-koden. Ved kryptografi kan bokstaver omdannes til tall (substitusjon) og tallene kan stokkes (transposisjon).

Innen kryptografi for å kode meldinger brukes to store primtall p og q, hvert av dem med >300 siffer. Produktet av disse to primtallene gir et tall N (p∙q =N) som er en offentlig kjent nøkkel (”public key”) som kan brukes til å kode meldinger, men kan ikke brukes til å dekode meldingene. De to store primtallene p og q er hemmelig for alle andre enn den som laget koden, og kan for sikkerhets skyld ødelegges straks nøkkelen er laget.  Nøkkelen N baserer seg på at faktorisering av store primtall er nesten en umulig oppgave selv med de raskeste datamaskinene i verden.

Whitfield Diffie og Martin Hellman utviklet i 1976 en kryptograferingsteknikk  (Diffie-Hellman nøkkelutveksling) basert på primtallsfaktorisering, offentlig nøkkel og privat nøkkel.

I 1977 kunne Ronald Rivest, Adi Shamir og Leonard Adleman utvikle RSA koden basert på store primtall.

I tillegg trenger man to tall k til koding og d til dekryptering(dekoding). Tallene k og d bestemmes ut fra formelen:

\(\displaystyle \frac{(p-1)(q-1))}{kd - 1}\)

Tallene N og k er offentlige nøkler og N og d er private nøkler (”private key”), og som nevnt er de store primtallene p og q hemmelige og kastes.

En bokstavmelding må først omformes til tall og det kan gjøres enkelt ved av A=01, B=02, C=03, D=04 osv. mellomrom=00.

Hvis man har en bokstavmelding M så vil

Mk/N gi en rest C som er lik den kodete meldingen:

\(\displaystyle C=M^k \bmod N\)

Tallet d brukes til dekryptering hvor man kommer tilbake til den opprinnelige meldingen ved:

\(\displaystyle C^d \bmod N=M\)

Vi benytter oss av Fermats lille teorem:

Hvis p er et primtall og n er et heltall som ikke har p som faktor så er:

\(\displaystyle n^{p-1}=1 \bmod p\)

slik at np-1 vil alltid ha rest 1 når dividert på p.

For eksempel hvis vi velger 5 som et primtall og tar et tilfeldig tall som ikke har 5 som faktor for eksempel 7 så har vi:

Potenser av 7

Potens av 7 modulo 5

71 =7

2

72 =49

4

73 =343

3

74 =2401

1

75 =16807

2

Vi ser at 75-1= 1 mod 5, og 75=2 mod 5 er tilbake til utgangspunktet.

Diffie-Hellman-Merkle-kryptering

Enhver utfordring for koding består i å overføre kodenøklene på en trygg og sikker måte mellom avsender og mottaker. Muligheten lå ARPA-net frigitt til sivil bruk i 1982, grunnlaget for Internet, som muliggjorde utveksling av kryptografiske nøkler over et usikkert offentlig nett mellom to eller flere personer som ikke kjenner hverandre. De som ga seg i kast med utfordringen var bl.a, Whitfield Diffie (f. 1944), Martin Hellman (f.1946) fra Standford-universitetet og Ralph Merkle. Svaret lå i modulær matematikk. Det er da Diffie forslår prinsippet med en asymmetrisk nøkkel, Diffie-Hellman-Merkle-metoden. En offentlig kjent krypteringsnøkkel som alle kan bruke til å kryptere meldinger, og en privat nøkkel som brukes til å dekryptere ("public key - private key"). Selv den som har kryptert meldingen kan ikke åpne den etter at den er kryptert, det er det bare den som har den private nøkkelen. Hva slags matematiske enveisfunksjoner er det som klarer dette ? En klokke virker etter prinsippet addisjon modulo 12, moldulær matematikk.

Man kan vise prinsippet ut fra følgende formel:

\(\displaystyle y^x (\bmod m)\;\;\; y<m\)

Astrid og Bjørn avtaler uten hemmeligheter og uten å møtes to primtall p=23 og en base g=5. Dette er offentlige nøkler ”public key”) åpent tilgjengelig for alle.

Deretter velger Astrid et hemmelig tall (privat nøkkel, ”private key”) for eksempel a=6 som hun holder skjult for alle andre,  og setter dette inn i formelen

\(\displaystyle A=g^a \bmod p\)

Dette gir tallet A=8 som hun sender til Bjørn.

\(\displaystyle B=g^b \bmod p\)

Bjørn gjør tilsvarende og velger seg en hemmelig tall (privat nøkkel) for eksempel b=15,

dette gir tallet B=19 som han sender til Astrid. Astrid beregner:

\(\displaystyle S=B^a \bmod p\)

Bjørn gjør tilsvarende og beregner:

\(\displaystyle S=A^b \bmod p\)

Vips, nå har begge har nå samme nøkkel S=2,  uten å ha sendt selve nøkkelen over nettet. Ukjent for innsyn er a, b og S

Selv om en utenforstående Luring skaffer seg tallene P=23, g=5, A=gamodp = 8 og B=gbmodp =19 som er blitt sendt åpent over nettet, kan han vanskelig finne at nøkkelkoden S = 2, som nå både Astrid og Bjørn besitter. Dette blir eksempel på en symmetrisk nøkkel som kan brukes til både enchiffrere og dechiffrere.

Vi kan bytte ut p, g, a og b med andre tall og se at prinsippet stemmer, men man ser også at velger man store tall stanger man fort hodet i taket. I virkeligheten bruker man primtall p med flere hundre siffer og hemmelige slumptall a og b kan bestå av 100 siffer, mens g  er et relativt lite primtall.

Litteratur:Wikipedia

RSA-koden

Selv om James Ellis, Clifford Cock og Malcolm Williamson ved GCHQ i Cheltenham, hadde funnet løsningen tidligere, så er det Ronald Rivest, Adi Shamir og Leonard Adleman ved MIT som sikret seg patentet på RSA metoden. Metoden baserer seg på en offentlig nøkkel n, kjent for alle, som er produktet av to meget store primtall p og q, helst av samme bitslengde

\(\displaystyle n=pq\)

Primfaktorene p og q holdes hemmelig. n er modulus for både den offentlige og private nøkkelen. n uttrykt i bits angir nøkkellengde. 

Beregner Eulers phifunksjon:

\(\displaystyle \phi (n)= (p-1)(q-1)\)

hvor φ(n) også kalles Eulers totient funksjon.

I tillegg trenger man en offentlig nøkkel til, k, som skal brukes til koding, hvor 1<k<φ(n).

k og φ(n)må ikke ha noen felles faktorer.

Velger et heltall k med kort bitlengde og liten Hamming vekt som eksponent slik at

\(\displaystyle 1<k<\phi (n)\)

og største felles divisor gfd(k,φ(n)=1, dvs. k og φ(n) er koprimtall. k er eksponenten i den offentlige nøkkelen. Hammingvekt er summen av antall symboler som er forskjellig fra null.  

Alle bokstaver og tall har en decimal ASCII-kode, eller vi kan på annen måte angi bokstaver med tall, og derved kan vi nå nå kode og kryptere en hvilken som helst bokstav eller tall M til C ifølge formelen:

\(\displaystyle C=M^k(\bmod n)\)

For dekoding trenger mottakeren en privat nøkkel d, og den offentlige nøkkelen n,  og vi kommer tilbake til M ved følgende:

\(\displaystyle C^d(\mod n)=M\)

Dekrypteringseksponenten d i den private nøkkel velges slik at 

\(\displaystyle k \cdot d \equiv 1(\bmod (p-1)(q-1) \equiv 1 (\bmod \phi (n)) \)

φ(n) må også holdes hemmelig.

For den som ønsker å vite mer har Simon Sing skrevet en utmerket og morsom bok: The code book. The science of secrecy from ancient Egypt to quantum cryptography (1999), som også foreligger på norsk.

Her kan man også lese om hvordan Phil Zimmermann utviklet kryptosystemet ”Pretty Good Privacy”, PGP, som er et symmetriske IDEA-chiffer som ligner DES. I PGP er alle prosessene automatisert, hvor bl.a. tilfeldige musebevegelser gir tilfeldige primtall p og q. I takt med datamaskiner med økt regnekapasitet er kryptosystemer stadig utsatt for angrep fra kodeknekkere, noe som krever stadig større primtall og bitslengde, 126 bits er ikke nok. 

SIKE («Supersingular Isogeny Key Encapsulation») er et krypteringssprogram som av NIST («National Institute of Standards and Technology») var planlagt brukt ved kvantedatamaskinenens inntog, og som skulle kunne erstatte krypteringssysteme RSA, Diffie-Hellmann, ChaCha, Salsa20 og elliptisk kurve kryptografi (ECC). Algoritmen Supersingular Isogeny Diffie-Hellman nøkkelutvekslinsprotokoll (SIDH) brukt av SIKE ble kodeknekket i løpet av en times tid med gode matematikkkunnskaper (Lim og splitt-teorem utviklet av matematikeren Ernst Kani i1997) og en vanlig datamaskin. Den er en analog til Diffe-Hellman nøkkelutveksling men anvender en supersingulær isogeni-graf. Supersingulære elliptiske kurver er en type elliptiske kurver beskrevet av Hesse i 1936 oppdaget i arbeidet med Riemannhypotesen for elliptiske kurver. I algebraisk geometri er en isogeni en morfisme, et strukturbarende avbildning fra en struktur til en annen ,av en algebraisk gruppe (gruppevarietet) som er subjektiv og har endelig kernel.

Kryptografering av datakommunikasjon

Kryptologi mellom ukermaskin og tjenermaskin

VPN med (IPSEC (Internet Protocol Security) gir sikker kommunikasjon i kobling to nettverk sammen så det fungerer som ett LAN selv om de er fysisk adskilt.

TLS (Transport Layer Security og  SSL(Secure Sockets Layer – (https) Kryptering for ende-til-ende applikasjoner – for eksempel nettbank eller butikker hvor data som sendes fra brukermaskin til en tjenermaskin server eller nettsted er kryptert. Sikker kommunikasjon for nettsøk og e-post. Tjeneren blir autentisert mens brukeren uautententisert. Uutveksling av nøkler og gjensidig autentisering og valg av krypteringsmetode, hvilket chiffer som ksal brukes. Utveksling av nøkler RSA, Diffie-Hellman, DSA, SRP, PSK. Symmetrisk chifferutveksling o chifferkryptering RC4, Trippel DES, AES.

Husk alltid å kontrollere at lenken du bruker er av typen https://... og klikk aldri på en lenke du ikke vet hva inneholder. Det er alltid noen som vil forsøke å lure deg. 

applikasjonsprotokollene som HTTP, FTP, SMTP, NNTP og XMPP og over en pålitelig transportprotokoll som for eksempel TCP.

Mobiltelefoni med fjerde og femte genereasjons kommunikasjon (4G og 5G) med tilhørende kryptografi

Et lokalt tårdløst nettverk WiFi (IEEE 802.11,  Institute of Electrical and Electronics Engineers) med ed frekvensbånd 2.4 gigaherz (GHz), 5 GHz, 6 GHz og  60 GHz.  WPA – (WiFi Protected Access) lager kryptering på trådløse nettverk, krypterer forbindelsen og informasjonsflyten mellom  mellom deg /brukermaskin og aksesspunkt/rutere.

Massiv datakraft, blant annet utvikling av kvantedatamaskiner, gjør det mulig ved tallknusing å knekke koder. 

Litteratur

Wikipedia

Tilbake til hovedside

Publisert 25. nov. 2019 11:39 - Sist endret 30. okt. 2023 11:16