Noțiuni introductive cu Criptosistemul SRVB

Introducere

Securitatea informației este un domeniu fascinant de cunoaștere care poate implica orice, de la informatică teoretică la ingineria software, și chiar poate observa psihologia erorii umane.

Criptografia este acum unul dintre numeroșii eroi tehnologici anonimi ai vieții noastre de zi cu zi. Rețelele sociale, serviciile bancare web, informațiile militare și orice alt sistem de informații care se ocupă cu informații sensibile se bazează în mare măsură pe criptografie. Criptografia ne permite să avem intimitate, pe care unii o consideră al 12-lea drept al omului.

Acest articol vă va oferi o introducere în principiile din spatele criptosistemelor cu cheie publică și vă va prezenta Santana Rocha-Villas Boas (SRVB), un criptosistem dezvoltat de autorul articolului și prof. Daniel Santana Rocha. La momentul scrierii, autorii algoritmului pregătesc o campanie care include o recompensă financiară pentru oricine reușește să spargă codul. Deoarece articolul va acoperi în detaliu funcționalitatea algoritmului, acesta este cel mai bun loc pentru a începe urmărirea pentru premiu. Mai multe informații sunt disponibile pe site-ul SRVB.

Ce este un criptosistem?

Criptografia este orice metodă de a împiedica interpretabilitatea unui mesaj, permițând în același timp o modalitate de interpretare fezabilă, atâta timp cât este furnizată o instrucțiune specifică, care este de obicei așa-numita „cheie”. Deși aceasta este o definiție foarte largă, care cuprinde chiar și cele mai timpurii tehnici, este demn de menționat că aceasta nu acoperă tot ceea ce este legat de securitatea informațiilor.

Cursa tehnologică dintre metodele de criptare și modalitățile de a le sparge este de așteptat să nu aibă niciodată un câștigător definitiv. Se așteaptă ca fiecare nouă generație să ridice standardele de securitate a informațiilor și criptoanalizei, care reprezintă setul de tehnici pentru a descifra/spărge în mod sistematic mesajele criptate, adică ocolirea securității sau criptării.

Pentru ca un criptosistem (tehnica de criptografie dată) să fie considerat sigur de utilizatorii săi, acesta trebuie să primească aprobarea comunității internaționale de experți și, astfel, să fie cunoscut public, ceea ce este cunoscut sub numele de principiul lui Kerckhoffs. Cu toate acestea, chiar această condiție expune sistemul controlului din partea comunității mondiale de criptoanaliza, care va încerca să găsească modalități de a sparge sistematic criptările.

Cum se poate face un anumit proces de criptare suficient de secret pentru ca numai agenții vizați să-l poată decripta, în timp ce, în același timp, suficient de public încât comunitatea mondială de criptoanaliză să-i poată atesta robustețea? Răspunsul este o componentă care este un element cheie al Criptologiei: cheia. O cheie a unui criptosistem este un parametru fie pentru algoritmii de criptare, fie pentru decriptare, fie pentru ambii. Păstrând parametrii secreti, mai degrabă decât familia de algoritmi, pot fi îndeplinite ambele cerințe contradictorii. Cu condiția ca familia de parametri să fie suficient de mare (posibil infinită) și că fiecare dintre componentele sale poate fi dovedit că are proprietăți adecvate, nu va fi fezabil ca atacatorii să determine parametrii doar prin inspecție.

În cele din urmă, pentru ca o cheie să funcționeze eficient, trebuie să fie produsă cu ușurință, dar aproape imposibil de ghicit. Cu puterea de calcul a computerelor de astăzi, un computer ar avea nevoie de mai puțin timp pentru a descifra o cheie generată de om decât ar avea nevoie orice om pentru a o imagina, pe lângă faptul că oricum nu este rentabil să generezi cheile în acest fel. Din acest motiv, cheile tind să fie generate de un algoritm.

Un algoritm de generare a cheilor nu trebuie să creeze rezultate previzibile/reproducibile ca rezultat al utilizării tipice. Deoarece algoritmii efectuează proceduri fără niciun proces inteligent, întrebarea devine cum se poate face acest lucru. Răspunsul este transformarea algoritmilor de generare a cheilor în hărți care transformă o cantitate mare de biți cu adevărat aleatori în chei. Biți cu adevărat aleatori pot fi achiziționați din sistemul de operare, ceea ce îi generează din incertitudinea universului. Unele surse ar fi mișcarea mouse-ului, latența pachetului de rețea sau chiar hardware-ul dedicat, în funcție de aplicație.

Criptosisteme cu cheie publică

Pregătește-te să fii surprins din nou, pentru că acum vom introduce un concept care aparent contrazice ceea ce tocmai am spus: cheia publică.

Până acum, am văzut crearea unei comunicări securizate după ce parametrii secreti (cheile) au fost schimbate în siguranță, dar rămâne problema schimbului de parametri pe un canal public. Chiar acum, vom introduce un concept care rezolvă o problemă ceva mai palpabilă: crearea unui canal securizat.

Să presupunem că Alice lucrează cu Bob și că vor să-și păstreze interacțiunile de lucru în siguranță folosind criptarea. Ei se pot întâlni și schimba cheile de criptare dându-și unul altuia o unitate flash USB cu cheile lor pe ele. Dar dacă Alice și Bob sunt localizați pe continente diferite. Cum se stabilește un canal securizat acolo unde nu există niciunul?

