BRPI0318492B1

BRPI0318492B1 - rede dependente de chave combinatória e método para criptografia/decifração de dados digitais de entrada

Info

Publication number: BRPI0318492B1
Authority: BR
Inventors: Golic Jovan
Original assignee: Telecom Italia Spa
Priority date: 2003-09-05
Filing date: 2003-09-05
Publication date: 2019-12-10
Also published as: US7913083B2; BR0318492A; AU2003274687A1; EP1661295A1; CN1826753B; WO2005025124A1; CN1826753A; EP1661295B1; US20060236102A1

Abstract

"rede dependente de chave combinatória para criptografia/decifração de dados digitais de entrada, bloco para ser usado para funções criptográficas controladas por chave secreta, método para criptografia/decifração de dados digitais de entrada, dispositivo de processamento de dados, e, dispositivo de multimídia para armazenar e reproduzir dados digitais". uma rede dependente de chave combinatória (46), adequada para a criptografia/decifração de dados em barramentos e em memórias de dispositivos de processamento de dados, inclui várias camadas, onde cada camada é composta de vários blocos de construção elementares (2) operando em tamanhos de bloco muito pequenos. um bloco de construção genérico (2) atua em um pequeno número de bits de dados de entrada, que são divididos em dois grupos de m e n bits, respectivamente. os m bits de entrada, que são passados à saída intactos, são usados para selecionar k fora de 2^ m^k bits de chave por um circuito de multiplexador; os k bits são então usados para selecionar uma transformação reversível de (nxn) bits (r~ k~) atuando nos n bits de entrada restantes para produzir os n bits de saída correspondentes. o número total dos bits de chave no bloco de construção é assim 2^ m^k, que pode facilmente ser feito maior que m+n. um bloco de construção inverso é o mesmo, exceto que as transformações reversíveis r~ k~ são substituídas por seus inversos r~ k~^ -1^.

Description

“REDE DEPENDENTE DE CHAVE COMBINATÓRIA E MÉTODO PARA CRIPTOGRAFIA/DECIFRAÇÃO DE DADOS DIGITAIS DE ENTRADA” DESCRIÇÃO

Campo da Invenção [0001] A presente invenção diz respeito a um método e um sistema de processamento de dados, e, em particular, a um circuito reversível controlado por chave secreta que é usado para codificar e decifrar dados.

[0002] Transformações reversíveis controladas por um parâmetro de chave secreta são entidades matemáticas usadas para codificar e para decifrar dados sensíveis de maneira a prover confidência de dados. As transformações deveriam ser tais que fosse impossível, computacionalmente, recuperar dados de entrada originais dos dados de saída transformados sem conhecer a chave secreta sendo usada e, em particular, deveria ser impossível reconstruir a chave secreta de vários pares de entrada/saída conhecidos. Ademais, eles deveriam ser relativamente fáceis de implementar em software e/ou hardware. Fundamentos da Técnica [0003] Cifras de bloco e fluxo são dois tipos em termos gerais de tais transformações. Cifras de bloco são transformações de bloco que operam em dados digitais arranjados em blocos de símbolos consecutivos, enquanto cifras de fluxo são transformações sequenciais que operam em sequências de dados digitais, tipicamente processando um símbolo de cada vez. Exemplos de cifras de bloco são ilustrados tais como e.g. AES e DES em J. Daemen e V. Rijmen, "The design of Rijndael: AES - The Advanced Encryption Standard" Berlim: Springer_Verlag, 2002, e em Agência Nacional de Padrões, "Data Encryption Standard", Publicação de Padrões de Processamento de Informação Federais 46, Janeiro de 1977, respectivamente.

[0004] Funções criptográficas lidando com chaves secretas tais como, por exemplo, cifras de bloco ou fluxo ou códigos de autenticação de mensagens podem ser implementados em software num dispositivo de processamento de dados de microeletrônica como, por exemplo, um cartão de chip de circuito integrado, que contém uma unidade de processamento central (CPU) tal como um microprocessador, uma ou mais memórias voláteis tais como memórias de acesso aleatório (RAM), e uma ou mais memórias não voláteis tais como uma memória só de leitura eletricamente programável e apagável (EEPROM), uma memória flash e uma memória somente de leitura (ROM). Durante a execução da função criptográfica, os dados sensíveis dependentes da chave secreta estão sendo enviados por meio dos barramentos de dados que conectam a CPU e as memórias e sendo armazenados nas RAMs no sistema. Nesta concretização, a informação sensível é a própria chave secreta e todos os dados intermediários dependendo da chave secreta, exceto os dados de saída. Até mesmo para chips resistentes à fraude, onde o circuito integrado subjacente é protegido através de medidas físicas especiais, tais como camadas protetoras e vários sensores e detectores, esta informação sensível pode vazar por vários canais laterais, tal como, por exemplo, medição de temporização, medição de análise de potência, irradiação eletromagnética, e micro-sondagem.

[0005] Documento US5850452 exibe um método para embaralhamento numérico através de permutação de bits de dados em um circuito programável incluindo uma unidade de controle e um barramento de dados para transmitir dados entre a unidade de controle e vários circuitos de memória.

