Loading
Nota de Estudos
Study Reminders
Support
Text Version

Grupos Cíclicos Candidatos

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 CryptographyDr. Ashish ChoudhuryDepartamento de Ciência da ComputaçãoInstituto Indígena de Ciência – BangalorePalestra-40Candidatos Clíclicos para Criptográficos Parte I(Consulte O Slide Time: 00:27)Olá a todos. Bem-vindo a esta palestra. Por isso, o plano para esta palestra é o seguinte. Nós introduzimos alguns grupos cíclicos candidatos onde acreditamos que o problema DDH, problema de CDH e os problemas discretos-log são de fato difíceis de serem resolvidos. A saber, introduziremos os grupos cíclicos de ordem prime . (Consulte O Slide Time: 00:46)Então, vamos começar nossa discussão com a importância de bons grupos cíclicos. Por isso, lembre-se que em a última palestra vimos a definição do assunção DLog, assunção CDH e DDH assumpção. Portanto, se estamos projetando qualquer primitivo criptográfico cuja segurança é baseada na dureza desses problemas, então precisamos escolher adequadamente os grupos cíclicos subjacentes .Porque se os grupos cíclicos subjacentes que utilizamos para instanciar o primitivo criptográfico, se nesses grupos esses problemas são mais fáceis de resolver, então o resultante criptográfico resultante não será mais seguro. Portanto, agora a questão interessante é para quais grupos cíclicos ou para os quais candidatos cíclicos candidatos de fato estes problemas, a saber, o problema DLog, o problema de CDH e o problema DDH são difíceis de resolver. Então lembre-se na última palestra as etapas concretas do Diffie – Hellman Key ExchangeProtocolo foi dado supondo que estamos operando em um grupo onde o problema DLog, CDH e DDH são de fato difíceis. Mas agora nossa pergunta é como exatamente encontramos esses grupos. Então, há 2 escolhas populares de grupos cíclicos ou grupos cíclicos candidatos, onde acreditamos que esses problemas são de fato difíceis de serem resolvidos. A primeira escolha são os grupos de prime order, a saber, grupos em que o número de elementos é algum número primo. No entanto, verifica-se que nem todos os grupos cíclicos de prime ordem são apropriados para aplicações criptográficas. De fato, veremos algum candidato de primeira ordem grupos cíclicos onde problema de DLog, problema de CDH, problema de DDH são de fato muito fáceis de resolver.Mas acontece que temos outros tipos de grupos cíclicos de ordem prime, onde nós fortemente acreditamos que DLog, CDH, problema DDH são de fato difíceis de serem resolvidos. A segunda escolha de escolher os grupos cíclicos candidatos, é o grupo baseado em pontos sobre curvas elípticas. Por isso, nesta palestra vamos considerar os grupos de prime-order baseados em certas propriedades. Na próxima palestra veremos os grupos cíclicos com base nos pontos em curvas elípticas e então vamos comparar esses 2 tipos de grupos, qual deles é melhor instanciar as primitivas criptográficas, cuja segurança é baseada na dureza dos problemas DLog, CDH e DDH. (Consulte O Tempo De Deslizamento: 03:07)Então antes de prosseguirmos mais, vejamos os grupos cíclicos inadequados para aplicações criptográficas , a saber quais grupos cíclicos devemos evitar para instanciar as primitivas criptográficas , cuja segurança é baseada em DLog, CDH e DDH assumpção. Então começamos com o grupo multiplicativo , a saber, o set ZÉ?, onde Zé? consiste nos elementos 1? − 1 e minha operação subjacente é o modulo de multiplicação?. Então lembre-se modulo de multiplicação? é definido da seguinte forma. Se você deseja executar o modulo de multiplicação ? de 2 números? e? a partir do conjunto ZÉ?, então você executa a multiplicação de número inteiro ?? e pegar o restante, fazendo um mod? operação, o que garante que o restante do resultante restante esteja no conjunto 0? − 1. Acontece que este conjunto ZÉ?, junto com este modulo de multiplicação ? operação, constitui um grupo cíclico de ordem? − 1.Por que de ordem? − 1? Porque os elementos neste conjunto Zé? são os elementos 1? − 1, então tem ? − 1 número de elementos. E desde então? é prime,? − 1 não pode ser prime, é por isso que a ordem deste grupo é um número não primo. E podemos provar que esse grupo é um grupo cíclico. E temos algoritmos eficientes para escolher um gerador para este grupo dada a factorização de ? − 1. Então lembre-se do Diferfie – Hellman key-exchange protocol passos que tínhamos visto na última palestra, o público configurado que precisamos de lá é a descrição do grupo, onde como parte da descrição do grupo, os detalhes do gerador também devem ser conhecidos publicamente. Então precisamos de algoritmo de polítime para picar o gerador e quando eu digo algoritmo de polítime, eu significa polinomial no número de bits que precisamos para representar o elemento do conjunto Zpartir?. Então temos algoritmos de polítime, algoritmo eficiente para escolher geradores para este grupo, dado que você recebe a factorização de? − 1.Então isso também é um positivo deste grupo. Também acredita-se que o problema do DLog seja de fato difícil de ser resolvido neste grupo, fornecido? é suficientemente grande. Portanto, essa também é uma boa notícia com relação a esse grupo. Mas o problema aqui é que o problema DDH não é duro em geral em este grupo e isso significa que não podemos usar este grupo para instanciar o Diffie – Hellman Key Exchange Protocol. Pois lembre-se pela segurança do protocolo Diffie – Hellman Key-Exchange, a saber, para a forte-privacidade do protocolo Diffie – Hellman Key-Exchange, nós precisamos que o problema DDH deve ser difícil de ser resolvido no grupo subjacente. Então se eu usar o Zvão?,junto com o modulo de multiplicação da operação? como meu grupo cíclico subjacente e realizar operações conforme as etapas do protocolo Diffie – Hellman Key-Exchange, então não é garantido que o protocolo de troca de chave resultante satisfaz a noção de privacidade forte. Porque não é garantia que o problema do DDH neste grupo específico seja duro. Então isso significa que esse grupo é adequado apenas para instanciar aqueles aplicativos ou aquelas primitivas criptográficas, cuja segurança é apenas baseada na suposição DLog e não na suposição DDH, que não é o caso do Diffie – Hellman Key-exchange protocol.Então, essa é a má notícia com relação a este grupo. Então isso significa que você pode ver agora o grupo ZPé?com o modulo de multiplicação da operação? pode não ser um grupo adequado para instanciar o Diffie –Hellman Key-exchange protocol, é um grupo cíclico inadequado. Agora considere o grupo aditivo. Então o grupo anterior Zé? com a multiplicação da operação modulo? era um grupo multiplicativo. Agora considere um grupo aditivo, onde meu conjunto é Z?,consistindo dos elementos 0? − 1 e minha operação é aditamento modulo?, onde adição modulo? em elementos? e? é definido da seguinte forma: você executa a adição inteira de? e ? e levar o lembrete com respeito ao modulo?. É assim que definimos a adição de?e? modulo?. Por isso, com respeito a este grupo os fatos a seguir são conhecidos. Em primeiro lugar, esse grupo é conhecido por ser um grupo cíclico e que também de prime order. Porque os elementos no conjunto Z? tem 0? − 1, nomeadamente, tem? número de elementos, onde? é um prime e é conhecido para ser um grupo cíclico. Portanto, essa é uma boa notícia. E outra propriedade interessante deste grupo de ordem prime, é que todo elemento, exceto o elemento de identidade é um gerador e este não é apenas específico para este grupo. Esta propriedade detém com relação a qualquer grupo que tenha uma ordem prime. O fato fundamental que vem da algebra abstrata é que se você tem um grupo cuja ordem é prime, a saber, ela consiste em número primo de elementos, então qualquer elemento desse grupo , exceto o elemento de identidade desse grupo, é um gerador. Por isso, o picking gerador não está em todo indo ser uma tarefa sofisticada. Se operarmos ou se executamos operações neste grupo, você pode escolher qualquer elemento, exceto 0, que é obrigado a ser um gerador. No entanto, a parte mais infeliz ou o fato mais infeliz com relação a esse grupo é que o problema da DLog é muito, muito fácil de ser resolvido neste grupo. Em quantidade poltica de tempo você pode computar o DLog de qualquer elemento escolhido aleatoriamente deste conjunto com probabilidade 1. Então o que exatamente será uma instância do problema DLog neste grupo? Então você escolhe um índice aleatório?no set 0? − 1, porque o seu grupo é de tamanho?. E você computa??, onde? é o gerador conhecido publicamente. E dizer que a saída resultante é? e o desafio para você é o de computar este desconhecido?, tal??? modulo? teria dado a você?. Então quais são as coisas conhecidas por você, você está sabendo? aqui, você está sabendo? aqui e você sabe que tudo é modulo relacionado? aqui e o seu objetivo é descobrir? aqui. Acontece que podemos computar facilmente? aqui, multiplicando-se tanto o lado com o inverso multiplicativo de?. E inverso multiplicativo de? modulo? pode ser computado em quantidade de tempo polinomial. E se você multiplicar ambos os lados com inverso multiplicativo de ?, então o efeito de? cancela fora, e o que você é deixado com, é?. E daí você está obtendo o valor de?, a saber, o log discreto de? para a base? em quantidade polinomial de tempo. Então eu não estou dando os detalhes completos do discreto log solver para este grupo, mas essa é a ideia geral do . Portanto, apesar de esse grupo específico ter algumas propriedades agradáveis, a saber, é um grupo cíclico de ordem prime , o picking gerador não é uma tarefa difícil, a parte mais infeliz aqui é que o problema do DLog é muito, muito fácil de resolver e que automaticamente implica que o problema de CDH é fácil de ser resolvido. E o que automaticamente implica que o problema DDH também é mais fácil de ser resolvido em este grupo. Então isso significa que esse grupo não pode ser usado em tudo para instanciar qualquer primitivo criptográfico , cuja segurança é baseada na dureza do problema DLog, problema de CDH, problema DDH . (Consulte O Slide Time: 10:24)Então agora vamos ver outro grupo, que é bastante apropriado para instanciar as primitivas criptográficas com base, na dificuldade dos problemas DLog e CDH e DDH. E esse grupo é basicamente um sub-grupo cíclico de primeira ordem do grupo Zícia?, com a multiplicação de operação modulo?. Então, deixa? e? ser primes, publicamente conhecidos, tal que? está relacionado a? nesta forma, a saber? =?? + 1, onde? também é publicamente conhecido.E então deixe-me definir um conjunto? ser o conjunto de todos os elementos da forma h? modulo?, onde hpertence ao conjunto Zura?. Então pictorialmente o que eu estou fazendo aqui é, você imagina os elementos neste círculo maior de como os elementos de Zé? e Zé? tem? − 1 número de elementos, pois o meu operação subjacente é o modulo de multiplicação?. O que eu estou fazendo aqui está no set?, eu sou apenas coletando um subconjunto menor de elementos da Zpartir?. Namely eu estou coletando todos os? ?hresíduos modulo?. Por que? ?hresíduos? Porque eu estou tirando h de Zento? e elevá-la para o poder? e tomando modulo?. E é por isso que o resultado pode ser visualizado como? ?hmodulo de resíduos?. Por exemplo, se? = 2, então basicamente? consiste em todos os elementos , que são squares perfeitos modulo?, pois estarei coletando elementos do formulário h2 mod?, onde h pertence a Zpartir?.Considerando que se? teria sido 3, então? basicamente consiste em todos os elementos que são perfeitos cube modulo? e assim por diante. Então em geral se? é algum h?, então? é o conjunto de todos? ?hresíduos modulo?. Então, é assim que eu estou computando esse conjunto? aqui. E um resultado muito interessante da teoria do número, que eu não vou provar aqui, afirma explicitamente que a coleção? ou o subconjunto ?, que é um subconjunto de Zhost?, juntamente com o modulo de multiplicação da operação?, constitui um grupo de ordem?.Namely o conjunto? terá? número de elementos. E desde que eu selecionei? para ser um prime, que significa a ordem de? é um prime. E podemos provar que se você executar a operação modulo de multiplicação? sobre os elementos que selecionamos no conjunto?, então ele satisfaz os axiomas do grupo . A saber, podemos provar que os elementos em? pode ser expressa como os poderes de um gerador, onde os índices dos poderes estarão na faixa de 0? − 1, para algum gerador ?, pertencente ao conjunto?. E além disso a importante propriedade interessante que obtemos aqui é que desde o meu set? ou em grupo? tem prime order, todo elemento neste conjunto?, exceto o elemento identidade, será um gerador para o subgrupo que eu escolhi. Por que eu estou chamando isso de subgrupo? Porque os elementos no conjunto? é um subconjunto dos elementos em Zbasta?. Mas a operação neste conjunto?, a saber, o modulo de multiplicação?, é o mesmo que a operação no grupo maior a saber, Zpartir?. É por isso que estou a chamá-lo como um subgrupo. Sendo assim, uma vez que a ordem deste subgrupo é prime, cada elemento deste subgrupo será um gerador, exceto o elemento de identidade. Além disso, para o subgrupo que escolhi aqui, temos algoritmos eficientes para captação de elementos aleatórios , bem como para a realização da exponenciação de grupo. Então se você relembrar os passos do Diffie – Hellman key-exchange protocol, seu emissor e receptor têm que escolher elementos aleatórios do grupo subjacente sobre o qual eles são realizando as operações. Então para isso precisamos ter algoritmo eficiente, algoritmos de polítime, para colher elementos aleatórios do grupo. E acontece que se eu definir meu grupo para ser o conjunto de todos? ?hresíduos modulo?, então eu tenho um algoritmo eficiente para captação de elementos aleatórios deste grupo e para a realização da exponenciação de grupo. E acontece que DLog, CDH, DDH, todos esses problemas são acreditados para muito, muito duro para valores suficientemente grandes de? e ?, se eu escolher meu subgrupo? para ser o conjunto de todos? ?hresíduos modulo?. (Consulte O Slide Time: 14:58)Então, vamos ver uma ilustração de subgrupo cíclico de primeira ordem de Z?s. Então imagine? = 11, onde ? = 11 é um número primo. Assim, eu posso expressar 11 no formato 2 × 5 + 1 e Z11O basicamente consiste em dos elementos 1 10. Então se eu levar o meu? para ser 5, então? e? estão relacionados como 2 vezes 5 + 1. Então eu posso levar o meu? para ser 2 e o que eu posso fazer é, eu posso definir o meu conjunto? ser todo o quadrado perfeito modulo 11. Refiro-me a todos os elementos h do conjunto Z11oaltoeleva-o para a potência 2 e faça o modulo 11. E a saída resultante é a minha coleção?. Então o que eu fiz nesta tabela, é eu ter tirado todos os elementos do conjunto Z11e os quadrados resultantes e se eu pegar as quadras resultantes eu obtenho meu set?. Nomeadamente o meu conjunto? consiste dos elementos 1,3, 4, 5, 9 e você pode ver na tabela , que sob os quadrados, os elementos 1,3, 4, 5, 9 são repetidos duas vezes.Então 12 me dá 1. 22me dá 4, então faz 92. 32me dá 9 e 82dá eu 9 e assim por diante. Isto porque qualquer quadrado perfeito, a saber, um elemento no conjunto? terá 2 raízes quadradas, pois se trata de um resíduo quadrado. Então ele terá 2 modulo raiz quadrada?. E se uma das raízes quadradas for? então a outra raiz quadrada será −?. E −? aqui não é nada mas? −?.Então por exemplo se eu pegar o elemento 9, que é um elemento de?, então ele tem 2 raízes quadradas porque ele é o resultado de 32, então é por isso que 3 é uma das raízes quadradas. E similarmente 9 é o resultado de 82modulo 11 e é por isso que 8 também é uma das raízes quadradas de 9. E é fácil de ver que o subconjunto 1, 3, 4, 5, 9 juntamente com o modulo de multiplicação da operação 11 constitui um grupo de ordem 5.Você pode verificar isso da mesma forma, para o mesmo exemplo onde? = 11, eu posso levar o meu? para ser 2 e consequentemente? será 5. E agora se eu me concentrar no quinto modulo de resíduos 11, a saber, a coleção de todos os h5módulo 11, onde h pertence a Z11e então eu obtenho o subconjunto 1, 10 e este subconjunto 1,10, podemos ver que ele realmente constitui um grupo cíclico de ordem 2. Porque ele tem 2 elementos e ele tem o elemento de identidade e 10 é o gerador. Então isso é uma ilustração aqui. Mas não provei os resultados genéricos. A saber, se eu levo? e? para estar no formulário ? =? ×? + 1, então o conjunto de todos? ?hresíduos dá a você um grupo cíclico. Não estou provando que, você pode ver qualquer uma das referências padrão para a teoria do número para a prova desse fato.(Consulte o Slide Time: 18:11)Então agora a questão é, vimos que podemos formar um subgrupo cíclico de primeira ordem de Z?Datae DLog, CDH, problemas de DDH são acreditados como muito difíceis nesses subgrupos cíclicos. As perguntas acontece que o que deve ser a magnitude do resultante? e? para garantir que realmente os problemas DLog, CDH e DDH são difíceis nos subgrupos resultantes. Então o problema que a gente quer abordar aqui é que somos dadas? e? que são primes, onde ? é do formulário?? + 1. E nós encontramos um conjunto de? ?hresíduos, que sabemos que é um grupo cíclico , que tem um gerador? e dizer o número de bits que precisamos representar? é l e o número de bits que precisamos representar? é?. Agora os algoritmos mais conhecidos para resolver o problema discreto-log no subgrupo que formamos aqui, ele cai abaixo de 2 categorias.Temos o algoritmo Classe I que conhecemos para resolver o problema de log discreto. Seu tempo de execução é de ordem √?. E agora desde então? é da magnitude 2?, isso significa √? será do ?magnitude 22. Então, apesar de este ser o tempo exponencial no parâmetro de segurança subjacente, temos que decidir muito judicialmente o valor de?, quando estamos instanciando esse subgrupo para instanciando um primitivo criptográfico cuja segurança é baseada na assunção DLog.Acontece que se você configurar? = 256, a saber, se selecionarmos? que é um prime de 256 bit e adequadamente configura um prime? onde? e? estão relacionados com a relação que? é?? + 1, então apenas configurando? = 256, atingimos um nível de segurança que é comparável ao AES-128. Então lembram quando vimos a instanciação prática de cifra de blocos, como AES, DES, onde nós busamos a segurança prática e por segurança prática de AES-128, quero dizer que o melhor ataque possível que um adversário pode lançar para recuperar uma chave AES, onde o adversário recebe vários pares (?,?), onde? é a entrada AES e? é a saída AES correspondente, sob uma chave desconhecida , então a complexidade do ataque mais conhecido deve ser de ordem 2128. Então acontece fora que se instanciamos qualquer primitivo criptográfico com base na dureza do problema DLog selecionando um subgrupo cíclico de Zhost? por definição? = 256, então o algoritmo mais conhecido para 256resolvendo o problema DLog por esta classe de algoritmo levará tempo aproximadamente da ordem 2 2, que será de ordem 2128. Isso significa que obtemos o mesmo nível de segurança, já que o seu AES-128 iria ter fornecido.Considerando que os algoritmos Classe 2 para solução do problema DLog neste subgrupo cíclico, seu tempo de execução é de ordem 2 para a ordem de potência logarítmica em número de bits que nós precisamos representar?. Assim, a partir de 2016, este algoritmo Classe 2 pode ser usado para resolver instâncias do problema de DLog e para qualquer instanciação do subgrupo cíclico onde l é 768. E é sugerido que para ter noção significativa de segurança devemos operar definindo l a ser 2048.Isso significa que se resumimos, para enfrentar os algoritmos de classe 1 e algoritmos de classe 2 que nós temos para resolver os problemas DLog neste subgrupo cíclico, para garantir que tenhamos razoável quantidade de segurança ou o tempo de execução do adversário para resolver o problema de log discreto é de ordem suficientemente grande, temos que executar computações modulo 2048 bit prime number. Isso significa dizer por exemplo se usarmos o Diffie – Hellman Key-exchange protocol e se nós instanciamos os passos do Diffie – Hellman Key-exchange protocol configurando meu set? ser set de todos? ?hresíduos modulo?, então eu tenho que garantir que o meu? deve ser um número 2048 bit grande . Isso significa que tanto o emissor quanto o receptor têm que realizar cálculos modulo este grande número primo, que realmente reduz o tempo de execução tanto do emissor quanto do receptor .Então, apesar de termos agora um subgrupo cíclico candidato que agora podemos usar para instanciar qualquer primitivo criptográfico, cuja segurança é baseada na dureza das premissas DLog, CDH e DDH , verifica-se que o tempo de execução do remetente, do receptor ou de todas as partes envolvidas também reduz. Porque vamos realizar operações modulo um número primo muito grande.Então uma questão interessante será, podemos ter outros tipos de grupos cíclicos candidatos, em que não temos que executar modulo de operações um número primo tão grande, mas ainda assim o problema CDH , problema DDH e problemas de DLog são difíceis de serem resolvidos nesses grupos alternativos. Snd na próxima palestra, veremos um tal grupo candidato. Então isso me leva até o final de esta palestra. Nesta palestra introduzimos um grupo cíclico candidato, a saber, o subgrupo cíclico de ZÉ? com relação ao modulo de multiplicação da operação?, e acreditamos que o problema de CDH , o problema DLog e o problema DDH são de fato difíceis de serem resolvidos neste grupo. No entanto para obter nível prático de segurança, temos que definir o valor do modulus? ser um número muito grande, para garantir que o emissor e o receptor obtenham uma quantidade razoável de segurança, o que realmente acaba tornando o tempo de execução do remetente e do receptor também lento. Obrigado você.