Trimiterea cheilor prin e-mail nu ar fi o opțiune, deoarece concurentul lor Eve poate intercepta schimbul și poate folosi cheile pentru a citi toate datele criptate ulterior. Dacă ar avea orice alt canal digital prin care să poată transmite aceste date sensibile, atunci nu ar avea nevoie de criptare și, prin urmare, de chei, în primul rând. Trimiterea cheii prin poștă fizică ar putea fi, de asemenea, interceptată, deoarece necesită pentru început schimbul de informații sensibile. Trimiterea unei chei steganografate prin ascunderea în alte date ar fi inteligentă, dar inutilă, cu excepția cazului în care expeditorul este sigur că destinatarul, și numai destinatarul, este conștient de existența unui astfel de mesaj și știe cum să-l extragă. După cum se întâmplă, conștientizarea existenței unui mesaj împreună cu descrierea modului de extragere a cheii din date este un tip de cheie în sine, ceea ce ne readuce la punctul unu.

Soluția constă în conceperea unui criptosistem pentru care parametrul de criptare nu este suficient pentru a interpreta în mod fezabil mesajul original ^[1] și păstrarea pentru tine a parametrului care ar permite interpretarea mesajului. Numim acel parametru cheie privată. Pe baza cheii private, se poate genera în mod fezabil un set de parametri pentru un instrument de criptare fără ca acești parametri noi să poată dezvălui care este cheia privată. Acest set de parametri poate fi partajat public, pentru că nu este atât de important cine poate cripta ceva, atâta timp cât o singură persoană îl poate decripta. Deoarece acest set de parametri pentru instrumentul de criptare poate fi făcut public, se numește cheie publică.

Criptografia în care cheile de criptare și de decriptare diferă, iar prima nu poate fi utilizată în mod fezabil pentru a deduce pe cea din urmă, se numește criptografie asimetrică, în timp ce criptografia simetrică este ceea ce avem atunci când acele chei sunt aceleași sau sunt ușor deduse una din cealaltă.

Alice îi trimite lui Bob cheia ei publică, care poate fi folosită doar pentru a cripta lucruri pe care numai ea le poate decripta (cu cheia ei privată, pe care o păstrează în mod privat) și, invers, Bob îi trimite Alicei cheia lui publică, care poate fi folosită doar pentru a cripta lucrurile. că numai el poate decripta (prin intermediul cheii sale private, pe care o păstrează și în mod privat). Dar cum se poate publica un parametru pentru un algoritm de criptare din care nu se poate deduce algoritmul invers exact?

Răspunsul se află în domeniul matematicii care este cel mai strâns legat de programare, teoria complexității computaționale. Oricine a pătruns suficient de adânc în problemele matematice a auzit despre transformări care sunt ușor de făcut într-un fel, dar greu de făcut invers. În calcul, de exemplu, găsirea unei derivate de manual este în mod obișnuit un exercițiu simplu, în timp ce efectuarea inversului (cum ar fi rezolvarea oricărei integrale puțin triviale sau a ODE sau PDE fizică de manual, de exemplu) necesită un proces mai investigativ de prima ipoteză a familiilor de funcții care sunt garantate (sau cel puțin plauzibile) să conțină soluția(le) și să rezolve probleme inverse pentru a găsi soluții din aceste familii.

Un exemplu care este de fapt utilizat în criptosistemul RSA este înmulțirea numerelor prime mari versus factorizarea produsului rezultat fără a cunoaște deja factorii. Înmulțirea este banală, dar factorizarea necesită să ghiciți aleatoriu ^[2] factorii primi, care au sute de cifre. O proprietate importantă a operațiunii este necesitatea ca aceasta să se scaleze bine. Adăugarea câtorva cifre la dimensiunea numerelor prime în RSA va avea ca rezultat o cheie care necesită operațiuni de mii de ori mai multe pentru a sparge, adăugând în același timp o mică creștere a complexității procesului de criptare. În linii mari, produsul numerelor prime este folosit pentru criptare, în timp ce perechea de factori primi este folosit pentru decriptare.

Având în vedere toate acestea, să aruncăm o privire la modul în care funcționează criptosistemul SRVB.

Algoritmul de bază - Privind SRVB

Problema sumei subsetului

Ca orice alt sistem criptografic cu cheie publică, SRVB se bazează pe dificultatea de a rezolva o anumită problemă care este ușor de produs. În cazul SRVB, este problema sumei subsetului, care poate fi descrisă după cum urmează:

Având în vedere întregul $w$ și $v_1, \cdot \cdot \cdot, v_N \in Z$ găsiți secvența $b_1, \cdot \cdot \cdot, b_N \in {0,1}$, astfel încât $ \sum_ {i = 1}^{N} v_i b_i = w $.

În mod clar, această problemă poate fi produsă prin alegerea aleatorie a N numere întregi, alegând aleatoriu un subset dintre ele și însumând acest submult - ceea ce este banal.

O căutare cu forță brută ar avea o complexitate de $ O( N * 2^N ) $, calculând pentru fiecare combinație de valori a $b$s. O abordare mai eficientă a fost oferită de Horowitz și Sahni în 1972, cu o complexitate de $ O ( N * 2 ^ {N / 2} ) $. Problema este cel puțin la fel de grea dacă înlocuim $b$s și $w$ cu vectori $k$-dimensionali ai numerelor întregi. Domeniul în care se ține această problemă mai dificilă, totuși, trebuie să aibă și un izomorfism cu un inel în care are loc o versiune mai ușoară a aceleiași probleme, așa cum vom vedea mai jos. Din acest motiv, SRVB exploatează problema sumei submulțimii din întregi gaussieni, unde $ k = 2 $.

