Uma Muito Breve Introduc˘~ao a Criptografia

Cifras Classicas Enigma RSA Bibliografia

Uma Muito Breve Introducaoa Criptografia

Antonio Machiavelo

Departamento de Matematica da FCUPCentro de Matematica da Universidade do Porto

27/2/2013

Antonio Machiavelo Uma Muito Breve Introducao a Criptografia


Cifras mono-alfabeticas

Uma chave

ABCD E F GH I J K L MNOPQR S TU V W X YZH I TOGB J NSCAQ Z D Y U E XV F KM L WPR

CRIPTOGRAFIA TXSUFYJXHBSHNYCG HOJE

Ha

26× 25× · · · × 3× 2× 1 = 403 291 461 126 605 635 584 000 000

' 4× 1026

chaves distintas para a cifra de substituicao.



Cripto-analise

Testando 1 milhao de chaves por segundo...

... demorar-se-ia mais de 6.39× 1012 anos a tester metade das

chaves!

Idade do Universo (desde o Big Bang)

... “apenas” cerca de 1.37× 1010 anos.



Um criptograma

IOINE PQNPV ITEIT NQEBP TDUIQ NQEBQ IUTPL QENSP ESIWP YFWPSPQLQE LXISP IWIHF EFWPL QTQQU SXPLQ FNPDU PODUI XLQTQ INSPKIWXPL FERIE SPITD UITIN IESQI WINLP ENQLQ TQINS IXFVI FXQTP ENQITNIXIE QNNQV XINNP OSQNL QTQIN SINKF EBIFX QNPOS QNDUI ITYIXWIIQF XQNIP CFSPT LQTQI NSPNP YINDU ICXFS PTITV IVIWI FXPNW IPRUOIOINE PQNPV ITDUI QNQEB QIYFE BQIIN KUTPI HIXTI ESQVF LBFEB QPOPLXIINI WIESQ WIHQL FEBQK QESFP CUWQD UIHQN NPPSX PYINW ISUWQEUTKI XKISU QTQYF TIESQ IOINE PQNPV ITDUI QNQEB QISIO PILQX IKFELIOVPN IHUNS ILPKF SIOPX LQITQ CFYPY FSXPO KFEPL UOQWI LPSIWXPOLQ ESXPK QESQN FEHQE FPTPN LPXPC XICPT PCFPD UIIXI SQXSPWIPOD UFTFN SPTPK PWQTU EWQWF NSPES IXQNP WQNYI ESQNF EHPESILPXP YIOPD UFEBI ESFNS PDUII LPVQW PVQPI NKIXP ELPQU XQLPE IOPTPXHFTH OQXIS IWIIN KPWPL BFTVP NSFWQ XKPNN QWIWP ELPLQ OQTVFEPIPX OIDUF TKPNN PXQOP YQPWQ XPKPX PXPFQ NOQLQ TQSFY PVPXLQWIKX QPHIN SFYPP OSQHQ XEQCI XPWQX PLFNP QWQPS QTQXP WPXUOSXPNQ TSIOI YFNPQ WINIT VPXDU IITHQ CUISP QEPNU KIXHF LFIOU EPXIOINEPQ NPVIT EITNQ EBPTD UIQNQ EBQLQ TPEWP PYFWP DUINI TKXIDUIUTB QTITN QEBPQ TUEWQ KUOPI PYPEL PLQTQ VQOPL QOQXF WPIESXIPNT PQNWI UTPLX FPELP



Estatısticas

Port Esp Ing Fran

A 13.8 12.7 7.8 9.4

B 0.9 1.4 1.3 1.0

C 4.5 3.9 2.9 2.6

D 5.6 5.6 4.1 3.4

E 12.0 13.2 13.1 15.9

F 1.0 0.5 2.9 1.0

G 1.2 1.1 1.4 1.0

H 0.6 1.2 5.9 0.8

I 7.0 6.3 6.8 8.4

J 0.3 0.6 0.2 0.9

K 0.0 0.0 0.4 0.0

L 2.8 5.9 3.6 5.3

M 4.1 2.7 2.6 3.2

Port Esp Ing Fran

N 5.3 7.0 7.3 7.2

O 10.8 9.5 8.2 5.1

P 2.9 2.4 2.2 2.9

Q 0.8 1.2 0.1 1.1

R 6.9 6.3 6.6 6.5

S 7.8 7.6 6.5 7.9

T 4.9 3.9 9.0 7.3

U 3.8 4.6 2.8 6.2

V 1.3 1.1 1.0 2.2

W 0.0 0.0 1.5 0.0

