TSM - Bitcoin și criptografia
ABONAMENTE VIDEO TESTE REDACȚIA
RO
EN
×
▼ LISTĂ EDIȚII ▼
Numărul 70
Abonament PDF

Bitcoin și criptografia

Dan Sabadis
Senior Software Programmer @ Siemens
PROGRAMARE


Vom începe articolul de față așa cum l-am început pe precedentul: descriind principiile fundamentale ale cripto-monedei (crypto-currency). Dacă articolul anterior, am explicat componenta "currency (monedă)" a cripto-monedă, acum vom explica partea "crypto".

Acest principiu fundamental se numește criptografie. Se referă la formulele matematice ce pot ascunde informații și la alte formule ce pot interpreta informația ascunsă anterior. Pentru a menține informația simplă, vom împărți aceste formule matematice în trei categorii: simetrice, asimetrice și hashing.

Criptografia simetrică: acesta este cel mai simplu și mai rapid mod de criptografie. Emițătorul criptează mesajul cu o parolă, iar destinatarul mesajului îl decriptează cu ACEEAŞI parolă. Un exemplu celebru de criptografie simetrică a fost menționat în "De Bello Gallico" de Cezar: personalul din armată să mute orice literă a alfabetului cu un anumit număr de pași (să zicem 3, deci A devine E, B => F, C => G), deci singurul lucru de care avea nevoie destinatarul era să știe parola pentru a decripta, parolă care în acest caz este 3. Destinatarul trebuia să deruleze literele în spate (E ar deveni A, F to B, G=>C). Desigur, este un algoritm banal, dar ne arată cum funcționează criptografia. Cei mai populari cripto-algoritmi simetrici care sunt momentan în uz sunt: AES, 3DES, RC4.

Criptografia asimetrică: este cel mai sigur tip de criptografie. Aici emițătorul și destinatarul nu mai au aceeași parolă! Destinatarul generează două chei: una este privată fiind o cheie cunoscută doar de el, și o cheie publică pe care destinatarul o poate da oricui. Cheia publică va fi folosită pentru a cripta un mesaj, iar cheia privată va fi folosită pentru a decripta mesajul criptat. Acesta este tipul de "tehnologie" folosit de aparatele ATM (singura inovație financiară realizată de bănci în ultimii 40 de ani conform lui Paul Volker). Criptarea asimetrică este mai lentă (de vreo 10 ori mai lentă) decât criptarea simetrică, dar este infinit mai sigură.

Primul și cel mai celebru algoritm asimetric ce a primit acceptare publică este RSA (în anii 70), unde atât cheia publică, cât și cea privată se generează în același timp. Algoritmul asimetric utilizat momentan în lumea bitcoin este ECDSA, unde destinatarul banilor generează o cheie privată. Apoi, din acea cheie generează mai târziu o cheie publică. Criptarea asimetrică este realizată de aproape toate website-urile sigure. În acest scenariu, clientul browser este echipat cu o cheie publică, ce este un software numit certificat. Browserul criptează mesajele cu această cheie publică și le trimite criptate către server. Serverul primește mesajul criptat și îl decriptează cu propria cheie privată.

Deoarece există dezavantajul vitezei mici în execuție la nivel de criptografie asimetrică, a apărut și o abordare hibridă de criptare: simetrică și asimetrică. Browserul și serverul utilizează comunicare asimetrică doar inițial, până când reușesc să schimbe și să dețină o cheie simetrică specială, numită cheie de sesiune (session key). Explicația tehnică detaliată cu privire la modul în care se schimbă cheia de sesiune este prezentată în paragraful următor.

