Warning: Missing argument 2 for wpdb::prepare(), called in /home/stromber/public_html/kryptoblog/wp-content/plugins/wp-super-edit/wp-super-edit.core.class.php on line 109 and defined in /home/stromber/public_html/kryptoblog/wp-includes/wp-db.php on line 1222
Jag, Python och kryptot HC-128 » Kryptoblog

Jag, Python och kryptot HC-128

May 5th, 2008 by Joachim Strömbergson Leave a reply »

Jag har ägnat några timmar den senaste dryga veckan med att implementera eSTREAMkryptot HC128.

Målet är egentligen att skapa en IP-core-generator, dvs ett program som kan generera ett antal olika implementationer, beroende på vilken prestanda som applikationen kräver och vilken storlek på konstruktionen som är acceptabel. Som jag brukar implementera krypton på InformAsic.

När jag bygger en generator av en funktion (ett krypto en hashfunktion etc) brukar jag börja med att skriva en SW-modell utifrån specifikationen. Ja, även om det redan finns en referensmodell. Skälet är helt enkelt att när jag arbetar med att skriva modellen får jag chans att arbeta rent konkret med specifikationen, se om jag begriper den och om den är entydig.

Att bygga en första modell gör även att jag hinner tänka igenom vad en HW-implementation kommer att kräva. Få koll på minnen, register och möjligheter att parallellisera. Se vilka resurser som i en HW-implementation skulle gå att dela på etc.

Själva generatorn skriver jag numera alltid i Python med diverse egenutvecklade klasser för att skapa generatorer för IP-cores. Och SW-modellen brukar jag skriva i C.

Men den här gången tänkte jag testa att göra även SW-implementationen i Python. Eftersom jag inte är ute efter att få en SW-modell som ger maximal prestanda, utan är funktionellt korrekt och uppdelad på ett sätt som stödjer verifieringen av HW-modellerna borde Python fungera bra.

Men Python är inte riktigt som C. En sak som skiljer är vad jag kallar för Pythons butler-inställning till problemlösning. (Om du verkligen vill skjuta dig i foten ställer Python snällt upp utan att klaga, och hjälper till så att du kan skjuta dig i foten på det sätt du vill.) Detta inkluderar att anpassa variabeltyper dynamiskt. Ett exempel på detta är skiftoperatorn:


>>> kalle
42
>>> kalle = kalle < < 33
>>> kalle
360777252864L

Exemplet ovan visar hur jag skapar mig en variabel kalle och tilldelar den ett litet heltal. Sedan skiftar jag kalle bitmässigt 33 bitar åt vänster. Hade detta varit i C och kalle var en (unsigned) int hade värdet på kalle varit noll. Men Python upptäcker att hoppsan! här är vi på väg att skifta bitar över kanten, och lägger helt enkelt till fler bitar i representationen för kalle så ingen information går förlorad.

Det här är en jättebra funktion i Python som gör att man (i stort sett) helt kan ignorera vad som händer internt, utan bara räkna på med godtyckligt stora tal. Det går exempelvis utmärkt att göra så här:


>>> kalle = kalle < < 100
>>> kalle
3241325209585634862861534625792L

Väldigt mycket datalogi och elegant. Men oj vad det inte funkar när man vill pilla runt på bitar – vilket man ofta gör i krypton.

Så nu har jag fått klura ut hur jag skall arbeta runt Pythons hjälpsamhet, något Python också snällt ställer upp på. Det blir en del hjälpfunktioner för att AND:a och MOD:a, men det går framåt. Jag har även sneglat på att använda array-modulen. Över huvud taget är val av representation något jag funderat mycket på. Jag vill få en modell med bra överblick över den interna implementationen, men jag vill även få en modell som är vettig att använda, dvs den får ett bra och normalt/användbart API.

Tyvärr har jag inte helt lyckats. Jag får fram en modell av som snurrar på bra och fint. Dock får jag inte ut rätt svar enligt de testvektorer som finns i specifikationen för HC-128. Modellen är inte korrekt.

I ren desperation/ilska hackade jag då snabbt samman en implementation i C. Den modellen är, trots att den inte är skriven för någon prestanda över huvud taget riktigt snabb. Jag får drygt 3 Gbit/s på min MacBook. Problemet är att den inte heller räknar rätt…

Jag sitter alltså med två SW-modeller, en i objektorienterad iPython och en i fulkodad C. Ingen av modellerna räknar rätt, och dom räknar inte heller lika utan ger olika fel svar på samma testvektorer.

Men jag ger inte upp! Ny vecka och nya tag! Och dessutom har jag klurat ut hur en HW-implementation bör se ut – om jag nu kan få till en sådan som dessutom räknar rätt.

Ang HC-128 och HW-implementation bör jag kanske säga att även om kryptot är rasande snabbt i SW är det ett krypto med bra möjligheter både till parallellism och till resursdelning – så jag tror att en HW-implementation är intressant och kan bli mycket bra. Det är svårt att banta bort de stora registerbankarna P, Q och W, så implementationen kräver rätt mycket register. Vad man kan laborera med är mängden läsportar, och därmed hur P, Q pch Q implementeras.

När jag fått min HW-generator att fungera kommer jag att publicera lite resultat. Och när jag får jag ordning på min Python-modell av HC-128 lägger jag upp koden här på Kryptoblog.

No related posts.

Related posts brought to you by Yet Another Related Posts Plugin.

Advertisement

2 comments

  1. Martin M says:

    Här är en liten 32-bits integer-klass ifall du skulle ha nytta av den:
    http://pastebin.com/m3caa0abc

    Exempel:
    >>> kalle = int32(5)
    5

    >>> kalle >> hex(int32(0xaabbccdd).rotl(8))
    0xbbccddaa
    >>> hex(int32(0xaabbccdd).rotr(8))
    0xddaabbcc
    >>> hex(int32(0xff) ^ 0xffffffff) # xor
    0xffffff00

    Observera att operationer som *, +=, -= osv inte är implementerade, men det är enkelt att lägga till om det behövs.

  2. Joachim says:

    Aloha!

    Tack! Jag har byggt mina egna, liknande funktioner med det kan vara bra att veta att det finns någon som byggt och testat sådana redan.

Leave a Reply

You must be logged in to post a comment.