Um pequeno exemplo de Criptografia RSA

Considere a tabela abaixo:

A	B	C	D	E	F	G	H	I	J	K	L	M
10	11	12	13	14	15	16	17	18	19	20	21	22
N	O	P	Q	R	S	T	U	V	W	X	Y	Z
23	24	25	26	27	28	29	30	31	32	33	34	35

O primeiro passo é pré-codificar a mensagem. Para isto necessitamos trocar as letras pelos respectivos números desta tabela. Caso haja espaço entre duas palavras, usamos 99. Assim, por exemplo:
LUIZ FERNANDO fica: 21 30 18 35 99 15 14 27 23 10 23 13 24 e, portanto:

LUIZ FERNANDO

21301835991514272310231324      (I)

Agora, precisamos determinar os parâmetros do sistema RSA que vamos usar. Estes parâmetros são dois primos distintos, que vamos denotar por p e q. Ponha n = pq. A última fase do processo de pré-codificação consiste em quebrar em blocos o longo número produzido anteriormente (I). Estes blocos devem ser números menores que n. Vamos adotar p = 11 e q = 29. Assim n = 319 [Chave Pública] . Desta forma, podemos quebrar o bloco (I) da seguinte maneira (lembrando que esta quebra não é única):

2 - 130 - 183 - 59 - 91 - 51 - 42 - 72 - 3 - 102 - 3 - 132 - 4       (II)

Observe que não iniciamos nenhum bloco por zero e também nenhum deles corresponde a algum elemento da tabela.

Agora precisamos encontrar um inteiro positivo x tal que mdc(x,w(n)) = 1, onde w(n) = (p-1)(q-1).

Como adotamos p =11 e q = 29, temos que w(n) = 10.28 = 280.

Como 3 é primo e não divide 280, podemos adotar x = 3.

OBS: Chamamos o par (n,x) de chave de codificação. Para este caso a chave de codificação é (319,3).

Agora começa o processo de codificação. 

A ideia é pegar todos os blocos de (II), elevar a x (neste caso x = 3) e obter o resto da divisão por n (neste caso 319). Assim obtemos que:

Blocos	Blocos elevados a x (neste caso x=3)	Resto da divisão dos números da coluna anterior por n (neste caso 319)
2	8	8
130	2197000	47
183	6128487	178
59	205379	262
91	753571	93
51	132651	266
42	74088	80
72	373248	18
3	27	27
102	1061208	214
3	27	27
132	2299968	297
4	64	64

Desta forma, a mensagem codificada é:

8 - 47 - 178 - 262 - 93 - 266 - 80 - 18 - 27 - 214 - 27 - 297 - 64       (III)

A tarefa de codificação termina aqui.

Decodificação:
Agora, nossa tarefa é encontrar o inverso multiplicativo de x em w(n) que chamaremos de d. Para este caso, devemos encontrar o inverso multiplicativo de 3 em 280, isto é, o número d tal que a divisão do produto 3d por w(n) = 280 deixe resto 1 [3d = 280q + 1].

Chamamos o par (n,d) de chave de decodificação.

Através de uma planilha eletrônica, observamos que 3.187 = 561 = (280).2 + 1. Logo d = 187. 

Agora, a ideia é elevar cada bloco de (III) ao expoente d (neste caso 187) e encontrar o resto da divisão desta potência por n (neste caso 319).

Para exemplificar vamos tomar o 8 do bloco (III) e tentar decodificá-lo.

8 elevado a 187 é um número razoavelmente grande para fazermos manualmente. Para saírmos deste problema, vamos atacar da seguinte maneira:

Tente você agora decodificar alguns dos blocos (III).

Grande Abraço!!!