Codiﬁcação de Informação 2010/2011 - orium.pworium.pw/univ/lei/ci/slides/C9-16Nov2010.pdf · • Baseado na diﬁculdade de calcular o logaritmo discreto ... • Rivest, Shamir

11/16/10

1

CodificaçãodeInformação2010/2011

Sumário:• Criptografiadechavepública

Tiposdechave:cifrassimétricas

Dept.InformáGca/FCT 16Novembro2010 2

• Chavecomumàoperaçãodecifrarededecifrar

• Chavesecreta Pmensagememclaro,Cmensagemcifrada

Kchaveusadaparacifraredecifar

ffunçãousadaparacifrar

f‐1funçãousadaparadecifrar

C=f(K,P)

P=f‐1(K,C)

11/16/10

2

Tiposdechave:Cifrasassimétricas


• KpChavepúblicaparacifrar• KsChaveprivadaparadecifrar• EstaschavesestãoligadasaumadeterminadaenGdadecomaqual

sequercomunicar

KpdiferentedeKs

ffunçãoparacifrarf‐1funçãoparadecifrar

Estasfunçõesexigemnormalmentetemposdeexecuçãomuitomaislongosdoqueasfunçõesusadasnaschavessimétricas

C=f(Kp,P)

P=f‐1(Ks,C)

Criptografiadechavesecreta


• Acriptografiadechavesecreta/únicausaapenasumachave

• ParGlhadapeloemissorepeloreceptor

• SeachaveédescobertaascomunicaçõesestãocompromeGdas

• Ésimétrica,osintervenientessãopares

• Assim,nãoprotegeoemissornocasoemqueumintrusoforjaumamensagemedeclaraqueestaprovémdoemissor

11/16/10

3

Desvantagenschavesimétrica

• Problemadedistribuiçãodechaves

• Chavedeveseralteradacomumacertafrequência

• AlgoritmosdeassinaturadigitalqueuGlizamchavessimétricasnecessitamdechavesgrandesoquecomplicaaindamaisoproblemadadistribuiçãodechaves.


Criptografiadechavepública


• ProvavelmenteoavançomaissignificaGvoem3000anosdecriptografia

• NSA(US):1960’s(?)

• CESG(UK):1970• JamesEllis,relatórioclassificado

• CESGnãoviuaspotencialidades

• Diffie&Hellman:1976

• RSA:1978(1ªrealizaçãopráGca)

• Usaduaschaves–umapúblicaeoutraprivada

• AssimétricaporqueosparGcipantesnãotêmomesmopapel

• NãosubsGtuimascomplementaacriptografiadechavesecreta

11/16/10

4



• Acriptografiadechavepública/duas‐chaves/assimétricaenvolveousodeduaschaves:

• achave‐pública,queéconhecidadetodos,epodeserusadaparacifrarmensagens,everificarassinaturas

• achave‐privada,conhecidasópeloreceptor,usadaparadecifrarmensagens,eassinar(criar)assinaturas



• Éassimétricaporque:

Aquelesquepodemcifrarmensagenseverificarassinaturasnãopodemdecifrarmensagensecriarassinaturas

11/16/10

5



Porquêacriptografiadechavepública?


• Desenvolvidapararesolverduasquestões:• Distribuiçãodechaves–comotercomunicaçõessegurassemterquetrocarachavenarede

• Assinaturasdigitais–comoverificarqueumamensagemchegouintactadoemissor,equeesteéquemdizser

11/16/10

6

CaracterisGcasdacriptografiadechavepública


• DependededuaschavesquedevemterasseguintescaracterísGcas:

• Computacionalmenteimpossívelconhecerachaveparadecifrarsabendoapenasoalgoritmoeachaveusadaparacifrar

• Computacionalmentefácilcifrar/decifrarmensagensquandoachavecorrectaéconhecida

• Opapeldasduaschavespodesertrocado

Segurançadesistemascomchavepública


• Ataquesdeforçabrutaporprocuraexaus@vasãoteoricamentepossíveis

• Masaschavessãodemasiadograndes(>512bits)

• Segurançabaseia‐senumasuficientementegrandediferençaentreafacilidadeemcifrar/decifrareadificuldadeemfazeracripto‐análise