[0006] Enquanto que, para uma função criptográfica, não deveria ser possível computacionalmente reconstruir a chave secreta de dados de entrada/ saída conhecidos, isto não precisa ser o caso se dados intermediários gerados durante a execução forem revelados. Logo, há uma necessidade de proteger os dados sensíveis no barramento de dados e nas memórias usando técnicas de criptografia/decifração às vezes referenciadas como embaralhamento de dados. Isto é especialmente útil contra os ataques de sondagem. Ataques de sondagem são técnicas de canal lateral invasivas consistindo em introduzir microsondas de condutor em certos pontos de um chip resistente à fraude para monitorar e analisar sinais elétricos nestes pontos, a fim de recuperar informação sensível sobre a chave secreta. A este respeito, pontos potencialmente mais vulneráveis são os correspondentes às ligações internas ou memórias que são prováveis de levar ou conter informação secreta e cuja implementação de hardware tem uma estrutura regular reconhecível, tais como os barramentos de dados e as RAMs no dispositivo de processamento de dados.

[0007] Documento US5943421 contém a descrição de um dispositivo de processamento de dados, onde os dados armazenados nas memórias (que incluem RAM) são codificados e comprimidos. O dispositivo usa uma unidade de hardware para criptografia/compressão e decifração/descompressão que é transparente para os outros componentes.

[0008] Aquela criptografia/decifração de dados somente nos dados ou barramentos de instrução pode ser alcançada usando uma cifra de fluxo rápida combinando a sequência de dados com a sequência de fluxo de chave sendo a sequência de saída de um gerador de número centralizado rápido aleatório ou pseudo-aleatório possivelmente pela operação de XOR bit a bit, como ilustrado por exemplo, em US2003/0005313 e em US2003/0005314.

[0009] Lembre-se que operação por XOR bit a bit de dois bits é igual a 0 se os dois bits forem iguais, e a 1, caso contrário. Mais precisamente, em cada momento, o bloco de dados é operado por XOR bit a bit em bits com o bloco de fluxo de chave. Note que o gerador de número pseudo-aleatório é um circuito sequencial em lugar de combinatório. Contudo, esta solução não é satisfatória para codificar ou decifrar dados a serem armazenados ou lidos das memórias, respectivamente, porque o mesmo bloco de fluxo de chave tem que ser usado para decifrar e codificar os dados para um local particular numa dada memória. As transformações reversíveis também podem depender do endereço do local de memória, enquanto o endereço pode ser codificado também, de maneira tal que os dados sejam armazenados efetivamente em um local de memória cujo endereço é uma versão codificada do endereço lógico original.

[00010] Para criptografia/decifração de dados em memórias foi proposto usar implementações de hardware de cifras de bloco, que requerem um grande número de portas e induzem um longo atraso. Documento US2002/0166058A1 contém uma descrição de um dispositivo de processamento de dados, para ser implementado num cartão de chip de circuito integrado, onde ambos o endereço e os dados a serem armazenados em memória, tal como por exemplo a RAM, são codificados/decifrados por uma cifra de bloco como DES, com 16 rodadas, implementadas em hardware programável.

[00011] Algumas simplificações de cifras de bloco clássicas, como, por exemplo, com o número reduzido de rodadas e o tamanho de bloco reduzido, também foram propostas. Em princípio, as simplificações também podem ser usadas para codificar/decifrar os dados e os barramentos de endereço. Porém, tais simplificações não são capazes de incorporar um número suficientemente grande de bits de chave secreta para resistir a alguns ataques estruturais bem conhecidos tais como os ataques de 'encontre no meio', especialmente se os tamanhos de bloco forem relativamente pequenos. Note que nas cifras de bloco clássicas, os bits de chave secreta são tipicamente operados por XOR bit a bit, com os bits de saída de rodadas individuais. Para aumentar o número de bits de chave secreta ainda é proposto usar permutações de bits controladas por chave secreta, mas elas não oferecem um nível de segurança satisfatório e o número de bits de chave secreta permanece pequeno se o tamanho de bloco requerido for pequeno.

[00012] Alguns circuitos lógicos para implementar permutações de bits controladas por chave secreta para serem usados em um embaralhamento dos dados contra ataques de sondagem, em cartões de chip de circuito integrado, são propostos em E. Brier, H. Handschuh, e C. Tymen, "Fast primitives for internal data scrambling in tamper resistant hardware", 'Cryptographic Hardware and Embedded Systems' - CHES 2001, Notas de Conferência em Informática, vol. 2162, pp. 16-27, 2001.

[00013] Em conclusão, as soluções atuais para a criptografia/decifração dos dados em memórias não são satisfatórias, particularmente, se os tamanhos dos blocos forem pequenos como, por exemplo, 16 bits ou menos.

[00014] Por conseguinte, existe uma necessidade de novos projetos de circuitos lógicos reversíveis dependentes de chave secreta apropriados para as implementações de hardware de pequeno tamanho, em termos do número de portas, e de alta velocidade, em termos do atraso induzido. Eles deveriam ser capazes de incorporar número relativamente grande de bits de chave secreta e operar em tamanhos de bloco pequenos e possivelmente variáveis.

