# STL 2 Assignment 1
## 2
Finding the modulus and the exponent value:
https://www.alpertron.com.ar/ECM.HTM
Our task is to decrypt the message in `encrypted.txt`, which is written in bytes rather than utf-8 format.
```python=
import os
import sys
def extended_gcd(a, b):
if b == 0:
return a, 1, 0
else:
gcd, x, y = extended_gcd(b, a % b)
return gcd, y, x - (a // b) * y
def mod_inverse(e, phi):
_, d, _ = extended_gcd(e, phi)
return d % phi
def find_inverse(e,n,p,q):
phi = (p-1) * (q-1)
d = mod_inverse(e, phi)
return d
def decrypt_message(ctxt, d, n):
decrypted = pow(ctxt, d, n)
return decrypted
def test_encrypt(ptxt, e, n):
encrypted = pow(ptxt, e,n)
return encrypted
def main():
'''
d * e == 1 modulo (p-1)(q-1)
'''
e = 65537
n = 86108002918518428671680621078381724386896258624262971787023054651438740237393
# n =p*q
p = 286748798713412687878508722355577911069
q = 300290718931931563784555212798489747397
d = find_inverse(e,n,p,q)
fpath = 'encrypted.txt'
with open(fpath, 'rb') as f:
bytes_txt = f.read()
ctxt = int.from_bytes(bytes_txt, byteorder=sys.byteorder)
ptxt = decrypt_message(ctxt, d, n)
print(ctxt == test_encrypt(ptxt, e, n))
f.close()
if __name__ =='__main__':
main()
```
Once the `ctxt` is read, the following int is obtained:
`27944268035289064083815606978860307067513436544328651302667249941033580858143`
To decrypt the `ctxt`, we use the values n,p,q that we obtained. These values are used to find the `d` value using the `find_inverse` function. The find_inverse function uses the Extended Euclidean Algorithm to calculate the modular inverse of e modulo phi. The Extended Euclidean Algorithm is used to find the modular inverse because e and phi are coprime (i.e., they have no common factors other than 1). This property ensures that a modular inverse exists, allowing the calculation of the private exponent d.
In RSA encryption, the public exponent e and the private exponent d are inverses modulo `phi`. The public exponent e is used for encryption, while the private exponent `d` is used for decryption. The `d` value would then be used in the `decrypt_mesage` function in order to decrypt the `ctxt`.
The following is the decrypted message ptxt :
`70378942757824654949832537619832731157925556229901391464156608761627925404135`
In order to check whether the encryption is done properly, I would check whether the re-encrypted ptxt results in ctxt. If it does then the decryption was done properly. The following is the screenshot after the python script is run:
## 3
When running `./random`, output.txt is created which uses the time() and srand() function to generate random numbers. The srand() function is used to seed the random number generator in C. It takes an argument for the seed, which in this case is the output of the time() function. By using srand() with different seed values, we can obtain different sequences of random numbers. The purpose of calling srand() with time(NULL) as the seed is to ensure that each run of the program generates a different sequence of random numbers. As such, the output.txt is filled with different hex values based on the seed, which is the amount of time (seconds) that has passed since January 1, 1970.
If the srand function is commented then the generated value would stay the same as there will be no randomisation done. No updates will be done as commenting out these functions results in the same keys generated.
Saved as `random_og.c`
## 4
Within a 2 hour window, seeds are generated in order to try to crack the encrypted pdf. The seeds are taken from 1524013729 - 1524020929. As such the code is ammended to the following:
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define KEYSIZE 16
// 2018-04-18 05:08:49 need to convert this to a seed
void main()
{
int i;
FILE *f;
char key[KEYSIZE];
f = fopen ("key.txt", "a");
long long seed;
for (seed = 1524013729; seed < 1524020929; seed++)
{
srand (seed);
for (i = 0; i< KEYSIZE; i++)
{
key[i] = rand()%256;
fprintf(f, "%.2x", (unsigned char)key[i]);
}
fprintf(f, "\n");
}
}
```
The output file is saved in `key.txt` and the amended code was saved as `random_encrypted.c`.
Now that the keys are generated and we know the following:
- Plaintext: 255044462d312e350a25d0d4c5d80a34
- Ciphertext: d06bf9d0dab8e8ef880660d2af65aa82
- IV: 09080706050403020100A2B2C2D2E2F2
We can write a code in python to bruteforce and carry out the AES encryption using the keys saved in `key.txt` file.
The following is the code:
```python
import os
import sys
from Crypto.Cipher import AES
def brute_force(ptxt,key, IV):
cipher = AES.new(key=key, mode=AES.MODE_CBC, iv = IV)
guess = cipher.encrypt(ptxt)
return guess
def main():
Plaintext = bytearray.fromhex('255044462d312e350a25d0d4c5d80a34')
Ciphertext = bytearray.fromhex('d06bf9d0dab8e8ef880660d2af65aa82')
IV = bytearray.fromhex('09080706050403020100A2B2C2D2E2F2')
with open('key.txt') as f:
keys = f.readlines()
for k in keys:
k = k.rstrip('\n') # clean out the txt
key = bytearray.fromhex(k)
guess = brute_force(Plaintext, key, IV)
if guess == Ciphertext:
k_bytes = bytes(key)
print(f'The cipher text is : {guess} and the key : {k_bytes}')
break
if __name__ =='__main__':
main()
```
Output
```
The cipher text is : b'\xd0k\xf9\xd0\xda\xb8\xe8\xef\x88\x06`\xd2\xafe\xaa\x82'
and the key : b'\x95\xfa 0\xe7>\xd3\xf8\xdav\x1bN\xb8\x05\xdf\xd7'
```
## 5
To generate some randomness the following command is run to check.
`cat /proc/sys/kernel/random/entropy_avail`
`watch -n .1 cat /proc/sys/kernel/random/entropy_avail`
It is observed that when a mouse is moved, the entropy count increases based on the distance we moved the mouse, and it increases very fast. Every time the mouse is clicked, the entropy increases by 1. When typing, the entropy increases each time the keyboard is pressed. Reading a file or visiting a website only result in small increment in the entropy.
----------------
`cat /dev/random | hexdump`
Immediately after the command is run, I made sure to not touch anything to make sure that there is no increase the entropy. The values in the red box are the values that were generated at the start of the command. The entropy is used to generate the random number and entropy drops to 0. When the entropy reaches zero and I do not move the mouse, /dev/random will block, until it gains enough randomness (entropy value).
-------------
Although it was not possible to capture the screenshot precisely, it is observed that a new set of random number will be generated when the entropy reaches 63 every 3 times,. Thus, it will need 192-bit (3 x 64) of entropy to generate a set of random number.
-------------------
DOS attack relies on exhausting /dev/random's entropy. Thus, when a connection request to the server, it will create a session key using the entropy which will consume the entropy value.
If the server is flooded with requests and the server generates countless number of session keys, the entropy value (/dev/random) will be used up and it can no longer generate a session key (random generator is blocked). This will result in DOS attack.
## 6
Moving my mouse doesn't affect the speed at which the values are being generated.
-----------------------
Windows 10 and Linux operating systems employ a mix of hardware and software sources to collect entropy and ensure the randomness of their random number generators. These sources include clock drift, thermal noise, mouse movements, and keyboard timings.
However, the algorithms and files utilized differ between the two systems. Windows 10 utilizes wincrypt.h, while Linux relies on urandom. Furthermore, Windows 10 has the ability to gather entropy from additional sources like performance counters and interrupt timings, whereas Linux mainly depends on mouse movements and keyboard timings.
-------------
Running the `head -c 1M /dev/urandom > output.bin` command resulted in the following screenshots:
###### Entropy
The entropy is calculated using an information density approach, expressed as several bits per character. The entropy value is 7.999868 bits per byte, true random number generators should have values above 7.9 bits of information per byte .The algorithm is unable to further compress the file as indicated that it can compress the file by 0%. This indicate that it is generated from a good random number generator.
###### Chi-Square
Chi-square distribution is calculated for the stream of bytes in the file and expressed as an absolute number and a percentage which indicates how frequently a truly random sequence would exceed the value calculated. If the percentage is greater than 99% or less than 1%, the sequence is almost certainly not random. If the percentage is between 99% and 95% or between 1% and 5%, the sequence is suspect. Percentages between 90% and 95% and 5% and 10% indicate the sequence is “almost suspect”.
Chi square distribution for 1048576 samples is 191.69, and randomly
would exceed this value 99.88 percent of the times. Therefore failing the chi-square test.
Null hypothesis forchi-square test : no relationship exists on the categorical variables in the population; they are independent.
As the probability of the value value exceeding 191.69 is > 99% we can safely reject the null hypothesis. There is sufficient evidence to believe that the null hypothesis is rejectable.
###### Arithmatic Mean
This is the result of adding all the bytes (bits if the -b option is specified) in the file and dividing by the file length. Data that are random will have values close to about 127.5.
The result as seen in the screenshot is 127.5912 which is very close to 127.5. Therefore, it shows it is a random number.
###### Monte Carlo Value for Pi
Each successive sequence of six bytes is used as 24-bit X and Y co-ordinates within a square. If the distance of the randomly generated point is less than the radius of a circle inscribed within the square, the six-byte sequence is considered a “hit”. The percentage of hits can be used to calculate the value of Pi. The value will approach the correct value of Pi if the sequence is close to random.
The results yielded from the screenshot indicated a value 3.138577036 and an error of 0.10% which is very close to the value of Pi, thus urandom is close to a true random generator.
###### Serial Correlation
Serial Coefficient It measures the dependency of each current byte has upon the previous byte. For random sequences, this value (either positive or negative) has to be close to 0.
The value for the urandom generator is 0.000580 (totally uncorrelated =0), so it is close to a true random generator.
---------------
No, it doesnt face the same issue as `/dev/random/`, `/dev/urandom` is seeded from Non-blocking entropy pool so it don’t get blocked and works with whatever is available in the OS’s entropy pool.
--------------
The following is the code:
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define LEN 32 // 32 hex-pairs(1 hex-pairs = 8bits) for 256bit use
int main(){
unsigned char * key = (unsigned char *)malloc(sizeof(unsigned char) * LEN);
FILE * random = fopen("/dev/urandom", "r");
fread(key, sizeof(unsigned char) * LEN, 1, random);
fclose(random);
printf("the key is : ");
for (int i = 0; i< LEN; i++){
printf("%.2x", key[i]);
}
printf("\n");
return 0;
}
```
note: The random.c is used for each case but then is copied in order to preserve the code. the filename is `random_upgrade.c`
## 7
The number of key generate in a day on average may be different depending on my internet usage. As such I would like to list out what I use my internet usage on a typical day:
- youtube browsing (20 video tabs)
- Genshin impact dailies (1 session)
- Spotify music (15 songs)
- googling (at least 100 tabs)
It's important to note that the session keys are ephemeral and unique to each TLS session. They are not persistent or directly related to the private/public key pair used by the server.
In summary, to connect to a website securely over TLS, the server typically uses a single private key and corresponding public key. The client does not generate any cryptographic keys for the connection itself, but rather negotiates temporary session keys during the TLS handshake.
##### Youtube
Since the 20 video tabs deal with at the very least 20 videos, at least 20 temporary TLS keys are generated in the day.
When connecting to Youtube a set of private and public key is generated, meaning 2 more keys are generated.
##### Genshin Impact
Similar to connecting to Youtube a set of private and public key is generated, meaning 2 keys are generated. Assuming that the I am done with my daily session within 1 session, only 1 TLS key is generated
##### Spotify
When app is opened 1 set is generated, and assuming each song uses TLS key to listen to, that means 15 keys were generated for each song.
##### Googling
Googling for information is a key part of my day-to-day as such I would assume that for each new google search, it would lead to a single different website that has not been mentioned.
For the google session 1 set of private and public keys are generated. For each search a temporary tls key is assumed to be generated to return the search result.
Once the search results is obtained, it is assumed that only 1 website is relevant and there for would lead to that website being visited. This creates a different private and public key set and a new TLS key for the specific website.
##### Total keys generated
(20 + 2) + (1 +2) + (15 + 2) + (100 + 2) + (2*100 +100) + (1+2) = 447 keys
Do note that this may be a severe underestimation since there may be more googling and more websites visited from the googling and many other reasons.
Sign in with Wallet
Connect another wallet