Introdução ao Criptosistema SRVB

Introdução

A segurança da informação é um campo de conhecimento fascinante que pode envolver desde ciência da computação teórica até engenharia de software, e até mesmo observar a psicologia do erro humano.

A criptografia é agora um dos muitos heróis tecnológicos anônimos de nossa vida diária. Redes sociais, web banking, inteligência militar e qualquer outro sistema de informação que lide com informações confidenciais dependem muito da criptografia. A criptografia nos permite ter privacidade, que alguns consideram o 12º direito humano.

Este artigo fará uma introdução aos princípios por trás dos criptossistemas de chave pública e apresentará o Santana Rocha-Villas Boas (SRVB), um criptosistema desenvolvido pelo autor do artigo e pelo Prof. Daniel Santana Rocha. No momento em que escrevo, os autores do algoritmo estão preparando uma campanha que inclui uma recompensa financeira para quem conseguir decifrar o código. Como o artigo abordará a funcionalidade do algoritmo em detalhes, este é o melhor lugar para começar a busca pelo prêmio. Mais informações estão disponíveis no site do SRVB.

O que é um Criptosistema?

A criptografia é qualquer método para dificultar a interpretabilidade de uma mensagem, enquanto ainda permite uma maneira viável de interpretá-la, desde que uma instrução específica seja fornecida, que geralmente é a chamada “chave”. Embora esta seja uma definição muito ampla que abrange até mesmo as técnicas mais antigas, vale a pena mencionar que isso não abrange tudo o que existe para segurança da informação.

Espera-se que a corrida tecnológica entre métodos de criptografia e formas de decifrá-los nunca tenha um vencedor definitivo. A cada nova geração espera-se elevar os padrões de segurança da informação e criptoanálise, que é o conjunto de técnicas para decifrar/quebrar sistematicamente mensagens criptografadas, ou seja, burlar a segurança ou criptografia.

Para que um sistema criptográfico (dada técnica de criptografia) seja considerado seguro por seus usuários, ele precisa receber a aprovação da comunidade internacional de especialistas e, assim, ser conhecido publicamente, o que é conhecido como princípio de Kerckhoffs. No entanto, essa mesma condição expõe o sistema ao escrutínio da comunidade mundial de criptoanálise, que tentará criar maneiras de quebrar sistematicamente as criptografias.

Como alguém pode tornar um determinado processo de criptografia secreto o suficiente para que apenas os agentes pretendidos possam descriptografá-lo e, ao mesmo tempo, público o suficiente para que a comunidade de criptoanálise do mundo possa atestar sua robustez? A resposta é um componente que é um elemento chave da Criptologia: a chave. Uma chave de um sistema criptográfico é um parâmetro para os algoritmos de criptografia ou descriptografia, ou ambos. Ao manter os parâmetros em segredo, em vez da família de algoritmos, ambos os requisitos contraditórios podem ser alcançados. Desde que a família de parâmetros seja grande o suficiente (possivelmente infinita) e cada um de seus componentes possa ser provado como tendo propriedades adequadas, não será viável para os invasores determinarem os parâmetros apenas por inspeção.

Finalmente, para que uma chave funcione efetivamente, ela deve ser facilmente produzida, mas quase impossível de adivinhar. Com o poder computacional dos computadores de hoje, um computador precisaria de menos tempo para decifrar uma chave gerada por humanos do que qualquer ser humano precisaria imaginar, além do fato de que não é rentável gerar chaves dessa maneira. Por causa disso, as chaves tendem a ser geradas por um algoritmo.

Um algoritmo de geração de chave não deve criar saída previsível/reprodutível como resultado do uso típico. Como os algoritmos realizam procedimentos sem nenhum processo inteligente, a questão é como isso pode ser feito. A resposta é transformar algoritmos geradores de chaves em mapas que transformam uma grande quantidade de bits verdadeiramente aleatórios em chaves. Bits verdadeiramente aleatórios podem ser adquiridos do sistema operacional, que os gera a partir da incerteza no universo. Algumas fontes seriam o movimento do mouse, latências de pacotes de rede ou até mesmo hardware dedicado, dependendo do aplicativo.

