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
Python » Kryptoblog

Archive for the ‘Python’ category

En liten 6502-emulator

July 15th, 2008

Vad passar bättre en regntung semesterdag än testkoda en emulator av den gamla processorn MOS 6502?

MOS 6502

Jag kunde i alla fall inte komma på något bättre och hackade lite Python nu på eftermiddagen. 176 rader senare inklusive kommentarer, filhuvud och testfall kan jag i alla fall köra några instruktioner:


js@sotis:/Users/js/tmp>./6502.py
MOS 6502: CPU initializing.
MOS 6502: Dumping memory from 100 to 111
100: ea
101: ea
102: ea
103: ea
104: ea
105: ea
106: ea
107: ea
108: ea
109: ea
10a: ea
10b: ea
10c: ea
10d: ea
10e: ea
10f: ea
110: 60
111: 0
MOS 6502: Running program from start address 100
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing NOP
MOS 6502: Executing RTS
Cycles executed: 34

(Japp, min emulator räknar bland annat även cykler. Har alltid velat ha den funktionen. Tänk vad många cykler man räknade i sin finniga ungdom när man kodade på C64:an.)

Det saknas en massa instruktioner och jag är inte säker på om jag verkligen skall ha en separat decode-funktion och en exekverings-funktion. Det blir väldigt mycket upprepning av if-elsif-elsif-else i de två funktionerna.

En intressant (nåja) observation är att min emulator, skriven i ett intepreterande språk, antagligen är flera gånger snabbare än den verkliga processorn. Dock inte lika snabb som den variant av 6502 vi byggde in i InformAsics VPN-chip, den går i upp till 33 MHz.

Jag, Python och kryptot HC-128

May 5th, 2008

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.

Bra introduktion till Pythons generatorer

April 30th, 2008

(Det börjar bli en del om Python här…. Jag har skapat en kategori för Pythonrelaterade postningar.)

För några veckor sedan bloggade jag om Pythons generatorer, vilka bland annat är utmärkta för att implementera strömkrypton, slumptalsgeneratorer etc.

För några dagar sedan sprang jag på en bra presentation som ger en introduktion till Pythons generatorer. Den klart bästa förklaring till vad generatorer är och hur man arbetar med dom. Väl värd att bläddra igenom.

Hacka Google med Google App Engine

April 10th, 2008

För några dagar sedan presenterade Google sin nya tjänst App Engine.

App Engine

Med App Engine erbjuder Google en miljö och utrymme för att köra applikationer hos Google. Google beskriver applikationsmiljön på följande sätt:


The Application Environment
Google App Engine makes it easy to build an application that runs reliably, even under heavy load and with large amounts of data. The environment includes the following features:

  • dynamic web serving, with full support for common web technologies
  • persistent storage with queries, sorting and transactions
  • automatic scaling and load balancing
  • APIs for authenticating users and sending email using Google Accounts
  • a fully featured local development environment that simulates Google App Engine on your computer

Google App Engine applications are implemented using the Python programming language. The runtime environment includes the full Python language and most of the Python standard library.

Although Python is currently the only language supported by Google App Engine, we look forward to supporting more languages in the future.

The Sandbox
Applications run in a secure environment that provides limited access to the underlying operating system. These limitations allow App Engine to distribute web requests for the application across multiple servers, and start and stop servers to meet traffic demands. The sandbox isolates your application in its own secure, reliable environment that is independent of the hardware, operating system and physical location of the web server.

Examples of the limitations of the secure sandbox environment include:

  • An application can only access other computers on the Internet through the provided URL fetch and email services and APIs. Other computers can only connect to the application by making HTTP (or HTTPS) requests on the standard ports.
  • An application cannot write to the file system. An app can read files, but only files uploaded with the application code. The app must use the App Engine datastore for all data that persists between requests.
  • Application code only runs in response to a web request, and must return response data within a few seconds. A request handler cannot spawn a sub-process or execute code after the response has been sent.

