###### tags: `finished`

:::success
# SSN Lab 4 - Asymmetrical encryption
:::

## Task 1

:::info
1. 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*
:::

I created a key pair using the `genrsa` command and the `-des 3` (Triple DES) parameter to encrypt the key with a password, without the encryption option, the private key is not encrypted and, therefore, the password is also not needed.

Password encryption can protect the private key even when bypassing file system-based access control.

<center>

Figure 1 - Creating a key pair and exporting a public key
</center>

We use the private key to sign the file. I also immediately extracted the public key from the key pair to verify the signature of the file, you can see the result in the screenshots below:

<center>


Figure 2, 3 - File signature and verification with a public key
</center>

<center>

Figure 4 - Public modulus and the exponent from the public key
</center>

#convert to Base64 format
openssl base64 -in /tmp/sign.sha256 -out secret.txt

---------------------secret.txt--------------------
FiSXSk3O/ki8ZMwecOpxWr2u0abpmSklXNEN/poYKmzdKH52rGvKypY9I7DZmP/A
ocKB7cAadxpXWVFqfuXBC36+F4wcuVoo/h3Vey99XIF/h4eutuRArpolmFhAYfe9
eGceFKKmA06zYjywB8L8ZVjXnEj8MxYSOmhoTYNDaAyCzprnkEJowSnjuStuhFJl
lkSCLpcZo7SVk3WFDCgp/R8q2T6jKGxrcN3uRUwgRPYQ5swv1pzNJyX3aDVk+H7p
xqZ37f0408bwGAK3OI97xp0L5z0h8ujzl13Ndt+dKlo1IOX9CfiViIBxxoBTveZa
K9fv5J61T/TNJxO553OY1A==
---------------------------------------------------

#viewing the public key
sudo less public.pem

-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAulduxjVZ+oWWxxs62nQa
qXRZaEseckWFCtAdXaQ3VVIsw3reyRPynZnoOnJ9Zx+Km5TgRbgCXT5jRumv8HkZ
dKQAkw7tPdDdlJ/q4KEpPBY/6Cw+E+dMqA11Cn2LlPfyg5WaQXM6UOBX0acEv8To
sDLnHxSX1EwYHbIQ6F1jVVwK6CguNdtZbqPI7SsJFuVu980OAELxj7Xj7I5hy5Mv
ffSdC37iL1uKWSH9okprDUP8stIZb+biiJDIA5FvqSjDXR6PEgk+/6/48Mbj79Lr
m5tOW6raxdp8/CFF+NEWNZir5eQLEIm7FkG+V6sBWdsOl+5dl6O3gzpIHOFIEmnG
mwIDAQAB
-----END PUBLIC KEY-----

We use a public key for encryption, you can see it above. And to decrypt the message, private.pem is needed, I will not show it to you, it should always be kept secret :)

## Task 2

:::info
2. Assuming that you are generating a 1024 bit RSA key and the prime factors have a 512 bit length, what is the probability of picking the same prime factor twice? Explain your answer.

*Hint: How many primes with length 512 bit or less exist?*
:::

Below you can see the formula, which is taken from the article by Samuel S. Wagstaff, on which the approximate number of primes in:

> Accepting this approximation naively, we would conclude that the number of 512-bit primes is about

<center>

