Elementos de Education.Criptografia

Trabalho Prático 1 (9 Mar)

Efectue a criptoanálise destes quatro criptogramas que foram obtidos recorrendo a cifras de substituição, Affine e Vigenere. Deve que determinar que cifra foi utilizada em cada um dos casos. Apresente todo o trabalho que desenvolver, incluindo o código, e explique como chegou a uma solução. Não é suficiente apresentar o texto limpo.

Os textos limpos são em Português, e não contêm acentuação de nenhum tipo, espaços ou pontuação. Os valores típicos da análise de frequência aplicáveis em Inglês não são aplicáveis neste caso: terão de ser calculados propositadamente para este efeito. Quanto melhor for a qualidade dos valores que obtiver, maiores serão as hipóteses de que os seus palpites estejam correctos.

JFHLTZZJHBVOHSBTJSOHSHBIHEBWHGJZLBQTQJZSJOJJEVQJOMTWJWFBTOJLBWKBHZJXOTFVAKHOBZJB
WMOBWKJOBLFOTZBZWHZBFKHOSOHGHFJQJZSHOQBZJZKOBZWJKVOJTZHVSOHUABLJZFATLJKTFHZFHLHJ
ZBFJDVBJMBFKJSHOKVXJAJSOHSHZKJZHUOBOTZFHZBXBZKJHQBFOTZBZWJJXOTFVAKVOJZBOJJSOBZBW
KJQJJHFHWZBAIHQBLTWTZKOHZQJVWTJHBVOHSBTJJFJKHOYBQBLJOFHBZVXBOBDVBHZJXOTFVAKHOBZB
SOHQVKHOBZQBJWTLJTZZBEJLFHLSBWZJQHZFJZHZHMOJLFHLFJKJZKOHMBZWJKVOJTZSOHUABLJZFATL
JKTFHZFOTZBQBLBOFJQHHVQHBWFJZJWTLJTZZBXVWQHHQHFVLBWKHJDVBJJXBWFTJAVZJKBGBJFBZZHH
HUEBFKTGHBBWFHWKOJOJLBAIHOZHAVFJHSJOJOBZSHWQBOJZZTKVJFHBZQBFOTZBWHZBFKHOJXOTFHAJ
ZVXBOTWQHKOBZHSFHBZZBXVOHJXOTFHAJMVWQHZLVKVHZBTWZKOVLBWKHZQBFOTZB

RAJRXRIPIQBUFLDSDPHOGQIVVLXLUGFLHAEYVWYFMAUDMVVGPIVASMDLKYQVBREVMXNWUEFSOPOQWVAS
SUBGSMFHDHDAKZISRHWHVINLHPXFOQIBWXJRVQIRVAWAVHHKOQQXHRNHWIBTHCWMYWJRRXICIVXXRALD
LHRXUEIQASIUMYBLHSSEFPUQIMULDDJGFMLAHQGWOFNXNGEPMTGWVAUIDTOMIFARHHAKFAREVESWXGII
EFLDLGQMYIGSDWLNKWOGIDTMHUDSGEVIRRODDDWYQZVUDSWIUMSZMQOVHHLKMIVSHMVITBAGELHDLKRI
QEFIVAOQIGEGISZKFMUVDVDLOTVLDDHHLGFXHSVSDAKADRLYMGIYNAVIPESIXGQUDHEPITUIDSVIVAUR
AQOWVLJAAIOMLPLBGELHLLWEWGIIRDHGRZXRZDPRVWILRKKAGESIXNYXEDWDTKTIGAVZLBOZIVPRWVIS
CZHSWEULKPTDRDGRMYFMPLLQLBGPWHSRYFWTFBUAQKLUKABRSRGRTKPBLVRHHRAVHHSDHPQZRVREQXDV
ZBYXERWMWXAIOIVXDAVBLHRDSYQXNBHRDTRAYVJLLLHDLKQMDSVMVBOEIDLJYPIYFMVSRIVLKFBHJXPJ
ISRVWOVIVMPHAWIIMFIXAWIUWYUWGCZRVHHRZGQIFAVESQGQMOIVFRIINBDLLRDXKFBDNDGRUKPWXHRN
HIYRZRUYMGITNYXAOMGIJRLHTHWWMSHVKAGIDKAFIFARRRRAYODMHRWWJBXUOFIVAURUTUHZDZOBAPEQ
SUMYNTXNRWGIWHMOALRVBOGCLCDSVMWHMLXDQGMGOCVOVWHFANQV

