Arxius

Archive for the ‘Matemàtica’ Category

Number base conversion from 64 to 58

If you are only looking for an example, you can find one here in my GitHub.

It would seem that a number base conversion is easy. And it is unless you deal with very large numbers. In this case, the problem gets worse. Here I explain how I developed an efficient base change algorithm that will take simple execution requisites for large number conversions.

As this nice page explains, the simplest way to convert base number is this algorithm:

// M = input number, N = output base,
result = “”
if M < N, result = ‘M’ + result. Stop.
S = M mod N, result = ‘S’ + result
M = M/N
goto 2

For example, if we try to convert 100 from base 10 to base 16, we should follow these steps:

M = 100, N = 16
100 < 16 ?
S = 4, result = ‘4’
M = 100/16 = 6
6 < 16 ?
result = ’64’

And therefore, we’ll get that 100 is equal 64 in base 16.

However, this algorithm involves working with the whole input number in math operations (such as division and modulus). If you tried to convert a long number (let’s suppose a long number has more than 30 digits), it would be needed a very long numeric data type for this operations. For instance, to allow a 60 hexadecimal digit number, we would need a 240-bit (30 bytes) data type number, which does not exist in most languages (usually the largest types are long and double-precision, with 64 bit).

So, I tried to find out a different way to manage a base conversion, where it would be possible to slice the number and work with their parts independently. It came to me that there must be an easier way to shift a number by only 1 base. And actually there is.

Let’s try to explain it with a simple example. Imagine you want to convert a 2 digit number from base 16 to base 15, for instance, the number “43 hex”. The second digit of this number (4) means that in fact, we have added 4*16 times the 1 value. If we try to allocate the same value in a 15 base number, we could find easily that: (4*16) = 4 * (4*15), so the second digit remains as “4”, but we must add the same second digit value to the first digit value (4+3). Finally, we get that “43” base 16 = “47” base 15. Notice that we did this conversion only with a simple and independent digit sum.

Well, to be fair let’s see the worst case in this conversion example. Let’s try to convert in the same way the number “FF hex” to 15 base. If we apply the same rule, by decoding the number as “FF = (F * 16) + F = (F * 15) + F + F”, we’ll have an overflow at the first digit (F + F = 1E), so we must add (carry) this “1” spent value to the second digit. And then, the second digit “F + 1” will also have another overflow, and will also take another carry value to the next digit. So finally we’ll get that “FF hex” equals to “1FE” in base 15. In fact, the method is the same, though we must pay attention to the carry values.

Now let’s try to convert a 4 digit number “5A78 hex”. In order to introduce yourself to my algorithm’s notation, I’m going to write this number as an integer array: “5A78 hex” = [5,10,7,8]. If we try to apply the same method, we’ll find that “[5,10,7,8] = (5 * 16³) + (10 * 16²) + (7 * 16) + 8”. By decoding every part independently, we’ll get:

(8 * 16⁰) = (8 * 15⁰) = [0,0,0,8]
(7 * 16¹) = (7 * 15) + 7 = [0,0,7,7]
(10 * 16²) = (10 * 15²) + (10 * 2 * 15) + 10 = [0,10,(10*2),10]
(5 * 16³) = (5 * 15³) + (5 * 3 * 15²) + (5 * 3 * 15) + 5 = [5,(5*3),(5*3),5]

It means that, for shifting each digit, we must add the following values:

5 10 7 8  
      8 the first digit needn’t be shifted
    7 7 to shift the second digit
  10 20 10 to shift the third digit
5 15 15 5 to shift the fourth digit
5 25 42 30 without carrying the overflows
6 12 14 0  

And thereafter, without missing the overflow carries, we’ll get the result = [6,12,14,0].
Notice that the same matrix would work for any other 4 digit conversion since we express the accumulators (the numbers we must add to shift the digits) as a multipliers of the original digits:

d c b a
      a
    b b
  c 2c c
d 3d 3d d

So, by following this method we can increase this matrix in size to the needed digits, and then apply simple sums for each digit. For instance, the 8 digit conversion matrix  is equal to:

h g f e d c b a
              a
            b b
          c 2c c
        d 3d 3d d
      e 4e 6e 4e e
    f 5f 10f 10f 5f f
  g 6g 15g 20g 15g 6g g
