BRPI0611402A2

BRPI0611402A2 - determinação de um inverso modular

Info

Publication number: BRPI0611402A2
Application number: BRPI0611402-4A
Authority: BR
Inventors: Bernd Meyer
Original assignee: Siemens Vdo Automotive Ag
Priority date: 2005-05-25
Filing date: 2006-05-19
Publication date: 2010-09-08
Also published as: EP1891512B1; US20080201398A1; WO2006125754A1; DE102005024609A1; DE502006005410D1; ATE449373T1; EP1891512A1; RU2007148503A; JP2008542802A; CN101180606A

Abstract

DETERMINAçãO DE UM INVERSO MODULAR. A presente invenção refere-se a métodos de decodificação de dados resistente ao ataque por canal secundário, segundo o qual um valor de retorno (r) é determinado como o inverso modular de um valor de entrada (a), por meio de um módulo (M). O objetivo da invenção é conseguir uma resistência ao ataque por canal secundário com as mínimas restrições na implementação ou determinação do inverso modular com a mínima complexidade técnica. Tal objetivo é atingido, segundo o qual, em uma primeira subetapa, um primeiro produto (d) do valor de entrada (a) e um número aleatório é gerado (c), em uma segunda subetapa, o inverso modular (e) do primeiro produto (d) é determinado por meio do módulo (M), em uma terceira subetapa, um segundo produto (b) do número aleatório (c) é determinado por meio do inverso modular (e) e em uma quarta subetapa, o valor de retorno (r) é igualado ao segundo produto(b).

Description

Relatório Descritivo da Patente de Invenção para "DETERMINA-ÇÃO DE UM INVERSO MODULAR".

A presente invenção refere-se a um método para computaçãoresistente ao ataque por canal secundário de um valor de retorno como uminverso modular de um valor de entrada usando um módulo.

Ataques por canal secundário são uma classe de métodos paracriptanálise. Em contraste com os ataques prévios sobre aplicações cripto-gráficas, um atacante nesse caso não tenta romper o algoritmo matemáticoabstrato básico, mas ao invés disso, ataca uma implementação específicade um método criptográfico. Para essa finalidade, o atacante usa variáveismedidas físicas facilmente acessíveis para a implementação real, tais comotempo de execução da computação, consumo de força e radiação eletro-magnética do processador durante a computação ou o comportamento daimplementação quando os erros são induzidos. Os valores medidos físicosde uma única computação podem ser analisados diretamente, por exemplo,usando a análise de força simples [SPA] ou um atacante grava os valoresmedidos de uma pluralidade de computações (por exemplo, usando um osci-loscópio de armazenamento) e a seguir avalia os valores medidos estatisti-camente, por exemplo, usando análise de força diferencial [DPA]. Os ata-ques por canal secundário são freqüentemente muito mais eficientes do queas técnicas de criptanálise convencionais e podem até mesmo romper méto-dos que são considerados como sendo seguros do ponto de vista dos algo-ritmos se a implementação desses algoritmos não é protegida contra os ata-ques por canal secundário. Medidas defensivas para impedir os ataques porcanal secundário são particularmente importantes para cartões inteligentes eaplicações embutidas.

Os ataques por canal secundário já são tratados nas seguintespublicações: Kocher: Timing attacks on implementations of Diffie-Hellman,RSA, DSS and other systems, Crypto 1996, LNCS 1109, páginas 104-113,Springer; Kocher, Jaffe, Jun: Differential power analysis, Crypto 1999, LNCS1666, páginas 388-397, Springer; Messerger, Dabbish, Sloan: Power analy-sis attacks of modular exponentiation in smartcards, CHES 1999, LNCS1717, páginas 144-157, Springer.

Nesse contexto, Boneh, Demillo, Lipton: On the importance ofchecking cryptographic protocols for faults, Eurocrypt 1997, LNCS 1233, pá-ginas 37-51, Springer, já refere-se à utilização da informação proveniente doconsumo de força e proveniente da radiação eletromagnética do processa-dor durante a computação ou o comportamento da implementação quandoerros são induzidos.

Métodos matemáticos para a inversão são também encontradosem Menezes, van Oorschot, Vanstone: Handbook of applied cryptography,CRC-Press 1996.

