[ Literatura ] [ Go ] [ Cibercultura ] [ Informàtica i ciència ] [ Col·labora ] [ Sobre Hak Nam ] [ Contacte ]

Hak Nam

L'algoritme d'encriptació "Solitaire"

Versió 1.2, 26/05/99

Dissenyat per Bruce Schneier
Aparegut en el Criptonomicón de Neal Stephenson

vectors de prova - Perl - Ada - C (#1) - C (#2) - C++ - Delphi - Forth (#1) - Forth (#2) - Java - Javascript - K - Palm OS - Pascal - Perl CGI - Python (#1) - Python (#2) - TCL
Nota: tan sols la implementació Perl ha estat provada per Coutnerpane.

Aquesta pàgina és una traducció de l'original en anglès de Bruce Schneier, que ha estat traduïda a l'alemany per Nils Plaumann, al francès per Fernandes Gilbert i al castellà per Jesús Cea Avión. La present traducció al català és de l'Arnau Fuentes.

A la novel·la de Neal Stephenson, Cryptonomicon, el personatge Enoch Root descriu un criptosistema amb el nom en codi "Pontifex" a un altre personatge anomenat Randy Waterhouse, i després revela que els passos de l'algoritme s'intenten dur a terme fent servir una baralla de cartes de joc. Aquests dos personatges continuen intercanviant múltiples missatges encriptats amb aquest sistema. El sistema es diu "Solitari" (a la novel.la, "Pontifex" es un nom en codi que pretén dissimular el fet que utilitza una baralla de cartes) i jo l'he dissenyat per a permetre als agents de camp comunicar-se d'una manera segura sense haver de dependre de l'electrònica o haver de dur eines incriminatòries. Un agent pot ser a una situació on no té accés a un ordinador, o pot ser demandat si té eines per a comunicacions secretes. Però una baralla de cartes...quin mal pot fer?

Solitari aconsegueix la seva seguretat de l'aleatorietat inherent en una baralla de cartes ben barrejada. Mitjançant la manipulació de la baralla, el comunicant pot crear una cadena de lletres aleatòria que llavors combina amb el missatge. Per suposat que Solitari pot ser simulat en un ordinador, pero s'ha dissenyat per a ser implementat a mà.

Solitari pot semblar de baixa tecnologia, pero la seva seguretat intenta ser d'alta tecnologia. Vaig dissenyar Solitari per a ser segur fins i tot contra els millors adversaris militars amb ordinadors potents i els criptoanalistes més intel·ligents. És clar, no hi ha garanties que algú no trobi un atac enginyós contra Solitari (mireu aquest espai per a actualitzacions), pero l'algoritme és certament millor que qualsevol xifrat en llapis i paper que hagi vist.

No és ràpid, però. Pot portar tot un vespre encriptar o desencriptar un missatge raonablement llarg. Al llibre d'en David Kahn Kahn on Codes descriu un xifrat real en llapís i paper usat per un espia soviètic. Tant l'algoritme soviètic com Solitari tarden més o menys el mateix temps en encriptar un missatge: gairebé tot el vespre.

Encriptant amb Solitari

Solitari és un xifrat stream en mode output-feedback. Alguns cops s'anomena generador de claus (KG en argot militar dels EUA). La idea bàsica és que Solitari genera una cadena de números, sovint anomenada keystream, entre 1 i 26. Per encriptar, genera una cadena igual de llarga que el text pla original. Llavors se sumen, mòdul 26, lletra a lletra al text original per a crear el text xifrat. Per a desencriptar, genera la mateixa cadena i resta, mòdul 26, del text xifrat per a recuperar el text original. (No us preocupeu, explicaré què vol dir mòdul 26 en un minut.

Per exemple, per a encriptar utilitzant Solitari el primer missatge mencionat a la novel·la de Stephenson, "DO NOT USE PC":

  1. Divideix el missatge de text pla en grups de cinc caràcters. (No hi ha res de màgic en els grups de cinc caràcters; només és tradició.) Utilitza X's per omplir l'últim grup. Així, si el missatge és "DO NOT USE PC", quedaria:

    DONOT USEPC

  2. Utilitza Solitari per a generar una cadena de deu lletres (Els detalls són més avall). Assumim que són:

    KDWUP ONOWT

  3. Converteix el missatge de text pla de lletres a numeros, A=1, B=2, etc:

    4 15 14 15 20   21 19 5 16 3

  4. Converteix la cadena de lletres de la mateixa forma:

    11 4 23 21 16   15 14 15 23 20

  5. Suma els números del text pla original i la cadena de números generada amb Solitari, mòdul 26. (El que això vol dir és que si la suma és superior a 26, has de restar 26 del resultat.) Per exemple, 1+1=2, 26+1=27, i 27-26=1, per tant 26+1=1.

    15 19 11 10 10   10 7 20 13 23

  6. Converteix els numeros a lletres.

    OSKJJ JGTMW

Si sou realment bons fent aixo, podeu aprendre a sumar mentalment les lletres, i simplement sumar les lletres dels passos 1 i 2. Només és qüestió de pràctica. És fàcil recordar que A+A=B; recordar que T+Q=K és més difícil.

Desencriptant amb Solitari

La idea bàsica és que el receptor genera la mateixa cadena, i llavors resta la cadena de lletres de les lletres del text xifrat.

  1. Agafa el text xifrat i divideix-lo en grups de cinc caràcters. (Ja hauria de estar així.)

    OSKJJ JGTMW

  2. Utilitza Solitari per a generar una cadena de deu lletres. Si el receptor fa servir la mateixa clau que l'emissor, la cadena de lletres" serà igual:

    KDWUP ONOWT

  3. Converteix el missatge xifrat de lletres a números:

    15 19 11 10 10   10 7 20 13 23

  4. Converteix la cadena de lletres de la mateixa manera:

    11 4 23 21 16   15 14 15 23 20

  5. Resta la cadena de números dels números del text xifrat, mòdul 26. Per exemple, 22-1=21, 1-22=5. (És facil. Si el primer número es menor o igual al segon, afegeix 26 al primer número abans de restar. Llavors 1-22=? es transforma en 27-22=5.)

    4 15 14 15 20   21 19 5 16 3

  6. Converteix els números en lletres.

    DONOT USEPC

Com pots veure, la desencriptació és igual que l'encriptació, excepte que restes el text xifrat menys la cadena.

Generant cadenes de lletres

Això és el cor de Solitari. Les descripcions anteriors d'encriptació i desencriptació funcionen per a qualsevol xifrat stream en mode output-feedback. És com funciona RC4. És com funciona el mode OFB per a DES. Aquesta secció és específica per a Solitari, i explica com Solitari genera les cadenes de lletres.

Solitari genera les seves cadenes usant una baralla de cartes. Podeu imaginar-vos una baralla de 54 cartes (recordeu els dos jokers) com una permutació de 54 elements. Hi ha 54!, o uns 2.31 x 1071, diferents ordres possibles de la baralla. Encara millor, hi ha 52 cartes a la baralla (sense els comodins), i 26 lletres a l'alfabet (a l'anglès). Aquest tipus de coincidència és massa bona com per deixar-la passar.