Există un caz special în care această problemă devine ușor de calculat prin utilizarea unui algoritm lacom. Dacă sortăm o secvență factori de scalare $ v_1, \cdot \cdot \cdot, v_N $ în care fiecare număr întreg din secvență este mai mare decât suma tuturor numerelor întregi care au venit înaintea lui ($ \forall i , \sum_{j= 1}^{i-1} v_j < v_i $), s-ar putea folosi o abordare lacomă pentru a găsi secvența b în timp liniar. O secvență cu proprietățile descrise se numește secvență supracrescătoare .

Iată o descriere simplă a soluției lacome pentru acest caz:

1. Începeți cu $ i = N $, factorul observat în prezent și $ w' = w $, restul lui $w$

2. Dacă factorul de scalare actual este prea mare pentru a se potrivi în ceea ce rămâne din $w$, adică $ v_i > w'$, setați $b_i = 0$ și continuați cu pasul următor. În caz contrar, știm că factorul de scalare trebuie să fie în succesiune (deoarece restul factorilor este mai mic decât $v_i$) și setăm $b_i = 1$.

3. $ w' \Leftarrow w' - v_i * b_i$, $i \Leftarrow i - 1$. Dacă $i > 0$, reveniți la pasul 2.

4. Verificați că, acum, $w' == 0$, altfel problema a fost coruptă

Acest lucru funcționează deoarece știm că toți multiplicatorii mai mici decât cel observat în prezent nu pot acoperi colectiv atât de mult din (sub)suma $ w' $ cât poate multiplica multiplicatorul actual. Deci, dacă suma rămasă este mai mare decât factorul curent, știm cu siguranță că toți factorii următori împreună nu vor reuși să se însumeze fără ajutorul factorului curent. Pe de altă parte, deoarece toți multiplicatorii sunt pozitivi, dacă factorul curent $ v_i $ este mai mare decât suma rămasă $ w' $, adăugarea oricărui alt factor ar face ca rezultatul să depășească $ w' $ și mai mult.

Să creăm o notație pentru restul articolului. Alegem $ v_1, \cdot \cdot \cdot, v_n $ și $w$ să fie factorii și suma secvenței supercrescente, în timp ce $ u_1, \cdot \cdot \cdot, u_n $ și $y$ vor fi parametri disponibili care sunt furnizați pentru a recupera $ b_1, \cdot \cdot \cdot, b_n $.

Cu o secvență $ u_1, \cdot \cdot \cdot, u_n $ aleasă astfel încât să nu fie în creștere, iar numărul $y$ fiind disponibil public, nu sunt furnizate în mod public suficiente informații pentru a recupera secvența $ b_1, \cdot \cdot \cdot , b_n $. Totuși, dacă există o secvență supracrescătoare $ v_1, \cdot \cdot \cdot, v_n $ care ar putea lua locul secvenței $ u_1, \cdot \cdot \cdot, u_n $, s-ar putea folosi această secvență pentru a rezolva problema cu o abordare lacomă.

Mai jos vom arăta cum funcționează.

Utilizarea sumelor de subseturi într-un criptosistem anterior

În 1978, Ralph Merkle și Martin Helman, au conceput o modalitate de a exploata acele două paradigme de rucsac și liniaritatea operației de modul pentru a construi conexiunea dintre cele două secvențe descrise în secțiunea anterioară - concepând astfel un Criptosistem cu cheie publică. Ideea a fost de a transforma rucsacul ușor (cel format din vectorul supracrescător al numerelor întregi) în cel dur (cel lipsit de această proprietate) prin intermediul unei operații liniare (modulul) cu operanzi secreti. Transformarea constă în înmulțirea fiecărui $v_i$ cu $\theta$ și luarea restului acestui produs cu $\alpha$, unde $\alpha \gt \sum_{i=1}^N v_i$ și $\gcd (\alpha, \theta) = 1$ (două constrângeri care vor fi în curând justificate). Rezultatul, secvența $u_1, \ldots, u_N$, nu mai este în creștere și poate fi considerată un rucsac dur .

O permutare aleatorie a secvenței $u_1, \ldots, u_N$ ar fi dată părții care dorește să cripteze și să ne trimită un mesaj. Permutarea se face astfel încât o terță parte are mai greu să ghicească care este secvența originală de supra-creștere. Blocurile de biți ale unui mesaj sunt utilizate ca coeficienți $b_1, \ldots, b_N$. Criptarea se face prin înmulțirea secvenței de chei cu această secvență de coeficienți și însumând înmulțirile într-un rezultat, pe care îl vom eticheta $y$. Doar proprietarul cheii private poate transforma $y$ în $w$ corespunzător care s-ar obține dacă aceleași blocuri $b_1, \ldots, b_N$ ar fi fost înmulțite cu numerele întregi simple (secvența $v_1, \ldots , v_N$). Aceasta se realizează prin înmulțirea $y$ cu $\theta^{-1}$, inversul multiplicativ al modulului $\theta$ $\alpha$ (a cărui existență depinde de acea condiție a $\gcd(\alpha, \ theta) = 1$). Cu alte cuvinte, $(\theta * \theta^{-1}) \bmod \alpha = 1$. După aceea, calculăm $w = (y * \theta^{-1}) \bmod a$. Motivul pentru care se garantează că funcționează este liniaritatea modulului , adică faptul că combinația liniară a resturilor este egală cu restul combinației liniare.

Dacă aplicăm consecutiv definiția lui $u$, inelul coeficient și proprietatea de liniaritate a operatorului modul, vedem corespondența:

$ \begin{align} y & = \sum_{i=1}^N b_iu_i \newline & = \sum_{i=1}^N b_i (v_i * \theta \bmod \alpha) \newline & = \sum_{ i=1}^N b_i * v_i * \theta \bmod \alpha \newline & = \left[ \sum_{i=1}^N b_i * v_i * \theta \right] \bmod \alpha \newline & = \ stânga[ \sum_{i=1}^N b_i * v_i \right] * \theta \bmod \alpha \newline & = w * \theta \bmod \alpha \end{align} $

