Guida introduttiva al sistema crittografico SRVB

introduzione

La sicurezza delle informazioni è un affascinante campo di conoscenza che può coinvolgere qualsiasi cosa, dall'informatica teorica all'ingegneria del software, e persino osservare la psicologia dell'errore umano.

La crittografia è ormai uno dei tanti eroi tecnologici anonimi della nostra vita quotidiana. I social network, il web banking, l'intelligence militare e qualsiasi altro sistema informativo che si occupi di informazioni sensibili si basano fortemente sulla crittografia. La crittografia ci consente di avere la privacy, che alcuni considerano il 12° diritto umano.

Questo articolo ti fornirà un'introduzione ai principi alla base dei crittosistemi a chiave pubblica e ti introdurrà al Santana Rocha-Villas Boas (SRVB), un crittosistema sviluppato dall'autore dell'articolo e dal Prof. Daniel Santana Rocha. Nel momento in cui scrivo, gli autori dell'algoritmo stanno preparando una campagna che include una ricompensa finanziaria per chiunque riesca a decifrare il codice. Poiché l'articolo tratterà in dettaglio la funzionalità dell'algoritmo, questo è il posto migliore per iniziare la ricerca del premio. Maggiori informazioni sono disponibili sul sito SRVB.

Che cos'è un criptosistema?

La crittografia è qualsiasi metodo per ostacolare l'interpretabilità di un messaggio, pur consentendo un modo per interpretarlo in modo fattibile purché venga fornita un'istruzione specifica, che di solito è la cosiddetta "chiave". Sebbene questa sia una definizione molto ampia che includa anche le prime tecniche, vale la pena ricordare che questa non copre tutto ciò che c'è per la sicurezza delle informazioni.

Si prevede che la corsa tecnologica tra i metodi di crittografia e i modi per decifrarli non avrà mai un vincitore definitivo. Ci si aspetta che ogni nuova generazione innalzi gli standard di sicurezza delle informazioni e crittoanalisi, che è l'insieme di tecniche per decifrare/interrompere sistematicamente i messaggi crittografati, ovvero aggirare la sicurezza o la crittografia.

Affinché un crittosistema (data la tecnica di crittografia) sia considerato sicuro dai suoi utenti, deve ricevere l'approvazione della comunità internazionale di esperti e quindi essere pubblicamente noto, il che è noto come principio di Kerckhoffs. Tuttavia, proprio questa condizione espone il sistema al controllo della comunità mondiale di crittoanalisi, che cercherà di escogitare modi per violare sistematicamente le crittografie.

Come si può rendere un determinato processo di crittografia sufficientemente segreto da consentire solo agli agenti previsti di decrittografarlo, e allo stesso tempo sufficientemente pubblico da consentire alla comunità mondiale di crittoanalisi di attestarne la solidità? La risposta è un componente che è un elemento chiave di Cryptology: la chiave. Una chiave di un crittosistema è un parametro per gli algoritmi di crittografia o decrittografia o entrambi. Mantenendo segreti i parametri, piuttosto che la famiglia di algoritmi, è possibile soddisfare entrambi i requisiti contraddittori. A condizione che la famiglia di parametri sia sufficientemente ampia (possibilmente infinita) e si possa dimostrare che ciascuno dei suoi componenti ha proprietà adeguate, non sarà possibile per gli aggressori determinare i parametri semplicemente mediante ispezione.

Infine, affinché una chiave funzioni in modo efficace, deve essere facilmente prodotta ma quasi impossibile da indovinare. Con la potenza di calcolo dei computer odierni, un computer avrebbe bisogno di meno tempo per decifrare una chiave generata da un essere umano di quanto qualsiasi essere umano avrebbe bisogno anche solo per immaginarla, oltre al fatto che generare chiavi in ​​quel modo non è comunque conveniente. Per questo motivo, le chiavi tendono ad essere generate da un algoritmo.

Un algoritmo di generazione di chiavi non deve creare output prevedibile/riproducibile come risultato dell'uso tipico. Poiché gli algoritmi eseguono procedure senza alcun processo intelligente, la domanda diventa come farlo. La risposta sta trasformando algoritmi di generazione di chiavi in ​​mappe che trasformano una grande quantità di bit veramente casuali in chiavi. Bit veramente casuali possono essere acquisiti dal sistema operativo, che li genera dall'incertezza nell'universo. Alcune fonti potrebbero essere il movimento del mouse, le latenze dei pacchetti di rete o persino l'hardware dedicato, a seconda dell'applicazione.

Crittosistemi a chiave pubblica