h 7h 21h 35h 35h 21h 7h h

We can also apply this to convert, for example, the number “39485A78 hex”. We only must apply this fix multiplier matrix:

              1
            1 1
          1 2 1
        1 3 3 1
      1 4 6 4 1
    1 5 10 10 5 1
  1 6 15 20 15 6 1
1 7 21 35 35 21 7 1

To the specific values:

  3 9 4 8 5 10 7 8
8               8
7             7 7
10           10 20 10
5         5 15 15 5
8       8 32 48 32 8
4     4 20 40 40 20 4
9   9 54 135 180 135 54 9
3 3 21 63 105 105 63 21 3
  3 30 121 268 362 311 169 54
  5 9 5 8 8 7 7 9

Once here, you should have noticed that the next goal should be to set a method for building any size multipliers matrix. Indeed, as you may have graphically seen, there’s an easier way to build the matrix without decoding each digit into a mathematical expression. Instead, we can iterate each digit and get the next multiplier value by adding the multiplier value at its previous position (at its right position in the grid). It would be something like:

 

gapi

We could easily get this with the following double loop:

var buffer_mult = [1,0,0,0,0,.....]; // First multiplier must be set as 1
for (var cdig = 0; cdig < buffer_mult.length; cdig++) {
    for (var t = cdig; t > 0; t--) buffer_mult[t] += (buffer_mult[t - 1] || 0);
}

This method always works for every number.

However, in the same way as the matrix grows, we’ll get higher multiplier values. We can reach several millions at a 30 digit conversion though there’s an optimization to avoid this lack. Shifting the multiplier values up, with a modulus and carry values at the conversion base, we could manage to avoid big numbers getting the same result.

For instance, in the last example we can optimize the seventh interation by shifting up the values over 15:

  1 6 15 20 15 6 1
    +1 +1 +1      
  1 7 1 6 0 6 1
1 8 8 7 6 6 7 1

and get the same result with fewer multiplier values.

.

Practical case: Convert from hexadecimal to 58 base

.

A practical case of this method could be used to convert from base 64 to base 58. It is usual to need number conversion to base 58 when you’re dealing with bitcoin addresses, URL shorteners and others. Therefore, it is nice to have a good way to do it.

I did it by applying this method with good results. I applied 6 times the algorithm, shifting from base 64 to base 58. I had good results with some 80 digit hexadecimal numbers. Fast executions, with less than 50.000 iterations, and maximum variable’s values under 200.000.

If you’d like to check it out, you can find this example developed in a simple html/javascript page just here in my GitHub repository, or try it working here.

gapi.png

Or if you are not still satisfied, here’s another page where you can find another ways to get the same.

 

 

 

 

Anuncis

La loteria : com destruir l’entropia de la riquesa

22/12/2011 4 comentaris

Avui 22 de desembre del 2011, a la nostre mediocre i fútil actualitat han succeït 2 esdeveniments importants a destacar.

El primer és el solstici d’hivern, aquesta fita cronològica que a tants ens agrada celebrar, fent referència a l’analogia de la mort del sol per tornar a néixer d’aquí 3 dies (l’any passat ja en varem parlar).

El segon esdeveniment, sobre el que avui m’agradaria parlar, és la loteria. Els meus companys més propers ja coneixen la meva radical opinió sobre tema, per la qual he rebut sempre duríssimes crítiques i m’he convertit en un referent de l’escepticisme i la falta de fe en la il·lusió. Val a dir que la loteria de nadal es desvia una mica de la convencionalitat del joc en general, però crec que tot i això avui és el dia perfecte per estendre la meva opinió i aprofitar per explicar-la en un post, que encantat de la vida m’agradaria compartir aquí al bloc.

Tal com s’ha utilitzat sempre per vendre’ns en el comercial, la loteria representa un sentiment  d’il·lusió i esperança a poder fer realitat els somnis materials de les persones. L’únic preu per aconseguir-ho és una petita aportació, i molta sort. Magnífic ! Ni el millor publicista podria resistir rendir-se als peus de tan esplèndid “ganxo comercial”, qual promesa de fer-nos creure que serem els afortunats desvia perfectament l’atenció a la trampa del negoci, amb un excel·lent exercici d’ignorància estadística. O com a mode resumit es pot dir, citant una gran veritat : la loteria no és més que un impost voluntari per aquells que no saben matemàtiques.