Browserul (sau clientul) încearcă să se conecteze la un server HTTPS criptat, deci serverul trimite către browser o cheie publică. Apoi, browserul generează o nouă cheie simetrică numită handshake token, o criptează cu cheia publică deja primită de la server, apoi o trimite către server. Serverul primește handshake token-ul criptat și îl decriptează cu cheia sa privată. Apoi, generează propria cheie simetrică numită session token și criptează acest nou session token cu handshake token-ul primit de la client, pentru a-l trimite înapoi către browser. Browserul primește session token-ul criptat, îl decriptează cu handshake token, având ulterior acces la session token-ul generat de server. Acest session token este cheia simetrică care va permite de acum înainte o comunicare rapidă și sigură (de 10 ori mai rapidă) între browser și server. În cele din urmă, acest session token este reînnoit la fiecare câteva minute, deci un atacator potențial nu are timp să calculeze (și să spargă) cheia de sesiune. Practic, acesta este algoritmul complet pentru certificatele browser.

Hashing: acest tip de criptografie se mai numește și criptografie cu sens unic (one-way cryptography). Contrar celor doi algoritmi descriși mai sus, prin hashing putem doar cripta un mesaj fără a-l mai putea decripta după aceea. În lumea Bitcoin, cel mai utilizat algoritm hashing se numește Sha256 și îl vom folosi în mostrele de cod ce urmează. Formal, hashing are următoarele patru proprietăți:

  1. Este o funcție ce permite calcularea facilă a unei valori agregate pentru orice mesaj de intrare.

  2. Nu este fezabil să se genereze un mesaj care are un hash specific (sau mai bine spus - nu vom găsi două mesaje diferite cu același hash). Există și o excepție celebră, algoritmul MD5, folosit extensiv în ultimii 10-15 ani. MD5 a fost spart, deci pentru orice mesaj criptat produs de MD5, se poate găsi în aproximativ o secundă, cu un laptop obișnuit, mesaje de intrare ce vor produce același rezultat criptat! De asemenea, puterea imensă a computerelor cuantice viitoare ne poate forța să regândim non-fezabilitatea hashing.

  3. Nu este fezabil să se modifice un mesaj fără a schimba hashul.

  4. Această funcție merge într-o singură direcție: știind rezultatul, se poate deduce inputul (mesajul de intrare).

Pe baza acestor principii, a apărut și conceptul de semnătură digitală. Proprietarul cheii private adaugă un număr magic la finalul acestui mesaj, semnându-l. (Numărul magic reprezintă semnătura digitală a documentului.) Oricine este proprietarul cheii publice (a fi public înseamnă că poate aparține oricui) poate verifica dacă semnătura este legitimă. Această semnătură pe care doar persoana cu acea cheie privată ar fi putut să o producă pentru acel mesaj este semnătura care "se potrivește perfect" cu cheia publică. Acest concept de semnătură digitală este folosit de Bitcoin pentru validarea tranzacțiilor financiare. De fapt, creatorul Bitcoin/blockchain Satoshi Nakamoto a rezolvat o celebră problemă "de nerezolvat", cea a generalilor bizantini, cu ajutorul acestor concepte.