Técnicas de mascarar para cripto métodos, particularmente paraDES e AES, são também conhecidas de Goubin, Patarin: DES and differen-tial power analysis, CHES 1999, LNCS 1717, páginas 158-172, Springer;Akkar, Giraud: An implementation of DES and AES, secure against someattacks, CHES 2001, LNCS 2162, páginas 309-318, Springer; Messerges:Securing the AES finalists against power analysis attacks, FSE 2000, LNCS1978, páginas 150-164, Springer; Coron, Goubin: On boolean and arithmeticmasking against differential power analysis, CHES 2000, LNCS 1965, páginas213-237, Springer; Trichina, de Seta, Germani: Simplified adaptive multiplicativemasking for AES and its securized implementation, CHES 2002, LNCS 2523,páginas 187-197, Springer; Golic, Tymen: Multiplicative masking and poweranalysis of AES, CHES 2002, LNCS 2523, páginas 198-212, Springer.

A geração das assinaturas digitais com base no padrão de assi-natura digital é também um assunto de discussão em FIPS 186: Digital sig-nature standard, Federal Information Processing Standards Publication 186,NIST 1997.

É um objetivo da invenção proteger a inversão modular de SPAe DPA, in particular. Muitos métodos criptográficos (particularmente métodode chave pública) usam aritmética em corpos finitos. Uma etapa de compu-tação importante usada nesse contexto é a computação das inversões mo·dulares nos corpos finitos.

Métodos para a inversão modular geralmente envolvem algorit-mos para calcular os maiores divisores comuns (algoritmo Euclidiano esten-dido ou suas variações, tal como o algoritmo de Stein da operação binária)ou usam o pequeno teorema de Fermat e, portanto, atribuem a inversão àexponenciação modular. Os algoritmos com base no cálculo de um maiordivisor comum têm uma seqüência de operação altamente dependente dosdados: o número de operações de divisão pode ser usado para deduzir onúmero a ser invertido, por exemplo. No caso do algoritmo de Stein da ope-ração binária, um é adicionado em um valor provisório para o cálculo do mó-dulo do corpo se esse valor provisório é desigual. Se um atacante pode ob-servar se essa adição é executada na \- etapa do algoritmo, ele pode desco-brir o número a ser invertido bit por bit. Esses algoritmos, portanto, permitemque um atacante deduza facilmente o número que é para ser invertido a par-tir do tempo de execução, consumo de força ou radiação eletromagnética.Embora algoritmos baseados no pequeno teorema de Fermat tenham umaseqüência de operação constante, eles são muito mais lentos e, portanto,mais ineficientes.

As técnicas geralmente usadas para impedir os ataques por ca-nal secundário tentam piorar a razão de sinal para ruído entre a informaçãoa ser protegida e todos os outros sinais mensuráveis e, portanto, tornar aobservação da informação secreta mais difícil ou usar técnicas de randomi-zação a fim de remover a correlação entre a informação a ser protegida e osvalores medidos. Métodos para tornar a observação da informação secretamais difícil incluem, por meio de exemplo, evitar as ramificações dependen-tes de dados que são dependentes da informação que merece proteção, ouso de etapas de programa com um perfil corrente que tem pouca flutuaçãoou o uso de partes de programa cujo tempo de execução não é mais depen-dente dos dados de computação, execução de partes de programa aleató-rias e/ou redundantes, etc. Essas medidas defensivas geralmente protegemcontra ataques de SPA, mas têm a desvantagem que a implementação ésubmetida a restrições desvantajosas.

As técnicas de randomização para remover a correlação entre ainformação que é para ser protegida e os valores medidos são usadas paraproteger contra os métodos de análise estatística de DPA. Tais medidas ge-ralmente envolvem mascarar a informação secreta com valores aleatórios.

Para cada novo cálculo, novos números aleatórios independentes são entãoescolhidos para as máscaras. Um atacante então mede um cálculo que elevê como aleatório toda vez, porque ele não sabe a máscara e não pode es-tabelecer quaisquer correlações simples entre os valores físicos medidos eos dados de entrada ou saída.

Contra o antecedente dos problemas e as desvantagens da téc-nica anterior, a invenção é baseada no objetivo de prover um método para ocálculo do inverso modular que seja resistente aos ataques por canal secun-dário e ao mesmo tempo reprima as restrições para a implementação e acomplexidade adicional com a finalidade de proteger contra ataques por ca-nal secundário.