Preparati a essere sorpreso ancora una volta, perché ora introdurremo un concetto che apparentemente contraddice ciò che abbiamo appena detto: la chiave pubblica.

Finora abbiamo assistito alla creazione di una comunicazione sicura dopo che i parametri segreti (chiavi) sono stati scambiati in modo sicuro, ma rimane il problema dello scambio dei parametri su un canale pubblico. In questo momento introdurremo un concetto che risolve un problema leggermente più palpabile: la creazione di un canale sicuro.

Supponiamo che Alice stia lavorando con Bob e che vogliano proteggere le loro interazioni di lavoro utilizzando la crittografia. Possono incontrarsi e scambiarsi le loro chiavi di crittografia dando a vicenda un'unità flash USB con le loro chiavi su di esse. Ma cosa succede se Alice e Bob si trovano in continenti diversi. Come stabilire un canale sicuro dove non ce ne sono?

L'invio di chiavi via e-mail non sarebbe un'opzione, dal momento che la loro concorrente Eve può intercettare lo scambio e utilizzare le proprie chiavi per leggere tutti i dati crittografati in seguito. Se avessero un altro canale digitale attraverso il quale trasmettere questi dati sensibili, non avrebbero bisogno della crittografia, e quindi delle chiavi, in primo luogo. Anche l'invio della chiave tramite posta fisica potrebbe essere intercettato, poiché all'inizio è necessario lo scambio di informazioni riservate. Inviare una chiave steganografata nascondendosi all'interno di altri dati sarebbe intelligente, ma inutile a meno che il mittente non sia sicuro che il destinatario, e solo il destinatario, sia a conoscenza dell'esistenza di un tale messaggio e sappia come estrarlo. Per caso, la consapevolezza dell'esistenza di un messaggio insieme alla descrizione di come estrarre la chiave dai dati è di per sé un tipo di chiave, che ci riporta al punto di partenza.

La soluzione è ideare un crittosistema per il quale il parametro di crittografia non è sufficiente per costruire in modo fattibile il messaggio originale ^[1] , e tenere per sé il parametro che consentirebbe di interpretare il messaggio. Chiamiamo quel parametro la chiave privata. Sulla base della chiave privata, è possibile generare in modo fattibile una serie di parametri per uno strumento di crittografia senza che quei nuovi parametri siano in grado di rivelare quale sia la chiave privata. Quel set di parametri può essere condiviso pubblicamente, perché non è così importante chi può crittografare qualcosa, purché solo una persona possa decrittografarlo. Poiché questo insieme di parametri per lo strumento di crittografia può essere reso pubblico, viene chiamato chiave pubblica.

La crittografia in cui le chiavi di crittografia e decrittografia differiscono e la prima non può essere utilizzata in modo fattibile per dedurre la seconda, è chiamata crittografia asimmetrica, mentre la crittografia simmetrica è ciò che abbiamo quando quelle chiavi sono le stesse o sono facilmente deducibili l'una dall'altra.

Alice invia a Bob la sua chiave pubblica, che può essere utilizzata solo per crittografare cose che solo lei può decifrare (con la sua chiave privata, che conserva privatamente) e, al contrario, Bob invia ad Alice la sua chiave pubblica, che può essere utilizzata solo per crittografare le cose che solo lui può decifrare (tramite la sua chiave privata, che conserva anche privatamente). Ma come si può pubblicare un parametro per un algoritmo di crittografia da cui non si può dedurre l'esatto algoritmo inverso?

La risposta sta nel campo della matematica più vicino alla programmazione, la teoria della complessità computazionale. Chiunque abbia approfondito abbastanza i problemi matematici ha sentito parlare di trasformazioni che sono facili da fare in un modo, ma difficili da fare inversamente. Nel calcolo, ad esempio, trovare una derivata da manuale è in genere un esercizio semplice, mentre fare l'inverso (come risolvere qualsiasi integrale leggermente non banale o ODE o PDE fisica da manuale, ad esempio) richiede un processo più investigativo per ipotizzare prima famiglie di funzioni che sono garantiti (o almeno plausibili) per contenere le soluzioni e risolvere problemi inversi per trovare soluzioni da queste famiglie.

Un esempio che viene effettivamente utilizzato nel crittosistema RSA è moltiplicare grandi numeri primi rispetto a fattorizzare il prodotto risultante senza già conoscere i fattori. Fare la moltiplicazione è banale, ma il factoring richiede di indovinare casualmente ^[2] i fattori primi, che hanno centinaia di cifre. Una proprietà importante dell'operazione è la necessità di una buona scalabilità. L'aggiunta di alcune cifre sulla dimensione dei numeri primi in RSA risulterà in una chiave che richiede migliaia di volte più operazioni per essere decifrata, aggiungendo un piccolo aumento di complessità al processo di crittografia. In parole povere, il prodotto dei numeri primi viene utilizzato per la crittografia, mentre la coppia di fattori primi viene utilizzata per la decrittazione.

