Trabalhos Práticos de EC - 2006/2007

Trabalho 1: Cifra RSA

Implemente em PARI/GP a geração de chaves RSA assim como as primitivas de cifragem e decifragem RSA.

Implemente também dois esquemas RSA: um sem padding (ou padding a zero) e outro que use a codificação PKCS1.5 (note que, apesar de estar ainda presente no Standard, o seu uso é preterido em favor de esquemas do tipo OAEP).

A sua implementação deverá cobrir as duas possiveis representações de chave privada. Comente adequadamente, optimize o seu código e inclua exemplos de execução.

Como referência, consulte

• 1363-2000 IEEE Standard Specifications for Public-Key Cryptography
• 1363a-2004 IEEE Standard Specifications for Public-Key Cryptography- Amendment 1: Additional Techniques
• PKCS #1: RSA Cryptography Standard (RSA labs)

Prazo de entrega:

Os trabalhos deverão ser enviados por email até ao dia 30/4/2007 7/5/2007 (Actualização)

Desafios:

Os seguintes desafios foram todos cifrados sem padding e demonstram algumas más práticas a evitar ou situações susceptíveis de ataque. A dificuldade dos desafios vai aumentando. Duas boas referências para ataques à cifra RSA:

• "Handbook of Applied Cryptography" (capítulo 8) - Menezes, Oorschot e Vanstone
• "Twenty years of attacks on the RSA cryptosystem" - D. Boneh

Tente recuperar o texto limpo original correspondente a cada um dos criptogramas RSA apresentados. O texto limpo foi dividido em blocos de k/8 caracteres, onde k é o tamanho do módulo RSA usado e codificando cada caractér com base no seu código ASCII (consulte as funções Vecsmall e Strchr). Na implementação foram usadas as funções de conversão de dados OS2IP e I2OSP para converter as strings de octetos em inteiros para uso das primitivas RSA e vice-versa (ver documentação acima). Em particular, os criptogramas estão apresentados como blocos de strings de octetos (em hexadecimal). Note ainda que números grandes podem estar partidos em várias linhas.

Submeta as scripts de código que produzir, o texto limpo que recuperou e uma explicação de como procedeu para resolver o problema.

• Problema 1
  • e = 5
  • N = 3587574192954427231067141445521243178607587714286579335419222874 9439203035201
  • C = 14 e7 47 40 30 e9 d6 81 63 1e 9c 27 84 3a 61 3a 3a 32 4a 48 e7 e2 db e7 54 4c b4 df 97 51 c6 8d

• Problema 2
  • e = 3
  • N = 1089032683577364550668153146809624530428147750062064927216784759 6909833919686793385914649409832768160832685955810794264464577272 1578023786494435786218535101121749241579474189946833477645334025 6712003090427026723655229095672214149022589694174418368841198294 49701459194027075720926766820866417694789983660054201
  • C = 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 05 1b 2b 27 94 53 9b 1a 7d 1c 51 d9 31 1c 58 d1 70 cc cc 0c 4b ca 28 8f 27 d1 a4 bd 91 d2 b2 4a 0c 54 10 bc 3f ee 2d 47 a9 a4 d5 5b fd 63 47 8d 0f 06 0d 97 68 c0

• Problema 3 - Uma mesma mensagem M foi cifrada para três destinatários distintos com chaves públicas, respectivamente, (N_A, e), (N_B, e) e (N_C, e).
  • e = 3
  • N_A = 1122108819125288328734887308976261927054733692196165387530817045 5144422828779927054951818350236074434502334082373179631020451837 1544839019675852328331644980384851027727542434889929546615023950 7870720121300501583706799423536865480798066430190233181161961115 24880623908853557168750513262508514183295567563396901
  • C_A = 5d f0 ba 37 0c ed 20 7b ef 9c 80 f2 fa e3 b7 98 91 44 ed 3f 34 5f a8 df 60 92 bb a1 c0 5b 2c ee 4b db b8 8a 91 e3 f2 4e 77 1f 5a 9a e0 12 68 e1 3d d5 8a 8a 29 be 59 fc c6 e1 b5 ed ed 50 c6 1a 28 75 76 59 c5 d9 0c 13 05 8e f2 77 09 5b 04 56 90 2e bc d5 bc 40 84 d0 11 6e 32 d1 7b 80 78 df ca 9d 5c 53 26 ec 89 77 8f d0 25 c6 0b a4 4e fe b6 19 10 15 17 67 58 fa 58 5d 3a 29 bb ad 80 7d
  • N_B = 1203920984865608812188685303379759281708284737097885756870024244 2218525209633774370409435193513981140455560063960980279313799625 7833314068179655039692270490823980274420626465969667005417243382 1860006189185562586976210825142393988849701185584377921996904077 36712811686600001659384083176017014815881112323115387
  • C_B = 8b ba 35 a0 e2 39 4b 76 b4 36 56 bc 59 c7 6b 42 45 a3 e2 86 55 a7 2b bb 6c 2f 03 62 4d 22 da ae dc fc 07 07 82 c8 00 07 bc a4 ec a6 76 9d cf c6 2c 78 1d 1c 51 11 8a ea e9 11 6b 12 1c 55 33 72 28 ca 49 ee 1c 8c d7 f2 33 57 e9 72 38 91 11 b0 b9 35 6b 40 ce b3 5f fa 10 a8 29 1a 5e 3a a9 ee f4 57 af 37 a5 d7 a3 61 ec 4a d4 b9 08 22 f4 7a 41 bb 0e 7b d4 23 87 1c 79 0d da 49 ad 00 d5 7b
  • N_C = 1022554975542090063482710721600443949132214642275677741779805505 6021040530801119347667248824133296162673405108799966263434683008 1397262246730728060484806512449999058632114263350609476673917049 5243777520161990777652437505720980003147743232552239269909862465 38360263915450005885639842950464914540414973228130477
  • C_C = 21 a3 3d bf e5 45 28 a2 a6 dd 2c cd be 3d fd 3c 66 29 1c f5 1e 09 6d e6 0d fd 9f 24 47 39 f7 48 14 e0 4d b6 0b f6 09 51 c9 d7 f3 d8 e5 04 ac 58 72 d3 63 87 3c 78 f1 76 b9 95 69 63 3e 69 a5 44 c0 a7 5e f7 1a 5c fe c8 81 10 19 04 74 d5 3b f4 97 0f 9e a0 23 e8 1b d4 6d 4d 3a 87 4c d6 5e 0b 41 df fe cd 03 6d fb f3 df 4f 08 fe 7e e9 ef 6e a7 57 3b 73 ab cb d2 47 21 ef c2 17 e4 50 2c 77

