BRPI0506365B1 - aparelho e método de processamento criptográfico, e, meio de armazenamento legível por computador para realizar o referido método - Google Patents

Abstract

"aparelho e método de processamento criptográfico e programa de computador para efetuar processamento criptográfico de bloco de chave comum do tipo feistel". a invenção realiza um aparelho de processamento criptográfico de alta segurança que aumenta a dificuldade de analisar sua chave, e um método para isto. no processamento criptográfico de bloco de chave comum do tipo feistel que executa repetidamente uma função f do tipo spn possuindo a seção de conversão não linear e a seção de conversão linear ao longo de diversos arredondamentos, o processamento de conversão linear de uma função f correspondente a cada um dos diversos arredondamentos é realizado por processamento de conversão linear que aplica matrizes mds quadradas (máxima distância separável). a invenção usa uma configuração em que m vetores coluna incluídos em matrizes inversas das matrizes mds quadradas sendo estabelecidos pelo menos em arredondamentos de numeração par consecutivos e em arredondamentos de numeração ímpar consecutivos, respectivamente, constitui uma matriz mds quadrada. esta estrutura realiza processamento criptográfico por meio do qual a resistência a ataque de criptoanálise linear na cifragem de bloco de chave comum é melhorada.

Description

“APARELHO E MÉTODO DE PROCESSAMENTO CRIPTOGRÁFICO, E, MEIO DE ARMAZENAMENTO LEGÍVEL POR COMPUTADOR PARA REALIZAR O REFERIDO MÉTODO”

Campo Técnico

A presente invenção refere-se a um aparelho de processamento criptográfico, um método de processamento criptográfico, bem como um meio de armazenamento legível por computador para realizar o método e, em especial, a um aparelho de processamento criptográfico com resistência melhorada para análise linear e análise diferencial conhecidas como processamento de análise de decifragem e de processamento de ataque de criptoanálise, a um método de processamento criptográfico e meio de armazenamento legível por computador para realizar o referido método.

Fundamentos da Técnica

Atualmente, com o desenvolvimento de comunicações de rede e comércio eletrônico, garantir segurança em comunicações toma-se uma questão vital. Um meio de garantir segurança é uma tecnologia criptográfica, e de modo simultâneo comunicações usando várias técnicas criptográficas estão realmente sendo executadas.

Por exemplo, tem sido posto em uso prático um sistema no qual um módulo de processamento criptográfico é embutido num pequeno dispositivo, tal como cartão IC, transmissão e recepção de dados é efetuada entre o cartão IC e um leitor/escritor atuando como um dispositivo de leitura e escrita de dados, um processamento de autenticação ou criptografia/decriptografia de dados de envio/recepção é efetuado.

Há diversos algoritmos no processamento criptográfico que são amplamente divididos no sistema criptográfico de uma chave, no qual chave de criptografia e chave de decriptografia diferentes, por exemplo, chave pública e chave secreta, são definidas e o sistema criptográfico de chave comum, no qual chave comum é definida como chave de criptografia e chave de decriptografia.

Petição 870180138490, de 05/10/2018, pág. 11/17

0¾

Há também vários algoritmos no sistema criptográfico de chave comum. Um deles é um sistema no qual diversas chaves são geradas usando uma chave comum como uma base e o processamento de conversão de dados é repetidamente efetuado para cada unidade de bloco (64 bits, 128 bits, etc.) usando as diversas chaves geradas. Um algoritmo típico que aplica tal método de geração de chave e processamento de conversão de dados é um método criptográfico de bloco de chave comum.

Como um algoritmo típico do processamento criptográfico de bloco de chave comum, por exemplo, há um algoritmo DES (Padrão de Criptografia de Dados) como um padrão de criptografia federal dos Estados Unidos, e é amplamente usado em vários campos.

Qualquer algoritmo do processamento criptográfico de bloco de chave comum tipificado pelo DES pode principalmente ser dividido em uma seção de função de arredondamento para efetuar conversão dos dados de entrada e uma seção de programa de chave para gerar uma chave a ser aplicado em cada parte da função de arredondamento (função F). Uma chave de arredondamento (subchave) a ser aplicado em cada arredondamento da seção de função de arredondamento é gerado na seção de programa de chave não qual uma chave mestre (chave principal) é inserido, e é aplicado em cada parte da função de arredondamento;

Entretanto, em tal processamento criptográfico de chave comum, o vazamento da chave por criptoanálise tem se tomado um problema. Como uma técnica típica de criptoanálise ou técnica de ataque, é conhecida uma análise diferencial (também chamada método de criptoanálise diferencial ou ataque de criptoanálise diferencial) no qual uma chave de aplicação em cada função de arredondamento é analisada, analisando muitos dados de entrada (texto comum) e seus dados de saída (texto cifrado), e uma análise linear (também chamada método de criptoanálise ou ataque de criptoanálise linear) que realiza uma análise baseada em textos comuns e textos cifrados correspondentes.

É fácil analisar uma chave por meio de criptoanálise de baixa segurança do processamento criptográfico. No algoritmo DES convencional há um problema que, uma vez que o processamento (matriz de conversão) a ser aplicado em uma seção de conversão linear em uma seção de função de arredondamento (função F) é equivalente em um arredondamento de cada estágio, a criptoanálise é fácil de fazer e consequentemente seus resultados em cada análise da chave.

Descrição da Invenção

Problema a ser Solucionado pela Invenção

Esta invenção é feita à vista dos problemas acima mencionados e tem como seu objetivo prover um aparelho de processamento criptográfico que realize um algoritmo criptográfico de chave de bloco comum altamente resistente a análise linear e análise diferencial, um método de processamento criptográfico e um programa de computador para os mesmos.

Meios para Solucionar o Problema

Um primeiro aspecto desta invenção é direcionado a um aparelho de processamento criptográfico para executar processamento criptográfico de bloco de chave comum do tipo Feistel, que é configurado para executar uma função F tipo SPN tendo uma seção de conversão não linear e a seção de conversão linear vários arredondamentos, onde a seção de conversão linear da função F correspondente a cada um dos diversos arredondamentos tem uma configuração de efetuar processamento de conversão linear para n bits emitidos de cada uma das m seções de conversão linear, no total mn bits, como processamento de conversão linear que aplica matrizes quadradas MDS (Máxima Distância Separável) e pelo menos nos arredondamentos de numeração par consecutivos e nos arredondamentos de numeração ímpar, diferentes matrizes MDS quadradas L_a e L_b são aplicadas e »* ·*· uma matriz composta de m vetores coluna selecionados arbitrariamente de vetores coluna constituindo matrizes inversas das matrizes MDS quadradas La”¹, Lb'¹ é linearmente independente.

Ainda mais, em uma realização do aparelho de processamento criptográfico desta invenção, o aparelho de processamento criptográfico é caracterizado por uma matriz composta de m vetores coluna selecionados arbitrariamente de vetores coluna constituindo as matrizes inversas L_a ^_I, Lb'¹ ser uma matriz quadrada MDS.

Ainda mais, em uma realização do aparelho de processamento criptográfico desta invenção, seu algoritmo é caracterizado pelo algoritmo de processamento criptográfico de bloco de chave comum do tipo Feistel ser um algoritmo criptográfico de nm de arredondamento 2r, e a seção de conversão linear da função F é configurada para efetuar processamento de conversão linear que aplica q espécies (2 <q < r) de diferentes matrizes MDS quadradas seqüencialmente e repetidamente em todos os r arredondamentos de numeração par e em todos os arredondamentos de numeração ímpar.

Ainda mais, em uma realização do aparelho de processamento criptográfico desta invenção, o aparelho de processamento criptográfico é caracterizado por cada uma das diversas matrizes MDS quadradas a ser aplicada na seção de conversão linear da função F ser uma matriz MDS quadrada que é composta de m vetores coluna selecionados arbitrariamente de vetores coluna constituindo as diversas matrizes MDS quadradas e é linearmente independente.

Ainda mais, em uma realização do aparelho de processamento criptográfico desta invenção, o aparelho de processamento criptográfico é caracterizado por cada uma das diversas matrizes MDS quadradas a ser aplicada na seção de conversão linear da função F ser uma matriz MDS quadrada tal como uma matriz composta de m vetores coluna selecionados arbitrariamente de vetores coluna constituindo as diversas matrizes MDS

1<L quadradas, também constituir uma matriz MDS quadrada.

Ainda mais, em uma realização do aparelho de processamento criptográfico desta invenção, o aparelho de processamento criptográfico é caracterizado por cada uma das diversas matrizes MDS quadradas a ser aplicada na seção de conversão linear da função F ser feita de uma matriz que é composta de vetores coluna extraídos de uma matriz M’ composta de vetores linha selecionados de um vetor M MDS quadrado incluindo todos os elementos constituindo as diversas matrizes MDS quadradas.

Um segundo aspecto desta invenção é um método criptográfico de executar um processamento criptográfico de bloco de chave comum do tipo Feistel, caracterizado pela função F tipo SPN para efetuar processamento de conversão não linear e o processamento de conversão linear serem repetidamente executados ao longo de diversos arredondamentos, o processamento de conversão linear da função F correspondente aos diversos arredondamentos efetua processamento de conversão linear de n bits emitidos das m seções de conversão não linear, totalizando mn bits, como processamento de conversão linear que aplica matrizes MDS quadradas (Máxima Distância Separável), pelo menos nos arredondamentos de numeração par consecutivos e nos arredondamentos de numeração ímpar consecutivos, são aplicadas diferentes matrizes MDS quadradas La'¹, L_b ^_1, e o processamento de conversão linear com matrizes MDS quadradas de tal modo que uma matriz composta de m vetores coluna selecionada arbitrariamente de vetores coluna constituindo as matrizes inversas Lf¹, Lb'¹ das matrizes MDS quadradas é linearmente independente, é efetuada.

Ainda mais, em uma realização do método de processamento criptográfico desta invenção, o aparelho de processamento criptográfico é caracterizado por efetuar processamento de conversão linear com matrizes MDS quadradas de tal modo uma matriz composta de m vetores coluna selecionada arbitrariamente de vetores coluna constituindo as matrizes ·· ··· inversas La'¹, Lb'¹ é uma matriz quadrada.

Adicionalmente, em uma realização do método de processamento criptográfico desta invenção, o algoritmo do tipo Feistel de processamento criptográfico de bloco de chave comum é caracterizado por ser um algoritmo criptográfico de número de arredondamento 2r, onde o processamento de conversão linear da função F é a execução de processamento de conversão linear aplicando q (2 < q < r) espécies de matrizes MDS quadradas diferentes seqüencialmente e repetidamente em todos os arredondamentos de numeração par e em todos os arredondamentos de numeração ímpar.

Adicionalmente, em uma realização do método de processamento criptográfico desta invenção, o método de processamento criptográfico é caracterizado por cada uma das diversas diferentes matrizes MDS quadradas a serem aplicadas ao processamento de conversão linear na função F ser uma matriz MDS quadrada que é composta de m vetores coluna selecionados arbitrariamente de vetores coluna constituindo as diversas matrizes MDS quadradas ser linearmente independente.

Ainda mais, em uma realização do método de processamento criptográfico desta invenção, o método de processamento criptográfico é caracterizado por cada uma das diversas diferentes matrizes MDS quadradas a ser aplicada ao processamento de conversão linear da função F ser uma matriz MDS quadrada que é uma matriz composta de m vetores coluna selecionados arbitrariamente a partir de vetores coluna constituindo asa diversas matrizes MDS quadradas ser também uma matriz MDS quadrada.

Adicionalmente, em uma realização do método de processamento criptográfico desta invenção, o método de processamento criptográfico é caracterizado por cada uma das diversas diferentes matrizes MDS quadradas a ser aplicada ao processamento de conversão linear da função F ser constituída de uma matriz composta de vetores coluna ·· ···

selecionados a partir de uma matriz M’ composta de vetores linha selecionados de uma matriz MDS quadrada incluindo todos os elementos constituindo as diversas matrizes MDS quadradas.

Um terceiro aspecto desta invenção é um programa de computador para efetuar o processamento criptográfico de bloco de chave comum tipo Feistel, que compreende a etapa de executar repetidamente a função F tipo SPN de efetuar processamento de conversão não linear e processamento de conversão linear ao longo de diversos arredondamentos, onde o processamento de conversão linear da função F correspondente a cada 10 um dos diversos arredondamentos é uma etapa de conversão linear de executar o processamento de conversão linear de uma entrada de n bits emitidos de cada uma das m seções de conversão não linear, totalizando mn bits, como processamento de conversão linear que aplica matrizes MDS quadradas (Máxima Distância Separável). Na etapa de conversão linear, pelo 15 menos nos arredondamentos de numeração par e nos arredondamentos de numeração ímpar consecutivos, matrizes MDS quadradas diferentes L_a, L_b são aplicadas, e cada uma das matrizes MDS quadradas é tal que uma matriz composta de m vetores coluna selecionados arbitrariamente dos vetores coluna constituindo as matrizes inversas La'¹, L_b ^_1 das matrizes MDS 20 quadradas, é linearmente independente.

Notar que o programa de computador desta invenção é um programa de computador que pode ser provido, por exemplo, a um sistema de computador capaz de executar várias chaves de programa por meio de quaisquer meios de armazenagem e meios de comunicação em uma forma 25 legível por computador (por exemplo, meios de armazenagem de um CD, um FD, um MO, etc., ou meios de comunicação de uma rede, etc.), provendo tal programa na forma legível por computador, o processamento que corresponde ao programa é realizado em um sistema de computador.

Adicionalmente, outros objetivos, características e vantagens • · · · · desta invenção tomar-se-ão aparentes a partir da seguinte descrição das realizações preferidas desta invenção, conforme ilustrado nos desenhos que a acompanham. Notar que nesta descrição, o sistema é tal que possui uma estrutura de combinação lógica de diversos dispositivos, porém não sendo y limitado a sistemas possuindo cada um seus próprios dispositivos no mesmo ^v invólucro.

De acordo com a configuração desta invenção, o processamento criptográfico é configurado conforme segue, no processamento criptográfico de bloco de chave comum do tipo Feistel para 10 executar a função F tipo SPN que tem a seção de conversão não linear e a seção de conversão linear repetidamente ao longo de diversos arredondamentos: Processamento de conversão linear da função F correspondente a cada um dos diversos arredondamentos, é executado como processamento de conversões linear que aplica matrizes MDS quadradas 15 (Máxima Distância Separável). E é configurado para executar processamento de conversão linear com matrizes MDS quadradas onde matrizes MDS quadradas L_a, Lb que são diferentes pelo menos nos arredondamentos de numeração ímpar são aplicadas, e uma matriz composta de m vetores coluna selecionadas arbitrariamente a partir de vetores coluna constituindo as 20 matrizes inversas La'¹, Lb”¹ das matrizes MDS quadradas, é linearmente independente ou faz uma matriz MDS quadrada. Consequentemente, a resistência a ataques de criptoanálise linear na cifragem de bloco de chave comum é melhorada e a dificuldade de analisar uma chave de criptografia, etc., é aumentada; portanto, processamento criptográfico de alta segurança é 25 realizado.

