:::success
# SSN Lab: RSA
### Name: Daniil Sinelnik
:::

### Task 1
:::info
Create a 2048-bit RSA key pair using OpenSSL. Write your full name in a text file
and encrypt it with your private key. Using OpenSSL extract the public modulus
and the exponent from the public key. Publish your public key and the base64
formatted encrypted text in your report. Verify that it is enough for decryption.
Hint: study OpenSSL params and encryption vs verification vs decryption vs signing
:::

#### Preparation
Fristly i have decomposed 1st task into 6 small sub-tasks
1. Generate private key via `openssl`.
2. Generate public key using `RSA` command.
3. Write a name into `MyName.txt`.
4. Extracting modulus and exponent from public key.
5. Publishing public key and the base64 formatted encrypted text.
6. Verification.

1.1 I have generated the provate key using `openssl`.

<center>

`ssn-task1.pem`
</center>

1.2 Generating public key using `RSA`.

<center>

`Generated public key`
</center>

1.3 Writing name into file called `MyName.txt`

<center>

`MyName.txt` file output.
</center>

1.4 Extracting modulus and exponent from public key.

<center>

`Exponent: 65537 (0x10001)`
</center>

1.5 Public key and the `base64` encrypted message

-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEA1CcDSSDglC2RdDAIOlCr
JqS/u3UUjQmdQ5395SP/wCzSX6f+jZGcRGEEwgA3Rno/bOzHzyHYQVpZp1XaIoT0
kIyIIaz7ABk67Q1/+bmTmFFjmGWn8kYsCx9eirfNcrlSlSkJ6BT69mqXDg+vCTQJ
0A/J1JJtSWN/H7oh+SeLts3PMYB0GUCeCNJoJYR1UmfOQHD8EDFRUh0nzHRaOfg6
dudw2MNemRNTLNDs5+L4kaiUuXq7bLzAwZxl6KVYlmfLn7ESfvK/it0N1JVYR/Fl
3VunMV3ND+RcGx95CsscW8LN6z7mTOC6ggy32cXADvTG80WJnswWfru5ShgZ+X03
UwIDAQAB
-----END PUBLIC KEY-----