Criptosistemas de chave pública

Prepare-se para ser surpreendido mais uma vez, pois agora vamos introduzir um conceito que aparentemente contradiz o que acabamos de dizer: a chave pública.

Até agora, vimos a criação de comunicação segura depois que os parâmetros secretos (chaves) foram trocados com segurança, mas o problema de trocar os parâmetros por um canal público permanece. Neste momento, apresentaremos um conceito que resolve um problema um pouco mais palpável: a criação de um canal seguro.

Suponha que Alice esteja trabalhando com Bob e eles desejam manter suas interações de trabalho seguras usando criptografia. Eles podem se encontrar e trocar suas chaves de criptografia dando um ao outro uma unidade flash USB com suas chaves neles. Mas e se Alice e Bob estiverem localizados em continentes diferentes? Como estabelecer um canal seguro onde não existe nenhum?

O envio de chaves por e-mail não seria uma opção, já que seu concorrente Eve pode interceptar a troca e usar suas chaves para ler todos os dados criptografados posteriormente. Se eles tivessem qualquer outro canal digital através do qual pudessem transmitir esses dados confidenciais, eles não precisariam de criptografia e, portanto, de chaves, em primeiro lugar. O envio da chave por correio físico também pode ser interceptado, pois requer a troca de informações confidenciais para começar. Enviar uma chave esteganografada ocultando-se em outros dados seria inteligente, mas inútil, a menos que o remetente tenha certeza de que o destinatário, e apenas o destinatário, está ciente da existência de tal mensagem e sabe como extraí-la. Acontece que a consciência da existência de uma mensagem juntamente com a descrição de como extrair a chave dos dados é um tipo de chave por si só, o que nos traz de volta à estaca zero.

A solução é desenvolver um sistema criptográfico para o qual o parâmetro de criptografia não seja suficiente para construir de forma viável a mensagem original ^[1] , e manter para si o parâmetro que permitiria a construção da mensagem. Chamamos esse parâmetro de chave privada. Com base na chave privada, é possível gerar um conjunto de parâmetros para uma ferramenta de criptografia sem tornar esses novos parâmetros capazes de revelar qual é a chave privada. Esse conjunto de parâmetros pode ser compartilhado publicamente, porque não é tão importante quem pode criptografar algo, desde que apenas uma pessoa possa descriptografá-lo. Como esse conjunto de parâmetros para a ferramenta de criptografia pode ser tornado público, ele é chamado de chave pública.

A criptografia em que as chaves de criptografia e descriptografia diferem, e a primeira não pode ser usada para deduzir a segunda, é chamada de criptografia assimétrica, enquanto a criptografia simétrica é o que temos quando essas chaves são as mesmas ou são facilmente deduzidas uma da outra.

Alice envia a Bob sua chave pública, que só pode ser usada para criptografar coisas que só ela pode descriptografar (com sua chave privada, que ela mantém em particular) e, inversamente, Bob envia a Alice sua chave pública, que só pode ser usada para criptografar coisas que ele sozinho pode descriptografar (por meio de sua chave privada, que ele também mantém em particular). Mas como é possível publicar um parâmetro para um algoritmo de criptografia do qual não se pode deduzir o algoritmo inverso exato?

A resposta está no campo da matemática mais próximo da programação, a teoria da complexidade computacional. Qualquer um que tenha se aprofundado o suficiente em problemas matemáticos já ouviu falar sobre transformações que são fáceis de fazer de uma maneira, mas difíceis de fazer o inverso. No cálculo, por exemplo, encontrar uma derivada de livro didático normalmente é um exercício direto, enquanto fazer o inverso (como resolver qualquer integral não trivial ou EDO ou EDP física de livro didático, por exemplo) requer um processo mais investigativo de primeiro hipotetizar famílias de funções que são garantidos (ou pelo menos plausíveis) conter a(s) solução(ões) e resolver problemas inversos para encontrar soluções dessas famílias.