Sumário da Invenção [00015] Em vista do exposto acima, é um objetivo da invenção prover um novo método e um dispositivo para projetar circuitos lógicos reversíveis controlados por chave secreta que sejam adequados para criptografia/decifração de dados em barramentos e em memórias de dispositivos de processamento de dados.

[00016] De acordo com a presente invenção, o objetivo é alcançado por meio de uma rede combinatória apresentando as características publicadas nas reivindicações logo em seguida. A presente invenção também diz a respeito de um método correspondente de criptografia/decifração de dados digitais. [00017] A solução proposta tem estrutura iterativa e granular, isto quer dizer, consiste em várias camadas, onde cada camada inclui vários blocos de construção elementar operando em tamanhos de bloco muito pequenos. [00018] Um bloco de construção genérico atua em um número pequeno de bits de dados de entrada, que são divididos em dois grupos de m e n bits, respectivamente. Os m bits de entrada, que são passados à saída intactos, são usados para selecionar k dentre 2mk bits de chave por um circuito multiplexador. k bits são então usados para selecionar uma transformação reversível de (nxn) bits Rk atuando nos n bits de entrada restantes para produzir os n bits de saída correspondentes. O número total dos bits de chave no bloco de construção é, assim, 2mk, o qual pode ser feito facilmente maior do que m+n. Um bloco de construção inverso é o mesmo, exceto que as transformações reversíveis - Rk -são substituídas pelos seus inversos Rk-1.

[00019] Cada bloco é assim capaz de incorporar um grande número de chave de bits secreta, tem um número pequeno de portas, e um atraso curto. Os blocos de construção são arranjados em camadas e as camadas podem ser conectadas por permutações de bits fixos.

Breve Descrição dos Desenhos Figura 1 é um diagrama em blocos de um bloco de construção genérico de um circuito lógico controlado por chave secreta que foi realizado de acordo com a invenção;

Figura 2 é um diagrama em blocos de uma estrutura de arranjo de um circuito lógico controlado por chave secreta realizado de acordo com a invenção;

Figura 3 é um diagrama em blocos de uma 1a concretização de um bloco conectando camadas adjacentes;

Figura 4 é um diagrama em blocos de uma 2a concretização de um bloco conectando camadas adjacentes;

Figura 5 é um diagrama em blocos de uma concretização, em particular, de um bloco de construção, realizado de acordo com a invenção; e Figura 6 é um diagrama em blocos de uma concretização de um bloco de construção simplificada, realizado de acordo com a invenção. Descrição Detalhada das Concretizações Preferidas [00020] Um circuito lógico reversível controlado por chave secreta de acordo com a invenção é uma rede combinatória incluindo diversas camadas, cada uma incluindo vários blocos de construção elementar, cada um dos blocos implementando uma transformação reversível dependente de chave.

[00021] Um bloco de construção genérico 2 é mostrado na Figura 1. Ele atua num número pequeno de bits de dados de entrada, dividido em dois grupos de m bits de controle e n bits transformados, respectivamente, por exemplo, m+n < 16. Os m bits de controle 14, que são levados intactos à saída 19, são usados para selecionar k dentre os 2mk bits de chave secreta por um circuito multiplexador 4 tendo m bits de controle 12, 2m entradas de k bits 8, e uma saída de k bits 10. O circuito multiplexador 4 pode ser implementado como uma tabela de consulta de mxk, isto é, k (binário) tabelas de consulta de mx1, cujo conteúdo é definido pela chave secreta.

[00022] Os k bits selecionados, isto é, a saída 10 do multiplexador 4, são usados para escolher uma transformação reversível de (nxn) bits Rk (bloco 6 na Figura 1) atuando nos n bits de entrada restantes 16, consequentemente chamados de bits transformados, para produzir aqueles correspondentes n bits de saída 18. Aquele conjunto das transformações reversíveis Rk para um bloco genérico pode ser arbitrário, e, preferencialmente, tem que ser implementável facilmente por circuito lógico com n+k bits de entrada e n bits de saída. Notar que o número total de bits de chave secreta no bloco de construção é assim 2mk, e pode ser feito facilmente (muito) maior que tamanho de bloco m+n subjacente. [00023] O bloco de construção inverso tem uma mesma arquitetura do circuito, exceto que as transformações reversíveis Rk são substituídas por seus inversos Rk-1.

[00024] Uma rede combinatória 46 que inclui várias camadas 48, cada qual incluindo vários blocos de construção elementar 2, é mostrada na Figura 2. [00025] A rede 46 opera em N bits de entrada 42, em cada camada 48, N bits são divididos em blocos pequenos e cada um deles é transformado por um bloco de construção elementar 2. Cada camada 48 é assim uma combinação paralela de vários blocos de construção. Num projeto uniforme, todos os blocos de construção são do mesmo tipo, não obstante implementações diferentes de blocos de construção podem ser usadas em uma única rede combinatória. [00026] Camadas 48 são conectadas por meio de blocos de permutação de bits fixos 40, que, para obter maior segurança, preferencialmente satisfazem as duas propriedades de difusão seguintes. Numa rede combinatória inversa, permutações de bit inversa têm que ser usadas. Se m=n, então as permutações de bits usada podem ser feitas iguais a seus inversos.