Adicionalmente, de acordo com a configuração desta invenção, no processamento criptográfico de bloco de chave comum do tipo Feistel no qual a função F tipo SPN tendo a seção de conversão não linear e a seção de conversão linear, é repetidamente executada ao longo de vários

arredondamentos, o processamento de conversão linear da função F correspondente a cada um dos diversos arredondamentos é executado como processamento de conversão linear que aplica matrizes MDS quadradas (Máxima Distância Separável), enquanto o processamento é configurado de 5 modo que as matrizes MDS quadradas que são diferentes pelo menos nos arredondamentos de numeração ímpar consecutivos e nos arredondamentos de numeração par consecutivos são aplicadas, e estas próprias matrizes MDS quadradas são configuradas para apresentar independência linear ou fazer matrizes MDS quadradas. Portanto, é possível garantir cancelamento de 10 diferença simultânea pela contribuição caixas S ativas não ocorrer, e conseqüentemente aumentar um número mínimo de caixas S ativas na totalidade de uma função criptográfica que é um dos índices da resistência a ataques de criptoanálise diferencial em uma cifragem de bloco de chave comum. Esta configuração melhora a resistência a ambos ataques de 15 criptoanálise linear e ataques de criptoanálise diferencial, e o processamento criptográfico de segurança mais alta é realizado.

Breve Descrição dos Desenhos

Figura 1 é um diagrama mostrando uma configuração de uma cifragem de bloco de chave comum tendo uma estrutura de Feistel.

Figuras 2A e 2B são diagramas explicando uma estrutura de uma função F sendo estabelecida como uma seção de função de arredondamento. Figura 2A é um diagrama mostrando uma entrada e uma saída da função F 120 em um arredondamento. Figura 2B é um diagrama mostrando detalhes da estrutura da função F 120.

Figura 3 é um diagrama mostrando um exemplo de uma matriz quadrada a ser aplicada a processamento de conversão linear.

Figura 4 é um diagrama explicando o cancelamento de diferença simultâneo de três estágios em uma cifragem de bloco de 128 bits de m = 8 e n = 8.

Figura 5 é um diagrama explicando um exemplo concreto de geração de uma diferença de saída de função F. AY_h efetuando conversão linear com uma matriz MDS quadrada.

Figura 6 é um diagrama explicando o cancelamento de diferença simultâneo de cinco estágios em uma cifragem de bloco de 128 bits de m = 8 e n = 8.

Figura 7 é um diagrama explicando uma definição do cancelamento de diferença simultâneo de estágio arbitrário no processamento criptográfico de bloco de chave comum.

Figura 8 mostra um exemplo da matriz MDS quadrada.

Figura 9 é um diagrama explicando um exemplo de estabelecimento de matrizes MDS quadradas como matrizes de conversão linear das funções F dos respectivos arredondamentos em um algoritmo criptográfico de bloco de chave comum de acordo com esta invenção.

Figura 10 é um fluxograma explicando uma seqüência de processamento de estabelecimento de matrizes MDS quadradas como as matrizes de conversão linear das funções F dos respectivos arredondamentos no algoritmo criptográfico de bloco de chave comum de acordo com esta invenção.

Figura 11 é um fluxograma explicando um exemplo de processamento al de geração de matrizes MDS quadradas que realizam resistência melhorada a ataques de criptoanálise diferencial como uma técnica de geração de matrizes MDS quadradas que são as matrizes de conversão linear a serem estabelecidas nas funções F dos respectivos arredondamentos.

Figura 12 é um fluxograma explicando um exemplo de processamento a2 de geração de matrizes MDS quadradas que realizam resistência melhorada a ataques de criptoanálise diferencial como uma técnica de geração de matrizes MDS quadradas que são as matrizes de conversão linear a serem estabelecidas nas funções F dos respectivos arredondamentos.

Figura 13 é um fluxograma explicando um exemplo de processamento a3 de geração de matrizes MDS quadradas que realizam resistência melhorada a ataques de criptoanálise diferencial como uma técnica de geração de matrizes MDS quadradas que são as matrizes de conversão 5 linear a serem estabelecidas nas funções F dos respectivos arredondamentos.

Figura 14 é um diagrama explicando uma técnica concreta do exemplo de processamento a3 de geração de matrizes MDS quadradas que são as matrizes de conversão linear a serem estabelecidas nas funções F dos respectivos arredondamentos.

Figura 15 é um fluxograma explicando um exemplo de processamento bl de geração de matrizes MDS quadradas que realizam resistência melhorada a ataques de criptoanálise linear como uma técnica de geração de matrizes MDS quadradas que são as matrizes de conversão linear a serem estabelecidas nas funções F dos respectivos arredondamentos.

Figura 16 é um fluxograma explicando um exemplo de processamento de geração de matrizes MDS quadradas que realizam resistência melhorada a ataques de criptoanálise linear como uma técnica de geração de matrizes MDS quadradas que são as matrizes de conversão linear a serem estabelecidas nas funções F dos respectivos arredondamentos.

Figura 17 é um fluxograma explicando um exemplo de processamento de geração de matrizes MDS quadradas que realizam resistência melhorada a ataques de criptoanálise linear como uma técnica de geração de matrizes MDS quadradas que são as matrizes de conversão linear a serem estabelecidas nas funções F dos respectivos arredondamentos.

Figura 18 é um diagrama mostrando um exemplo de uma configuração de um módulo IC como aparelho de processamento criptográfico para efetuar processamento criptográfico de acordo com esta invenção.

Melhor modo para Realizar a Invenção ·· ···

Posteriormente, detalhes de um aparelho de processamento criptográfico desta invenção, um método de processamento criptográfico e um programa de computador para os mesmos serão explicados. A explicação será dada na seguinte ordem de itens.

1. Processamento de análise diferencial em um algoritmo criptográfico de bloco de chave comum

2. Processamento de análise linear em um algoritmo criptográfico de bloco de chave comum

3. Algoritmo criptográfico baseado nesta invenção (3-a) Exemplo de geração de matrizes MDS quadradas que realizam resistência melhorada a ataques de criptoanálise diferencial e ajustando-as às funções F (3-b) Exemplo de geração de matrizes MDS quadradas que realizam resistência melhorada a ataques de criptoanálise linear e ajustando-as 15 às funções F (3-c) Exemplo de geração de matrizes MDS quadradas que realizam resistência melhorada a ataques de criptoanálise diferencial e ataques de criptoanálise linear e ajustando-as às funções F.

[1. Processamento de análise diferencial em algoritmo 20 criptográfico de bloco de chave comum]

Primeiramente, linhas gerais do processamento de análise diferencial no algoritmo criptográfico de bloco de chave comum tipificado por processamento criptográfico DES (Padrão de Criptografia de Dados) será explicado usando um modelo generalizado do processamento criptográfico de 25 bloco de chave comum.

O algoritmo do processamento criptográfico de bloco de chave comum pode ser principalmente dividido em uma seção de função de arredondamento para efetuar conversão de dados de entrada e uma seção de programação de chave para gerar uma chave a ser aplicado em cada ·· ··· arredondamento da parte da função de arredondamento, Uma chave (subchave) aplicado em cada arredondamento da função de arredondamento é gerado pela seção de programação de chave ao qual uma chave mestre (chave principal) é atribuído, baseado neste, e é aplicado em cada arredondamento.

Entre sistemas típicos deste sistema criptográfico de chave comum, há um DES (Padrão de Criptografia de Dados) como um sistema padra federal dos Estados Unidos.

Uma estrutura do processamento criptográfico de bloco de chave comum típica, chamada estrutura Feistel será explicada com referência 10 à Figurai.

A estrutura de Feistel tem uma configuração de converter um texto comum em um texto cifrado, pela simples repetição de uma função de conversão. A extensão de um texto comum é ajustada para 2mn (2xmxn) bits. Aqui, m e n são ambos inteiros. Primeiramente, um texto comum de 2mn bits 15 é dividido em dois dados de entrada, um P_L (Normal Esquerdo) lOlde mn bits e um P_R (Normal Direito) 102 de mn bits, e são usados como valores de entrada.

A estrutura de Feistel é expressa pela repetição de uma estrutura básica chamada função de arredondamento, e uma função de 20 conversão de dados sendo incluída em cada arredondamento é chamada função F 120. Figura 1 mostra um exemplo de configuração composta de funções F (funções de arredondamento) 120 repetidas por r estágios.

Por exemplo, no primeiro arredondamento, dados de entrada X de mn bits e uma chave de arredondamento kj 103 de mn bits inseridos a 25 partir de uma unidade de geração de chave (não mostrado na Figura) são inseridos na função F 120, que emite dados Y de mn bits após processamento de conversão de dados nesta. Uma seção de OU exclusivo 104 executa uma operação de OU exclusivo na saída e nas outras peças de dados de entrada a partir do estágio precedente, e emite um resultado de operação de mn bits para ãO ã próxima função de arredondamento. O processamento criptográfico se completa, aplicando este processamento, isto é, a função F repetidamente para um número de arredondamento pré-determinado (r) e emite dados divididos CL (Cifragem Esquerdo) e dados CR (Cifragem Direito) de um texto cifrado.

A configuração acima conduz a um fato de que, no sentido de executar decifragem com a estrutura de Feistel, é apenas necessário fazer uma seqüência reversa de inserir chaves de arredondamento, não necessários para configurar uma função inversa.

A estrutura da função F 120 sendo estabelecida como uma 10 função de cada arredondamento será explicada com referência à Figura 2. Figura 2A é um diagrama mostrando uma entrada e uma saída da função F 120 em um arredondamento. Figura 2Bee um diagrama mostrando detalhes da estrutura da função F 120. A função F 120 tem a assim chamada estrutura tipo SPN consistindo de uma camada de conversão não linear e uma camada de 15 conversão linear conectadas juntas, conforme mostrado na Figura 2B.

A função F 120 tipo SPN possui diversas caixas S 121 para executar processamento de conversão não linear, conforme mostrado na Figura 2B. A operação de OU exclusivo é executada em um valor de entrada X de mn bits a partir de um estágio precedente da seção de função de 20 arredondamento, juntamente com uma chave de arredondamento K_; inserido a partir da seção de programação de chave, e sua saída é inserida em diversas (m) caixas S, cada uma das quais executa processamento de conversão não linear por n bits. Cada uma das caixas S efetua processamento de conversão não linear que aplica, por exemplo, uma tabela de conversão.

Um valor de saída Z de mn bits que consiste em dados de saída da caixa S 121 é inserido em uma seção de conversão linear 122 para efetuar processamento de conversão linear, que executa processamento de conversão linear, por exemplo, processamento de troca de posições de bit, etc., e emite um valor de saída Y de m bits. O valor de saída Y juntamente com dados de entrada do estágio precedente é submetido à operação de OU exclusivo e seu resultado é designado a um valor de entrada da função F do próximo arredondamento.

Na função F 120 mostrada na Figura 2, a extensão de bit de uma entrada/saída é mxn (m, n: inteiros), a camada de conversão linear possui uma configuração na qual m caixas S 121, cada uma servindo como a camada de conversão não linear cuja entrada e saída são n bits, são arranjadas em paralelo, e a seção de conversão linear 122 como a camada de conversão linear executa processamento de conversão linear baseado em uma m-ésima 10 matriz quadrada que possui elementos em um corpo de extensão GF (2ⁿ) definido por um polinômio irredutível de grau n como seus elementos.

Figura 3 mostra um exemplo de uma matriz quadrada a ser aplicada ao processamento de conversão linear na seção de conversão linear 122. Uma matriz quadrada 125 mostrada na Figura 3 é um exemplo de n = 8 e 15 m = 8. A conversão linear é executada em mn bits de dados Z[l], Z[2],..., Z[m] emitidos a partir da seção de conversão não linear (caixa S 121) que aplica a matriz quadrada pré-determinada 125 e Y[l], Y[2],..., Y[m] como saídas da função F (função de arredondamento) são determinadas. Notar que a operação linear de elementos de uma matriz de cada um dos dados é 20 executada no campo de extensão pré-determinada GF (2ⁿ) de 2.

Uma vez que a cifragem do tipo de Feistel usada até então usa a mesma camada de conversão linear para as funções F de todos os estágios, há uma propriedade de que diversas diferenças se cancelam simultaneamente quando as diferenças se propagam. Conforme explicado no parágrafo dos 25 fundamentos da técnica, como uma técnica de criptoanálise típica, é conhecida uma análise diferencial (ou técnica de decriptografia de diferença) na qual uma chave de aplicação para cada função de arredondamento é analisado, analisando muitos dados de entrada (texto comum) e seus dados de saída (texto de cifragem). No processamento criptográfico de bloco de chave «· · »« ··· comum tal como o algoritmo criptográfico DES, uma vez que o processamento (matriz de conversão) a ser aplicado na seção de conversão linear 122 das funções F 120 é ajustado para ser equivalente em um arredondamento de cada estágio, é fácil efetuar análise diferencial, e como um 5 resultado facilita a análise de uma chave.

Um exemplo onde diversas diferenças se cancelam simultaneamente no instante de propagação das diferenças, será explicado com referência à Figura 4. Nesta descrição, ao expressar uma diferença, a diferença é indicada adicionando um símbolo Δ (delta).

Figura 4 é um diagrama explicando o cancelamento de diferença simultâneo de três estágios em um bloco de cifragem de 128 bits de m = 8 e n = 8. Notar que na figura, dados de 64 bits serão divididos por byte, cada um será expresso como um vetor, e cada elemento será representado em hexadecimal.

O cancelamento de diferença simultâneo na função F possuindo uma estrutura de três estágios ocorre, por exemplo, baseado em um mecanismo de ajuste dos seguintes estados de dados 1- 4. Os estados de dados gerados pelo mecanismo que será explicado abaixo são estados de dados que podem ser gerados estabelecendo muitos dados de entrada de diferença, isto é, 20 isto pode ser gerado analisando uma chave (chave de arredondamento) na assim chamada análise diferencial.

(Estado 1)

Suponha que a metade esquerda da diferença de entrada a arredondar i consista de diferenças de entrada toda composta de zeros (ΔΧμ = 25 (00, 00, 00, 00, 00, 00, 00, 00)) e a metade direita desta consiste de diferenças de entrada todas zero, exceto para uma entrada para somente uma caixa S (ΔΧμ = (34, 00, 00, 00, 00, 00, 00, 00)). Este estado de dados indica que, estabelecendo muitos dados de entrada de diferença, tal estado de dados pode ser obtido no arredondamento i.