Um exemplo que é realmente utilizado no sistema criptográfico RSA é multiplicar grandes primos versus fatorar o produto resultante sem já conhecer os fatores. Fazer a multiplicação é trivial, mas a fatoração exige que você adivinhe aleatoriamente ^[2] os fatores primos, que têm centenas de dígitos. Uma propriedade importante da operação é a necessidade de escalar bem. A adição de alguns dígitos no tamanho dos números primos no RSA resultará em uma chave que requer milhares de vezes mais operações para ser quebrada, ao mesmo tempo em que adiciona um pequeno aumento na complexidade do processo de criptografia. Muito grosso modo, o produto de números primos é usado para criptografar, enquanto o par de fatores primos é usado para descriptografar.

Com tudo isso em mente, vamos dar uma olhada em como funciona o sistema de criptografia SRVB.

O Algoritmo Subjacente - Olhando para o SRVB

O problema da soma do subconjunto

Como qualquer outro sistema criptográfico de chave pública, o SRVB conta com a dificuldade de resolver um problema específico que é fácil de produzir. No caso do SRVB, é o problema da soma do subconjunto, que pode ser descrito da seguinte forma:

Dado o inteiro $w$ e $v_1, \cdot \cdot \cdot, v_N \in Z$ encontre a sequência $b_1, \cdot \cdot \cdot, b_N \in {0,1}$, tal que $ \sum_ {i = 1}^{N} v_i b_i = w $.

Claramente, esse problema pode ser produzido escolhendo aleatoriamente N inteiros, escolhendo aleatoriamente um subconjunto deles e somando esse subconjunto - o que é trivial.

Uma busca de força bruta teria uma complexidade de $ O( N * 2^N ) $, calculando para cada combinação de valores dos $b$s. Uma abordagem mais eficiente foi dada por Horowitz e Sahni em 1972, com uma complexidade de $ O ( N * 2 ^ {N / 2} ) $. O problema é pelo menos tão difícil se substituirmos $b$s e $w$ por vetores $k$-dimensionais de inteiros. O domínio onde este problema mais difícil deve ser mantido, entretanto, deve ter também um isomorfismo com um anel onde ocorre uma versão mais fácil do mesmo problema, como veremos a seguir. Por esta razão, SRVB explora o problema da soma de subconjuntos dentro de inteiros gaussianos, onde $ k = 2 $.

Há um caso especial em que esse problema se torna fácil de calcular através do uso de um algoritmo guloso. Se ordenarmos os fatores de escala de uma sequência $ v_1, \cdot \cdot \cdot, v_N $ em que cada inteiro na sequência é maior que a soma de todos os inteiros que vieram antes dele ($ \forall i , \sum_{j= 1}^{i-1} v_j < v_i $), pode-se usar uma abordagem gulosa para encontrar a sequência b em tempo linear. Uma sequência com as propriedades descritas é chamada de sequência supercrescente .

Aqui está uma descrição simples da solução gananciosa para este caso:

1. Comece com $ i = N $, o fator observado atualmente, e $ w' = w $, o restante de $w$

2. Se o fator de escala atual for muito grande para caber no que resta de $w$, significando $ v_i > w'$, defina $b_i = 0$ e continue para a próxima etapa. Caso contrário, sabemos que o fator de escala precisa estar na sequência (já que o restante dos fatores é menor que $v_i$) e configuramos $b_i = 1$.

3. $ w' \Leftarrow w' - v_i * b_i$, $i \Leftarrow i - 1$. Se $i > 0$, volte ao passo 2.

4. Verifique se, agora, $w' == 0$, caso contrário o problema foi corrompido