Figure 5 - The number of 512-bit primes [[3](https://homes.cerias.purdue.edu/~ssw/shortage.pdf)]
</center>

the probability that any two of them will be the same prime number will be approximately 10^(-123). But as far as I understand, this is called [RSA-155](https://en.wikipedia.org/wiki/RSA_numbers#RSA-155), that is, the algorithm uses 155 decimal digits (512 bits) and was taken into account in 1999 for six months. Its cost and factorization were found. That is, now it will take a few days to crack.

And this is my [favorite comment](https://crypto.stackexchange.com/questions/1978/how-big-an-rsa-key-is-considered-secure-today/1982#1982) on the topic that I managed to find on a forum that describes the current state of affairs in the field of RSA key security.

## Task 3

:::info
3. 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.

*Hints: study the RSA algorithm. What private information can two keys share? What practical attacks exist? You may have to write code or use existing code for simple arithmetic operations. Be careful with bigInt values!*
:::

<center>

Figure 6 - Decryption of the list
</center>

> 7, 0xb74215e333b87454e9be7724c18074d96945491b15e59d8fe5d5456faec0d9c97cfaf8d8ef15aa120c1444ea9ca925b16ab65b9245c0d480390125a4f056658491be51e946da006f993df8eae9df7c0dc1a8bb4e40be3232d64d7621d047134325f66acfa9c4a25b1464c7eae014636887ee47bfdc826e66ea1df4e976693055L, 0xa5772d865f821662a2ef20b885ad36bfbeeab5c9ba43123d0a5c3afcc1849b2a32f12baf83fd7fd1ff0fce8dab787f72d5c7c6940e468ed8ee0ea6cedd0fd2062bde3edd24a7c0b92cab8c4337638a71c9495329c7ac88bb14841327bb3a564108b7fb388008a1c5b940837b1b82c16a4c00fd074d107184585cddc5d0dac1b3L

For this task, we need to convert the hexadecimal values of the module to decimal, and then fined the GCD of these numbers, since we assume that one of the primes is the same for both keys.

> 128688246808225058791537697159120051298185016571990432638460245089861968514159969556783303181515506299820781554385473963411450565330720708800481794433752178934260770276531610753218511806593926255551008267190912299820262420816866207104351067574669261222769704813995255325016334942879004810106331855806997803093
>
> 116193852518182539456582985074443409869926558539649508062903138014028807912597948057014820296699165359601804044064321346522537079534448018219938996555756194014011785553115689601247621348374449437630215705169218379230409981600461968187190985568936672183164781529907558110285977310902423416653082012675861037491

[GCD](https://www.calculator.net/big-number-calculator.html?cx=128688246808225058791537697159120051298185016571990432638460245089861968514159969556783303181515506299820781554385473963411450565330720708800481794433752178934260770276531610753218511806593926255551008267190912299820262420816866207104351067574669261222769704813995255325016334942879004810106331855806997803093&cy=116193852518182539456582985074443409869926558539649508062903138014028807912597948057014820296699165359601804044064321346522537079534448018219938996555756194014011785553115689601247621348374449437630215705169218379230409981600461968187190985568936672183164781529907558110285977310902423416653082012675861037491&cp=1&co=gcd) is:
> 10667412827789873784338126518932017331824312333026063054281800130330262497206066351622240662513652560324524663251454183188030199572612615976182954335183519

Q1 = a/gcd
>12063679252477876827869544993062831205964076095626271244069424637563079070349445740499807359754948719379799103350652537887389458845334922264707074716638347

Q2 = b/gcd
>10892411721001721478604438170735044637820859895294503172383905909460181913312509560163257558289846105130884375762500419893809159074601457426782578276039789

## Task 4

:::info
4. 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.
:::

Let's make this script great again:
First of all - moduls

pip install gmpy
pip3 install PyCryptodome

<center>

Figure 7 - Script
</center>

:::spoiler
from Crypto.PublicKey import RSA
from Crypto import Random
import gmpy
import base64
from Crypto.Cipher import PKCS1_v1_5
from base64 import b64decode,b64encode

#tup (tuple) - A tuple of long integers, with at least 2 and no more than 6 items. The items come in the following order:
#RSA modulus (n).
#Public exponent (e).
#Private exponent (d)
#First factor of n (p).
#Second factor of n (q)

n = 128688246808225058791537697159120051298185016571990432638460245089861968514159969556783303181515506299820781554385473963411450565330720708800481794433752178934260770276531610753218511806593926255551008267190912299820262420816866207104351067574669261222769704813995255325016334942879004810106331855806997803093
#116193852518182539456582985074443409869926558539649508062903138014028807912597948057014820296699165359601804044064321346522537079534448018219938996555756194014011785553115689601247621348374449437630215705169218379230409981600461968187190985568936672183164781529907558110285977310902423416653082012675861037491
p = 10667412827789873784338126518932017331824312333026063054281800130330262497206066351622240662513652560324524663251454183188030199572612615976182954335183519
q = 12063679252477876827869544993062831205964076095626271244069424637563079070349445740499807359754948719379799103350652537887389458845334922264707074716638347
e = 65537

string_to_be_encrypted="Fige Polina"

phi = (p - 1) * (q - 1)
d = int(gmpy.invert(e, phi))
print(type(d))
tup = (n ,e, d, p, q )
key = RSA.construct(tup)

cipher = PKCS1_v1_5.new(key)
data = cipher.encrypt(string_to_be_encrypted.encode())

print(key.exportKey('PEM'))
print(key.publickey().exportKey())
print(base64.b64encode(data))

:::

<center>

Figure 8 - Result
</center>

> -----BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQC3QhXjM7h0VOm+dyTBgHTZaUVJGxXlnY/l1UVvrsDZyXz6+NjvFaoSDBRE6pypJbFqtluSRcDUgDkBJaTwVmWEkb5R6UbaAG+ZPfjq6d98DcGou05AvjIy1k12IdBHE0Ml9mrPqcSiWxRkx+rgFGNoh+5Hv9yCbmbqHfTpdmkwVQIDAQABAoGAI9bv0uRdkZq9r/s7HADUWWSmITsD2EktSESidMoXe0BVifu66V8ySJ9GI4hCpS3y+ay6UewEX0rIWzoSfNJYvfSlb5dtuAUc0H6DqV6JRajnmE4ATmtf6M5c5CrwtOT3EgSn1aFZB3TK5nGJpgK96SjQRA0C9xdwxS0Vi038m+0CQQDLrTpOsntW1IVr7eGQBAhpEGpmDz+zK1ATy7qF2PdmHM/tnOZZcQ4ujqxkRukNzf4EloM2UC7FNMQfxmCArKKfAkEA5lYJL4kYhOC7l1FnyBkWARCIYfobbzUPkyfckZ9PuQ39HjLpWZ72bU8l5SBtvYCV8N5ufGzd1E0pAwVcpeyciwJAWMysuDTuu1uq0/SBvEVV2WCz0s1hK1996TOQndyLeHSlXuZiM6qr0TaZCJs17rPZxOxORrbMvWQVAfl+h3s85wJBAKhkLcL6z1oVkg9GDEFVVajhlVNLrdLXT9OdSLuNZJM9jtcNEVvbwvyW6HViB9iKsROvCccdL++NmXYD7X/AQ5ECQCzP3x1P17DROYlaA1EGy6P+rflEOZ3jDSV8tVE3vW0OP7bTfpcCM0Db5+yJVj76A8QgKIv+FfAXrtimNuCAvcI=
-----END RSA PRIVATE KEY-----

> -----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQC3QhXjM7h0VOm+dyTBgHTZaUVJ
GxXlnY/l1UVvrsDZyXz6+NjvFaoSDBRE6pypJbFqtluSRcDUgDkBJaTwVmWEkb5R
6UbaAG+ZPfjq6d98DcGou05AvjIy1k12IdBHE0Ml9mrPqcSiWxRkx+rgFGNoh+5H
v9yCbmbqHfTpdmkwVQIDAQAB
-----END PUBLIC KEY-----

> -----BEGIN ENCRYPTED TEXT-----lvBKcwQzXIHqQ/lwnQe8hy4tRabb8N6Bry/R7UrCr/bTn03coUQmsdcNTOjNZiPWw93Lr1uItsXOCJWfWygZutKavO3LJCB7gw2drbaHe5wrXLR+MQJxXkDHRDusFv6T/zIVKhzlNCVTAD9QYZ1dLrP/guCUTr0KnMR4AzbR2Xg=
> -----END ENCRYPTED TEXT-----

## References:
1. [Encrypting with private key](https://security.stackexchange.com/questions/81760/what-happens-when-encrypting-with-private-key)
2. [Public exponent e=3 in RSA](https://crypto.stackexchange.com/questions/8454/what-security-authorities-and-standards-reject-e-3-in-rsa-when-and-with-what)
3. [Is there a shortage of primes for cryptography?](https://homes.cerias.purdue.edu/~ssw/shortage.pdf)
4. [Prime numbers in RSA](https://stackoverflow.com/questions/16091581/how-many-prime-numbers-are-there-available-for-rsa-encryption)