Con tutto questo in mente, diamo un'occhiata a come funziona il crittosistema SRVB.

L'algoritmo sottostante - Esame di SRVB

Il problema della somma dei sottoinsiemi

Come qualsiasi altro crittosistema a chiave pubblica, SRVB si basa sulla difficoltà di risolvere un particolare problema che è facile da produrre. Nel caso di SRVB, è il problema della somma dei sottoinsiemi, che può essere descritto come segue:

Dato il numero intero $w$ e $v_1, \cdot \cdot \cdot, v_N \in Z$ trova la sequenza $b_1, \cdot \cdot \cdot, b_N \in {0,1}$, tale che $ \sum_ {i = 1}^{N} v_i b_i = w $.

Chiaramente, questo problema può essere prodotto selezionando casualmente N interi, scegliendo casualmente un sottoinsieme di essi e sommando questo sottoinsieme, il che è banale.

Una ricerca a forza bruta avrebbe una complessità di $ O( N * 2^N ) $, calcolando per ogni combinazione di valori dei $b$s. Un approccio più efficiente è stato fornito da Horowitz e Sahni nel 1972, con una complessità di $ O ( N * 2 ^ {N / 2} ) $. Il problema è almeno altrettanto difficile se sostituiamo $b$s e $w$ con $k$ vettori dimensionali di interi. Il regno in cui questo problema più difficile deve essere tenuto, tuttavia, deve anche avere un isomorfismo con un anello in cui si verifica una versione più semplice dello stesso problema, come vedremo in seguito. Per questo motivo, SRVB sfrutta il problema della somma dei sottoinsiemi all'interno di interi gaussiani, dove $ k = 2 $.

C'è un caso speciale in cui questo problema diventa facile da calcolare attraverso l'uso di un algoritmo avido. Se ordiniamo i fattori di scala di una sequenza $ v_1, \cdot \cdot \cdot, v_N $ in cui ogni intero nella sequenza è maggiore della somma di tutti gli interi precedenti ($ \forall i , \sum_{j= 1}^{i-1} v_j < v_i $), si potrebbe usare un approccio avido per trovare la sequenza b in tempo lineare. Una sequenza con le proprietà descritte è chiamata sequenza supercrescente .

Ecco una semplice descrizione della soluzione golosa per questo caso:

1. Inizia con $ i = N $, il fattore attualmente osservato, e $ w' = w $, il resto di $w$

2. Se il fattore di scala corrente è troppo grande per adattarsi a ciò che resta di $w$, ovvero $ v_i > w'$, impostare $b_i = 0$ e continuare con il passaggio successivo. Altrimenti sappiamo che il fattore di scala deve essere nella sequenza (poiché il resto dei fattori è minore di $v_i$) e impostiamo $b_i = 1$.

3. $ w' \Freccia sinistra w' - v_i * b_i$, $i \Freccia sinistra i - 1$. Se $i > 0$, torna al passaggio 2.

4. Verifica che, ora, $w' == 0$, altrimenti il ​​problema era danneggiato

Questo funziona perché sappiamo che tutti i moltiplicatori più piccoli di quello attualmente osservato non possono coprire collettivamente tanta (sotto)somma $ w' $ quanto il moltiplicatore corrente può. Quindi, se la somma rimanente è maggiore del fattore corrente, sappiamo per certo che tutti i fattori seguenti insieme non riusciranno a sommarlo senza l'aiuto del fattore corrente. D'altra parte, poiché tutti i moltiplicatori sono positivi, se il fattore corrente $ v_i $ è maggiore della somma rimanente $ w' $, l'aggiunta di qualsiasi altro fattore farebbe superare ulteriormente $ w' $.

Impostiamo una notazione per il resto dell'articolo. Scegliamo $ v_1, \cdot \cdot \cdot, v_n $ e $w$ come fattori e somma della sequenza supercrescente, mentre $ u_1, \cdot \cdot \cdot, u_n $ e $y$ saranno le parametri disponibili forniti per recuperare $ b_1, \cdot \cdot \cdot, b_n $.

