🧛 🙍🏼 📔 Problema de mochila em criptografia 👨🏻‍🎨 👩🏻‍🚒 👩🏿‍🎨

O problema da mochila (Knapsack Problem) é o problema que levou os criptógrafos americanos Ralph Merkle e Martin Hellman a desenvolver o primeiro algoritmo de criptografia de chave pública.

Mais adiante no programa

Formulação do problema da mochila (+ por que uma mochila?)
Desafios fáceis e difíceis
Exemplos de
História

O que é criptografia de chave pública?

, , «», .

. , , , .

: , .

, - !

O primeiro algoritmo de chave pública geral usou o algoritmo da mochila.

Com base na definição de sistemas de chave pública, são necessárias duas chaves para criptografar (e descriptografar) uma mensagem com êxito. O destinatário "legal" da mensagem conhece a chave secreta

А

enquanto o remetente possui outra chave pública

B

$B$ ...

O que fazer se uma chave pública se tornar conhecida por um invasor?

Há uma resposta: a chave pública deve ser obtida da chave secreta usando uma transformação ( função unidirecional )

f

$f$ com as duas propriedades a seguir:

$B = f(A)$ sabendo A, é fácil calcular a própria função

$A = f^{-1} (B)$ , e é difícil calcular a função inversa

O que é "fácil" e "difícil"?

.

«» , . ..

n

$n$ , —

t \propto n^{a}

$t \propto n^a$ ,

a

$a$ — . , .

«» . , , .

..

n

$n$ ,

t \propto 2 n

$t \propto 2n$ , , .

O problema da mochila é formulado da seguinte forma

O conjunto (vetor mochila)

A = (a_{1}, . . ., a_{n})

$A = (a_1, ... , a_n)$ É um conjunto ordenado de

n

$n$ (

n > 2),

$n > 2),$ números naturais distintos

a_{i}

$a_i$ ... Que haja um número

k

$k$ - inteiro e positivo. A tarefa é encontrar tal conjunto

a_{i}

$a_i$ de modo que no total eles dão exatamente

k

$k$ ...

Na versão mais famosa do problema da mochila, é necessário descobrir se um determinado par tem

(A, k)

$(A , k)$ decisão. Na variante usada em criptografia, você precisa desta entrada

(A, k)

$(A , k)$ construir uma solução sabendo que tal solução existe. Ambas as opções são NP-completas.

Analogia da mochila

No caso mais simples

k

$k$ denota o tamanho (capacidade) da mochila, e cada um dos números

a_{i}

$a_i$ indica o tamanho (peso) de um item que pode ser embalado em uma mochila. A tarefa é encontrar esse conjunto de itens de forma que a

mochila fique completamente cheia.

Ou seja, imagine que você tem um conjunto de pesos 1, 6, 8, 15 e 24, você precisa levar uma mochila com peso 30.

Em princípio, uma solução pode sempre ser encontrada pela pesquisa exaustiva de subconjuntos

А

e verificando qual de suas somas é

k

$k$ ... No nosso caso, isso significa força bruta

2^{5} = 32

$2^5 = 32$ subconjuntos (incluindo o conjunto vazio). Isso é bastante viável.

Mas e se houver várias centenas de números $a_i$ ?

No nosso exemplo, n = 5, para não complicar a apresentação. Em condições reais, um exemplo terá, digamos, 300

a_{i} - х

$a_i-$ ... A questão aqui é que nenhum algoritmo conhecido que tenha uma complexidade significativamente menor em comparação com a pesquisa exaustiva. Pesquisar entre

2^{300}

$2^{300}$ subconjuntos não podem ser processados. Na verdade, o problema da mochila é conhecido como NP-completo ... Problemas NP-completos são considerados difíceis de calcular.

A função atende aos requisitos especificados?

Nós definimos a função

f (x)

$f(x)$ Da seguinte maneira. Qualquer número

0 \leq x \leq 2 n - 1

$0 ≤ x ≤ 2n − 1$ pode ser dado por uma representação binária de

n

$n$ bits, onde zeros à esquerda são adicionados, se necessário. Agora vamos definir

f (x)

$f(x)$ como um número obtido de

A

$A$ resumindo tudo isso

a_{i}

$a_i$ que o bit correspondente em notação binária

x

$x$ é igual a 1.

Ou seja,

f (1) = f (0 . . . 001) = a_{n}

$f(1) = f(0 . . . 001) = a_n$

f (2) = f (0 . . . 010) = a_{n - 1}

$f(2) = f(0 . . . 010) = a_{n−1}$

