Notes and coins

No sentido de tentar resolver o problema de distribui¸c˜ao de chaves imposto pela criptografia sim´etrica(distribui¸c˜ao da chave secreta atrav´es de um ca- nal inseguro), surgiu no fim dos anos 70 um novo esquema criptogr´afico, conhecido por criptografia assim´etrica ou de chave p´ublica. Este tipo de criptografia, como foi mencionado, possui um maior peso computacional na codifica¸c˜ao/descodifica¸c˜ao da informa¸c˜ao. Al´em disso, possui tamb´em uma ‘filosofia” diferente de utiliza¸c˜ao. ´E neste tipo de criptografia que os computa- dores quˆanticos provocam um maior impacto1, comprometendo a seguran¸ca de quase todos os esquemas criptogr´aficos assim´etricos. Nestes, cada inter- veniente tem um par de chaves respectivamente, p´ublica e privada. A chave p´ublica ´e pass´ıvel de ser transmitida em aberto, podendo com ela qualquer pessoa cifrar informa¸c˜ao que apenas o detentor da chave privada pode des- codificar.

Este tipo de criptografia assenta em conven¸c˜oes profundamente enraizadas na dificuldade de resolver problemas matem´aticos, no atual modelo com- putacional sem o conhecimento de todas as vari´aveis do problema. Como exemplo, e atendendo ao futuro caso pr´atico por n´os demonstrado, vamos considerar o problema de fatoriza¸c˜ao de dois n´umeros primos muito grandes (sensivelmente 1024 bits cada):

1. Sejam P e Q, dois n´umeros primos de grande dimens˜ao, e PQ o respec- tivo resultado da multiplica¸c˜ao.

2. Descartando P e Q, apenas estando na posse de PQ, queremos saber quais os fatores que lhe deram origem. isto ´e PQ.

Apesar do enunciado inocente, facilmente percebemos que o problema ´e com- plexo na medida em que a dimens˜ao dos n´umeros escapa “`as nossas m˜aos”. Este problema matem´atico, est´a no cerne de um dos mais bem sucedidos esquemas criptogr´aficos de chave p´ublica, o RSA.

Voltando por agora `a generalidade das cifras assim´etricas e por forma a man- ter a coerˆencia com a apresenta¸c˜ao da cifras sim´etricas, vamos apresentar os principais pontos fortes e fracos desta.

• + N˜ao ´e necess´ario os dois intervenientes chegarem a acordo sobre a chave secreta a usar.

• + Possibilita autentica¸c˜ao e o n˜ao repudio das mensagens. • – ´E necess´aria a valida¸c˜ao da autenticidade nas mensagens.

• – Custo acrescido na codifica¸c˜ao/descodifica¸c˜ao de informa¸c˜ao.

Posto isto, avan¸caremos ent˜ao para um exemplo concreto, o RSA, onde perceberemos como os algoritmos quˆanticos por n´os estudados, comprometem a seguran¸ca desta cifra.

6.2.1 Exemplo - RSA

Criado em 1978 por trˆes investigadores do MIT, nomeadamente, Rivest, Sha- mir e Adlemen, Rivest et al. [1978], o RSA veio a torna-se num dos principais esquemas criptogr´aficos em uso no mundo inteiro. Como foi referido baseia- se num sistema de chaves p´ublica/privada. Entre estas existem as seguintes dependˆencias

1. Informa¸c˜ao codificada com a chave p´ublica pode apenas ser lida com a correspondente chave privada.

2. Informa¸c˜ao codificada com a chave privada apenas pode ser lida pela chave publica.