Perquè sóc tant pessimista ? I si m’equivoco ? i si realment em toca la grossa ? Quantes fal·làcies juntes he arribat a escoltar en justificació a la falta de comprensió sobre l’atzar…

Guanyar la loteria és difícil. Molt difícil. Extremadament difícil ! De fet, ho és tant, que la majoria de persones són incapaces d’entendre la magnitud de tal improbabilitat. En les moltes discussions que he tingut al respecte, sempre m’ha agradat molt fer referència a una comparativa que fa Nassim Taleb al seu llibre “¿ Existe la Suerte ?” (molt interessant per cert), en la que afirma que és més probable que avui et caigui un llamp a sobre, que que et toqui un primer premi de loteria alguna vegada a la vida. Sembla difícil creure-ho, però realment és així, els números no enganyen i la probabilitat és una ciència exacte. Per exemple, amb un simple càlcul, podem veure que les probabilitats de les principals loteries són :

Joc Primer premi Probabilitat
Euro millones 1 de 76.275.360 0.0000000131
La primitiva 1 de 13.983.816 0.0000000715
La Once 1 de 15.000.000 0.0000000667
La 6/49 1 de 13.983.816 0.0000000715

o dit d’un altre manera més entenedora, podríem estar durant 268.920 anys jugant cada setmana a la primitiva per assegurar-nos que estadísticament ens toqués, i tot i així, podria ser que mai passés.

Com ja he dit, la loteria de nadal es desvia una mica d’aquesta tendència i contempla una esperança matemàtica més alta, amb el que és més probable guanyar alguna cosa, un dels motius del perquè possiblement gaudeix d’una millor acceptació mediàtica (tot i existir una clara tendència al canvi), però això no és cap excusa, segueix contenint la mateixa essència de l’engany.

El que m’indigna realment d’aquesta pràctica però, no és veure com els il·lusos perden ingènuament els seus diners, sinó l’efecte holístic que això provoca en el conjunt de la societat. De la mateixa manera que per molt que intentem evitar-ho la política, l’economia i el  desenvolupament ens afecten a tots (encara que sigui de forma indirecta), el fet d’acumular riquesa en mans de pocs, també ens afecta, independentment de si juguem o no a la loteria. La riquesa, tot i la variabilitat del mercat, és un valor constant, i el fet de que algú sigui més ric ens suposa directament que nosaltres som més pobres, encara que simplement seguim tenint els mateixos diners. Per això sempre he considerat que la loteria és el màxim exponent d’un repartiment irresponsable de la riquesa, ja que consisteix en assignar-la de forma aleatòria, sense tenir en compte si el qui obté el premi realment ho mereix.

Sóc conscient de que no vivim en un món perfecte, i que actualment sense tenir en compte la loteria la riquesa també es reparteix de forma injusta. Però considero que l’aprovació per part d’una majoria tant àmplia a aquest joc pervers és directament un insult a l’apologia que tants reclamen sobre la causa comú, a la bona voluntat de les persones humils, i a l’esperança d’evolucionar cap a una societat més justa. Tots volem ser rics, ser més i tenir més que els altres, aquest és un sentiment d’ambició que per defecte es troba intrínsec en la nostre naturalesa humana, i no el podem evitar. De fet, no cal veure-ho com un fenomen negatiu, tot el contrari, aporta un valor afegit al conjunt, una forma de justa competència que ens fa avançar i millorar com a societat. En definitiva, és bo despertar l’ambició de voler superar-nos constantment. La loteria però, és la forma en que s’incentiva exactament tot el contrari. Un discurs que xoca directament contra la cultura del valor del esforç, on la riquesa es reparteix d’una forma tant absurda que desprestigia totalment la recompensa a obtenir per una feina ben feta, desmotivant i aconsellant a ni tant sols intentar-ho : per què m’haig d’esforçar a treballar durament tota la meva vida, si potser invertint un sol euro puc guanyar més del que a mai he aspirat ?

I és en definitiva aquesta filosofia tant negativa el que hi ha darrera de la loteria (o jocs d’atzar pur), motiu pel que sempre he tingut una opinió tant radical al respecte, doncs en última instància la meva voluntat no és ser un “aguafiestas” (o aixafaguitarres), tot el contrari, a banda del que tothom pensa quan els recomano no jugar, l’objectiu és ser positiu, i evitar tant la desil·lusió, com aquest sentiment tant hipòcrita en que es basa el fet de pensar que obtenir diners sense cap esforç és legítim.