Os oitos elementos em ΔΧμ = (34, 00, 00, 00, 00, 00, 00, 00) correspondem a diferenças de entrada correspondentes às respectivas m caixas S (m 8) estruturadas na função F. Uma diferença (34) é inserida na primeira caixa S ((Sl) na Figura 4 e os (00) são diferenças de entrada na segunda a oitava caixas.

Aqui, uma diferença de saída de uma caixa S tendo uma diferença de entrada de zero (00) é zero (00). Tanto quanto se sabe dos dados de diferença, a caixa S tendo uma diferença de entrada de zero (00) não causa efeito algum, consequentemente sendo chamada uma caixa S que não está ativa, isto é, uma caixa S inativa. Por outro lado, uma caixa S tendo uma diferença de entrada não zero (no exemplo da Figura 4, diferença = 34) gera um resultado de conversão não linear correspondente à diferença de entrada de não zero, sendo consequentemente chamada uma caixa S ativa.

(Estado 2)

Uma diferença de saída de uma caixa S possuindo uma diferença de entrada não zero para arredondamento i (posteriormente chamada caixa S ativa) é difusa na camada de conversão linear, e é emitida a partir da função F (valor de saída = AYj) tomando-se uma diferença de entrada ΔΧ_ί+1 para o próximo arredondamento, conforme é.

A conversão linear no exemplo da Figura 4 é tal como conversão linear com certa matriz quadrada específica 125, por exemplo, conforme mostrado na Figura 5, comum nas funções F dos respectivos arredondamentos, é executada para emitir uma diferença ΔΥ, = (98, c4, b4, d3, ac, 72, Of, 32) como uma diferença de saída de uma função F de arredondamento i. Como pode ser entendido da estrutura de conversão linear mostrada na Figura 5, a diferença de saída ΔΥ| = (98, c4, b4, d3, ac, 72, Of, 32) é determinada como um valor somente dependente de um elemento de saída Z[l] = b7 a partir de uma caixa S ativa (Sl).

Este ΔΥ = (98, c4, b4, d3, ac, 72, Of, 32) como função F emite ·· ···

diferenças deste arredondamento i, juntamente com diferenças de entrada de todos zeros (AX_i4 = (00, 00, 00, 00, 00, 00, 00, 00)) são submetidas à operação de OU exclusivo (XOR) em uma seção de OU exclusivo 131 mostrada na Figura 4, e um resultado da operação é dado como AX_i+] para o próximo arredondamento i+1.

Uma vez que os resultados das operações de OU exclusivo (XOR) em AYj = (98, c4, b4, d3, ac, 72, Of, 32), como diferenças de saída de função F de arredondamento i, e diferenças de entrada de todos zeros AXm = (00, 00, 00, 00, 00, 00, 00, 00) são AY,, as diferenças de entrada AX_i+i para o próximo arredondamento i+1 tomam-se iguais a AY_t = (98, c4, b4, d3, ac, 72, Of, 32).

(Estado 3)

Uma diferença de saída AY_i+i de uma função F de arredondamento i+1 tem o valor não zero somente em uma posição da caixa S ativa no arredondamento i. Este estado de dados indica que, estabelecendo muitos dados de entradas de diferença, tal estado de dados pode ser obtido.

Isto é, AYj+i = (ad, 00, 00, 00, 00, 00, 00, 00) e a diferença de saída AYi₊i possui um valor não zero somente em uma posição da caixa S (primeira caixa S (S1)) que tem um valor de diferença não zero, similarmente ao arredondamento i. Incidentalmente, está claro que ad Φ 00.

(Estado 4)

No caso em que uma diferença de saída de uma caixa S ativa (Sl) no arredondamento i+2 é de acordo com uma diferença de saída de uma caixa S ativa (Sl) no arredondamento i, conforme mostrado na Figura 4, uma diferença de saída da caixa S ativa (Sl) no arredondamento i+2 toma-se b7 e é de acordo com a diferença de saída (b7) da caixa S ativa (Sl). Este estado de dados indica que, estabelecendo muitos dados de entrada de diferenças, tal estado de dados pode ser obtido.

Quando este estado de dados ocorre, a diferença de saída AY_i+2 • · · · ·

= (98, c4, b4, d3, ac, 72, Of, 32) de uma função F de arredondamento i+2 concordará com a diferença de saída ΔΥι = (98, c4, b4, d3, ac, 72, Of, 32) da função F de arredondamento que é um arredondamento prévio, porém um arredondamento.

Como um resultado, uma seção de OU exclusivo 133 executará a operação de OU exclusivo em AX_i+i = AYj = (98, c4, b4, d3, ac, 72, Of, 32) e AY_i+2- (98, c4, b4, d3, ac, 72, Of, 32), que são ambos os mesmos valores e emitirão valores de todos os zeros como um resultado da operação de OU exclusivo.

Como um resultado a diferença de entrada esquerda AX_i+3 do estágio precedente (arredondamento i+2) que produz a diferença de saída para o próximo estágio (arredondamento i+3) toma-se AX_i+3 = (00, 00, 00, 00, 00, 00, 00, 00).

A entrada esquerda AX_i+3 = (00, 00, 00, 00, 00, 00, 00, 00) para este arredondamento i+3 consiste toda de zeros como com a diferença de entrada esquerda AX^ = (00, 00, 00, 00, 00, 00, 00, 00) para o arredondamento i, e há a possibilidade de que o mesmo processamento dos arredondamentos i a i+2 seja repetido também no arredondamento i+3 e arredondamentos posteriores.

Como resultado, surge um problema de que o número de caixas S ativas não aumentará em comparação a um aumento do número de arredondamento, e a robustez a ataques de criptoanálise diferencial não será muito melhorada.

Na cifragem de bloco de chave comum, um número mínimo de caixas S ativas na totalidade da função criptográfica é conhecido como um dos índices de robustez aos ataques de criptoanálise diferencial. Quanto maior o número mínimo de caixas S ativas, mais alta a resistência a ataques de criptoanálise diferencial é determinada.

Conforme descrito acima, a análise diferencial (ataque de ·· ···

criptoanálise diferencial) é uma técnica para analisar uma chave de aplicação, em cada função de arredondamento, estabelecendo muitos dados de entrada (textos comuns) com uma certa diferença e seus dados de saída (textos cifrados) e analisando esta correspondência. Se o número de caixas S ativas pode ser reduzido nesta análise diferencial, a análise tomar-se-á fácil e o número de processos de análise poderá ser reduzido.

Embora o exemplo referente à Figura 4 acima mencionada, um estado de ocorrência de uma configuração onde apenas uma primeira caixa S (Sl) é uma caixa S ativa, para outras caixas S (S2 - S8), um ajuste no qual cada caixa S é estabelecida para ser uma caixa ativa, é possível, estabelecendo dados de entrada na análise diferencial. Portanto, realizando um processo de análise diferencial como este, toma-se possível analisar procedimento de conversão não linear de cada caixa S, e análise adicional de uma chave de arredondamento inserido para a função F.

No sentido de aumentar a resistência a análise diferencial como esta, é necessário manter um estado onde o número de caixas S ativas seja sempre grande, isto é, o número mínimo de caixas S ativas seja grande.

No exemplo explicado com referência à Figura 4, no caso da função F à qual é dada uma entrada em uma direção a partir da direita para a esquerda, isto é, ao considerar apenas o arredondamento i e o arredondamento i+2 como arredondamentos objeto do processamento de cálculo da caixa S ativa, o número de caixas S ativas é de apenas duas, nas funções F para cujas entradas são dadas em uma direção a partir da esquerda ou da direita, o número de caixas S ativas toma-se zero pelo cancelamento da diferença simultânea, e conseqüentemente o processamento de análise de processamento de conversão não linear de cada caixa S pela análise diferencial toma-se fácil.

O processamento criptográfico de bloco de chave comum mostrado na Figura 4 consiste nas matrizes de conversão linear aplicadas nas seções de conversão linear nos respectivos arredondamentos serem iguais, e esta configuração particular conduz à possibilidade de que o cancelamento de diferença simultânea seja causado apenas por apenas duas caixas S ativas, especialmente nas funções F às quais é dada uma entrada e uma direção da direita para a esquerda. Portanto, há um problema de que o número mínimo de caixas S ativas não aumenta plenamente em comparação com o crescimento do número de arredondamento, e a robustez contra ataques de criptoanálise diferencial não aumenta muito.

A seguir, similarmente, na configuração na qual a mesma matriz de conversão linear é usada para as funções F de todos os estágios (arredondamentos) um mecanismo de ocorrência do cancelamento de diferença simultânea ao longo de cinco arredondamentos será explicado com referência à Figura 6.

Figura 6 é um diagrama explicando o cancelamento de diferença simultâneo de cinco estágios em uma cifragem de bloco de 128 bits dem = 8 en = 8. Notar que, na figura, dados de 64 bits serão representados como vetores, dividindo-os por um byte e cada elemento será representado em hexadecimal.

O cancelamento de diferença simultâneo da função F com uma configuração de cinco estágios ocorre, por exemplo, baseado no seguinte mecanismo de ajuste dos estados de dados 1-7. O estado de dados gerado por um mecanismo explicado abaixo é um estado de dados que pode ser gerado estabelecendo muitos dados de entradas de diferença, e o estado de dados pode ser gerado analisando uma chave (chave de arredondamento) na assim chamada análise diferencial.

(Estado 1)

Seja uma metade esquerda de diferenças de entrada de arredondamento i consistindo de diferenças de entrada todas zeros (ΔΧ,-ι = (00, 00, 00, 00, 00, 00, 00, 00)) e uma metade direita de diferenças de entrada consistindo de diferenças de entrada todas zero exceto para uma entrada para apenas uma caixa S (ΔΧ, = (34, 00, 00, 00, 00, 00, 00, 00)). Este estado de dados indica que, estabelecendo muitos dados de entradas de diferença tal estado de dados pode ser obtido no arredondamento i.

Oito elementos ΔΧ] = (34, 00, 00, 00, 00, 00, 00, 00) correspondem a respectivas diferenças de entrada para m (m = 8) caixas S ativas configuradas nas funções F. (34) é inserido em uma primeira caixa S ((Sl) na Figura 6) e (00) são diferenças de entrada para a segunda a oitava caixas.

Conforme descrito acima, qualquer diferença de saída de caixa S possuindo uma diferença de entrada de zero (00) é zero (00). Tanto quanto se conhece da diferença de saída, a caixa S tendo uma diferença de entrada de zero não executa qualquer operação, sendo conseqüentemente chamada uma caixa S que não está ativa, a saber, uma caixa S inativa. Por outro lado, uma vez que somente uma caixa S (Sl) com a diferença de entrada não zero (no exemplo da Figura 6, diferença =34) gera um resultado de conversão não linear correspondente à diferença de entrada de não zero como uma diferença de saída, sendo conseqüentemente chamada uma caixa S ativa.

No exemplo da Figura 6, uma caixa S ativa (Sl) à qual uma diferença de entrada 34 de não zero é inserida, gera uma diferença de saída (b7) e outras caixas S ativas inativas S2-S8 geram diferenças de saída (00) baseadas nas diferenças de entrada (00) de zeros, que são designadas como entradas de diferença da seção de conversão linear.

(Estado 2)

Uma diferença de saída de uma caixa S (posteriormente chamada uma caixa S ativa) que possui uma diferença de entrada não zero para arredondamento i (no exemplo da Figura 4, diferença = 34) é difusa na camada de conversão linear, e emitida a partir da função F (valor de saída = ΔΥί) tomando-se uma diferença de entrada ΔΧ_ί+ι para o próximo arredondamento, conforme é.

No exemplo da Figura 6, a conversão linear é executada com certa matriz quadrada específica 125, que é comum a todo arredondamento, por exemplo, o que é mostrado na Figura 5, e ΔΥ, = (98, c4, b4, d3, ac, 72, Of, 5 32) como uma diferença de saída de uma função F de arredondamento i é emitida.

ΔΥί = (98, c4, b4, d3, ac, 72, Of, 32) como diferenças de saída de função F de arredondamento i, é submetido à operações de OU exclusivo em uma seção 141 mostrada na Figura 6, juntamente com diferenças de 10 entrada todas zero (ΔΧ,-ι - (00, 00, 00, 00, 00, 00, 00, 00)) e os resultados de operação tomam-se diferenças de entrada para o próximo arredondamento i+1.

Uma vez que os resultados das operações de OU exclusivo (XOR) em AY, = (98, c4, b4, d3, ac, 72, Of, 32), como diferenças de saída de 15 função F de arredondamento i, e diferenças de entrada de todos zeros AXm = (00, 00, 00, 00, 00, 00, 00, 00) são ΔΥί, diferenças de entrada para o próximo arredondamento i+1 tomam-se AX_i+i = ÁYj = (98, c4, b4, d3, ac, 72, Of, 32).

(Estado 3)

Uma diferença de saída AY_i+i da função F de arredondamento 20 i+1 tem o valor não zero somente em uma posição da caixa S ativa no arredondamento i. Este estado de dados indica que, estabelecendo muitos dados de entradas de diferença, tal estado de dados pode ser obtido.

Isto é, AY_i+] é AYi₊i = (34, 00, 00, 00, 00, 00, 00, 00) e tem um valor não zero somente em uma posição da caixa S (primeira caixa S (Sl)) 25 que tem um valor de diferença não zero (no exemplo da Figura 6, diferença ~ 34) como com o arredondamento i.

(Estado 4)

Uma entrada para a função F de arredondamento i+2 é um resultado da operação de OU exclusivo na seção de OU exclusivo 142 em AX,

3>o = (34, 00, 00, 00, 00, 00, 00, 00) e ΔΥ_ί+1 = (34, 00, 00, 00, 00, 00, 00, 00) que são ambos os mesmos dados, e se tomam uma entrada consistindo todas de zeros AX_í+2 = (00, 00, 00, 00, 00, 00, 00, 00). Como um resultado, uma diferença de saída da função F de arredondamento i+2 também se toma uma 5 diferença de saída consistindo toda de zeros, ΔΥ_ί+2 = (00, 00, 00, 00, 00, 00, 00, 00).

(Estado 5)

Entradas para uma função F de arredondamento i+3 são resultados da operação de OU exclusivo na seção de OU exclusivo 143 em 10 ΔΧ₁₊₁ = (98, c4, b4, d3, ac, 72, Of, 32) e ΔΥ_ί+2 - (00, 00, 00, 00, 00, 00, 00, 00) que são diferenças de saída de função F de arredondamento i+2 de todos zeros, e tomam-se entradas ΔΧί+3 = ΔΧί+ι = (98, c4, b4, d3, ac, 72, Of, 32) para a função de arredondamento i+3.

(Estado 6)

