Pós-graduação
  1. Introdução à análise real  1.1. Teoria dos conjuntos e lógica em análise real  1.1.1. Conjuntos e operações na teoria dos conjuntos e lógica em análise real  1.1.2. Relações e funções  1.1.3. Lógica e quantificadores  1.1.4. Cardinalidade dos conjuntos  1.2. Espaço métrico  1.2.1. Introdução aos conjuntos abertos e fechados em espaços métricos  1.2.2. Convergência de sequências em um espaço métrico  1.2.3. Função contínua em um espaço métrico  1.2.4. Compacidade e completude em espaços métricos na análise real  1.3. Sequências e séries  1.3.1. Convergência de sequências  1.3.2. Séries infinitas  1.3.3. Convergência uniforme  1.3.4. Séries de potências  1.4. Discriminação  1.4.1. Teorema do valor médio  1.4.2. Série de Taylor  1.4.3. Funções de várias variáveis  1.4.4. Derivada parcial  1.5. Integração  1.5.1. Integração de Riemann e Lebesgue  1.5.2. Integrais impróprias  1.5.3. Teoria da Medida: uma ferramenta fundamental na integração  1.5.4. Teorema de Fubini  1.6. Análise funcional  1.6.1. Compreendendo espaços de Banach  1.6.2. Espaços de Hilbert  1.6.3. Operadores em espaços  1.6.4. Teoria Espectral
  2. Álgebra Abstrata  2.1. Compreendendo grupos na álgebra abstrata  2.1.1. Definições e exemplos de grupos na álgebra abstrata  2.1.2. Homomorfismos de grupos  2.1.3. Introdução aos subgrupos normais  2.1.4. Teorema de Sylow  2.2. Anéis e campos  2.2.1. Ideais e anéis quocientes  2.2.2. Extensões de campos  2.2.3. Teoria de Galois  2.2.4. Anéis de polinômios  2.3. Introdução aos módulos em álgebra abstrata  2.3.1. Homomorfismo de Módulos  2.3.2. Módulos livres  2.3.3. Introdução aos produtos tensoriais  2.3.4. Sequência exata em módulos  2.4. Álgebra linear  2.4.1. Espaço vetorial  2.4.2. Autovalores e autovetores  2.4.3. Espaço de produto interno  2.4.4. Diagonalização
  3. Topologia  3.1. Topologia Geral  3.1.1. Conjuntos abertos e fechados  3.1.2. Compacidade e conexidade  3.1.3. Mapas contínuos  3.1.4. Axioma de separação  3.2. Topologia algébrica  3.2.1. Compreendendo grupos fundamentais em topologia algébrica  3.2.2. Homotopia e homologia  3.2.3. Complexo simplicial  3.2.4. Sequências exatas em homologia  3.3. Topologia Diferencial  3.3.1. Compreendendo variedades na topologia diferencial  3.3.2. Funções Suaves  3.3.3. Espaço tangente e cotangente  3.3.4. Feixes vetoriais
  4. Equações diferenciais  4.1. Equação diferencial ordinária  4.1.1. Equações de primeira ordem  4.1.2. Equações lineares de segunda ordem  4.1.3. Sistemas de equações diferenciais  4.1.4. Análise de estabilidade em equações diferenciais ordinárias  4.2. Equações diferenciais parciais  4.2.1. Classificação de PDE  4.2.2. Compreendendo séries de Fourier em equações diferenciais parciais  4.2.3. Introdução às funções de Green  4.2.4. Método de caracterização  4.3. Sistemas dinâmicos em equações diferenciais  4.3.1. Teoria da Sustentabilidade  4.3.2. Ciclos limite em sistemas dinâmicos  4.3.3. Teoria do caos  4.3.4. Teoria da bifurcação
  5. Probabilidade e estatística  5.1. Teoria da probabilidade  5.1.1. Variáveis aleatórias  5.1.2. Distribuições de probabilidade  5.1.3. Lei dos grandes números  5.1.4. Teorema Central do Limite  5.2. Inferência estatística  5.2.1. Teste de hipótese  5.2.2. Intervalo de confiança  5.2.3. Métodos bayesianos  5.2.4. Estimativa de máxima verossimilhança  5.3. Processos estocásticos  5.3.1. Cadeias de Markov  5.3.2. Movimento Browniano  5.3.3. Compreendendo os processos de Poisson  5.3.4. Martingales: Um estudo abrangente em probabilidade e estatística
  6. Análise numérica  6.1. Soluções numéricas de equações  6.1.1. Descoberta original  6.1.2. Métodos iterativos  6.1.3. Análise de convergência  6.1.4. Limites de erro em soluções numéricas de equações  6.2. Álgebra linear numérica  6.2.1. Fatoração de matrizes  6.2.2. Cálculo de autovalores  6.2.3. Matrizes esparsas  6.2.4. Técnicas de pré-condicionamento  6.3. Integração e diferenciação numéricas  6.3.1. Métodos de quadratura  6.3.2. Introdução às diferenças finitas  6.3.3. Análise de erro na integração e diferenciação numérica  6.3.4. Métodos adaptativos em integração e diferenciação numérica
  7. Análise complexa  7.1. Números complexos  7.1.1. Forma polar  7.1.2. Conjugados Complexos  7.1.3. Forma exponencial de números complexos  7.1.4. Raízes da unidade  7.2. Funções analíticas  7.2.1. Equações de Cauchy–Riemann  7.2.2. Séries de potências  7.2.3. Mapeamento conforme  7.2.4. Funções harmônicas  7.3. Integração no plano complexo  7.3.1. Teorema de Cauchy  7.3.2. Teorema do resíduo  7.3.3. Integração de contorno  7.3.4. Transformadas integrais
  8. Lógica Matemática e Fundamentos  8.1. Lógica proposicional  8.1.1. Tabelas de verdade  8.1.2. Equivalência lógica na lógica proposicional  8.1.3. Técnicas de prova em lógica proposicional  8.1.4. Solução na lógica proposicional  8.2. Lógica de predicados  8.2.1. Quantificadores na lógica de predicados  8.2.2. Sistemas formais na lógica de predicados  8.2.3. Completude e correção  8.2.4. Teoria dos modelos  8.3. Teoria dos conjuntos  8.3.1. Cardinalidade e ordinalidade  8.3.2. Sistemas axiomáticos  8.3.3. Compreendendo a teoria dos conjuntos de Zermelo-Fraenkel  8.3.4. Forças na teoria dos conjuntos
  9. Personalização  9.1. Programação linear  9.1.1. Método simplex  9.1.2. Dualidade na programação linear  9.1.3. Análise de sensibilidade em programação linear  9.1.4. Métodos de ponto interior  9.2. Programação não linear  9.2.1. Descida do Gradiente  9.2.2. Múltiplos de Lagrange  9.2.3. Otimização convexa  9.2.4. Programação quadrática  9.3. Otimização Combinatória  9.3.1. Algoritmos de grafos  9.3.2. Programação inteira  9.3.3. Fluxo de Rede  9.3.4. Algoritmos de aproximação
  10. Matemática discreta  10.1. Teoria dos grafos  10.1.1. Representação de grafos  10.1.2. Planicidade e cor  10.1.3. Algoritmo de caminho mais curto  10.1.4. Fluxo de rede  10.2. Companheirismo  10.2.1. Percmutações e combinações  10.2.2. Função geradora  10.2.3. Relação de recorrência  10.2.4. Compreendendo o Princípio da Inclusão-Exclusão  10.3. Criptografia  10.3.1. Aplicações da teoria dos números na criptografia  10.3.2. Criptografia Simétrica e Assimétrica  10.3.3. RSA e criptografia de curva elíptica  10.3.4. Criptografia pós-quântica

