Ankor på vift

A freedom-oriented travel blog

Elliptiska kurvor och Bitcoin / Elliptic curves and Bitcoin

(Please scroll down to the orange text for the English version)

En av fördelarna med att vara en del i en ankgemenskap är att man lär känna väldigt intressanta människor som kan olika saker. Denna vecka anordnande en vän till oss en föreläsning om matematiken bakom Bitcoin och vi såg med spänning fram emot föreläsningen. Vår vän är matematiker från Finland och hans föreläsning handlade om primtal, modulär aritmetik och elliptiska kurvor över begränsade fält, som är vad Bitcoin delvis bygger på. Det var en oerhört givande föreläsning för oss båda. Ulrika blev överlycklig över att nu fått lära sig hur man utför division i modulär aritmetik, då hon håller på att lära sig själv om modulär aritmetik och hittills bara har utforskat multiplikation.
Föreläsningen gick igenom hur modulär aritmetik fungerar för addition, subtraktion, multiplikation och division. Sedan hur ekvationer för olika kurvor ser ut och hur de beter sig i ett vanligt enkelt tvådimensionellt (kartesiskt) koordinatsystem och hur man avgör om en viss punkt i koordinatsystemet finns på en viss kurva eller inte. Sedan kom vi in på elliptiska kurvor och vilka särskilda egenskaper de har, som att addition av två punkter alltid blir lika med en annan punkt på kurvan.

Efter vi gjort allt detta med förenklade exempel så var det dags att studera den specifika elliptiska kurva som används i Bitcoin för den assymetriska krypteringen som används för att generera den privata och publika nyckeln som en bitcoin-plånbok i sin enklaste form består av. Den privata nyckeln skall hållas hemlig och är den som behövs för att signera en överföring av bitcoin från dig till någon annan. Den publika nyckeln behöver som namnet antyder inte hållas hemlig och är något förenklat den address som du ger ut för att andra personer ska kunna överföra bitcoin till dig. För mer detaljerad information om hur detta fungerar så kan ni läsa Pontus guide till hur man förvarar bitcoin säkert. Men om ni inte kan så mycket om Bitcoin alls så börja med att läsa Pontus guide om vad Bitcoin är och hur det skiljer sig från andra sorters valutor.

Anledningen till att man använder modulär aritmetik för den elliptiska kurvan i Bitcoin är för att få en kurva med ett begränsat antal punkter (en begränsad kropp), istället för en kurva med oändligt antal punkter. Man använder också bara primtal för den modulära aritmetiken då primtal aldrig generar samma punkt två gånger på den elliptiska kurvan, vilket andra tal gör.
En publik nyckel i Bitcoin representerar en specifik punkt på den elliptiska kurvan inom den begränsade kroppen skapad av modulär aritmetik. Den privata nyckeln är hur många gånger en definierad startpunkt på den elliptiska kurvan, som kallas generatorn (G), adderas med sig själv för att ge punkten för den publika nyckeln. Har man bara tillgång till en publik nyckel så är det omöjligt att gissa den privata nyckeln, dvs hur många gånger punkten G ska adderas med sig själv, utan att prova alla möjliga kombinationer. Däremot  är det enkelt att räkna fram punkten på kurvan för den publika nyckeln om man vet vad den privata nyckeln är. En privat nyckel (hur många gånger punkten G ska adderas med sig själv) väljs som ett slumpmässigt tal mellan 1 och ungefär 10^77 (2^256, eller 256 bitar). Detta tal är oerhört stort, i storleksordningen av antal atomer i universum. Säkerheten i Bitcoin bygger på att det är omöjligt att testa alla kombinationer för att avgöra vilken “atom” i universum som är din privata nyckel.

Det blev också en hel del diskussioner om matematik och speciellt skolundervisning generellt i Finland, Sverige och andra delar av världen, och vi fick vädra våra argument om varför vi aldrig kommer sätta våra eventuella framtida barn i det svenska skolsystemet.


One of the benefits of being part of an ancap community is that you get to know very interesting people that know different things. This week, a friend to us arranged a lecture on the mathematics behind Bitcoin and we looked forward with excitement to the lecture. Our friend is a mathematician from Finland, and his lecture was about prime numbers, modular arithmetic and elliptic curves over finite fields, which is part of what makes Bitcoin possible. It was an incredibly rewarding lecture for both of us. Ulrika was overjoyed to learn how to perform division in modular arithmetic, because she has been teaching herself about modular arithmetic and only explored multiplication so far.

The lecture went through how addition, subtraction, multiplication and division works in modular arithmetic. Then we explored how the curves for different equations look like, how they behave in a normal simple two-dimensional (Cartesian) coordinate system and how to determine whether a certain point in the coordinate system exist on a defined curve or not. Thereafter, we continued with elliptic curves and what special properties they have, such as how the addition of two points on the curve is always equal to another point on the curve.
After we have done all this with simplified examples, it was time to study the specific elliptic curve used in Bitcoin for the asymmetric encryption used to generate the private and public key, which is a bitcoin wallet in its simplest form. The private key must be kept secret and it is required for signing a transfer of bitcoin from you to someone else. The public key, as the name suggests, do not need to be kept private, and the public key is somewhat simplified, the address you give out to other people so they can send bitcoins to you. For more detailed information on how this works, you can read Pontus guide on how to store bitcoin safely.  If you do not know much about Bitcoin at all, we suggest you start with reading Pontus guide on what Bitcoin is and how it differs from other kinds of currencies first.

The reason for using modular arithmetic for the elliptic curve in Bitcoin, is to obtain a curve with a limited number of points (a finite field), instead of a curve with an infinite number of points. Also, only prime numbers are used for the modular arithmetic, because prime numbers never generate the same point twice on an elliptic curve, which other numbers do.
A public key in Bitcoin represents a specific point on the elliptic curve within the finite field created by the modular arithmetic function. The private key is the number of times a defined start point, called the generator (G), on the elliptic curve, is added to itself to end up on the point on the curve which is the public key. It is impossible to guess the private key, ie how many times G must be added to itself, if you only have access to a public key, unless you try all possible combinations. However, it is easy to calculate the point on the curve that is the public key, if you know what the private key is. A private key (how many times the point G is added to itself) is chosen as a random number between 1 and approximately 10 ^ 77 (2 ^ 256 or 256 bits). This number is extremely large, the same order as the number of atoms in the universe. The safety of Bitcoin is based on that it is impossible to test all the combinations to determine which “atom” in the universe that is your private key.

We also had a lot of discussion about mathematics and about public schools in general, in Finland, Sweden and other parts of the world, and we got to air our arguments about why we never want to put our possible future children in the Swedish school system.20160328_171715.jpg

20160328_171706.jpg

20160328_172628.jpg

En bra översikt över elliptiska kurvor och hur de används inom kryptografi / A good overview of elliptic curves and how they are used in cryptography:

2 Comments

  1. Wow en helt ny värld! Beroende på hur stekt jag känner att min hjärna är så ska jag eventuellt gå på föreläsning på Paralelní Polis med Adam Back

    • Ulrika

      April 3, 2016 at 9:45 pm

      Den föreläsningen tycker jag inte att du ska missa :)! Har du kollat in videon längst ned inlägget också? /Ulrika

Leave a Reply

Your email address will not be published.

*

© 2017 Ankor på vift

Theme by Anders NorenUp ↑