[00027] A primeira propriedade é que os bits de controle em cada camada são usados como bits transformados na próxima camada. Em cada camada, o número de bits de controle não pode consequentemente exceder o número de bits transformados, de forma que em um projeto uniforme, m < n. [00028] A segunda propriedade é que, para cada bloco de construção, ambos bits de controle e bits transformados são extraídos do número máximo possível de blocos de construção na camada precedente. Num projeto uniforme, este número iguala a min (m,N/(m+n)) para bits de controle e min (n,N/(m+n)) para bits transformados.

[00029] Como uma alternativa, poderá ser aceitável que os requisitos da segunda propriedade só sejam cumpridos parcialmente, a saber, bits de controle e bits transformados são extraídos de um grande número (porém não o número máximo possível) de blocos de construção na camada precedente.

[00030] Uma possível concretização para um bloco de permutação de bits fixos 40 para N=8 e dois blocos por camada com parâmetros m=n=2 é mostrado na Figura 3. A primeira e a segunda propriedades são verificadas na concretização mostrada na Figura 3.

[00031] Num projeto uniforme, todos os blocos 40 conectando camadas adjacentes 48 são do mesmo tipo, não obstante, concretizações diferentes de bloco 40 podem ser implementadas em uma única rede combinatória 46. [00032] Para embaralhar os dados, ou seja, para criptografia/decifração de barramentos e memórias em dispositivos de processamento de dados, um número relativamente pequeno de camadas pode ser suficiente, por exemplo, 3 a 5.

[00033] Para segurança criptográfica, vários outros critérios desejáveis também são propostos.

[00034] Em primeiro lugar, o número de tais blocos de construção 2 por cada camada 48 deveria ser pelo menos 2.

[00035] Segundo, as transformações reversíveis Rk deveriam ser tais que cada bit de saída de Rk seja uma função não linear de n bits de dados de entrada e k bits de chave com a forma normal algébrica contendo pelo menos um produto binário envolvendo ambos bits de dados de entrada e de chave. Por exemplo, isto é satisfeito pelas transformações reversíveis mostradas na Figura 5, que serão explicadas em detalhes mais tarde.

[00036] Mais precisamente, para esquema da Figura 5, a forma normal algébrica para os bits de saída yi e y2 é: yi = ki Φki.kí Φk2.k3 Φxi Φk3.xi Φk3.X2 y2 = k2 Φk2.k3 Φki.k3 ΦX2 Φ k3.X2 Φ k3.xi, onde os bits de chave ki e k2 são usados para as portas de XOR 26, 28 e o bit de chave k3 é usado para controlar a chave 30. Aqui denota a operação por XOR bit a bit e denota a operação de produto binário.

[00037] Os bits de entrada transformados e os bits de controle em cada camada são assim combinados não linearmente juntos.

[00038] O segundo critério implica que n > 2, como as únicas funções reversíveis de uma variável são as funções de identidade e de complemento binário, de forma que o único bit de chave tenha que ser operado por XOR bit a bit com o bit de entrada para obter o bit de saída. O segundo critério não é satisfeito se k=n e os bits de chave forem operados por XOR bit a bit com n bits de dados de entrada, como na estrutura de Feistel habitual usada em DES. [00039] Terceiro, as transformações reversíveis Rk deveriam satisfazer um critério do tipo Shannon que a incerteza de n bits de entrada providos por k bits de chave aleatórios uniformemente usados quando os n bits de saída são conhecidos é máxima possível, quer dizer, n bits. Para isto é necessário que k > n. O terceiro critério pode ser satisfeito facilmente operando-se por XOR bit a bit um subconjunto de n bits de chave com n bits de dados de entrada, como implementado na Figura 5.

[00040] Uma classe simples de circuitos lógicos implementando aquelas transformações reversíveis dependentes de chave Rk consiste em operar XORs de dois bits de entrada e chaves (controladas) apenas, onde uma chave tem dois bits de entrada, dois bits de saída, e um bit de controle que determina se os bits de entrada são ou não comutados.

[00041] Claramente, uma chave pode ser implementada usando-se dois multiplexadores em paralelo, enquanto somente um multiplexador basta para implementar uma XOR. Aqui e ao longo da descrição presente, a menos que especificado diferentemente, um multiplexador tem 2 bits de entrada, 1 bit de controle, e 1 bit de saída. Para cada XOR, um dos dois bits de entrada é um bit de chave, enquanto para cada chave, o bit de controle é um bit de chave. [00042] Os bits de chave são incorporados no circuito de tal modo que não haja nenhuma chave equivalente, isto é, que combinações diferentes dos bits de chave dão origem a transformações reversíveis diferentes. Isto não é um problema para verificação como os parâmetros n e k são pequenos. Para cada chave fixa, tais transformações reversíveis são afins, e a não linearidade é alcançada pelos bits de chave dependendo dos bits de dados de entrada de controle. Para n=3, note que todas as 24 transformações reversíveis de 2 bits de entrada são necessariamente afins.

