Re: [obm-l] o Livro dos Códigos

[Rodrigo Malta Schmidt <rodrigo.schmidt@xxxxxxxxxxxxx>]

Oi,

> 
> sejam, M,E,P e Q tal que P e Q sao primos e E é primo com (P-1)*(Q-1)
> 
> entao calcule:
> (M representa a mensagem original e C a mensagem cifrada)
> C=M^E (mod P*Q)
> 
> calcule D tal que:
> E*D=1 (mod (P-1)*(Q-1))

Supondo que D foi calculado. (mais adiante eu explico como)

> 
> entao prove que:
> M=C^D (mod P*Q)
> 
> alguém poderia me ajudar a demonstrar isso ??

Pelo Teorema de Euler:

" Se a e b sao primos entre si, entao 
     a^k = a^(k mod phi(b)) (mod b)  "

Entao, como phi(P*Q) = (P-1)*(Q-1) e

C^D = M^(E*D) (mod P*Q)

entao

M^(E*D) = M (mod P*Q)


> 
> no livro ele diz que D pode ser encontrado através do Algoritmo de Euclides
> .. alguém pode me dizer como é ??
> 

O Algoritmo de Euclides serve para calcular o mdc de dois valores.

Sua forma original eh a seguinte:

funcao mdc(a,b)
  se (b = 0)
     retorne a
  senao 
     retorne mdc(b,a mod b)


Eh sabido que o mdc de dois valores eh uma combinacao linear dos mesmos.
Existe um algoritmo conhecido como o algoritmo estendido de Euclides que
retorna esta combinacao linear, ao inves de simplesmente o valor do mdc:

mdc_estendido(a,b) retorna uma tripla <d,x,y>, onde d = mdc(a,b) e
d=ax+by

* no codigo abaixo, <-- significa atribuicao de um valor a uma variavel

funcao mdc_estendido(a,b)
  se (b=0)
     retorne <a,1,0>
  fim se
  <d',x',y'> <-- mdc_estendido(b,a mod b)
  <d,x,y> <-- <d',y',x' - piso(a/b) * y'>
  retorne <d,x,y>

A prova de corretude do 2o algoritmo sai por inducao:
(supondo a corretude do algoritmo de euclides original)

A base eh trivial (b = 0)

passo:

pela hipotese temos que d' = bx' + (a mod b)y'

Como d = d' (pelo algoritmo original de Euclides)

d = bx' + (a - piso(a/b) * b)y'
  = ay' + b(x' - piso(a/b) * y')


=========
Como calcular D no RSA

> E*D=1 (mod (P-1)*(Q-1))

D eh calculado pelo algoritmo de euclides, pela invocacao

<1,D,X> <-- mdc_estendido(E,(P-1)*(Q-1))

Sabe-se que E eh primo relativo de (P-1)*(Q-1), entao mdc = 1; e para os
fins do RSA, o valor X retornado pode ser desprezado, ficando-se com o
D.

Espero ter ajudado,
Rodrigo


> muito obrigado ..
> 
> "Mathematicus nascitur, non fit"
> Matemáticos não são feitos, eles nascem
> ---------------------------------------
> Gabriel Haeser
> www.gabas.cjb.net
> 
> ------------------------------------------
> Use o melhor sistema de busca da Internet
> Radar UOL - http://www.radaruol.com.br
> 
> =========================================================================
> Instruções para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
> O administrador desta lista é <nicolau@mat.puc-rio.br>
> =========================================================================
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================