---
# System prepended metadata

title: RSA

---

::: success
# SSN Lab № 3 Assignment: RSA
**Name: Khasan Abdurakhmanov**
:::

> **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.**

* Open a terminal or command prompt and generate a **2048-bit** **RSA** key pair using **OpenSSL** by running the following command:

```
openssl genpkey -algorithm RSA -out private_key.pem -aes256

```

<center>

![](https://hackmd.io/_uploads/HkL5jKZk6.png)
    Figure 1:Generating a 2048-bit RSA key pair

</center>

This command generates a private key file named **private_key.pem** that is encrypted with **AES256**. We will be asked to provide a **passphrase** in order to **safeguard** the private key.

* Write our full name in a text file named `name.txt`.

<center>

![](https://hackmd.io/_uploads/SJg32FZya.png)
    Figure 2: Full name in name.txt
    
</center>

* Encrypt the `name.txt` file using your private key by running the following command:
```
openssl rsautl -encrypt -inkey private_key.pem -in name.txt -out name.enc

```
<center>

![](https://hackmd.io/_uploads/r13VTFZJT.png)
    Figure 3: Ecrypting the name.txt
</center>

This command encrypts the **name.txt** file using our** private key** and saves the encrypted data to a file named **name.enc.**

* Extract the **public modulus** and **exponent** from our **public key** by running the following command:
```
openssl rsa -in private_key.pem -pubout -out public_key.pem
openssl rsa -in public_key.pem -pubin -text -noout

```

<center>

![](https://hackmd.io/_uploads/B1jR6FWy6.png)
Figure 4: Modulus and exponent
</center>

The first command extracts our **public key** from our **private key** and saves it to a file named **public_key.pem.** The second command extracts the **modulus** and **exponent** from the **public key**.

```markdown
Public-Key: (1024 bit)
Modulus:
    00:d6:e0:a1:f0:fe:18:6b:04:f4:a6:24:37:7e:f7:
    80:22:bd:4a:c4:aa:c9:7a:ae:fd:f6:a0:73:23:cd:
    d2:0a:1c:4b:9d:34:e7:a8:6f:f4:7c:87:16:fa:41:
    45:6b:ad:2a:f2:14:34:a3:70:ee:f0:ff:2e:24:ce:
    17:7d:ba:ba:7a:d4:d0:d9:3c:1e:30:c5:60:2a:a3:
    44:0a:07:de:48:50:17:02:19:9c:a3:be:f7:d3:b3:
    13:ea:95:5d:c0:58:56:b1:f0:82:88:18:ed:af:0e:
    a7:6b:c1:2b:16:46:8b:b1:24:47:36:54:ca:21:35:
    b3:ae:79:05:32:50:38:e0:af
Exponent: 65537 (0x10001)
```

**Public key in base64 format:**
```
-----BEGIN CERTIFICATE-----
LS0tLS1CRUdJTiBQVUJMSUMgS0VZLS0tLS0KTUlHZk1BMEdDU3FHU0liM0RRRUJB
UVVBQTRHTkFEQ0JpUUtCZ1FEVzRLSHcvaGhyQlBTbUpEZCs5NEFpdlVyRQpxc2w2
cnYzMm9ITWp6ZElLSEV1ZE5PZW9iL1I4aHhiNlFVVnJyU3J5RkRTamNPN3cveTRr
emhkOXVycDYxTkRaClBCNHd4V0FxbzBRS0I5NUlVQmNDR1p5anZ2ZlRzeFBxbFYz
QVdGYXg4SUtJR08ydkRxZHJ3U3NXUm91eEpFYzIKVk1vaE5iT3VlUVV5VURqZ3J3
SURBUUFCCi0tLS0tRU5EIFBVQkxJQyBLRVktLS0tLQo=
-----END CERTIFICATE-----
```
**The base64 formatted encrypted text:**
```
-----BEGIN CERTIFICATE-----
losnh+8VWl1QRA8sTkKtPsIMfExQNmKySx/X5YI0q1nXKR4QdUDj+lTNoBFUnLlz
1NDfWKHzjLgLiTKReRoc9Y43xKhKZutl/k7wDOmLPyfVwmVs14YDfEBKRskY/Go8
3h6jKuJZulCzsxXgbwtLB0OXIfiINjr4awxweJXitYU=
-----END CERTIFICATE-----
```

* Verify that it is enough for decryption by running the following command:
```
openssl rsautl -decrypt -inkey private_key.pem -in name.enc -out name_decrypted.txt

```
<center>

![](https://hackmd.io/_uploads/Hk1MZqbyp.png)
    Figure 5: Decrypting name.enc 
</center>

This command decrypts the `name.enc` file using our **private key** and saves the decrypted data to a file named `name_decrypted.txt`.

We should be able to open the `name_decrypted.txt` file and verify that it contains our full name.

<center>

![](https://hackmd.io/_uploads/HylVW5-JT.png)
    Figure 6: name_decrypted.txt
</center>

> **2. 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**

There are approximately **2^511 / ln(2) = 1.9 x 10^152** prime multipliers of length **512 bits** or less.
Assuming you are generating a **1024-bit RSA key**, the length of each prime factor should be **512 bits**. When generating prime factors, the probability of choosing the same prime factor twice is negligible because the probability of choosing any particular prime factor is **1 in 1.9 x 10^152**. While it is theoretically possible for the same prime factor to be selected twice, the probability of this happening is extremely small, to the point where it is virtually impossible.


> **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**

Utilizing a reliable **random number generator (RNG)** plays a vital role in safeguarding the RSA algorithm, as its security foundation lies upon the complexity of factorizing large numbers into their prime constituents. If an attacker can predict the random numbers used to generate the RSA keys, they can potentially factor the keys and break the encryption.
One real-world case where a poor RNG led to a security vulnerability is the **Debian OpenSSL** vulnerability. In 2008, it was discovered that the **Debian distribution of OpenSSL** had a flawed RNG that generated predictable keys. This made it possible for an attacker to decrypt encrypted communications that were thought to be secure.

> **[Here](https://docs.google.com/document/d/1pMiWS12Po3v3VG64TogFqxM4wcM0B6YS9ouTdA3kuII/edit) you can find the modulus (public information) of two related 1024bit RSA keys. Your keys are numbered using the [list](https://docs.google.com/document/d/16Fi-asKgRB_lDloIaUYBPMhnuO3m9Tvw/edit). Your task is to factor them i.e. retrieve p and q. You may use any tools for this. Explain your approach.**



First of all we should analyze our keys
<center>

![](https://hackmd.io/_uploads/SkzBOeU1p.png)
    Figure 7: Our keys
</center>

We should try to understand which cipher was used for these keys. Let's visit **www.boxentriq.com** and thoroughly analyze our keys.


<center>

![](https://hackmd.io/_uploads/ryGPFg8Jp.png)
    Figure 8:  Analyzing keys 
    
![](https://hackmd.io/_uploads/Hk1OYx81a.png)
    Figure 9: Got some results
    
</center>

After these we got some results:

* Monoalphabetic Substitution Cipher (**48 votes**)
* Caesar Cipher (**37 votes**)
* Vigenere Cipher (**12 votes**)
* Two-Square Horizontal Cipher (**3 votes**)

According to the results, the **Monoalphabetic Substitution Cipher** emerged as the clear favorite, scoring an impressive **48 votes**. Coming in second place is the trusted Caesar Cipher with a respectable **37 votes**. The elegant **Vigenere Cipher** secured a solid **12 votes**, while the unique **Two-Square Horizontal Cipher** garnered a modest **3 votes**.

Than I go to www.cachesleuth.com and try to decode these keys
<center>
    
![](https://hackmd.io/_uploads/HJO4seL1a.png)
    Figure 10: Decoded keys 
</center>

I have successfully decoded these keys and discovered that my full name is hidden beneath the number 10.
Now we're going to the modulus (public information) of two related 1024bit RSA keys. I will select number 10 since I discovered that my entire name corresponds to this particular number.
<center>

![](https://hackmd.io/_uploads/rk712eIJp.png)
    Figure 11: Modulus of two RSA keys
</center>

We have two hexadecimal numbers.
> **1. 0xde9e10a438016ead23e753e3488113c100cbfe4c1b0e31c908d25b5fb663438bd6c96199ad6cb19a1472a2143d3d16db6f227ec866b3b1487cce0e60224ccfd1cf16379fe352e6582d26472297234a319b26a6218f80a9fb7b7d86a23876355d76fc8f49be053202f99c35f63d63b0e7a99393ef20095b87280b7793abc5febdL**
**2. 0xcde3e5c9b26d913871eeb2e1c66407cc5204c54563f816e464ce3d3a989d7169cc5f905127484294914dfb0a03c73686e85a2b73d7b10bc1637cd4417dda37a9027a7291a195a84ecb1bc1d5537ceb19b95220afa2ea608f71d1cf2d68900e5e73b1c62afdb2735e8bbe6341134611f3858252e982befe394aa37f8e35e06a6bL**

We should translate them into decimal:
<center>
    
![](https://hackmd.io/_uploads/r1-x-ZUk6.png)
    Figure 12: First number
    
![](https://hackmd.io/_uploads/Sk_L--LyT.png)
    Figure 13: Second number
    
</center>

Here is the expanded version of these two numbers:

> **1. 156327283655162195740218699956484507864298346127147377469083764504557667450689049490194125120472116441710524261232115017083493858217475030272557605661556452474514755341833225980212686392035942969928006623145332224304384720138290401898401576861036036503818267894669046521589581906801684429684487965965271039677**

> **2.
> 144581032843854571475365692239053689788269378721883120774871410490534517732698177556525362746506658697909135610446186887601591102419021799039321891771042063079874113580177223343553186540462825773161097064066426766931457625867302793051814019191143019603798211938995788897712509830430472661141325498216083384939** 

We need to find the greatest common divisor of these two numbers:
<center>

![](https://hackmd.io/_uploads/BJa_9HDyT.png)
    Figure 14: The greatest common divisor
</center>

> **12299273442936068281693548953380994272842706534026096342133613289180656269701040114279670583097635100739257866373383750279904544019720903866005027424081051**

Then we need to find **result of division** of x= it's our first modulus and y= it's our GCD
<center>
    
![](https://hackmd.io/_uploads/r18YirwJp.png)


    Figure 15: Result for q1
</center>

And we got the result for q1

> **12,710,286,049,046,806,786,040,554,496,458,598,658,675,176,233,897,852,293,984,071,919,249,089,792,410,477,128,437,074,016,978,765,234,666,474,102,374,561,446,699,447,349,140,458,072,712,234,826,293,736,327**

<center>
    
![](https://hackmd.io/_uploads/S1x5eUwJT.png)
    Figure 16:Result for q2
</center>

> **11,755,249,894,610,063,658,883,873,892,121,150,443,472,450,303,228,831,880,194,773,848,664,427,679,022,132,438,908,261,115,319,441,211,138,940,409,601,885,784,145,654,311,568,333,736,401,381,811,841,701,489**

> **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**


First we need to fill in our variables and then try to get keys
We converted our variables in hex format.
<center>

![](https://hackmd.io/_uploads/rknPdLDJT.png)
    Figure 17: Filled in variables
</center>

And we get public and private keys:

<center>

![](https://hackmd.io/_uploads/Sk12OLD1T.png)
    Figure 18: Get private and public keys
</center>

here is public key:
> -----BEGIN PUBLIC KEY-----\n
> MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDenhCkOAFurSPnU+NIgRPBAMv+\nTBsOMckI0ltftmNDi9bJYZmtbLGaFHKiFD09FttvIn7IZrOxSHzODmAiTM/RzxY3\nn+NS5lgtJkcilyNKMZsmpiGPgKn7e32Gojh2NV12/I9JvgUyAvmcNfY9Y7DnqZOT\n7yAJW4coC3eTq8X+vQIDAQAB
> \n-----END PUBLIC KEY-----'


After that we go to **the-x.cn** web-site and try to encrypt our name with private key and get Base64 encrypted text

<center>
    
![](https://hackmd.io/_uploads/r1Mq6Lv1a.png)
    Figure 19: Encrypted text
</center>

**Encrypted text Base64:**
> f1CpD9Sv3mZ/P5nBqqNYSdCvlC/gaB+LppyD1YcnpEDtkWkmD+HGvQUkBC+Sc/aW7F19vHXBumjeM8CcJMkxf8BSzOfv1yj+xql4vX20se5FDX6WkD2OoUinhiIp5H78t5eEZDjaPd6XQwIshsDXJZR6FSO8TvRAB3oIUFD2Xbk=



## References:
1. https://the-x.cn/en-US/cryptography/Rsa.aspx
2. https://www.boxentriq.com/code-breaking/cipher-identifier
3. https://www.rapidtables.com/convert/number/decimal-to-hex.html
4. https://www.dcode.fr/gcd
5. https://www.calculator.net/big-number-calculator.html?cx=144581032843854571475365692239053689788269378721883120774871410490534517732698177556525362746506658697909135610446186887601591102419021799039321891771042063079874113580177223343553186540462825773161097064066426766931457625867302793051814019191143019603798211938995788897712509830430472661141325498216083384939&cy=12299273442936068281693548953380994272842706534026096342133613289180656269701040114279670583097635100739257866373383750279904544019720903866005027424081051&cp=20&co=divide
