Om krypto

Om krypton
Olika metoder
Andra metoder
Utökningar och varianter på denna metod
Diffie-Hellman
Rivest, Shamir och Adler
Fingerprinting
Sign here, please...

 


26/08-02 | Icepic | icepic@64bits.se
Utskriftsvänligare versionUtskriftsvänligare version


Rivest, Shamir och Adler

Tre andra herrar, med efternamns-initialer som bildar R, S & A kom på hur själva matematiken skulle utformas för att kunna dra nytta av Diffie-Hellmans nyckelutbyte. Diffie-Hellmans teorier slutade vid att man hade nycklar delade i två, och att man sände de publika delarna till varandra. Att nyckeldelarna hade ett samband som ändå inte avslöjade varandras egenskaper och att det skulle vara lätt att verifiera men svårt att knäcka. Det skulle alltså vara en algoritm där det går fort att komma fram till svaret om man vet "frågan", men mycket svårt att gå andra vägen.

Rivest och Shamir kom på hur man skulle använda Diffie-Hellmans metod för att sedan kunna kryptera filer och strömmar av data, hur man skulle bygga upp sina nycklar, hur man kunde signera varandras nycklar och skapa digitala signaturer på dokument Adler hjälpte till att kontrollera och verifiera att deras teorier höll ihop och ville först inte komma med i "RSA", men blev övertalad att hans deltagande var värt att få sin bokstav med där.

Det tål ju att nämnas att dessa nycklar egentligen "bara" är en bunt mångsiffriga primtal. Man får alltså fram dessa nycklar genom att multiplicera ett gäng enorma tal ett par gånger. Jag tänker inte gå inte på den exakta matematiken av flera skäl. Ett är givetvis att jag inte kan det till 100% rätt ur huvudet, men också för att det finns långt bättre källor som kan förklara detaljerna runt operationerna om någon är intresserad av själva matematiken.

En bra källa för den intresserade är den här artikeln på
LinuxJournal.

Poängen är iallafall att det tar en bråkdel av en sekund för min
dator att räkna ut att:
155177129484270555606651621342977585583569373069878490856036577
591028437471509237207019133164702658161482497210425897077728509
586880427013755844106585790173828572631607273389394972814692148
284749632724380567159231160878317653030185704143004400758282030
026326904112312096804714696187557204585239177411214582219
gånger
155177129484270555606651621342977585583569373069878490856036577
591028437471509237207019133164702658161482497210425897077728509
586880427013755844106585790173828572631607273389394972814692148
284749632724380567159231160878317653030185704143004400758282030
026326904112312096804714696187557204585239177411224832943
blir:
240799415149780701910680748339718321712735608949210571744000444
482792945821771244451979580458926399117821172943693395720059960
258363189136138455587451374957003872827242459255743835826495915
101826060051800197744825562340179230170054697133490714081317976
834701423908465379067536666227216539848968297138099828958600011
712535803244947255555528157314566530517370462077661707640654843
116266926954047286501723592603571972548476504961408093339257027
965028535981634868947231226312835297307256943445925869314947697
927899849726458453373514822389338162238815251565129775175448034
65207131418028168696141022678871849550733813240517

..men jag kan lova att det tar aningens mer tid att räkna ut vilka två primtal som svaret består av om man bara fick svaret och ska prova sig fram bland alla primtal från 3 -> svaret.

Det är enbart de två första talen som överhuvudtaget kan ge det svaret och inga andra, så för att ta reda på vilka de talen är krävs en hel genomgång av så gott som hela talserien upp till och med svaret och sen multiplikation av samtliga tal med varandra tills man får fram de enda två faktorer som ger rätt produkt.

Antalet primtal som är lägre än talet X är ungefär lika med X/(ln(X) -1). Har man en produkt som är högst 1000000 så finns det cirka 78000 primtal att testa mot varandra. Är produkten man ska leta primtalspar till i storleksordningen 100 miljoner (11 siffror) istället finns det cirka 5.7 miljoner primtal att matcha mot varann. Som ni ser stiger antalet möjliga kombinationer fort. Har man (som ovan) ett 700-siffrigt tal blir antalet primtal enormt. Antalet kombinationer som man måste testa igenom blir mer än enormt.

På det viset är metoden matematiskt säker. Även om det finns tusentals personer på jorden som kan RSA utan och innan så finns det ingen som kan multiplicera 5.7 miljoner primtal med varandra på alla tänkbara vis för att komma fram till de två enda primtalen som blir den nyckel man söker. Och det är i fallet med 11-siffriga primtal. Använder man 4096-bitars RSA så är det i runda slängar 12-1300-siffriga tal det rör sig om. Det är det som är charmen med bra krypton. Även om man vet exakt hur allt går till så hjälper det inte en eventuell avlyssnare.