[00043] O critério do tipo Shannon não é satisfeito se o circuito apenas contiver chaves controladas por chave de segredo.

[00044] Um exemplo concreto básico de um bloco de construção 20 da classe descrita acima, com parâmetros (m, n, k) = (2, 2, 3), é mostrado na Figura 5.

[00045] Dois bits de entrada x3, x4 são empregados para controlar um multiplexador 24 e são passados à saída y3, y4 intactos. Os bits de entrada x3, x4 selecionam três entre doze bits de chave por meio do circuito multiplexador 24, que tem dois bits de controle 36, para entradas de 3 bits 32 e uma saída de 3 bits 34.

[00046] A saída de 3 bits 34 é usada para controlar um bloco 38, que implementa as transformações reversíveis Rk, transformando bits de entrada X1 e X2 em bits de saída embaralhados yt e y2. O bloco 38 inclui duas portas de XOR 26 e 28, cada uma tendo dois bits de entrada e um bit de saída, e uma chave controlada 30 com 2 bits de entrada, 2 bits de saída, e 1 bit de controle, que determina se os bits de entrada são ou não comutados.

[00047] A chave controlada 30 poderá ser implementada utilizando dois multiplexadores em paralelo, enquanto apenas um multiplexador é suficiente para implementar cada uma das duas portas de XOR 26, 28.

[00048] O bloco de construção 20 como mostrado na Figura 5 pode ser implementado usando um circuito com 13 multiplexadores e com profundidade 4, onde a profundidade é definida como o número de portas no caminho mais longo da entrada à saída. O número total de bits de chave secreta incorporado é 12.

[00049] O bloco de construção 20 pode ser utilizado pronta e facilmente para definir funções de embaralhamento de dados concretas do tipo uniforme. Por exemplo, para N=16 bits de entrada, cada camada contém 4 tais blocos e, consequentemente, tem um total de 52 multiplexadores e incorpora 48 bits de chave. Por conseguinte, cinco camadas deste tipo incorporam 240 bits de chave e podem ser implementadas por um circuito com 210 multiplexadores e com profundidade 20. A rede resultante incorpora um número relativamente grande de bits de chave e tem um tamanho muito pequeno e profundidade, que, para um N relativamente pequeno tal como N < 16, é impossível alcançar por redes resultantes de cifras de bloco clássicas simplificadas e de permutações de bits controladas por chave. Ademais, a sua segurança criptográfica é aperfeiçoada consideravelmente.

[00050] Para aumentar ainda mais a segurança, é desejável que a chave secreta usada para o embaralhamento de dados seja inovada para cada nova execução da função criptográfica no dispositivo de processamento de dados. Assim, a chave secreta usada para o embaralhamento de dados é per se muito menos exposta aos ataques de canal lateral, tais como os ataques de análise de potência. Como tal, também provê um certo grau de resistência a ataques de análise de potência.

[00051] A chave secreta é preferivelmente gerada por um gerador de número aleatório implementado no mesmo dispositivo. Alternativamente, mas menos seguramente, pode ser gerado por um gerador de número pseudo-aleatório de uma semente secreta e alguma informação adicional que não têm que ser secreta ou aleatória, mas está sendo inovada toda vez.

[00052] Os blocos de construção propostos também podem ser usados para projetar cifras de bloco de alta velocidade e pequeno tamanho adequadas para implementações de hardware em geral. Para este propósito, um tamanho de bloco maior, por exemplo N > 64, é preferivelmente usado, e o número de camadas, isto é rodadas, é aumentado. Como o tamanho e como o atraso de cada camada é consideravelmente menor que em construções iteradas usuais de cifras de bloco, o número de rodadas pode ser inúmeras vezes maior. Por exemplo, para bloco de construção da Figura 5 e N=128, o número de rodadas pode ser cerca de 32 ou até maior.

[00053] Diferente das funções de embaralhamento de dados, as funções de criptografia ou decifração para cifras de bloco não têm que ser executadas em somente um ciclo de microprocessador de tal maneira que elas possam ser implementadas por uma combinação de circuitos lógicos e registradores. Por exemplo, várias camadas combinadas podem ser implementadas através de um circuito lógico. As arquiteturas de tubulação são extremamente rápidas devido ao pequeno atraso de cada camada.

[00054] Para a segurança criptográfica, as camadas deveriam satisfazer aqueles três critérios adicionais desejáveis descritos acima. À parte disso, dois requisitos adicionais relativos às conexões entre as camadas são propostos.

[00055] Primeiro, duas chaves secretas de entrada e saída adicionais de tamanho N deveriam ser operadas por XOR bit a bit com os bits de entrada e de saída, respectivamente, à parte das chaves secretas utilizadas em rodadas individuais que são chamadas as chaves redondas.

