Aula04 - RSA

Gestão de Segurança da Informação

•

USP-BR

0

murilo041092

14/04/2024

E aí, curtiu este material?

Ajude a incentivar outros estudantes a melhorar o conteúdo

Gostou desse material? Compartilhe! 🧡

Gestão de Segurança da Informação

13.459 Materiais compartilhados

Baixe o app para aproveitar ainda mais

Leia os materiais offline, sem usar a internet. Além de vários outros recursos!

Prévia do material em texto

Aula 04 - RSA
(Stallings, Capı́tulo 8 e 9)
1
Cifras Simétricas vs Cifras Assimétricas
Cifras Simétricas: única chave utilizada na criptografia e decrip-
tografia
C “ EpM,Kq eM “ DpC,Kq
Cifras Assimétricas: chaves diferentes utilizadas na criptografia
e decriptografia
C “ EpM,KEq eM “ DpC,KDq
2
Confidencialidade: Criptografia Assimétrica
Enc - E Dec - D
c
A
KPU KPR
S
m m
R
‚ Adversário não conhece KPR, mas conhece KPU
‚ c “ Epm,KPUq em “ Dpc,KPRq, isto é,m “ DpEpm,KPUq,KPRq
‚ E e D são fáceis de calcular (complexidade polinomial)
3
‚ dados E, D, c e KPU (KPR desconhecido) é difı́cil (ideal-
mente complexidade exponencial) calcular m
Cifras de Chave Pública
4
Cifras de Chave Pública
Etapas:
1. cada usuário gera par de chaves para criptografia e decrip-
tografia das mensagens
2. cada usuário disponibiliza publicamente a chave pública
KPU (registro público, inı́cio da troca de mensagens, ar-
quivo em comum, etc.)
3. cada usuário mantem a chave privada KPR apenas de seu
conhecimento
4. se Bob deseja enviar uma mensagem para Alice, Bob crip-
tografa a mensagem com a chave pública de Alice
5. Alice decriptografa a mensagem usando sua chave privada
6. outros usuários não podem decriptografar a mensagem,
apenas Alice
5
Aplicações de Chave Pública
Criptografia/decriptografia: emissor criptografa uma mensa-
gem com a chave pública do destinatário
Assinatura Digital: o emissor assina uma mensagem com sua
chave privada ao criptografar um texto conhecido pelo receptor
Troca de chave: os dois lados cooperam para trocar uma chave
simétrica de sessão
6
Requisitos de Chave Pública
Definidos por Diffie e Hellman
1. ser computacionalmente fácil para uma parte B gerar um
par (chave pública KPUb, chave privada KPRb).
2. ser computacionalmente fácil para um emissor A encriptar
uma mensagem, isto é, computar
C “ EpM,KPUbq
3. ser computacionalmente fácil para o receptor B decripto-
grafar um texto cifrado, isto é, computar
M “ DpC,KPRbq “ DpEpM,KPUbq,KPRbq
7
4. ser computacionalmente inviável para um adversário deter-
minar a chave privada KPRb apenas conhecendo a chave
pública KPUb e as funções Dp¨q e Ep¨q
5. ser computacionalmente inviável para um adversário de-
terminar o texto aberto M apenas conhecendo a chave
pública KPUb e as funções Dp¨q e Ep¨q
6. as duas chaves podem ser aplicadas em qualquer ordem
M “ DpEpM,KPUbq,KPRbq “ DpEpM,KPRbq,KPUbq
RSA - Rivest-Shamir-Adleman
Geração de Chaves
‚ Selecione p e q primos e p ‰ q
‚ Calcule n “ pˆ q
‚ φpnq “ pp´ 1q ˆ pq ´ 1q, φpnq é o de tociente de n
‚ Selecione o inteiro e, tal que 1 ă e ă φpnq eMDCpφpnq, eq “
1, isto é, tociente de n e e são relativamente primos
‚ Calcule d “ e´1 mod φpnq
‚ Chave pública: KPU “ te, nu
‚ Chave privada: KPR “ td, nu
8
Propriedade
‚ se M ă n, então Med mod n “M
Criptografia
‚ Texto claro é um número M ă n
‚ Texto cifrado é calculado por C “Me mod n
Decriptografia
‚ Texto cifrado é um número C ă n
‚ Texto claro é obtido por M “ Cd mod n
Exercı́cio
Escolha dois números primos pequenos p e q
Calcule n “ pˆ q
Calcule o tociente φpnq “ pp´ 1q ˆ pq ´ 1q
Escolha e tal que 1 ă e ă φpnq e MDCpφpnq, eq “ 1
Calcule d “ e´1 mod φpnq
Escolha um número (mensagem) aberto M ă n
Calcule o número (mensagem) cifrado C “Me mod n
Teste se M “ Cd mod n
9
Prova - Med mod n “M
Definição: a função tociente de Euler φpnq é definida como o
número de inteiros positivos menores que n e relativamente pri-
mos de n.
Propriedade 1: se p é primo, então φppq “ p´ 1
Propriedade 2: se p e q são primos e p ‰ q, então φppqq “
pp´ 1qpq ´ 1q
10
Prova - Med mod n “M
Teorema de Euler: seja a e n relativamente primos, então
aφpnq mod n “ 1
Prova: considere o conjunto ordenado R dos inteiros positivos
menores que n e relativamente primos de n e rotule-os da se-
guinte forma:
R “ tx1, x2, . . . , xφpnqu.
Construa também o conjunto ordenado S da seguinte forma:
S “ tpax1 mod nq, pax2 mod nq, . . . , paxφpnq mod nqu
Temos que S é uma permutação de R, pois:
11
1. axi mod n é relativamente primo de n e todos elementos
em S são menor que n e relativamente primo de n.
2. Não existem duplicatas em S, pois se axi mod n “ axj
mod n, então xi “ xj.
Então temos:
śφpnq
i“1 paxi mod nq “
śφpnq
i“1 xi
p
śφpnq
i“1 axi mod nq mod n “
śφpnq
i“1 xi mod n
aφpnq
śφpnq
i“1 xi mod n “
śφpnq
i“1 xi mod n
aφpnq mod n “ 1 mod n
Corolário: seja a e n relativamente primos, então
ax mod n “ apx mod φpnqq mod n.
Prova - Med mod n “M
Caso 1: M e n são relativamente primos. Temos:
Med mod n “ M ped mod φpnqq mod n
“ M1 mod n “M
Caso 2: M e n não são relativamente primos, então M P
t0,1p,2p, . . . , pq´1qp,1q,2q, . . . , pp´1qqu. O caso M “ 0 é
trivial, considere o caso M “ xp. Temos:
pMed ´Mq “ pxpqed ´ pxpq
ppxpqed ´ pxpqq mod q “
ppxpqpedq mod φpqq mod q ´ xp mod qq mod q “
ppxpq1 mod q ´ xp mod qq mod q “ 0
ppxpqed ´ pxpqq mod p “ 0
ppxpqed ´ pxpqq “ kpq ô pMed ´Mq mod n “ 0
12
Implementação
Requisitos:
‚ Ser possı́vel encontrar valores de e, d, n tais queMed mod n “
M para todo M ă n
‚ Ser relativamente fácil calcular Me mod n e Cd mod n
para todo M,C ă n
‚ Ser inviável determinar d dados e e n
Chaves:
13
‚ p, q são dois números primos (privados e escolhidos)
‚ n “ pq (público e calculado)
‚ e com MDCpφpnq, eq “ 1 e 1 ă e ă φpnq (público e
escolhido)
‚ d “ e´1 mod φpnq (privado e calculado)
Exercı́cio
1. Considere que se deseje criptografar textos com 8 bits. De-
termine um par de chaves pública e privada para criptogra-
far tais textos.
2. Considere que você intercepte a seguinte chave pública de
um servidor e “ 77, n “ 1829 e uma mensagem encrip-
tada C “ 56 utilizando tal chave.
(a) Determine a chave privada do servidor.
(b) Determine o texto claro M .
14
Implementação - Exponenciação
Como calcular ab mod n?
Técnica Ingênua: multiplique a b vezes e depois tire o módulo
aˆ aˆ aˆ . . .ˆ aˆ a mod n.
Problemas: valor pode ficar muito grande e é muito lento.
Técnica Ingênua com módulo: multiplique a b vezes, mas tire o
módulo após cada multiplicação paˆ a mod nˆ a mod nˆ
. . .ˆ a mod nˆ a mod nq.
Problema: é muito lento.
Exponenciação com Representação Binária: considere o exem-
plo x11 mod n
15
1. pode-se representar x11 mod n “ x8`2`1 mod n “
ppx8 mod nq ˆ px2 mod nq ˆ px1 mod nqq mod n
2. pode-se obter x2
n
realizando nmultiplicações: x2
0
“ x1 “
x e x2
n
“ x2
n´1
ˆ x2
n´1
mod n
3. se expressarmos b como um número binário bkbk´1 . . . b0,
temos:
b “
k
ÿ
i“1
bi2
i ab “ a
řk
i“1 bi2
i
“
k
ź
i“1
abi2
i
ab mod n “
«
k
ź
i“1
abi2
i
ff
mod n “
˜
k
ź
i“1
”
abi2
i
mod n
ı
¸
mod n
Implementação - Exponenciação
EXPONENCIACAO(a,b,n)
1. cÐ 0
2. fÐ 1
3. kÐ tlog(b)u
4. for i=k:-1:0
5. cÐ 2 ˆ c
6. fÐ f ˆ f mod n
7. if bi = 1
8. cÐ c ` 1
9. fÐ f ˆ a mod n
16
Implementação - Números Primos
Para escolher as chaves, precisamos escolher números primos
p e q
Solução Ingênua: dado um candidato ı́mpar a número primo n,
testa para todo 1 ă a ă
?
n se n mod a “ 0
Solução Miller-Rabin: considera propriedade de números pri-
mos para realizar o teste de primalidade e executa o teste várias
vezes.
Resultado 1: a probabilidade de que um número não primo
passe no teste é menor que 1
4
Resultado 2: em média lnN
2 testes são necessários para en-
contrar um primo próximo a N
17
Implementação - Números Primos
Propriedades (Miller-Rabin):
1. Qualquer inteiro positivo ı́mpar n ě 3 pode ser expresso
da seguinte forma:
n “ 2kq ` 1, com k ą 0, q ı́mpar
2. Se n é primo e 0 ă a ă n, então a2 mod n “ 1 se e
somente se:
a mod n “ 1 ou a mod n “ n´ 1
3. Se n é primo e 1 ă a ă n ´ 1, então uma das duas
condições é verdadeira:
18
(a) aq mod n “ 1
(b) um dos números aq, a2q, a4q, . . . , a2
k´1q tem módulo
em n igual a n´ 1
Implementação - Números PrimosTEST-PRIMO(n,k,q)
1. selecione um inteiro aleatório a, tal que 1<a<n-1
2. if aq mod n=1 então return inconclusivo
3. for j=0 até k-1 faça
4. if a2
jq mod n=n-1 então return inconclusivo
5. return composto
19
GF ppq - Inverso Multiplicativo
Como obter o inverso multiplicativo sem construir toda a tabela
para multiplicação?
‚ algoritmo de Euclides encontra o MDC (Máximo Divisor Co-
mum) entre dois inteiros positivos, e usa a seguinte propri-
edade:
MDCpa, bq “MDCpb, amod bq
‚ algoritmo de Euclides Estendido encontra o Inverso Multi-
plicativo
‚ se MDCpm, bq “ 1 (m e b são relativamente primos),
então b tem um inverso multiplicativo
20
GF ppq - Algoritmo de Euclides
EUCLIDES-MDC(a,b) : a>b>0
1. AÐ a
2. BÐ b
3. if B=0 return MDC(a,b)=A
4. RÐ A mod B
5. AÐ B
6. BÐ R
7. goto 3
21
GF ppq - Algoritmo de Euclides
Exemplo: calcule MDC(1234,432)?
22
GF ppq - Algoritmo de Euclides Estendido
EUCLIDES-ESTENDIDO(m,b) : m>b>0
1. (A1,A2,A3)Ð (1,0,m)
2. (B1,B2,B3)Ð (0,1,b)
3. if B3=0 return MDC(m,b)=A3 e não existe inverso
4. if B3=1 return MDC(m,b)=B3 e b´1mod m=B2
5. QÐ
X
A3
B3
\
6. (T1,T2,T3)Ð (A1-QˆB1,A2-QˆB2,A3-QˆB3)
7. (A1,A2,A3)Ð (B1,B2,B3)
8. (B1,B2,B3)Ð (T1,T2,T3)
9. goto 3
23
GF ppq - Algoritmo de Euclides Estendido
Exemplo: calcule inverso multiplicativo de 1234 mod 1237?
24
Implementação - Relativamente Primos
Solução: escolha um número aleatório e utilize o algoritmo de
Euclides para testar se é relativamente primo.
Resultado: a probabilidade de que dois números aleatórios se-
jam relativamente primos é 0,6.
25