Teoria dos Números Unesp - III Bienal da SBM IME-UFG - 2006

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

CampusdeSãoJosédoRioPreto
Introduc¸a˜o a` Teoria dos Nu´meros
com Aplicac¸o˜es em Criptografia
Rafael Lucas de Arruda (rafaa @hotmail.com)
Orientador: Je´fferson Luiz Rocha Bastos (jeferson@ibilce.unesp.br)
IIIBienaldaSBM-IME/UFG-2006
1 Introduc¸a˜o
O termo Criptografia surgiu da fusa˜o das palavras gregas “krypto´s”
e “gra´phein”, que significam “oculto” e “escrever”, respectivamente.
Trata-se de um conjunto de conceitos e te´cnicas que visa codificar uma
informac¸a˜o de forma que somente o emissor e o receptor possam acessa´-la,
evitando que um intruso consiga intercepta´-la.
Com o avanc¸o da tecnologia e sua facilidade de entregar informac¸o˜es
de maneira precisa e extremamente ra´pida, a criptografia tornou-se uma
ferramenta fundamental para permitir que apenas o emissor e o receptor
tenham acesso livre a` informac¸a˜o trabalhada.
2 Introduc¸a˜o a` Teoria dos Nu´meros
2.1 Divisibilidade
Definic¸a˜o 2.1 Sejam a, b ∈ Z. Dizemos que a divide b, denotando
por a | b, se existir k ∈ Z tal que b = ak.
Se a na˜o divide b denotamos a - b.
Teorema 2.1 (Algoritmo da Divisa˜o)Dados a, b ∈ Z, b 6= 0,
existe um u´nico par de inteiros q e r tais que
a = bq + r, com 0 ≤ r < |b| (r = 0⇔ b | a)
(q e´ chamado de quociente e r de resto da divisa˜o de a por b).
Definic¸a˜o 2.2 (Ma´ximo Divisor Comum)O ma´ximo divisor
comum de dois nu´meros a, b ∈ Z, denotado por mdc(a, b), e´ o maior
inteiro que divide a e b.
Teorema 2.2 (Algoritmo Euclidiano) Sejam a, b ∈ Z+, n 6=
0, a ≥ b. Se o algoritmo da divisa˜o for aplicado sucessivamente para
se obter
rj−2 = rj−1qj + rj, 0 ≤ rj < rj−1
para j = 0, 1, 2, · · · , n e rn = 0 enta˜o mdc(a, b) = rn−1, o u´ltimo
resto na˜o nulo.
2.2 Nu´meros Primos
Teorema 2.3 (Teorema da fatorac¸a˜o u´nica)Dado um inteiro
positivo n ≥ 2 podemos sempre escreveˆ-lo, de modo u´nico, na forma
n = pe11 . . . p
ek
k ,
onde pi : primos distintos, 1 < p1 < p2 < p3 < · · · < pk e e1, . . . , ek
sa˜o inteiros positivos.
Proposic¸a˜o 2.1 Sejam a, b, c ∈ Z e suponhamos que mdc(a, b) = 1.
1. Se b | ac enta˜o b | c
2. Se a | c e b | c enta˜o ab | c
2.3 Congrueˆncias
Definic¸a˜o 2.3 Seja m um inteiro fixo na˜o-nulo. Dizemos que os
inteiros a e b sa˜o congruentes mo´dulo m, se m dividir a diferenc¸a
(a− b). Nesse caso escrevemos
a ≡ b (mod m).
Teorema 2.4 (Pequeno Teorema de Fermat) Seja p um
nu´mero primo. Se p - a enta˜o ap−1 ≡ 1 (mod p).
Teorema 2.5 (Teorema Chineˆs do Resto) Sejam
m1,m2, . . . ,mr nu´meros inteiros positivos tais que mdc(mi,mj) = 1,
sempre que i 6= j. Enta˜o, o sistema de congrueˆncias
x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
...
x ≡ ar (mod mr)
admite u´nica soluc¸a˜o em Zm1·m2...mr.
Definic¸a˜o 2.4 (Func¸a˜o φ de Euler ou Func¸a˜o Totiente)
Seja n ∈ Z+. A func¸a˜o φ de Euler, denotada por φ(n), e´ definida
como sendo o nu´mero de inteiros positivos menores ou iguais a n
que sa˜o relativamente primos com n.
Teorema 2.6 Seja n ∈ Z+ de fatorac¸a˜o
n = pe11 . . . p
ek
k .
Enta˜o, a fo´rmula geral para o ca´lculo de φ(n) e´ dada pela expressa˜o
pe1−11 (p1 − 1) . . . pek−1k (pk − 1).
3 Cifras
A cifra de substituic¸a˜o e´ um me´todo de codificac¸a˜o no qual as letras orig-
inais do texto original, tratadas individualmente ou em grupos de com-
primento constante, sa˜o substitu´ıdas por outras letras, figuras, s´ımbolos
ou uma combinac¸a˜o destes de acordo com um sistema predefinido e uma
chave.
Veremos aqui, um exemplo simples de cifragem que consiste em usar
uma congrueˆncia para codificar uma mensagem. Suponhamos que
queiramos codificar a palavra Estudante. Primeiro, devemos converter
letras em nu´meros usando a seguinte tabela:
A B C D E F G H I J K L M
0 1 2 3 4 5 6 7 8 9 10 11 12
N O P Q R S T U V W X Y Z
13 14 15 16 17 18 19 20 21 22 23 24 25
Assim, obtemos a sequ¨eˆncia nume´rica
4− 18− 19− 20− 3− 0− 13− 19− 4.
Onde cada nu´mero corresponde a um bloco b da mensagem a ser codi-
ficada.
Para codificar a mensagem usaremos uma congrueˆncia do tipo
ab ≡ c (mod 26)
onde c e´ o bloco codificado. Devemos escolher um valor para a de tal
modo que mdc(a, 26) = 1. Em nosso exemplo escolhemos a = 3.
Tomando b = 18, temos 3 ·18 ≡ 2 (mod 26). Ou seja, c = 2. Efetuando
todos os ca´lculos, obtemos a sequ¨eˆncia de nu´meros
12− 2− 5− 8− 9− 0− 13− 5− 12,
que corresponde a mensagem codificada MCFIJANFM.
Para decodificarmos a mensagem basta usarmos a congrueˆncia
x ≡ 9b (mod 26).
Isto porque 9 e´ o inverso de 3 em Z26.
4 Criptografia RSA
4.1 Pre´-codificac¸a˜o
Na pre´-codificac¸a˜o convertemos a mensagem em nu´meros, usando a
seguinte tabela:
A B C D E F G H I J K L M
10 11 12 13 14 15 16 17 18 19 20 21 22
N O P Q R S T U V W X Y Z
23 24 25 26 27 28 29 30 31 32 33 34 35
Para identificarmos o espac¸o entre duas palavras, utilizaremos o nu´mero
99. Por exemplo, a mensagem Paraty e´ linda corresponde ao nu´mero
2510271029349914992118231310
Precisamos determinar os paraˆmetros do sistema RSA que vamos usar.
Estes paraˆmetros sa˜o os dois primos distintos, que denotaremos por p e q.
Fac¸amos n = p · q. A u´ltima fase do processo de pre´-codificac¸a˜o consiste
em quebrar em blocos menores que n o nu´mero produzido anteriormente.
Escolhendo p = 11 e q = 13 temos n = 11 ·13. Neste caso, a mensagem
convertida acima pode ser quebrada nos seguintes blocos:
25 - 102 - 7 - 102 - 93 - 49 - 91 - 49 - 92 - 118 - 23 - 13 - 10.
4.2 Codificando
Precisamos determinar e ∈ Z+ que seja invers´ıvel mo´dulo φ(n). Ou
seja, mdc(e, φ(n)) = 1. Para o ca´lculo de φ(n) fazemos
φ(n) = (p− 1)(q − 1).
Chamamos o par (n, e) de chave de codificac¸a˜o do sistema RSA.
No exemplo que estamos considerando, temos φ(143) = (11 − 1)(13 −
1) = 120. Vamos escolher e = 7, que e´ o menor nu´mero primo com 120.
Agora, temos que codificar os blocos obtidos anteriormente. Cada um
separadamente. Denotaremos o bloco b codificado por C(b). A expressa˜o
para se calcular C(b) e´ a seguinte:
be ≡ C(b) (mod n) (1)
Em termos de aritme´tica modular,C(b) e´ a forma reduzida de bemo´dulo
n.
Desta maneira, o bloco 102 da mensagem e´ codificado como o resto da
divisa˜o de 1027 por 143. Fazendo as contas:
1027 ≡ (−47)7 ≡ −477 ≡ −81 · 138 ≡ −24 ≡ 119 (mod 143).
Logo, C(102) = 119.
Codificando toda a mensagem, obtemos a seguinte sequ¨eˆncia de blocos:
64 - 119 - 6 - 119 - 102 - 36 - 130 - 36 - 27 - 79 - 23 - 117 - 10
Esta sequ¨eˆncia de nu´meros e´ a mensagem codificada.
4.3 Decodificando
Para decodificarmos um bloco da mensagem codificada, precisamos de n
e o inverso de e em φ(n), que denotaremos por d. Chamamos o par (n, d)
de chave de decodificac¸a˜o. Seja a um bloco da mensagem codificada,
denotaremos porD(a) o bloco decodificado. A expressa˜o para se calcular
D(a) e´ a seguinte:
ad ≡ D(a) (mod n) (2)
Em termos de aritme´tica modular, D(a) e´ a forma reduzida de ad
mo´dulo n.
Para calcularmos d, devemos aplicar a identidade de Bezout a e e φ(n).
No exemplo que estamos considerando, temos que φ(143) = 120 e e = 7.
Dividindo φ(143) = 120 por e = 7 obtemos
120 = 7 · 17 + 1⇔ 1 = 120 + (−17) · 7
Como −17 ≡ 103 (mod 120) temos que d = 103. Assim, para de-
codificarmos o bloco 119 da mensagem codificada, calculamos 119103 ≡
D(119) (mod 143).
Observe que os ca´lculos a serem efetuados para a decodificac¸a˜o sa˜o muito
maiores que o da codificac¸a˜o. Isso impede que um invasor do sistema de-
codifique a mensagem secreta. Pore´m, a seguranc¸a da criptografia RSA
e´ outra. Esta consiste no fato de se fatorar n em fatores primos. No
nosso exemplo, sabemos que n = 143 = 11 · 13 = p · q. Logo, pode-
mos fazer uso do Teorema Chineˆs do Resto para resolver a congrueˆncia
119103 ≡ D(119) (mod 143):{
119103 ≡ a (mod 11)
119103 ≡ b (mod 13)
Aplicando o Teorema de Fermat a cada um destes primos, temos que{
119103 ≡ (11910)10 · 1193 ≡ 1 · 1193 ≡ 3 (mod 11)
119103 ≡ (11912)8 · 1197 ≡ 1
· 1197 ≡ 11 (mod 13)
Chamemos x = 119103. Ficamos com o sistema{
x ≡ 3 (mod 11)
x ≡ 11 (mod 13)
Da segunda equac¸a˜o temos x = 11 + 13 · q1, q1 ∈ Z. Substituindo na
primeira equac¸a˜o, ficamos com 11 + 13 · q1 ≡ 3 (mod 11) ⇔ 13 · q1 ≡
−8 (mod 11). Utilizando a identidade de Bezout para os nu´meros 13 e
11, descobrimos que o inverso de 13 em Z11 e´ −5. Desta forma,
(−5) · 13 · q1 ≡ 1 · q1 ≡ (−5) · (−8) ≡ 40 ≡ 7 (mod 11)
Ou seja, q1 = 7 + 11 · q2, q2 ∈ Z.
Assim, x = 11 + 13 · (7 + 11 · q2) = 102 + 143 · q2. Mas isto significa
que x ≡ 102 (mod 143). Portanto,
119103 ≡ 102 (mod 143)
4.4 Como Funciona?
Vamos mostrar que ao decodificarmos um bloco codificado, obteremos
de volta o bloco correspondente da mensagem original.
Precisamos verificar que se b ∈ Z e 1 ≤ b ≤ n− 1 enta˜o D(C(b)) = b.
Na verdade, vamos provar que D(C(b)) ≡ b (mod n). Note que a con-
grueˆncia so´ sera´ verificada seD(C(b)) = b, pois 1 ≤ D(C(b)), b ≤ n−1.
E´ por isso que na pre´-codificac¸a˜o “quebramos” a mensagem em blocos
menores que n e os mantemos separados mesmo apo´s a codificac¸a˜o.
Pela definic¸a˜o de D e C temos que
D(C(b)) ≡ (be)d ≡ bed (mod n)
Como d e´ o inverso de e mo´dulo φ(n), enta˜o
ed = 1 + k · φ(n) = 1 + k · (p− 1)(q − 1), k ∈ Z (3)
Lembremos que n = p · q, onde p, q: primos distintos. Calcularemos a
forma reduzida de bed mo´dulo p e mo´dulo q. Vejamos a forma reduzida
de bed mo´dulo p.
De (3) temos que
bed ≡ b · (bp−1)k(q−1) (mod p) (4)
Usaremos o teorema de Fermat. Para isto, vamos supor que p - b. Enta˜o
bp−1 ≡ 1 (mod p). E assim obtemos bed ≡ b (mod p).
Para o caso em que p | b temos b ≡ 0 (mod p). O fato de p ser primo
nos garante que bed ≡ b (mod p).
Analogamente, mostramos que bed ≡ b (mod q). Assim sendo, temos
que p | (bed − b) e q | (bed − b). Como p e q sa˜o primos distintos, temos
que mdc(p, q) = 1 e isto implica que pq | (bed − b). Mas n = p · q e
portanto bed ≡ b (mod n), ∀b ∈ Z. Disto, conclu´ımos que
D(C(b)) ≡ b (mod n).
Logo, D(C(b)) = b.
4.5 A Seguranc¸a do RSA
O RSA e´ um me´todo de chave pu´blica. A chave de codificac¸a˜o cor-
responde a` chave pu´blica do sistema. Assim, o par (n, e) e´ acess´ıvel a
qualquer usua´rio. O me´todo de codificac¸a˜o RSA so´ sera´ seguro se for
dif´ıcil calcular d quando apenas n e e sa˜o conhecidos.
Para calcularmos d precisar´ıamos aplicar o algoritmo euclidiano esten-
dido a φ(n) e e. Pore´m, para calcularmos φ(n) ter´ıamos que fatorar n
para obtermos p e q. Portanto, na pra´tica, so´ podemos quebrar o co´digo
se conseguirmos fatorar n. Mas, fatorar n com 150 algarismo ou mais,
pode ser um trabalho um tanto dif´ıcil ja´ que na˜o disponibilizamos de
algoritmos ra´pidos de fatorac¸a˜o.
5 Refereˆncias Bibliogra´ficas
[1] COUTINHO, S. C. Nu´meros inteiros e criptografia RSA. Segunda
Edic¸a˜o. Rio de Janeiro: IMPA/SBM, 2000.
[2] SANTOS, Jose´ Pl´ınio de Oliveira. Introduc¸a˜o a` Teoria dos
Nu´meros. Segunda Edic¸a˜o. Rio de Janeiro: IMPA, CNPq, 2000.
6 Apoio
ARRUDA, Rafael Lucas de. Introduc¸a˜o a` Teoria dos Nu´meros com Aplicac¸o˜es em Criptografia. Bolsista PET/SESu. Orientador: Je´fferson Luiz Rocha Bastos.