Diferenças de saída de função F de arredondamento i+3 tomam-se ΔΥ]₊₃ = (43, 00, 00, 00, 00, 00, 00, 00). As operações de OU exclusivo na seção de OU exclusivo 144 nestas diferenças, juntamente com ΔΧ_ί+2 = (00, 00, 00, 00, 00, 00, 00, 00) consistindo de todos zeros resulta em ΔΧί+4 = ΔΥ_]+3 = (43, 00, 00, 00, 00, 00, 00, 00), que se transforma em 20 diferenças de entrada de função F de arredondamento i+4.

(Estado 7)

Quando uma diferença de saída de uma caixa S ativa (Sl) no arredondamento i+4 é de acordo com uma diferença de saída da caixa S ativa (Sl) no arredondamento i, uma diferença de saída da caixa S ativa (Sl) no 25 arredondamento i+4 toma-se b7, conforme mostrado na Figura 6, e de acordo com uma diferença de saída (b7) da caixa S ativa (Sl) no arredondamento i. Este estado de dados indica que, estabelecendo muitos dados de entrada de diferença, tal estado de dados pode ser obtido.

Quando este estado de dados ocorre, a diferença de saída AY_i+4

34.

= (98, c4, b4, d3, ac, 72, Of, 32) de uma função F de arredondamento i+4 será de acordo com a diferença de saída ΔΧί₊₃ = (98, c4, b4, d3, ac, 72, Of, 32) da seção de OU exclusivo 143 de arredondamento i+1 que é o arredondamento prévio mais um.

Como resultado, na seção de OU exclusivo 145, ΔΧ_ί+3 = (98, c4, b4, d3, ac, 72, Of, 32) e ΔΥ_Η4 = (98, c4, b4, d3, ac, 72, Of, 32), que são ambos o mesmo valor, serão submetidos à operação de OU exclusivo, emitindo valores todos zeros como resultado da operação de OU exclusivo.

Conseqüentemente, diferenças de entrada para o próximo estágio (arredondamento i+5) são estabelecidas como ΔΧί₊₅ = (00, 00, 00, 00, 00, 00, 00, 00).

Esta entrada esquerda para este arredondamento i+5, ΔΧ_ί+5 = (00, 00, 00, 00, 00, 00, 00, 00) consiste de todos zeros como com a entrada esquerda para arredondamento i, ΔΧ;.] = (00, 00, 00, 00, 00, 00, 00, 00) e há a possibilidade de que o mesmo processamento do arredondamento i para o arredondamento i+4 seja repetido também no arredondamento i+5 e arredondamentos posteriores.

Consequentemente, um problema de que o número de caixas S ativas não aumenta em comparação com o aumento do número de arredondamento, e a robustez contra ataques de criptoanálise diferencial não aumenta tanto.

Conforme descrito acima, a análise diferencial (ataque de criptoanálise diferencial) é uma técnica de analisar uma chave de aplicação em cada função de arredondamento, ajustando muitos dados de entrada (texto comum) tendo uma certa diferença e seus dados de saída (texto cifrado) e analisar esta correspondência. Nesta análise diferencial, se o número de caixas ativas S pode ser reduzido, a análise se tomará fácil e o número de processos de análise será capaz de ser reduzido.

No exemplo referindo-se à Figura 6 descrita acima, no caso de *·· «· *·· funções F cujas entradas são dadas em uma direção da direita para a esquerda, isto é, no caso em que o arredondamento i, arredondamento i+2 e arredondamento i+4 são considerados como arredondamentos alvo do cálculo da caixa S ativa, o número de caixas S ativas é apenas dois, uma soma do arredondamento i = l, arredondamento i+2 = 0 e arredondamento i+4 = 1. No caso das funções F cujas entradas são dadas em uma direção da esquerda para a direita, isto é, no caso em que o arredondamento i+1 e o arredondamento i+3 são considerados como arredondamentos alvo, embora o número de caixas S ativas seja oito, o número de caixas S ativas no arredondamento i+5 toma-se zero devido ao cancelamento de diferença simultâneo; portanto, a análise de processamento de conversão não linear de cada caixa S por análise diferencial e processamento de criptoanálise de uma chave de arredondamento de entrada pára a função F toma-se comparativamente fácil.

Embora o exemplo referindo-se à Figura 6 apresente um estado de ocorrência de uma configuração onde somente a primeira caixa S (Sl) é uma caixa S ativa, com vistas a outras caixas S (S2 a S8), o ajuste dos dados de entrada de análise diferencial habilita qualquer uma das outras caixas S a serem ajustadas como uma caixa S ativa, portanto, a execução de tal processo de análise diferencial tomará possível analisar processamento de conversão não linear de cada caixa S e adicionalmente analisar a chave de arredondamento inserido na função F.

Embora o exemplo de ocorrência de cancelamento de diferença simultâneo nos casos de três e cinco arredondamentos tenha sido explicado com referência à Figura 4 e Figura 6, se estes casos são generalizados para número de arredondamento arbitrário para definir o cancelamento de diferença simultâneo, a definição pode ser dada como segue. Com referência à Figura 7, a definição do cancelamento de diferença simultâneo em um número de arredondamento arbitrário será explicado. Figura 7 mostra arredondamentos seriais “mais um” (i, i+2, i+4,...,i+2j) da

·· ··· estrutura de Feistel que executa o processamento criptográfico de bloco de chave comum da estrutura Feistel.

“Definição”

Em um processo onde uma metade das diferenças de entrada da estrutura de Feistel no arredondamento i consiste de zeros (na Figura 7,

AXj = (00, 00, 00, 00, 00, 00, 00, 00) e cada uma delas e cada uma das diferenças de saída da função F de arredondamento i + 2j são submetidas à operação de OU exclusivo na seção de OU exclusivo, um caso onde resultados da operação de OU exclusivo tomam-se zeros na Figura 7, AX^j+i 10 = (00, 00, 00, 00, 00, 00, 00, 00) é chamado cancelamento de diferença simultâneo.

Neste instante, caixas S ativas existentes nas funções F de arredondamentos i, i + 2, i + 4,..., i +2k são chamadas caixas S ativas que causam o cancelamento de diferença simultâneo. Definindo o número de 15 elementos não zeros de um vetor A como Ponderação de Hamming hw (A), o número “A” de caixas S ativas que causam o cancelamento de diferença simultâneo pode ser expresso pela seguinte equação.

[Equação 1] α = Σ MM_í+2j) >0

Nos exemplos de três arredondamentos e cinco 20 arredondamentos descritos acima, o número de caixas S ativas que causa o cancelamento de diferença simultâneo é dois, em ambos, isto é, a = 2.

Conforme descrito acima, um dos índices de robustez contra ataques de criptoanálise diferencial na cifragem de bloco de chave comum é o número mínimo de caixas S ativas na totalidade das funções criptográficas, e 25 é determinado que quanto maior o número mínimo de caixas S ativas, mais alta a resistência a ataques de criptoanálise diferencial se toma.

Entretanto, na configuração onde a mesma matriz de conversão linear é usada para as funções F de todos os estágios, como no

algoritmo DES, existe a possibilidade de que apenas duas caixas S ativas causem o cancelamento de diferença simultâneo, como pode ser entendido da explicação com referência às Figuras 4 e 6. Há um problema de que, devido à presença de tal propriedade, o número mínimo de caixas S ativas não aumenta suficientemente e a robustez contra ataques de criptoanálise diferencial não é tão reforçada.

[2. Processamento de análise linear no algoritmo criptográfico de bloco de chave comum]

O processamento de análise diferencial, conforme descrito acima, requer que um executor da análise prepare dados de entrada (texto comum) possuindo uma diferença constante e analise seus dados de saída correspondentes (texto cifrado). Para processamento de análise linear, não é necessário preparar dados de entrada (texto comum) tendo uma diferença constante e a análise é executada com base nos dados de entrada (texto comum) cuja quantidade é igual ou mais do que uma quantidade prédeterminada e seus dados de saída correspondentes (texto cifrado).

Conforme descrito acima, no algoritmo criptográfico de bloco de chave comum, caixas S como a seção de conversão não linear são preparadas e não há relação linear entre os dados de entrada (texto comum) e seus dados de saída correspondentes (texto cifrado). Na análise linear, a análise é executada aproximando linearmente a entrada/saída desta caixa S, analisando uma relação linear entre muitos dados de entrada (texto comum) e valores de bits constituintes dos dados de saída correspondentes (texto cifrado) e reduzindo-se a chaves que são supostos candidatos. Na análise linear, não é necessário preparar dados de entrada com uma diferença específica, e a análise se toma possível somente preparando um grande número de textos comuns e seus textos cifrados correspondentes.

[3. Algoritmo criptográfico baseado nesta invenção]

Posteriormente, um algoritmo criptográfico desta invenção

será explicado. O algoritmo criptográfico desta invenção possui uma estrutura que melhora a resistência a ataques de criptoanálise linear, ataques de criptoanálise diferencial descritos acima, e similares, isto é, tendo uma estrutura que melhora a dificuldade de análise de chave e reforça a segurança.

Uma das características do algoritmo criptográfico correspondente a esta invenção é que o algoritmo é construído estabelecendo diversas matrizes MDS quadradas (Máxima Distância Separável) diferentes ao invés de uma estrutura na qual o processamento comum (matriz de conversão) é aplicado à seção de conversão linear de uma função F de cada arredondamento, como com o algoritmo DES convencional. Especificamente, o algoritmo é configurado para executar processamento de conversão linear aplicando matrizes MDS quadradas que são diferentes pelo menos nos arredondamentos de numeração par consecutivos e nos arredondamentos de numeração ímpar consecutivos.

O algoritmo criptográfico correspondente a esta invenção implementa uma estrutura com a qual o cancelamento de diferença simultâneo baseado em um pequeno número de caixas S ativas não ocorre ou é menos provável de ocorrer usando propriedades das matrizes MDS quadradas (Máxima Distância Separável), de tal modo que o número mínimo de caixas S ativas é aumentado e o processamento criptográfico de bloco de chave comum mais robusto quanto a ataques de criptoanálise diferencial é realizado. Altemativamente, esta invenção implementa uma estrutura com a qual é causada dificuldade de análise linear com um ataque de criptoanálise de um texto comum conhecido.

O algoritmo criptográfico desta invenção aplica uma estrutura criptográfica de bloco de chave comum típica que é chamada estrutura de Feistel possuindo funções F tipo SPN explicadas com referência às Figuras 1 e 2, isto é, aplica uma estrutura que converte um texto comum para um texto cifrado ou converte um texto cifrado para um texto comum pela simples

repetição da função F tipo SPN que possui a seção de conversão não linear e a seção de conversão linear ao longo de diversos arredondamentos.

Por exemplo, a extensão de um texto comum é suposta como 2mn bits (aqui, m e n sendo ambos inteiros). A estrutura de vídeo em um texto comum de 2mn bits em dois dados PL (Comum Esquerdo e Comum Direito) cada um de mn bits, e executa a função F em cada arredondamento usando-os como valores de entrada. A função F é uma função F com um tipo SPN consistindo da seção de conversão não linear composta de caixas S e da seção de conversão linear conectadas juntas.

Na configuração desta invenção, como uma matriz para o processamento de conversão linear a ser aplicado à seção de conversão linear na função F, matrizes selecionadas dentre diversas matrizes MDS quadradas (Máxima Distância Separável) são estabelecidas como matrizes a serem aplicadas nas seções de conversão linear das funções F dos respectivos arredondamentos. Especificamente, matrizes MDS quadradas que são diferentes pelo menos nos arredondamentos de numeração par consecutivos e nos arredondamentos de numeração ímpar consecutivos são aplicadas.

A matriz MDS quadrada será explicada. A matriz quadrada é uma matriz satisfazendo a propriedades de (a) e (b) abaixo, (a) A matriz é uma matriz quadrada, (b) Determinantes de todas as submatrizes incluídas em uma matriz não são zero, a saber det (submatriz) Φ 0.

A matriz satisfazendo às condições de (a) e (b) acima é chamada matriz MDS quadrada. As extensões de bits de entrada/saída para a função F sendo executada em cada arredondamento do processamento criptográfico de bloco de chave comum é de mxn bits (m, n: inteiros). Figura 8 mostra um exemplo da matriz MDS quadrada no caso em que a seção de conversão não linear configurada na função F é construída com m caixas S, cada uma possuindo n bits de entrada/saída, e a seção de conversão linear executa processamento de conversão linear com base nas matrizes quadradas

mxm tendo cada uma elementos no campo de extensão GF (2ⁿ) de 2 definido por um polinômio irredutível de grau n como seus elementos. Um exemplo da matriz MDS quadrada mostrada na Figura 8 é um exemplo da matriz MDS quadrada de n = 8 e m = 8.

Designando o número de elementos não zeros no vetor A pela Ponderação de Hamming hw (A), uma matriz MDS quadrada mxm por M, e um vetor de entrada para a matriz MDS quadrada M por x, uma matriz MDS quadrada satisfazendo (a) e (b) acima satisfaz a seguinte desigualdade (Equação 1).

hw(x) + hw(M_x) > m+1............................(Equação 1)

A expressão acima mencionada (Equação 1) indica que o número total de elementos não zero hw(x) dos dados de entrada x para serem linearmente convertidos pela matriz MDS quadrada (M) mais o número de elementos não zeros hw(M_x) dos dados de saída M_x que foram convertidos linearmente pela matriz MDS quadrada (M) é maior que o número de ordem m da matriz MDS quadrada.

Incidentalmente, o nome da matriz MDS quadrada é dado porque uma metade direita de uma forma padrão de uma matriz de geração da chave MDS quadrado (Máxima Distância de Chave Separável) satisfaz às condições acima mencionadas.

É sabido que, mesmo na configuração convencional na qual uma única matriz é incorporada em todas as funções F, o uso de uma matriz MDS quadrada como uma matriz de conversão linear habilita o número mínimo de caixas S ativas a ser mantido em um nível comparativamente alto, se comparado com um caso em que uma matriz diferente da matriz MDS quadrada for usada.

Esta invenção propõe um método para usar uma matriz satisfazendo as condições da matriz MDS quadrada para a função F de cada arredondamento e estabelecendo adicionalmente diferentes matrizes para

3¾

arredondamentos respectivos. Especificamente, matrizes MDS quadradas que são diferentes pelo menos nos arredondamentos de numeração par consecutivos e arredondamentos de numeração ímpar consecutivos são aplicadas.

Diversos exemplos de configurações em cada uma das quais a resistência a ataques de criptoanálise diferencial é tomada mais alta na cifragem de bloco de chave comum do tipo Feistel do número de estágio 2r (r sendo um inteiro) serão explicados abaixo.

Na explicação seguinte, MLTj denota a matriz de conversão linear a ser aplicada na seção de conversão linear da função F do j-ésimo estágio na estrutura criptográfica de bloco de chave comum do tipo Feistel do estágio número 2r (número de arredondamento).

