Como a criptografia pode envolver aleatoriedade?

8

Se um algoritmo de criptografia pretende converter uma string para outra, que pode ser descriptografada de volta ao original, como esse processo pode envolver qualquer aleatoriedade?

Certamente, isso deve ser determinístico; caso contrário, como a função de descriptografia poderia saber quais fatores estavam envolvidos na criação da cadeia criptografada?

CJ7
fonte
3
Por favor, não faça perguntas idênticas em vários sites do Stack Exchange, como este no Crypto.SE .
Paŭlo Ebermann 27/05

Respostas:

5

Pode haver mais de um texto cifrado que mapeia de volta para o mesmo texto simples. Em termos matemáticos, o algoritmo de criptografia deve ser injetivo para que você possa recuperar o texto sem formatação para o texto cifrado, mas isso não impede que o texto cifrado codifique mais informações que o texto sem formatação.

Como um exemplo concreto, considere modos de operação de codificação de bloco, como CBC , CTR ou OFB . Todos esses modos envolvem um IV (vetor de inicialização), além do texto simples, o algoritmo da cifra de bloco e sua chave. (Para CTR, o IV é chamado noncece, mas desempenha um papel semelhante.) A função de criptografia é determinística para um determinado IV. O IV, por outro lado, pode ser escolhido aleatoriamente (para CTR, deve ser escolhido aleatoriamente). Assim, a menos que o protocolo especifique um método determinístico de escolha do IV (como uma constante acordada), o IV é enviado juntamente com o texto cifrado. De fato, a saída do software de criptografia geralmente consiste no IV seguido pelo texto cifrado stricto sensu. O IV em si é enviado em texto simples; não contém (não deve) nenhuma informação confidencial.

Como outro exemplo, considere o modo PKCS1.5 ("esquema de preenchimento") do RSA (definido no PKCS # 1 versão 1.5 - consulte as páginas 22 a 25 do PKCS # 1 v2.1 ). Simplificando um pouco, esse modo consiste em concatenar uma sequência aleatória com a mensagem e aplicar a operação de exponenciação. O texto cifrado é onde é concatenação, é a mensagem e é uma string de preenchimento cuja maioria dos bits é aleatória. Para recuperar a mensagem do texto cifrado , aplique a operação de descriptografia bruta e divida em preenchimento (que é descartado) e mensagem.(PM)emodnMPCCdmodnC

Gilles 'SO- parar de ser mau'
fonte
4

Não apenas os esquemas de criptografia podem ter aleatoriedade, mas em alguns casos (por exemplo, criptografia de chave pública), eles devem ser randomizados. Isso não é um problema, pois exigimos que um esquema de criptografia esteja correto , ou seja, para qualquer mensagem e qualquer chave ela mantenha através da aleatoriedade .mk

Pr[ DEC( ENC(k,m,R) )=m]=1
R

A razão pela qual os esquemas de chave pública devem ser aleatórios deriva da maneira como definimos a segurança: não queremos que o texto cifrado vaze nenhuma informação sobre a mensagem criptografada. O exemplo clássico é o seguinte. Suponha que é a chave pública e secreta, respectivamente, e que o adversário intercepte uma mensagem criptografada enviada a alguma unidade no campo. O adversário sabe que a mensagem é "ATAQUE" ou "RETIRO", mas não sabe qual. Uma coisa que o adversário pode fazer é criptografar as duas mensagens usando o público . deixe e . Se(pk,sk)cpkcA=ENCpk("ATTACK ")cR=ENCpk("RETREAT")ENCé determinístico, o adversário pode descobrir a mensagem com certeza comparando com e .ccAcR

A maneira como essa noção é formalmente definida é conhecida como segurança semântica :

Um esquema de criptografia é semanticamente seguro se algum adversário não puder vencer o jogo a seguir com probabilidade visivelmente maior que :A1/2

  1. Um desafiante gera chaves e envia a chave pública ao adversário.C(pk,sk)pk
  2. A escolhe duas mensagens de igual comprimento e e as fornece a .m0m1C
  3. C seleciona uniformemente um pouco e envia de volta .b{0,1}ENC(mb)
  4. A precisa dizer qual mensagem foi criptografada: ou , ou seja, ele precisa gerar o bit .m0m1b

(Estou omitindo o parâmetro de segurança , que é fundamental para definir "insignificante" ou "perceptível"; precisamos assumir que a geração das chaves depende de e que a vantagem tem acima é insignificante em , ou seja, menor que ) κκA1/2κκω(1)

Tocou.
fonte
podemos adicionar uma sequência aleatória ao final da entrada antes de pré-formar a criptografia para evitar o problema e sempre ter , ou seja, a condição pode ser mais forte do que a que você declarou no topo . DEC(ENC(k,m,R))=m
Kaveh
3

Você não indicou que tipo de criptografia estamos discutindo, mas deixe-me apontar o que é realmente necessário para a segurança dos protocolos cartográficos (além do que é indicado em outras respostas).

O que realmente precisamos é isto: as chaves devem ser geradas aleatoriamente (isso pode ser feito em colaboração como em criptografia de chave pública como RSA ou por uma entidade como em criptografia de chave privada). A aleatoriedade da chave garante que um adversário não possa prever as chaves (e usá-las para quebrar o protocolo). Enquanto as chaves parecerem aleatórias para o adversário, o protocolo estará seguro. Freqüentemente, as chaves são geradas por um algoritmo aleatório e depois são fornecidas às partes, enquanto os algoritmos de criptografia e descriptografia não são randomizados, mas determinísticos.

Lembre-se também de que ser randomizado não significa que o processo não seja invertível. Um exemplo simples é o seguinte: dado , gere aleatoriamente , produza . Para inverter, podemos produzir a primeira parte do par.xrx,r

Kaveh
fonte
seu exemplo é importante: sem preenchimento aleatório, a baunilha RSA é insegura. com estofamento aleatório, RSA pode ser provado ter propriedades de segurança agradáveis no modelo de oráculo aleatório
Sasho Nikolov
1

Os algoritmos de criptografia e descriptografia podem ser randomizados, desde que você possa provar algum teorema de que a criptografia seguida pela descriptografia fornecerá a mensagem original na maioria das vezes .

Por que alguém iria querer esse esquema de criptografia? Porque: 1) existem situações em que não queremos estar certos o tempo todo, mas apenas 99999999 vezes a cada 100000000 e 2) permitindo que erros tão pequenos muitas vezes melhorem algo mais (como eficiência) em uma quantidade desproporcional.

