Loading
Nota de Estudos
Study Reminders
Support
Text Version

Grupos Cíclicos baseados em Curvas de Eliptic

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Fundamentos da Cryptography Dr. Ashish Choudhury Department of Computer Science International Institute of Information Technology – Bangalore Lecture – 41 Candidate Cyclic Groups for Cryptographic Propósitos Part II (Consulte Slide Time: 00:44) Olá todos, bem-vindos a esta palestra nesta palestra vamos continuar nossa discussão sobre os candidatos grupos cíclicos para fins criptográficos e nesta palestra, introduziremos especificamente os grupos cíclicos baseados em curvas elípticas. Por isso, comecemos pela discussão sobre os grupos cíclicos de curvas elípticas. Por isso, lembre-se na última palestra que tínhamos visto que se p e q são primes onde p é da forma r tempos q + 1 e se tomarmos todos os r os resíduos modulo p então o conjunto resultante que denotamos como G constitui um subgrupo de Zp * e podemos provar que este conjunto G junto com o modulo de multiplicação da operação constitui um grupo cíclico. No entanto, verifica-se que para a segurança prática temos de operar ou selecionar valores muito grandes deste prime p a saber, temos de assegurar que o p é pelo menos 2048 bit números primos que realmente acabam por garantir que o tempo resultante do remetente e do receptor também é muito lento. Assim, o que agora vamos fazer é nesta palestra veremos grupos cíclicos baseados nos pontos sobre curvas elípticas e estes são basicamente grupos cíclicos alternativos onde o problema DLog o problema da CDH e os problemas DDH são de fato difíceis. Mais especificamente se o tamanho de prime que vamos operar com é de tamanho n bits, então o mais conhecido solver DLog que conhecemos para estes grupos é da ordem 2 n / 2 e que significa seu suficiente para operar com um número primo de 256 bit para a maioria dos propósitos práticos e que nos dá instanciações altamente eficientes de DLog, CDH e DDH baseados sistemas cripto comparados com as instanciações baseadas em subgrupos de ordem prime de Zp * direito. Sendo assim, esse é mais ponto deste grupos em comparação com as instanciações baseadas nos subgrupos de ordem prime de Zp *. Outra propriedade interessante dos grupos cíclicos com base nas curvas elípticas é que ela nos fornece estruturas adicionais o que chamamos como pares que não vamos discutir neste curso. Como estes são conceito avançado mas apenas para suas informações esta estrutura adicional que chamamos de emparelamento pode ser usada para construir primitivas criptográficas altamente avançadas como assinaturas agregadas, criptografia de broadcast, criptografia funcional e etc. (Consulte O Tempo De Deslizamento: 02:59) Então antes de entrar no grupo cíclico de base elíptico exato que vamos usar para o propósito criptográfico vamos fazer uma aquecida e ver como exatamente curvas elípticas sobre os números reais se parecem. Portanto, seja R o conjunto de números reais e deixe que a e b sejam 2 números reais ou constantes publicamente conhecidos tais que esta relação toda a saber 4a3 + 27b2 não é 0.The razão para esta constante será clara em breve e imagine que temos tal e b constantes a e b considere esta equação em x e y considere esta equação em x e y, y2 = x3 + ax + b então se eu plotar os pontos sobre esta equação ou se eu trai todos aqueles x, y valor que são números reais que são números reais que são números reais satisfazendo esta equação e junto com isso se eu pegar um ponto especial que eu não fiz como O então o conjunto resultante eu chamo como E. Então por exemplo se eu for pegar a curva ou a equação y2 = x3- x e traçar todo o real x, y satisfazendo esta equação então eu obtive essa curva da mesma forma se eu pegar a curva y2 = x3-x + 1 e traçar todo o real x, y satisfazendo esta equação então eu obtenho essa curva. Portanto, o que E é basicamente uma vez que fixamos a equação tomemos todos os x, y números reais que satisfazem esta equação e juntamente com isso um ponto especial que denotamos como O e este ponto especial O é chamado como o ponto no infinito que é espécie de um ponto imaginário que se pode imaginar sentado na parte superior do eixo y e deitado em cada linha vertical. Assim, pode-se imaginar que toda linha vertical acabará se encontrando em um horizonte em um único ponto e aquele ponto em que todas as linhas verticais vão se encontrar é considerada como o ponto no infinito que seria denote por esta notação especial O. Então é assim que eu construo o conjunto E agora o conjunto de pontos E que definimos acima é chamado de curva elíptica não singular sobre o conjunto de números reais e por que ele é chamado de não-singular, é porque garantimos a condição 4a3 + 27b2 ≠ 0 que é uma condição necessária e suficiente para garantir que a curva resultante que definimos aqui a saber: y2 = x3 + ax + b tem 3 raízes distintas por se trata de uma equação do grau 3 em x. No entanto, se não garantimos esta condição a saber a 4a3 + 27b2 ≠ 0 se deixarmos que ela seja 0 então a curva correspondente ou o conjunto de pontos que obtemos é chamado de curva elíptica singular não terá 3 raízes distintas. (Consulte O Tempo De Deslizamento: 05 :55) Então, essa é a definição de curvas elípticas. Agora o que vamos fazer aqui é vamos encontrar uma maneira muito sofisticada de fazer a operação de execução: adição operação nos pontos dessa curva elíptica. Então imagine que você recebe uma curva elíptica não singular sobre os números reais e nós definimos a operação adicional sobre esses pontos de tal forma que a maneira como vamos definir a operação de adição ele satisfaz a todos os nossos axiomas de grupo a saber: ele irá satisfazer a propriedade de encerramento, propriedade associatividade, será garantido que temos um elemento de identidade e um aditivo inverso para cada ponto da curva e que garante que o conjunto E juntamente com a operação mais a que vamos definir agora constitui um grupo aditivo. Sendo assim, a operação mais a ser definida da seguinte forma, definimos o ponto no infinito para ser o elemento de identidade que é a nossa definição. Por isso, definimos que se definimos uma + operação em qualquer ponto p sobre esta curva elíptica e um ponto no infinito para dar o resultado como p. Portanto, se você pegar qualquer ponto p que poderia ser o ponto no próprio infinito e a esse ponto se você adicionar o ponto no infinito o resultado é definido para ser o ponto p em si. Portanto, essa é uma primeira propriedade da operação de adição que definimos aqui. Por outro lado, se você for dado 2 pontos P e Q deitado na curva E e dizer que as coordenadas do ponto P são (x1, y1) e as coordenadas do ponto Q são (x2, y2) e nem P nem Q é o ponto no infinito então a forma como vamos definir a operação mais a mais nestes 2 pontos P e Q é a seguinte. Assim, podemos ter 3 dos casos possíveis dependendo da relação que se mantém entre as coordenadas de P e Q. Assim, o primeiro caso é quando x1 ≠ x2 neste caso a forma como definimos o resultado de P + Q é a seguinte. Por isso, definimos L de x para ser a linha que passa pelos pontos P e Q. Então, sua linha reta que passa pelo P e Q para que você tenha a representação pictórica aqui e deixe R ser o terceiro ponto distinto que fica tanto na linha reta quanto na curva elíptica. Por isso estou denotando as coordenadas x e y do terceiro ponto a ser x3, -y3 e chamo aquele ponto de ser R. Tão pictórico é dizer que esta curva a linha reta passa por P e Q e ela se cruza a curva elíptica no terceiro ponto diz em R cujas coordenadas eu denoco como x3 e -y3. Por isso, neste exemplo particular na representação pictórica a coordenada y de R é realmente positiva mas que não precisa ser sempre o caso. Então, é por isso que eu estou apenas representando isso como -y3 porque se por exemplo se o seu Q tivesse sido aqui então em passar a linha reta ou através de P e Q ele teria se encontrado em algum lugar aqui, e y coordenada de R teria sido uma coordenada negativa. Portanto, independentemente do que exatamente é o caso. É apenas uma questão notacional o terceiro ponto distinto no qual a linha intercepta a curva elíptica é denotada como R e sua coordenada x é x3 e a coordenada y é -y3. Agora o que fazemos aqui é apenas refletirmos o ponto R ao longo do eixo x e se refletirmos o ponto R ao longo do eixo x a coordenada x vai continuar a mesma, mas a coordenada y seu signo vai ser alterada. Se fosse – y3 ele se tornará + y3 enquanto que se nós teríamos sido mais, então ele se torna menos. E o resultado da adição de P e Q é definido para ser esse ponto refletido. Sendo assim, é assim que definimos a operação mais em pontos P e Q ambas nem P e Q são ponto infinito e x1 ≠ x2. Então agora se quisermos matematicamente computar o valor exato de x3 e y3 aqui é como podemos computar: verifica-se que x3 e y3 estão relacionados com as coordenadas x1, x2, y2, y2 por esta relação 3 = 2 − 1 − 3 = 1 − 3 − 3 − 1 e aqui &ldão; é basicamente a inclinação da linha reta passando para os pontos P e Q e a inclinação da linha que passa para os pontos P e Q vem através desta fórmula 2 − 1 2 − 1 e já que estamos no caso em que x1 − x2 que significa o denominador não é 0 e, portanto, o &ldusão de &ldusão − 1 e, portanto, o &ldusão − x2 que significa que o denominador não é 0 e, portanto, o &ldusão de &ldusão − 1 − 1 − 1 − 1 − 1 − 1 − 1 &min Sendo assim, é definida a operação de operação de adição (mais) em pontos P e Q é definida para este caso para o caso em que x1 ≠ x2 agora deixe-nos levar o segundo caso em que x1 = x2 mas as coordenadas y de P e Q são exatamente opostas umas das outras certas. Portanto, neste caso o que fazemos aqui é a linha que fazemos passar por P e Q ela basicamente acaba convergindo no ponto no infinito direito. Por isso, a ideia aqui também é a mesma em que realmente passamos uma linha passar nos pontos P e Q e ver onde exatamente ela atende a curva elíptica. Mas, neste caso, uma vez que as coordenadas x de P e Q são iguais mas apenas suas coordenadas y são diferentes nas no signo a linha reta que passa por P e Q basicamente atendem ao ponto no infinito, convergem em ponto no infinito e é por isso que definimos a operação P + Q neste caso para dar ao resultado o ponto no infinito que significa podemos interpretar 2 pontos x1, y1 e x2, -y1 onde x1 e x2 são mesmos para ser o inverso aditivo de cada um. Certo enquanto que para o terceiro caso em que x1 = x2 e y1 = y2 temos 2 sub-casos se y1 = 0 então podemos interpretar y2 para ser = -y1 porque 0 e + 0 e-0 como mesmo certo? então se y1 = 0 então podemos interpretar y2 para ser =-y1 e então chegamos basicamente ao caso anterior em que x1 = x2 e y1 é-y2. Nesse caso a forma como definimos a operação mais conseguimos que a somatória de P com o mesmo ponto que é basicamente 2P dá a você o ponto no infinito. Por outro lado se y1 não é 0 que significa dizer que temos um ponto como este P e queremos adicionar P a si mesmo então a linha que passa por este ponto é definida de uma maneira diferente: a linha aqui é basicamente a tangente a esta curva E passando pelo ponto P e vemos onde exatamente a tangente toca a curva que chamamos de R e dizem que as coordenadas de R são x3 e -y3 que é o terceiro ponto, 2 dos pontos são P e o terceiro ponto deitado na curva é R e o que agora fazemos é apenas refletirmos o ponto R ao longo do eixo x e que é o resultado da adição P a si mesmo. Então o resultado P + P, que é 2P neste caso será x3, y3 e matematicamente novamente x3 e y3 são exatamente os mesmos que foi definido para o caso em que x1 não foi igual a x2 a única diferença agora é que a inclinação da linha é diferente aqui comparada com o primeiro caso. Porque no primeiro caso os pontos P e Q são pontos distintos mas aqui estão os pontos P e Q são os mesmos pontos e é por isso que a linha é a tangente e a inclinação da tangente é computada por esta fórmula 31221 + .. E como o y1 não é 0 certo estamos no caso em que y1 não é 0 o denominador 2 vezes y1 é non 0 e é por isso que a inclinação é bem definida. (Consulte Slide Time: 13:55) Então é assim que executamos a operação de adição para curvas elípticas definidas sobre o conjunto de números reais mas como disse anteriormente para primitivas de criptografia queremos operar em um conjunto que tem um tamanho finito é por isso que agora o que vamos fazer é vamos computar executar operações em curvas elípticas modulo prime número que não terá agradáveis representações geométricas como tivemos para curvas elípticas sobre os números reais mas propriedade wise podemos estender a definição da operação mais como temos feito para o caso de números reais aqui também. Então aqui é como definimos curvas elípticas modulo a prime: então deixe E seja um elíptico não singular sobre o conjunto Zp basicamente o que significa é formamos uma equação de curva elíptica aqui a saber a equação é y2 = x3 + ax + ax + b modulo p e nós tiramos todos x, y elementos ou x, y pares do conjunto Zp x Zp e pegar todos os elementos da forma x, y onde x está na faixa 0 p-1 e y também está na faixa de 0 a p-1 que satisfaz esta equação e junto com aqueles x, y pares nós tiramos o ponto imaginário especial a saber o ponto no infinito especial.Assim como foi o caso de curvas elípticas definidas sobre o conjunto de números reais o ponto no infinito serve como elemento de identidade a saber: definimos que qualquer ponto P pertencente ao estado E se realizamos a operação mais a operação com relação ao ponto no infinito então chegamos ao mesmo ponto P enquanto que se temos 2 pontos P e Q pertencentes ao conjunto E que não são os pontos no infinito e dizem que as coordenadas de P são x1, y2 e x2, y1 onde x2, y2, y2 são todos os elementos do estado Zp então a operação mais é definida da seguinte forma. Para o caso em que x1 = x2 e y1 =-y2 definimos P + Q para ser infinito, este é exatamente o caso este é o mesmo que no caso 2 para as curvas elípticas sobre os números reais. Considerando que se x1 ≠ x2 ou y1 ≠ y2 então definimos P + Q a ser (x3, y3) onde x3 e y3 são elementos de Zp e onde x3 será este valor a saber será &ldash; 2 – x2 – x2 claro tudo o modulo p e y3 será o λ x3) – y1 modulo p direita e o λ será computado de uma forma diferente para 2 sub-casos: se P = Q então λ é definido desta forma a saber (3x12 + a) * (2 y1-1) * (2 y1-1) e isto basicamente corresponde a este caso que é como definimos x3, y3 para o caso de número real e se P ≠ Q então o &ldda; é basicamente o declive da linha que passa pelos pontos P e Q que basicamente é semelhante ao primeiro caso para as curvas elípticas sobre o número real. E acontece que todas as operações de mais e toda a operação de multiplicações que estamos realizando aqui são modulo p quando na verdade estamos realizando operação nas curvas elípticas modulo p e se você ver aqui a forma como definimos &ldda; este é o elemento 2 vezes y1-1 não é 2 /y1. Não é o caso. Isto deve ser interpretado como o elemento 2 vezes y1 ‘ inverso multiplicativo que existe porque estamos realizando operação modulo prime p e da mesma forma para o segundo caso em que o λ é deste formulário 2 − 1 2 − 1, este (x2-x1) -1 é o inverso multiplicativo do elemento (x2-x1) modulo p que também é garantido a existir porque x2-x1 será um valor diferente de 0. Sendo assim, é assim que ampliamos naturalmente a definição da operação mais para curvas elípticas definidas sobre o modulo prime. (Consulte O Tempo De Deslizamento: 18 :18) E para uma ilustração deixe-nos levar este exemplo digamos que executo todas as minhas operações no Z11. Eu levo minha curva para ser equação x3 + x + 6 modulo 11 e levo o meu conjunto E para ser o conjunto de todos x, y pertencente ao conjunto Z11 x Z11 satisfaz esta equação juntamente com o ponto no infinito. Por isso, se você pegar todo x, y pertencente ao conjunto Z11 x Z11 e ver qual deles satisfaz essa equação então obtemos o conjunto E para consistir desses valores todos os pares satisfazem esta equação modulo 11 e junto com isso temos um ponto no infinito. Assim, uma vez que o tamanho deste E é um número primo a saber: temos 13 entidades neste conjunto E ele segue-se a partir de um fato básico da teoria de número que o conjunto E juntamente com a operação mais a que definimos constitui um grupo cíclico aditivo e uma vez que a ordem deste grupo é um número primo a cada elemento deste grupo, exceto o elemento de identidade que é o ponto no infinito pode ser tratado como gerador para este grupo. Portanto, por exemplo podemos pegar o elemento (2, 7) pertencente ao conjunto E que é um elemento não identidade e você pode verificar que realmente ele constitui um gerador a saber de diferentes poderes deste elemento (2, 7) dará a você todos os elementos do estado E. So 0 vezes g conforme a definição ele lhe confere o elemento identidade a saber o ponto no infinito e se executamos a operação 1 vezes g, 2 vezes g, 3 vezes g então a forma como definimos termo de operação de grupo aditivo teremos de volta cada um dos elementos do estado E a saber os elementos não identidade do conjunto E uma vez, isto significa o elemento 2,7 realmente constitui um gerador do conjunto E. (Consulte o Tempo de deslizamento: 20:12) Agora temos outro grupo candidato a saber: os grupos cíclicos baseados em elípticos e vejamos como exatamente o problema DLog, problema de CDH e problema DDH se parecerá com esses grupos porque na descrição do problema DLog, DDH e CDH que tínhamos visto na última palestra supusemos que a operação de grupo sublinhado é a operação multiplicativa mas agora apenas queremos reformular essas definições nos grupos cíclicos baseados em curva elíptica. Então, o que você é dado aqui é a descrição dada de um grupo cíclico baseado nos pontos sobre a curva elíptica modulo prime e dizer que o tamanho do grupo é um número primo q e você recebe um gerador que significa diferentes poderes de g a saber: 1 ª potência de g teria dado a você todo o conjunto E. Então o problema DLog é como segue o desafiante aqui escolhe um índice aleatório do conjunto 0 para q – 1. E ele dá g α tempos g que não é nada, mas o elemento g adicionado a si mesmo (α – 1) vezes e o desafio para o adversário é descobrir o índice α. Há um problema de CDH é o desafiante escolheu 2 pontos aleatórios da curva elíptica escolhendo os índices α e β e computação α vezes g e β vezes g e o objetivo da consulta é computar a função Diffie Hellman sem saber α e β .E o problema DDH é o desafiante prepara um triplet onde os primeiros 2 componentes são pontos aleatórios da curva elíptica e o terceiro componente é a saída da função DH a função Diffie Hellman com relação aos primeiros 2 componentes ou um ponto aleatório da curva e o objetivo do adversário é encontrar out se ele está vendo um triplet Diffie Hellman triplet ou um triplet Hellman non-Diffie (Consulte o Tempo do slide: 22:06) Então agora vimos a definição de curvas elípticas para aplicativos de criptografia para que a próxima pergunta que gostaríamos de responder seja, é o caso de que todas as curvas elípticas modulo prime adequadas para aplicações criptográficas? Por isso, antes de responder isso deixe-nos ver um resultado interessante para a curva elíptica baseada em curva elíptica modulo prime. Portanto, deixe p ser um prime e diga E seja uma curva elíptica arbitrária definida sobre Zp que poderia ser uma curva singular, curva não singular ou seja, diz-se E é a coleção de todos os x, y pares que satisfazem esta equação juntamente com o ponto no infinito então um encadernado muito conhecido que é chamado como Hasse bound lhe confere um limite inferior, bem como superior ligado no número de pontos que temos sobre esta curva elíptica. Portanto, este é o limite inferior (e este é o seu limite superior ligado (e curiosamente temos algoritmos de tempo polinomial no número de bits que precisamos representar um prime p que pode dar-lhe a cardinalidade da curva elíptica, temos também algoritmos de tempo de polia para escolher pontos aleatórios da curva, também temos algoritmos de tempo de polia para adicionar 2 pontos e também sabemos como gerar uma curva elíptica onde o tamanho da curva elíptica é um número primo. Por isso, a próxima pergunta que gostaríamos de responder é que é o DLog, CDH e DDHproblema computacionalmente difícil de resolver em cada grupo cíclico baseado em curva elíptica e resposta não é realmente. Por isso, há certas curvas que devemos evitar completamente para instanciar primitivas criptográficas. Portanto, não podemos tomar as curvas definidas sobre Zp onde o tamanho da curva ou o número de pontos na curva é exatamente p que porque há algoritmos bem conhecidos para resolver os problemas de DLog nesses grupos, portanto, essas curvas tais são chamadas de curvas anômalas. Da mesma forma devemos evitar curvas onde o tamanho da curva p + 1 que são chamados de curvas super singulares e devemos também evitar curvas onde o tamanho da curva é pk-1 para um grupo pequeno. Todas essas curvas são curvas criptograficamente fracas porque como eu disse anteriormente as instâncias do problema DLog é muito fácil de resolver neste grupo. Isso significa que se amanhã você está propondo um novo modulo de curva elíptica baseado em então temos que analisar com muito rigor a propriedade de segurança dessas curvas elípticas antes de tomarmos aquelas curvas elípticas e realizar operações nessas curvas para instanciar qualquer primitiva criptografia dizer por exemplo um protocolo de troca de chave Diffie Hellman e acontece que analisar qualquer elíptico recém proposto é uma tarefa muito desafiadora. Assim, uma alternativa que você pode fazer é confiar e utilizar qualquer uma das curvas recomendadas do NIST se por exemplo curva P256, curva 25519 que foram rigorosamente analisadas pelo NIST e eles afirmam que não encontraram fraquezas naquelas curvas em termos de solução do problema DLog que significa que não existe algoritmos de polenidade para resolver o problema DLog para computar o DLog de qualquer ponto aleatoriamente dado naquelas curva. Mas você deve confiar na reivindicação do NIST por seu próprio risco e é por isso que quando um governo de qualquer país tenta adotar qualquer primitivo criptográfico onde o grupo cíclico subjacente é baseado em curvas elípticas então eles se tornam muito céticos em usar ou confiar nas curvas que são recomendadas pelo NIST porque acreditam que pode haver algumas brechas que só o NIST sabe, mas não é conhecido no domínio público e é por isso que o governo para tal aplicação crítica se empurra para apresentar novas curvas e tentar analisar essas curvas e usar aquelas curvas para instanciar as primitivas de criptografia. Mas acontece que para muitas finalidades práticas essas curvas são muito popularmente usadas para instanciar a curva elíptica e os grupos cíclicos por instanciar os primitivos de criptografia. Por isso, isso me leva ao final desta palestra apenas para resumir nesta palestra introduzimos a segunda turma de grupos cíclicos onde acreditamos que o problema DLog, CDH e DDH será difícil, a saber, os grupos cíclicos baseados em curvas elípticas modulo prime. A vantagem desses grupos em comparação com os grupos cíclicos Zp * modulo multiplicativo p é que aqui os algoritmos mais conhecidos para solução de problema DLog é da ordem 2n/2. Por isso, não temos de operar com modulus muito grande a saber: 2048 bit modulus que foi o caso de subgrupos cíclicos de Zp * seu bastão para configurar o modelo como tamanho para ser 256 bits e obtemos o mesmo nível de segurança que você poderia esperar da AES 128 e não só que os grupos cíclicos baseados em curvas elípticas lhe conferem outra estrutura adicional que chamamos como pares que