Na configuração desta invenção, como uma matriz para processamento de conversão linear a ser aplicada na seção de conversão linear da função F de cada estágio na estrutura criptográfica de bloco de chave comum do tipo Feistel de número de estágio 2r (número de arredondamento), matrizes selecionadas dentre diversas matrizes MDS quadradas (Máxima Distância Separável) diferentes são estabelecidas como matrizes a serem aplicadas nas seções de conversão linear das funções F dos respectivos arredondamentos. Especifícamente, matrizes MDS quadradas que são diferentes pelo menos nos arredondamentos de numeração par consecutivos e nos arredondamentos de numeração ímpar consecutivos são aplicadas.

Especificamente, em conformidade com a estrutura criptográfica de bloco de chave comum do tipo Feistel de número de estágio (número de arredondamento) 2r, q matrizes MDS quadradas L_b L_q são geradas (q < r). Então, como matrizes para o processamento de conversão linear a ser aplicado nas seções de conversão linear nas funções F dos estágios de numeração ímpar da estrutura criptográfica de bloco de chave comum do tipo Feistel de número de estágio (número de arredondamento) 2r, q matrizes • · ·

MDS quadradas são repetidamente estabelecidas designando L_b L₂,..., L_q, L_b L₂₎... a partir de seu estágio superior das funções F. Ainda mais, para as funções F de estágios de numeração par, q matrizes MDS quadradas são repetidamente estabelecidas designando L_b L₂,..., L_q, L_b L₂,... a partir de seu estágio inferior das funções F.

Figura 9 mostra um exemplo de configuração ao qual esta configuração é aplicada. Como um exemplo de configuração no qual três espécies de matrizes MDS quadradas diferentes são arranjadas na estrutura criptográfica de bloco de chave comum do tipo Feistel de q = 3, a saber o número de arredondamento 12 no caso em que uma estrutura é definida como a estrutura criptográfica de bloco de chave comum do tipo Feistel de número de estágio (número de arredondamento) 2r = 12, a saber r = 6, matrizes MDS quadradas (L_b L₂, L₃) a serem estabelecidas nas seções de conversão linear nos respectivos arredondamentos são mostradas na Figura 9.

A configuração da Figura 9 é uma estrutura que divide um texto comum de mn bits em dois dados de PL (Comum Esquerdo) e PR (Comum Direito) de mn bits cada, e executa uma função F em cada arredondamento, usando-os como valores de entrada. A função F do primeiro arredondamento bem como as funções F de outros arredondamentos são funções F cada uma com o tipo SPN consistindo da seção de conversão não linear composta de caixas S e da seção de conversão linear conectadas juntas.

O exemplo de configuração da Figura 9 é de r = 6 e q = 3, onde um símbolo L_n mostrado em cada função F denota uma matriz MDS quadrada 402. Isto é, L_b L₂ e L₃ denotam três espécies de matrizes MDS quadradas mutuamente diferentes, cada uma das quais é uma matriz MDS quadrada a ser aplicada a processamento de conversão linear na seção de conversão linear de cada função F.

Uma seqüência de processamento de configuração da matriz de conversão linear MLTj será explicada com referência à Figura 10.

• * *·♦ [Etapa S21]

Número q igual ou menor à metade r do número de arredondamento 2r, a saber q satisfazendo q < r é selecionado. Aqui, q é um inteiro de dois ou mais.

[Etapa S22] q matrizes MDS quadradas de ordem m L_b L₂,..., L_q em GF (2ⁿ) são geradas. Detalhes das q matrizes MDS quadradas de ordem m L_b L₂,..., L_q em GF (2ⁿ) serão explicados em um parágrafo posterior.

Após as q matrizes MDS quadradas de ordem m L_b L₂,..., L_q 10 em GF (2ⁿ) serem geradas na Etapa S22, processamento de configuração de matriz MDS quadrada abaixo é executado.

[Etapa S23]

A matriz de conversão linear MLT_2i_i do estágio número 2i-l (1 < i < r) é estabelecida para L(_i4modq) + _b [Etapa S24]

A matriz de conversão linear MLTj do estágio número 2i (1 < i < r) é estabelecida para MLT_2r-2i+i.

Por exemplo, no caso do exemplo de configuração mostrado na Figura 9, isto é, no caso em que o aparelho de processamento criptográfico 20 possui 12 estágios (r = 6) e q = 3, o ajuste será:

MLTi = L_b MLT₂ = L₃, MLT₃ = L₂, MLT₄ = L₂, MLT₅ - L₃, MLT₆ = L_b MLT₇ - L_b MLT₈ = L₃, MLT₉ = L₂, MLT_l0 - L₂, MLT_n = L₃, MLT₁₂=L_b

Então, o aparelho de processamento criptográfico desta 25 invenção usa a seguinte estrutura. Em conformidade com a estrutura criptográfica de bloco de chave comum do tipo Feistel de número de estágio (número de arredondamento) 2r, q matrizes MDS quadradas são geradas onde q < r. Para as funções F dos estágio de numeração ímpar, q matrizes MDS quadradas são repetidamente estabelecidas designando L_b L₂,..., L_q, L_b L₂,...

seqüencialmente a partir de seu estágio superior da função F, e para as funções F de estágios de numeração par, q matrizes MDS quadradas são repetidamente estabelecidas designando Lj, L₂,..., L_q, Li, L₂,... seqüencialmente a partir da função F do estágio inferior.

A seguir, detalhes das q matrizes MDS quadradas de ordem m Li, L₂,..., L_q em GF (2ⁿ) na Etapa S22 no fluxo de processamento da Figura 10 e configurando-as para as funções F serão explicados. A explicação será dada juntamente com os itens seguintes.

(3-a) Exemplo de geração de matrizes MDS quadradas que realizam resistência melhorada a ataques de criptoanálise diferencial e configurando-as para as funções F.

(3-b) Exemplo de geração de matrizes MDS quadradas que realizam resistência melhorada a ataques de criptoanálise linear e configurando-as para as funções F.

(3-c) Exemplo de geração de matrizes MDS quadradas que realizam resistência melhorada a ataques de criptoanálise diferencial e ataques de criptoanálise linear, e configurando-as para as funções F.

(3-a) Exemplo de geração de matrizes MDS quadradas que realizam resistência melhorada a ataques de criptoanálise diferencial e configurando-as para as funções F. Primeiramente, como um exemplo de geração de matrizes MDS quadradas que realizam resistência melhorada a ataques de criptoanálise diferencial e configurando-as para as funções F, três exemplos de processamento al, a2 e a3 serão explicados.

(Exemplo de processamento al)

Um primeiro exemplo de geração de matrizes MDS quadradas que realizam resistência melhorada a ataques de criptoanálise diferencial e configurando-as para as funções F será explicado. Primeiramente, a explicação será dada para processamento de geração de uma matriz MDS quadrada com referência a um fluxograma mostrado na Figura 11.

[Etapa S101]

Designação de entrada: o número de matrizes MDS quadradas necessárias por q, uma ordem de extensão por n, e um tamanho de matriz por m, as q matrizes MDS quadradas de ordem m L_b L_q são geradas randomicamente em GF(2ⁿ). O fluxograma mostrado na Figura 11 mostra um exemplo de processamento como com o número de matrizes MDS q = 6, ordem de extensão n = 8 e tamanho de matriz m = 8.

[Etapa S102]

É verificado se vetores coluna arbitrários qm obtidos de vetores coluna qm incluídos nas q matrizes MDS quadradas de ordem m L_b L_2}..._? L_q são linearmente independentes. Se o fluxo passou na verificação, o fluxo avança para a etapa S103; se não for o caso, o fluxo retoma à etapa S101.

[EtapaS 103]

As q matrizes MDS quadradas de ordem m L_b L₂,..., L_q são emitidas como matrizes MDS quadradas a serem aplicadas à cifragem de bloco de chave comum do tipo Feistel de número de arredondamento 2r.

Através do processo acima, as q matrizes MDS quadradas de ordem m L_b L₂,..., L_q são geradas. Aqui, q satisfaz q < r.

As q matrizes MDS quadradas de ordem m L_b L₂,..., L_q geradas deste modo são configuradas como matrizes a serem aplicadas ao processamento de conversão linear na seção de conversão linear da função F de cada estágio na estrutura criptográfica de bloco de chave comum do tipo Feistel de número de estágio (número de arredondamento) 2r, de acordo com o processamento da [Etapa S23] e [Etapa S24] explicado previamente com referência à Figura 10. Isto é„ para estágios de numeração ímpar, q matrizes MDS quadradas são designadas por L_b L₂,..., L_q, L_b L₂,... seqüencialmente e repetidamente a partir da função F do estágio inferior.

Então, as matrizes MDS quadradas de arredondamentos de • · ·

numeração par e as matrizes MDS quadradas de arredondamentos de numeração ímpar são arranjadas em ordens mutuamente reversas, respectivamente por meio das quais é garantido que o processamento de criptografia e o processamento de decriptografia são os mesmos, exceto para processamento de substituição de uma seqüência de chaves.

Esta configuração garante o seguinte, (a) A matriz de conversão linear de cada função F é uma matriz MDS quadrada, (b) Vetores de m colunas arbitrários a partir das matrizes de conversão linear incluídas em pelo menos q funções F consecutivas em arredondamentos de numeração ímpar em uma função criptográfica são linearmente independentes, (c) Vetores de m colunas arbitrários a partir das matrizes de conversão linear incluídas em pelo menos q funções F consecutivas em arredondamentos de numeração par em uma função criptográfica são linearmente independentes. Desde que os aspectos (a) a (c) são garantidos, é garantido que, na estrutura criptográfica de bloco de chave comum do tipo Feistel possuindo diversos arredondamentos, o cancelamento de diferença simultâneo pela contribuição de m ou menos caixas S ativas não ocorre. Portanto, o valor mínimo do número de caixas S ativas na totalidade da função criptográfica aumentará.

Então, este exemplo de processamento toma possível aumentar o número mínimo de caixas S ativas na totalidade da função criptográfica que é uma dos índices de robustez contra ataques de criptoanálise diferencial na cifragem de bloco de chave comum. Como resultado, o número de caixas S ativas quando a análise diferencial (ataque de criptoanálise diferencial) é tentada, aumentará, e a dificuldade da análise será reforçada. Portanto, processamento criptográfico de alta segurança cuja chave é difícil de analisar, é realizado.

(Exemplo de processamento a2)

Um segundo exemplo de geração de matrizes MDS quadradas que realizam resistência melhorada a ataques de criptoanálise diferencial e ^4 configurando-as para as funções F será explicado. O processamento de geração das matrizes MDS quadradas será explicado com referência ao fluxograma da Figura 12.

[Etapa S201]

Designação de entrada: o número de matrizes MDS necessárias por q, a ordem de extensão por n, e o tamanho da matriz por m, as q matrizes MDS quadradas de ordem m L_í; L₂,..., L_q são geradas randomicamente em GF(2ⁿ). O fluxograma mostrado na Figura 12 mostra um exemplo de processamento como com o número de matrizes MDS q = 6, ordem de extensão n = 8 e tamanho de matriz m = 8.

[Etapa S202]

É verificado se uma matriz composta de m colunas selecionadas arbitrariamente de qm colunas incluídas nas q matrizes MDS quadradas de ordem m L_b L₂,..., L_q é uma matriz MDS quadrada. Se o fluxo passou na verificação, o fluxo avança para a etapa S203; se não for o caso, o fluxo retoma à etapa S201. Aqui, a matriz MDS quadrada significa uma matriz satisfazendo às seguintes propriedades, conforme descrito acima, (a) É uma matriz quadrada, (b) Determinantes de todas as submatrizes incluídas em uma matriz não são zero, isto é, det (submatriz) Ψ 0.

[Etapa S203]

As q matrizes MDS quadradas de ordem m L_b L₂,..., L_q são emitidas como matrizes MDS quadradas a serem aplicadas à cifragem de bloco de chave comum do tipo Feistel de número de arredondamento 2r.

Através do processo acima, as q matrizes MDS quadradas de ordem mL_bL₂,...,L_q são geradas. Aqui, q satisfaz q < r.

No processamento de geração de matriz MDS quadrada no exemplo de processamento acima mencionado al, conforme explicado na seqüência de processamento da Figura 11, a independência linear de uma matriz composta de m colunas arbitrárias obtidas de qm colunas incluídas nas

q matrizes MDS quadradas de ordem m L_b L₂,..., L_q na Etapa S101 foi determinada. No processamento de geração de matriz MDS quadrada neste exemplo de processamento a2, é verificado se uma matriz composta de m colunas arbitrárias obtidas a partir de qm colunas incluídas nas q matrizes MDS quadradas de ordem m L_b L₂,..., L_q é uma matriz MDS quadrada. Isto é, uma verificação mais severa será executada.

Similarmente, como exemplo de processamento al explicado previamente, as q matrizes MDS quadradas de ordem m L_b L₂,...> L_q geradas pelo processamento de geração de matriz MDS quadrada que seguiu uma seqüência de processamento mostrada nesta Figura 12, são estabelecidas como matrizes a serem aplicadas a processamento de conversão linear das seções de conversão linear das funções F dos respectivos estágios na estrutura criptográfica de bloco de chave comum do tipo Feistel de número de estágio (número de arredondamento) 2r, de acordo com o processamento da [Etapa S23] e [Etapa S24] explicado previamente com referência à Figura 10. Isto é, para estágios de numeração ímpar, q matrizes MDS quadradas são repetidamente designadas por L_b L₂,..., L_q, L_b L₂,... seqüencialmente a partir da função F do estágio superior, e para estágios de numeração par, q matrizes MDS quadradas são repetidamente designadas por L_b L₂,..., L_q, L_b L₂,... seqüencialmente a partir da função F do estágio inferior.

Então, as matrizes MDS quadradas dos arredondamentos de numeração par e as matrizes MDS quadradas dos arredondamentos de numeração par são arranjadas em ordem mutuamente reversas, respectivamente, e deste modo é garantido que o processamento de criptografia e processamento de decriptografia são os mesmos, exceto para processamento para substituir uma seqüência de chaves.

Esta configuração garante o seguinte:

(a) A matriz de conversão linear de cada função F é uma matriz MDS quadrada.

(b) Vetores de m colunas arbitrários a partir das matrizes de conversão linear incluídas em pelo menos q funções F consecutivas em arredondamentos de numeração ímpar constituem uma matriz MDS quadrada.

(c) Vetores de m colunas arbitrários a partir das matrizes de conversão linear incluídas em pelo menos q funções F consecutivas em arredondamentos de numeração par constituem uma matriz MDS quadrada.