[00056] Segundo, tendo em vista os métodos de análise criptográfica estatística tal como a análise criptográfica de cifras de bloco, é proposto usar funções lineares reversíveis muito simples entre as camadas, em vez de usar só as permutações de bit. Em particular, se os números totais de bits de dados transformados e de controle por camada forem iguais, é proposto empregar as permutações de bit projetadas como explicado acima e então operar por XOR bit a bit todos os bits de dados transformados na entrada para cada camada com um bit de dados transformado distinto da camada precedente. Isto não aumenta, normalmente, o atraso das camadas. Uma concretização de um bloco 40' usado para conectar camadas adjacentes, implementando uma função linear reversível, é mostrada na Figura 4. O bloco 40' mostrado implementa uma transformação linear reversível de 8 bits, para m=n=2 e N=8.

[00057] Numa rede combinatória realizada de acordo com a invenção, o número de bits de chave por rodada, quer dizer, o tamanho de bit da chave de rodada é tipicamente maior do que o tamanho de bloco. Tal aspecto é de grande vantagem para aplicações de embaralhamento de dados, onde tamanho de bloco e número ou rodadas são ambos relativamente pequenos.

[00058] Por exemplo, o bloco de construção como mostrado na Figura 5 requer três bits de chave por cada bit de entrada. Como para aplicações de cifra de bloco, o número de rodadas é aumentado, o número total de bits de chave requeridos é maior que em projetos de cifra de bloco habituais. Estes bits de chave podem ser produzidos em um número menor de bits de chave secreta, armazenados em uma RAM, por um algoritmo de expansão de chave, que pode ser baseado, conforme explicado aqui em seguida, em um bloco de construção modificado.

[00059] O algoritmo de expansão de chave produz as chaves de rodada iterativamente e ele mesmo pode ser implementado em hardware por uma combinação de circuitos lógicos e registradores, de forma que nem todas as chaves de rodada tenham que ser armazenadas em RAM.

[00060] Um bloco de construção modificado o qual implemente aquele algoritmo de expansão de chave opera como a seguir. Deixe K e K' denotarem os tamanhos de bit da chave secreta e da chave de rodada, respectivamente. Os K bits de chave secreta são primeiro expandidos através de transformações lineares em K' bits de chave usando um código linear apropriado de tal forma que qualquer subconjunto de K'' bits de chave expandida seja independente linearmente, onde K'' não é pequeno (K'' < K). Na terminologia de códigos de correção de erro, a distância mínima do dual deste código linear deveria ser pelo menos K''+1.

[00061] A chave expandida obtida é então utilizada como uma entrada para uma rede combinatória de tamanho de bloco K', que é parametrizada por uma chave gerada aleatoriamente fixa que satisfaz uma condição adicional de que todo o bloco multiplexador na rede implementa tabelas de consulta binárias equilibradas, isto é, aquelas tabelas de consulta binárias contendo um número igual de 0s e 1s. Os K' bits produzidos depois de todas as duas camadas da rede combinatória são usados sucessivamente como chaves de rodada, junto com os K' bits de entrada. Como o número de camadas é assim dobrado quando e se comparado com a rede combinatória utilizada para a própria cifra de bloco, os blocos de construção usados para expandir a chave poderiam ser simplificados. [00062] Uma concretização possível de um bloco de construção simplificado 50 é mostrada na Figura 6, com parâmetros (m, n, k) = (1, 2, 1). Tal bloco de construção é obtido removendo os 2 blocos de XOR e 1 entrada de controle do bloco de construção mostrado na Figura 5.

[00063] Um bit de entrada X3 é usado para controlar um multiplexador 54 e é passado à saída y3 intacto. O bit de entrada x3 seleciona um dentre dois bits de chave por meio do circuito multiplexador 54, o qual possui um bit de controle 58, duas entradas de 1 bit 52 e uma saída de 1 bit 60.

[00064] A saída de 1 bit 60 é usada para controlar um bloco 56, o qual implementa uma transformação reversível simples Rk, transformando os bits de entrada x1 e x2 em bits de saída y1 e y2. O dito bloco 56 inclui uma chave controlada tendo dois bits de entrada, dois bits de saída, e um bit de controle que determina se os bits de entrada são ou não comutados.

[00065] Alternativamente, os K' bits de chave de rodada poderiam ser produzidos depois de cada camada da rede combinatória, se um permitisse às porções de chaves de rodadas sucessivas serem permutações de bits uma da outra. Neste algoritmo iterado, cada rodada é uma transformação reversível, tal que um critério desejável de que cada chave de rodada seja uniformemente aleatória, se a entrada para a primeira rodada for uniformemente aleatória, for satisfeita.

[00066] O algoritmo de expansão de chave pode ser simplificado com uso apenas de transformações lineares do seguinte modo. Os K bits de chave secreta são primeiro expandidos por meio de transformações lineares em 2K' bits de chave, como descrito acima, utilizando um código linear apropriado de forma que não haja nenhum subconjunto pequeno de bit de chave expandida linearmente dependente. Os 2K' bits expandidos são então usados como chaves de rodada para as primeiras duas rodadas, enquanto os pares subsequentes de chaves de rodadas sucessivas são produzidos aplicando permutações de bits fixos aos bits de chave expandidos.