När man nu hade en metod för nyckelutbyte som var säker och ett assymetriskt krypto som använde sig av den så var "allt" klart rent akademiskt. Efter att ha råkat ut för en bunt konstiga politiska problem med amerikansk säkerhetstjänst var det till slut en person som läckte ut källkoden till RSA-krypteringen på newsgruppen sci.crypt och sen var det kört. Alla i hela världen kunde själva skapa ett program som använde den nya metoden.

Först ut blev Phil Zimmerman som skapade programmet PGP - Pretty Good Privacy. Namnet var ju lite av ett skämt, eftersom "pretty good" betyder "hyffsat bra" men man visste redan då att RSA-metoden skulle stå emot otroligt mycket bättre än tidigare kända metoder. Hyffsat var årets underdrift.

Man kan lugnt påstå att säkerhetstjänsten gick i taket när det framgick att metoden var publicerad på nätet så alla kunde se. Nu fanns det dessutom ett färdigt program för det. Som de brukar säga i amerika, när man släppt ut anden ur flaskan går det inte att stoppa tillbaka den igen.

RSA är dock inte helt utan nackdelar. Den tar otroligt mycket längre tid att köra än vanligt symmetriskt krypto, och man får ta till mycket större tal för att få motsvarande skydd som de andra kryptometoderna. När vanliga krypton har 56,64 eller 128 bitars nyckel så har RSA 1024, 2048 eller 4096 bitar.

Tyvärr är de inte jämförbara rakt av, men man kan anse att 128-bitars symmetriskt krypto är säkert hundra år framöver, och 2048-bitars RSA troligen är det också om inget oväntat händer.

RSA-krypto drar enormt mycket cpu jämfört med symmetriska krypton, pga att man hanterar så enormt stora tal hela tiden, så för att spara tid i det verkliga livet har PGP tagit till en listig metod.

Det största problemet hos symmetriska krypton var ju att hantera och distribuera nycklarna, medans själva kryptots säkerhet i stort sett är lika säker som assymetriska krypton. Så PGP gör helt enkelt så att den slumpar fram en engångsnyckel, krypterar meddelandet med ett starkt symmetriskt krypto, och sen så krypterar man helt enkelt enbart nyckeln med RSA. Det här får en hel del intressanta konsekvenser. Ett av dem är att om man krypterar samma fil flera gånger blir resultatet alltid olika eftersom engångsnyckeln är slumpad. En annan konsekvens är att enkelt kunna ha flera mottagare till samma fil.

Antag att Alice vill skicka ett hemligt meddelande till Bob och Cloe. Om hon använder ett symmetriskt krypto har hon två val, antingen skapar hon två krypterade filer, två nycklar och sen sänder hon filerna till respektive person och på nåt sätt för över nycklarna till rätt mottagare, eller så måste hon ge samma nyckel till både Bob och Cloe, och det är kanske nåt man inte alls vill, speciellt inte om man har en nyckel som är tänkt att räcka länge.

Det PGP gör i det fallet är givetvis att hitta på en engångs-nyckel, kryptera innehållet och sen kryptera engångsnyckeln i två versioner. En gång så att enbart Bob kan dekryptera den, och en gång så att Cloe kan dekryptera den. Ett 100Mb stort meddelande förblir 100Mb pga det symmetriska kryptot, och sen kommer ett par hundra bytes x2 för de två skyddade versionerna av nyckeln. Man kan alltså ha en dummy-user vars nyckel ligger i ett kassaskåp som man adderar som mottagare varje gång man krypterar ett mail eller meddelande, och i händelse av att "han-som-kunde-koden" ramlar i sjön och drunknar kan man fortfarande låsa upp filerna i efterhand med dummy-nyckeln.

PGP har dessutom ett antal extra funktioner vad det gäller nycklarna. Det är ju en sak att Alice sänder sin nyckel till Bob och att Eliza kanske hör dem sända sina publika nycklar till varandra, men hur gör man om Alice pratar med nån som utger sig för att vara Bob? Eliza skulle kunna säga att hon är Bob, ta emot Alice publika nyckel och sända sin tillbaka. Sedan tar Eliza kontakt med Bob och påstår sig vara Alice. Eliza sänder sin falska Alice-liknande nyckel till Bob och Bob sänder tillbaka sin publika nyckel. Nu har man skapat en situation där Alice och Bob skulle kunna skicka krypterade meddelanden till varandra i tron att det var säkert, men i verkligheten sitter Eliza mellan och dekrypterar och åter-krypterar hela tiden. (s.k. Man-in-the-middle-attack)

Fingerprinting

Man har löst det genom att varje nyckel kan skapa en "fingerprint",
ett digitalt fingeravtryck. Eftersom det är ohållbart att Alice och Bob sitter och läser upp 100-siffriga primtal till varandra gör man en checksumma på sin publika nyckel som är kort och fin och som är långt lättare att verifiera över telefon. Risken, eller sannolikheten för att två slumpade RSA-nycklar ska få samma checksumma är otroligt liten, speciellt som den tar hänsyn till de userdata man knyter till sin nyckel. (oftast emailaddress och namn)