Portanto, na estrutura criptográfica de bloco de chave comum do tipo Feistel com número de arredondamento de diversos estágios, é garantido que o cancelamento de diferença simultâneo pela contribuição de m ou menos caixas S ativas não ocorre nos arredondamentos 2q-l consecutivos. Adicionalmente, é garantido o seguinte.

(d) O número de elementos não zero nos valores de diferença obtidos pela contribuição de “a” (a < m) caixas S ativas toma-se m+l-a ou mais, a partir da propriedade da matriz MDS quadrada. Portanto, o valor mínimo do número de caixas S ativas na totalidade da função criptográfica aumenta.

Então, por este exemplo de processamento, toma-se possível aumentar o número mínimo de caixas S ativas na totalidade da função criptográfica que é um dos índices de robustez contra ataques de criptoanálise diferencial na cifragem de bloco de chave comum, e como resultado o número de caixas S ativas no caso em que análise diferencial (ataque de criptoanálise diferencial) é tentada, aumentará, e a dificuldade de análise será reforçada. Portanto, processamento criptográfico de alta segurança cuja chave é difícil de analisar é realizado.

(Exemplo de processamento a3)

O terceiro exemplo de geração de matrizes MDS quadradas que realizam resistência melhorada a ataques de criptoanálise diferencial e configurando-as para as funções F será explicado. O processamento de geração das matrizes MDS quadradas será explicado com referência ao

fluxograma da Figura 13.

[Etapa S301]

Designação de entrada: o número de matrizes MDS necessárias por q, a ordem de extensão por n, e o tamanho da matriz por m, uma qm-ésima matriz MDS quadrada é gerada em GF(2ⁿ). O fluxograma mostrado na Figura 1 mostra um exemplo de processamento como com o número de matrizes MDS q = 6, ordem de extensão n = 8 e tamanho de matriz m=8.

[Etapa S302] m linhas são selecionadas e extraídas arbitrariamente de uma matriz MDS quadrada de qm-ésima ordem M e uma matriz M’ de m linhas e qm colunas é composta.

[Etapa S303]

Os qm vetores coluna incluídos na matriz M’ de m linhas e qm colunas é arbitrariamente dividido em q grupos, cada um consistindo de m vetores coluna, sem a presença de qualquer vetor coluna em dois ou mais grupos. Matrizes quadrada de ordem m L_b L_q são emitidas a partir dos vetores colunas incluídos nos respectivos grupos, como matrizes MDS quadradas a serem aplicadas à cifragem de bloco de chave comum do tipo Feistel de número de arredondamento 2r.

Através do processo acima, as q matrizes MDS quadradas de ordem m L_b L₂,..., L_q são geradas. Aqui, q satisfaz q < r.

A técnica de geração de matriz MDS quadrada 3 no exemplo de processamento a3 será explicada mais concretamente com referência à Figura 14.

[Etapa S301 ]

Uma matriz MDS quadrada de ordem qm M é gerada em GF(2ⁿ). Conforme mostrado na Figura 14, uma matriz MDS quadrada M de qm x qm é gerada. Notar que a ordem da matriz M gerada nesta Etapa S301 pode ser maior que qm (ordem).

[Etapa S302]

Conforme mostrado na Figura 14, m colunas selecionadas e extraídas arbitrariamente da matriz MDS quadrada de ordem qm e uma matriz M’ de m linhas e qm colunas é composta. Notar que, embora o exemplo na figura seja mostrado como um exemplo no qual m linhas consecutivas são selecionadas e extraídas, uma matriz M’ de m linhas e qm colunas pode ser composta selecionando e extraindo m linhas arbitrárias possuindo um afastamento entre elas que constituirá a matriz MDS quadrada de ordem m, M.

[Etapa S303] qm vetores coluna incluídos na matriz M’ de m linhas e qm colunas são divididos em x grupos possuindo cada um m vetores coluna, sem a presença de qualquer vetor coluna em dois ou mais grupos, e matrizes quadradas de ordem m L_b L₂,..., L_x são geradas a partir do vetores coluna incluídos nos respectivos grupos.

Como os exemplos de processamento al e a2 explicados previamente, as q matrizes MDS quadradas de ordem m Lj, L₂,..., L_q geradas pelo processamento de geração de matriz MDS quadrada que seguiu uma seqüência de processamento explicada com referência às Figuras 13 e 14 são estabelecidas como matrizes a serem aplicadas a processamento de conversão linear das seções de conversão linear das funções F dos respectivos estágios na estrutura criptográfica de bloco de chave comum do tipo Feistel de número de estágio (número de arredondamento) 2r, de acordo com o processamento da [Etapa S23] e [Etapa S24] explicado previamente com referência à Figura 10. Isto é, para estágios de numeração ímpar, q matrizes MDS quadradas são repetidamente designadas por L_b L₂,..., L_q, L_b L₂,... seqüencialmente a partir da função F do estágio superior e para estágios de numeração par, q matrizes MDS quadradas são repetidamente designadas por L_t, L₂,..., L_q, L_b L₂,...

seqüencialmente a partir da função F do estágio inferior.

Então, as matrizes MDS quadradas de arredondamentos de numeração par e as matrizes MDS quadradas de arredondamentos de numeração ímpar são arranjadas em ordens mutuamente reversas, respectivamente por meio das quais é garantido que o processamento de criptografia e o processamento de decriptografia são os mesmos, exceto para processamento de substituição de uma sequência de chaves.

Esta configuração garante o seguinte, (a) A matriz de conversão linear de cada função F é uma matriz MDS quadrada, (b) Vetores de m colunas arbitrários da matriz de conversão linear incluída em pelo menos q funções F consecutivas de arredondamentos de numeração ímpar na função criptográfica são linearmente independentes, (c) Vetores de m colunas arbitrários da matriz de conversão linear incluída em pelo menos q funções F consecutivas nos arredondamentos de numeração par nesta, são linearmente independentes. Uma vez que estes aspectos (a) a (c) são garantidos, é garantido que o cancelamento de diferença simultâneo pela contribuição de m ou menos caixas S ativas não ocorre nos 2q-l arredondamentos na estrutura criptográfica de bloco de chave comum do tipo Feistel com número de arredondamento de diversos estágios. Adicionalmente, o seguinte é garantido, (d) A partir da propriedade da matriz MDS quadrada, o número de elementos não zero nos valores de diferença obtidos pela contribuição de Ai” (a < m) caixas S ativas torna-se m+l-a ou mais. Portanto, o valor mínimo do número de caixas S ativas na totalidade da função criptográfica aumenta.

Um caso em que o exemplo de processamento a3 produz especialmente um efeito, é um caso em que m e r tomam-se grandes, um custo de tempo requerido em um sistema de processamento de determinação de matriz dos exemplos al e a2 de processamento acima mencionados, tomase enorme, e deste modo é difícil determinar uma matriz dentro de um tempo realista. Mesmo em tal caso, se for usada a técnica de geração de matriz MDS quadrada deste exemplo de processamento a3, tomar-se-á possível o processamento de geração de matriz em um tempo comparativamente curto.

Isto é porque se toma possível no exemplo de processamento a3 aplicar um sistema capaz de processar grandes m e r suficientemente em um tempo realista, por exemplo, um método de geração para gerar uma matriz com a chave Reed-Solomon.

Também neste exemplo de processamento a3, conforme descrito acima, toma-se possível aumentar o número mínimo de caixas S ativas na totalidade da função criptográfica que é um dos índices de robustez contra ataques de criptoanálise diferencial na cifragem de bloco de chave comum. Como resultado, quando a análise diferencial (ataque de criptoanálise diferencial) é tentada, o número de caixas S ativas aumenta, o que reforçará a dificuldade na análise. Portanto, processamento criptográfico de alta segurança cuja chave é difícil de analisar é realizado.

[(3-b) Exemplo de geração de matrizes MDS quadradas que realizam resistência melhorada a ataques de criptoanálise linear e ajustando-as para as funções F]

A seguir, dois exemplos de processamento bl, b2 serão explicados como exemplos de geração de matrizes MDS quadradas que realizam resistência melhorada a ataques de criptoanálise linear e ajustando-as para as funções F.

[Exemplo de processamento bl]

Um primeiro exemplo de geração das matrizes MDS quadradas que realiza resistência melhorada a ataques de criptoanálise linear e ajustando-as às funções F será explicado. O processamento de geração das matrizes MDS quadradas será explicado com referência ao fluxograma mostrado na Figura 15.

[Etapa S401]

Designação de entrada: o número de matrizes MDS quadradas