X 0.2 0.1 0.3 0.3

Y 0.0 1.1 1.5 0.2

Z 0.3 0.1 0.1 0.3



Cripto-analise

pt cpt frq

A 13.8 0 0.00

B 0.9 15 1.58

C 4.5 9 0.95

D 5.6 18 1.89

E 12.0 57 6.00

F 1.0 48 5.05

G 1.2 0 0.00

H 0.6 13 1.37

I 7.0 128 13.50

J 0.3 0 0.00

K 0.0 20 2.11

L 2.8 39 4.11

M 4.1 0 0.00

pt cpt frq

N 5.3 70 7.37

O 10.8 30 3.16

P 2.9 127 13.40

Q 0.8 112 11.80

R 6.9 2 0.21

S 7.8 48 5.05

T 4.9 52 5.47

U 3.8 38 4.00

V 1.3 17 1.79

W 0.0 38 4.00

X 0.2 53 5.58

Y 0.0 16 1.68

Z 0.3 0 0.00

A,E I,PO QS NR E ou X



Cripto-analise

E IA P

O QS N

R XM T

E-ES- AOSA- EM-EM SO--A M--EO SO--O E-MA- O-S-A --E-A ---A- AO-O- -RE-AE-E-- ---A- OMOO- -RA-O -SA-- A---E R-OMO ES-A- E-RA- ---E- -AEM- -EMESE--OE -ES-A -SO-O MOES- ER--E -ROMA -SOEM SERE- OSSO- RESSA --OS-OMOES -ES-- --E-R OSA-- OS--E EM-ER -EEO- ROSEA ---AM -OMOE S-ASA-ES-- E-R-- AMEM- E-E-E -RAS- EA--- E-ES- AOSA- EM--E OSO-- OE--- -OEES--MAE -ERME --O-- ----- OA-A- REESE -E--O -E-O- ---O- O---A ---O- -E-OS SAA-RA-ES- E---O --M-E R-E-- OMO-- ME--O E-ES- AOSA- EM--E OSO-- OE-E- AE-ORE---- E--AS E--S- E-A-- -E-AR -OEMO ---A- --RA- ---A- --O-E -A-E- RA--O --RA-O--OS ---O- -AMAS -ARA- RE-AM A--A- -EERE -OR-A -EA-- --M-S -AMA- A-OM---O-- S-A-- EROSA -OS-E --OS- --A-- E-ARA -E-A- ----E ---S- A--EE -A-O- A-OAES-ERA --AO- RO-A- E-AMA R--M- -ORE- E-EES -A-A- --M-A S---O R-ASS O-E-A--A-O -OM-- -AEAR -E--- M-ASS ARO-A -OA-O RA-AR ARA-O S-O-O MO--- A-AR-O-E-R OA-ES ---AA --O-O R-O-E RA-OR A--SA O-OA- OMORA -AR-- -RASOM-E-E --SAO -ESEM -AR-- EEM-O --E-A O-AS- -ER-- --E-- -ARE- ES-AO SA-EM-EMSO --AM- -EOSO --O-O MA--A A---A --ESE M-RE- -E-M- OMEMS O--AOM---O ---AE A-A-- A-OMO -O-A- O-OR- -AE-- REASM AOS-E -MA-R -A--A



Texto original

ELESN AOSAB EMNEM SONHA MQUEO SONHO EUMAC ONSTA NTEDAVIDAT AOCON CRETA EDEFI NIDAC OMOOU TRACO ISAQU ALQUE RCOMOESTAP EDRAC INZEN TAEMQ UEMES ENTOE DESCA NSOCO MOEST ERIBEIROMA NSOEM SEREN OSSOB RESSA LTOSC OMOES TESPI NHEIR OSALTOSQUE EMVER DEEOI ROSEA GITAM COMOE STASA VESQU EGRIT AMEMBEBEDE IRASD EAZUL ELESN AOSAB EMQUE OSONH OEVIN HOEES PUMAEFERME NTOBI CHINH OALAC REESE DENTO DEFOC INHOP ONTIA GUDOQUEFOS SAATR AVESD ETUDO NUMPE RPETU OMOVI MENTO ELESN AOSABEMQUE OSONH OETEL AECOR EPINC ELBAS EFUST ECAPI TELAR COEMOGIVAV ITRAL PINAC ULODE CATED RALCO NTRAP ONTOS INFON IAMASCARAG REGAM AGIAQ UEERE TORTA DEALQ UIMIS TAMAP ADOMU NDODISTANT EROSA DOSVE NTOSI NFANT ECARA VELAQ UINHE NTIST AQUEECABOD ABOAE SPERA NCAOU ROCAN ELAMA RFIMF LORET EDEES PADACHIMBA STIDO RPASS ODEDA NCACO LOMBI NAEAR LEQUI MPASS AROLAVOADO RAPAR ARAIO SLOCO MOTIV ABARC ODEPR OAFES TIVAA LTOFORNOGE RADOR ACISA ODOAT OMORA DARUL TRASO MTELE VISAO DESEMBARQU EEMFO GUETA ONASU PERFI CIELU NAREL ESNAO SABEM NEMSONHAMQ UEOSO NHOCO MANDA AVIDA QUESE MPREQ UEUMH OMEMSONHAO MUNDO PULAE AVANC ACOMO BOLAC OLORI DAENT REASM AOSDEUMACR IANCA