[00067] Uma concretização do projeto proposto das cifras de blocos é a criptografia/decifração de dados digitais de direito autoral a serem armazenados em memórias, tais como a EEPROM, ou memórias flash, por exemplo, para aplicações de multimídia.

REIVINDICAÇÕES

Claims

1. Rede dependente de chave combinatória (46) para criptografia/ decifração de dados digitais de entrada (42) de tamanho de palavra N em dados digitais de saída (44) do mesmo tamanho de palavra, compreendendo pelo menos duas camadas (48), em que camadas adjacentes (48) são conectadas por meio de um bloco de permutação de bit fixo (40), cada camada incluindo uma pluralidade de blocos de construção elementar (2), cada bloco de construção (2) operando em um bloco de entrada de bits (14, 16) possuindo um tamanho de palavra n+m menor do que ou igual ao dito tamanho de palavra N, para gerar um bloco de saída de bits (18, 19), caracterizada pelo fato de que cada bloco de construção (2) compreende: - um circuito multiplexador (4), que recebe em uma entrada de controle (12) uma primeira porção m (14) de dito bloco de bits de entrada, para selecionar k dentre os 2mk bits de chave em uma saída de k bits (10) daquele circuito multiplexador (4), a dita primeira porção (14) de bits sendo transferida intacta para uma saída (19) de dito bloco de construção (2); e - um circuito de transformação (6), para transformar uma porção restante n (16) de dito bloco de entrada de bits de entrada em bits transformados (18), de acordo com uma transformação reversível (Rk) escolhida, por meio dos k bits (10) selecionados, dentre uma pluralidade de transformações reversíveis (Rk) implementadas em dito circuito de transformação (6), em que cada camada (48) compreende pelo menos dois blocos de construção (2), e em que as referidas transformações reversíveis (Rk) são tais que cada bit de saída das referidas transformações reversíveis (Rk) seja uma função não linear de n bits de dados de entrada e dos referidos k bits de chave, com a forma normal algébrica contendo pelo menos um produto binário que envolve ambas a segunda porção (16) de dito bloco de entrada de bits de entrada e ditos bits de chave.

2. Rede de acordo com a reivindicação 1, caracterizada pelo fato de que compreende uma pluralidade de blocos de permutação de bits fixos (40) do mesmo tipo.

3. Rede de acordo com a reivindicação 1, caracterizada pelo fato de que compreende pelo menos dois diferentes tipos de blocos de permutação de bits fixos (40).

4. Rede de acordo com a reivindicação 1, caracterizada pelo fato de que bits em dita saída (19) daquele bloco de bits de entrada são usados, em uma próxima camada, como bits a serem transformados (16).

5. Rede de acordo com a reivindicação 1, caracterizada pelo fato de que, para cada bloco de construção (2), a dita primeira porção (14) de dito bloco de bits de entrada é extraída de pelo menos dois blocos de construção em uma camada precedente, contanto que m > 2.

6. Rede de acordo com a reivindicação 1, caracterizada pelo fato de que, para cada bloco de construção (2), a dita segunda porção (16) de dito bloco de bits de entrada é extraída de pelo menos dois blocos de construção em uma camada precedente, contanto que n > 2.

7. Rede de acordo com a reivindicação 1, caracterizada pelo fato de que o número k de bits de chave é igual a ou maior do que o número n de dita porção restante de dito bloco de entrada de bits.

8. Rede de acordo com a reivindicação 1, caracterizada pelo fato de que dito circuito multiplexador (4) compreende uma tabela de consulta, cujo conteúdo é definido pela chave.

9. Rede de acordo com a reivindicação 1, caracterizada pelo fato do circuito de transformação (6) compreender portas XOR e chaves controladas.

10. Rede de acordo com a reivindicação 9, caracterizada pelo fato de que cada porta XOR tem dois bits de entrada e um bit de saída, um dos dois bits de entrada sendo um bit de chave, e cada chave controlada com dois bits de entrada, dois bits de saída e um bit de controle que determina se os bits de entrada são ou não comutados, o dito bit de controle sendo um bit de chave.

11. Rede de acordo com a reivindicação 10, caracterizada pelo fato de que o circuito multiplexador (4) tem dois bits de controle (36), quatro entradas de 3 bits (32) e uma saída de 3 bits (34), e o circuito de transformação (6) compreende duas portas XOR (26, 28) e uma chave controlada (30).

12. Rede de acordo com a reivindicação 11, caracterizada pelo fato dos três bits de dita saída de 3 bits (34) serem conectados, respectivamente, a um primeiro bit de entrada de cada porta XOR (26, 28) e ao bit de controle de dita chave controlada (30).

13. Rede de acordo com a reivindicação 12, caracterizada pelo fato de um segundo bit de entrada de cada porta XOR (26, 28) ser conectado a um bit de dita segunda porção (16) de dito bloco de entrada de bits de entrada.

14. Rede de acordo com a reivindicação 13, caracterizada pelo fato de os bits de saída de ditas portas XOR (26, 28) serem conectados aos dois bits de entrada de dita chave controlada (30).

