Sessões laboratoriais de EC

5ª feira, 14:00-16:00, DI 1.04

23/02/2006 - Apresentação

Apresentação e inscrição nos turnos.

02/03/2006 - Introdução ao ao PARI/GP

PARI-GP

• Web page
• Instalação:
  1. Download do programa (da página web)
  2. Na dictoria source: ./Configure --prefix=$HOME/pari
  3. make; make install
  4. export PATH=$HOME/pari/bin:$PATH
  5. gp
• Reference Card

Problemas simples:

Funções simples em aritmética modular:

• Defina uma função que determine o inverso multiplicativo de x\in Zn (note que pode não existir).
• Defina uma função que determine o grupo multiplicativo Zn*.
• Modifique a função anterior para que, a cada elemento de x\in Zn*, associe o sub-grupo cíclico gerado por x.

09/03/2006 - Aritmética Modular e RSA

As seguintes funções do PARI/GP vão ser uteis nesta sessão: eulerphi, gcd, bezout, chinese, prime, isprime, ispseudoprime, random. Recomenda-se portanto uma leitura rápida da documentação disponibilizada pelo GP (e.g. ?eulerphi, ou para mais detalhe ??eulerphi).

• Utilize a função bezout para calcular o inverso multiplicativo de x\in Zn.
• O teorema chinês dos restos permite resolver um sistema de equações {x = ai [ni]} quando os valores ni são primos entre si dois a dois. Como poderá explorar esse resultado (e função respectiva do GP) para resolver o seguinte sistema de equações?
  • 13 x = 4 [99]
  • 15 x = 56 [101]
• Codifique uma função que gere aleatóriamente um número primo (o número de dígitos é passado como argumento).
• Pretende-se codificar o algoritmo RSA. Para tal deverá realizar três funções:
  • rsa_setup, que recebe como argumento o número de dígitos da chave e retorna como resultado o par de chaves.
  • rsa_enc, que recebe como argumento a chave pública e o texto limpo, e retorna o criptograma.
  • rsa_dec, que recebe como argumento a chave privada e o criptograma, e retorna o texto limpo.

16/03/2006 - Ataques ao RSA

• Correcção do RSA (i.e. x=rsa_dec(rsa_enc(x,pubKey),privKey))
• Alguns ataques ao RSA:
  • Factorização do módulo
  • Codebook
  • Módulo comum
  • Expoente baixo

Trabalho 1: Cifra RSA

Deverá desenvolver uma script PARI/GP que implemente o algoritmo RSA assim como os ataques estudados a essa cifra. Deve procurar tornar o seu código o mais eficiente possível e não esqueça de incluir comentários por forma a tornar inteligível a sua leitura. Inclua também exemplos que ilustrem as funcionalidades implementadas.

• Algumas referências:
  • High Speed RSA implementation (pdf)
  • http://www.rsasecurity.com/rsalabs

Prazo de entrega:

Os trabalhos deverão ser enviados por email até ao dia 30/3/2006.

Desafios:

Tente recuperar o texto limpo correspondente a cada um dos seguintes criptogramas obtidos com a cifra RSA. Os textos limpos são em Português. 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 e codificado sob uma base b: cada bloco Li ... L1 L0 é codificado no inteiro Li*(b^i) + ... + L1*b + L0. Para valores de base b adoptam-se alternativamente o 26 (só se codificam as letras, omitindo-se do texto limpo espaços, dígitos e pontuação) ou 255 (código ascii). 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 as scripts de código que produzir, o texto limpo que recuperou e uma explicação de como procedeu para resolver o problema.

Importante: note que certos números são apresentados em várias linhas.

• Problema 1
  • i = 9; b = 255
  • e = 17
  • n = 1249041700673382695459846605609514730554186626237
  • C = 321180546341126455980279730178761953097183911234, 716950862594240028452266734363072497454521223524, 574948179391147816051505896812694387194959833965, 111532735643033423942855061239383848643971241832