Para essa finalidade, a invenção propõe um método de acordocom a reivindicação 1. Além disso, um tacógrafo de acordo com a reivindica-ção 3 e um cartão de dados de acordo com a reivindicação 4 são propostosque são respectivamente em uma forma tal que eles operam usando o mé-todo da reivindicação 1. As subreivindicações respectivas com referência devolta contêm desenvolvimentos vantajosos.

A técnica inventiva permite quaisquer implementações de méto-dos para o cálculo de inversões modulares (incluindo os algoritmos muitoeficientes com base no cálculo de um maior divisor comum) a serem prote-gidas contra SPA e DPA por uma transformação simples.

O uso de uma técnica de mascarar homomórfica aritmética combase na invenção tem, entre outras, a vantagem que a ação de mascararpode ser executada no começo da computação e o resultado poderia serdesmascarado no fim e, ao mesmo tempo, a implementação para a inversãomodular é protegida contra ataques de SPA e DPA.

Uma aplicação vantajosa da invenção para um método de crip-tografia ou decriptografia, particularmente em um tacógrafo inventivo ou ummeio de armazenamento de dados móvel inventivo é a inversão necessáriaquando gerando as assinaturas digitais com base no padrão de assinaturadigital DSA, por exemplo:

Deixe ρ ser um número primário, q | p-1 ser um número primário,0 < g < ρ ser um gerador para o subgrupo cíclico da ordem q em (Z/pZ)*, 0 <a < q ser uma chave secreta, A = gAa mod ρ ser a chave pública associada e0 <= m < ρ ser a mensagem a ser assinada. Para calcular a assinatura (r, s)para a mensagem m e a chave pública A, as seguintes etapas de computa-ção são executadas pela unidade de computação em linha com a DSA:

1) seleção de um número aleatório 0 < k < q que precisa sermantido secreto

2) cálculo de r = (aAk mod p) mod q

3) cálculo da inversão modular h = 1/k mod q usando um módulo M

4) cálculo de s = h*(m+a*r) mod q

O cálculo da inversão modular na etapa 3) pode ser particular-mente protegido de maneira vantajosa contra SPA de acordo com a inven-ção, de modo que o número aleatório secreto k, que é conhecido como achave efêmera, não se torna conhecido para o atacante. Se um atacantedescobre a chave efêmera k, ele poderia calcular a chave secreta a da pes-soa criando essa assinatura.

O módulo inventivo M, que tem uma implementação para calcu-lar os inversos modulares em um corpo finito K, pode determinar o inversomodular no modo resistente ao canal secundário a partir de um elemento apertencente ao corpo finito K1 por exemplo. Nesse contexto, o método inven-tivo funciona usando as seguintes etapas, por exemplo:

1) a unidade de computação seleciona um elemento aleatório c de K

2) a unidade de computação determina d = a*c

3) o módulo M determina o inverso e = M(d)

4) a unidade de computação determina b = e*c

5) a unidade de computação estabelece o valor de retorno r :=b

Na etapa 3), um atacante observa apenas a inversão de um e-lemento de corpo aleatório d que é escolhido com uma distribuição uniformee que é independente da entrada real a para o cálculo. Desde que ele nãoconhece o elemento aleatoriamente selecionado c, nem os ataques de SPAnem de DAP o mune com qualquer informação das etapas de computaçãoexecutadas por M.

Uma outra vantagem do método é que uma implementação des-protegida precisa ser estendida, em linha com a invenção, somente pelasetapas 1), 2), 4) e 5) a fim de obter resistência contra SPA e DPA. Em parti-cular, os métodos eficientes para calcular os inversos modulares podem serusados na base do algoritmo Euclidiano sem mudanças. Nesse caso, acomplexidade de computação adicional é muito menor do que no caso demétodos para inversão que envolvem o pequeno teorema de Fermat.

Um desenvolvimento conveniente do método inventivo propor-ciona os resultados provisórios c, d e e a serem apagados depois das res-pectivas etapas de computação.

O texto abaixo explica a invenção em mais detalhes usando umamodalidade exemplar específica com relação aos desenhos, a invenção nãosendo limitada às ilustrações nesse exemplo. Nos desenhos:

a figura 1 mostra uma ilustração em perspectiva esquemática deum tacógrafo inventivo com um cartão de dados inventivo,

a figura 2 mostra uma ilustração esquemática da seqüência deoperação com base no método inventivo.