Imaginați-vă că există trei armate bizantine, fiecare condusă de un general, unul dintre ei fiind chiar împăratul Bizanțului. Încep asediul unei cetăți din zona greu accesibilă a Anatoliei ce aparține unui emir. Din cauza terenului dificil, toate cele trei armate sunt complet separate și pot comunica doar prin porumbei călători. De fapt, aceste condiții sunt atât de dificile, iar poziția emirului este atât de avantajoasă încât împăratul realizează că are o singură șansă să câștige: dacă toate cele trei armate atacă simultan. Dacă una dintre armate nu atacă împreună cu celelalte, atacul va eșua iar pagubele vor fi semnificative. Împăratul trimite celorlalte două armate mesaje prin intermediul porumbeilor: "Atacați la 11 P.M. -9". Unii porumbei zboară direct deasupra orașului ce urmează să fie asediat, deci emirul îi vânează și interceptează mesajul. Emirul observă '-9' de la finalul mesajului și își dă seama că este semnătura mesajului. Rămâne fără opțiuni și trebuie să ia rapid o decizie. Creează un alt mesaj înșelător "Atacați la 6 P.M. -x" și pune 'x' drept semnătură a acestui nou mesaj. Din fericire pentru el, emirul a capturat un ofițer bizantin care este expert criptograf care cunoaște algoritmul necesar pentru producerea semnăturii. Algoritmul utilizează numere prime, iar numărul prim folosit în acest caz este 13 (în lumea reală a IT-ului acesta fiind un număr prim enorm). Prizonierul spune: Imaginați-vă un ceas care nu are 12, ci 13 ore! Pentru mesajul "Atacați la 11 P.M." trebuie să luăm fiecare literă a mesajului și să mutăm ca să corespundă fiecărei litere din alfabet. Deoarece 'A' este prima literă a alfabetului, mutăm acul de la poziția inițială superioară (care este 13) la poziția 1, deci pasul 1: *hash*(A) = 1. A doua literă este 't' care este a 20-a literă din alfabet. Deci, mutăm acul cu 20 de ore de la pasul existent, astfel încât pasul 2 este: hash(t) = 8 ((1+20 =21) % 13). La a 3-a literă întâlnim iar caracterul 't', deci avansăm acul cu încă 20 de ore. Pasul 3: hash(t) = 2 ((8 + 20 = 28) % 13). Repetăm pașii până găsim ultimul număr care este 9. Acest număr este semnătura mesajului original. Observăm că, dacă schimbăm orice literă din mesaj, rezultatul se va schimba semnificativ, deci semnătura va fi cu totul alta. Apoi, emirul spune: Modifică mesajul în "Atacați la 6 P.M. -y" și calculează semnătura y cât mai repede posibil. După ce echipa de criptografi ai emirului a modificat mesajul original și a recalculat noua semnătură ca fiind 5, a trimis câțiva porumbei către armata care credea că ar fi trebuit să primească mesajul. Când armata destinatară a primit toate mesajele de la toți porumbeii călători, au constatat că au primit două mesaje diferite: de la trei porumbei au primit mesajul "Atacați la 11 P.M. -9", iar de la alți doi porumbei, mesajul: "Atacați la 6 P.M. -5". Pentru că au dedus că a fost compromis canalul lor de comunicare, au trimis zece porumbei către armata împăratului cu mesajul "Comunicarea este compromisă. Mai trimiteți o dată ora atacului! -2". După câteva astfel de mesaje, toate armatele bizantine s-au sincronizat la ora corectă a atacului (11 P.M.) deoarece au realizat că MAJORITATEA mesajelor conțineau această oră, iar mesajele ce conțineau orice altă oră au ajuns la destinație cu preponderența DUPĂ cele ce conțineau informația critică: 11 P.M. Într-o manieră pur teoretic-matematică, această problemă nu este rezolvată (încă), dar în manieră probabilistic-practică, această problemă a fost rezolvată de Satoshi sau cel puțin este rezolvată până când computerele cuantice vor fi general disponibile.

În concluzie, cea mai importantă funcționalitate a unui sistem modern criptografic este ca arhitectura sa să fie publică! Se mai numește și Principiul lui Kerchoff: chiar dacă inamicul vostru știe cum codați sau decodați mesajele, nu le va putea decoda deoarece ei nu au parola ta secretă.

Gata cu teoria! Haideți să ne ocupăm de puțin cod real. Toate exemplele următoare vor fi prezentate în limbajul C#. Majoritatea exemplelor sunt preluate dintr-o carte excelentă: "Mastering Bitcoin" de Andreas Antonopoulos. Cum programele originale sunt scrise în Python, pe care noi le-am transpus în C# 7, veți avea nevoie de Visual Studio 2017 Community Edition pentru a rula mostrele (sau orice alt editor împreună cu compilatorul de C# 7).

Pentru început, creăm o metodă de extindere (extension method) a tipului public string, deci putem produce un hash SHA256 pentru fiecare string de intrare (input string).

public static string ToSha256(this string value)
{
  var sb = new System.Text.StringBuilder();

  using (var hash = System.Security
     .Cryptography.SHA256.Create())
    {
      byte[] result = hash.ComputeHash(
        Encoding.UTF8.GetBytes(value));

      foreach (byte b in result)
        sb.Append(b.ToString("x2"));
    }

    return sb.ToString();
 }

