Universidade Federal de Santa Catarina

Centro Tecnológico
Depto de Informática e Estatı́stica
INE5403-Fundamentos de Matemática Discreta para a Computação

12) Teoria de Números

12.4) Aplicações da MD: O sistema criptográfico RSA
NOTA: Este material foi elaborado com base nas seguintes referências:
ˆ Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 2nd ed., MIT Press, 2001.
ˆ Rosen, “Discrete Mathematics and its Aplications”, 6th ed., McGraw-Hill, 2007.

Princı́pios de Criptografia

ˆ Métodos convencionais: baseados em engenharia

ˆ Criptografia com chave pública:

– baseada em funções matemáticas

– assimétrica: duas chaves relacionadas
* uma é amplamente divulgada: chave pública
* a outra é guardada em segredo: chave privada

ˆ Uso da chave privada (secreta, pessoal) pode ser comprovado sem a participação do seu proprietário:

– integridade de dados
– análogo eletrônico de uma assinatura manuscrita

Origem: troca de chaves

ˆ Em 1976, Diffie e Hellman propuseram um modo seguro de trocar chaves criptográficas.

ˆ Era baseado na suposição de existência de funções de mão única, que são funções em que:

y = f (x) é fácil

y = f −1 (x) é difı́cil

– Exemplo: f (x) = 12345x mod 31469

ˆ Exemplo deste esquema na comunicação entre A e B:

– A e B decidem usar a função (pública) f (x) = 12345x mod 31469

– A gera a = 27283 (secreto) e o envia para B “disfarçado” como:
1234527283 mod 31469 = 9800
– B gera b = 12745 (secreto) e o envia para B “disfarçado” como:
1234512745 mod 31469 = 26310

243
 – A eleva o nro que recebeu ao seu expoente secreto, obtendo:
2631027283 mod 31469 = 27313
– B eleva o nro que recebeu ao seu expoente secreto, obtendo:
980012745 mod 31469 = 27313
– ambos utilizam a chave 27313 = 12345a×b mod 31469 2

Criptografia com Chave Pública

ˆ Problema do esquema anterior: só funcionava com troca simultânea de informações.

ˆ Na sequência, Diffie e Hellman postularam a existência de um sistema criptográfico com duas chaves

ˆ Chaves seriam “duais”: o que uma faz, a outra desfaz

ˆ Isto resolveria de uma vez o problema da troca de chaves:

– uma das chaves poderia ser divulgada publicamente!

– não seria mais preciso “combinar” uma chave secreta
ˆ 1ra implementação do esquema imaginado por Diffie e Hellman:

– Rivest, Shamir e Adleman (MIT, 1977)

ˆ Baseada na dificuldade de fatoração de produtos de primos grandes

– dados p e q, calcular n = p × q: fácil

– dado n = p × q, achar p e q: difı́cil, se p e q forem grandes...

Fundamentos matemáticos (1): aritmética modular

ˆ Aritmética “módulo n” ou “mod n”

ˆ Usa inteiros não-negativos menores do que algum inteiro positivo n

ˆ Operação: a mod n (resto da divisão de a por n)

ˆ Exemplo: hora do dia (mod 24)

Adição modular

ˆ Vejamos adição “mod 10”:

3+5=8
7 + 6 = 13 → resposta mod 10 = 3
– só usar último dı́gito...
ˆ Adição de constante mod 10 (tabela):

– serve como esquema para cifragem de dı́gitos

– chave secreta para cifrar = constante “k”
* decifragem = subtrair “k” (mod 10)
· se resultado < 0, acrecentar 10

244
 + 0 1 2 3 4 5 6 7 8 9
0 0 1 2 3 4 5 6 7 8 9
1 1 2 3 4 5 6 7 8 9 0
2 2 3 4 5 6 7 8 9 0 1
3 3 4 5 6 7 8 9 0 1 2
Adição módulo 10 4 4 5 6 7 8 9 0 1 2 3
5 5 6 7 8 9 0 1 2 3 4
6 6 7 8 9 0 1 2 3 4 5
7 7 8 9 0 1 2 3 4 5 6
8 8 9 0 1 2 3 4 5 6 7
9 9 0 1 2 3 4 5 6 7 8

Subtração modular

ˆ Subtração: adicionar −k, a inversa aditiva de k

ˆ Inversa aditiva de k:

– “número que é preciso adicionar a k para obter 0”

