> For the complete documentation index, see [llms.txt](https://davidjosearaujo.gitbook.io/notes-miect/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://davidjosearaujo.gitbook.io/notes-miect/redes-e-sistemas-autonomos/qos-and-security/security/rsa-rivest-shamir-adleman-key.md).

# RSA (Rivest-Shamir-Adleman) Key

Each user generates the pair public/private key.

Randomly generates 2 large prime numbers - **p**, **q**.

Calculates the modulus of the system **N**=**p**.**q**.

* ø(N)=(p-1)(q-1)

Selects a random key **e**

* Where 1<**e**<ø(**N**), gcd(e,ø(**N**))=1 gcd = greatest common divisor.

Solves the equation to find the key and deciphers **d**.

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

Publishes the public key: KU={**e**,&#x4E;**}**.

Maintains the private key to decipher: KR={**d**,**p**,**q**}.

## Example RSA

1. Selects prime numbers: **p**=17 & **q**=11.
2. Calculates **n** = pq =17×11=187.
3. Calculates ø(n)=(p–1)(q-1)=16×10=160.
4. Selects e : gcd(e,160)=1; chooses e=7
5. Determines d: **de**=1 mod 160 and d < 160: value is d=23 because 23×7=161= 160+1
6. Publishes public key KU= {**e**,**N**}={7,187}.
7. Maintains secret key KR={**d**,**p**,**q**} = {23,17,11}

## Use of RSA

To cipher the message M, the sender:

* Obtains a public key of the receiver KU={e,N}.
* Calculates: C=Me mod N, where 0≤M\<N.

To decipher C:

* Uses its private key KR={d,p,q}.
* Calculates: M=Cd mod N.

Message M has to be lower than the modulus N

* Message M = 88 (88\<N=187).
* Cipher: C = 887 mod 187 = 11 ; e=7.
* Decipher: M = 1123 mod 187 = 88 ; d=23.