15. Rede de acordo com a reivindicação 14, caracterizada pelo fato de compreender meio para gerar os bits transformados (18) de dito circuito de transformação (6) a partir dos dois bits de saída de dita chave controlada (30).

16. Rede de acordo com a reivindicação 1, sendo caracterizada por compreender uma pluralidade de blocos de construção (2) do mesmo tipo.

17. Rede de acordo com a reivindicação 1, sendo caracterizada por compreender pelo menos dois diferentes tipos de blocos de construção (2).

18. Rede de acordo com a reivindicação 1, sendo caracterizada pelo fato de que camadas adjacentes (48) são conectadas por meio de um bloco (40') implementando uma função linear reversível.

19. Rede de acordo com a reivindicação 1, sendo caracterizada pelo fato de que duas chaves adicionais de entrada e de saída de tamanho de palavra N são operadas por XOR bit a bit, respectivamente, com ditos dados digitais de entrada (42) e com ditos dados digitais de saída (44).

20. Rede de acordo com a reivindicação 1, sendo caracterizada por compreender meio para gerar ditos bits de chave em cada camada, tendo tamanho de bit K', a partir de um número menor de bits de chave secreta, que tem tamanho de bit K, por meio de um algoritmo de expansão de chave.

21. Rede de acordo com a reivindicação 20, caracterizada pelo fato de que ditos K bits de chave secreta são primeiro expandidos por meio de transformações lineares em K' bits de chave, com o uso de um código linear, de tal maneira que qualquer subconjunto de K'' bits de chave expandida seja independente linearmente, onde K'' < K.

22. Rede de acordo com a reivindicação 21, caracterizada pelo fato de que a dita chave expandida tendo tamanho de bit K' é usada como uma entrada para uma rede dependente de chave combinatória adicional de tamanho de bloco K' que é parametrizada por uma chave gerada aleatoriamente fixa que satisfaz a condição de que todo o multiplexador implementa tabelas de consulta binárias equilibradas.

23. Rede de acordo com a reivindicação 22, caracterizada pelo fato de que os K' bits produzidos depois de todas as duas camadas de dita rede dependente de chave combinatória adicional são usados como tais bits de chave dos circuitos multiplexadores dentro das camadas da rede combinatória (46).

24. Rede de acordo com a reivindicação 22, caracterizada pelo fato de que dita rede dependente de chave combinatória adicional compreende uma pluralidade de camadas, cada camada compreendendo uma pluralidade de blocos de construção simplificados (50), cada bloco de construção (50) incluindo: - um multiplexador (54) tendo uma entrada (58), que recebe um bit de controle (x3) que é passado à saída (y3) intacto, para selecionar um dentre dois bits de chave (52) em uma saída de bits (60); - uma chave controlada (56) tendo dois bits de entrada (x1, X2), dois bits de saída (y1, y2) e um bit de controle conectado à saída do multiplexador (60), o bit de controle determinando se ditos bits de entrada (x1, X2) são ou não comutados.

25. Método para criptografia/decifração de dados digitais de entrada (42) de tamanho de palavra N em dados digitais de saída (44) do mesmo tamanho de palavra, caracterizado pelo fato de compreender as etapas de: a) dividir ditos dados digitais de entrada (42) em blocos de bits (14, 16), cada um possuindo um tamanho de palavra n+m menor do que o dito tamanho de palavra N, cada bloco de bits sendo dividido numa primeira porção m (14) e numa segunda porção n (16); b) para cada bloco de bits: b1) endereçar uma tabela de consulta (4), contendo 2mk bits de chave, por meio de dita primeira porção m (14) de bits, para selecionar k dentre os 2mk bits de chave, transferindo intacta a dita primeira porção m (14) de bits para uma primeira porção de bits transformados (19); b2) selecionar, por intermédio de k bits (10) selecionados, uma transformação reversível (Rk) dentre uma pluralidade de transformações reversíveis (Rk); b3) aplicar a transformação reversível (Rk) na dita segunda porção n (16) de bits, assim gerando uma segunda porção de bits transformados (18); c) coletar os bits transformados a partir de cada bloco em ditos dados digitais de saída (44), em que as referidas transformações reversíveis (Rk) são tais que cada bit de saída das referidas transformações reversíveis (Rk) seja uma função não linear de n bits de dados de entrada e dos referidos k bits de chave, com a forma normal algébrica contendo pelo menos um produto binário que envolve ambas a segunda porção n (16) de dito bloco de bits de entrada e os ditos bits de chave.

26. Método de acordo com a reivindicação 25, caracterizado pelo fato de que dita etapa b) é reiterada em um bloco de bits compreendendo ditas primeira (19) e segunda (18) porções de bits previamente transformados.

27. Método de acordo com a reivindicação 26, caracterizado pelo fato de que, antes de cada reiteração da etapa b), uma permutação de bits fixos (40) é aplicada em ditos bits previamente transformados.

28. Método de acordo com a reivindicação 26, caracterizado pelo fato de que, antes de cada reiteração da etapa b), uma função linear (40') reversível é aplicada em ditos bits previamente transformados.