Con una sequenza $ u_1, \cdot \cdot \cdot, u_n $ selezionata in modo che non sia super-aumentato e il numero $y$ è pubblicamente disponibile, non vengono fornite pubblicamente informazioni sufficienti per recuperare la sequenza $ b_1, \cdot \cdot \cdot , b_n $. Tuttavia, se c'è una sequenza supercrescente $ v_1, \cdot \cdot \cdot, v_n $ che potrebbe prendere il posto della sequenza $ u_1, \cdot \cdot \cdot, u_n $, si potrebbe usare questa sequenza per risolvere il problema con un approccio avido.

Di seguito mostreremo come funziona.

Uso di somme di sottoinsiemi in un crittosistema precedente

Nel 1978, Ralph Merkle e Martin Helman, hanno escogitato un modo per sfruttare questi due paradigmi dello zaino e la linearità dell'operazione del modulo per costruire la connessione tra le due sequenze descritte nella sezione precedente, concependo così un Criptosistema a chiave pubblica. L'idea era di trasformare lo zaino facile (quello costituito dal vettore sovracrescente degli interi) in quello duro (quello privo di questa proprietà) mediante un'operazione lineare (il modulo) con operandi segreti. La trasformazione consiste nel moltiplicare ogni $v_i$ per $\theta$ e prendere il resto di questo prodotto per $\alpha$, dove $\alpha \gt \sum_{i=1}^N v_i$ e $\gcd (\alpha, \theta) = 1$ (due vincoli che saranno presto giustificati). Il risultato, la sequenza $u_1, \ldots, u_N$, non aumenta più e può essere considerato uno zaino rigido .

Una permutazione casuale della sequenza $u_1, \ldots, u_N$ verrebbe data alla parte che vuole crittografarci e inviarci un messaggio. La permutazione viene eseguita in modo che una terza parte abbia più difficoltà a indovinare quale sia la sequenza originale di superaumento. I blocchi di bit di un messaggio vengono utilizzati come coefficienti $b_1, \ldots, b_N$. La crittografia viene eseguita moltiplicando la sequenza di chiavi con questa sequenza di coefficienti e sommando le moltiplicazioni in un risultato, che chiameremo $y$. Solo il proprietario della chiave privata può trasformare $y$ nel corrispondente $w$ che si otterrebbe se questi stessi blocchi $b_1, \ldots, b_N$ fossero stati moltiplicati per gli interi facili (la sequenza $v_1, \ldots , v_N$). Ciò avviene moltiplicando $y$ per $\theta^{-1}$, l'inverso moltiplicativo del modulo $\theta$ $\alpha$ (la cui esistenza dipende da quella condizione di $\gcd(\alpha, \ theta) = 1$). In altre parole, $(\theta * \theta^{-1}) \bmod \alpha = 1$. Dopodiché, calcoliamo $w = (y * \theta^{-1}) \bmod a$. Il motivo per cui è garantito il funzionamento è la linearità del modulo , cioè che la combinazione lineare dei resti è uguale al resto della combinazione lineare.

Se applichiamo consecutivamente la definizione di $u$, l'anello quoziente, e la proprietà di linearità dell'operatore modulo, vediamo la corrispondenza:

$ \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 & = \ sinistra[ \sum_{i=1}^N b_i * v_i \right] * \theta \bmod \alpha \newline & = w * \theta \bmod \alpha \end{align} $

E così la somma facile $w$ può essere recuperata moltiplicando entrambi i membri per $\theta^{-1}$ e prendendo il modulo con $\alpha$. Per fare ciò, è necessario conoscere sia $\alpha$ che $\theta$ (che consentono di calcolare facilmente $\theta^{-1}$), che devono essere mantenuti privati ​​come parti della chiave privata.

Un unico vincolo, $\alpha \gt \sum_{i=1}^N v_i$, è stato lasciato ingiustificato ed ecco la spiegazione: l'uguaglianza tra la seconda e la terza riga consiste in un'uguaglianza tra le classi residue del quoziente anello di interi modulo $\alpha$. In altre parole, afferma solo l'uguaglianza del resto dei membri quando divisa per $\alpha$, che non è una condizione sufficiente per l'uguaglianza dei membri stessi . Di conseguenza, è possibile mappare più di un vettore di valori $b$ in un singolo $y$, il che viene evitato limitando la somma parziale massima possibile (cioè la somma di tutti i lotti $v_i$) $w_{max}$ a essere inferiore a $\alpha$ per qualsiasi combinazione di valori $b$.

Come ogni altra istanza della vita quotidiana, la conoscenza completa di tutte le ipotesi è spesso impossibile e mai facile. Di conseguenza, dobbiamo fare affidamento sull'intuizione matematica nel giudicare se un crittosistema è sicuro da usare, il che non ci fornisce garanzie reali. Sei anni dopo la sua creazione, il crittosistema MH è stato interrotto da un attacco di A. Shamir. Ci furono molti altri tentativi di rianimare MH, molti dei quali fallirono.

