Jump to content
triplexim32

RSA

Recommended Posts

triplexim32

alguém me poderia dar um exemplo básico de como funciona o RSA mas por cálculos?

Queria desde a geração de chaves até a encriptação e desencriptação.

Imaginemos:

Geração de chaves:

2 Números primos p = 23 q = 41

Multiplica-os e fica com a chave publica: PUB -> 23*41 = 943

A partir daqui nao percebo mais nada :S

O que é o e?


<

Share this post


Link to post
Share on other sites
KTachyon

N = P*Q

T = (P-1)(Q-1)

Escolhes um valor E, com 1 < E < T, em que E não tem nenhum divisor comum com T (excepto o 1, claro).

(N, E) é a tua chave pública.

Depois tens que achar um D, que podes iterar.

int i = 1;

while (1) {
    mT = (i * T) + 1;
    
    if (mT % E == 0) {
        D = mT / E;
    }

    i++;
}

Basicamente, (DE-1) % T == 0

(N, D) é a tua chave privada.

Basicamente a tua encriptação e desencriptação tem que ser feita em blocos inferiores a N. Sendo M a mensagem e C a mensagem encriptada, as operações são:

C = pow(M, E) % N

M = pow(M, D) % N

Agora, atenção a uma coisa. Em relação à encriptação e desencriptação, não vais conseguir fazer nada com inteiros ou longs. E, se as tuas chaves cabem em inteiros ou longs, provavelmente não são lá muito seguras.


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
triplexim32

obrigado pela ajuda, só não percebi uma coisa:

Escolhes um valor E, com 1 < E < T, em que E não tem nenhum divisor comum com T (excepto o 1, claro).

E é um numero primo entre 1 e T certo?

Esse while que ai é infinito, quando é que o devo parar? Faltou-te ai um break dentro do if certo?

como calculo isto:

pow(M, D)

Potencia de 2 numeros?  😲, dá-me um exemplo escrito desta operação


<

Share this post


Link to post
Share on other sites
KTachyon

obrigado pela ajuda, só não percebi uma coisa:

E é um numero primo entre 1 e T certo?

Não precisa de ser primo, apenas não pode ter divisores comuns com T. Por exemplo, tendo em conta o teu P e Q,

T = 22*40 = 880

A variável E podia ser, 9, 21, 27, 39, 49,... que não são primos, mas não tem divisores comuns com T.

Esse while que ai é infinito, quando é que o devo parar? Faltou-te ai um break dentro do if certo?

Exacto, faltou o break a seguir a definir o valor de D. Mas esse while é só um exemplo. Acredito que hajam formas mais saudáveis de encontrar um valor para D :)

como calculo isto:

pow(M, D)

Potencia de 2 numeros?  😲, dá-me um exemplo escrito desta operação

Sim, M^D, mas reparei que a fórmula para desencriptar a mensagem está errada. Seria:

M = pow(C, D) % N

Como exemplo:

N = 943

T = 880

E = 29 (por exemplo)

D = 789          //  == (880 * 26 + 1) / 29

M = 2

C = 2^29 % 943

C = 536870912 % 943

C = 266

M = 266^789 % 943

Percebes agora porque é que inteiros ou longs não chegam? :)

Basicamente, se tudo correu bem, M vai dar 2.


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
triplexim32

Só uma questão:

Como faço o equivalente a RSA 1024bits?

1024bits é o que em concreto?

Sei que é o tamanho da chave privada, mas em que termos?


<

Share this post


Link to post
Share on other sites
mjamado

Só uma questão:

Como faço o equivalente a RSA 1024bits?

1024bits é o que em concreto?

Sei que é o tamanho da chave privada, mas em que termos?

Em bits. :cheesygrin:

Teoricamente, corresponde a 128 caracteres ASCII.


"Para desenhar um website, não tenho que saber distinguir server-side de client-side" - um membro do fórum que se auto-intitula webdesigner. Temo pelo futuro da web.

Share this post


Link to post
Share on other sites
triplexim32

Em bits. :cheesygrin:

Teoricamente, corresponde a 128 caracteres ASCII.

E como faço isso?

Aumentando o tamanho de N (visto ser usado para encriptar junto com E)?