Per a poder utilitzar-la amb Solitari, la baralla ha de ser de 52 cartes i 2 jokers. Els jokers han de ser diferents d'alguna manera. (Això és bastant comú. La baralla que estic mirant ara mateix té estrelles als jokers: una té una estrella petita i l'altre en té una de grossa.) Anomeneu a un joker A i a l'altre B. Generalment, hi ha algun element gràfic que és igual però de diferent mida. Agafeu com a joker "B" aquell que sigui més gran. Podeu escriu-re unes lletres "A" i "B" ben grans, pero recordeu que haureu d'explicar-ho a la policia secreta si us agafen.

Per inicialitzar la baralla, agafeu-la cara amunt. Ara ordeneu les cartes en la configuració original que és la clau. (Parlaré de la clau més endavant, però és diferent a la cadena.) Ara ja esteu llestos per a fer una cadena de lletres.

Aquí es veu com generar un sol caràcter. Això és Solitari:

  1. Trobeu el joker A. Moveu-lo una carta avall. (Això vol dir, intercanvieu-la amb la de sota.) Si el joker és l'última carta de la baralla, poseu-lo sota de la primera.
  2. Trobeu el joker B. Poseu-lo dues cartes per sota. Si el joker és l'última carta de la baralla, poseu-lo just a sota de la segona carta. Si el joker és la penúltima, poseu-lo sota la primera carta. (Bàsicament, penseu que la baralla és un bucle... aquesta es la idea.)

    És important fer aquests dos passos en ordre. És temptador tornar-se mandrós i moure els jokers tant bon punt es troben. És correcte, excepte si es troben molt a prop entre ells.

    Llavors, si la baralla apareixia així abans del primer pas:

    A 7 2 B 9 4 1

    després del segon pas hauria de quedar aixi:

    7 A 2 9 4 B 1

    I si la baralla estava aixi abans del pas 1:

    3 A B 8 9 6

    després del pas 2 hauria de veure's d'aquesta manera:

    3 A 8 B 9 6

    Si us queda algun dubte, recordeu moure primer el joker A abans del joker B. I sigueu curosos quan els dos jokers es trobin cap al final de la baralla. Si el joker es l'última carta, penseu com si fos la primera quan comenceu a comptar.

  3. Realitzeu un tall triple. Això vol dir que intercambieu les cartes de sobre el primer joker amb les cartes de sota el segon. Si la baralla quedava aixi:

    2 4 6 B 5 8 7 1 A 3 9

    llavors despres del triple tall hauria de quedar aixi:

    3 9 B 5 8 7 1 A 2 4 6

    "Primer" i "segon" jokers es refereixen a qualsevol joker que sigui més proper i més llunyà del principi de la baralla. Ignoreu les designacions "A" i "B" per a aquest pas.

    Recordeu que els jokers i les cartes entre ells no es mouen; són les altres cartes les que es mouen al voltant seu. És fàcil de fer. Si no hi haguessin cartes en alguna de les tres seccions (tant si els jokers fossin adjacents, o un és al capdamunt i l'altre a baix de tot), tracteu la secció com a buida i moveu-la igualment. Si la baralla estava aixi:

    B 5 8 7 1 A 3 9

    llavors després del tall triple quedaria aixi:

    3 9 B 5 8 7 1 A

    Una baralla que es veiés d'aquesta manera:

    B 5 8 7 1 A

    quedaria sense canvis després d'aquest pas.

  4. Ara feu un tall per comptar. Mireu l'ultima carta. Convertiu-la en un numero del 1 al 53. Feu servir l'ordre de bridge per als pals: trèbols, diamants, cors i piques". Si la carta és un trèbol, és del valor que mostri. Si la carta és un diamant, és el valor més 13. Si és un cor, és el valor més 26. Si és una pica, és el valor més 39. Cada joker val 53.) Compta el valor obtingut a partir de la primera carta. (Generalment jo compto des de l'1 al 13 una vegada i una altra si cal; és més fàcil que comptar números grans seqüencialment.) Talleu després d'aquesta carta, deixant l'última carta sota de tot. Si la baralla es veu així:

    7 ... cartes .. 4 5

    ... cartes ... 8 9

    i la novena carta era el 4, el tall resultaria en:

    5 ... cartes ... 8 7

    ... cartes ... 4 9

    La raó perquè l'última carta es deixa al seu lloc és per a poder tornar enrera. Això és important per a l'analisi matematic de la seguretat.

    Una baralla amb un joker com a última carta quedaria sense canvis en aquest pas.

    Assegureu-vos de no invertir l'ordre quan compteu. La manera correcta de comptar és passant les cartes, d'una a una, d'una mà a l'altra. No feu piles a la taula.

  5. Busca la carta de sortida. Per a fer això, mira la primera carta. Converteix-la en un número de l'1 al 53 de la mateixa manera que al pas 4. Compta el valor que resulti. (Compta la primera carta com la número 1.) Apunta la carta que hi hagi després de l'última que comptis; no la treguis de la baralla. (Si surt un joker, no apuntis res i torna a començar des del primer pas.) Aquesta és la primera carta de sortida. Aquest pas no modifica l'estat de la baralla.
  6. Converteix la carta de sortida en un número. Com abans, utilitzeu l'ordre del bridge. De la més baixa fins la més alta, tenim trèbols, diamants, cors i piques. Per tant, de l'As al Rei de trèbols és de 1 a 13, de l'As al Rei de diamants és de 14 a 26, de l'As al Rei de cors és de 1 a 13, i de l'As al Rei de piques és de 14 a 26. (Necessitem comptar des de l'1 al 26, i no de 1 fins a 52, així podem passar-ho a lletres.)