Outra cifra...

A B C

D E F

G H I

N* O* P*

Q* R* S*

T* U* V*

K

M

LJX*

Z*

Y*W*

MATEMÁTICA



A cifra de Vigenere

A B C D E F G H I J K L MN O P Q R S T U VWX Y ZB C D E F G H I J K L MN O P Q R S T U VWX Y Z AC D E F G H I J K L MN O P Q R S T U VWX Y Z A BD E F G H I J K L MN O P Q R S T U VWX Y Z A B CE F G H I J K L MN O P Q R S T U VWX Y Z A B C DF G H I J K L MN O P Q R S T U VWX Y Z A B C D EG H I J K L MN O P Q R S T U VWX Y Z A B C D E FH I J K L MN O P Q R S T U VWX Y Z A B C D E F GI J K L MN O P Q R S T U VWX Y Z A B C D E F G HJ K L MN O P Q R S T U VWX Y Z A B C D E F G H IK L MN O P Q R S T U VWX Y Z A B C D E F G H I JL MN O P Q R S T U VWX Y Z A B C D E F G H I J KN O P Q R S T U VWX Y Z A B C D E F G H I J K L MO P Q R S T U VWX Y Z A B C D E F G H I J K L MNP Q R S T U VWX Y Z A B C D E F G H I J K L MN OQ R S T U VWX Y Z A B C D E F G H I J K L MN O PR S T U VWX Y Z A B C D E F G H I J K L MN O P QS T U VWX Y Z A B C D E F G H I J K L MN O P Q RT U VWX Y Z A B C D E F G H I J K L MN O P Q R SU VWX Y Z A B C D E F G H I J K L MN O P Q R S TVWX Y Z A B C D E F G H I J K L MN O P Q R S T UWX Y Z A B C D E F G H I J K L MN O P Q R S T U VX Y Z A B C D E F G H I J K L MN O P Q R S T U VWY Z A B C D E F G H I J K L MN O P Q R S T U VWXZ A B C D E F G H I J K L MN O P Q R S T U VWX Y

Chave: CRIPTO

CR I PTOCR I PTOCR I PTOCR I PTOCR I PESTAMENSAGEMNAOEMU ITOSECRETAGJBPFSPJ I VXAPRWTF IKKWHXQTVBP



Enigma

Figura : Maquinas Enigma



Enigma

Figura : Esboco do interior de uma Enigma



Enigma

Figura : A “chave” na cifra Enigma



A arma mais secreta...

Figura : Bletchley Park e Alan Turing (1912–1954)



Numeros Primos

Numero primo

Numero natural, maior do que um, que nao pode ser escrito comoum produto de dois numeros menores que ele.

91 nao e primo, pois 91 = 7× 13.

17 e um numero primo.

Alguns primos:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137,139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277,281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359,367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, ...



GIMPS e EFF

O maior numero primo actualmente conhecido e:

257 885 161 − 1,

um numero com 17 425 170 algarismos!... Encontrado pelo grupo

GIMPS (Great Internet Mersenne Prime Search) em Janeiro de

2013.



GIMPS e EFF

Encontrado em Agosto de 2008, o numero primo:

243 112 609 − 1,

com 12 978 189 algarismos, foi o primeiro numero primo que se

descobriu com mais de 10 000 000 de algarismos. Foi encontrado

pelo grupo GIMPS (Great Internet Mersenne Prime Search), que

com ele ganhou o premio de $100 000 da Electronic Frontier

Foundation (EFF), pelo feito.

A EFF oferece um premio de $150 000 pela descoberta do primeiro primo com

mais de 100 000 000 de algarismos e um de $250 000 pela descoberta do

primeiro primo com mais de 1 000 000 000 de algarismos.



Factorizacao

90 = 9× 10 = (3× 3)× (2× 5) = 2× 32 × 5

