Föreläsning 10 - Kryptering, simulering

Kryptering
- Lösenord (symmetrisk kryptering)
- Private key - public key (asymmetrisk kryptering)
- PGP och Kerberos
Simulering i simulerad tid
Simulering i realtid

Kryptering

Teoretisk datalogi lever ibland sitt eget liv i avskildhet från databranschen, men ett lysande undantag är kryptering. Det är något som utvecklats av teoretikerna men som är helt avgörande för branschens kommersiella sida. På Nada är vi stolta över att ha några världskändisar på kryptering: professorn Johan Håstad och ett gäng doktorander (numera doktorer) som knäckte chiffren i Simon Singhs Kodboken (dom heter Staffan Ulfberg, Gunnar Andersson och Lars Ivansson).

Lösenordskryptering

Sedan urminnes tider har man känt till metoder att med en hemlig nyckel kryptera ett meddelande så att det bara kan avkrypteras med samma nyckel. Om meddelandet M och nyckeln K skrivs binärt är krypteringen enkel - i varje position summeras bitarna modulo två, dvs 1+1=0, och det ger den krypterade bitföljden C. Nyckeln upprepas så att den räcker meddelandet ut. Avkryptering går till på exakt samma sätt.

	M = 1 1 0 1 1 0 0 0 0 1 0 1...
       +K = 1 0 1 1 0 1 1 1 0 1 1 0...
        ------------------------------
	C = 0 1 1 0 1 1 1 1 0 0 1 1...
       +K = 1 0 1 1 0 1 1 1 0 1 1 0...
        ------------------------------
	M = 1 1 0 1 1 0 0 0 0 1 0 1...

Krypteringen går blixtsnabbt men om man gör det så här okomplicerat finns det metoder att knäcka kryptot med hjälp av statistik på bokstavsfrekvenser och andra ännu listigare angreppssätt. Om man kombinerar metoden med upprepade blandningsoperationer blir den tillräckligt svårknäckt och en sådan standardmetod är DES, som är amerikanska försvarsmaktens standard.
Den enda nackdelen är att lösenordet måste distribueras till alla som ska vara invigda och det kan inte göras över en avlyssnad kanal utan måste ske med kurir. Det trodde man i alla fall innan Diffie och Hellman 1973 kom på hur det kunde gå till.

Vi tänker oss att Alice vill skicka ett meddelande til Bob. Hon krypterar det med sin hemliga nyckel (som inte Bob känner till) och skickar det med e-post till Bob. På vägen tjuvläser Eve det men hon fattar förstås ingenting. Det gör inte Bob heller, men han krypterar det en gång till med sin hemliga nyckel och skickar tillbaka det till Alice. Alice avkrypterar med sin hemliga nyckel och skickar tillbaka till Bob. När nu Bob avkrypterar med sin nyckel blir meddelandet läsbart för honom utan att Eve kunnat snoka fram det. Detta förutsätter förstås att krypteringsmetoden är sådan att det inte spelar någon roll i vilken ordning A och B krypterar.

Public key - secret key

Diffie kom ett par år senare på en ännu effektivare metod, som gör att meddelandena inte behöver gå tre gånger fram och tillbaka. Den kräver att alla människor har två nycklar, en hemlig och en offentlig. Krypteringsmetoden är sådan att det som krypteras med den ena nyckeln bara kan avkrypteras med den andra.

           ___               ___
    A---->| p |------------>| s |---->B
       M  |__B|      C      |__B|  M

Alice slår upp Bob i public-key-katalogen och krypterar sitt meddelande med p_B. Den enda i världen som kan avkryptera det är Bob, för han känner till s_B. Nu kan inte Eve tjuvlyssna men hon kan sabotera på ett annat sätt. Eve kan skicka ett med p_B krypterat meddelande till Bob som ser ut så här.
Bry dej inte om vad jag skrev nyss. Alice
För att gardera sej mot detta krypterar Alice först med sin hemliga nyckel. Det krypterade meddelandet förser hon med överskriften "Hemligt meddelande från Alice" och krypterar en gång till med Bobs offentliga nyckel.

           ___     ___               ___     ___
    A---->| s |---| p |------------>| s |---| p |---->B
       M  |__A|   |__B|      C      |__B|   |__A|  M