Com a última pinzellada a favor de la meva justificació, dir també que l’última cosa que necessita la complicadíssima trama econòmica en que es desenvolupa la nostre actualitat, és la encara més accentuada concentració de la riquesa. Existeix una clara tendència a destruir el factor d’entropia a nivell econòmic, cosa a que la loteria no fa més que col·laborar : cada com hi ha menys rics més rics, i més pobres més pobres. Això no és bo, ni tant sols pels mateixos rics, ja que com la història ens ha ensenyat, aquesta tendència sempre deriva en un cataclisme de dimensions bíbliques (tal com va ser la segona guerra mundial), i no cal ser cap il·luminat per assegurar que en la delicada situació actual, posar més llenya al foc no és una bona idea…

així que ja ho sabeu, seguiu jugant a l’atzar !

 

Alguns enllaços força interessants al respecte :

http://www.estadisticaparatodos.es/taller/loterias/loterias.html

http://www.uv.es/~montes/mat_omni/uimp.pdf

http://www.microsiervos.com/archivo/azar/inversiones-azar.html

Sistema de votació electrònic amb garantia d’autenticació i anonimat

28/10/2011 2 comentaris

Ahir a la nit, mentre donava voltes al llit sense poder dormir, vaig estar rumiant sobre un problema que ja fa temps que em balla pel cap : Com s’hauria de dissenyar un sistema de votació electrònic amb garantia d’autenticació i anonimat ?

Perquè ens entenguem, la idea és intentar traslladar el, per exemple, tradicional sistema presencial de votació de les eleccions generals del proper 20N, a un sistema amb les mateixes prestacions que funcioni íntegrament per suport electrònic (a Internet, per exemple). A primer cop d’ull sembla una idea poc útil, però de ben segur que els milers de persones que han estat convocades (per obligació) alguna vegada a les taules dels col·legis electorals durant els comicis, sabran apreciar els avantatges d’utilitzar un mètode no presencial.

Analitzant el problema, ràpidament s’observa que les principals condicions que requereix el sistema són l’autenticació i l’anonimat.

És a dir, cal que l’entitat que s’encarrega de centralitzar i fer el recompte dels vots pugui cerciorar de forma inequívoca que cadascun d’aquests vots prové d’un elector vàlid, alhora que també cal conservar l’anonimat de l’elector, és a dir, no s’ha de poder conèixer de cap manera quina ha estat l’elecció del seu vot. Aquests requisits que semblen tant simples, com es pot comprovar si s’hi reflexiona una mica, son totalment contraproduents, de manera que aconseguir dissenyar un sistema que compleixi les dues condicions, lluny de ser trivial, començo a tenir dubtes de si realment és possible.

Així doncs, el disseny d’un sistema de tals característiques ja ha començat a transcendir de les meves inquietuds nocturnes, i de fet avui s’ha convertit en tema de debat durant l’hora d’esmorzar, juntament amb un bon company molt especialitzat en el tema, i amb el que, tot i plantejar esquemes força interessants, hem estat incapaços d’arribar a una solució factible. És per això que m’agradaria fer-ne encara més ressò, per veure si realment algú és capaç d’arribar a alguna bona conclusió.

Sobre el plantejament, i entrant ja en l’anàlisi estrictament del problema, cal dir que la garantia que dona el fet de realitzar les eleccions de forma presencial, a mètode d’urna amb un sobre tancat per cada vot, i un interventor independent responsabilitzant-se i verificant la identitat de cada votant, tot i ser una manera àmpliament consensuada d’aconseguir l’anonimat i l’autenticació, tampoc és fiable al 100%, ja que l’autenticació pot ser falsejada, al mateix temps que l’anonimat pot tenir un percentatge baix d’entropia quan es divideix el total  del cens en moltes urnes (com menys vots per urna, més fàcilment es pot elaborar una estimació estadística de quin ha estat el vot de cada elector). Per exemple, si en un municipi només hi ha censades 2 persones, tot i entregar el vot en un sobre tancat de forma anònima, es pot estimar en un mínim d’un 50% l’elecció de cada participant, o encara més, si els 2 resultats són els mateixos, sabrem del cert al 100% què ha votat cadascú. Així doncs, aconseguir l’anonimat en el sistema de votació no és tant senzill com sembla, doncs inclús els utilitzats actualment de forma oficial tenen els seus defectes, que depenen directament de la quantitat de resultats diferents que es comptabilitzen, i de la segmentació amb que es fa l’escrutini, per la qual cosa sempre s’ha de tenir en compte que l’anonimat al 100% és impossible d’aconseguir, i tant sols se’n podrà garantir un llindar percentualment acceptable.