A figura 1 mostra um tacógrafo inventivo DTCO e um cartão dedados inventivo DC. O cartão de dados DC pode ser inserido no DTCO atra-vés de uma das duas fendas de recepção 2, de modo que durante a trans-missão dos dados entre os dois elementos, o cartão de dados DC é mantidono tacógrafo DTCO de modo que ele fica inacessível do exterior. Na sua par-te frontal 3, próximo das duas fendas de recepção 2, o tacógrafo DTCO temuma unidade de exibição 1 e elementos de controle do operador 4. Seguinteà inserção em uma fenda de recepção 2, o cartão de dados DC é conectadoem um processador central CPU por meio de linhas de dados 5, o dito pro-cessador central tendo acesso a uma memória interna MEM. O cartão dedados, da mesma forma, tem uma memória interna (não mostrada em deta-lhes) e um processador central.

A transmissão de dados entre o tacógrafo DTCO e o cartão dedados DC é executada com criptografia por meio de uma chave de sessão,com os processadores centrais CPU no tacógrafo DTCO e no cartão de da-dos DC determinando um inverso modular de um valor de entrada A, entreoutras coisas, durante a criptografia e a decriptografia. Para esta finalidade,os processadores CPU fazem uso do módulo KRY mostrado na figura 2.

O módulo KRY é parte de uma seqüência para a criptografia. Ovalor de entrada a é transferido para o módulo KRY e é enviado para o mó-dulo Mod Inv dentro deste módulo. O módulo Mod Inv1 em primeiro lugar,determina um número aleatório C e multiplica esse número pelo valor deentrada a para obter um produto d. O módulo M é usado para determinar oinverso modular e do produto d e a seguir para multiplicá-lo pelo número a-leatório c. Um valor de retorno r é igualado com esse produto e é retornadopara o módulo KRY como o resultado.

Claims

1. Método para criptografia e/ou decriptografia de dados resis-tente ao ataque por canal secundário usando uma unidade de computação,onde a etapa de criptografia e/ou decriptografia envolve determinar um valorde retorno (r) como o inverso modular de um valor de entrada (a) usando ummódulo (M)1 caracterizado em que- uma primeira subetapa envolve produzir um primeiro produto(d) a partir do valor de entrada (a) e um número aleatório (c),- uma segunda subetapa envolve o módulo (M) determinar o in-verso modular (e) do primeiro produto (d),- uma terceira subetapa envolve determinar um segundo produto(b) a partir do número aleatório (c) e do inverso modular (e),- uma quarta subetapa envolve igualar o valor de retorno (r) como segundo produto (b).

2. Método de acordo com a reivindicação 1 ou 2, caracterizado emque o número aleatório (c), o primeiro produto (d), o segundo produto (b) e o in-verso modular (e) são apagados seguinte a determinação do valor de retorno (r).

3. Tacógrafo tendo uma unidade de computação, onde a unida-de de computação criptografa e/ou decriptografa os dados e fica em umaforma tal que a etapa de criptografia e/ou decriptografia envolve determinarum valor de retorno (r) como o inverso modular de um valor de entrada (a)usando um módulo (M) da unidade de computação, caracterizado em que aunidade de computação- usa uma primeira subetapa para produzir um primeiro produto(d) a partir do valor de entrada (a) e de um número aleatório (c),- usa uma segunda subetapa para o módulo (M) determinar oinverso modular (e) do primeiro produto (d),- usa uma terceira subetapa para a unidade de computação de-terminar um segundo produto (b) a partir do número aleatório (c) e do inver-so modular (e),- usa uma quarta subetapa para a unidade de computação igua-lar o valor de retorno (r) com o segundo produto (b).

4. Meio de armazenamento de dados móvel, particularmente ummeio de armazenamento de dados na forma de um cartão de dados, tendouma unidade de computação, onde a unidade de computação criptografae/ou decriptografa os dados e é em uma forma tal que a etapa de criptogra-fia e/ou decriptografia é usada para determinar um valor de retorno (r) comoo inverso modular de um valor de entrada (a) usando um módulo (M) da uni-dade de computação, caracterizado em que a unidade de computação- usa uma primeira subetapa para produzir um primeiro produto(d) a partir do valor de entrada (a) e de um número aleatório (c),- usa uma segunda subetapa para o módulo (M) determinar oinverso modular (e) do primeiro produto (d),- usa uma terceira subetapa para a unidade de computação de-terminar um segundo produto (b) a partir do número aleatório (c) e do inver-so modular (e),- usa uma quarta subetapa para a unidade de computação igua-lar o valor de retorno (r) com o segundo produto (b).