• Problema 4 - Uma entidade gerou dois pares de chaves (e_A, d_A), (e_B, d_B) com o mesmo módulo N. O criptograma C resultou de cifrar uma mensagem M com a chave pública(N, e_A). O par (e_B, d_B) é-lhe conhecido.
  • e_A = 7
  • e_B = 65537
  • d_B = 3941660308803989588796406037133474870767018186927131910996047734 7702105880619234458420932298926540265854465032835901877079191136 3625596047742324915271764994317854466603971318473969792423131558 0999119099507819572983084995937043975358564874839468140832738389 2352649528455574857326003405818818014111476249182273
  • N = 9319068963134454028894302397388764163256063164381076625214573607 2740004080019580400488190478887037135761330261795328330380192983 5423184999310560893656770122690039118217688075368974268275502654 0262403851351000479569108965475246903102665778935639554017423017 4770649063948079509069830480072323583374601495530559
  • C = 80 f8 31 9a 3c 3c 59 e3 a3 50 58 15 18 72 d2 d6 9a ce 3e d9 8e a0 69 55 55 dc 7e 65 63 ce 3d f1 a2 c2 d1 79 dd 71 e0 a8 dc b9 8d 85 61 63 fb c6 fb 86 e0 a2 4d 53 6b c5 29 8d c8 a6 82 12 4c a2 a2 7c 0f db ee 1a cb 0b 82 5e 66 ec dc 8d e1 ac f9 d0 5b 9f 6a 35 85 f7 99 1a 63 39 9c 10 2d c7 72 1b 22 ca 55 e4 a9 51 77 04 4f dd bd b0 a9 9c 59 8b a6 77 21 d8 e4 01 ef 87 60 45 48 1a 4b f1

• Problema 5
  • e = 2781256904645424482432081634242555131496595019896396122661652483 1852818707612280200369494571182920614986907740197159710639233959 9362621130977624648471971584109105417809729915120380582976281221 6593313934362689149547380900478372287256449191972768111548274700 1462621144735141539925656762024582802558939120369493
  • N = 1390628452322712241216040817121277565748297509948198061330826241 5926409353806140100184747285591460307493453870098579855319616979 9681310565488812324235985815731186882762045899073877401244364116 6541174461115382050943958194070324865198444165777393853885199987 26871321612903150483200686546285155751607596546340899
  • C = 77 81 2f 94 ed 89 d2 3a 00 fd 62 99 c8 2a e0 61 b1 bb f7 9a b8 80 24 9e 9f c2 22 a4 dc 7d 34 32 69 f0 cd 2f 71 87 d1 13 64 7b c3 3d b5 30 bb d0 64 99 fc c9 67 40 c6 eb 1b 5f df aa 1b c5 0f 24 50 b4 de 42 54 0f 52 fb ab 05 c3 89 4a 84 c9 8c ae c1 c2 42 21 03 93 63 e6 3b da 64 2b 99 38 d2 b4 06 1b 67 59 cd 66 b9 b9 14 8b ea 93 15 57 47 a2 b9 db 45 08 2a 07 9f 4b b2 34 31 b9 03 99 8f

Trabalho 2: Funções sobre GF(2ⁿ) e GF(2)ⁿ

No que se segue, cp é um polinómio característico de GF(2n), B é uma base de GF(2n) e (.)~: GF(2n) -> GF(2)n denota a representação vectorial de um elemento x de GF(2n) segundo a base B, isto é, x = B.x~. A representação xs (respectivamente, As) denota o vector (ou matriz) cujas componentes são dadas por xs[i] = sigi(x) (respectivamente, As[i,j] = sigj(A[i])), sigi o automorfismo de ordem i.

Igualmente, T é a matriz dos traços cruzados (T[i,j] = tr(bi.bj), bi,bj elementos de B, em que tr(.) denota o traço) e B' = T-1B é a base dual de B.

1. Escreva um programa em Pari que, dado um polinómio característico cp e, opcionalmente, uma base B, construa as várias componentes e funções descritas acima: Bs, T, T-1, B', Bs', (.)~,...

2. Considere a S-box de Rijndael usada no AES Rijndael S-box que define uma transformação afim g~(y~) = H y~ + b~. Usando as funções anteriores, reconstrua g(y) = b + h.xs, com =h = (H B')_s^t B.

3. Verifique que a sua implementação reflecte o facto 28 na página 184-185 dos apontamentos.

Prazo de entrega:

Os trabalhos deverão ser enviados por email até ao dia 20/7/2007.

-- PaulaCristinaValenca? - 11 Jun 2007