Il criptosistema Santana Rocha - Villas Boas (SRVB).

Nel 2016, dopo alcuni brainstorming con l'autore di questo articolo sulle possibilità di un criptosistema di diversa ispirazione ^[3] , Daniel Santana Rocha ha avuto l'idea di sostituire $\theta$ e $\alpha$ con numeri interi gaussiani. Per ragioni più tecniche, questo approccio porta alla resistenza contro il suddetto attacco di Shamir.

Ha anche concepito un bit block composto da molti passaggi della combinazione lineare precedentemente descritta di uno zaino rigido . In ognuno di essi, alla fine della sequenza, verrebbe aggiunto un nuovo intero (gaussiano), equivalente a uno, maggiore della somma di tutti i precedenti, mentre il più piccolo attualmente verrebbe eliminato.

Un vincolo diverso ma elegantemente analogo si applica a $\alpha$, che ora è un intero gaussiano. Abbiamo bisogno di $w_{max} \leq \vert\alpha\vert^2$. Il motivo è molto difficile da formalizzare, ma fortunatamente può essere facilmente intuito da una descrizione elegante:

Immagina un reticolo quadrato nel piano dei numeri complessi, il cui lato è un'ipotenusa di un triangolo rettangolo di cateti aeb, parallelo all'asse reale e immaginario. Un esempio di tale reticolo è riportato di seguito. Gli interi guassiani modulo $\alpha = a + bi$ possono essere rappresentati da punti situati all'interno di tale reticolo. All'interno di tale reticolo ci sono $\vert\alpha\vert^2$ punti distinti. Se scegliamo un $\alpha$ abbastanza grande, possiamo adattare tutte le combinazioni lineari dello zaino facile.

Questa è la rappresentazione grafica dell'isomorfismo $f : Z/n \rightarrow Z[i]/(\alpha)$, dove $n = 13$ e $\alpha = a + bi = 3 + 2i$ (notare che $ n$ e $\alpha$ soddisfano effettivamente $n = \vert \alpha \vert ^ 2 = a^2 + b^2 $ come richiesto). I punti rappresentano gli interi gaussiani, cioè i numeri complessi $a + bi$, dove $a$ e $b$ sono interi. Come di consueto, l'asse orizzontale rappresenta la parte reale, mentre quello verticale rappresenta la parte immaginaria. Pertanto, spostare un punto a destra oa sinistra equivale rispettivamente ad aggiungere +1 o -1 al valore corrente. Allo stesso modo, spostare un punto verso l'alto o verso il basso corrisponde rispettivamente all'aggiunta di +i o -i.

I punti rossi sono gli equivalenti di $0 \bmod(\alpha)$. Oltre a questi, abbiamo anche colorato altre 4 paia di punti.

L'isomorfismo $f$ è definito dalla trasformazione dell'$i$esimo elemento della sequenza ciclica $(0,1,2,\cdot\cdot\cdot,10,11,12,0,1,2,\cdot \cdot\cdot)$ nell'$i$esimo elemento della sequenza di punti anche ciclica della figura, che rispetta le seguenti regole:

1. Parte dal punto rosso della prima riga;
2. Segue le frecce orizzontali a destra; salvo che
3. Quando seguendo le frecce si porta la sequenza al di fuori del reticolo, si raggiunge uno dei punti non neri. Invece di andare a quel punto, salta allo stesso punto colorato (cioè il punto equivalente modulo $\alpha$) all'interno dello stesso quadrato; e infine
4. Quando questo punto non nero sembra essere rosso (cosa che accade dopo che tutti gli altri colori sono stati attraversati), la sequenza salta al punto rosso più in alto, riavviando così il ciclo;

Per mappare almeno $Y$ interi naturali, si deve prendere un quadrato con area $\vert\alpha\vert^2$ (dove $\vert\alpha\vert = \sqrt{a^2 + b^2} $ è, per il teorema di Pitagora, la misura del suo lato) almeno altrettanto alta.

Si noti che ogni "salto" cambia il numero di riga $r$ in $r \leftarrow (r + b)(mod a + b)$ se si contano le righe dall'alto in basso e, equivalentemente, in $r \leftarrow (r + a)(mod a + b)$ se si conta dal basso verso l'alto. Quindi, la condizione necessaria e sufficiente per ogni riga (e punto) da percorrere esattamente una volta su ogni ciclo è che la dimensione dei salti sia coprimi con il numero di righe, o, in altre parole, $gcd(a,a + b) = gcd(b,a + b) = 1$. A causa delle proprietà dell'operatore del massimo comun divisore, entrambi sono equivalenti a $gcd(a,b) = 1$.