3. N˜ao existe uma rela¸c˜ao ´obvia entre as duas no sentido de, a partir da chave p´ublica ser poss´ıvel chegar `a chave privada em tempo polinomial. Devido ao grande custo computacional dos processos inerentes a este tipo de codifica¸c˜ao/descodifica¸c˜ao de informa¸c˜ao, que analisaremos de seguida, este tipo de esquema ´e normalmente usado em simbiose com criptografia sim´etrica. A ideia ´e proteger por exemplo com uma cifra RSA, o acordo de chave, procedendo de seguida a ”conversa¸c˜ao” com a chave acordada, recor- rendo a criptografia sim´etrica.

Vamos agora proceder a an´alise do algoritmo RSA. Para uma melhor le- gibilidade, vamos construir um pequeno exemplo de utiliza¸c˜ao. Com esta abordagem, procuramos clarificar o ponto onde algoritmo de Shor interv´em, permitindo-nos quebrar a cifra.

1. Sejam P e Q dois n´umeros primos de grande dimens˜ao (100 d´ıgitos cada um). Para ilustrar o nosso exemplo, vamos escolher dos n´umeros mais pequenos, P = 61 e Q = 53.

2. Em seguida calculamos o produto PQ = 3233. Este valor ´e do conhe- cimento p´ublico. Este valor ser´a o coeficiente modular das opera¸c˜oes a realizar.

3. Seja E a chave p´ublica. Para escolha da mesma, o algoritmo garante, E ≤ PQ, E ´e impar e n˜ao possui fatores comuns com (P-1)(Q-1). 4. Vamos admitir E = 17. A chave p´ublica ´e ent˜ao o par (PQ,E)

5. Seja D a chave privada. O seu c´alculo ´e dado pelo c´alculo da in- versa multiplicativa da chave p´ublica E, m´odulo PQ isto ´e, DE = 1 mod((P-1)(Q-1)). D = 2753.

Neste momento estamos na posse do par chave p´ublica, (E,PQ) e chave privada D que devemos guardar em absoluto sigilo. Vamos analisar agora as fun¸c˜ao de codifica¸c˜ao/descodifica¸c˜ao. Come¸cando pela codifica¸c˜ao, a sua fun¸c˜ao ´e dada por,

C(T ) = TE mod P Q, (6.1)

onde T ´e a informa¸c˜ao a cifrar. Voltando ao nosso exemplo, e considerando T = 123, obtemos,

C(123) = 12317 mod 3233 = 855 (6.2)

Por outro lado a fun¸c˜ao de descodifica¸c˜ao ´e dada por,

C−1(V ) = VD mod P Q, (6.3)

no nosso exemplo, V ´e a informa¸c˜ao cifrada, recebida pelo portador da chave privada. Substituindo a mesma na fun¸c˜ao de decifra¸c˜ao, obtemos rapida- mente a informa¸c˜ao,

C−1(855) = 8552753 mod 3233 ≡ 123. (6.4) Devido as opera¸c˜oes matem´aticas envolvidas obter, D,P, Q, apenas com o conhecimento de PQ e E ´e considerado dif´ıcil. Relembrando a f´ormula de calcular a chave privada, exposta no ponto 5 concretamente,

DE = 1 mod (P − 1)(Q − 1), (6.5)

percebemos que um atacante na posse de E, PQ e com recurso a um com- putador quˆantico, a correr o algoritmo de Shor por n´os estudado, consegue fatorizar PQ nos seus dois fatores P e Q. Isto em tempo polinomial. O atacante consegue ent˜ao deduzir a chave privada a partir da informa¸c˜ao da chave publica.

De facto, a maior parte dos esquemas criptogr´aficos baseados em cripto- grafia de chave p´ublica s˜ao sustentados por problemas matem´aticos de dif´ıcil resolu¸c˜ao, a n˜ao ser que se conhe¸cam todas as vari´aveis inerentes ao mesmo. Este conhecimento ´e por vezes referido na literatura como al¸cap˜ao/porta tra- seira2 das fun¸c˜oes de codifica¸c˜ao/descodifica¸c˜ao. Quem n˜ao as conhece, n˜ao consegue computar a fun¸c˜ao em tempo ´util. Outro exemplo deste tipo de constru¸c˜ao, s˜ao problemas baseados no logaritmo discreto3. Como exemplo temos a cifra El Gamal, o acordo de chaves Diffie-Hellman(Anexo C.1) ou as

2

do inglˆes trap doors.

assinaturas digitais. Ou seja, atendendo ao volume de informa¸c˜ao mundial, que se encontra protegido por estas cifras (o que passa por todos os setores da sociedade moderna), a constru¸c˜ao de um computador quˆantico com capa- cidade para correr estes algoritmos, provoca alguma apreens˜ao `a comunidade criptogr´afica bem como a sociedade.

Nos pr´oximas se¸c˜oes deste cap´ıtulo, analisaremos tanto a resposta desta comunidade ao aparecimento deste algoritmos, como propostas da pr´opria computa¸c˜ao quˆantica no design de esquemas criptogr´aficos mais seguros