Pós-graduação → Matemática discreta → Criptografia ↓


RSA e criptografia de curva elíptica


Códigos e criptografia estão no cerne das comunicações digitais modernas. Os dois métodos mais conhecidos para comunicações seguras, RSA e Criptografia de Curva Elíptica (ECC), baseiam-se nos princípios da matemática discreta. Este artigo explorará mais a fundo esses sistemas criptográficos e ajudará a esclarecer como usamos princípios matemáticos para criptografar dados, para que se mantenham seguros de olhares curiosos.

Criptografia RSA

RSA leva o nome de seus desenvolvedores, Ron Rivest, Adi Shamir e Leonard Adleman, que o introduziram em 1977. É uma forma de criptografia de chave pública, que utiliza duas chaves – uma chave pública usada para criptografar e uma chave privada usada para descriptografar.

Princípios básicos do RSA

A segurança do RSA depende da dificuldade de fatorar grandes inteiros. Funciona assim:

  1. Criação de chaves:
    • Escolha dois números primos diferentes p e q.
    • Calcule n = p * q. O número n é usado como módulo para ambas as chaves pública e privada. Seu comprimento, geralmente expresso em bits, é o comprimento da chave.
    • Calcule φ(n) = (p-1)(q-1).
    • Escolha um inteiro e tal que 1 < e < φ(n) e gcd(e, φ(n)) = 1. O número e é o expoente público.
    • Defina d como d ≡ e -1 (mod φ(n)), o que significa que d é o inverso multiplicativo modular de e módulo φ(n).
    A chave pública é (e, n), e a chave privada é (d, n).
  2. Criptografia:
    • A mensagem M é criptografada com a chave pública do destinatário: C ≡ M e (mod n), onde C é o texto cifrado.
  3. Descriptografia:
    • O texto cifrado C é descriptografado usando a chave privada: M ≡ C d (mod n), retornando a mensagem original M.

Exemplos ilustrativos

Suponha que escolhamos os números primos p = 61 e q = 53, então n = 61 * 53 = 3233.

O total é φ(n) = (61-1)(53-1) = 3120.

Escolha e = 17, que é coprimo a 3120.

Para encontrar d, o algoritmo euclidiano estendido fornece d = 2753.

Criptografando uma mensagem

Deixe M = 65 mensagens criptografadas C:

