Fundamentos of Cryptography Dr. Ashish Choudhury Department of Computer Science International Institute of Information Technology – Bangalore Lecture – 47 Hybrid Public Key Cryptosystem Welcome to this lecture. O plano para esta palestra é o seguinte. (Consulte Slide Time: 00:36) Nesta palestra, introduziremos o esquema de criptografia de chave pública da Hybrid e introduziremos o paradigma KEM/DEM, e veremos uma instanciação de KEM baseada em CDH no modelo de oracle de Random e de instanciação baseada em DDH do KEM no modelo padrão. (Consulte O Slide Time: 00 :49) Então, deixe o ’ começar com a motivação do Hybrid Public-Key Ciphers e antes de fazer isso, deixe-nos comparar o esquema de criptografia de chave pública com um esquema de criptografia de chave secreta. Imagine, somos dados um esquema de criptografia de chave pública, Π pub, e somos dados um esquema simétrico de criptografia, Π priv, então se considerarmos o esquema de criptografia de chave pública, o acordo chave não é em todo um desafio. É isso que toda a motivação para o nascimento do processo de criptografia pública. Se eu sou um receptor, é suficiente para mim apenas anunciar a minha público-chave no domínio público. Quem quiser criptografar uma mensagem e enviá-la para mim, pode escolher minha chave pública, criptografar a mensagem e enviá-la para mim. Por outro lado, tínhamos visto que o acorto-chave é o maior desafio no domínio de chave simétrica. Até e a não ser que a chave comum seja estabelecida entre o emissor e o receptor, não podemos utilizar nenhuma das primitivas de chave simétrica. Se considerarmos o esquema de criptografia de chave pública, o lado negativo há o espaço da mensagem tem que ser um grupo finito ou uma estrutura algébrica finita, que a maioria dos casos é o grupo, o que é meio que uma restrição porque, na prática, o espaço de mensagens deve ser um conjunto de cordas de bits. Por outro lado, o espaço de mensagens na palavra-chave simétrica são strings binárias. Não exigimos nenhuma estrutura algébrica sofisticada a partir do espaço de mensagem subjacente para a segurança geral dos meus esquemas de criptografia de chave simétrica. Se considerarmos esquemas de criptografia de chave pública, eles são computacionalmente muito pesados porque temos que realizar exponenciações modulares por exemplo em função RSA e em esquema de criptografia El Gamal. Realizar exponenciações modulares é muito computacionalmente caro e pesado em comparação com o processo de criptografia, processo de decriptografia que usamos em esquema de criptografia de chave simétrica, que são superrápidos e executa operações que são de operações XOR. Da mesma forma, o esquema de criptografia de chave pública, a expansão de texto cifrado é enorme, por exemplo, se você vir o esquema de criptografia El Gamal, o texto simples que você deseja pode criptografar é um único elemento de grupo, mas o texto cifrado consiste em dois elementos de grupos e RSA acolchado, a quantidade de mensagem, que você acaba criptografando é muito curta em comparação com a quantidade de aleatoriedade que você realmente está preenchendo. Por outro lado, no mundo chave simétrica, a expansão de texto cifrado pode ser tão mínima quanto possível usando qualquer um dos chamados modos seguros de operação de cifras de blocos. Então, agora podemos ver ter tanto prós como contras de esquema de criptografia de chave publicitário, esquemas de criptografia simétrica, e o que podemos fazer é, podemos pensar de alguma forma combinando esses dois processos de forma genérica e obter um tipo híbrido de processo de criptografia onde no processo de criptografia híbrida, que chamamos como EncHyb. O remetente escolhe uma chave aleatória para o esquema de criptografia de chave simétrica e criptografa-lo usando o processo de criptografia de chave pública, a saber, ele criptografa a chave aleatória k, que ele selecionou e criptografa-lo usando a chave pública do receptor e uma vez que o texto simples está disponível com o remetente, a criptografia real do texto simples acontece usando um processo de criptografia de chave simétrica usando a chave aleatória, que foi colhida pelo remetente. Se fizermos isso, o que está acontecendo aqui é basicamente toda a eficiência do processo de criptografia híbrida torna-se quase a do processo de criptografia de chave simétrica porque a mensagem real que estamos criptografando fica criptografada usando um processo de criptografia de chave simétrica. A carga de pagamento extra que estamos pagando aqui é para criptografar a chave simétrica que é usada para criptografar o texto simples real usando um processo de criptografia de chave pública. No entanto em princípio sintaticamente todo esse processo híbrido ainda será considerado como uma instanciação do processo de criptografia de chave pública porque a chave para a criptografia de chave simétrica que o remetente está usando está sendo criptografada por um processo de criptografia de chave pública. Então, esse é o que é a motivação geral para projetar Cifradores de Chave Pública Hybrid. (Consulte O Slide Time: 5:01) Para deixar meu ponto mais claro, vamos considerar uma instanciação da Cipher público-chave Hybrid El Gamal. Por isso, deixe-me relembrar a sintaxe da cifra de chave pública Hybrid El Gamal, digamos que a Seetha quer dizer para configurar para seu parâmetro público, sua chave pública e chave secreta, por isso a descrição pública, que está disponível para todos é a descrição do grupo cíclico, do gerador e do tamanho do grupo. Para fazer a configuração de chave, o que a Seetha faz é, você pode imaginar que ela faz sua parte do protocolo de troca de chave Diffie Hellman uma vez por todas para cada potencial Ram. Para cada remetente potencial que deseja criptografar uma mensagem e enviar para a Seetha. Então, ela escolhe seu aleatório α do set Zq a saber: 0 q-1, e que é uma chave secreta e uma chave pública, que é g α, que está disponível no domínio público, e esta se pode imaginar como a contribuição da Seetha ’ s para a chave geral Diffie-Hellman, que ela quer estabelecer com cada remetente qualquer em potencial neste mundo. Agora imagine que há um remetente, que tem um texto simples m, que ele quer criptografar e agora este texto simples é um pouco string, ele não precisa ser um elemento de grupo. Assim, ao contrário do processo de criptografia El Gamal onde o texto simples real, que remetente poderia criptografar e enviar para a Seetha deveria ser um elemento de grupo, agora o texto simples é um bit string. Agora, para criptografar este texto simples m, o que o emissor faz é, ele escolhe um elemento aleatório do grupo que são anotados por e ele criptografa esta mensagem usando o processo de criptografia El Gamal. Assim, computa-se o texto cifrado c1, c2 onde c1 pode ser interpretado como sender ’ s contribuição para o protocolo de troca de chave Diffie-Hellman, a saber g β, onde β é uma captação aleatória, e c2 é a criptografia real deste aleatório usando a chave comum Diffie-Hellman g α β. Ora, essa não é a criptografia da mensagem, então até agora o que remete fez basicamente o c1, c2, que remetente enviou para a Seetha é uma criptografia do aleatório, mas o objetivo do remetente é criptografar o texto simples m, portanto, o que fazemos aqui é assumimos que além da descrição do grupo cíclico, gerador, ordem de grupo e assim por diante, assumimos que temos uma descrição de uma função de derivação chave H publicamente disponível e assumimos que a função de derivação de chave mapeia os elementos do grupo g para o espaço chave do esquema de criptografia de chave simétrica, esse remetente agora vai usar. Então agora, o que o remetente vai fazer é, remetente sabe que ao enviar c1, c2, para a Seetha. O Sender sabe que a Seetha também vai acabar conseguindo a chave comum g α β e supondo que a assunção DDH seja verdadeira no grupo subjacente, esta chave g α β vai ser um elemento aleatório do grupo a partir do ponto de vista de um adversário computacionalmente delimitado. Assim, o que remete agora pode sim, pode derivar uma chave de cadeia de bits para o processo de criptografia simétrica aplicando uma função de derivação de chave a este elemento aleatório e essa chave é usada para agora criptografar o texto simples m, que é um string de bits e que é uma criptografia real do texto simples m, que remetente quer criptografar. A decriptografia no Seetha ’ s end acontece da seguinte forma. Assim, para decriptografia, a Seetha também precisa recuperar o mesmo, que remetente usou para derivar a chave simétrica k e pode ser obtido por decriptografando c1, c2 conforme a sintaxe do esquema de criptografia El Gamal e uma vez é recuperada pela Seetha, o que a Seetha pode fazer, ela também pode aplicar a mesma função de derivação de chave publicamente disponível no e uma vez é recuperada, ela pode descriptografar o componente c do texto cifrado conforme o algoritmo de decriptografia do processo de criptografia de chave simétrica e recuperar m. Então, é assim que se pode interpretar uma versão híbrida da cifra de El Gamal public-key. Por isso, pictorialmente o que está acontecendo é aqui que como disse anteriormente c1, c2 é a criptografia de chave pública da chave simétrica, enquanto que o componente c aqui é a criptografia de chave privada real do texto simples. No entanto, se você pausar aqui por um momento, a ideia acima de criptografar o elemento de grupo aleatório por remetente e derivar uma chave a partir dela é um overkill. Então, o que está acontecendo aqui é remetente está usando um elemento de grupo aleatório, criptografando-o como um todo usando o processo de criptografia El Gamal e, em seguida, derivando que uma chave simétrica. Então isso é um supermate aqui. Uma observação próxima diz que é suficiente para o remetente apenas enviar g β. Não precisa ter que enviar c2. É suficiente para o remetente apenas enviar g β. Porque o remetente sabe que se envia g β, o que pode ser revisto como se ele remete está enviando sua parte da mensagem de protocolo de troca de chave Diffie-Hellman, então sabe que ao enviar g β, tanto Seetha quanto Ram acabarão concordando com g α β e assumindo que DDH assunção é verdadeira no grupo subjacente, sabemos que g α β será aleatório no ponto de vista do adversário.Daí a chave k pode ser derivada do g α β em vez de derivar a chave do elemento aleatório, porque se fizermos isso em vez de usar a abordagem que vimos até agora, fazemos uma poupança aqui. Não precisamos ter que escolher o elemento aleatório e não precisamos criptografar, daí não precisamos enviar c2, e tamanho geral do texto cifrado vai ficar significativamente reduzido e isso também levará a economizar na largura de banda também, pois se não precisarmos enviar o c2 isso significa que não precisamos enviar um elemento de grupo extra para criptografar a mensagem. (Consulte O Slide Time: 11:22) Mesmo que tenhamos visto uma instanciação da cifra Hybrid El Gamal aqui, verifica-se que essa abordagem é um exagero. Então o que vamos fazer agora, como agora somos motivados pela discussão aqui que, basta o remetente aqui apenas enviar g β e derivar uma chave da g β, o que nós vamos fazer é agora vamos derivar um novo primitivo, que chamamos como Key-Encapsulation mecanismo ou KEM e então veremos que como podemos obter criptografia Hybrid mais eficiente usando este KEM. Então, para deixar meu ponto claro o modo de na ï ter a criptografia Hybrid que vimos agora é justamente no contexto do Hybrid El Gamal é o seguinte. Então, na ponta da criptografia o que estávamos fazendo é que o remetente estava escolhendo uma chave aleatória para a chave simétrica e ele estava ficando criptografado pela chave pública do receptor para derivar o texto cifrado c, que pode ser considerado como uma criptografia da chave simétrica. E a criptografia real da mensagem foi feita usando a chave k e esta foi uma espécie de uma abordagem de dois estágios, em que fomos escolhendo primeiramente nossa chave simétrica aleatória e depois usando-a para o processo de criptografia de chave pública. Uma abordagem mais eficiente será feita usando um primitivo, o qual vamos definirá-lo em breve o qual chamamos como mecanismo de encapsulamento de chave onde ambas essas duas coisas são feitas em um único tiro em um único estágio. E a vantagem aqui é que não só ela é conceitualmente mais simples, mas em muitos casos é mais eficiente e para entender que como exatamente a KEM vai ser eficiente em comparação com essa abordagem de dois estágios, você pode ver o que temos visto há pouco no contexto do Hybrid El Gamal. O na ï ve way de implementar El Gamal o remetente foi escolher um aleatório derivando a chave e foi todo criptografado usando o processo de criptografia El Gamal. Mas mais tarde argumentamos que o remetente não precisa ter que fazer isso. Ele pode realizar a Criptografia Híbrida mesmo apenas enviando g β para o receptor. Agora, basta que a função de derivação de chave subjacente seja um tipo especial de função, que distribui o elemento de grupo quase uniformemente entre os elementos do espaço chave do processo de criptografia de chave simétrica. O que eu quero dizer com isso é, se eu considerar se este é o meu grupo g, e se este é o meu conjunto K, e o número de elementos, que mapeia para um elemento candidato a partir deste espaço chave, o número de elementos de grupo que mapeia para este único elemento candidato a partir deste espaço chave deverá quase ser o mesmo. Não deve haver qualquer viés na distribuição ou no mapeamento pelo qual esta função H esteja mapeando os elementos do grupo para os elementos do espaço chave do meu processo de criptografia de chave simétrica. Se eu assumir que a minha função de derivação de chave subjacente tem esse tipo de efeito de defumação, então é suficiente para eu apenas permanecer no modelo padrão e reivindicar a segurança deste mecanismo de encapsulamento chave, apenas baseado no pressuposto DDH. Agora, você pode ver a importância de pressupostos que estamos fazendo ao longo deste curso. Uma mesma construção aqui pode ser comprovada segura em com suposições de dureza mais fracas, nomeadamente a assunção CDH. Mas com propriedades mais poderosas a partir da função hash subjacente, a saber, assumir que está agindo como um Random-oracle enquanto que se você não deseja modelar sua função hash subjacente como um Random-oracle, você quer modelá-lo como um tipo especial de função de distribuição suave, então você precisa ter uma suposição de dureza mais poderosa em seu grupo subjacente, a saber, você precisa ter o problema DDH difícil de ser resolvido em seu grupo subjacente. Então, isso me leva até o final desta palestra. Só para resumir nesta palestra, introduzimos o processo de criptografia da Hybrid e discutimos a CPA-segurança do processo de criptografia Hybrid. Também vimos uma construção genérica de como combinar um mecanismo de encapsulamento de chave segura de um CPA ou um COA-seguro juntamente com qualquer chave simétrica segura de COA