Isso funciona porque sabemos que todos os multiplicadores menores do que o atualmente observado não podem cobrir coletivamente tanto da (sub)soma $ w' $ quanto o multiplicador atual pode. Portanto, se a soma restante for maior que o fator atual, sabemos com certeza que todos os seguintes fatores juntos não serão somados sem a ajuda do fator atual. Por outro lado, como todos os multiplicadores são positivos, se o fator atual $ v_i $ for maior que a soma restante $ w' $, adicionar qualquer outro fator faria com que o resultado superasse ainda mais $ w' $.

Vamos configurar uma notação para o resto do artigo. Escolhemos $ v_1, \cdot \cdot \cdot, v_n $ e $w$ para serem os fatores e a soma da sequência supercrescente, enquanto $ u_1, \cdot \cdot \cdot, u_n $ e $y$ serão os valores públicos parâmetros disponíveis que são fornecidos para recuperar $ b_1, \cdot \cdot \cdot, b_n $.

Com uma sequência $ u_1, \cdot \cdot \cdot, u_n $ escolhida de modo que não seja super crescente e o número $y$ esteja disponível publicamente, não há informações suficientes fornecidas publicamente para recuperar a sequência $ b_1, \cdot \cdot \cdot , b_n $. No entanto, se houver uma sequência supercrescente $ v_1, \cdot \cdot \cdot, v_n $ que poderia substituir a sequência $ u_1, \cdot \cdot \cdot, u_n $, pode-se usar essa sequência para resolver o problema com uma abordagem gananciosa.

Abaixo vamos mostrar como isso funciona.

Uso de somas de subconjuntos em um sistema criptográfico anterior

Em 1978, Ralph Merkle e Martin Helman, conceberam uma maneira de explorar esses dois paradigmas da mochila e a linearidade da operação do módulo para construir a conexão entre as duas sequências descritas na seção anterior - concebendo assim um Criptosistema de Chave Pública. A idéia era transformar a mochila fácil (a que consiste no vetor supercrescente de inteiros) na difícil (a que não possui essa propriedade) por meio de uma operação linear (o módulo) com operandos secretos. A transformação consiste em multiplicar cada $v_i$ por um $\theta$ e tomar o restante deste produto por um $\alpha$, onde $\alpha \gt \sum_{i=1}^N v_i$ e $\gcd (\alpha, \theta) = 1$ (duas restrições que em breve serão justificadas). O resultado, a sequência $u_1, \ldots, u_N$, não é mais super crescente e pode ser considerada uma mochila dura .

Uma permutação aleatória da sequência $u_1, \ldots, u_N$ seria dada à parte que deseja criptografar e enviar uma mensagem para nós. A permutação é feita para que um terceiro tenha mais dificuldade em adivinhar qual é a sequência super crescente original. Blocos de bits de uma mensagem são usados ​​como os coeficientes $b_1, \ldots, b_N$. A encriptação é feita multiplicando a sequência de chaves com esta sequência de coeficientes, e somando as multiplicações num resultado, que rotularemos $y$. Somente o dono da chave privada pode transformar $y$ no $w$ correspondente que seria obtido se esses mesmos blocos $b_1, \ldots, b_N$ fossem multiplicados pelos inteiros fáceis (a sequência $v_1, \ldots , v_N$). Isso é feito por meio da multiplicação de $y$ por $\theta^{-1}$, o inverso multiplicativo do módulo $\theta$ $\alpha$ (cuja existência depende dessa condição de $\gcd(\alpha, \ teta) = 1$). Em outras palavras, $(\theta * \theta^{-1}) \bmod \alpha = 1$. Depois disso, calculamos $w = (y * \theta^{-1}) \bmod a$. A razão pela qual isso é garantido para funcionar é a linearidade do módulo , ou seja, que a combinação linear dos restos é igual ao restante da combinação linear.

Se aplicarmos consecutivamente a definição de $u$, o anel quociente e a propriedade de linearidade do operador módulo, vemos a correspondência:

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