• Problema 2 - Uma mesma mensagem M foi cifrada para três destinatários distintos resultando em C1, C2 e C3. Os parâmetros utilizados foram:
  • i = 29; b = 26
  • e1 = e2 = e3 = 3
  • n1 = 7339811139556615823122116433204023904398461533454681143699547686798 95395710761486433977041087334202131031022237869598972234480380246 70748019733228699398088635793210311345924939173837819595011974404 1458944308322479035696269545435389
  • n2 = 10551118842387729281629728443352288086734202318038326556978629363 87643461149599232735810295170139939550508599355640349872906993902 86287424947045202026909343965313253370799066569052047150238445288 9783863513694420141935182919987207969
  • n3 = 66787488008015564075615898071345013083744411800144184623626939980 95523632027297575911308308620562384855840269609220415026029449041 06785572985937898110504326376313806658941820172438404052482076621 471581424529754975069348027227843883
  • C1 = C2 = C3 = 1397942583169351242004858195909208100459634258305080963095015127 6016199568460358374777794775331783767638927484305527216576
• Problema 3
  • i = 6; b = 26
  • e = 3
  • n = 6391470411061826399294574162150528765326145415479599749142416894309248161455 17449512309787590608539069992632564642773771493135705574804621403767304660931 39279042063802231438893958813649137968723832554178514469387083227792295356047 773281856489868696857456780247422046270127054298844870602475384663637199209513
  • C = 350915208109496145856, 27661335465828884684696, 31802586529207976000000, 494171409093635852161856, 407524745047362736519656
• Problema 4
  • i = 6; b = 26
  • e = 7
  • n = 6391470411061826399294574162150528765326145415479599749142416894309248161455 17449512309787590608539069992632564642773771493135705574804621403767304660931 39279042063802231438893958813649137968723832554178514469387083227792295356047 773281856489868696857456780247422046270127054298844870602475384663637199209513
  • C = 32043924526870920534079392028726370777600000000000000, 19306983940121876610266501070351375064373302782143184896, 868570571278402253220237877279110105219431120896, 74155878556235370096776829384639812609423519551832064
• Problema 5
  • i = 2; b = 255
  • e = 65537
  • n = 1726120091695287336748214486649445090936069756304670744586344362 7091875871740773679233823099712178179358393710196331449844554301 4908468113510758146965296371923698514351552479129463911417817582 4625618889392815511799802366562518515699589132221215938849844735 5096970990510996522873761394696658254094897711248116842246989910 7296684641515320426052691201842320489808621103968851915391479179 3882292176416407903400284274126479429182876522757014113844850087 4109634833892704185454278081338756835822183447573030032642382069 9701757863403235839486294252564058181653989667152484099706921850 32883713278510782005243891336381732676319
  • C[1] = 24492930461896806666688173882443022616341159620904080632491569436 7295145339095154833512450776182636128906766811185274784571366871 5685446002101094904530116176935207126568628230394824693756357468 9261047349588164141823782249091399369881959924516838772369936845 6178403800744692450942825063850358385773429812281228364234067068 2966160669194758123590741440347700009229641826750858540071813978 4579339767379068752950816183878537919228732555913818070867153795 3523665490905907614866228501723203815974064273868106451196543778 3726120453598788613098120872934914753911015457148044860816498106 559653875138348551486855579718238577296
  • C[2] = 1673366376448871596834627029054078736527949106585297997884439572 3773007701671233121396405519318355002837431067518086946826468284 3164992255899700683067117772718526650944025177933368337844768808 0834168210617200696150674134650143117386345449740059114962289307 4654123612602714960248641487702147193379776782836852929079119885 5212422362455070495259827227866489717433246635381324670887164118 6174496983301260624395049965468369272669276130211823362733002054 2788531705808012398283863718970174343311709203322443500718670680 2267624433909804125958755325226693899085860632774554753505434457 20507641793760440454760670110940875121791
  • C[3] = 1009557433344333314360404743038565945317821467070447532549243230 3878307928053154605638345591744954830780686496595727400596980725 4321478131207133963656485184082856670301082572342552334483706159 3276231401353103303555517747531454878970806884252859219815552914 3758622279549415242939815639605656673456329775443214294573443307 8601281807812205702602324008031056043549943192686051508230988156 5754602890773743408303118668137610226439806239927350648656953791 7202280729731869297259949666668440955811850114951235592250187630 8392588068633391439720694009281517401379251236662907013551667695 82935586604497186521569909715340689722407
  • C[4] = 2595944282196925660346361344016834221714875708717882928563301267 0806390872492698924869258912202307062233476648921193467957186861 7622115206265627572866783529243022624764399217250406274747538630 1845744177858816858088801989504849945704230101564449954861207222 4302056289796661364171462503977839320178723251689596138484149268 7838331843894538827787015113544491039314664949468604795293046259 5281731836325876587905207436645681310571047659855208952688092662 3757899176343148108453497191678793051769451465654898953776332957 3789789306423112835137649021905465440915667649375142340394028855 8726225138165891059222334474716695244217