76 = 22 × 19←→ H2O



Uma assimetria importante

7432339208719× 341117531003194129 = ?

2101 − 1 = 2535301200456458802993406410751 = p × q ?...

RSA2048 = 25 195 908 475 657 893 494 027 183 240 048 398 571 429 282 126 204 032 027 777 137 836

043 662 020 707 595 556 264 018 525 880 784 406 918 290 641 249 515 082 189 298 559 149 176 184

502 808 489 120 072 844 992 687 392 807 287 776 735 971 418 347 270 261 896 375 014 971 824 691

165 077 613 379 859 095 700 097 330 459 748 808 428 401 797 429 100 642 458 691 817 195 118 746

121 515 172 654 632 282 216 869 987 549 182 422 433 637 259 085 141 865 462 043 576 798 423 387

184 774 447 920 739 934 236 584 823 824 281 198 163 815 010 674 810 451 660 377 306 056 201 619

676 256 133 844 143 603 833 904 414 952 634 432 190 114 657 544 454 178 424 020 924 616 515 723

350 778 707 749 817 125 772 467 962 926 386 356 373 289 912 154 831 438 167 899 885 040 445 364

023 527 381 951 378 636 564 391 212 010 397 122 822 120 720 357



Uma assimetria importante

Primalidade

Ha algoritmos “muito rapidos” de verificar se um dado numeronatural e ou nao primo.

Factorizacao

Nao sao conhecidos algoritmos “rapidos” para factorizar numeroscompostos “genericos”.

Por exemplo: sabe-se que o numero 2220

+ 1 e composto (tem

315 653 algarismos!....), mas nao se conhece nenhum seu factor...

Outro exemplo:

2739 − 1 = 184603056517613273120809×

48050683584092004380805463790111× C168



RSA

(1978)



RSA

(2003)



Receita para construir uma cifra RSA

p e q dois numeros primos “grandes” (∼ 300 algarismos...)

n = pq

c um numero sem factores comuns com ϕ(n) = (p− 1)(q− 1)

Calcule-se (usando o algoritmo de Euclides) “o” numero

inteiro d tal que cd deixe resto 1 quando dividido por ϕ(n)

chave publica : n, c

chave privada : d



Como se cifra e decifra

Alice cria uma cifra RSA (n, c , d), publica n, c e mantem d secreto.

Bob −→ Alice

Mensagem (em forma numerica) a transmitir e dividida em

blocos correspondentes a numeros inferiores a n.

Se M e um bloco da mensagem a transmitir, calcula-se o

resto da divisao de Mc por n.

Esse resto constitui o criptograma C correspondente a M.

Para obter a mensagem original, Alice calcula o resto da divisao de

Cd por n e obtem (gracas a Fermat e Euler!) M.



Assinaturas digitais

Com o RSA nao e necessario compartilhar segredos: cada um criaa sua cifra RSA, que os outros usam para comunicarem com ele.

Assinaturas digitais

Alice ←− nA, cA, dA

Para assinar um contrato, C , que Bob lhe manda, Aliceenvia-lhe M = resto da divisao de CdA por nA.

Tem-se que o resto da divisao de McA por nA e igual a C, oque qualquer pessoa pode verificar.



Alguns usos da Criptografia contemporanea

comunicacoes militares;

pagamentos e transferencias bancarias;

comunicacao segura via internet;

assinatura e datacao de contratos digitais;

autenticacao e certificacao de documentos digitais

eleicoes electronicas;

(futuro proximo?...) dinheiro digital.



Chave publica da CGD



NSA



NSA



NSA



Bibliografia

Martin Gardner, Codes, Ciphers and Secret Writing, Simon &Schuster, 1972.

David Khan, The Codebreakers, The Macmillian Co., 1967.Reeditado pela Scribner, em 1996.

Simon Singh, O Livro dos Codigos, Temas e Debates, 1999.



Webgrafia

RSA Laboratorieshttp://www.rsasecurity.com/rsalabs

Decoding Nazi Secrets (NOVA - PBS)http://www.pbs.org/wgbh/nova/decoding

Bletchley Park - Station Xhttp://www.bletchleypark.org.uk

The Principle of the Enigma, por Tony Salehttp://www.codesandciphers.org.uk/enigma/enigma1.htm


http://www.rsasecurity.com/rsalabs

http://www.pbs.org/wgbh/nova/decoding

http://www.bletchleypark.org.uk

http://www.codesandciphers.org.uk/enigma/enigma1.htm

Documents

Uma Muito Breve Introduc˘~ao a Criptografia