När Bob avkrypterar med sin hemliga nyckel ser han att det är från Alice, slår upp henne i public-key-katalogen, avkrypterar och är nu säker på att det verkligen kommer från Alice.

PGP och Kerberos

Eftersom asymmetrisk kryptering är tusen gånger långsammare än lösenordskryptering är det effektivaste att använda den långsamma krypteringen för att utbyta lösenordet, ett lösenord som bara gäller under någon timme. Ett utvecklat system för detta är PGP (pretty good privacy) med upphovsmannen Phil Zimmermann, en hjälte i datavärlden. Härmed uppmanas alla att läsa denna trevliga beskrivning av PGP och att skaffa sej PGP-nycklar.

Simulering i simulerad tid

Simuleringsprogram är lika roligt att skriva som att köra! Vi tar ett löjligt exempel som ändå innehåller allt väsentligt.
På institutionens plan fyra arbetar ett tjugotal personer och där ska finnas tvä toaletter. Hur ska man bedöma om kapaciteten är tillräcklig och hur avgör man om det är bäst att ha båda toaletterna i mitten eller en i var ände av korridoren? Enda sättet är simulering. En simulerad dag kan se ut så här.

08.54:26 N behöver
08.54:51 Toakö: N
08.54:51 N går in
08.54:51 Toakö:
08.55:07 C behöver
08.55:32 Toakö: C
08.57:50 H behöver
08.58:15 Toakö: C H
08.59:06 N går ut
08.59:06 C går in
08.59:06 Toakö: H
 - - -

Varje utskriftsrad beskriver en händelse och händelser kan i exemplet vara av fem typer:

behöver
köar
går in
går ut
hinner inte

Planerade händelser ligger i en prioritetskö eventq med sin tidpunkt som prioritet. Den händelse som tas ut ur eventq är den som har lägst tid. När händelsen verkställs kan den ge upphov till nya planerade händelser, exempelvis ger en behöver-händelse upphov till en köar-händelse cirka en halv minut senare. I eventq läggs trippler av typen (tid,händelsetyp,objekt), där objektet i vårt exempel är personen. Så här blir programmets huvudslinga ("eventloopen"). Systemtiden t är en global variabel som ändras av getevent

while True:
    (event,obj)=getevent()
    if event=="behöver":
        person=obj
        print klockslag(t),person.namn,event
        person.state="nödig"
        setevent(t+person.maxhold,"hinner inte",person)
        setevent(t+person.walktime,"köar",person)
    elif event=="köar":
        person=obj
        toaq.put(person)
        write(toaq)
        if toa.state=="ledigt":
            setevent(t,"går in",toa)
    elif event=="går in":
        toa=obj
        if toaq.isempty(): continue
        person=toaq.get()
        print klockslag(t),person.namn,event
        write(toaq)
        toa.state="upptaget"
        toa.person=person
        person.state="onödig"
        setevent(t+person.besokstid(),"går ut",person)
    elif event=="går ut":
        person=obj
        print klockslag(t),person.namn,event
        toa.state="ledigt"
        toa.person=None
        setevent(t+person.mellantid(),"behöver",person)
        setevent(t,"går in",toa)
    elif event=="hinner inte":
        person=obj
        if person.state=="onödig": continue
        print klockslag(t),event,person.namn
        break
    elif event=="slut":
        print klockslag(t),event
        break

Här finns ett toaobjekt, en toakö och ett antal personobjekt. Varje person kan ha egna normalfördelningsparametervärden för toabesökstid och tid mellan besök. För att få slut på simuleringsdagen har vi lagt in en sluthändelse klockan 19.00. Katastrofhändelsen hinner inte ger genast avbrott eftersom den bara inte får hända. Hela programkoden finns här.

Sidansvarig: <henrik@nada.kth.se>
Senast ändrad 31 januari 2011
Tekniskt stöd: <webmaster@nada.kth.se>