# RSA (Rivest Shamir Adleman)

RSA is a public-key cryptosystem that is widely used for secure data transmission.

### RSA Algorithm in Python <a href="#rsa-algorithm-in-python" id="rsa-algorithm-in-python"></a>

Reference: <https://medium.com/@gowtham180502/implementing-rsa-algorithm-using-python-836f7da2a8e0>

```shellscript
from Crypto.Util.number import getPrime, long_to_bytes
from math import gcd # for greatest common divisor

class RSA:
    def __init__(self):
        # p, q (large prime numbers)
        self.p = getPrime(512)
        self.q = getPrime(512)

        # calculate n (n is used for both the public key (n, e) and the private key (n, d))
        self.n = self.p * self.q

        # calculate t (totient, or called as 'phi')
        self.t = (self.p - 1) * (self.q - 1)

        # calculate e (e is one of the puclic key (n, e))
        for i in range(2, self.t):
            if gcd(i, self.t) == 1:
            self.e = i
            break

        # calculate d (d is one of the private key(e, d))
        self.d = pow(self.e, -1, self.t)


    def encrypt(self, plaintext: str):
        # ciphertext = plaintext ** e % n
        ct = pow(int(plaintext.encode().hex(), 16), self.e, self.n)
        return long_to_bytes(ct)


    def decrypt(self, ciphertext: str):
        # plaintext = ciphertext ** d % n
        pt = pow(int(ciphertext.hex()), self.d, self.n)
        return long_to_bytes(pt)


    def sign(self, plaintext: str):
        h = SHA256.new()
        h.update(plaintext.encode())
        # signed_plaintext = hash(plaintext) ** d % n
        signed_pt = pow(bytes_to_long(h.digest()), self.d, self.n)
        return signed_pt


msg = "Hello"

rsa = RSA()
enc_msg = rsa.encrypt(msg)
dec_msg = rsa.decrypt(enc_msg)
```

### Basic Rules <a href="#basic-rules" id="basic-rules"></a>

#### n <a href="#n" id="n"></a>

**`p`** and **`q`** should be prime numbers.

```
n = p * q
```

#### Totient (Phi) <a href="#totient-phi" id="totient-phi"></a>

```
t = (p - 1) * (q - 1)
```

#### e (Exponentiation) <a href="#e-exponentiation" id="e-exponentiation"></a>

**65536** is often used for the value of exponentiation (**`e`**).

```
e = 65537
```

#### Decryption Key <a href="#decryption-key" id="decryption-key"></a>

```
d = e ** -1 % t
```

#### Encrypt/Decrypt <a href="#encryptdecrypt" id="encryptdecrypt"></a>

```
# Encrypt
ciphertext = plaintext ** e % n

# Decrypt
plaintext = ciphertext ** d % n
```

### Interesting Rules <a href="#interesting-rules" id="interesting-rules"></a>

#### Factoring `n` into two prime numbers (`p`, `q`) <a href="#factoring-n-into-two-prime-numbers-p-q" id="factoring-n-into-two-prime-numbers-p-q"></a>

Reference: <https://cryptohack.org/courses/public-key/rsa\\_factoring/>

We can calculate prime numbers (**`p`** and **`q`**) by factoring **`n` (`n = p * q`)**.\
To do that, we can use online tools such as [factordb](http://factordb.com/), or create a Python script as below.

```
from sympy import factorint

n = 510143758735509025530880200653196460532653147

factors = factorint(n)
print(f"factors: {factors}")
# factors: {25889363174021185185929: 1, 19704762736204164635843: 1}
```

#### Phi is `n - 1` if `n` is prime <a href="#phi-is-n-1-if-n-is-prime" id="phi-is-n-1-if-n-is-prime"></a>

If **`n`** is prime, **totient (phi)** will be **`n - 1`**.

```
t = n - 1
```

#### Calculate Totient from Many Factors <a href="#calculate-totient-from-many-factors" id="calculate-totient-from-many-factors"></a>

If there are many factors of **`n`**, we can multiply each **`(factor - 1)`** to calculate totient.

```
factors = [factor1, factor2, factor3, factor4]

t = 1
for factor in factors:
    t *= (factor-1)

print(f"totient: {t}")
```

### Using CLI <a href="#using-cli" id="using-cli"></a>

#### Decrypt <a href="#decrypt" id="decrypt"></a>

```
openssl pkeyutl -decrypt -in ciphertext -inkey private-key.pem
```

#### Encrypt <a href="#encrypt" id="encrypt"></a>

```
openssl pkeyutl -encrypt -in plain.txt -inkey public-key.pem -pubin
```

#### Generate a Keypair <a href="#generate-a-keypair" id="generate-a-keypair"></a>

To generate a private key,

```
# genrsa: Generate an RSA private key
openssl genrsa -out private-key.pem 2048
```

To generate a public key,

```
openssl rsa -in private-key.pem -pubout -out public-key.pem
```

#### Get the Prime Number <a href="#get-the-prime-number" id="get-the-prime-number"></a>

```
openssl rsa -in private-key.pem -text -noout
```

#### Diffie-Hellman Exchange <a href="#diffie-hellman-exchange" id="diffie-hellman-exchange"></a>

```
openssl dhparam -out dhparams.pem 2048
```