Cryptopals del 11 (RSA!) av ?
(Del 1 Del ”2” Del 3 (men egentligen 2) Del x (där 2.5 ≤ x ≤ 4) Del 5+0 Del 6(?) Del Counter=7, Del 8, Del (9,deadbeefcafe)), Del 7^5 mod 11
Välkommen till det nu årliga blogg-inlägget om Cryptopals. Här går vi i ”tur” och ”ordning” igenom uppgifterna som finns tillgängliga på sidan cryptopals.com och diskuterar saker som vi i stunden tycker känns intressanta. Notera att lösningar på själva uppgifterna oftast lämnas till läsaren – här tar vi istället upp ”relevant” kuriosa.
I det senaste inlägget i denna bloggserie diskuterade vi hur Diffie och Hellman kunde skapa en hemlig krypteringsnyckel som båda kände till trots att de behövde skicka alla meddelanden mellan sig genom en opålitlig brevbärare.
I dag kommer vi se ett liknande problem där en person vill skicka ett hemligt meddelande till en annan, på ett sätt så att enbart mottagaren har möjlighet att dekryptera meddelandet. Många har nog hört om begreppet som löser detta: RSA (wow, äntligen har vår serie kommit hit). Författaren till denna blogg har förstått att det i vårt samhälle finns vissa som tycker att matematik är läskigt och svårt (det visar sig nämligen vara en ytterst vanlig replik till när någon berättat att man doktorerat i matematik), och för dessa potentiella läsare är kanske en djupdykning ner i RSA inte vad man hoppas på. Vi kommer dock försöka hålla den första delen av denna blogg helt matematik-fri och så lättläst som möjligt, så ifall ni känner vissa matte-aversioner kan ni vara helt lugna!
Låt oss börja med att ta två primtal \(p\) och \(q\), och beräkna den minsta gemensamma multipeln av \(p-1\) och \(q-1\). Sedan… Nej, okej det där var bara för att skrämmas (passande i dessa Halloween-tider).
RSA utan matematik
Tänk oss istället att vi har en kista innehållandes en värdefull skatt. Vi kommer använda detta begrepp ofta, så låt oss ge det ett namn. Låt oss kalla detta en ”skattkista”. I vårt informationssamhälle finns det väl ingenting mer värdefullt än information/data, men vi kan låtsas som att vi lever i Karibien under 1700-talet och då innehåller lådan lite mer spännande grejer.
Ifall vi skulle vilja skicka denna ”skattkista” till någon annan via en opålitlig brevbärare så är det inte så troligt att skatten kommer komma fram. I fallet med juveler och mynt kanske något skulle saknas och i fallet med data så kanske brevbäraren har läst informationen eller till och med ändrat datat på något sätt.
Hur löser man detta? En idé som de tre kryptologerna Ron Rivest, Adi Shamir och Leonard Adleman kom på var att använda ett koncept involverandes en ”publik nyckel” och en ”privat nyckel”.
Tänk på ett hänglås. I teorin så kan vem som helst låsa hänglåset (man trycker ned bygeln) men bara den som har nyckeln till hänglåset kan låsa upp den igen. Detta kanske inte stämmer i praktiken eftersom hänglås kan dyrkas upp eller helt enkelt förstöras, men vi tänker oss ett teoretiskt perfekt hänglås.
Vissa kanske hävdar att kalla ett hänglås för en publik nyckel låter fel (och det är också därför som vi använder citationstecken i bilden), men detta är notationen som används inom RSA.
Den tilltänkta mottagaren av vår skattkista skulle i förväg kunna skicka iväg ett hänglås till oss men behålla nyckeln för sig själv. Vi skulle då kunna låsa vår skattkista med denna publika ”nyckel” och gladeligen skicka iväg den till mottagaren.
Så länge som hänglåset håller (den underliggande algoritmen inte knäcks) så är skatten i säkert förvar och vi kan vara säkra på att det enbart är den som har den privata nyckeln som kan låsa upp kistan.
För att underlätta framtida skattkist-leveranser så kan mottagaren kopiera upp massa kopior av sitt hänglås (med samma privata nyckel) och skicka ut dessa hänglås över hela världen. Sedan kan vem som helst plocka upp ett sådant hänglås, låsa en godtycklig skattkista och skicka det till mottagaren. Superenkelt och bra! Ett par saker att tänka på:
- Fysiska hänglås funkar inte så bra att skicka över internet, och de funkar inte så bra med att kryptera 1or och 0or, så vi måste hitta någon motsvarande lösning för detta. (Det är här som matematiken kommer in, men vi avvaktar med detta en stund till.)
- Hur kan man vara säker på att hänglåset som vi fått faktiskt har skickats av den tilltänkta skattkiste-mottagaren? Tänk om den opålitlige brevbäraren är smart och byter ut alla hänglås mot sina egna. Om vi då låser skattkistan med ett sådant hänglås så kan ju brevbäraren öppna lådan i alla fall. Detta är ett av grundproblemen i all form av kryptering – någonstans behövs någon form av tilltro. Sättet som detta löses på internet är med så kallade certifikat. Vi kan visualisera ett certifikat med vår uppsättning som i följande bild:
Eftersom en signatur är personlig och omöjlig att förfalska så vet folk som ser detta att Gustav verkligen har intygat att hänglåset är Görans, och om man litar på Gustav så kan man lita på hänglåset. Återigen, i verkligheten är det kanske möjligt att förfalska en namnteckning, men i vår teoretiska värld så är det dundersäkert. Men, eftersom hänglås som sagt inte funkar att skicka över internet så använder internet-certifikat andra typer av signaturer/namnteckningar, och dessa är också baserade på matematik (och svårare att förfalska än en namnteckning).
Sidetrack!
Det vi läste om ovan var den konceptuella idén bakom RSA. Innan vi går in på matematiken som används för att faktiskt implementera RSA så tänkte vi visa en annan konceptuell idé som Rivest, Shamir och Adleman hade. Följande information är kanske sann. Vi använder ordet kanske eftersom det enbart bygger på vad bloggförfattaren har ett minne av att han läste i Simon Singhs bok The Code Book. Notera att det var cirka 6 år sedan som bloggförfattaren läste boken, och han har inte öppnat den sedan dess, så detta kan vara rena fantasier. Oavsett är det intressant!
RSA bygger på att en mottagare skickar ut kopior av sitt hänglås över hela världen (vilket innebär att det krävs en hel del infrastruktur för att ta emot och lagra alla olika människors hänglås på alla möjliga platser). Istället skulle man kunna tänka sig ett annat tillvägagångssätt.
Tänk att vi återigen vill skicka vår ”skattkista” till en mottagare. Om vi inte har mottagarens hänglås, så kan vi istället ta vårt egna hänglås, som bara vi har en nyckel till, och låsa kistan:
Vi kan sedan skicka kistan till mottagaren. När mottagaren får paketet så kan den ju inte öppna kistan, men den kan låsa kistan en extra gång med sitt egna hänglås! Sedan skickar mottagaren tillbaka kistan till oss.
När vi får tillbaka kistan så kan vi låsa upp vårt hänglås eftersom vi har nyckeln, och sedan skicka kistan tillbaka till mottagaren.
När mottagaren nu får kistan för andra gången så kan kistan slutligen låsas upp och skatten tas emot! Detta koncept innebär ganska mycket extra arbete för brevbäraren eftersom kistan nu måste transporteras fram och tillbaka flera gånger, men den är skyddad i varje steg, och vi behövde aldrig bry oss om mottagarens låsmekanism.
Tyvärr återstår samma problem med ett behov av tilltro även i detta koncept. Hur vet vi att när vi får tillbaka kistan med två hänglås att det nya hänglåset verkligen var den tilltänkta mottagarens hänglås? Jag vet faktiskt inte hur man skulle lösa detta. Oavsett så lyckades tydligen (enligt mitt minne av vad jag läste i en bok för länge sedan) aldrig Rivest, Shamir och Adleman komma på hur detta koncept faktiskt skulle implementeras på en dator, eftersom man behöver att de två hänglåsen/algoritmerna går att låsa/låsa upp oberoende av varandra (algoritmerna behöver kommutera). Självklart skulle man kunna hitta algoritmer som kommuterar (exempelvis Caesar-chiffer) men dessa visar sig alltid ha andra sårbarheter och bloggförfattaren känner inte till någon vettig och säker implementation. Oavsett så är det en intressant tanke och något som en intresserad läsare skulle kunna försöka ge sig på att lösa. Slut på sidetrack!
RSA med matematik
Vi börjar detta avsnitt med att säga adjö till de som ej är intresserade av matematik. Tack för att ni läste ända hit!
Det finns många texter om hur matematiken bakom RSA fungerar, och vi vet inte vilka nya insikter vi kan bidra med. Den intresserade kan istället läsa detaljerna på wikipedia. Vi kan dock göra ett kort räkneexempel bara för att vi ska ha begreppet i huvudet. Låt oss ta två stora primtal, exempelvis \(p=17\) och \(q=11\), och beräkna produkten \(n=pq=187\).
Efter att ha skippat detaljer så kan man få fram att det för \(e=3\) och \(d=27\) gäller, för alla heltal \(x\), att $$(x^e)^d =x \ (\text{mod }n).$$ Exempelvis gäller att $$(54^3)^{27} = 54\ (\text{mod }187).$$ Hur man kommer fram till dessa tal \(e\) och \(d\) är genom att först välja ett \(e\) och sedan beräkna inversen av \(e\) modulo \(\lambda(n)\) där \(\lambda(n)=\lambda(pq)\) är den minsta gemensamma nämnaren av \(p-1\) och \(q-1\). Läsaren behöver inte bry sig om dessa detaljer, men det man kan ta med sig är att även man vet \(e\) så är det väldigt svårt att beräkna \(d\) om man inte vet primtalsfaktorerna av \(n\).
Givet att vi håller primtalen vi valde hemliga skulle vi alltså kunna låta \(e=3\) och \(n=187\) vara den ”publika nyckeln” som vi berättar om för hela världen. Sedan om någon vill skicka något hemligt \(x\) till oss, så kan de beräkna \(y=x^3\ \text{mod }187\) och skicka detta tal \(y\) till oss. Eftersom vi är de enda som känner till den ”privata nyckeln” \(d=27\) så är det bara vi som kan beräkna $$y^{27}=(x^3)^{27}=x\ (\text{mod }187).$$ Notera att vi med dessa val av primtal aldrig kan kryptera något som är större än 187, så det vore kanske bra om vi hade valt lite större primtal.
I exemplet ovan så använde vi som sagt kanske inte jättestora primtal, så det finns också en risk att någon skulle kunna testa sig fram och komma på värdet av vår hemliga nyckel \(d\). På internet brukar man nu ofta prata om RSA 2048, vilket innebär att primtalen \(p\) och \(q\) består av ungefär 1024 bitar vardera, så att produkten \(n=pq\) består av 2048 bitar. För att få en känsla för hur stort ett sådant tal är så ges ett exempel nedan: $$p=124851015837396652329802378618700456496154449718991687335679207429037162645731370194285435257260630957265978893726383287889943748516431422176093310633557449842656742385735552477494086455180099238675852898242211858391532347868743622869120844593963421437247348688274402275593184502977025687500170283891724945167$$ $$q=154121568072728878930903785347851302863934809986549478861717506492409898426165416616596493252852373555616700973788626329246436889795387999185425321253202437026596799499641757010316896953010468206969157872441837696776071657278910378978849606625193804565493463692219290973482472311158802224268061774178393417671$$ $$n=19242234336332679510258367935303478159238670785544656710147162298446949799577167710946260574973433900552248949822408520962348408623043328527194926290566660293886401501037030761716347620607646923223977972049814165869627366472165036974179787196651582062855199446503131383414949809130145634412878270307831176137795445273888709565813439644496512118977727165376520084972845678151805885694830661837075746006366471111693731560994368945351994069494540401939671555618550015127457248472931772437929130136827349447158691050727037730866583926614699421124146268610585531805420601866063326378198425415410865467437877741826203846057$$
En lite knasig egenskap hos matematik är att det är mycket enklare att multiplicera två tal än vad det är att o-multiplicera en produkt två tal. Min dator kan multiplicera de två talen \(p\) och \(q\) ovan på mindre än en sekund, men om man börjar med talet \(n\) och vet att det är produkten av två tal så är det väldigt svårt att hitta dessa tal. En liknelse är att det är väldigt enkelt att blanda ett glas mjölk med ett glas vatten genom att hälla dem båda i ett stort glas, men det är väldigt svårt att dela upp denna osmakliga sörja i de två ursprungliga glasen. Det som vi ville ha sagt med argumentet ovan är att detta är anledningen till att man ofta hör talas om begreppet primtalsfaktorisering, och att om någon skulle hitta en snabb algoritm för detta så skulle alla våra kryptosystem fallera. Detta är också anledningen till varför kvantdatorer är ett hett ämne, eftersom en fungerande kvantdator skulle ha möjlighet att utföra snabba primtalsfaktoriseringar.
En sista poäng innan vi går vidare: Med riktigt stora val av primtal så spelar det ofta ingen roll vad den publika nyckeln \(e\) är. Om man vill underlätta krypteringsbiten (vilket är att beräkna potensen \(x^e\)) så väljer man ofta små tal för \(e\) för att effektivisera denna beräkning. Klassiskt vanliga val av \(e\) är \(3\) och \(2^{16}+1=65537\). Det kan kännas lite obehagligt att ett så litet tal som 3 används av ens kreditkort (är det verkligen säkert!?) men även om \(e\) är litet så är det lika svårt att beräkna inversen \(d\).
Det här blev en lång introduktion till RSA, men nu är vi fullt rustade att börja med dagens cryptopals-uppgifter! Nästa uppgift på tur är:
Challenge 36: Implement Secure Remote Password (SRP)
Jaha… Vi var visst inte framme vid RSA än…
Det där en ganska trist uppgift i alla fall, så vi skippar den.
Hmm, ajdå. Eh. Vi skippar uppgift 37 och 38 också. De är också tråkiga. Vi kanske kommer tillbaka till dessa i framtiden när vi får slut på roliga grejer att prata om. Dags för RSA!
Challenge 39: Implement RSA
Som ni sett ovan så är denna ganska enkel, det är bara att tänka på hänglås. Vissa detaljer kan bli lite jobbiga beroende på programmeringsspråk eftersom man måste kunna hantera väldigt stora tal, men det löser ni!
Challenge 40: Implement an E=3 RSA Broadcast attack
Vi har nu diskuterat RSA i en evighet och pratat om hur bra det är, och nu ska vi redan knäcka algoritmen? Känns bra. Konceptuellt är RSA sten-säkert, men när vi i praktiken implementerar algoritmen med matematik så uppkommer vissa sårbarheter som man måste vara medveten om för att kunna hantera.
I denna uppgift tänker vi oss att det finns ett hemligt meddelande \(x\) som vi vill komma åt, men det skyddas av en (dålig) RSA-implementation där den publika nyckeln \(e\) alltid är lika med 3, men där den andra publika nyckeln \(n\) ändras från gång till gång. Antag att vi kan skicka en förfrågan till en webbsida som svarar med en RSA-kryptering av \(x\). Låt oss tänka att varje gång vi gör denna förfrågan så får vi tillbaka en ny RSA-kryptering av \(x\) med en ny publik nyckel \(n\).
Med andra ord, antag att vi har fått tre varianter:
- \(y_1 = x^3\ (\text{mod }n_1)\)
- \(y_2 = x^3\ (\text{mod }n_2)\)
- \(y_3 = x^3\ (\text{mod }n_3)\)
Vi vet inte vad \(x\) är, och vi känner inte till de privata nycklarna \(d_1,d_2,d_3\). Men vi känner till matematik! En rolig sats är den kinesiska restsatsen som helt enkelt säger hur man kan beräkna konstanter \(m_1,m_2,m_3\) så att $$y = y_1\cdot m_1+y_2\cdot m_2+y_3\cdot m_3$$ uppfyller
- \(y = y_1 = x^3\ (\text{mod }n_1)\)
- \(y = y_2 = x^3\ (\text{mod }n_2)\)
- \(y = y_3 = x^3\ (\text{mod }n_3)\)
Det innebär till och med att detta \(y\) uppfyller $$y=x^3\ (\text{mod }n_1\cdot n_2\cdot n_3)$$ och eftersom \(x<n_1, x<n_2\) och \(x<n_3\) så vet vi att \(y=x^3\) även utan modulo. Alltså, vi kan helt enkelt beräkna tredje-roten ur \(y\) för att få fram \(x\).
Math!
Vad var det för fel på denna implementation då? Jo, det stora problemet var att man inte använde någon form av padding av \(x\) innan den krypterades. Om vi skulle lägga på en slumpmässigt padding på \(x\) innan kryptering så skulle denna attack ej fungera. Man skulle också kunna försöka säkerställa att samma \(x\) inte krypteras flera gånger med olika RSA-parametrar. I allmänhet behövs lika många krypterade meddelanden som storleken på exponenten \(e\) för att denna attack ska fungera, så i detta avseende är ett litet val av \(e\) dåligt.
Challenge 41: Implement unpadded message recovery oracle
I denna uppgift tänker vi oss att det finns en webbserver med en fixerad RSA-uppsättning (med kända publika nycklar \(e\) och \(n\) samt en okänd privat nyckel \(d\)) som tar emot emot krypterade (icke-paddade) meddelanden \(x^e\) och returnerar \(x\). Denna webbserver fungerar helt enkelt som ett orakel som tar emot krypterade meddelanden och returnerar klartexten. Ett krav som oraklet har är dock att den vägrar svara om den redan har tagit emot det krypterade meddelandet vid ett tidigare tillfälle. Den sparar helt enkelt en lista över alla krypterade meddelanden som den får in, och om någon försöker få ut samma information igen så vägrar den.
Målet i uppgiften är att försöka lura detta orakel att returnera klartexten från en text som redan har krypterats. Låt oss tänka oss scenariot där vi via avlyssning kommit över någons krypterade meddelande \(y=x^e\), och denna person har redan bett oraklet att dekryptera det.
Detta är enkelt gjort. Låt oss ta ett godtyckligt tal \(s\), säg \(s=2\). Eftersom vi vet de publika nycklarna så kan vi kryptera \(s\) som \(t=s^e=2^e\ (\text{mod }n)\) och sedan beräkna produkten $$z = y\cdot t\ (\text{mod }n).$$
Vi kan nu be oraklet att dekryptera \(z\) (eftersom den aldrig sett \(z\) tidigare), vilket ger oss $$z^d=(t\cdot y)^d = (s^e\cdot x^e)^d = ((s\cdot x)^e)^d = s\cdot x\ (\text{mod }n).$$
Med (andra) ord, oraklet kommer då returnera klartexten \(s\cdot x\) och det är bara för oss att dividera bort \(s=2\) från denna klartext för att få ut \(x\).
Math!
Notera bara att divisionen sker i \(\mathbb{Z}/n\mathbb{Z}\) (det vill säga: modulo \(n\)) så tänk lite innan du dividerar så ska det nog gå bra!
Denna uppgift visar helt enkelt återigen att padding av klartexten innan kryptering är en bra grej. Dessutom får man väl helt enkelt akta sig för att råka exponera sådana orakel ifall det enda de kollar på är ifall det krypterade meddelandet skickats in tidigare eller inte. Man skulle exempelvis kunna kontrollera om den underliggande klartexten har en förväntad struktur, om informationen i klartexten har returnerats tidigare, etc.
Mer än så här hinner vi nog inte denna gång. Nästa gång kommer vi troligtvis visa på andra möjliga fel man kan göra när man implementerar RSA (även med padding). På återseende!