YS Villas Boas ha notato la necessità di coprimalità di $a$ e $b$. Per preservare la superaumento, ogni nuovo intero $w$ aggiunto alla fine della sequenza deve superare la somma di tutti quelli correnti ($w > \sum_{i=1}^k v_i$). Ha osservato che per ottenere ciò, i loro coefficienti di moltiplicazione $b_i$ dovrebbero essere almeno 1, e quindi ogni bit non potrebbe essere mappato nei coefficienti 0 e 1. Se i coefficienti fossero 0 e 1, solo il blocco composto solo da uno soddisferebbe la sovracrescita. Per questo motivo i bit 0 e 1 sono stati quindi mappati rispettivamente ai coefficienti moltiplicatori 1 e 2.

Infine, e meno banalmente: ad ogni passo della decodifica si trova un nuovo intero $v_1$ come soluzione dell'equazione $b_1 v_1 = v_{n+1} - \sum_{i = 2}^{n} b_i v_i$, dove tutti i $v_i$ e $b_i$ sono noti per $1 < i \leq n$. Dal momento che non sappiamo nemmeno $b_1$, ci ritroviamo con un sistema con un'equazione e due variabili, che ci lascia con un grado di libertà. Per correggere questo, dobbiamo arbitrare un valore positivo (per semplicità, 1) da assegnare sempre a $b_1$, eliminando così l'ambiguità. Quindi, poiché il primo coefficiente è fissato a 1, per codificare $n$ bit ad ogni passo, le nostre sequenze di interi devono essere lunghe $n + 1$ elementi.

Un ultimo aspetto tecnico da risolvere è il caso in cui la dimensione in byte del messaggio non è un multiplo della dimensione del blocco. In altre parole, cosa fare con gli eventuali byte rimanenti dell'ultimo blocco dati in modo che, una volta recuperati i blocchi dati, vengano conservati tutti i byte del contenuto originale, ma non di più? Lo abbiamo risolto ripetendo l'ultimo byte del messaggio una volta. Questa copia è, quindi, seguita da una sequenza casuale in cui ogni componente deve solo essere diverso dal precedente. Pertanto, quando i blocchi di dati vengono recuperati, l'ultimo di essi o, nel peggiore dei casi, quello prima dell'ultimo viene troncato nell'ultima ripetizione di byte. ^[4]

Ora mostriamo un esempio del crittosistema SRVB.

Partiamo dai parametri:

$k = 4$;

$m = 4$;

che produce una lunghezza di blocco di $l = 4 * 4 = 16$, e una sequenza supercrescente di $k + 1 = 5$ interi naturali, che viene operata , cioè combinata linearmente, aggiunta al risultato di questa combinazione lineare, e ridotto agli ultimi $k + 1$ elementi —$m = 4$ volte;

Per semplicità, sia il vettore (supercrescente) di $v_i$:

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

Infatti, la sequenza delle prime cinque potenze di 2, proprio perché questa è la sequenza sovracrescente con cinque elementi e i più piccoli valori strettamente positivi possibili (evitando così uno 0 nella chiave pubblica, che tradirebbe banalmente il corrispondente 0 della sua controparte ).

Come abbiamo detto prima, per $\alpha = a + bi$, gli interi $a$ e $b$ devono essere coprimi, e secondo il nuovo vincolo di cui abbiamo parlato, dobbiamo richiedere che $a^2 + b^2 = \vert\alpha\vert^2 \geq W$. Un rapido calcolo produce $W = 1590$. Poiché $\sqrt{1590} \simeq 39.8$, un $\alpha$ molto conveniente da scegliere sarebbe $\alpha = 39 + 40i$, poiché è abbastanza grande da contenere un isomorfismo con un anello di interi con at almeno 1590 componenti, pur soddisfacendo anche $gcd(a,b)=1$. Inoltre, dobbiamo scegliere un $\theta$ tale che $gcd(a,\theta)=1$ ^[5] e preferibilmente non sia troppo basso, in modo che $(a_1 * \theta) \% \alpha \neq v_1 * \theta$, (anche per evitare di rivelare informazioni). $\theta = 60$ fa il lavoro, ottenendo:

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

Sporciamoci le mani, allora. Prendi il messaggio Hello Toptal! . Per prima cosa lo mappiamo in un array di byte secondo ASCII e la nostra convenzione per il troncamento dei blocchi di dati:

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