23/03/2006 - Técnicas baseadas no Log. Discreto

Pretende-se implementar algumas técnicas baseadas no problema do Logaritmo Discreto, nomeadamente o acordo de chaves Diffie-Hellman e a cifra El Gamal.

• Codifique procedimentos que:
  • gere primos de Sophie Germain (i.e. q tal que 2*q+1 também é primo).
  • um gerador do grupo multiplicativo Zp* (em que p=2*q+1). Utilize o facto que g\in Zp* é um gerador se g^2!=1[p] e g^q!=1[p].
  • um gerador de um sub-grupo de Zp* de ordem q (onde p=2*q+1).
• Implemente as seguintes técnicas (incluindo a geração dos parâmetros):
  • Acordo de chaves Diffie-Hellman,
  • Cifra ElGamal

23/03/2006 - (16:00-18:00 - substituição da aula de 30/03/2006)

Aula de acompanhamento ao primeiro trabalho prático.

06/04/2006 - (JOIN06)

JOIN'06

20/04/2006 - Corpos Finitos

Pretende-se implementar algumas funções de manipulação de Corpos Finitos em Pari/GP. Para tal far-se-á uso da habilidade desse sistema possibilitar a manipulação directa de polinómios.

• Utilize o PARI/GP para:
  • Determinar se x^5-x é divisível por x^2+1 em GF(3)
  • Calcular a factorização de x^9-x
  1. OBS: Note que funções bem conhecidas como gcd, factor admitem polinómios como argumentos. Existem também funções específicas para manipulação de polinómios como polisirreducible, factormod, polrootsmod, etc. -- consulte o help (?7).
• Defina uma função que calcule todos os polinómios primitivos do corpo finito GF(m) (com m=p^n e p primo). Determine os polinómios promitivos de GF(9) e GF(81). [RELEMBRE: um polinómio f(X) diz-se primitivo em GF(p^n) se tiver grau n e se o menor inteiro k para o qual f(X) divide x^k-1 for p^n-1.]
• Defina as operações do corpo finito com m=p^n elementos (p primo) visto como GF(p)[X]/<f(X)> onde f(X) é um polinómio primitivo de grau n com coeficientes em GF(p).

Informação adicional relativa a corpos finitos: http://eom.springer.de/g/g043140.htm, http://eom.springer.de/G/g130010.htm.

27/04/2006 - ElGamal sobre GF(2^n)

• Implemente a cifra ElGamal sobre o corpo finito GF(2^n). (obs.: para n suficientemente grande, as funções realizadas na aula anterior para encontrar o polinómio primitivo não irá funcionar. Para tal deve consultar a tabela de polinómios primitivos disponibilizados em P1363-AnexoA).