XTHSVXOHTLCZSYZLXBAFLCZTHZCFAZXAHMCXNXBGFVAXYZTHZCXZSMHCSXYZFSXBVFNCHAHTFYCXYZXM
HCCFCZVTFHVHOUCXSYXRUHFSMHTVHCHXBZIFUHTTXACZAPFZXAHRUHXBUMXYFSMCXFMHCCFCZVTFAHEH
LCHVHCEXCXAHTFYCXYZXSHVMHHSYFSMCFAHCHPBHJXFHGFTHSXOHTXVEZMZTXVAFVXMHSMXAFVAHFSIH
AHTXCYFAHAFZVTZBHRUXMCFSXYXLZMXBHVLXSGFBXHVMXFLCHVHSMHVMCZSMXHYZSYFXYMUXZVHXSMZO
FVYGHPHVAHHVMXAFHAHOFEHCSFAXHUCFLXXTHCZYXHXVZXAHEHTVHTLCHVHCLCHVHCEXAFVFVLCZSYZL
ZFVAHTFYCXMZYFVSFYFTNXMHXFMHCCFCZVTFFVOFEHCSFVAHEHTAZVMZSOUZCFVAZPHCHSMHVMZLFVAH
MHCCFCZVTFFVOCULFVMHCCFCZVMXVZVFBXAFVAXVUXYFTUSZAXAHYFTXRUHBHVYFTXTLBXNXVHAHXLFZ
FLXCXRUHXCHVLFVMXSXFVHQXZSAZVYCZTZSXAXFYXVMZOFAHEHVHCAZCZOZAFXFVRUHYFTHMHTFXMXRU
HXFVFUMCFVAHEHCZXTFVPXYZBZMXCUTXVXZAXAFOCULFHXCHZSMHOCXYXFZVVFLHCTZMHXOCULFVRUHS
FLXVVXAFCHYFCCHCXTXEZFBHSYZXYFSEHCMHCHTVHHTLXCMZAFVLFBZMZYFV 

LDOMXRGXRGAJREYLMTRTIIDNRRYSWVUAJRQMHXAUHDSUNUXXSWDYQLHAYLNAJYSDHMEWHWXRXEGXFELA
NFUORFCATRBWLXEIDGITOELPOGRCSRQOSHRIJWSESYNRVDSUKUVVSMJHOIDEYHYSJDQSLMAVAWWWYEMD
WHDCTVPCWXGAIDPYOUDVLBHLANRFOSSURVFSMPJOJVWZHFOVVHEGIAHXSMVNOTKSKROSFPCWVYMGUSSV
GEJPCWRLAMHXEPMOZVHSQUOJLURLZITDEYHJOIYSDHMSVQOSWYNYDFECUODDGRROTIDGIXGTZTIIQISL
SZIPYNKRAMOZOCKOWHRIJWSYPCNHXSVLNOZQHMWOLRGCSVGELVZMYLOJRBHHMEGHFKXHTRRGPLPRFVEY
HMERQREDFEIRGUXYSVGSMAURRPOQHCOFVEYHAOJWOVLUMFVRIYYRKUOHXTIURGIPKUVOIKDLEJJCWWUM
FVRIOYRVDGWLGPFURMDHTVQOYONIDDGIPUNRDDEUYCVWWEJIRVESPRUPIHGIQNAURQSPIJFUBEOCSKDS
IVWRZWCVDJRFSCWLNOUHHVDXUTRSWGCZERGSTOEVXUSVNAILOIUUMVVASGYVVUCWOCVIRGTRLTLJIIVY
SKUOHXTIURGRROTIDGPLHGLDGIHMPRQHSVICFPCESLEJHBGDFIKHFEUCAGRFXXAUVVORRYSKUORJYIIR
STUUTZFOQHHTVLBIACSKHBXHBAGDWWHMCFPPIPGEERGMQZLLHBGLUNRFSRDCNKHFRDWIFQOPGIQLHCRR
MSFHQSPGUZWCQDCSVVQVLNOIHGXUUDLCWHRMCFQHEPMEGHZSVXEURGHHOMRPOSRMEJFFMWIRVVDSUNUX
XSWHMCFQHIPJOIDBIRMPLEZMFUDFVBSHMTIDBKHCRFHWWWIEKDCKUUVVTIIDNEURWSVYSTUWXRLEJVOS
RMMRLCVHMEDEOMAUDFUSWGUCLOHYUUDVXATDCSDDGFDMTRYSVDUTVQQERKUVRGWXWEJVWZRMMZQWWWLO
JGOGXFTLUOHDIAFVSWFLIKRFIVUODHFGDXOURZMYLORVTILLAJQOGLINRLGILHTVUBEFCOEDWWHYSKDH
YGIDZWC

Trabalho Prático 2 (29 Mar)