Google beskriver även Pythonmiljön närmare:


The Python runtime environment uses Python version 2.5.2.

The environment includes the Python standard library. Of course, calling a library method that violates a sandbox restriction, such as attempting to open a socket or write to a file, will not succeed. For convenience, several modules in the standard library whose core features are not supported by the runtime environment have been disabled, and code that imports them will raise an error.

Application code must be written exclusively in Python. Code with extensions written in C is not supported.

The Python environment provides rich Python APIs for the datastore, Google Accounts, URL fetch and email services. App Engine also provides a simple Python web application framework called webapp to make it easy to start building applications.

For convenience, App Engine also includes the Django web application framework, version 0.96.1. Note that the App Engine datastore is not a relational database, which is required by some Django components. Some components, such as the Django template engine, work as documented, while others require a bit more effort. See the Articles section for tips on using Django with App Engine.

You can upload other third-party libraries with your application, as long as they are implemented in pure Python and do not require any unsupported standard library modules.

Det ser alltså ut som att Google lagt ner mycket arbete på att se till att App Engine-applikationer exekverar i en säker miljö som inte hotar andra applikationer eller Googles egna system. Det har nu inte hindrat folk att försöka. Tvärt om, att döma av maillistor som Dailydave har rätt många börjat stampa på Pythonmiljön för att se om det går att slå hål på sandlådan.

En av de första applikationer som dykt upp i App Engine är ett interaktivt Python-skal. Och den applikationen använts för att undersöka vad som går att göra, bland annat försök att komma åt passwd-filer, och på andra sätt titta och peta i Pythonmiljön och det underliggande systemet. En hel del försök har dock slutat i det här meddelandet:

This Google App Engine application is temporarily over its serving quota. Please try again later.

Jag satt och testade lite själv för att se hur mycket av Pythons standardbibliotek man får med:


Google Apphosting/1.0
Python 2.5.2 (r252:60911, Mar 12 2008, 14:07:58)
[GCC 4.1.0]

>>> import this
>>> import os
>>> os.path
(module ‘posixpath’ from ‘/base/python_dist/lib/python2.5/posixpath.py’)

(Jag har ändrat syntaxen från responsen i skalet då hakparanteserna fastnade i WordPress…)

OS-modulen finns med, och det går uppenbarligen att titta runt i sandlådans struktur. Men Pythons påskägg “this” har Google inte plockat med…

Vi får se om/när någon lyckas slå hål på App Engine, om Google lyckats rensa ut alla accesser till underliggande systemet eller ej. Google har ju en bra grundförutsättning i och med att Guido van Rossum arbetar på Google.
Guido

Är det någon som borde kunna ha bra koll på hur man bygger om Python är det BDFL.

Pythongeneratorer och RC4

April 7th, 2008

Ett litet erkännande: Jag gillar programspråket Python.

Jag började använda Python så smått för några år sedan, och sedan dess har användningen bara ökat. Jag använder i dag Python bland annat till att bygga program som genererar parametriserade hårdvarubeskrivningar (i Verilog eller VHDL), exempelvis av krypton.

Ofta har jag även ett Pythonskal igång i ett terminalfönster och använder den som en miniräknare, genererar små sekvenser, testhackar m.m. Jag upplever att Python har gjort att mina konstruktioner inte bara är mycket bättre, utan att jag arbetar mer effektivt och är mer produktiv.

Några av de saker jag gillar med Python är dess objektorientering, att det är lätt att komma igång och att det känns som att det finns en organiserad tanke och struktur hur kommandon etc är uppbyggda. Det funkar som jag tror att det gör. Men en av de viktigaste aspekterna är (anser jag) att programmen blir läsbara.

Jag kan läsa program jag skrev för flera veckor sedan och fatta vad det gör och jag kan läsa andras kod. (I det här läget brukar jag peka på Trac och dess kod som exempel på hur snygg Pythonkod kan vara. Trac är för övrigt en annan sak jag gillar.)