f (3) = f (0 . . . 011) = a_{n - 1} + a_{n}

$f(3) = f(0 . . . 011) = a_{n−1} + a_n$

. . .

$...$

Função

f (х)

$f( )$ foi determinado

n -

$n-$ conjunto

A

$A$ ... Obviamente, se formos capazes de calcular

x

$x$ do

f (x)

$f(x)$ , então praticamente ao mesmo tempo o problema da mochila será resolvido:

x

$x$ sua representação binária é imediatamente calculada, o que por sua vez dá os componentes do conjunto

A

$A$ incluído na soma para

f (x)

$f(x)$ ... Por outro lado, o cálculo

f (x)

$f(x)$ do

x

$x$ é leve. Como o problema da mochila é NP-completo,

f (x)

$f(x)$ é um bom candidato para uma função unilateral. Claro, é preciso exigir que $n$ era grande o suficiente, não diga menos $200$ ...

Encriptação

Texto simples

(. plain text) — , , . ( ).

Você pode criptografar de duas maneiras:

A cifra da mensagem é obtida elevando-se os elementos deste vetor de mochila à potência dos bits correspondentes da mensagem criptografada e depois multiplicando todos os resultados, ou seja, se $A = (2,3,5)$ e a mensagem $(100)$ , então a cifra será o número $2^1*3^0*5^0=2$ ... Esta é uma forma multiplicativa .
A cifra da mensagem é obtida multiplicando-se os elementos deste vetor de mochila pelos bits correspondentes da mensagem criptografada e somando todos os resultados, ou seja, se $A = (2,3,5)$ e a mensagem $(100)$ , então a cifra será o número $2^ *1+3^ *0+5^ *0= 2$ ... Este método é denominado aditivo .

Exemplo

Para criptografar texto simples em representação binária, ele é dividido em blocos de comprimento

n

$n$ (por exemplo, você pode representar o peso 30 com o binário 11110). Acredita-se que um indica a presença de algum item na mochila e zero indica sua ausência.

A criptografia de mochila fornece uma boa abordagem para a criação de chaves públicas e privadas, onde a chave privada é fácil de usar e a chave pública é difícil de descobrir.

Assim, podemos criar um sistema onde: o problema "difícil" servirá como a

chave pública ; com ele, você pode criptografar facilmente e é impossível descriptografar a mensagem.

uma chave privada - o problema "fácil" servirá como usando-o, você pode descriptografar a mensagem facilmente. Sem a chave privada, você tem que resolver o "difícil" problema da mochila.

Problema "fácil"

Vetor de mochila supercrescendo

A = (a_{1}, . . ., a_{n})

$A=(a_{1},...,a_{n})$ ,

Σ_{i = 1}^{j - 1} a_{i} < a_{j}

$Σ_{i=1}^{j-1} a_{i} < a_{j}$

j = 2, . . ., n

$j=2,...,n$ , . .

Para vetores supercrescentes Α, o problema da mochila é facilmente resolvido. Essa. a mochila é fácil de montar.

Vamos dar um exemplo:

Algoritmo

.

, , . , .
.
(1)-(2) .

, .

Problema "difícil"

É muito mais difícil decifrar o problema de uma mochila não muito grande .

Um algoritmo, que usa uma mochila de chave privada grande e uma mochila de chave pública não grande, foi criado por Merkle e Hellman.

Eles fizeram isso pegando a tarefa da mochila superdimensionada e transformando-a em uma tarefa não superdimensionada.

(Merkle e Hellman, usando aritmética modular, desenvolveram uma maneira de transformar uma mochila "leve" em uma "rígida")

Crie uma chave pública

Vários conceitos importantes

$(x, mod m)$ $x$ $m$ ,

$x$ — , $m > 1$ , [x/m] — ,
$x = (x, m o d m) + [x / m] * m$
$x = (x, mod m) + [x/m]*m$

$A$ , $m > max A$ $t < m$ , $(t, m) = 1$ .

$B = (b_1, . . . , b_n)$ , $b_i = (ta_i, modm)$ , $i = 1, . . . , n$ , , B A m t , , $(m, t)$ .

$(t, m) = 1$

$t^{−1} = u$ , ,

$t u \equiv 1 (m o d m)$
$tu ≡ 1 (mod m)$

$1 ≤ u < m$ . , $A$ $B$

$m, u$ .

$m > max A$

$m > Σ_{i=1}^{n} a_{i}$ , , $B$ $A$ $m, t$ .

— , , , .

O criador do criptossistema escolhe tal sistema