Și astfel suma simplă $w$ poate fi recuperată prin înmulțirea ambelor părți cu $\theta^{-1}$ și luând modulul cu $\alpha$. Pentru a face acest lucru, trebuie să cunoașteți atât $\alpha$ cât și $\theta$ (care vă permit să calculați cu ușurință $\theta^{-1}$), care trebuie să fie păstrate private ca părți ale cheii private.

O singură constrângere, $\alpha \gt \sum_{i=1}^N v_i$, a fost lăsată nejustificată și iată explicația pentru aceasta: egalitatea dintre a doua și a treia linie constă într-o egalitate între clasele de reziduuri ale coeficientului. inel de numere întregi modulo $\alpha$. Cu alte cuvinte, afirmă doar egalitatea restului de membri atunci când este împărțit la $\alpha$, ceea ce nu este o condiție suficientă pentru egalitatea membrilor înșiși . Ca rezultat, mai mult de un vector de valori $b$ ar putea fi mapat într-un singur $y$, ceea ce este prevenit prin limitarea subsumei maxime posibile (adică suma tuturor parcelelor $v_i$) $w_{max}$ la $w_{max}$ să fie mai mic decât $\alpha$ pentru orice combinație de valori $b$.

La fel ca orice alt exemplu al vieții de zi cu zi, cunoașterea completă a tuturor ipotezelor este adesea imposibilă și niciodată ușoară. În consecință, trebuie să ne bazăm pe intuiția matematică atunci când judecăm dacă un criptosistem este sigur de utilizat, ceea ce nu ne oferă nicio garanție reală. La șase ani de la crearea sa, criptosistemul MH a fost rupt printr-un atac al lui A. Shamir. Au existat mai multe încercări de a resuscita MH, multe dintre ele, de asemenea, eșuate.

Criptosistemul Santana Rocha - Villas Boas (SRVB).

În 2016, după câteva brainstorms cu autorul acestui articol despre posibilitățile ^[3] inspirate diferit ale unui criptosistem, Daniel Santana Rocha a avut ideea de a înlocui $\theta$ și $\alpha$ cu numere întregi gaussiene. Din motive mai tehnice, această abordare duce la rezistența împotriva atacului Shamir menționat mai sus.

El a conceput, de asemenea, un bloc de biți constând din mulți pași din combinația liniară descrisă anterior a unui rucsac dur . În fiecare dintre ele, un întreg nou (gaussian), echivalent cu unul, mai mare decât suma tuturor anterioare ar fi adăugat la sfârșitul secvenței, în timp ce cel mai mic în prezent ar fi eliminat.

O constrângere diferită și totuși elegant analogă se aplică pentru $\alpha$, care este acum un întreg gaussian. Avem nevoie de $w_{max} \leq \vert\alpha\vert^2$. Motivul este foarte greu de oficializat, dar din fericire poate fi ușor intuit dintr-o descriere elegantă:

Imaginează-ți o rețea pătrată în planul numerelor complexe, a cărei latură este o ipotenuză a unui triunghi dreptunghic de cateti a și b, paralel cu axele reale și imaginare. Un exemplu de astfel de zăbrele este dat mai jos. Numerele întregi Guassiene modulo $\alpha = a + bi$ pot fi reprezentate prin puncte situate într-o astfel de rețea. Într-o astfel de rețea există $\vert\alpha\vert^2$ puncte distincte. Dacă alegem un $\alpha$ suficient de mare, putem încadra toate combinațiile liniare ale rucsacului ușor.

Aceasta este reprezentarea grafică a izomorfismului $f : Z/n \rightarrow Z[i]/(\alpha)$, unde $n = 13$ și $\alpha = a + bi = 3 + 2i$ (rețineți că $ n$ și $\alpha$ într-adevăr satisfac $n = \vert \alpha \vert ^ 2 = a^2 + b^2 $ după cum este necesar). Punctele reprezintă numerele întregi gaussiene, adică numerele complexe $a + bi$, unde $a$ și $b$ sunt numere întregi. Ca de obicei, axa orizontală reprezintă partea reală, în timp ce verticală reprezintă partea imaginară. Astfel, mutarea unui punct la dreapta sau la stânga echivalează cu adăugarea de +1 sau respectiv -1 la valoarea sa curentă. De asemenea, mutarea unui punct în sus sau în jos corespunde adăugării +i sau respectiv -i.

Punctele roșii sunt acele echivalente cu $0 \bmod(\alpha)$. În afară de acestea, am mai colorat încă 4 perechi de puncte.

Izomorfismul $f$ este definit de transformarea $i$-lea element al secvenței ciclice $(0,1,2,\cdot\cdot\cdot,10,11,12,0,1,2,\cdot \cdot\cdot)$ în $i$-lea element al secvenței, de asemenea, ciclice de puncte din figură, care respectă următoarele reguli:

1. Începe de la punctul roșu al primului rând;
2. Urmează săgețile orizontale la dreapta; cu excepția că
3. Când urmărirea săgeților conduce secvența în afara rețelei, aceasta ar ajunge la unul dintre punctele non-negre. În loc să meargă în acel punct, sare în același punct colorat (adică, punctul echivalent modulo $\alpha$) în interiorul aceluiași pătrat; și, în sfârșit
4. Când acest punct non-negru se întâmplă să fie roșu (ceea ce se întâmplă după ce toate celelalte culori au fost trecute prin), secvența sare la punctul roșu cel mai de sus, reinițiind astfel ciclul;

