Algoritmer og datastrukturer

Obligatorisk oppgave 1: Kryptering med stack og kø

I denne obligatoriske oppgaven skal du lage et lite program for å kryptere og dekryptere tekststrenger. Det skal brukes både en stack og en kø for å lage krypteringen. For å kunne løse oppgaven må du ha gått gjennom lærestoffet for stack og kø, slik at du er fortrolig med hvordan man bruker disse datastrukturene.

1 Kryptering

Kryptering brukes for å transformere data slik at de (forhåpentligvis) blir uleselige for andre enn de som vet hvilken krypteringsmetode som er brukt.

Det er viktig og helt nødvendig å kryptere dataene våre for å beskytte spesielt personlig og sensitiv informasjon når vi kommuniserer på nettet. Mange internett-tjenester bruker derfor relativt avanserte krypteringsmetoder basert på intrikate matematiske formler og algoritmer, f.eks. Hypertext Transfer Protocol Secure — HTTPS — som kombinerer kryptering av websider med digitale sertifikater. Disse metodene forbedres stadig for å gjøre det sikrere og enda mer vanskelig for kriminelle hackere som er ute etter å "knekke koden" for å misbruke informasjon.

2 En enkel krypteringsmetode: ROT13

Kryptering ble opprinnelig brukt militært for å hindre at fienden skulle kunne lese/avlytte kommunikasjon som inneholdt strategisk viktig informasjon. Et av de meste berømte systemene var kodemaskinen Enigma, som tyske militærstyrker brukte til både kryptering og dekryptering av informasjon under andre verdenskrig. Knekkingen av Enigmakoden, der informatikk-pioneren Alan Turing spilte en sentral rolle, antas å ha forkortet tiden det tok før de allierte vant krigen med flere år.

Et primitivt eksempel på militær kryptering er såkalt "Cæsar cipher", som ble brukt av romerne til å kode meldinger som ble sendt med kurér. Krypteringen bestod i å bytte ut hver bokstav i en melding med bokstaven som står et bestemt antall posisjoner lenger frem i alfabetet (med "wrap-around" tilbake til 'A' når vi teller oss frem til siste bokstav i alfabetet).

Hvis vi bytter ut hver bokstav med den som står 13 posisjoner lenger frem i alfabetet, får vi en krypteringsalgoritme som kalles ROT13 ("rotate by 13 places"). Med engelsk alfabet som har 26 bokstaver, får vi denne "oppslagstabellen" for å kode og dekode tekst:

Input:

a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

s

t

u

v

w

x

y

z

Output:

n

o

p

q

r

s

t

u

v

w

x

y

z

a

b

c

d

e

f

g

h

i

j

k

l

m

Her er et eksempel der ROT13 brukes til å kryptere svaret på en "gåte":

    Why did the chicken cross the road?
    Gb trg gb gur bgure fvqr!

Hvis vi transformerer begge disse linjene med ROT13, ser vi svaret:

    Jul qvq gur puvpxra pebff gur ebnq?
    To get to the other side!

Merk at ROT13 blir symmetrisk fordi 2·13=26. Vi trenger derfor ikke en egen dekrypteringsalgoritme, to påfølgende ROT13-transformasjoner vil først kryptere og deretter dekryptere teksten.

Nedenfor gis det en beskrivelse av en krypteringsalgoritme som først bruker ROT13 og deretter bytter om på rekkefølgen av tegnene.

3 En krypteringsalgoritme med stack og kø

Vi skal se på en enkel (og sikkerhetsmessig helt ubrukelig) metode for å kryptere tekststrenger, som bruker både en stack og en kø. Algoritmen for å kryptere en streng S med n tegn kan beskrives slik:

1. Kjør algoritmen ROT13 på (bare de engelske bokstavene) i strengen S.

2. Legg deretter de n/2 første tegnene i S i en kø (enqueue), i samme rekkefølge som de forekommer i strengen.

3. Legg så de resterende tegnene i S på en stack (push), i samme rekkefølge som de forekommer i strengen.

4. Start med en tom streng T og lag den nye krypterte strengen slik:

   • Ta ut ett tegn av stacken (pop) og legg dette inn som første tegn i T.
     Ta ut ett tegn fra køen (dequeue) og legg dette inn som andre tegn i T.

   • Fortsett på samme måte, med å ta ut ett tegn fra stacken og ett tegn fra køen og legge dem til på slutten T, inntil både stacken og køen er tom.

Her er et eksempel på hvordan denne algoritmen virker for tekststrengen S="Karmann-Ghia" som har n=12 tegn:

1. ROT13("Karmann-Ghia") = "Xneznaa-Tuvn"

2. Kø:
   

   X

   n

   e

   z

   n

   a

3. Stack (fra toppen):
   

   n

   v

   u

   T

   -

   a

4. T = "nXvnueTz-naa"
   

Vi ser av eksempelet ovenfor at den krypterte strengen lages ved å hente annethvert tegn fra henholdsvis stacken (røde tegn) og køen (grønne tegn). Etter at alle stegene i algoritmen er ferdig, ser vi at den krypterte utgaven av strengen "Karmann-Ghia" er lik "nXvnueTz-naa".

Du skal programmere denne metoden i oppgaven nedenfor, og også lage en metode som dekrypterer strengene tilbake til originalteksten.

4 Programmeringsoppgave

1. Lag en Java-metode:

   public static String krypter(String S);

   Metoden krypter() skal implementere krypteringsmetoden beskrevet ovenfor, og returnere den krypterte versjonen av strengen S.

2. Lag en Java-metode:

   public static String dekrypter(String S);

   S er her er en streng som er kryptert med metoden krypter() i oppgave a ovenfor. Metoden dekrypter() skal reversere krypteringen og returnere den ukrypterte versjonen av strengen S.

3. Lag et lite testprogram som kan brukes for å sjekke at løsningen din fungerer som den skal. Programmet skal lese en streng fra bruker og kryptere/dekryptere strengen.

Begge metodene skal bruke Javas innebygde stack (java.util.Stack) og kø (Java.util.Queue). Du skal også bruke metoden nedenfor, som gjør "engelsk" ROT13 på en tekststreng:

public static String ROT13(String S) 
{
   char[] C = S.toCharArray();
   for (int i = 0; i < S.length(); i++)
   {
      char c = C[i];
      if       (c >= 'a' && c <= 'm') c += 13;
      else if  (c >= 'A' && c <= 'M') c += 13;
      else if  (c >= 'n' && c <= 'z') c -= 13;
      else if  (c >= 'N' && c <= 'Z') c -= 13;
      C[i] = c;
   }
   return String.valueOf(C);
}

5 Hva skal du levere?

Løsningen din legges på en fil med navn Oblig_01.java. Den skal være kompilerbar og fungere korrekt. Java-filen postes her i Canvas som svar på oppgaven.