* k + “−k” = 0
– em aritmética mod 10:
* 4 + 6 = 0 ⇒ “ − 4” = 6
· também: “ − 4” = −4 + 10
· note que: 10 ≡ 0 (mod 10)

ˆ Cifragem com chave secreta = 4:

– cifrar: somar 4 (mod 10)

– decifrar: somar 6 (mod 10)

Multiplicação modular

x 0 1 2 3 4 5 6 7 8 9
0 0 0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7 8 9
2 0 2 4 6 8 0 2 4 6 8
3 0 3 6 9 2 5 8 1 4 7
4 0 4 8 2 6 0 4 8 2 6
5 0 5 0 5 0 5 0 5 0 5
6 0 6 2 8 4 0 6 2 8 4
7 0 7 4 1 8 5 2 9 6 3
8 0 8 6 4 2 0 8 6 4 2
9 0 9 8 7 6 5 4 3 2 1

ˆ Multiplicação “mod n” é uma cifra:

– podemos “embaralhar” os dı́gitos multiplicando por k (mod n)

245
 ˆ Decifragem:

– efeito da multiplicação é desfeito com uma multiplicação pela inversa multiplicativa de k:

* k−1 é o número pelo qual se deve multiplicar k para obter 1
* k × k−1 = 1
– note que: x × k × k−1 = x × 1 = x

ˆ Funcionam como cifradores: ×3, ×5, ×7, ×9

– multiplicação por qualquer um dos outros não

– logo: é preciso escolher bem o “multiplicador”

ˆ Exemplo: k = 7 ⇒ k−1 = 3

– pois: 7 × 3 = 1 (mod 10)

– cifragem seria “×7” e decifragem seria “×3”

Fundamentos matemáticos (2): inversas multiplicativas

ˆ Definição: Zn = {0, 1, 2, . . . , n − 1}

ˆ Um elemento a de Zn tem inversa multiplicativa a−1 somente se mdc(a, n) = 1

– são os relativamente primos a n

ˆ O mdc entre dois valores a e b pode ser calculado pelo algoritmo de Euclides.

ˆ O valor de a−1 pode ser calculado eficientemente por uma extensão do algoritmo de Euclides.

ˆ Exemplo: Z9 = {0, 1, 2, 3, 4, 5, 6, 7, 8}

– Há 6 elementos inversı́veis: 1,2,4,5,7 e 8

* 4−1 = 7 porque 4 × 7 ≡ 1 (mod 9)
* 5−1 = 2 porque 5 × 2 ≡ 1 (mod 9)
– Diz-se que: quantidade de inversı́veis = 6 = φ(9)

ˆ Cálculo de inversas: Algoritmo de Euclides Estendido

Fundamentos matemáticos (3): Função φ(n) de Euler

ˆ φ(n) = qtde de inteiros a para os quais mdc(a, n) = 1

ˆ Teorema: se mdc(a, n) = 1, aφ(n) ≡ 1 (mod n)

ˆ Exemplo: Z10 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

– inversı́veis: {1, 3, 7, 9}
– de modo que: φ(10) = 4
– logo: 14 ≡ 34 ≡ 74 ≡ 94 ≡ 1 (mod 10)

246
 ˆ Exemplo: quais os 3 últimos dı́gitos de 7803 ?

– mesmo que trabalhar “mod 1000”

– então, como φ(1000) = 400, temos:
7803 = (7400 )2 × 73 ≡ (1) × 73 ≡ 343 (mod 1000)
– portanto, os 3 últimos dı́gitos são 343

Avaliação de φ(n)

ˆ Quantos números < n são relativamente primos a n?

– Se n é primo: φ(n) = n − 1
– Se n = p × q (produto de 2 primos):
φ(p × q) = (p − 1) × (q − 1)
– Exemplo: φ(10) = (2 − 1).(5 − 1) = 4

O sistema criptográfico RSA (1/5)

ˆ Cifrador em blocos

ˆ Computações são feitas “módulo n”

– n = p × q = produto de 2 números primos distintos

– “n” é um número muito grande

* |n| > 1024 bits (> 300 dı́gitos decimais)

– textos são números inteiros entre 0 e n − 1

ˆ Infelizmente: muito lento

– na prática: usado só na troca de chaves simétricas...

O sistema criptográfico RSA (2/5)

ˆ Cifrar: y = xe mod n

ˆ Decifrar: x = y d mod n

ˆ Configuração do sistema:

p e q são números primos (secretos)