Recupere o texto limpo correspondente a cada um dos seguintes criptogramas obtidos com a cifra RSA. Os textos limpos são em Português, e não contêm acentuação de nenhum tipo, espaços ou pontuação. Note que para módulos pequenos o problema da factorização do módulo é relativamente fácil de resolver. O texto limpo foi dividido em blocos de i letras: cada bloco Li ... L1 L0 é codificado no inteiro Li*(26^i) + ... + L1*26 + L0. No último bloco é sempre inserido padding, correspondendo cada letra inserida ao tamanho do padding. Escreva e use os seus próprios programas para fazer a criptoanálise. Submeta listagens comentadas das partes relevantes do código que produzir, o texto limpo que recuperou e uma explicação de como procedeu para resolver o problema.

• n = 50551003, b = 43895939, i = 5

48719265 21880419 23965733 14001622 3070522  47443255 48309887 33673752 35549706 49914515 
43921685 41763987 40617457 28547288 24741601 47660212 5408554  20291721 1586284  26316809 
38752125 10669665 5702740  24003390 11736573 3357958  8385983  38988184 6154291  42157963 
43114702 47389753 25802737 29586057 22820212 3690070  50243706 6246549  43436024 163876 
50047952 18202724 22089148 43564874 48311699 31508947 33093643 14605746 43867811 34936684

• n = 496512267794407, b = 310797528069941, i = 10

494950396530045 360281654495711 368975154129887 30561943863961  334948285104881
18316458143035  96000472684982  133666404416183 409533889130276 350688627329095
213732952172345 60429274433144  63602792292608  268349095750036 103815596223158
464367601174306 170369569453302 317460468215202 378234199027787

• n = 35284289135845204898669273297, b = 15726997560115741338660832027, i = 2

16594592540948632866410856152 4628705454357396018364171298  26515904109882395927917599254 
16323700905536914131565125686 19129858834350460740923828759 25414556268366263391700381021 
22979061971598930334210341534 11810960361886427149732895484 1085800860141793848945882117 
17654636174389044433202415878 11272843556062964972731697302 18821622262586937231039250826 
25435603738790311227309443963 4827012698550488751951768313  15666427695314052817191701099 
15666427695314052817191701099 11810960361886427149732895484 9866380858673686609452780090 
31641696783154640262798844648 31491823762568666759921435169 17654636174389044433202415878 
35126199541878816183852478437 20056298078993283887887339548 14551027357478031831613617509 
12633638776833338220017642818 30663092625857909816595084761 30224578244323036924848705339 
3128872702613793094100228835  1386820748125155472606902357  13420052590603012550180596268 
8518952267006363930378494507  9529857145202206292577951750  23781581582663358728219167151 
24607738631382740752599647590 4377141701176394900719737566  17095837257824688500219792240 
3128872702613793094100228835  15236705311097736922229162330 1519683421940540807847914743 
4546144604184083487868364999  17095837257824688500219792240 25160415929591742360745266342 
15666427695314052817191701099 14551027357478031831613617509 12633638776833338220017642818 
28027160953063196348757287545 31641696783154640262798844648 32778492478772700203318631446 
4377141701176394900719737566  17095837257824688500219792240 1085800860141793848945882117 
17095837257824688500219792240 2079393894100576310021781669  20590916608497244504872413657 
6809426493653542163806993157  16323700905536914131565125686 32185215707174199438263906801 
1972135201431540827995553840  25414556268366263391700381021 23781581582663358728219167151 
16594592540948632866410856152 17095837257824688500219792240 30970683011186084958082199749

Gere uma chave RSA que permita cifrar blocos de 20 letras, como por exemplo a seguinte:

• n = 1174131352704207214349241420991791462495108045279851173277
• a = 935796131047316636883975835187745394794578628568303251791
• b = 401138724311605979942538127567746219521486438387303984111

Já agora, como extra poderá tentar factorizar este módulo.

Trabalho Prático 3 (5 Maio)

Seja E a curva elíptica y^2 = x^3 + x + 13 definida sobre Z149.

• Determine o número de pontos em E.
• Determine se E é ou não um grupo cíclico. Em caso afirmativo encontre um gerador desse grupo. Senão, encontre um elemento com ordem máxima.
• Decifre o seguinte criptograma determinado com a cifra de Menezes-Vanstone descrito na secção 5.2.2 do livro Cryptography: Theory and Practice. O expoente secreto é a = 100. Cada elemento do texto em claro representa dois caracteres, codificados como A<->1, B<->2, ..., Z<->26 (neste caso, 0 não é permitido no texto em claro).

((10,24),38,68) ((19,22),45,111) ((6,91),22,2) ((69,33),83,54) ((146,79),52,145) ((107,54),49,36)