Poiché il nostro blocco dati è lungo 16 bit = 2 byte e il nostro messaggio ha 13 caratteri, ci ritroviamo con 7 blocchi dati di 2 byte ciascuno, dove l'ultimo contiene due volte la rappresentazione in bit del carattere '!' . Criptiamo passo dopo passo il primo blocco. Prestare molta attenzione perché i bit di ogni byte sono presi in ordine di significato.

$m=01001000 01100101$

• Primo nibble del primo byte: $(0,0,0,1)\rightarrow(1,1,1,1,2)\cdot(-19-1i,1+38i,3-3i,6-6i,12 -12i)=15+4i$
• Secondo nibble del primo byte: $(0,0,1,0)\rightarrow(1,1,1,2,1)\cdot(1+38i,3-3i,6-6i,12-12i,15+ 4)=49+9i$
• Primo nibble del secondo byte: $(0,1,0,0)\rightarrow(1,1,2,1,2)\cdot(3-3i,6-6i,12-12i,15+4i,49+ 9i)=106-10i$
• Secondo nibble del secondo byte: $(0,1,1,0)\rightarrow(1,1,2,2,1)\cdot(6-6i,12-12i,15+4i,49+9i,106- 10i)=252-2i$

E quindi, abbiamo appena mappato

“Lui” $\Freccia destra(12-12i,15+4i,49+9i,106-10i,252-2i)$

Il resto del messaggio crittografato è il seguente:

“ll” $\Freccia destra(12-12i,21-2i,61-3i,185-31i,367-59i)$

“o “ $\Freccia destra(12-12i,25+33i,65+32i,111+44i,244+124i)$

“A” $\Freccia destra(12-12i,9+10i,46+12i,149+5i,277+31i)$

“pt” $\Freccia destra(12-12i,3+16i,46+12i,73+23i,201+49i)$

“al” $\Freccia destra(12-12i,4+54i,44+53i,117+193i,231+389i)$

"!!" $\Freccia destra(12-12i,4+54i,32+65i,63+92i,121+247i)$

Ora, per la decrittazione, abbiamo $\theta^{-1}=60^{-1}=27+i$:

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

Ora, arriva l'algoritmo avido:

Innanzitutto, sottraiamo ogni fattore contribuente moltiplicato per uno, perché è noto che hanno contribuito almeno una volta per l'ultimo, ottenendo:

• Secondo nibble del secondo byte:

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

$(T \geq 223) = (148 \geq 223) = falso \Freccia destra b_1=0 ; T \freccia sinistra (T - 0 * 223) = 148$

$(T \geq 93) = (148 \geq 93) = vero \Freccia destra b_2 = 1; T \freccia sinistra (T - 1 * 93) = 55$

$(T \geq 47) = 55 \geq 47) = vero \Freccia destra b_3 = 1; T \freccia sinistra (T - 1 * 47) = 8$

$(T \geq 16) = 8 \geq 16) = falso \Freccia destra b_4 = 0; T \freccia sinistra (T - 0 * 16) = 8$

Risultato: 0110;