• ObterachaveprivadaaparGrdachavepúblicaépossívelteoricamente,masdemasiadamentepesadocomputacionalmenteparaserpossívelnapráGca

• Osmétodosconhecidosparacifraredecifrarmensagenssãocomputacionalmentebastantespesado.Assimsendo,sãolentosquandocomparadoscomosmétodosdechavesecreta

11/16/10

7

Cifraassimétrica• ComunicaçãoAliceparaBob

• Bobcalculaopar(KPB,KSB)– KSBémanGdosecreto,KPBépublicado(porexemplonapáginawebdoBob)

• Alice– ObtémachavepúblicaKPBdeBobe,– cifraamensagemPcomachaveKPBdoBob

C=cifra_assimétrica_E(KPB,P)

• Bob– UsaachaveprivadaKSBdoBobparadecifrarC: P=cifra_assimétrica_D(KSB,P)


Aplicaçãoàassinaturadigital


• Procedimento:

• Alice• Geraumresumo(digestouhash)h=h(m)damensagem

• CalculaumaassinaturasparamusandoasuachaveprivadaKPA: s=RSA_D(KSA,h)

• EnviamesaBob

• Bob• Calculah=h(m)aparGrdem

• Decifrah’=RSA_E(KPA,h)usandoachavepúblicadeAlice• Verificaseheh’sãoiguais

• GaranGdaaautenGcidadedoemissoreaintegridadedamensagem

11/16/10

8

Escolhadoalgoritmo


• Tempodeexecuçãodeumalgoritmo

• Dependedadimensãodoproblema

• Exemplo:Ordenar10númeroslevamenostempoqueordenar10000números

• Paraalgunsproblemassabe‐seonúmerodepassosquequalqueralgoritmolevaaresolverumproblemacomnelementos

• Ordenarnnúmeroslevanlognpassos

Escolhadoalgoritmo


• Énecessárioumproblemaquenecessitedepelomenosumnúmeroexponencialdepassos

• Sãoconhecidosproblemasemqueassoluçõesconhecidaslevamtempo(sub)exponencial

• Factorizarprimos

• Calcularologaritmodiscreto

• ...

11/16/10

9

TrocadechavesdeDiffieHelman


• InventadoporDiffie&Helmanem1976• Primeirapublicaçãosobrecriptografiadechavepública

• MétodopermitequedoisuGlizadoresconcordemnumachavesimétricadeformasegura.Essachaveédepoisusadaparacifrar/decifrarasmensagens

• Sóparatrocadechaves• NãouGlizadoparacifrar/assinar

• Chavesde1024bits• Baseadonadificuldadedecalcularologaritmo

discreto

Logaritmosdiscretos


• EmaritméGcamódulop:

• araizprimi0vadeumnúmeroprimopéovaloratalqueassuaspotênciasgeramtodososinteirosde1ap‐1

• SeaéraizprimiGvadep,osnúmerosamodp,a2modp,…,ap‐1modpsãodisGntosecorrespondemaumapermutaçãodosnúmerosde1ap‐1

• ParaqualquerinteirobeumaraizprimiGvaadeumnúmeroprimop,pode‐seencontrarumitalque

• b=aimodp(emque0<=i<=p–1)

• béologaritmodiscretomódulopparaabasea

11/16/10

10

Logaritmodiscreto


• Computaçãomódulon

• Exemplomódulo13

171059111263842

121110987654321i

2éraizprimiGvade13(módulo13)

b=2imod13

b=aimod13

b

MétododeDiffieHellman


• TodososuGlizadoresconcordamnosseguintesvalores:

• Umnúmeroprimoqmuitogrande

• αéumaraizprimiGvadeq(emmóduloq)

• CadauGlizador(eg.A)geraasuachave• Escolheumachavesecreta(número):xA < q

• Calculaasuachavepública:yA = αxA mod q

• CadauGlizadorpublicaasuachavepúblicayA

11/16/10

11

ChavesdeDiffieHellman


Elementosglobaisq,α

GeraçãodechaveSeleccionarXA<qCalcularYA=αXAmodq

K=(YB)XAmodq

GeraçãodechaveSeleccionarXB<qCalcularYB=αXBmodq

K=(YA)XBmodq

UGl.A UGl.B

YA

YB