Així és com es fa servir Solitari per encriptar un sol caràcter. Podeu fer-lo servir per a crear tantes cadenes com necessiteu; nomes heu de seguir els passos 1 a 6 per cada caràcter. (No barrejeu la baralla.) I recordeu, en necessiteu un per caràcter.

Sé que hi ha diferencies entre baralles, depenent del país. En general, no importa la forma en què les ordeneu, o com convertiu les cartes a números. El que realment importa és que tant l'emissor com el receptor es posin d'acord amb les regles. Si no ho feu, no podreu comunicar-vos.

Posant una clau a la baralla

Abans que comenceu a crear cartes de sortida, heu d'introduïr una clau a la baralla. Això és probablement el mes important de tota l'operació, i en la que es basa tota la seguretat del sistema. Solitari és tan segur com ho sigui la seva clau. Això vol dir que la forma més fàcil de trencar Solitari és esbrinar quina clau fan servir els comunicants. Si no teniu una bona clau, tota la resta no te cap importància. Aquí teniu algunes suggerències per intercanviar la clau.

  1. Useu baralles mesclades de la mateixa forma. Una clau aleatòria es la millor. Un dels comunicants pot barrejar una baralla i després crear-ne una d'idèntica. Una la fara servir l'emissor i l'altra el receptor. La majoría de la gent no és bona barrejant cartes, per això barregeu al menys sis cops. Ambdues parts haurien de tenir una baralla addicional en el mateix ordre, en cas que hi hagués algun error mai es podria desxifrar el missatge. També recordeu que la clau és en perill mentre existeixi; la policia secreta podria trobar la baralla i copiar el seu ordre.
  2. Feu servir un ordre del Bridge. Qualsevol descripció d'una mà de Bridge que pugueu trobar a un diari o algun llibre és una clau d'aproximadament 95 bits. Acordeu una forma de convertir el diagrama de Bridge i convertir-lo en l'ordre de la baralla. Després poseu-vos d'acord en una forma d'introduir els jokers dins la baralla. (Una forma òbvia es introduir el joker A després de la primera carta mencionada al text, i el joker B després de la segona carta mencionada.)

    Advertència: la policia secreta podria trobar la vostra columna de Bridge i copiar l'ordre. Podeu provar de seguir alguna mena de convenció per decidir quina columna de Bridge feu servir; per exemple, "fes servir la columna del diari de la teva ciutat natal corresponent al dia en que es va xifrar el missatge", o quelcom semblant. O useu una llista de paraules clau al lloc web del New York Times, i feu servir la columna de Bridge del dia de l'article que aparegui quan feu la cerca amb aquestes paraules. Si les paraules son interceptades, semblaran una mena de contrasenya. I escolliu la vostra pròpia convenció per a convertir les columnes de Bridge en ordres de baralles; recordeu que la policia secreta també llegeix els llibres den Neal Stephenson.

  3. Utilitzeu una paraula de pas per ordenar la baralla. Aquest mètode fa servir l'algoritme de Solitari per a crear un ordre inicial de la baralla. Emissor i receptor comparteixen una paraula de pas. (Per exemple "CLAU SECRETA".) Comenceu amb la baralla en un ordre fixe; de la carta mes baixa a la mes alta, en pals de Bridge, i seguits amb el joker A en primer lloc i després el B. Comenceu l'operació de Solitari, però enlloc del pas 5, feu un altre tall basat en el primer caràcter de la paraula clau (3 en aquest exemple). Dit d'una altra manera, repetiu el pas 4, fent servir 3 com el numero per tallar en lloc de l'ultima carta. Recordeu posar les cartes de dalt just a sota de l'ultima carta, com abans.