Vinayak Pathak
fonte
3
Embora a criptografia probabilística exista, elas são do lado exótico. Muitos algoritmos de criptografia todos os dias envolvem aleatoriedade sem serem probabilísticos.
Gilles 'SO- stop be evil'
@ Gilles: Uma distinção importante a fazer.
Raphael
0

Só para citar um exemplo, na criptografia RSA , você precisa gerar dois primos e e um inteiro que será usado para criar o seu público e chaves privadas.pqe

Se você gerar algum desses valores de maneira determinística, a geração deles poderá ser reproduzida, comprometendo potencialmente sua criptografia. Se esses números são gerados de maneira aleatória, isso não é problema.

Atualizar

Como um exemplo mais específico da resposta de Ran G. , você pode dar uma olhada na criptografia Elliptic Curve , onde o algoritmo requer um parâmetro aleatório (geralmente chamado , ou ) para criptografar e descriptografar mensagens. Se o mesmo parâmetro "aleatório" for usado mais de uma vez, a chave poderá ser calculada a partir de duas mensagens criptografadas. Este foi o problema / premissa do hack do PlayStation 3 do ano passado .dkr

Pedro
fonte
1
Essa é a aleatoriedade na geração de chaves, que duvido que seja a questão: qualquer geração de chave deve envolver aleatoriedade, caso contrário, a chave é previsível (ou derivada e não gerada).
Gilles 'SO- stop be evil'
Não acho que esse seja o lugar para a randomização que o OP tem em mente. As chaves são fornecidas e estáticas para a criptografia (en | de). Como você escolhe sua chave é independente disso.
Raphael
@ Gilles: Eu não consideraria isso tão claro. Os valores , e geralmente são armazenados em um formato criptografado, com uma senha escolhida pelo usuário. Estritamente falando, eles são a chave, mas, da perspectiva do usuário , são apenas valores aleatórios gerados ao digitar sem sentido no teclado e não têm nada a ver com a senha cuidadosamente escolhida. pqe
23312 Pedro
@ Pedro Eu não entendo como o seu último comentário está relacionado à pergunta. Mesmo da perspectiva dos arquivos de chave (que não vejo na pergunta), a chave evidentemente não é gerada aleatoriamente, é derivada do arquivo de chave e da senha.
Gilles 'SO- stop be evil'