E assim a soma fácil $w$ pode ser recuperada multiplicando ambos os lados por $\theta^{-1}$ e tomando o módulo por $\alpha$. Para fazer isso, é preciso conhecer $\alpha$ e $\theta$ (que permitem calcular facilmente $\theta^{-1}$), que devem ser mantidos privados como parte da chave privada.

Uma única restrição, $\alpha \gt \sum_{i=1}^N v_i$, foi deixada injustificada e aqui vai a explicação para ela: A igualdade entre a segunda e a terceira linha consiste em uma igualdade entre as classes de resíduos do quociente anel de inteiros módulo $\alpha$. Em outras palavras, ele só declara a igualdade do restante dos membros quando dividido por $\alpha$, o que não é condição suficiente para a igualdade dos próprios membros . Como resultado, mais de um vetor de valores $b$ pode ser mapeado em um único $y$, o que é evitado limitando o máximo possível subsoma (ou seja, a soma de todas as parcelas $v_i$) $w_{max}$ para ser menor que $\alpha$ para qualquer combinação de valores de $b$.

Assim como qualquer outra instância da vida diária, o conhecimento completo de todas as hipóteses é muitas vezes impossível e nunca fácil. Como resultado, temos que confiar na intuição matemática ao julgar se um criptosistema é seguro de usar, o que não nos fornece garantias reais. Seis anos após sua criação, o criptosistema MH foi quebrado com um ataque de A. Shamir. Houve várias outras tentativas de reviver o MH, muitas das quais também falharam.

Criptosistema Santana Rocha - Villas Boas (SRVB)

Em 2016, após alguns brainstorms com o autor deste artigo sobre possibilidades ^[3] de um criptosistema de inspiração diferente, Daniel Santana Rocha teve a ideia de substituir $\theta$ e $\alpha$ por inteiros gaussianos. Por razões mais técnicas, essa abordagem leva à resistência contra o já mencionado ataque de Shamir.

Ele também concebeu um bloco de bits consistindo de muitas etapas da combinação linear descrita anteriormente de uma mochila dura . Em cada um deles, um novo inteiro (gaussiano), equivalente a um, maior que a soma de todos os anteriores seria adicionado ao final da sequência, enquanto o menor atualmente seria descartado.

Uma restrição diferente e ainda elegantemente análoga se aplica a $\alpha$, que agora é um inteiro gaussiano. Exigimos $w_{max} \leq \vert\alpha\vert^2$. A razão é muito difícil de formalizar, mas felizmente pode ser facilmente intuída a partir de uma descrição elegante:

Imagine uma rede quadrada no plano dos números complexos, cujo lado é uma hipotenusa de um triângulo retângulo de catetos a e b, paralelos aos eixos real e imaginário. Um exemplo de tal rede é dado abaixo. Inteiros guassianos módulo $\alpha = a + bi$ podem ser representados por pontos localizados dentro de tal rede. Dentro de tal rede existem $\vert\alpha\vert^2$ pontos distintos. Se escolhermos um $\alpha$ grande o suficiente, podemos encaixar todas as combinações lineares da mochila fácil.

Esta é a representação gráfica do isomorfismo $f : Z/n \rightarrow Z[i]/(\alpha)$, onde $n = 13$ e $\alpha = a + bi = 3 + 2i$ (note que $ n$ e $\alpha$ realmente satisfazem $n = \vert \alpha \vert ^ 2 = a^2 + b^2 $ conforme necessário). Os pontos representam os inteiros gaussianos, ou seja, os números complexos $a + bi$, onde $a$ e $b$ são inteiros. Como de costume, o eixo horizontal representa a parte real, enquanto o vertical representa a parte imaginária. Assim, mover um ponto para a direita ou para a esquerda equivale a adicionar +1 ou -1 ao seu valor atual, respectivamente. Da mesma forma, mover um ponto para cima ou para baixo corresponde a adicionar +i ou -i, respectivamente.

Os pontos vermelhos são os equivalentes a $0 \bmod(\alpha)$. Além destes, também colorimos mais 4 pares de pontos.