Son però, aquests petits i despreciables defectes, els que a l’hora de traslladar el problema al món electrònic impossibiliten un mètode fàcil i fiable d’implementació. El problema de l’autenticació és fàcilment resoluble amb una firma digital, assignant a cada elector una paritat de claus asíncrones. De fet, i des de fa molt de temps, existeixen múltiples solucions que ja ho implementen de diverses maneres (l’anomenat vot electrònic), a més de ser un tema que actualment està sobre la taula de molts debats polítics a arrel de les recents crítiques al sistema “democràtic” amb que s’escull l’actual representació de l’organisme executiu i legislatiu, com pot posar de manifest amb un clar exemple la proposta de Democràcia 4.o.

El problema però, recau a l’hora de voler introduir en aquest mateix sistema la garantia de l’anonimat, tal com evidencia el fet de que cap d’aquests sistemes existents ofereixi tal característica. Podem pensar que xifrant i firmant el nostre vot es pot conservar l’anonimat vers els demés electors, però al moment d’enviar al centre autoritzador la teva firma juntament amb la teva elecció de vot, queda en mans d’aquest garantir que aquesta vinculació es trencarà, i que ningú coneixerà quin ha estat el teu vot. Així doncs, penso que fer recaure la confiança de l’anonimat en un tercer no és garantia pel sistema, doncs la bona voluntat mai hauria de ser un factor, ja que aporta un grau indeterminista al problema, i impossibilita la seva resolució.

Buscant l’analogia en el sistema presencial, es pot traslladar la idea de llançar varis sobres tancats dins d’una urna i barrejar-los, un cop autenticada la validesa de cadascun d’aquests vots, trencant així la vinculació entre elector vàlid i vot. Implementar aquest concepte dins d’un entorn digital però és força complicat, doncs es requereix d’una operació que aporti un factor d’atzar, que a més, pugui ser garantit per a tots els participants. Aquí és on es troba la principal qüestió del problema, i on hem divergit en les possibles solucions.

Jo particularment, la solució més viable que fins ara he trobat, tot i que no m’agrada per la seva alta complexitat, consisteix en un sistema on s’implementa un recorregut del missatge que representa el conjunt de tots els vots (cadascun xifrat), de manera que circuli per tots els electors, els quals, un per un, reordenen el missatge per generar una assignació on, cadascú coneix quina és la seva posició (on ubicarà el seu vot), però li és impossible saber a qui li corresponen les demés posicions on la resta ubicarà el seu vot. El fet de que cada elector del sistema faci una reordenació aleatòria, garanteix que realment es trenca la vinculació entre elector i elecció, doncs per tornar reconstruir l’ordenació inicial és imprescindible saber totes (sense excepció) les reordenacions que s’han fet, de manera que des del punt de vista d’un elector, no publicar quina ha estat la seva reordenació li atorga la garantia de que el seu vot serà realment anònim. Caldria detallar una mica millor la idea (que de moment està en forma d’esborrany sobre el tinter), però de moment penso que aquesta hauria de ser la direcció a prendre per trobar la solució més correcte. No cal dir però, que de ben segur que deuen existir altres mètodes que no he tingut en compte, de manera que deixo el debat obert a noves idees o propostes.

Lluny de semblar doncs un problema particular en l’àmbit acadèmic, crec que dissenyar solucions a aquest tipus de plantejaments aporta un valor més que tangible en la nostra societat, demostrant la interrelació que hi pot haver en disciplines tant distants com poden ser la política i la matemàtica, i deixant en evidència que a vegades, aquelles coses a que menys importància ens reflecteixen, acaben sent les que realment aconsegueixen canviar el món.