Algumas funções úteis para converter inteiros em polinómios binários...

\\assume-se que o polinómio "p" está definido sobre a variável "x"!!!
poleval(y,p) =
{
  local(x=y);
  return (eval(p));
}

pol2int(p) = poleval(2,lift(lift(p)))

int2pol(v) = 
{
  local(dr,i,res,p);

  dr=divrem(v,2)~;
  res = 0;
  p = 0;
  dr = [v,0];
  until(dr[1] == 0, dr=divrem(dr[1],2)~; res += Mod(dr[2],2)*x^p; p++);

  return (res);
}

Trabalho 2: Cifra ElGamal e Acordo de Chaves Diffie Hellman

Deverá desenvolver uma script PARI/GP que implemente o acordo de chaves Diffie Hellman e a cifra ElGamal nos seguintes grupos:

1. Sub-grupo de ordem elevada de Zp.
2. No corpo finíto GF(2^n).
3. Numa curva elíptica sobre GF(p).

Deve procurar tornar o seu código o mais eficiente possível e não esqueça de incluir comentários por forma a tornar inteligível a sua leitura. Inclua também exemplos que ilustrem as funcionalidades implementadas.

Prazo de entrega:

Os trabalhos deverão ser enviados por email até ao dia 8/6/2006 (actualizado em 25/5/2006).

04/05/2006 - Palestra de Tatjana Weltzer

Palestra Data Reusability (DI-A2).

11/05/2006 - A segurança semântica de primitivas criptográficas

Aula sobre definição de segurança das primitivas criptográficas. Demonstração da segurança semântica do El Gamal (pelo prof. Manuel Barbosa).

18/05/2006 - Enterro da Gata

Tolerância de ponto: Enterro da Gata.

25/05/2006 - Curvas Elípticas sobre Corpos Finitos

Aula sobre os fundamentos de técnicas criptográficas baseadas em Curvas Elípticas. No sistema PARI-GP, faremos uso das funções dedicadas às curvas elípticas, em particular ellinit, ellisoncurve, elladd, ellpow.

• Siga o tutorial disponível em http://www.certicom.com/index.php?action=ecc_tutorial,home sobre intuição geométrica das curvas elípticas.
• Replique, em PARI-GP, os exemplos apresentados no tutorial de curvas elípticas sobre corpos finitos GF(p). Obs.: O Pari-GP não suporta apropriadamente curvas elípticas sobre corpos finitos binários GF(2^n). Por esse motivo vamos considerar unicamentre curvas elípticas sobre corpos da forma GF(p) (p primo).
• Implemente o El Gamal e o DH em curvas elípticas sobre corpos GF(p). Para o efeito, pode utilizar os parâmetros gerados na página http://www.cryptomathic.com/labs/ellipticcurvedemo.html ou, ainda melhor, disponibilizados por um standard apropriado como http://www.secg.org/?action=secg,docs_secg. Obs.: A codificação directa do El Gamal em curvas elípticas pressupõe a codificação da mensagem em pontos da curva. Esta tarefa não é de todo imediata, motivo pelo qual não é normalmente utilizada essa técnica nessa forma em curvas elípticas (um segundo motivo prende-se com o facto de que essa técnica não ser segura face a ataques de criptograma escolhido). Uma forma de ultrapassar a operação de codificação da mensagem em pontos da curva é utilizar-se a versão Hashed El Gamal (c.f. aula de provas de segurança dada por prof. Manuel Barbosa).

Uma função de conversão que pode ser util:

hextodec(s)= \\s string
{local(v=Vecsmall(s), sett=Vec("0123456789abcdef"));
sum(i=0,#v-1,(setsearch(sett,Strchr(bitor(v[#v-i],32)))-1)*16^i)}

25/05/2006 - (16:00-18:00 - substituição da aula de 01/06/2006)

Aula de acompanhamento dos trabalhos práticos.