O isomorfismo $f$ é definido pela transformação do $i$th elemento da sequência cíclica $(0,1,2,\cdot\cdot\cdot,10,11,12,0,1,2,\cdot \cdot\cdot)$ no $i$th elemento da sequência de pontos também cíclica na figura, que segue as seguintes regras:

1. Começa a partir do ponto vermelho da primeira linha;
2. Segue as setas horizontais direitas; exceto aquilo
3. Ao seguir as setas leva a sequência para fora da rede, ela atingiria um dos pontos não pretos. Em vez de ir para esse ponto, ele pula para o mesmo ponto colorido (ou seja, o ponto equivalente módulo $\alpha$) dentro do mesmo quadrado; e finalmente
4. Quando esse ponto não-preto passa a ser vermelho (o que acontece depois que todas as outras cores passaram), a sequência salta para o ponto vermelho mais alto, reiniciando assim o ciclo;

Para mapear pelo menos $Y$ inteiros naturais, deve-se pegar um quadrado com área $\vert\alpha\vert^2$ (onde $\vert\alpha\vert = \sqrt{a^2 + b^2} $ é, pelo teorema de Pitágoras, a medida de seu lado) pelo menos tão alta.

Observe que cada “salto” muda o número da linha $r$ para $r \leftarrow (r + b)(mod a + b)$ se contarmos as linhas de cima para baixo e, equivalentemente, para $r \leftarrow (r + a)(mod a + b)$ se contar de baixo para cima. Portanto, a condição necessária e suficiente para que cada linha (e ponto) seja percorrida exatamente uma vez em cada ciclo é que o tamanho dos saltos seja coprime com o número de linhas, ou, em outras palavras, $gcd(a,a + b) = mdc(b,a + b) = 1$. Devido às propriedades do máximo operador divisor comum, ambos são equivalentes a $gcd(a,b) = 1$.

YS Villas Boas percebeu a necessidade de coprimalidade de $a$ e $b$. Para preservar a supercrescente, cada novo inteiro $w$ adicionado no final da sequência precisa superar a soma de todos os atuais ($w > \sum_{i=1}^k v_i$). Ele observou que para conseguir isso, seus coeficientes multiplicadores $b_i$ teriam que ser pelo menos 1, e assim, cada bit não poderia ser mapeado nos coeficientes 0 e 1. Se os coeficientes fossem 0 e 1, apenas o bloco composto apenas de uns satisfaria a superaumento. Por esta razão, os bits 0 e 1 foram então mapeados respectivamente para os coeficientes multiplicadores 1 e 2.

Finalmente, e menos trivialmente: durante cada etapa da decodificação, um novo inteiro $v_1$ deve ser encontrado como solução da equação $b_1 v_1 = v_{n+1} - \sum_{i = 2}^{n} b_i v_i$, onde todos os $v_i$ e $b_i$ são conhecidos por $1 < i \leq n$. Como também não conhecemos $b_1$, acabamos com um sistema com uma equação e duas variáveis, o que nos deixa com um grau de liberdade. Para corrigir isso, temos que arbitrar um valor positivo (para simplificar, 1) a ser sempre atribuído a $b_1$, eliminando assim a ambiguidade. Assim, como o primeiro coeficiente é fixado em 1, para codificar $n$ bits em cada passo, nossas sequências de inteiros devem ter $n + 1$ elementos.

Um detalhe técnico final a ser resolvido é o caso em que o tamanho em bytes da mensagem não é um múltiplo do tamanho do bloco. Em outras palavras, o que fazer com os possíveis bytes restantes do último bloco de dados para que, uma vez recuperados os blocos de dados, todos os bytes do conteúdo original sejam preservados, mas não mais do que eles? Resolvemos isso repetindo o último byte da mensagem uma vez. Esta cópia é, então, seguida por uma sequência aleatória na qual cada componente é requerido apenas para ser diferente do anterior. Assim, quando os blocos de dados são recuperados, o último deles ou, no pior caso, o anterior ao último é truncado na última repetição de bytes. ^[4]