..... · .·. .·· ··: .·· :·· • * í ί ; ϊ· * * ·· · :·* ··♦ ·· : : s :/ ·/* ·„· ·.· ·.· • ··· * · necessárias por q, a ordem de extensão por n, e o tamanho de matriz por m, as q matrizes MDS quadradas de ordem m M_b M₂,..., M_q são geradas randomicamente em GF(2ⁿ). O fluxograma mostrado na Figura 14 mostra um exemplo de processamento como com o número de matrizes MDS q - 6, ordem de extensão n - 8 e tamanho de matriz m = 8.

[Etapa S402]

É verificado se vetores linha m arbitrários obtidos de 2m vetores linha incluídos em duas matrizes inversas adjacentes após calcular as matrizes inversas Mf^l, Μ2\..., Mq'¹ de q matrizes MDS quadradas de ordem m Mb M₂,..., M_q são linearmente independentes. t^Rna Figura 15 denota um vetor transposto de um vetor linha. Se o fluxo passou na verificação, o fluxo avança para a etapa S403; se não for o caso, o fluxo retoma à etapa S401. Aqui, as matrizes ΜΓ¹, Mq’¹ serão consideradas como matrizes adjacentes.

[Etapa S403]

As q matrizes MDS quadradas de ordem m L_b L₂,..., L_q são emitidas como matrizes MDS quadradas a serem aplicadas à cifragem de bloco de chave comum do tipo Feistel de número de arredondamento 2r.

Através do processo acima, as q matrizes MDS quadradas de ordem m L_b L₂,..., L_q são geradas. Aqui, q satisfaz q < r.

As q matrizes MDS quadradas de ordem m geradas deste modo L_b L₂,..., L_q são estabelecidas como matrizes a serem aplicadas a processamento de conversão linear das seções de conversão linear das funções F dos respectivos estágios na estrutura criptográfica de bloco de chave comum do tipo Feistel de número de estágio (número de arredondamento) 2r, de acordo com o processamento da [Etapa S23] e [Etapa S24] explicado previamente com referência à Figura 10. Isto é, para estágios de numeração ímpar, q matrizes MDS quadradas são repetidamente designadas por L_b L₂,..., L_q, L_b L₂,... seqüencialmente a partir da função F do estágio superior e para estágios de numeração par, q matrizes MDS quadradas são repetidamente ·· ··,·

designadas por L_b L2,..., L_q> L_b L_2j... seqüencialmente a partir da função F do estágio inferior.

As matrizes MDS quadradas de arredondamentos de numeração par e as matrizes MDS quadradas de arredondamentos de numeração ímpar são arranjadas em ordens mutuamente reversas, respectivamente por meio das quais é garantido que o processamento de criptografia e o processamento de decriptografia são os mesmos, exceto para substituição de uma seqüência de chaves.

Esta configuração garante o seguinte, (a) A matriz de conversão linear de cada função F é uma matriz MDS quadrada, (b) Vetores de m colunas em uma matriz inversa incluída consecutivamente nos arredondamentos de numeração ímpar em uma função criptográfica e em uma matriz inversa incluída consecutivamente em arredondamentos de numeração par nestas são linearmente independentes. Estas propriedades habilitam a dificuldade na análise por aproximação linear em ataques de criptoanálise linear a ser aumentada, e processamento criptográfico de alta segurança com dificuldade aumentada na análise, isto é, cuja chave é difícil de analisar, é realizado.

(Exemplo de processamento b2)

Um segundo exemplo de geração das matrizes MDS quadradas que realiza resistência melhorada a ataques de criptoanálise linear e ajustando-as às funções F será explicado. A explicação será dada para processamento de geração da matriz MDS quadrada referindo-se ao fluxograma mostrado na Figura 16.

[Etapa S501]

Designação de entrada: 0 número de matrizes MDS quadradas necessárias por q, uma ordem de aumento por n, e um tamanho de matriz por m, as q matrizes MDS quadradas de ordem m M_b M_q são geradas randomicamente em GF(2ⁿ). O fluxograma mostrado na Figura 16 mostra um

exemplo de processamento como com o número de matrizes MDS quadradas q = 6, ordem de extensão n = 8 e tamanho de matriz m = 8.

[Etapa S502]

É verificado se vetores linha m arbitrários obtidos de 2m vetores linha incluídos em duas matrizes inversas adjacentes após calcular as matrizes inversas Mf¹, M/¹,..., M^¹ de q matrizes MDS quadradas de ordem m M], M₂,..., M_q constituem uma matriz MDS quadrada. ^tR na Figura 16 denota um vetor transposto de um vetor linha. Se o fluxo passou na verificação, o fluxo avança para a etapa S503; se não for o caso, o fluxo retoma à etapa S401. Aqui, as matrizes ΜΓ¹, Mq’¹ serão consideradas como matrizes adjacentes. A matriz MDS quadrada é uma matriz satisfazendo às seguintes propriedades, (a) É uma matriz quadrada, (b) Determinantes de todas as submatrizes incluídas na matriz não são zero, a saber det(submatriz) *0.

[Etapa S503]

As q matrizes MDS quadradas de ordem m L_b L₂,..., L_q são emitidas como matrizes MDS quadradas a serem aplicadas à cifragem de bloco de chave comum do tipo Feistel de número de arredondamento 2r.

Através do processo acima, as q matrizes MDS quadradas de ordem m L_b L₂,..., L_q são geradas. Aqui, q satisfaz q < r.

No processamento de geração de matriz MDS quadrada no exemplo de processamento acima mencionado bl, conforme explicado na sequência de processamento da Figura 15, o que é determinado é a independência linear ao considerar m vetores coluna arbitrários a partir de qm vetores coluna incluídos nas matrizes inversas Mf¹, M2'Mq'¹ de q matrizes MDS quadradas de ordem m Mb M₂,..., M_q na Etapa S402. No processamento de geração de matriz MDS quadrada neste exemplo de processamento b2, é verificado se m vetores coluna arbitrários obtidos a partir de m vetores coluna incluídos nas matrizes inversas Mf¹, M2'¹,..., Mq^_1 das q ·· ···

matrizes MDS quadradas de ordem m M_b M₂,..., M_q constituem uma matriz MDS quadrada. Isto é, verificação mais severa será executada.

Similarmente ao exemplo de processamento bl descrito previamente, as q matrizes MDS quadradas de ordem m L_b L₂,..., L_q geradas pelo processamento de geração de matriz MDS quadrada que é conforme a uma seqüência de processamento mostrada nesta Figura 16, são estabelecidas como matrizes a serem aplicadas a processamento de conversão linear das seções de conversão linear das funções F dos respectivos estágios na estrutura criptográfica de bloco de chave comum do tipo Feistel de número de estágio (número de arredondamento) 2r, de acordo com o processamento da [Etapa S23] e [Etapa S24] explicado previamente com referência à Figura 10. Isto é, para estágios de numeração ímpar, q matrizes MDS quadradas são designadas por L_b L₂,..., L_q, L_b L₂,... seqüencialmente e repetidamente a partir da função F do estágio superior, e para estágios de numeração par, q matrizes MDS quadradas são designadas por L_b L₂,..., L_q, L_b L₂,.·· seqüencialmente e repetidamente a partir da função F do estágio inferior.

Então, as matrizes MDS quadradas de arredondamentos de numeração par e as matrizes MDS quadradas de arredondamentos de numeração ímpar são arranjadas em ordens mutuamente reversas, respectivamente por meio das quais é garantido que o processamento de criptografia e o processamento de decriptografia são os mesmos, exceto para processamento de substituição de uma seqüência de chaves.

Esta configuração garante o seguinte, (a) A matriz de conversão linear de cada função F é uma matriz MDS quadrada, (b) Vetores de m colunas arbitrários a partir de matrizes inversas da matriz de conversão linear incluídas consecutivamente em arredondamentos de numeração ímpar nestas constituem uma matriz MDS quadrada. Estas propriedades habilitam a dificuldade na análise por aproximação linear em ataques de criptoanálise linear a ser aumentada, e processamento criptográfico de alta segurança com ^6

dificuldade aumentada na análise, isto é, cuja chave é difícil de analisar, é realizado.

[(3-c) Exemplo de geração de matrizes MDS quadradas que realizam resistência melhorada a ataques de criptoanálise diferencial e ataques de criptoanálise linear e ajustando-as para as funções F]

A seguir, um exemplo de geração de matrizes MDS quadradas que realizam resistência melhorada a ataques de criptoanálise diferencial e ataques de criptoanálise linear e ajustando-as para as funções F será explicado.

O algoritmo criptográfico com a resistência a ataques de criptoanálise diferencial aplicando o processamento explicado previamente com referência às Figuras 10 a 13, isto é, estabelecendo matrizes MDS quadradas a serem aplicadas a conversão linear nas seções de processamento linear das funções F, aplicando qualquer um dos exemplos de processamento acima mencionados al (Figura 1 l)a a3 (Figura 13). Ainda mais, o algoritmo criptográfico com a resistência a ataques de criptoanálise linear é realizada aplicando o processamento explicado com referência à Figura 10 e Figuras 14 e 15 previamente, isto é, estabelecendo matrizes MDS quadradas a serem aplicadas a conversão linear nas seções de processamento linear das funções F, aplicando qualquer dos exemplos de processamento acima mencionados bl (Figura 14) e b2 (Figura 15).

O algoritmo usando matrizes MDS quadradas que realizam resistência melhorada a ataques de criptoanálise diferencial e ataques de criptoanálise linear é implementado estabelecendo matrizes MDS quadradas geradas executando um dos processamentos dos exemplos de processamento al (Figura 11) a a3 (Figura 12) e um dos processamentos dos exemplos de processamento bl (Figura 14) e b2 (Figura 15) como matrizes a serem aplicadas ao processamento de conversão linear das seções de conversão linear das funções F dos respectivos estágios na estrutura criptográfica de ♦

.·.· ·/·^:·· ·.’ ·· ··* %

bloco de chave comum do tipo Feistel de número de estágio (número de arredondamento) 2r.

Isto é, q matrizes MDS quadradas são geradas por qualquer das seguintes combinações: um exemplo de processamento al é um exemplo de processamento bl; um exemplo de processamento al e um exemplo de e b2; bl; b2; bl;

um um um um exemplo exemplo exemplo exemplo de de de de processamento processamento processamento processamento a2 a2 a3 a3 um um um um exemplo exemplo exemplo exemplo de de de de processamento processamento processamento processamento processamento b2; e são estabelecidas como matrizes a serem aplicadas a processamento de conversão linear das seções de conversão linear das funções F dos respectivos estágios na estrutura criptográfica de bloco de chave comum do tipo Feistel de número de estágio (número de arredondamento) 2r. Isto é, para estágios de numeração ímpar, q matrizes MDS quadradas são designadas por L_b L₂,..., L_q, L_b L₂,... seqüencialmente e repetidamente a partir da função F do estágio superior, e para estágios de numeração par, q matrizes MDS quadradas são designadas por L_b L_q, L_b L₂,...

seqüencialmente e repetidamente a partir da função F do estágio inferior. Isto é, para estágios de numeração ímpar, q matrizes MDS quadradas são designadas por L_b L₂,..., L_q, L_b L_2v.. seqüencialmente e repetidamente a partir da função F do estágio superior, e para estágios de numeração par, q matrizes MDS quadradas são designadas por L_b L₂,..., L_q, L_b L₂,... seqüencialmente e repetidamente a partir da função F do estágio inferior. Por este ajuste, processamento criptográfico que realiza resistência melhorada a ataques de criptoanálise diferencial e ataques de criptoanálise linear toma-se possível.

quadradas resistência

Um exemplo de processamento de geração de matrizes MDS para implementar processamento criptográfico que realiza melhorada a ataques de criptoanálise diferencial e ataques de • * · criptoanálise linear, será explicado com referência à Figura 17. Este processamento é uma combinação do exemplo de processamento a2 e exemplo de processamento b2 descrito acima.

[Etapa S601]

Designação de entrada: o número de matrizes MDS quadradas necessárias por q, a ordem de extensão por n, e om tamanho de matriz por m, as q matrizes quadradas de ordem m são geradas randomicamente em GF(2ⁿ). O fluxograma mostrado na Figura 17 mostra um exemplo de processamento como com o número de matrizes MDS quadradas q = 6, ordem de extensão n = 8 e tamanho de matriz m = 8.

[Etapa S602]

Quando m colunas são retiradas de qm colunas incluídas nas q matrizes MDS quadradas de ordem m, M_b M₂,..., M_q é verificado se estas constituem uma matriz MDS quadrada. Se o fluxo passou na verificação, o fluxo avança para a etapa S6O3; se não for o caso, o fluxo retoma à etapa S601. Aqui, a matriz MDS quadrada significa uma matriz satisfazendo as seguintes propriedades, (a) É uma matriz quadrada, (b) Um determinante de qualquer submatriz incluída na matriz não são zero, a saber det(submatriz) ψ 0.

[Etapa S603]

Matrizes inversas Mf¹, Mf¹,..., Mq'¹ de q matrizes MDS quadradas de ordem m M_b M₂,..., M_q são calculadas, e é verificado se m vetores linha arbitrários são obtidos a partir de 2m vetores linha incluídos em duas matrizes inversas adjacentes, constitui uma matriz MDS quadrada. ^lR na Figura 17 denota um vetor transposto de um vetor linha. Se o fluxo passou na verificação, o fluxo avança para a etapa S604; se não for o caso, o fluxo retoma à etapa S601. Aqui, as matrizes ΜΓ¹, Mq'¹ serão consideradas como matrizes adjacentes.

[Etapa S604]

As q matrizes MDS quadradas de ordem m L_b L₂,..., L_q são emitidas como matrizes MDS quadradas a serem aplicadas à cifragem de bloco de chave comum do tipo Feistel de número de arredondamento 2r.

Através do processo acima, as q matrizes MDS quadradas de ordem m L_b L₂,..., L_q são geradas. Aqui, q satisfaz q < r.

As q matrizes MDS quadradas de ordem m L_b L_q geradas pelo processamento de geração de matriz MDS quadrada que seguiu uma seqüência de processamento mostrada nesta Figura 17, são estabelecidas como matrizes a serem aplicadas a processamento de conversão linear das seções de conversão linear das funções F dos respectivos estágios na estrutura criptográfica de bloco de chave comum do tipo Feistel de número de estágio (número de arredondamento) 2r, de acordo com o processamento da [Etapa S23] e [Etapa S24] explicado previamente com referência à Figura 10. Isto é, para estágios de numeração ímpar, q matrizes MDS quadradas são repetidamente designadas por L_b L₂,...> L_q, L_b L₂,... seqüencialmente a partir da função F do estágio superior, e para estágios de numeração par, q matrizes MDS quadradas são repetidamente designadas por L_b L₂,..., L_q, L_b L₂,... seqüencialmente a partir da função F do estágio inferior.

Então, as matrizes MDS quadradas dos arredondamentos de numeração par e as matrizes MDS quadradas dos arredondamentos de numeração ímpar são arranjadas em ordem mutuamente reversas, respectivamente, e deste modo é garantido que o processamento de criptografia e o processamento de decriptografia são os mesmos, exceto para processamento para substituir uma seqüência de chaves.

Esta configuração garante os seguintes aspectos (a) a (c). (a) A matriz de conversão linear de cada função F é uma matriz MDS quadrada, (b) Vetores de m colunas arbitrários da matriz de conversão linear incluída em pelo menos q funções F consecutivas em arredondamentos de numeração ímpar na função criptográfica constituem uma matriz MDS quadrada, (c) • · ·

Vetores de m colunas arbitrários da matriz de conversão linear incluída em pelo menos q funções F consecutivas em arredondamentos de numeração par constituem uma matriz MDS quadrada. Uma vez que estes aspectos (a) a (c) são garantidos, na estrutura criptográfica de bloco de chave comum do tipo Feistel de número de arredondamento de diversas etapas, é garantido que o cancelamento de diferença simultâneo pela contribuição de m ou menos caixas S ativas não ocorre nos 2q-l arredondamentos consecutivos. Adicionalmente, (d) a partir da propriedade da matriz MDS quadrada, é garantido que o número de elementos não zero nos valores de diferença obtidos pela contribuição de “a” (a < m) caixas S ativas toma-se m+l-a ou mais. Portanto, o valor mínimo do número de caixas S ativas na totalidade da função criptográfica aumenta. Adicionalmente, o seguinte é garantido, (e) Vetores de m colunas arbitrários a partir de matrizes inversas da matriz de conversão linear incluídas consecutivamente em arredondamentos de numeração ímpar e das matrizes de conversão linear incluídas consecutivamente nos arredondamentos de numeração par, ambos na função criptográfica, constituem uma matriz MDS quadrada. Estas propriedades habilitam a dificuldade na análise por aproximação linear em ataques de criptoanálise linear a ser aumentada, e processamento criptográfico de alta segurança com dificuldade aumentada na análise, isto é, cuja chave é difícil de analisar, é realizado.

Então, por este exemplo de processamento, a dificuldade na análise em ambos ataques de criptoanálise diferencial e ataques de criptoanálise linear é aumentada, e o processamento criptográfico de alta segurança cuja chave é difícil de analisar é realizado. O exemplo mostrado na Figura 17 foi, conforme descrito acima, um exemplo de geração das matrizes MDS quadradas pela combinação do exemplo de processamento a2 e exemplo de processamento b2 explicados previamente. Entretanto, outras gerações podem ser adotadas. Isto é, q matrizes MDS quadradas são geradas * · · · · *· ··· combinando um dos seguintes pares: o exemplo de processamento al e o exemplo de processamento bl, o exemplo de processamento al e o exemplo de processamento b2, o exemplo de processamento a2 e o exemplo de processamento bl, o exemplo de processamento a3 e o exemplo de 5 processamento bl, e o exemplo de processamento a3 e o exemplo de processamento b2. Para estágios de numeração ímpar, q matrizes MDS quadradas são repetidamente designadas por L_b L₂,..., L_q, L_b L₂>... seqüencialmente a partir da função F do estágio superior, e para estágios de numeração par, q matrizes MDS quadradas são repetidamente designadas por 10 L_b L₂,..._s L_q, L_b L₂,... seqüencialmente a partir da função F do estágio inferior, como uma matriz a ser aplicada nas seções de conversão linear das funções F dos respectivos estágios na estrutura criptográfica de bloco de chave comum do tipo Feistel de número de estágio (número de arredondamento) 2r; deste modo, processamento criptográfico de alta 15 segurança que possui dificuldade reforçada na análise em ataques de criptoanálise diferencial e ataques de criptoanálise linear e cuja chave é difícil de analisar, pode ser realizado.

Embora a explicação até este ponto suponha que a matriz de conversão linear seja uma matriz de mxm definida em GF(2ⁿ) e usada em uma 20 operação de conversão de dados de mn bits para mn bits, o efeito similar a ataques de criptoanálise diferencial e ataques de criptoanálise linear pode ser efetivamente obtido mesmo no caso em que uma matriz mn x mn definida em GF(2) é usada. Realmente, a matriz arbitrária em GF(2ⁿ) pode ser trazida em correspondência unívoca com uma matriz em GF(2) mostrando a mesma 25 conversão. Portanto, pode ser dito que a matriz em GF(2) mostra uma representação mais geral. A matriz em GF(2) possui mn colunas e mn linhas, que são n vezes aquelas no caso de GF(2ⁿ). Por esta razão, a primeira coluna da matriz em GF(2ⁿ) corresponde às colunas primeira a n-ésima da matriz em GF(2), e a primeira linha da matriz em GF(2ⁿ) corresponde à primeira a n55

ésima fila desta. Isto é, a i-ésima linha corresponde da [(i-1) + l]-ésima à [(i1) + n]-ésima filas e a i-ésima coluna corresponde da [(i-1) + l]-ésima à [(i-1) + n]-ésima colunas. Portanto, no sentido de efetuar uma operação de extrair uma coluna ou linha em GF(2ⁿ), se é usada uma matriz definida em GF(2), é 5 necessário efetuar uma operação de extrair n linhas ou n colunas que correspondem à coluna ou linha em GF(2). A operação de extrair m linhas ou colunas em GF(2) requer extrair n linhas ou colunas por m vezes em GF(2) e como resultado uma matriz mn x mn pode ser obtida. A coordenação acima habilita as matrizes a serem facilmente estendidas a matrizes definidas em

GF(2).

Finalmente, a Figura 18 mostra um exemplo de configuração de um módulo IC 600 como um aparelho de processamento criptográfico para efetuar processamento criptográfico. O processamento acima mencionado é executável em vários aparelhos de processamento de informação, por 15 exemplo, um PC, um cartão IC, um leitor/escritor, etc., e o módulo IC 600 mostrado na Figura 18 pode ser usado como um constituinte para estes vários aparelhos.

Uma CPU (Unidade de Processamento Central) 601 mostrada na Figura 18 é um processador para executar vários programas, tais como iniciar processamento criptográfico, concluí-lo, controlar a transmissão/recepção de dados, controlar a transferência de dados, entre seções de configuração e executar vários programas. A memória 602 consiste de ROM (Memória de Somente Leitura) para armazenar um programa que a CPU 601 executa, ou dados fixos como parâmetros de operação, RAM (Memória de Acesso Randômico) usada como uma área de armazenagem do programa executado no processamento da CPU 601, parâmetros sempre variando no processamento do programa, e uma área de trabalho, etc. A memória 602 pode também ser usada como áreas de armazenagem de dados de chave necessários para processamento criptográfico, etc. É preferível que

uma área de armazenagem de dados etc., seja construída como memória com uma estrutura resistente a intromissões.

Uma seção de processamento criptográfico 603 efetua criptografia, decriptografia, etc., que segue, por exemplo, o algoritmo de processamento criptográfico de bloco de chave comum do tipo Feistel descrito acima. Embora seja mostrado um exemplo no qual o meio de processamento criptográfico é feito como um módulo individual, este pode ser configurado de tal modo que, por exemplo, um programa criptográfico seja armazenado em ROM e a CPU 606 leia e execute o problema armazenado na ROM, sem prover tal módulo criptográfico independente.

Um gerador de número randômico 604 executa processamento de geração de números randômicos que são necessários na geração de uma chave que é requerido para processamento criptográfico e similar.

Uma seção de transmissão/recepção 605 é uma seção de comunicação de dados para efetuar comunicação de dados extemamente, que executa comunicação de dados, por exemplo, com um leitor-escritor, etc., e um módulo IC, emitindo um texto cifrado gerado no módulo IC ou inserindo dados no mesmo etc., a partir do leitor-escritor externo etc.

Anteriormente, esta invenção foi descrita em detalhe com referência a realizações específicas. Entretanto, é óbvio que os especialistas na técnica podem obter modificação e substituição da realização sem se desviar do escopo e espírito desta invenção. Isto é, esta invenção foi descrita na forma de ilustração, e não deveria ser interpretada restritivamente. No sentido de julgar o ponto principal desta invenção, a coluna de acordo com a reivindicação de patente deveria ser considerada.

Notar que uma série de processamento explicada na descrição pode ser implementada por hardware, por software ou por uma combinação de ambos. Ao efetuar processamento por software, um programa que grava uma seqüência de processamento pode ser executado instalando-o em uma • · · · · ·· ··· memória incorporada em hardware exclusivo em um computador, ou pode ser executado instalando-o em um computador de uso geral capaz de executar vários processamentos.

Por exemplo, um programa pode ser gravado antecipadamente em um disco rígido ou ROM (Memória de Somente Leitura) como um meio de gravação. Altemativamente, o programa pode ser armazenado temporariamente ou permanentemente em meios de gravação removíveis, tais como um disco flexível, CD-ROM (Disco Compacto de Memória de Somente Leitura), um disco MO (Magneto Óptico), um DVD (Disco Versátil Digital), um disco magnético e memória de semicondutor. Tal meio de gravação removível pode ser provido como o assim chamado pacote de software.

Em adição a instalar o programa no computador a partir de um meio de gravação removível como descrito acima, o seguinte esquema pode ser adotado. O programa é transferido sem fio para o computador, a partir de um site de transferência, ou transferido por cabo para o computador através de uma rede, tal como uma LAN (Rede de Área Local) e pela Internet, enquanto o computador recebe o programa sendo transferido de tal modo e o instala em um meio de gravação, tal como um disco rígido interno.

Notar que várias espécies de processamento escrito na descrição podem ser executados em paralelo ou individualmente, de acordo com a capacidade de processamento do aparelho efetuando o processamento ou, se necessário, sendo executado em seqüência de tempo de acordo com a descrição. Notar que nesta descrição, o sistema é tal que possui uma estrutura de combinação lógica de diversos dispositivos, mas não sendo limitado a sistemas tendo cada um seus próprios dispositivos no mesmo invólucro.

Conforme descrito acima, de acordo com a configuração desta invenção, no processamento criptográfico de bloco de chave comum do tipo Feistel, para execução da função F do tipo SPN que possua a seção de conversão não linear e a seção de conversão linear repetidamente para

diversos arredondamentos, é configurado para executar o seguinte. Enquanto executa processamento de conversão linear da função F correspondente a cada um dos diversos arredondamentos, como um processamento de conversão linear que aplica as matrizes MDS quadradas (Máxima Distância Separável), matrizes MDS quadradas L_a, L_b que são diferentes pelo menos nos arredondamentos de numeração ímpar consecutivos e nos arredondamentos de numeração par consecutivos, são aplicadas, respectivamente, e o processamento de conversão linear com matrizes MDS quadradas é efetuado, onde matrizes MDS quadradas L_a, L_b diferentes pelo menos em arredondamentos de numeração ímpar consecutivos e nos arredondamentos de numeração par consecutivos, são aplicadas, e uma matriz composta de m vetores coluna selecionados arbitrariamente de vetores coluna constituindo as matrizes inversas Lf¹, L_b ^-1 das matrizes MDS quadradas é linearmente independente ou forma uma matriz MDS quadrada. Conseqüentemente, a resistência a ataques de criptoanálise linear na cifragem de bloco de chave comum é melhorada, e a dificuldade de analisar uma chave de criptografia, etc., é aumentada, de tal modo que é realizado processamento criptográfico de alta segurança. Portanto, esta invenção pode ser aplicada a um aparelho de processamento criptográfico que é requerido para reforçar a dificuldade de análise para encontrar uma chave e possui alta segurança.

Adicionalmente, de acordo com a configuração desta invenção, no processamento criptográfico de bloco de chave comum do tipo Feistel que executa a função F do tipo SPN tendo a seção de conversão não linear e a seção de conversão linear repetidamente ao longo de diversos arredondamentos, é configurado para efetuar processamento de conversão linear da função F correspondente a cada um dos diversos arredondamentos, como processamento de conversão linear que aplica matrizes MDS quadradas (Máxima Distância Separável) e ao mesmo tempo aplica matrizes MDS quadradas que são diferentes pelo menos nos arredondamentos de numeração

Gó par consecutivos e nos arredondamentos de numeração ímpar consecutivos, onde estas matrizes MDS quadradas apresentam independência linear ou formam matrizes MDS quadradas. Portanto, é garantido que o cancelamento de diferença simultâneo pela contribuição de caixas S ativas não ocorre, e 5 toma-se possível aumentar o número mínimo de caixas S ativas na totalidade da função criptográfica, que é um dos índices de robustez contra ataques de criptoanálise diferencial na cifragem de bloco de chave comum. Por esta configuração, a resistência a ambos ataques de criptoanálise linear e ataques de criptoanálise diferencial é melhorada, e deste modo processamento 10 criptográfico de alta segurança é implementado. Portanto, esta invenção pode ser aplicada ao aparelho de processamento criptográfico que é requerido para aumentar a dificuldade de analisar uma chave e possui alta segurança.

Claims (12)

1. REIVINDICAÇÕES

   1. Aparelho de processamento criptográfico para a realização de processamento criptográfico de bloco de chave comum do tipo Feistel, aparelho este caracterizado pelo fato de possuir:

   5 uma estrutura que executa repetidamente uma função F (120) do tipo SPN tendo uma seção de conversão não linear (121) e uma seção de conversão linear (122) ao longo de diversos arredondamentos, em que cada uma da seção de conversão linear (122) de uma função F correspondente a cada um dentre diversos arredondamentos é configurada para 10 realizar processamento de conversão linear de uma entrada de n bits emitidos a partir de cada uma de m seções de conversão não linear, totalizando mn bits, como processamento de conversão linear que aplica uma matriz quadrada (402) MDS (Máxima Distância Separável), em que pelo menos nos arredondamentos de numeração ímpar consecutivos, e nos arredondamentos de numeração par 15 consecutivos, são aplicadas diferentes matrizes MDS quadradas L_a, Lb, e uma matriz composta de m vetores de colunas arbitrariamente selecionados a partir de vetores de colunas constituindo matrizes inversas La¹, Lb¹ das matrizes MDS quadradas é linearmente independente.
2. 2. Aparelho de acordo com a reivindicação 1, caracterizado pelo 20 fato de que:

   uma matriz composta de m vetores de colunas arbitrariamente selecionados a partir de vetores de colunas constituindo as matrizes inversas La¹, Lb¹ é uma matriz MDS quadrada.
3. 3. Aparelho de acordo com a reivindicação 1, caracterizado pelo 25 fato de que:

   um algoritmo do processamento criptográfico de bloco de chave comum do tipo Feistel é um algoritmo criptográfico de número de arredondamento 2r, e a mencionada seção de conversão linear (122) da função F (120)

   Petição 870180138490, de 05/10/2018, pág. 12/17 é configurada para executar conversão linear aplicando q espécies de matrizes MDS quadradas diferentes (2 < q < r) sequencialmente e de modo repetido em todos os r arredondamentos de numeração par e em todos os r arredondamentos de numeração ímpar.
4. 5 4. Aparelho de acordo com a reivindicação 1, caracterizado pelo fato de que:

   cada uma das diversas matrizes quadradas (402) MDS diferentes a ser aplicada naquela seção de conversão linear (122) da função F (120) é uma matriz MDS quadrada que é composta de m vetores de colunas arbitrariamente 10 selecionados a partir de vetores de colunas que constituem as diversas matrizes MDS quadradas e é linearmente independente.

   5. Aparelho de acordo com a reivindicação 1, caracterizado pelo fato de que:

   cada uma das diversas matrizes quadradas (402) MDS diferentes 15 a ser aplicada naquela seção de conversão linear (122) da função F (120) é uma matriz MDS quadrada de tal modo que uma matriz composta de m vetores de colunas arbitrariamente selecionados a partir de vetores de colunas constituindo diversas matrizes MDS quadradas seja também uma matriz MDS quadrada.
5. 6. Aparelho de acordo com a reivindicação 1, caracterizado pelo 20 fato de que:

   cada uma das diversas matrizes quadradas (402) MDS diferentes a ser aplicada na referida seção de conversão linear (122) da função F (120) é constituída por uma matriz composta de vetores de linhas extraídos a partir de uma matriz M’ que é composta de vetores de linhas selecionados a partir de 25 uma matriz MDS quadrada M incluindo todos os elementos que constituem as diversas matrizes MDS quadradas.
6. 7. Método de processamento criptográfico para a realização de processamento criptográfico de bloco de chave comum do tipo Feistel, método este caracterizado pelo fato de compreender as etapas de:

   Petição 870180138490, de 05/10/2018, pág. 13/17 executar uma função F (120) do tipo SPN para a realização de processamento de conversão não linear e processamento de conversão linear repetidamente ao longo de diversos arredondamentos; e no processamento de conversão de uma tal função F (120) que corresponde a cada um dos diversos arredondamentos, efetuar conversão linear para n bits emitidos a partir de m seções de conversão não linear, totalizando mn bits, como processamento de conversão linear aplicando matrizes quadradas (402) MDS (Máxima Distância Separável); em que tal processamento de conversão linear com matrizes quadradas (402) MDS é realizado de tal maneira que, pelo menos nos arredondamentos de numeração par consecutivos, e nos arredondamentos de numeração ímpar consecutivos, diferentes matrizes MDS quadradas L_a, Lb são aplicadas, e uma matriz composta de m vetores de colunas arbitrariamente selecionados a partir de vetores de colunas constituindo matrizes inversas La¹, Lb¹ das matrizes MDS quadradas é linearmente independente e constitui uma matriz MDS quadrada.
7. 8. Método de acordo com a reivindicação 7, caracterizado pelo fato de que:

   dito processamento de conversão linear por matrizes quadradas (402) MDS é realizado de tal modo que uma matriz composta de m vetores de colunas arbitrariamente selecionados a partir de vetores de colunas constituindo as matrizes inversas La¹, Lb¹ seja uma matriz MDS quadrada.
8. 9. Método de acordo com a reivindicação 7, caracterizado pelo fato de que:

   um algoritmo do processamento criptográfico de bloco de chave comum do tipo Feistel é um algoritmo criptográfico de número de arredondamento 2r, e o referido processamento de conversão linear da função F (120) executa processamento de conversão linear seqüencialmente e de modo repetido

   Petição 870180138490, de 05/10/2018, pág. 14/17 aplicando q espécies de matrizes MDS quadradas diferentes (2 < q < r).
9. 10. Método de acordo com a reivindicação 7, caracterizado pelo fato de que:

   cada uma das diversas matrizes quadradas (402) MDS diferentes a ser aplicada ao processamento de conversão linear da função F (120) é tal que uma matriz composta de m vetores de colunas arbitrariamente selecionados a partir de vetores de colunas constituindo as diversas matrizes quadradas (402) MDS seja linearmente independente e constitua uma matriz MDS quadrada.
10. 11. Método de acordo com a reivindicação 7, caracterizado pelo fato de que:

    cada uma das diversas matrizes quadradas (402) MDS diferentes a ser aplicada ao processamento de conversão linear da função F (120) é uma matriz MDS quadrada, de tal modo que uma matriz composta de m vetores de colunas arbitrariamente selecionados a partir de vetores de colunas constituindo as diversas matrizes MDS quadradas tome-se uma matriz MDS quadrada.
11. 12. Método de acordo com a reivindicação 7, caracterizado pelo fato de que:

    cada uma das diversas matrizes quadradas (402) MDS diferentes a ser aplicada ao processamento de conversão linear daquela função F (120) é constituída por uma matriz composta de vetores de colunas extraídos a partir de uma matriz M’ composta de vetores de linhas selecionados a partir de uma matriz MDS quadrada M que inclui todos os elementos que constituem as diversas matrizes quadradas (402) MDS.
12. 13. Meio de armazenamento legível por computador para realizar o método conforme definido na reivindicação 7, caracterizado por compreender instruções nele armazenadas que, quando executadas por um computador, fazem com que o dito computador realize a etapa de:

    executar uma função F (120) do tipo SPN para a realização de processamento de conversão não linear e processamento de conversão linear

    Petição 870180138490, de 05/10/2018, pág. 15/17 ao longo de diversos arredondamentos, em que dito processamento de conversão linear da função F (120), que corresponde a cada um dos diversos arredondamentos, é uma etapa de conversão linear para realizar o processamento de conversão linear para n bits emitidos a 5 partir daquelas m seções de conversão não linear, que totaliza mn bits, como processamento de conversão linear aplicando uma matriz quadrada (402) MDS (Máxima Distância Separável), e na etapa de conversão linear, processamento de conversão linear por matrizes quadradas (402) MDS é executado de tal maneira que, pelo menos 10 nos arredondamentos de numeração par consecutivos, e nos arredondamentos de numeração ímpar consecutivos, diferentes matrizes MDS quadradas (402) são aplicadas, e uma matriz composta de m vetores de colunas arbitrariamente selecionados a partir de vetores de colunas constituindo matrizes inversas L_a ^_1, 15 Lb¹ das matrizes MDS quadradas (402) é linearmente independente.