ChavesdeDiffieHellman

11/16/10

12

TrocadechavesdeDiffieHellman


• AchaveparGlhadaparaumasessãodosuGlizadoresA&BéKAB:

• KAB = αxA.xB mod q

• = yAxB mod q (que B pode calcular)

• = yBxA mod q (que A pode calcular)

• KABéusadacomochavedesessãonumacomunicaçãoentreAliceeBob

• KABpodeserusadanoutrassessõesentreAliceeBob

• Umintrusonecessitaumdosx;paraissotemdecalcularumlogaritmodiscreto,oqueécomputacionalmentemuitodi|cil

PorqueéqueD‐Hfunciona?


K = (Yb)xa mod q =

= (axb mod q)xa mod q =

= a xb.xa mod q =

= (axa mod q)xb mod q=

= (Ya) xb mod q

11/16/10

13

ExemplodeDiffieHelman


• OsuGlizadoresAliceeBobqueremtrocarchaves:• Concordamnoprimoq=353eα=3

• Seleccionamaoacasoaschavessecretas:• AescolhexA=97, BescolhexB=233

• Calculamaschavespúblicas:• yA=3

97 mod 353 = 40 (Alice)

• yB=3233

mod 353 = 248 (Bob)

• Calculamachavedesessão:• KAB= yB

xA mod 353 = 24897 = 160 (Alice)

• KAB= yAxB mod 353 = 40

233 = 160 (Bob)

SegurançadeDiffieHellman


• XAeXBsãoprivadas;ointrusoconheceq,α, YA, YB

• Parafuraracifraéprecisocalcularologaritmodiscreto

XB=logaritmodiscretoα,q(YB)

• Éfácilcalcularexponenciaismódulop,masémuitodi|cilcalcularlogaritmosdiscretos

11/16/10

14

RSA


• Rivest,Shamir&AdlemandoMITem1977

• EsquemadechavepúblicamaisbemconhecidoemaisuGlizado

RSA


• BaseadoemexponenciaçãodeinteirosusandoaritméGcamodular

ExponenciaçãolevaO((logn)3)operações(fácilcifrar/decifrar)

• Usainteirosmuitograndes(eg.1024bits)

• Segurançadevidaàdificuldadeemfactorizarnúmerosprimosmuitograndes

FactorizaçãolevaO(elognloglogn)operações(muitodi|cilobterachaveprivadaaparGrdachavepública)

11/16/10

15

GeraçãodechavesRSA


• CadauGlizadorcalculaumparchavepública/chaveprivada

• Selecciona2númerosprimosaleatoriamente‐p, q

• CalculaN = p.q ø(N)=(p-1)(q-1)

• Seleccionaachavedecifrae quedevecumprir:

1<e<ø(N), gcd(e,ø(N))=1 • Resolveaequaçãoseguinteparadeterminarachaved

(e.d)mod ø(N)=1 e 0≤d≤N

• Publicaasuachavepública:KP={e,N}• Mantémsecretaasuachaveprivada:KS={d,N}

UsodoRSA


• ParacifraramensagemM,oemissor:

ObtémachavepúblicadoreceptorKP={e,N}

Calcula:C=Me mod N,emque0≤M<N

• ParadecifrarotextocifradoCodesGnatário: usaasuachaveprivadaKS={d,N}

calcula:M=Cd mod N

• Note‐sequeMtemdesermenorqueomóduloN(divide‐seotextoemblocosdexbits,talque2x<Neomaiorpossível)

11/16/10

16

PorqueéqueoRSAfunciona?


• TeoremadeEuler:aø(n)mod N = 1

• emquegcd(a,N)=1

• NoRSAtemos:• N=p.q • ø(N)=(p-1)(q-1)• Escolhem‐see&dparasereminversosmod ø(N)

• Portantoe.d=1+k.ø(N)paraalgumk

• Assimsendo(sempreemaritméGcamod N) Cd mod N = (Me)d mod N = M1+k.ø(N) mod N =

M1.(Mø(N))k mod N = M1.(1)k mod N =

M1 mod N = M

ExemploRSA


• Seleccionarprimos:p=17 & q=11

• Calcular n = pq =17×11=187

• Calcular ø(n)=(p–1)(q-1)=16×10=160