Acest algoritm se numește SHA256 deoarece, pentru orice string, indiferent de lungime, obținem un rezultat de dimensiune fixă: un tablou (array) de 256 bits care transpuși în stringuri hexazecimale vor genera un string de 64 de caractere lungime (256 împărțit la 4 - o valoare hexazecimală este reprezentată pe 4 bits de memorie). Vom produce 20 de stringuri de intrare (input strings) ce diferă prin doar un caracter și vom calcula rezultatul lor SHA256 hash.

private static void Sha256Sample()
{
   string text = "I am Satoshi Nakamoto";
   Console.WriteLine(text.ToSha256());

   for (int nonce = 0; nonce < 20; nonce++)
    {
      string input = text + nonce;
      var hash = input.ToSha256();
      Console.WriteLine($"{input}=>{hash}");
     }
}

Dacă rulăm metoda Sha256Sample, aceasta va produce rezultatul de mai jos. Putem observa că, deși stringurile de intrare (input strings) diferă doar la nivel de un caracter, rezultatele sunt complet diferite și nelegate vizual una de cealaltă. În plus, observăm că pentru nonce=13 (la a 14-cea iterație) rezultatul este cel mai mic, singurul care are un 0 inițial.

Mai mult, este important de menționat că, indiferent de hardware-ul utilizat, de limbajul de programare sau de sistemul de operare, acest program va produce mereu același rezultat; deci, pentru un input string precum "I am Satoshi Nakamoto" și un *nonce* 13 rezultatul va fi acesta peste tot: "0ebc56d59a34f5082aaef3d66b37a661696c2b618e62432727216ba9531041a5"

Implicația este că, dacă cineva găsește o valoare mică pentru oricare string de intrare (input string), va încerca să adauge repetat nonce la string (care are un număr egal cu încercările precedente eșuate). Odată ce găsește o valoare mai mică decât un prag scăzut, va publica tot: input string, nonce și rezultatul. Apoi, oricine poate testa foarte rapid că a face hashing pentru un input dat și pentru nonce duce la obținerea rezultatului publicat. Toată această informație publicată (input, nonce și rezultat) se numește Proof of Work. Acest algoritm a fost introdus și publicat pentru prima oară de Hal Finney. Practic, așa funcționează încrederea în lumea Bitcoin. Explicăm mai jos detaliile implementării.

Vom folosi un tip de date special, numit BigInteger ce susține un interval mult mai mare de valori decât un integer obișnuit (4 bytes de meorie) sau long (8 bytes de memorie).

Am creat încă două extension methods, una numită "Pow" ce aplică exponențierea oricărui număr întreg și una numită ToBigInteger ce convertește reprezentarea string-ului dintr-un număr hexazecimal într-un număr zecimal.

Metoda ProofOfWork ia drept prim input stringul pe baza căruia trebuie să producem un rezultat criptat SHA256. Apoi, ia drept input parametrul Bits ce este al doilea ca dificultate și care este folosit pentru a calcula numărul țintă cu o valoare "suficient de mică". Acesta este algoritmul de bază: după ce calculăm ținta, încercăm să producem în mod repetat o valoare mai mică decât ținta. Odată obținută, după multe încercări și erori, oprim execuția publicând cele trei elemente: primul string de intrare, nonce și rezultatul calculat ce este mai mic decât ținta.

public static class Sha256HashAlgorithms
{
  static readonly BigInteger MAX_NONCE;

  static Sha256HashAlgorithms()
  {
     MAX_NONCE = 2.Pow(32);
  }

  public static BigInteger Pow(this int baseOfPower
     ,int exponent)
  {
     return (BigInteger)Math
       .Pow(baseOfPower, exponent);
  }

  public static BigInteger ToBigInteger(
    this string hexString)
  {
  return BigInteger.Parse(0+hexString, 
    NumberStyles.AllowHexSpecifier); 
   // converts hex string into decimal number
  }