A, t, m, B

$A, t, m, B$ aquele vetor

A

$A$ está supercrescendo e

B

$B$ vem de

A

$A$ forte multiplicação modular em relação a

m, t

$m, t$ ... Vetor

B

$B$ expandido como chave de criptografia e blocos binários de comprimento

n

$n$ enviado para o designer como números

β

$β$ obtido usando o vetor

B

$B$ ...

O interceptor de mensagem deve resolver o problema da mochila para entrar

(B, β)

$(B, β)$ ... O criador do criptosistema calcula

α = (u β, m o d m)

$α = (uβ, modm)$

e resolve o problema de entrada na mochila

(A, α)

$(A, α)$ ... Por que tudo isso funciona é

mostrado no seguinte lema.

Lemma . Vamos fingir que

A = (a_{1}, . . ., a_{n})

$A = (a_1, . . . , a_n)$ vetor supercrescimento e vetor

B

$B$ derivado de

A

$A$ forte multiplicação modular em relação a

m, t

$m, t$ ... Suponha ainda que

u \equiv t^{- 1} (m o d m)

$u ≡ t^{−1} (mod m)$ ,

β

$β$ - um número natural arbitrário e

α = (u β, m o d m)

$α = (uβ,modm)$ ... Então, as seguintes afirmações são verdadeiras.

(i) O problema da mochila

(A, α)

$(A, α)$ solucionável em tempo linear. Se houver uma solução, ela será única.

(ii) O problema da mochila

(B, β)

$(B, β)$ tem no máximo uma solução.

(Iii) Se houver uma solução para entrar

(B, β)

$(B, β)$ então ele corresponde à única solução de entrada

(A, α)

$(A, α)$ ...

prova (p. 104)

Exemplo

Considere uma sequência de supercrescimento; por exemplo, {1, 2, 4, 10, 20, 40}. O módulo deve ser maior do que a soma de todos os números na sequência, por exemplo 110. O multiplicador não deve ter divisores comuns com o módulo. Então, vamos escolher 31.

Portanto, calculamos a chave pública: {31, 62, 14, 90, 70, 30} e a chave privada - {1, 2, 4, 10, 20,40}.

Agora vamos tentar enviar uma sequência binária: 100100111100101110

Alguns dos benefícios das chaves públicas

Ao usar um criptosistema de chave pública, ambas as partes não se encontram, podem nem mesmo se conhecer e usar qualquer tipo de comunicação.

Comprimento da chave. Na criptografia simétrica, se a chave for maior do que a mensagem original, nenhum ganho real é obtido. Quanto aos criptosistemas de chave pública, o comprimento da chave de criptografia não importa, uma vez que é público e público. Portanto, o comprimento da chave de descriptografia não é tão importante (o destinatário apenas a armazena em um local secreto)

História

Por muito tempo, os criptossistemas de mochila foram considerados os mais atraentes e promissores devido à sua NP-completude e alta velocidade de criptografia e descriptografia. Muitos esquemas usam o problema da mochila (em várias variações), aqui estão apenas alguns deles: o problema da mochila compacta, o problema da mochila multiplicativa, o problema da mochila modular, o problema da capa de matriz, o problema de fatoração de grupo ...

Infelizmente, a maioria deles é vulnerável a ataques. Descobriu-se que não é trivial projetar um criptossistema seguro baseado no problema da mochila, embora o problema seja conhecido como NP-completo. A maioria dos criptossistemas de mochila foi hackeada. Apesar disso, em contraste com a fatoração inteira e o logaritmo discreto, o problema geral da mochila (solução) é um problema NP-completo comprovado.

Algumas pessoas pensam que um dia um algoritmo de tempo polinomial pode ser inventado para resolver problemas de fatoração de inteiros e logaritmos discretos, enquanto o problema da mochila ainda será NP-completo.

Existem vários "MAS" aqui.

Primeiro, NP-completude é baseada na análise do pior caso e, segundo, NP-completude são características de um problema geral, não de um caso específico. Isso significa que se considerarmos a complexidade média, o problema da mochila pode ser simples.

O material foi preparado com base nesta literatura:

(1) A. Salomaa. Criptografia de chave pública. - Springer-Verlag, 1990. - p. 75-82, pp. 101-111

(2)Min Kin Lai. Knapsack Cryptosystems : Past and Future - University of California, 2001

(3) Baocang Wang, Qianhong Wu, Yupu Hu. Um esquema de criptografia probabilística baseado em mochila. 2007

(4) - (5)

Problema de mochila em criptografia