Pentru a mapa cel puțin $Y$ numere întregi naturale, trebuie să luăm un pătrat cu aria $\vert\alpha\vert^2$ (unde $\vert\alpha\vert = \sqrt{a^2 + b^2} $ este, după teorema lui Pitagora, măsura laturii sale) cel puțin la fel de mare.

Observați că fiecare „săritură” schimbă numărul rândului $r$ în $r \leftarrow (r + b)(mod a + b)$ dacă se numără rândurile de sus în jos și, în mod echivalent, la $r \leftarrow (r + a)(mod a + b)$ dacă se numără de jos în sus. Prin urmare, condiția necesară și suficientă pentru ca fiecare rând (și punct) să fie parcurs exact o dată pe fiecare ciclu este ca dimensiunea sărituri să fie coprime cu numărul de rânduri sau, cu alte cuvinte, $gcd(a,a + b) = mcd(b,a + b) = 1$. Datorită proprietăților celui mai mare operator comun divizor, ambele sunt echivalente cu $gcd(a,b) = 1$.

YS Villas Boas a observat nevoia de coprimalitate a $a$ și $b$. Pentru a păstra supracreșterea, fiecare număr întreg nou $w$ adăugat la sfârșitul secvenței trebuie să depășească suma tuturor celor actuale ($w > \sum_{i=1}^k v_i$). El a observat că pentru a realiza acest lucru, coeficienții lor de înmulțire $b_i$ ar trebui să fie de cel puțin 1 și, astfel, fiecare bit nu ar putea fi mapat în coeficienții 0 și 1. Dacă coeficienții ar fi 0 și 1, numai blocul compus numai din unele ar satisface supracreşterea. Din acest motiv, biții 0 și 1 au fost apoi mapați la coeficienții de înmulțire 1 și 2.

În sfârșit, și mai puțin trivial: în timpul fiecărei etape a decodării, se găsește un nou întreg $v_1$ ca soluție a ecuației $b_1 v_1 = v_{n+1} - \sum_{i = 2}^{n} b_i v_i$, unde toate $v_i$ și $b_i$ sunt cunoscute pentru $1 < i \leq n$. Deoarece nici nu știm $b_1$, ajungem la un sistem cu o ecuație și două variabile, ceea ce ne lasă cu un grad de libertate. Pentru a corecta acest lucru, trebuie să arbitram o valoare pozitivă (de dragul simplității, 1) care să fie întotdeauna atribuită lui $b_1$, eliminând astfel ambiguitatea. Astfel, deoarece primul coeficient este fixat la 1, pentru a codifica $n$ biți la fiecare pas, secvențele noastre de numere întregi trebuie să aibă o lungime de $n + 1$ elemente.

O ultimă tehnică de rezolvat este cazul în care dimensiunea în octeți a mesajului nu este un multiplu al mărimii blocului. Cu alte cuvinte, ce să facem cu posibilii octeți rămași ai ultimului bloc de date pentru ca, odată recuperate blocurile de date, să fie păstrați toți octeții conținutului original, dar nu mai mulți decât ei? Am rezolvat asta repetând ultimul octet al mesajului o dată. Această copie este, apoi, urmată de o secvență aleatorie pe care fiecare componentă trebuie doar să fie diferită de cea anterioară. Astfel, atunci când blocurile de date sunt preluate, ultimul dintre ele sau, în cel mai rău caz, cel dinaintea ultimului este trunchiat în ultima repetare de octeți. ^[4]

Acum să arătăm un exemplu de criptosistem SRVB.

Începem cu parametrii:

$k = 4$;

$m = 4$;

care dă o lungime a blocului de $l = 4 * 4 = 16$ și o secvență supracrescătoare de $k + 1 = 5$ numere întregi naturale, care este operată - adică combinate liniar, adăugate cu rezultatul acestei combinații liniare și redus la ultimele sale $k + 1$ elemente —$m = 4$ ori;

De dragul simplității, să fie următorul vector (supracrescător) al lui $v_i$:

$(1,2,4,8,16)$

Într-adevăr, succesiunea primelor cinci puteri ale lui 2, doar pentru că aceasta este șirul supracrescător cu cinci elemente și cele mai mici valori strict pozitive posibile (evitându-se astfel un 0 în cheia publică, care ar da banal corespondentul 0 al omologul său). ).

După cum am spus mai devreme, pentru $\alpha = a + bi$, numerele întregi $a$ și $b$ trebuie să fie coprime, iar conform noii constrângeri pe care am menționat-o, trebuie să cerem ca $a^2 + b^2 = \vert\alpha\vert^2 \geq W$. Un calcul rapid are ca rezultat $W = 1590$. Deoarece $\sqrt{1590} \simeq 39,8$, un $\alpha$ foarte convenabil de ales ar fi $\alpha = 39 + 40i$, deoarece este suficient de mare pentru a găzdui un izomorfism cu un inel de numere întregi cu la cel puțin 1590 de componente, în același timp satisfăcând $gcd(a,b)=1$. De asemenea, trebuie să alegem un $\theta$ astfel încât $gcd(a,\theta)=1$ ^[5] și, de preferință, să nu fie prea mic, astfel încât $(a_1 * \theta) \% \alpha \neq v_1 * \theta$, (de asemenea, pentru a evita oferirea de informații). $\theta = 60$ face treaba, rezultând:

$-19-1i,1+38i,3-3i,6-6i,12-12i$ ^[6]

Atunci hai să ne murdărim mâinile. Preia mesajul Hello Toptal! . Mai întâi îl mapăm într-o matrice de octeți conform ASCII și convenția noastră pentru trunchierea blocurilor de date:

 01001000 01100101 01101100 01101100 01101111 00100000 01010100 01101111 01110000 01110100 01100001 01101100 00100001 00100001