Ett exempel, taget från nätet på måfå: PGP fingerprint: E2C9 1159 6ACF 9909 F4D2 F4EF 941B FBDE 4090 AE6C

Så Alice och Bob sänder sina nycklar antingen över nätet, via floppydiskar eller brevduva, men tar kontakt efteråt och verifierar att deras fingerprints matchar den publika nyckel de tagit emot. Skulle Eliza sitta mitt i mellan, kommer inte fingerprinten att matcha, och Alice och Bob vet att de måste sända nycklarna via en annan kanal. Men det är inte slut där. PGP låter dessutom mottagaren signera en annan persons nyckel. Man skapar det som kallas för en nyckelring. Om Bob tar emot Alice nyckel, pratar med Alice över telefon och verifierar hennes fingerprint så kan Bob sätta en signatur på sin publika nyckel som säger att "Jag, Bob, litar på Alice som har nyckeln med id 0xdeadf00d".

Det hamnar som sagt på Bobs publika nyckel, eftersom det är han som står för påståendet. Han bör sända iväg sin nya publika nyckel till en nyckelserver på nätet eftersom den har ändrat sig lite. Den är givetvis inte ändrad så att det förändrar hur man pratar med Bob själv, men för andra mottagare av hans nyckel kan det ha större betydelse.

Om Cloe träffar Bob och byter publika nycklar med honom på ett säkert sätt kan hon "ärva" referensen till Alice. Cloe vet vem Bob är, och Bob vet vem Alice är, så om Cloe tar emot Alice publika nyckel från en anonym källa så kan Cloe bygga en rak kedja från sin nyckel till Alice nyckel. Detta kan växa sig enormt stort om man signerar varandras nycklar regelbundet och ökar definitivt säkerheten och användbarheten hos PGP. Det brukar kallas Web of Trust, men har givetvis inbyggda begränsningar, så att en person 40 steg bort inte ska kunna introducera andra, men ett par tre, fyra steg brukar man låta vara lagom för att det inte ska bli för klent förtroende.

Sign here, please...

Men PGP nöjer sig inte med att bara kryptera, den kan även signera meddelanden och filer. Genom att göra en checksumma av innehållet och sedan kryptera checksumman på ett speciellt sätt kan man göra checksumman möjlig att kontrollera för alla som har ens publika nyckel.

På det viset kan alla verifiera att innehållet i meddelandet inte har ändrats av någon annan efteråt, eftersom det skulle förändra checksumman. Den potentiella busen kan dessutom inte bara räkna ut en ny checksumma efter att ha ändrat, eftersom denne inte kan kryptera den nya checksumman så att det ser ut som originalverifieraren gjort det. Med enbart en publik nyckel kan man inte skapa en signatur, utan det kräver att man använder både sin hemliga och sin publika del av nyckeln.

Det har ju två sidor dock, för man kan få svårt att neka till att man skrivit någonting om ens signatur är satt på meddelandet. PGP skyddar ju alltid filen som håller ens hemliga RSAnyckel med ett symmetriskt krypto, där nyckeln kommer från ett lösenord som man måste mata in varje gång man måste komma åt den, så det duger inte heller att påstå att städaren måste ha varit på min terminal när jag var borta.

Assymetriska system är däremot en bra metod om man ska ha röstning och val online eller liknande system där själva meddelandet inte nödvändigtvis måste vara hemligt, men där man vill hindra dubletter eller att folk senare påstår att de inte fick delta.

Att dela ut 9 miljoner separata engångskryptonycklar till varje svensk för att kunna använda symmetriska krypton är ju inte att tänka på. Att ha en enda nyckel till alla gör givetvis kryptot helt värdelöst. Däremot kan ett system med varsin publik nyckel fungera, där myndigheten/erna har en myndighetsnyckel som alla sedan kan sätta som mottagare då de sänder in sin röst eller liknande.

Det finns en massa bra anledningar till varför man vill ha krypto, inte minst för att skydda sig mot oönskat informationsläckage, men likaväl för att kunna verifiera överförda signaturer och förhindra at folk påstår sig inte ha sänt viss information. Utvecklingen går enormt fort framåt, men krypto kommer alltid gå att göra säkert så länge det finns matematiska metoder och formler som är lätta åt ena hållet och jobbiga åt andra. Frågan är bara hur många hundratusen bitar nycklarna är på år 2100, och hur många GHz våra armbandsur har för att kunna räkna på dem i realtid. Den som lever får se.


« Föregående  

 

26/08-02 | Icepic | icepic@64bits.se
Utskriftsvänligare versionUtskriftsvänligare version

Diskutera denna artikeln i vårt forum!