Agora vamos mostrar um exemplo do sistema criptográfico SRVB.

Começamos com os parâmetros:

$k = 4$;

$m = 4$;

que produz um comprimento de bloco de $l = 4 * 4 = 16$, e uma sequência supercrescente de $k + 1 = 5$ inteiros naturais, que é operada - ou seja, linearmente combinada, anexada com o resultado dessa combinação linear, e reduzido aos seus últimos $k + 1$ elementos —$m = 4$ vezes;

Para simplificar, seja o vetor (supercrescente) de $v_i$:

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

De fato, a sequência das cinco primeiras potências de 2, só porque esta é a sequência supercrescente com cinco elementos e os menores valores estritamente positivos possíveis (evitando assim um 0 na chave pública, que trivialmente daria o correspondente 0 de sua contraparte ).

Como dissemos anteriormente, para $\alpha = a + bi$, os inteiros $a$ e $b$ devem ser coprimos, e de acordo com a nova restrição que mencionamos, temos que solicitar que $a^2 + b^2 = \vert\alpha\vert^2 \geq W$. Um cálculo rápido rende $W = 1590$. Como $\sqrt{1590} \simeq 39.8$, um $\alpha$ muito conveniente para ser escolhido seria $\alpha = 39 + 40i$, pois é grande o suficiente para acomodar um isomorfismo com um anel de inteiros com at menos 1590 componentes, enquanto também satisfaz $gcd(a,b)=1$. Além disso, precisamos escolher um $\theta$ tal que $gcd(a,\theta)=1$ ^[5] e de preferência que não seja muito baixo, de modo que $(a_1 * \theta) \% \alpha \neq v_1 * \theta$, (também para evitar dar informações). $\theta = 60$ faz o trabalho, gerando:

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

Vamos sujar as mãos, então. Leve a mensagem Hello Toptal! . Primeiro, mapeamos em uma matriz de bytes de acordo com ASCII e nossa convenção para truncar blocos de dados:

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

Como nosso bloco de dados tem 16 bits = 2 bytes e nossa mensagem tem 13 caracteres, acabamos com 7 blocos de dados de 2 bytes cada, onde o último contém duas vezes a representação de bits do caractere '!' . Vamos criptografar o primeiro bloco passo a passo. Preste muita atenção porque os bits de cada byte são tomados em ordem de significado.

$m=01001000 01100101$

• Primeiro nibble do primeiro byte: $(0,0,0,1)\rightarrow(1,1,1,1,2)\cdot(-19-1i,1+38i,3-3i,6-6i,12 -12i)=15+4i$
• Segundo nibble do primeiro byte: $(0,0,1,0)\rightarrow(1,1,1,2,1)\cdot(1+38i,3-3i,6-6i,12-12i,15+ 4)=49+9i$
• Primeiro nibble do segundo byte: $(0,1,0,0)\rightarrow(1,1,2,1,2)\cdot(3-3i,6-6i,12-12i,15+4i,49+ 9i)=106-10i$
• Segundo nibble do segundo 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 assim, acabamos de mapear

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

O resto da mensagem criptografada é a seguinte:

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

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

"Para" $\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)$

“!!” $\Seta para a direita(12-12i,4+54i,32+65i,63+92i,121+247i)$

Agora, para a descriptografia, temos $\theta^{-1}=60^{-1}=27+i$:

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

Agora, vem o algoritmo ganancioso:

Primeiro, subtraímos cada fator contribuinte multiplicado por um, porque se sabe que eles contribuíram pelo menos uma vez para o último, obtendo-se:

• Segundo nibble do segundo byte:

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

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

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

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

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

Resultado: 0110;

Restante: 8 (adicionado ao início da sequência como novo elemento mais baixo);

Solte 527 do final da sequência atual;