Deoarece blocul nostru de date are 16 biți = 2 octeți, iar mesajul nostru are 13 caractere, ajungem la 7 blocuri de date a câte 2 octeți fiecare, unde ultimul conține de două ori reprezentarea biților a caracterului '!' . Să criptăm primul bloc pas cu pas. Acordați o atenție deosebită deoarece biții fiecărui octet sunt luați în ordinea semnificației lor.

$m=01001000 01100101$

• Prima ciugulire a primului octet: $(0,0,0,1)\rightarrow(1,1,1,1,2)\cdot(-19-1i,1+38i,3-3i,6-6i,12 -12i)=15+4i$
• Al doilea ciupit al primului octet: $(0,0,1,0)\rightarrow(1,1,1,2,1)\cdot(1+38i,3-3i,6-6i,12-12i,15+ 4)=49+9i$
• Primul mic al doilea octet: $(0,1,0,0)\rightarrow(1,1,2,1,2)\cdot(3-3i,6-6i,12-12i,15+4i,49+ 9i)=106-10i$
• Al doilea ciupit al celui de-al doilea octet: $(0,1,1,0)\rightarrow(1,1,2,2,1)\cdot(6-6i,12-12i,15+4i,49+9i,106- 10i)=252-2i$

Și astfel, tocmai am mapat

„El” $\Rightarrow(12-12i,15+4i,49+9i,106-10i,252-2i)$

Restul mesajului criptat este după cum urmează:

„ll” $\Rightarrow(12-12i,21-2i,61-3i,185-31i,367-59i)$

„o „ $\Rightarrow(12-12i,25+33i,65+32i,111+44i,244+124i)$

„Către” $\Rightarrow(12-12i,9+10i,46+12i,149+5i,277+31i)$

„pt” $\Rightarrow(12-12i,3+16i,46+12i,73+23i,201+49i)$

„al” $\Rightarrow(12-12i,4+54i,44+53i,117+193i,231+389i)$

”!!” $\Rightarrow(12-12i,4+54i,32+65i,63+92i,121+247i)$

Acum, pentru decriptare, avem $\theta^{-1}=60^{-1}=27+i$:

$($”El” $\Rightarrow)$ $(12-12i,15+4i,49+9i,106-10i,252-2i)*\theta^{-1}\%\alpha=(16,47 ,93.223.527)$

Acum, vine algoritmul lacom:

În primul rând, scădem fiecare factor contributiv înmulțit cu unul, deoarece se știe că au contribuit cel puțin o dată pentru ultimul, rezultând:

• Al doilea ciupit al celui de-al doilea octet:

$T \leftarrow (527-233-93-47-16) = 148$

$(T \geq 223) = (148 \geq 223) = fals \Rightarrow b_1=0 ; T \leftarrow (T - 0 * 223) = 148$

$(T \geq 93) = (148 \geq 93) = adevărat \Rightarrow b_2 = 1; T \leftarrow (T - 1 * 93) = 55$

$(T \geq 47) = 55 \geq 47) = adevărat \Rightarrow b_3 = 1; T \leftarrow (T - 1 * 47) = 8$

$(T \geq 16) = 8 \geq 16) = fals \Rightarrow b_4 = 0; T \leftarrow (T - 0 * 16) = 8$

Rezultat: 0110;

Rest: 8 (adăugat la începutul secvenței ca element nou cel mai de jos);

Drop 527 din finalul secvenței curente;

• Prima ciugulire a celui de-al doilea octet:

$T \leftarrow (233-93-47-16-8) = 59$

$(T \geq 93) = (59 \geq 93) = fals \Rightarrow b_1 = 0; T \leftarrow(T - 0 * 93) = 59$

$(T \geq 47) = (59 \geq 47) = adevărat \Rightarrow b_2 = 1; T \leftarrow (T - 1 * 47) = 12$

$(T \geq 16) = (12 \geq 16) = fals \Rightarrow b_3 = 0; T \leftarrow (T - 0 8 16) = 12$

$(T \geq 8) = (12 \geq 8) = adevărat \Rightarrow b_4 = 1; T \leftarrow (T - 0 * 12) = 4$

Rezultat: 0101;

Rest: 4 (adăugat la începutul secvenței ca element nou cel mai de jos);

Drop 233 din finalul secvenței curente;

• Al doilea ciupit al primului octet:

$T \leftarrow (93 - 47 - 16 - 8 - 4) = 18$

$(T \geq 47) = (18 \geq 47) = fals \Rightarrow b_1 = 0; T \leftarrow (T - 0 * 47) = 18$

$(T \geq 16) = (18 \geq 16) = adevărat \Rightarrow b_2 = 1; T \leftarrow (T - 1 * 16) = 2$

$(T \geq 8) = (2 \geq 8) = fals \Rightarrow b_3 = 0; T \leftarrow (T - 0 * 8) = 2$

$(T \geq 4) = (2 \geq 4) = fals \Rightarrow b_4 = 0; T \leftarrow (T - 0 * 4) = 2$

Rezultat: 0100;

Restul: 2 (adăugat la începutul secvenței ca element nou cel mai de jos);

Drop 93 din finalul secvenței curente;

• Prima ciugulire a primului octet:

$T \leftarrow (47-16-8-4-2) = 17$

$(T \geq 16) = (17 \geq 16) = adevărat \Rightarrow b_1 = 1; T \leftarrow (T - 1 * 16) = 1$

$(T \geq 8) = (1 \geq 8) = fals \Rightarrow b_2 = 0; T \leftarrow (T - 0 * 8) = 1$