Repetiu els cinc passos de l'algoritme de Solitari per cada caràcter de la clau. Això vol dir, el segon com que realitzem Solitari agafeu el segon caràcter de la clau, el tercer cop agafeu el tercer caràcter, etc.

Pas opcional: (Aquest NO s'utilitza en els exemples següents.) Feu servir els dos últims caràcters per a decidir les posicions dels jokers. Si l'ultima lletra es una G (un 7), poseu el joker A després de la setena carta. Si la lletra es una T (un 20), poseu el joker B després de la vintena carta.

Recordeu, no obstant, que nomes hi ha una aleatorietat d'1.4 bits per caràcter en Angles estàndard.[En català es semblant N.del T.]Necessitaríeu una paraula de pas de 64 caràcters per a que sigui segura.; Recomano 80 caràcters com a mínim, per si de cas. Ho sento; no es pot aconseguir una bona seguretat amb una clau mes curta.

Exemples

Aquí teniu alguns exemples per a practicar les vostres habilitats amb Solitari:

Seguretat Real, No Seguretat Basada En Obscurantisme

Solitari esta dissenyat per a ser segur fins i tot si l'enemic sap com funciona l'algoritme. Assumeixo que "Cryptonomicon" serà un èxit de vendes, i que sen podran trobar copies a qualsevol lloc. Assumeixo que la NSA i tothom estudiara l'algoritme i que el buscaran. Assumeixo que l'únic secret es la clau.

Per això és tant important mantenir la clau en secret. Si teniu una baralla de cartes en un lloc segur, hauríeu d'assumir que l'enemic pot pensar que esteu utilitzant Solitari. Si teniu una columna de Bridge a una caixa de seguretat, hauríeu d'esperar que s'aixequessin algunes celles. Si és sabut que algun grup fa servir l'algoritme, també és d'esperar que la policia mantingui una base de dades de columnes de Bridge per a fer-les servir com atac. Solitari és un sistema fort encara que l'enemic sàpiga que l'esteu utilitzant, i una simple baralla de cartes és molt menys incriminatòria que qualsevol programari d'encriptació que funcioni al vostre portàtil.

Notes Operacionals

  1. La primera regla d'un xifrat de cadena en mode 'output-feedback', qualsevol d'ells, és que mai hauríeu de fer servir la mateixa clau per a encriptar dos missatges diferents. Repetiu amb mi: MAI FEU SERVIR LA MATEIXA CLAU PER ENCRIPTAR DOS MISSATGES DIFERENTS. Si ho feu, esteu trencant completament la seguretat del sistema. Aquí teniu el perquè: si teniu dos textos xifrats, A+K i B+K, i traieu un de l'altre, tenim (A+K)-(B+K) = A+K-B-K = A-B. Això son dos textos plans sense xifrar combinats l'un amb l'altre sense cap clau involucrada, i és molt fàcil de trencar. Feu-me cas: pot ser que no sigueu capaços de recuperar A i B de A-B, però un criptoanalista professional si que pot. Això és d'una importància vital: mai feu servir la mateixa clau per a encriptar dos missatges diferents.
  2. Feu missatges curts. Aquest algoritme esta dissenyat per a fer-lo servir amb missatges curts: un parell de milers de caràcters com a molt. Feu servir abreviacions, argot, etc. als vostres missatges. No us enrrotlleu. Si heu d'encriptar una novel·la de 100,000 paraules, utilitzeu un ordinador.
  3. Com tots els xifrats 'output-feedback', aquest sistema té la desafortunada característica de no recuperar-se mai d'un error. Si esteu encriptant un missatge, i teniu una errada en una de les operacions, cada lletra que segueixi estarà mal encriptada. No sereu capaços de desencriptar-la, fins i tot amb la clau. I mai ho sabreu. Per això si esteu encriptant un missatge, feu tot el procés dos cops per assegurar-vos que es correspon. Si l'esteu desencriptant, comproveu que el missatge té sentit a mesura que l'aneu desencriptant. I si esteu introduint una clau a partir d'una baralla aleatòria, tingueu una copia de reserva de la baralla ordenada per la mateixa raó.
  4. Solitari es reversible. Això significa que si us deixeu la baralla pel voltant després d'haver encriptat el vostre missatge, la policia secreta podria trobar-la i reconstruir l'algoritme a l'inreves. Es important que barregeu la baralla completament, sis cops, després d'acabar amb l'encriptació.
  5. Per a una màxima seguretat, intenteu fer-ho tot amb les mans i el cap. Si la policia secreta comença a tirar la porta a terra, nomes cal barrejar la baralla amb calma. (no la llenceu a l'aire; us sorprendríeu de com es pot arribar a conservar l'ordre.) Recordeu barrejar la còpia de la baralla, si en teniu alguna.
  6. Sigueu curosos amb els apunts, si heu d'escriure alguna cosa. Contindran informació important. Cremar-los és possiblement el millor mètode de destrucció de dades existent, però penseu en el paper. Els papers d'arròs sense goma per a fer cigarrets son ideals per a aquesta feina. Un col·lega va fer proves amb papers 'Club Cabaret Width', i es van consumir completament.

    No és tan difícil escriure en papers de fumar com es podria arribar a pensar. Un llapis Nº.2 amb la punta fina per suau funciona be. Un llapis del numero 3 funciona millor, però és una mica estrany portar-lo. Els bolígrafs tenen uns quants problemes. Primer de tot la punta dura del bolígraf podria deixar impressions a la superfície de sota el paper. I tot allò que porti tinta té la possibilitat de filtrar-se a la superfície de sota.

    Els bons papers de fumar estan fets per a cremar neta i completament. Els papers 'Club' cremaven millor a l'aire lliure. Es a dir, encesos i deixats anar des de l'alçada del pit. Aquests papers també tenen l'avantatge de tenir molt poc volum i que es poden menjar fàcilment si es dona el cas.

    Poden ser extremadament prims. Aquests papers de 3 polzades [7.5 cms N.del T] es poden doblegar sis cops en un quadrat d'un centímetre de costat i un mil·límetre de gruix. Un paper pot contenir fàcilment 80 caràcters en 8 files de dos blocs de cinc lletres cadascun. Sembla que un escriptor amb cura podria arribar fins als 120 caràcters.

  7. Solitari pot implementar-se a un ordinador. Sovint nomes un dels comunicants ha de fer servir la baralla de cartes; l'altre esta bastant segur com per a utilitzar un ordinador. Feu servir un ordinador mentre pugueu: és més ràpid i mai s'equivocarà.
  8. La majoria de jocs de cartes no inclouen els jokers, per això portar una baralla amb ells podria ser sospitós. Prepareu alguna historia.
  9. La seguretat de Solitari no depèn del secretisme del mètode. Assumeixo que la policia secreta sap que l'esteu fent servir.

Anàlisi de Seguretat

N'hi ha molt per a reproduir-lo aquí; Visiteu http://counterpane.com o escriviu a: Counterpane Systems, 1711 North Ave #16, Oak Park, IL 60302

Aprenent Mes

Recomano el meu propi llibre, 'Criptografia Aplicada' (John Wiley & Sons, 1996), com una bona manera de començar. Després podeu llegir 'The Codebreakers', de David Kahn (Scribner, 1996). Després d'això, hi han bastants llibres sobre criptografia amb ordinadors, i alguns altres sobre criptografia manual. És un camp divertit; bona sort.

[ Literatura ] [ Go ] [ Cibercultura ] [ Informàtica i ciència ] [ Col·labora ] [ Sobre Hak Nam ] [ Contacte ]

Hak Nam: Literatura, Go i Cibercultura en català.
Web realitzat amb software lliure en XHTML 1.0 Estricte amb CSS.