Afegir com a últim repunt en forma de complement, la idea relacionada que sempre he manifestat sobre la validació / publicació de l’elecció de vot. Crec que un sistema que vulgui ostentar un mínim de garanties de ser fidedigne (no corruptible), hauria de poder incorporar de facto la possibilitat de que cada elector pogués comprovar que el seu vot realment s’ha comptabilitzat allà on ell ha indicat. De fet, qualsevol analista a qui se li plantegés el problema consideraria intrínseca aquesta mesura en la solució. No obstant, no cal ser cap geni per donar-se compte que els actuals sistemes que tanta acreditació popular se’ls confia no implementen tal característica, atorgant a mans d’una minoria la bona voluntat de que el sistema realment sigui fiable… A vegades és atònit comprovar la bona fe amb que la gent acredita el seu futur a altres desconeguts. En definitiva, i sense voler encetar un nou debat paral·lel (ho reservo per un nou post), crec que és remarcable aquesta qüestió que per tants sol ser d’irrellevant importància a l’hora d’analitzar aquest tipus de sistemes. Inclús aprofundint fins al final sobre el tema de l’anonimat, i essent conscient de que existeixen formules per garantir la prestació de validació del vot conservant l’anonimat, crec que la millor solució, tot i ser conscient de que això pot comportar coacció, és el vot públic. Si alguna cosa m’ha ensenyat la criptografia, és que el sistema més segur i fiable no és aquell que ningú coneix, sinó aquell que tothom coneix.

Dit això, la meva proposta de procediment per aconseguir resoldre el problema és :

Donats N usuaris que realitzen una votació amb R resultats. Cada usuari disposa d’un par de claus pública/privada (U[N].pub / U[N].pri).
Existeix un “Centre autorizador” (CA) que acredita que els usuaris són vàlids, a l’hora que els comunica entre ells.
El CA també disposa d’un par de claus pública/privada (CA.pub / CA.pri).
El procediment a seguir és :
1. Tots els usuaris escullen un vot fals aleatori qualsevol, el seu vot autèntic, i dos identificadors aleatòris (Id.pri1, Id1.pri2). Cadascu xifra (amb CA.pub) el vot fals juntament amb el Id.pri1, i el voto autèntic amb el Id.pri2, obtenint un vot xifrat fals (vf) i un vot xifrat autèntic (va).
2. El CA selecciona un usuari al atzar per començar la votació (U1).
3. U1 escull un altre identificador aleatòri (Id1.pub1) i l’afageix a vf1 (m1 = vf1+Id1.pub1). Ho xifra amb la clau pública del següent usuari (U2), ho firma, i li envia al següent usuari a través del CA.
4. U2 rep el missatge de U1 i el desxifra (obtenint Id1.pub1 i vf1). Escull un altre identificador aleatorio (Id2.pub1), diferent a Id1.pub1, i l’afegeix a vf2 (m2=vf2+Id2.pub1). U2 uneix m1 y m2 (en qualsevol ordre), ho xifra amb la clau pública del següent usuari, ho firma, i li envia al següent usuari a través del CA.
5. El següent usuari realitza la mateixa acció, afegint el seu vot.
6. L’últim usuari (UN), realitza la mateixa acció, i envia el missatge (ja amb tots els vots falsos), al primer usuari (U1).
7. U1 comprova que el seu vot fals xifrat (vf) segueix estant al missatge, juntament amb el identificador Id1.pub1. Substitueix el vot fals xifrat per el seu vot autèntic xifrat (va1), i li asigna un nou identificador aleatori (Id1.pub2), diferent a tots els identificadors Id.pub1 del missatge. Reordena tots els vots xifrats amb els seus identificadors, ho xifra, i li envia al següent usuari (U2).
8. U2 realitza la mateixa acció (substitueix el seu vot fals per l’autèntic, li asigna un nou identificador Id.pub2, ho reordena, i ho envia al següent usuari).
9. L’últim usuari (UN), realitza la mateixa acció, i li envia el resultat a CA.
10. CA rep tots els vots autèntics xifrats, juntament amb els seus Id.pub2. Els desxifra un per un, obtenint cada vot vinculat al seu Id.pri2 i Id.pub2.
11. CA Publica la llista. Cada usuari pot comprovar que el seu vot correspon al que ha realitzat mitjançant Id.pub2 i Id.pri2, sense ser capaç de distingir a quí pertany cadascun dels demés Id.pub2 / Id.pri2.