$(T \geq 4) = (1 \geq 4) = fals \Rightarrow b_3 = 0; T \leftarrow (T - 0 * 4) = 1$

$(T \geq 2) = (1 \geq 4) = fals \Rightarrow b_4 = 0; T \leftarrow (T - 0 * 2) = 1$

Rezultat: 1000;

Rest: 1 (adăugat la începutul secvenței ca element nou cel mai de jos);

Drop 47 din finalul secvenței curente;

Ca urmare, am recuperat blocul de date: „01001000 01100101” care conține primele două caractere „El”, ale mesajului nostru. Nu numai atât, am preluat corect și secvența noastră de supracreștere a cheii private $(1,2,4,8,16)$.

Celelalte hărți ale blocurilor de date merg în același mod.

Comparație cu principalele criptosisteme cu cheie publică

SRVB este:

1. Total gratuit și public;

2. Considerabil mai simplu și mai ușor de înțeles și implementat decât ECC ^[7] ;

3. Abundent pe chei și, prin urmare, practic fără costuri, spre deosebire, de exemplu, de RSA, care se bazează pe numere prime, care sunt scumpe.

Putem deja rezuma cele mai probabile vulnerabilități. Deoarece SRVB descinde din MH, este ușor de bănuit că ar fi vulnerabil la o generalizare a atacului Shamir sau la un alt atac care îl distruge. Deși autorul avea motive să creadă că acesta nu ar fi cazul, nu a fost încă făcută nicio confirmare (ceea ce este foarte tipic atunci când se ocupă de criptosisteme).

Ce urmeaza?

Rocha a observat câteva generalizări pentru inelele de coeficient de utilizat, care pot duce eventual la o creștere a complexității criptoanalizei. Vom investiga și aceste posibilități.

Obscurizarea algebrică liniară

După cum se întâmplă, în timpul dezvoltării și documentării SRVB, Villas Boas a venit cu o altă abordare pentru a îmbunătăți conceptul de criptosistem cu cheie publică de rucsac, care nu va fi explicat în multe detalii aici, pentru ca acest articol să nu devină prea lung. și obositor, dar iată o scurtare a ei. Dacă nu reușiți să-l înțelegeți, nu vă faceți griji, rămâneți aproape pentru lansarea următorului nostru articol, în care vom intra în detalii mai amănunțit: Vedeți suma subsetului $y$, a, de exemplu, $N$ elemente de inel coeficient $u_i$ (care sunt corespondente izomorf cu numerele întregi pozitive $v_i$ ale secvenței supercrescătoare, ca mai înainte) ca o multiplicare a unui vector rând al acestor $u_i$ cu un vector coloană $B$ ( pentru binar) de zerouri și unu ^[8] .

$y = \sum_{i=1}^n u_i b_i = (u_1,\cdot\cdot\cdot,u_n)^T\cdot(b_1,\cdot\cdot\cdot,b_n)$=UB,

unde $b_i \in {0,1}$

Acum, imaginați-vă că, în loc de acest vector de $u_i$, aveți, în stânga, o matrice $n$ cu $N$ (cu $n < N$) V, având $v_i$ (numerele întregi din supra-creșterea secvență) vector ca (fără pierderea generalității) primul său rând și toate celelalte intrări umplute cu zgomot. Observați că, acum, înmulțirea V cu același vector de biți B vă oferă un vector coloană W care are $w$ ca primă intrare și zgomot în celelalte. Acum, luați această matrice V și înmulțiți-o cu o matrice aleatorie ^[9] n cu n matrice R din stânga, definind n cu N matricea P:

P = RV

Ideea este că Bob folosește P ca nouă cheie publică. Din cauza aleatoriei lui R, vectorul

$Y = PB = RV B = RW$

are informația $w$ ascunsă de zgomotul din alte rânduri ale lui V. Bob calculează și el în avans și stochează vectorul rând S care satisface:

$R^TS^T = e_1$

Când Alice îi trimite Y lui Bob, acesta îl găsește pe SY, deoarece:

$SY=S(PB)=S((RV)B)=SRVB= {e_1}^TR^{-1}((RV)B)=$

(pana acum doar definitii)

${e_1}^T (VB)={e_1}^TW = w$

(Acum, exploatând asociativitatea pentru a anula Rs)

and then proceeds as before to extract the vector of $b_i$ from $w$ by means of the greedy algorithm.

So, in one word, the Linear Algebraic Obscuring exploits the associativity of matricial multiplication (the fact that we could expand the terms and then operate their components in a new order provided we that preserved the sequence of all the operands in the sequence) to 'linearly' scramble and then filter (in the encryption and in the decryption respectively) noise to/from $w$. And in limit case $n = 1$, the system elegantly goes back to original to Rocha's approach.

The SRVB Campaign – a prize challenge

As explained before, in accordance to Kerckhoffs' principle, experience shows that antiquity of a publicly known unbroken cryptosystem is the main source of reliability of it, far more than any theoretical argumentation by the own authors, apart from anything else, because definitive proof of efficacy of the algorithms usually are not available.

And here it is our great chance to put these concepts to practice to earn a big money prize: Aware of this fact, we launched the aforementioned campaign, which is basically a crowdfunding for a prize automatically awarded to the first one that manages to break a message. The money is going to be converted to bitcoins in a given wallet whose private key will be SRVB encrypted and published so that anyone able to decipher it can simply take the money anonymously, no questions asked.

Acknowledgments

This article in particular and the whole SRVB Crypto project in general have been greatly helped by Prof. Charles F. de Barros, assistant professor at the Federal University of Sao Joao Del Rei. Prof. Barros provided us a technical review of the SRVB cryptosystem itself. I judged it necessary to submit to before daring to publish, and that I would certainly take much longer to do by myself.