  public static Tuple 
    ProofOfWork(string eachMinerBlockHeaderHash, 
    int difficultyBits)
    {
      var target = 2.Pow(256 - difficultyBits); 
      // the greater difficulty => the lower the target
      for (int nonce = 0; nonce < MAX_NONCE; nonce++)
      {
        string hashResult = (eachMinerBlockHeaderHash 
          + nonce).ToSha256();
        var result = hashResult.ToBigInteger();
        if (result < target)
        {
          return Tuple.Create(hashResult, nonce, 
           target);
        }
     }

     return Tuple.Create(string.Empty, 0, 
       new BigInteger());
   }

   public static void ProofOfWorkSample()
   {
     Stopwatch stopWatch = new Stopwatch();
     string previousHashResult = string.Empty;
     for (int difficultyBits = 0; difficultyBits < 32; 
       difficultyBits++)
     {
       var difficulty = 2.Pow(difficultyBits);
       Console.WriteLine($"\nDifficulty: {difficultyBits}
         =>2^{difficultyBits}={difficulty}");

       string oldBlock="test block with transactions" 
         + previousHashResult;

       Console.WriteLine($"Starting search for new"+ 
        "block based on the old: {oldBlock}...");

       stopWatch.Start();

       //Deconstruction in C# 7
       var (hashResult, nonce, target) = 
     ProofOfWork(oldBlock, difficultyBits);

       previousHashResult = hashResult;

       stopWatch.Stop();

       // Get the elapsed time as a TimeSpan value.
       TimeSpan ts = stopWatch.Elapsed;
       if (ts > TimeSpan.Zero)
       {
         string elapsedTime = $"{ts.Hours:00}:
           {ts.Minutes:00}:{ts.Seconds:00}.
           {ts.Milliseconds/10:00}";

         Console.WriteLine($"Success with"+     
           "nonce {nonce}.\nHash is {hashResult}.\"+
           "nElapsed Time {elapsedTime}\nTarget was"+ 
       "2^(256 - {difficultyBits})={target}.");

         var hashPower = (int)(nonce/
       ts.TotalSeconds);

        Console.WriteLine($"Hashing Power: "+
          "{hashPower} hashes per second.");
         }
       }
   }
}

ProofOfWorkSample este metoda input pentru tot programul, ce folosește extension methods și celelalte metode explicate. Invocarea metodei în Main Console, produce rezultatul de mai sus.

La fiecare iterație, creștem (dublăm) dificultatea, ceea ce înseamnă că vom avea o țintă în descreștere continuă (prag), iar noi va trebui să calculăm un număr egal sau mai mic decât ținta pentru a câștiga competiția. De asemenea, afișăm timpul necesar pentru a găsi o soluție și numărul mediu de calcule efectuate pe secundă. Veți observa următoarele: cu cât este mai mic numărul țintă, cu atât mai mare va fi dificultatea, numărul de iterații (încercare-eroare) și timpul final necesar pentru a găsi o soluție.

Odată ce am găsit un număr și l-am publicat, începem imediat încercările pentru a calcula următorul număr pentru problema a cărei dificultate este în continuă creștere. Așa cum am explicat în articolul precedent, în lumea bitcoinului dificultatea este ajustată de toți cripto-minerii, pe baza dificultății medii din ultimele două săptămâni, astfel încât computerele să poată găsi o soluție, în medie la fiecare zece minute.

LANSAREA NUMĂRULUI 74, CLUJ

Prezentări articole și
Panel: Autonomous driving

Miercuri, 22 August, ora 18:00
sediul Bosch, str. Someșului 14

Înregistrează-te

Facebook Meetup

Sponsori

  • kronsoft
  • ntt data
  • 3PillarGlobal
  • Betfair
  • Telenav
  • Accenture
  • Siemens
  • Bosch
  • FlowTraders
  • Crossover
  • MHP
  • BCR
  • Itiviti
  • Connatix
  • MicroFocus
  • Colors in projects