• Primeiro nibble do segundo byte:

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

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

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

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

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

Resultado: 0101;

Restante: 4 (adicionado ao início da sequência como novo elemento mais baixo);

Solte 233 do final da sequência atual;

• Segundo nibble do primeiro byte:

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

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

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

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

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

Resultado: 0100;

Restante: 2 (adicionado ao início da sequência como novo elemento mais baixo);

Solte 93 do final da sequência atual;

• Primeiro nibble do primeiro byte:

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

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

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

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

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

Resultado: 1000;

Restante: 1 (adicionado ao início da sequência como novo elemento mais baixo);

Solte 47 do final da sequência atual;

Como resultado, recuperamos o bloco de dados: “01001000 01100101” contendo os dois primeiros caracteres “He”, da nossa mensagem. Além disso, também recuperamos corretamente nossa sequência de supercrescimento de chave privada $(1,2,4,8,16)$.

Os outros mapas de blocos de dados seguem o mesmo caminho.

Comparação com os principais criptossistemas de chave pública

SRV é:

1. Totalmente gratuito e público;

2. Consideravelmente mais simples e fácil de entender e implementar do que ECC ^[7] ;

3. Abundante em chaves e, portanto, praticamente sem custo, ao contrário, por exemplo, do RSA, que se baseia em números primos, que são caros.

Já podemos resumir as vulnerabilidades mais prováveis. Como o SRVB descende do MH, é fácil suspeitar que seria vulnerável a uma generalização do ataque de Shamir, ou algum outro que o quebre. Embora o autor tivesse motivos para acreditar que não seria esse o caso, ainda não foi feita nenhuma confirmação disso (o que é muito típico quando se trata de criptossistemas).

Qual é o próximo?

Rocha observou algumas generalizações para os anéis de quociente a serem utilizados, o que possivelmente pode levar a um aumento na complexidade da criptoanálise. Vamos investigar essas possibilidades também.

O obscurecimento algébrico linear

Acontece que, durante o desenvolvimento e documentação do SRVB, Villas Boas surgiu com mais uma abordagem para aprimorar o conceito de criptossistema de chave pública da mochila que não será detalhada aqui, para que este artigo não fique muito longo e cansativo, mas aqui está um resumo dele. Se você não conseguir entendê-lo, não se preocupe, fique atento ao lançamento do nosso próximo artigo, no qual entraremos em detalhes mais detalhadamente: Veja a soma do subconjunto $y$, do, digamos, $N$ elementos de anel quociente $u_i$ (que são isomorficamente correspondentes aos inteiros positivos $v_i$ da sequência super crescente, como antes) como uma multiplicação de um vetor linha desses $u_i$ por um vetor coluna $B$ ( para binário) de zeros e uns ^[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,

onde $b_i \in {0,1}$

Agora, imagine que, ao invés desse vetor de $u_i$, você tenha, à esquerda, uma matriz V $n$ por $N$ (com $n < N$), tendo o $v_i$ (os inteiros da supercrescente sequência) como (sem perda de generalidade) sua primeira linha e todas as outras entradas preenchidas com ruído. Observe que, agora, multiplicando V pelo mesmo vetor de bits B, você obtém um vetor de coluna W que tem $w$ como sua primeira entrada e ruído nas outras. Agora, pegue esta matriz V e multiplique-a por uma matriz aleatória ^[9] n por n R à esquerda, definindo a matriz n por N P:

P = RV

A ideia é que Bob use P como sua nova chave pública. Por causa da aleatoriedade de R, o vetor

$Y = PB = RV B = RW$

tem a informação $w$ obscurecida pelo ruído em outras linhas de V. Bob também calcula antecipadamente e armazena o vetor linha S que satisfaz:

$R^TS^T = e_1$

Quando, Alice envia Y para Bob, ele apenas encontra SY, porque:

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

(até agora apenas definições)

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

(Agora, explorando a associatividade para cancelar os 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.

Glossário

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