Ou tenho que gerar mais números primos, expoentes, etc, ou seja: fazer várias vezes o mesmo.

Tou confuso  :confused:


<

Share this post


Link to post
Share on other sites
KTachyon

Quanto maior for o N, maior é a chave de encriptação, é um facto. Se não me engano, existe uma gama de valores primos que te permite gerar chaves suficientemente grandes. Mas repara que o E pode ter muitos valores diferentes para os mesmos números primos, só que tem que ser menor que T. Relativamente a "acertar" no tamanho exacto, já terás que ser tu a investigar. Penso que existe bastante material que explica a matemática por detrás da geração de chaves com determinado tamanho.

Outras clarificações: Pela formula, podes mesmo escolher o E fazendo T-1. Mas o ideal é sempre escolheres qualquer valor aleatoriamente. Valores muito baixos de E não são, de todo, recomendados, por isso convém evitar.

E, chaves de 1024-bit já não são exactamente consideradas seguras. As recomendações actuais já indicam que o mínimo tamanho para as chaves deve ser 2048-bit.


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
triplexim32

Mas se eu quisesse gerar RSA 1024bts o que teria que fazer ao certo no algoritmo discutido acima?


<

Share this post


Link to post
Share on other sites
KTachyon

Primeiro precisas de um objecto capaz de aguentar 1024-bit, ou seja, 128 bytes. Um int aguenta 4 bytes e um long long 8 bytes, claramente não servem para o que pretendes. Esse objecto tem que permitir operações aritméticas e de comparação, de modo a que possas efectuar os cálculos que foram discutidos sobre esses valores.


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
triplexim32

Mas isso também requer números primos com tamanhos maiores?


<

Share this post


Link to post
Share on other sites
KTachyon

Yep.


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
Rui Carlos

Uma estratégia para gerares uma chave de 1024 bits é gerares um primo de 512 bits, e depois ires gerando primos de 512 bits e 513 bits até que encontres um que multiplicado pelo primeiro dê um valor de 1024 bits.

Ao fim de duas ou três tentativas já deves ter um número com as propriedades pretendidas.

Share this post


Link to post
Share on other sites
triplexim32

Eih cum carago :D

Bem ja deu para matar a curiosidade, vou ver se faço isto de outra forma  :confused:

Obrigado a todos pela ajuda


<

Share this post


Link to post
Share on other sites
triplexim32

Só mais uma questão:

Com estes dados quantos bits terão a minha chave e como vejo isso?

p = 308567919282384537389260800962022473770

q = 215347206174966580671239468406232093236

n (sendo p*q)

66449239332684108886057690750699673312641170420254732937003606689030258986727

Apesar de achar que ha aqui qualquer coisa mal com estes números primos oO


<

Share this post


Link to post
Share on other sites
pedrosorio

Confesso que não sei nada de encriptação, mas esse n cabe num inteiro (sem sinal) de 256 bit pelo que se a chave é um par com n e outro inteiro da mesma ordem de grandeza, deves precisar de 512 bit.

EDIT: A razão pela qual digo que cabe num inteiro de 256 bit é porque o seu logaritmo de base 2 é ~255.2


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
triplexim32

yah tens razão, fiz um algoritmo para analisar o tamanho dos bits usados, porem q com o logaritmo era mais fácil  :P

Tou confuso perante a geração de chaves RSA porque procuro números primos gigantes que dêem chaves de 128bytes, 256bytes e afins para criar RSA 1024bits, 2048, 4080... (não sei ao certo o bytes standard do RSA, mas é +/- isto) e não existem, até agora só descobri meia dúzia de números primos com uma carrada de dígitos: http://www.bigprimes.net/archive/mersenne/ mas são poucos.

Desconfio que há outra maneira de gerar chaves grandes : D

Com openssl já gerei chaves de 6000bytes, portanto se o openssl consegue eu tambem queria conseguir : (


<

Share this post


Link to post
Share on other sites
triplexim32

Normalmente geram-se números aleatórios, e verifica-se se são primos usando o algoritmo de Miller-Rabin, por exemplo.

E como é que arranjo N tal que N de para 1024bits?

Esta-me a falhar alguma coisa em concreto?


<

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.