n=p×q (público)
φ(n) = (p − 1).(q − 1) (secreto)
e tal que: mdc(e, φ(n)) = 1 (público)
−1
d≡e (mod φ(n)) (secreto)

247
O sistema criptográfico RSA (3/5)

ˆ Exemplo: Bob escolhe p = 3119 e q = 1571.

– Configurando:
* n = p × q = 5214149
* φ(n) = (3119 − 1).(1571 − 1) = 5209260

– Bob escolhe e = 3533 e calcula (Euclides):

* d = 3533−1 = 4034117 (mod 5209260) (privado)

– Bob publica em um diretório:

* e = 3533 e n = 5214149

O sistema criptográfico RSA (4/5)

ˆ Exemplo (cont.): {n = 5214149, e = 3533, d = 4034117}

– Para Alice enviar o texto 16597 para Bob, ela deve fazer:
* 165973533 mod 5214149 = 976827

– Do outro lado, Bob decifra usando o expoente d:

* 9768274034117 mod 5214149 = 16597

O sistema criptográfico RSA (5/5)

ˆ Como pode a decifragem ser o mesmo que a cifragem, mas com um expoente diferente??

ˆ Note que: e.d ≡ 1 (mod φ(n))

⇒ e.d = k.φ(n) + 1

ˆ então:
(xe )d ≡ xk.φ(n)+1 (mod n)
≡ (xφ(n) )k .x1 (mod n)
≡ (1)k .x (mod n)
≡ x (mod n) 2

ˆ Nota: tudo isto funciona também quando mdc(x, n) 6= 1

ˆ Neste caso, deve ocorrer: mdc(x, n) = p ou mdc(x, n) = q

ˆ Em ambos os casos, mostra-se que a análise anterior é válida utilizando-se o Teorema Chinês do
Resto

248
Implementação do RSA

ˆ Cifragem e decifragem:

– exponenciação módulo n com inteiros (muito) grandes

– exemplo: 97263533 mod 11413 = ??

ˆ Executar exponenciações e só depois “reduzir módulo n”:

– valores intermediários astronômicos!

ˆ A solução é explorar a propriedade:

(a × b) mod n = ((a mod n) × (b mod n)) mod n

ˆ Exemplo1: 117 mod 13 = ??

– pode ser calculado como: 19487171 mod 13

– ou então como: 11 .11 .114 ≡ 11.4.3 ≡ 132 ≡ 2 mod 13
1 2

– note que:
* 112 = 121 ≡ 4 mod 13
* 114 = 42 ≡ 3 mod 13

ˆ Exemplo2: computar 21234 mod 789

– Primeiro note que:

22 ≡ 4 (mod 789) → 24 ≡ 42 ≡ 16 (mod 789)
28 ≡ 162 ≡ 256 (mod 789) →216 ≡ 2562 ≡ 49 (mod 789)
232 ≡ 34 (mod 789) → 264 ≡ 367 (mod 789)
128
2 ≡ 559 (mod 789) → 2256 ≡ 37 (mod 789)
2512 ≡ 580 (mod 789) → 21024 ≡ 286 (mod 789)

– Em seguida note que: 1234 = (10011010010)2 = 1024 + 128 + 64 + 16 + 2

– De modo que: 21234 ≡ 286.559.367.49.4 ≡ 481 (mod 789)
– Note que não foi preciso trabalhar com números > 7882

Algoritmo “quadrado-e-multiplica”

ˆ O exemplo anterior ilustra a justificativa para o algoritmo abaixo.

ˆ Algoritmo para computar xb mod n:

z=1
for i=r-1 downto 0 do
z=z2 mod n
if bi =1 then z=z.x mod n

ˆ “r” é o nro de bits na representação binária de b

249
 ˆ Exemplo3: cálculo de 97263533 mod 11413:

3533 = (110111001101)2 ⇒ 12 bits ⇒ 20 multiplicações

i bi z
11 1 12 ×9726 = 9726
10 1 97262 ×9726 = 2659
9 0 26592 = 5634
8 1 56342 ×9726 = 9167
7 1 91672 ×9726 = 4958
6 1 49582 ×9726 = 7783
5 0 77832 = 6298
4 0 62982 = 4629
3 1 46292 ×9726 = 10185
2 1 101852 ×9726 = 105
1 0 1052 = 11025
2
0 1 11025 ×9726 = 5761

Leituras sugeridas sobre o RSA:

ˆ Ler Cormen2: seção 31.7

ˆ Ler Rosen6: seção 3.7

250