C = 65 17 mod 3233

Usando exponenciação rápida, obtemos C = 2790.

Descriptografando a mensagem

Para recuperar M:

M = 2790 2753 mod 3233

Mais uma vez, utilizando cálculo eficiente retornamos a M = 65.

Segurança do RSA

A força do RSA reside no tamanho do módulo n. Quanto maior o valor, mais difícil é dividir n em seus componentes primos, p e q. Esta dificuldade computacional garante a segurança da chave privada. Além disso, escolher um expoente suficientemente grande e desempenha um papel em tornar o RSA robusto contra tipos específicos de ataques.

Criptografia de curva elíptica (ECC)

A criptografia de curva elíptica é um método moderno de criptografia. Utiliza as propriedades das curvas elípticas em campos finitos. A ECC é elogiada por sua eficiência, pois fornece segurança equivalente ao RSA, mas com tamanhos de chave muito menores.

Entendendo as curvas elípticas

Uma curva elíptica é definida pela seguinte equação:

y 2 = x 3 + ax + b

Para fins de criptografia, focamos em curvas elípticas sobre campos finitos, especialmente campos de ordem prima.

y 2 = x 3 + ax + b sobre campos finitos

Considere um campo finito F p onde p é um número primo. Então a curva elíptica consiste nos pontos (x, y) que satisfazem a equação da curva, que inclui um ponto especial no infinito denotado como O

Operações nos pontos das curvas elípticas

As operações em curvas elípticas são regidas pelas regras de adição de pontos e multiplicação por escalar. Essas operações operam sob aritmética modular de campos finitos.

Adicionando dígitos

Dado dois pontos P = (x 1 , y 1) e Q = (x 2 , y 2), sua soma R = P + Q = (x 3 , y 3) é calculada como segue:

  • Se P ≠ Q, então use: 
    λ = (y 2 - y 1) / (x 2 - x 1) mod px 3 = λ 2 - x 1 - x 2 mod py 3 = λ(x 1 - x 3) - y 1 mod p
  • Se P = Q, então use: 
    λ = (3x 1 2 + a) / 2y 1 mod px 3 = λ 2 - 2x 1 mod py 3 = λ(x 1 - x 3) - y 1 mod p

Multiplicação por escalar

Esta operação é importante na ECC. Se k é um escalar e P é um ponto na curva, então kP é o resultado obtido ao adicionar o P a ele mesmo k vezes.

Geração de chave ECC

A ECC usa multiplicação por escalar para gerar chaves. Aqui está um esboço simples de como gerar um par de chaves de curva elíptica:

  1. Escolha um número primo p e parâmetros a e b para definir a curva.
  2. Escolha o ponto base G na curva.
  3. Selecione um inteiro aleatório d como a chave privada.
  4. Calcule Q = dG, onde Q é a chave pública.

Exemplo de geração de chave pública ECC

Considere uma curva elíptica em F p onde p = 17, a = 2, e b = 2. Vamos escolher G = (5,1).

Suponha d = 7, então calculamos:

Q = 7G = G + G + G + G + G + G + G

Somando repetidamente os pontos, obtemos Q

Segurança da ECC

A segurança da ECC é baseada no Problema do Logaritmo Discreto da Curva Elíptica (ECDLP). Dados dois pontos P e kP, determinar k é computacionalmente impossível. Isso é semelhante ao problema de fatoração de grandes números primos no RSA.

Comparação entre RSA e ECC

Embora RSA e ECC sirvam ao mesmo propósito em termos de criptografar, assinar e verificar dados, eles o fazem por meio de princípios matemáticos diferentes. Aqui estão algumas diferenças chave:

  • Tamanho da chave: ECC oferece maior força por bit do que RSA, o que significa chaves menores para o mesmo nível de segurança.
  • Desempenho: ECC pode ser mais eficiente em termos de custo computacional, especialmente para dispositivos móveis e ambientes com recursos limitados.
  • Longevidade: Como o RSA exigirá tamanhos de chave maiores para manter a segurança no futuro, a ECC é uma candidata mais promissora para segurança criptográfica a longo prazo.

Representação visual

Considere como esses princípios funcionam na representação gráfica de uma curva elíptica.

Hey

Neste exemplo, a curva azul representa uma curva elíptica, enquanto o ponto rotulado O representa o ponto no infinito, um conceito essencial na aritmética de curvas elípticas.

Ambos RSA e ECC representam importantes realizações criptográficas baseadas em matemática discreta. RSA depende fortemente da fatoração de inteiros, enquanto ECC depende das propriedades geométricas das curvas elípticas. Juntos, eles fornecem soluções robustas para proteger dados na era digital, cada um com suas próprias forças e aplicações únicas.


Pós-graduação → 10.3.3


U
username
0%
concluído em Pós-graduação

← Anterior (10.3.2)
Criptografia Simétrica e Assimétrica
Próximo (10.3.4) →
Criptografia pós-quântica

Comentários 



RSA e criptografia de curva elíptica

https://www.buddymath.com/g/10.3.3?bmal=pt