Amb un exemple pràctic :

4 usuaris (U1, U2, U3, U4) realitzen una votació amb 3 opcions (A, B, C) :

usr vot fals vot aut. Id.pri1 Id.pri2 Id.pub1 Id.pub2 VF VA m a
1 C A 33 5 21 39 [C33|CA.pub] [A05|CA.pub] VF01,21 VA01,39
2 B A 45 50 20 33 [B45|CA.pub] [A50|CA.pub] VF02,20 VA02,33
3 C C 33 39 59 9 [C33|CA.pub] [C39|CA.pub] VF03,59 VA03,09
4 A B 12 27 18 44 [A12|CA.pub] [B27|CA.pub] VF04,18 VA04,44

1. U1 escull Id1.pub1 (21), i genera m1 = VF01,21. Ho xifra amb U2.pub, i genera el missatge M1. Ho firma i li envia a CA perquè ho verifiqui i ho reenvii a U2 :

M1 [m1|U2.pub]

2. U2 escull Id2.pub1 (20), i genera m2 = VF02,20. Ho reordena aleatòriament amb m1, ho xifra amb U3.pub, i genera el missatge M2. Ho firma i li envia a CA perquè ho verifiqui i ho reenvii a U3 :

M2 [m2,m1|U3.pub]

3. U3 escull Id3.pub1 (59), i genera m3 = VF03,59. Ho reordena aleatòriament amb m1 i m2, ho xifra amb U4.pub, i genera el missatge M3. Ho firma i li envia a CA perquè ho verifiqui i ho reenvii a U4 :

M3 [m2,m3,m1|U4.pub]

4. U4 escull Id4.pub1 (18), i genera m4 = VF04,18. Ho reordena aleatòriament amb m1, m2 i m3, ho xifra amb U1.pub, i genera el missatge M4. Ho firma i li envia a CA perquè ho verifiqui i ho reenvii a U1 :

M4 [m2,m4,m1,m3|U1.pub]

5. U1 verifica que m1 segueixi al missatge, escull Id1.pub2 (39), genera a1 = VA01,39, i ho substitueix per m1 dins del missatge. Ho reordena aleatòriament amb m2, m3 i m4, ho xifra amb U2.pub, i genera el missatge A1. Ho firma i li envia a CA perquè ho verifiqui i ho reenvii a U2 :

A1 [m4,a1,m3,m2|U2.pub]

6. U2 verifica que m2 segueixi al missatge, escull Id2.pub2 (33), genera a2 = VA02,33, i ho substitueix per m2 dins del missatge. Ho reordena aleatòriament amb a1, m3 i m4, ho xifra amb U3.pub, i genera el missatge A2. Ho firma i li envia a CA perquè ho verifiqui i ho reenvii a U3 :

A2 [m3,a1,m4,a2|U3.pub]

7. U3 verifica que m3 segueixi al missatge, escull Id3.pub2 (09), genera a3 = VA03,09, i ho substitueix per m3 dins del missatge. Ho reordena aleatòriament amb a1, a2 i m4, ho xifra amb U4.pub, i genera el missatge A3. Ho firma i li envia a CA perquè ho verifiqui i ho reenvii a U4 :

A3 [a2,m4,a3,a1|U4.pub]

8. U4 verifica que m4 segueixi al missatge, escull Id4.pub2 (44), genera a4 = VA04,44, i ho substitueix per m4 dins del missatge. Ho reordena aleatòriament amb a1, a2 i a3, ho xifra amb CA.pub, i genera el missatge A4. Ho firma i li envia a CA.

A4 [a1,a3,a4,a2|U1.pub]

9. CA rep el missatge, el dexifra, sencer, i a continuació dexifra cadascun dels vots. Publica la següent llista :

Id.pri2 Id.pub2 vot aut.
5 39 A
50 33 A
39 9 C
27 44 B

És necessari donar dues voltes completes per assegurar que tots els usuaris poden barrejar tots els vots xifrats, impedint així que el següent usuari de la cadena pugui identificar quin és el seu vot (encara que estigui xifrat).

Enfilant el camí

Visualitzant el present per construir el futur

El Noguer

Visualitzant el present per construir el futur

Visualitzant el present per construir el futur