• Seleccionare:gcd(e,160)=1; escolhere=7

• Determinard:de=1 mod 160ed < 160; d=23umavezque23×7=161

• PublicarachavepúblicaKU={7,187}

• GuardarachaveprivadaKR={23,187}

11/16/10

17


ExemploRSA

• Exemplodafasedecifrar/decifrardoRSA:

• DadaamensagemM = 88(note‐seque88<187)

• Cifrar:

C = 887 mod 187 = 11

• Decifrar:

M = 1123 mod 187 = 88

Outroexemplonãorealista


11/16/10

18


Exemplomaisrealista(1)p e q têm 512 bits a que corresponde cerca de 160 dígitos decimais; n e Φ têm 309 dígitos


Exemplomaisrealista(2)p e q têm 512 bits a que corresponde cerca de 160 dígitos decimais; n e Φ têm 309 dígitos

THIS IS A TEST passa a C = Pe mod n

THIS IS A TEST P = Cd mod n

11/16/10

19

AspectoscomputacionaisdoRSA


• Geraçãodachave• Exponenciação

• PeeCdpodemproduzirresultadosintermédiosgigantescos

• PropriedadesdaaritméGcamodular

[(a mod n) * (b mod n)] mod n =

(a * b) mod n

• Podem‐seproduzirresultadosintermédios

GeraçãodachaveRSA


• OsuGlizadoresdoRSAtêmde:

• determinardoisprimosaoacasop, q

• Seleccionareoudecalcularooutro

• Osprimosp,qnãopodemserdeterminadosfacilmenteaparGrdeN=p.q

• Têmdesersuficientementegrandes

• Nãohámétodosdirectosparadeterminarprimosmuitograndes;Gpicamenteusam‐senúmerosaleatóriosetestesde“primalidade”.Essestestesnãogarantemqueonúmerosejaprimo

11/16/10

20

GeraçãodachaveRSA–algoritmoMiller‐Rabin


1. Obterumnúmeroímparnaoacaso

2. Obteroutronúmerointeiroaoacaso(1< a < n)

3. Aplicaraaen umteste;seotestefalha,rejeitaronúmeroeirpara1

4. Senpassouoteste3paraumnºsuficientementegrandedetentaGvasaceitarn

5. AteoriadosnúmerosdizqueosnúmerosprimospertodeXestãoespaçadosdelnX;logoparadeterminarumprimoserãonecessáriasln(N)/2tentaGvas

AlgoritmoparaotestedeprimalidadeprobabilisGcadeMiller‐Rabin

Miller-Rabin(n,t)

INPUT: An odd integer n > 1 and a positive security parameter t

OUTPUT: the answer "COMPOSITE" or "PRIME" Write n - 1 = 2sr such that r is odd Repeat from 1 to t Choose a random integer a which satisfies 1 < a < n - 1 Compute y = ar mod n IF y <> 1 and y <> n-1 then DO j := 1 WHILE j < s and y <> n - 1 then DO y := y2 mod n IF y = 1 THEN return("COMPOSITE") j := j + 1 IF y <> n - 1 THEN return("COMPOSITE") return("PRIME")


11/16/10

21

SegurançadoRSA


• TrêsabordagensparaatacaroRSA:

• Forçabrutasobreachave(impossíveldadoonúmerodebitsdachave)

• Baseadosnateoriadosnúmeros(tentaGvadefactorizaromóduloN)

• Pormedidadotempoquedemoraacorreroalgoritmoparadecifrar

Problemadafactorização


• Trêsformas:

• factorizarN=p.q,encontrarø(N)edepoisd• determinarø(N)ouddirectamente

• Pensa‐sequetodoselessãoequivalentesafactorizar:• Melhoriaslentasaolongodosanos

• EmAgostode1999conseguiu‐sefuraroRSAcom130dígitosdecimais(512bits)usandooalgoritmo“GeneralizedNumberFieldSieve”

• HojeemdiaasegurançaégaranGdausandochavesentreos1024e2048bits

Documents

Codiﬁcação de Informação 2010/2011 - orium.pworium.pw/univ/lei/ci/slides/C9-16Nov2010.pdf · • Baseado na diﬁculdade de calcular o logaritmo discreto ... • Rivest, Shamir