Encrypted message in `base64` via this [web-site](https://www.freeformatter.com/base64-encoder.html#before-output)

EJq6flUVmUiwT2MQXXhHbSPZL5/Q7RjTQ+sJR8zovtnnNMXLbnkDjUR6Dys9Gzxeo4hblFkOI2/K0jEm0tksMQ7fsulaIExLkb24x+DzOQsZxYNjWSjngNyxXkQaSTPnE/PuC6HIQBX4szUm2j4qy7qZ+i4yApoBZbZ7PCpcVSyeRQGu4z3GLxfif5Ih+TocC3OPEGJRu3yTO4Ocrk9V8G/8wS+U6B5lV1VwYjtY7Jc9VKB+FZ4B4PUNcNymUKnGLxrSpzCkf+2RXfnqgVgiEj56aguH2Z+0aQi+yBfFcMZ0r3LkTLJsCnkqP9LRg+/5jE7++FqX/4Nd8+gOnNpfJA==

:::spoiler Research
Since i have tried to use openssl to decrypt but it provides me an errors as shown in the screen below.
<center>

</center>

I have tried to use `openssl` to encrypt the message using the private key but i can only sign the hash of the message. Later on i won't be able tp verify because `openssl pkeyutil` requires the file that the hash was created from.

From now i have 2 ways to finish the task. Write my own simple programm or find any other web resources that can encrypt and decrypt my message using private and public keys.

I know that it is a bad idea to use online tools. In order to show to the whole world(probably) my private key. But i have decided to use [this](https://www.devglan.com/online-tools/rsa-encryption-decryption).

After that i have regenerated new RSA keys, and this keys that were provided in the report are not valid and noone would use it for a bad purposes.
:::

1.6 Verification

<center>


</center>

I have entered the plain text that is exactly the same as in `MyName.txt` in the left side of the screenshot and private key as a signature to get `Base64` string. And in the left side i have entered vise versa, `Base64` and public key to decipher and get the plain text.

The online tool successfuly recovered the message.

Keys were deleted:

<center>

</center>

### Task 2
:::info
Assuming that you are generating a 1024-bit RSA key and the prime factors have a
512bit length, what is the probability of picking the same prime factor twice?
Explain your answer
Hint: How many primes with length 512bit or less exist?
:::

I have read the prime number [theorem](https://en.wikipedia.org/wiki/Prime_number_theorem). It says that the prime numbers that are less or equal to a some number `N` can be approximated using formula.

I have decided to use [Wolphram Alpha](https://www.wolframalpha.com/)

<center>

Approximate number of primes full string `13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096`
</center>

`2^512` is approximated, so it equals `3.778 * 10^151`.

We can conclude that the selection probability a certain prime number is less than `2^512`. It is `(3.778 * 10^151)^(-1)`.

According to that, the probability of selecting same numbers 2 times is `(3.778 x 10^151)^(-2)`.

<center>

</center>
Therefore we can conclude that it is very very small chance to generate same prime numbers.

:::info
3. Explain why using a good RNG is crucial for the security of RSA. Provide one reference to a real-world case where a poor RNG leads to a security vulnerability.
:::

The RSA algorithm requires to select 2 large prime numbers. Commonly it is done by random number generator or RNG. If RNG can be predicted, then it's very easy to get the keys that were generated.

Another vector of attack that was disscussed during the lecture by professor was if 2 keys share the common prime factor. In this case this factor can be obtained using the Euclid’s algorithm for finding the greatest common divisor (GCD),

The other numbers can be obtained by dividing each modulus by the GCD. That is, if the keys somehow share one of the 2 private prime numbers, both keys are compomised and extremely vulnerable.

One of the [research](https://dl.acm.org/doi/10.5555/2362793.2362828) shows that the 0.75% of TLS certificates share keys due to insifficient entropy during key generation, and that another 1.70% come from the same faulty impelementations and may be suspectible to compromise.
The list of the researches i have found [here](https://crypto.stackexchange.com/questions/76757/the-gcd-strikes-back-to-rsa-in-2019-good-randomness-is-the-only-solution).

:::info
4. Here you can find the modulus (public information) of two related 1024bit RSA keys. Your keys are numbered using the list. Your task is to factor them i.e. retrieve p and q. You may use any tools for this. Explain your approach.
:::

I have decoded the list vias dCode, it was [ROT cipher](https://www.dcode.fr/rot-cipher), it was number 8. It seems that my keys are under number 8.
<center>

</center>

hex string1

0xd25778227ec453362aa37cd41c7613547c562610b659eac78323a3040418faa6ba16f3be775fafd880f39e343a2d2dc9451897c2a69881ec500e0d1e7115bb3df13816db5b4e03f38bbf163982458eb1900f757c463f70415388380f590da26f33f764776e6eba28b7b2ebf7536ddccad259958f9f0bcaabecbb1a3ca5fc6f4dL

hex string2

0xdd2653adc131f79719caba1c5e1b98d7bed9d8eaa355051bc5d0b2cf52ae54ad3392249f048d6a058ec41ae37b77ce353b27a70495df672a9a909c3139c6182fb347badb98f5ad72bb1681da91e3f7d9febf9fd0b044547f8dce790f8494b244dd50f0b02250475bb26f4ac185dead5073d378349b3438bb76030787a627f711L

I have converted them to decimals via this [tool](https://www.mobilefish.com/services/big_number/big_number.php)

To convert them you have to delete prefixes in both hex strings such as: `0x` and letter `L` in the end, to get correct numbers

Big number1

147706948620319160411996478455491268043004138729875170948794130994870370369580976637116651212766266850087013196405145253195340192132932515269059006000440257639857078132225500453674130005072272014247075522969850084163352253085162725638345398803134827605788798516420855999533740167212053465249037734050434674509

Big number2

155296610640128435088339889808511578851058309488147542915179348270560906724906821093327246548910801519518718889408726562033095076065917194094219077598878521114843412605682219937995205934239337728155898301962691732573763112954748621325811220441237183161468767512622894269885725974354260771205273916707409753873

I wrote simple python script that calculates GCD. Python is a good tool for GCD calculating because it supports big integer.

<center>


</center>

This is the output

<center>

</center>

:::info
5. Now that you have the p and q for both keys, recreate the first public and private key using this script. Encrypt your name with the private key and post the public key and the base64 formatted encrypted data in your report
:::

I don't know what happens but it seems that the script that was provided as a link is outdated and doesn't work.
I have decided to update this script by myself.

:::spoiler The code for updated script

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from Crypto import Random
import gmpy2
import base64

p = 11727055932449918331640476387360215321027287637924797767932009026715087012021778050948661925322793624661821491396505152386857720807252239087274917335058521
q = 12595399004757834517799050678062475877912134573350116574323406763001462484083264048726660295067410740743815153601483731196628415982031759662532955942289429
n = p * q
e = 65537


string_to_be_encrypted = bytes(b'Daniil Sinelnik')

phi = (p - 1) * (q - 1)
d = int(gmpy2.invert(e, phi))

tup = (n, e, d, p, q)
key = RSA.construct(tup)

random_generator = Random.new().read

cipher = PKCS1_OAEP.new(key)
data = cipher.encrypt(string_to_be_encrypted)

print(key.exportKey('PEM').decode('ascii'))
print("-----------------------------------------------------------------------------")

print(key.publickey().exportKey().decode('ascii'))
print("-----------------------------------------------------------------------------")
print(base64.b64encode(data).decode('ascii'))


print(cipher.decrypt(bytes(data)))

:::

This is the public key:

-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDSV3gifsRTNiqjfNQcdhNUfFYm
ELZZ6seDI6MEBBj6proW8753X6/YgPOeNDotLclFGJfCppiB7FAODR5xFbs98TgW
21tOA/OLvxY5gkWOsZAPdXxGP3BBU4g4D1kNom8z92R3bm66KLey6/dTbdzK0lmV
j58Lyqvsuxo8pfxvTQIDAQAB
-----END PUBLIC KEY-----

This is the encrypted data(Name and Surname):

HR5m0+6Xjj49OQOL3FkpDrh5OMFMaFA/12IF57GDA0DxOOMJoJLhknGAPelWK6RH3QYxhoj8cXYMt+X5SnOBKj8soUEPukWqPjN3W9RxTdu2dqHeHQqruZ2SgVSPoLoFGp4q3BZ54cdXSEr8y8kuO0gz5bf3CeGFu7PyJndOvq4=

Output for the text decryption(Proof of work):
<center>

</center>

But it decrypts only with the python and not any other tools, because was used to decrypt by python with it's libraries that has it's own specification.