In addition, I also would like to extend my deep gratitude to professor Adnan Ademovic for his extraordinarily insightful, attentive, and patient work as the editor of this article.

Glossary

1. Cryptology/Cryptography: The science/practice of making a message nearly impossible to interpret without a specific set of instructions (in this context, the so-called "key"), thus allowing agents who share these instructions to communicate securely even if tapped by third parties;
2. Steganography: The science/practice of hiding a message within another by means of adding apparently innocuous modifications to the latter;
3. Key generation: the mapping of (expectedly) random inputs into (as random) valid keys;
4. Encryption/Encoding: The easily computable mapping of an easily interpretable message into another that is either hard or impossible to construe, by means of an (as randomly specified) element the one correspondent to the key of a (by Kerckhoffs' principle, publicly known and validated) family of algorithms;
5. Decryption/Decoding: The easily computable mapping that consists of the inverse of the previous, also being definable by an (as randomly specified, and therefore, unknown and hard to be guessed by third parties) element _again, the one correspondent to the key_ of a (by the same principle, usually known) family of algorithms, that thus outputs the original message when input with the encrypted one;
6. Cryptosystem: A triad of the family of encoding algorithms, the family of corresponding decrypting algorithms, and a key generating algorithm;
7. Allies: The agents with whom the communication is intended, and who are expected to act according to the protocol's rules;
8. Enemies/Third Parties: The agents with whom the communication is not intended, but try, nevertheless, to eavesdrop the communication and bypass the security enhanced by the cryptosystem;
9. Secure Channel: Any protocol (procedure) for communication that is easy to use while also effectively preventing third parties to feasibly construe what is meant by its users;
10. Insecure Channel: any channel (ie, protocol or procedure) that, as the name suggests, is not a secure channel;
11. Breaking a Key: The process of discovering a key by means of public pieces of information (like an encrypted message or public key) other than the key itself to be discovered and that was not expected to feasibly allow the discovery of the key. Since the information that results from this process grants the decryption of the messages, this is a particular case of…
12. Breaking/Deciphering a message: Any way to deduce the original content of an encrypted message only by means of the encrypted message itself and other pieces of information that were not expected to suffice for the deduction of the original content;
13. Breaking a Cryptosystem: Discovery of a systematic way to feasibly break whatever message is encrypted by this method under whatever parameter;
14. Kerckhoffs' Principle/Desideratum/Axiom/Law: A cryptologic principle named after the dutch cryptographer Auguste Kerckhoffs, according to which, in order for a cryptosystem to be deemed secure, everything about it except by its (private) keys must be of public knowledge;
15. Key: Secret parametrization of a cryptosystem allowing it to be infeasible to be guessed (and consequently broken) by third parties while also being validated by the community of cryptanalysts (in accordance to Kerckhoffs' principle);
16. Symmetric Cryptosystem: Any cryptosystem on which any parameter for the encoding suffices for easily deducing the parameter for decoding, and, for this reason, must be kept private. One can rephrase it by saying that the encryption and decryption parameters are both equivalent to the key;
17. Asymmetric/Public Key Cryptosystem: Any cryptosystem for which there is a way to express the parameters for the encoding that does not suffice to feasibly deduce the correspondent parameter for decoding, allowing it to be sent to allies through an insecure channel, or even made public, and thus creating a secure channel where there was none;
18. Public Key: A component of an asymmetric cryptosystem that suffices for parameterizing the encryption but does not suffice for feasibly deducing the decryption parameter, ie, the…
19. Private Key: A component of an asymmetric cryptosystem that suffices for parameterizing the decryption and thus must be kept privately and usually also suffices for parameterizing the encryption;

^[1] Note that, here, the phrases decipher or decrypt do not apply, because before a given cryptosystem (with all its components, including its keys) is well defined, one cannot classify a given method of construing the original message from the encrypted one as the intended communication (decryption) or an attack (deciphering).

^[2] Though there are techniques to improve this guessing work, it still remains far more difficult discovering than multiplying them.

^[3] The first inspiration was to look at the tree of the tau conjecture, an infinite tree rooted in the number 1, whose other nodes consist of integers resulting in one binary operation of sum, subtraction, or multiplication between previous nodes, possibly one node operated with itself. The theory's goal relates to the depth, in this tree, in which each integer first appears. It is apparently hard to find large numbers in low branches (even if we relax the need for it), but is it immediate to check if a given sequence of operations indeed produces a given result.

^[4] This is surely not the most natural approach, but by adopting this, one ensures that this byte filling (called padding)…

1. Conceals the size of the padding (differently, for example of ciphertext stealing) and obscures the end of the message, thus rendering chosen-plaintext attacks more difficult;
2. Enhances a distribution of bits as close to uniform as possible;

If the last blocks of every message were known to be systematically biased in a far from uniform distribution, an attacker could exploit this fact to do a statistical cryptanalysis, for any given sample of messages would be statistically more representative than otherwise. In other words, the last blocks being statistically less diverse, they become they become the weakest links of the message.

^[5] Make no mistake: this greatest common divisor is Gaussian, while the previous is real.

^[6] …which is not perfect, because it easily gives away the fact that the last three components are proportional to 1, 2, and 4. But, again, for the sake of simplicity, we will ignore this detail.

^[7] …which is so complex that there are a few notorious cases of failure to implement and maintain protocols based on it.

^[8] Here, we will not adopt Rocha's approach of a multiple linear combinations block, which also allows us to randomly permute the bis to obscure them even more.

^[9] Though not totally random. Its transpose must span the subspace generated by the vector $ e_1 = (1,0,…,0) $.