Samtidigt anser jag mig fortfarande mycket av en Python-novis. Jag använder få av språkets många funktioner, men det är inget problem utan med de kunskaper jag har i dag kan jag snabbt och enkelt göra det jag vill. Sedan är det bara kul att lära sig nya aspekter av språket som gör mig än mer effektiv.

I morse satte jag mig ned och testade generatorer (generators), dvs funktioner som kan fungera som en tillståndsmaskin, eller varför inte som uppdateringsfunktionen i ett strömkrypto.

När jag ändå är igång och erkänner en massa saker kan jag väl erkänna att jag gillar strömkryptot RC4. Ja, det har sina vårtor, speciellt i vissa tillämpningar. Men jag vet få relativt bra krypton som är så enkla att förstå och där man lätt kommer ihåg algoritmen som RC4 (försök att memorera AES-algoritmen).

En annan fördel med RC4 är att RC4 går att köra för hand med papper och penna om så krävs. Och med en nyckel som skalar till 4096 bitar, om man tar hänsyn till FMS-attacken (och kastar bort säg 4096 bytes från strömmen) är det fortfarande ett rätt säkert krypto.

Därför valde jag i morse att implementera RC4 som en Pythongenerator. Själva generatordelen av koden ser ut så här:


def rc4(key):

# RC4 stream generation. The while loop will yield between # function calls and return the latest key stream value. ipoint = 0 jpoint = 0 while(True): ipoint = (ipoint + 1) % 256 idata = state_array[ipoint] jpoint = (jpoint + idata) % 256 jdata = state_array[jpoint] state_array[ipoint] = jdata state_array[jpoint] = idata kpoint = (idata + jdata) % 256 kdata = state_array[kpoint] yield(kdata)

(Ja, koden går att dra ihop och bla går swap att göra på ett mer kompakt sätt…)

Notera satsen yield. Detta kommando beter sig som en vanlig return-sats, men skillnaden är att tillståndet hos funktionen bevaras, och vid nästa anrop fortsätter exekveringen efter yield-satsen, dvs nästa varv i while()-satsen.

För att använda en generator skapar man en referens till funktionen genom att göra en tilldelning. Men eftersom funktionen innehåller en yield-sats och därmed är en generator kommer Python att skapa ett objekt (allt i ett Pythonprogtam är ju objekt) med en next()-metod. Och det är via den vi sedan kör vår generator:

# Create an RC4 generator initialized with a key. my_key = “Kryptoblog” my_rc4 = rc4(my_key) # Generate a short key stream. print “RC4 key stream for key ‘%s’:” % my_key for i in range(16): print ” key stream value %d = %d” % (1, my_rc4.next())

När jag kör detta program får jag följande:


js@sotis:/Users/js/tmp/Div>./rc4_test.py
RC4 key stream for key ‘Kryptoblog’:

key stream value 0 = 184 key stream value 1 = 152 key stream value 2 = 122 key stream value 3 = 134 key stream value 4 = 184 key stream value 5 = 174 key stream value 6 = 24 key stream value 7 = 177 key stream value 8 = 238 key stream value 9 = 192 key stream value 10 = 172 key stream value 11 = 176 key stream value 12 = 86 key stream value 13 = 90 key stream value 14 = 51 key stream value 15 = 205

Det som inte finns med i koden ovan är initieringsdelen av RC4, vilket naturligtvis måste finnas med för att vi skall få ut en korrekt nyckelström. Jag kommer att lägga upp det kompletta programmet på en sida här på bloggen. Återkommer om detta.

Min erfarenhet av att leka en söndagsmorgon med Python-generatorer är att det fungerade precis som jag hoppats, att det var enkelt att använda och fungerade bra för att implementera en funktion som RC4.

(Vill man se en objektorienterad Pythonimplementation av RC4 i finns det en på Wikipedias sida för RC4, vilket jag upptäckte när jag byggt klart mitt hack och skulle äta frukost….)