Resto: 8 (aggiunto all'inizio della sequenza come nuovo elemento più basso);

Drop 527 dal finale della sequenza corrente;

• Primo nibble del secondo byte:

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

$(T \geq 93) = (59 \geq 93) = falso \Freccia destra b_1 = 0; T \freccia sinistra(T - 0 * 93) = 59$

$(T \geq 47) = (59 \geq 47) = vero \Freccia destra b_2 = 1; T \freccia sinistra (T - 1 * 47) = 12$

$(T \geq 16) = (12 \geq 16) = falso \Freccia destra b_3 = 0; T \freccia sinistra (T - 0 8 16) = 12$

$(T \geq 8) = (12 \geq 8) = vero \Freccia destra b_4 = 1; T \freccia sinistra (T - 0 * 12) = 4$

Risultato: 0101;

Resto: 4 (aggiunto all'inizio della sequenza come nuovo elemento più basso);

Drop 233 dalla finale della sequenza corrente;

• Secondo nibble del primo byte:

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

$(T \geq 47) = (18 \geq 47) = falso \Freccia destra b_1 = 0; T \freccia sinistra (T - 0 * 47) = 18$

$(T \geq 16) = (18 \geq 16) = vero \Freccia destra b_2 = 1; T \freccia sinistra (T - 1 * 16) = 2$

$(T \geq 8) = (2 \geq 8) = falso \Freccia destra b_3 = 0; T \freccia sinistra (T - 0 * 8) = 2$

$(T \geq 4) = (2 \geq 4) = falso \Freccia destra b_4 = 0; T \freccia sinistra (T - 0 * 4) = 2$

Risultato: 0100;

Resto: 2 (aggiunto all'inizio della sequenza come nuovo elemento più basso);

Drop 93 dal finale della sequenza attuale;

• Primo nibble del primo byte:

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

$(T \geq 16) = (17 \geq 16) = vero \Freccia destra b_1 = 1; T \freccia sinistra (T - 1 * 16) = 1$

$(T \geq 8) = (1 \geq 8) = falso \Freccia destra b_2 = 0; T \freccia sinistra (T - 0 * 8) = 1$

$(T \geq 4) = (1 \geq 4) = falso \Freccia destra b_3 = 0; T \freccia sinistra (T - 0 * 4) = 1$

$(T \geq 2) = (1 \geq 4) = falso \Freccia destra b_4 = 0; T \freccia sinistra (T - 0 * 2) = 1$

Risultato: 1000;

Resto: 1 (aggiunto all'inizio della sequenza come nuovo elemento più basso);

Drop 47 dal finale della sequenza attuale;

Di conseguenza abbiamo recuperato il data block: “01001000 01100101” contenente i primi due caratteri “He”, del nostro messaggio. Non solo, abbiamo anche recuperato correttamente la nostra sequenza di superincrementi di chiave privata $(1,2,4,8,16)$.

Le altre mappe dei blocchi di dati procedono allo stesso modo.

Confronto con i principali crittosistemi a chiave pubblica

SRVB è:

1. Totalmente gratuito e pubblico;

2. Notevolmente più semplice e facile da comprendere e implementare rispetto a ECC ^[7] ;

3. Abbondante di chiavi e quindi praticamente a costo zero, contrariamente, ad esempio, a RSA, che fa affidamento sui numeri primi, che sono costosi.

Possiamo già riassumere le vulnerabilità più probabili. Dal momento che SRVB discende da MH, è facile sospettare che sarebbe vulnerabile a una generalizzazione dell'attacco Shamir, oa qualche altro che lo rompe. Sebbene l'autore avesse motivo di ritenere che non sarebbe stato così, non è stata ancora fatta alcuna conferma (cosa molto tipica quando si ha a che fare con i criptosistemi).

Qual è il prossimo?

Rocha ha osservato alcune generalizzazioni per gli anelli quozienti da utilizzare, che possono eventualmente portare ad un aumento della complessità della crittoanalisi. Indagheremo anche queste possibilità.

L'oscuramento algebrico lineare

Guarda caso, durante lo sviluppo e la documentazione di SRVB, Villas Boas ha escogitato un altro approccio per migliorare il concetto di crittosistema a chiave pubblica a zaino che non verrà spiegato in molti dettagli qui, in modo che questo articolo non diventi troppo lungo e noioso, ma eccone una scrematura. Se non riesci ad afferrarlo, non preoccuparti, resta sintonizzato per il rilascio del nostro prossimo articolo, in cui entreremo nei dettagli in modo più approfondito: Vedi la somma del sottoinsieme $y$, del, diciamo, $N$ elementi ad anello quoziente $u_i$ (che sono isomorficamente corrispondenti agli interi positivi $v_i$ della sequenza supercrescente, come prima) come moltiplicazione di un vettore riga di questi $u_i$ per un vettore colonna $B$ ( per binario) di zeri e uno ^[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,

dove $b_i \in {0,1}$

Ora, immagina di avere, al posto di questo vettore di $u_i$, a sinistra una matrice V di $n$ per $N$ (con $n < N$), avente $v_i$ (i numeri interi dalla supercrescente sequenza) vettore come (senza perdita di generalità) la sua prima riga e tutte le altre voci riempite di rumore. Si noti che, ora, moltiplicando V per lo stesso vettore di bit B si ottiene un vettore colonna W che ha $w$ come prima voce e rumore negli altri. Ora prendi questa V matrice e moltiplicala per una ^[9] n per n matrice R casuale a sinistra, definendo la matrice n per N P:

P = RV

L'idea è che Bob usi P come sua nuova chiave pubblica. A causa della casualità di R, il vettore

$Y = PB = RV B = RW$

ha l'informazione $w$ oscurata dal rumore in altre righe di V. Bob calcola anche in anticipo e memorizza il vettore di riga S che soddisfa:

$R^TS^T = e_1$

Quando Alice manda Y a Bob, lui trova semplicemente SY, perché:

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

(finora solo definizioni)

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

(Ora, sfruttando l'associatività per annullare le R)

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.

Glossario

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) $.