# Cryptographic Utilities Exercise || I.BA_MOVK_MM, Semesterweek 04
*Please write down to solution of the exercises in a consise but comprehensible way. Numerical results
should be accurate to 4 digits.*

## 1 Exercise 1: MD5, SHA1, SHA256, SHA512

Generate the previsously mentioned hash values of the string $Hello World!$. Do You get the same  
result as Your neighbour? Check the size of each hash value! What are the corresponding block sizes?  
Make a table! How many hash values would You have to generate in order to find a collision with a  
probability of at least 50% (90%)?  

---

We will use some good ol' Python for that


```python
import hashlib

plaintext = b'HelloWorld!'

md5hash = hashlib.md5(plaintext)
print("md5: ",md5hash.hexdigest())
print("md5-size: ",md5hash.digest_size)
print("md5-lenght: ",str(md5hash.digest_size * 8))
print("md5-block-size: ",md5hash.block_size)
print()

sha1hash = hashlib.sha1(plaintext)
print("sha1: ",sha1hash.hexdigest())
print("sha1-size: ",sha1hash.digest_size)
print("sha1-lenght: ",str(sha1hash.digest_size * 8))
print("sha1-block-size: ",sha1hash.block_size)
print()


sha256hash = hashlib.sha256(plaintext)
print("sha256: ",sha256hash.hexdigest())
print("sha256-size: ",sha256hash.digest_size)
print("sha256-lenght: ",str(sha256hash.digest_size * 8))
print("sha256-block-size: ",sha256hash.block_size)
print()


sha512hash = hashlib.sha512(plaintext)
print("sha512: ",sha512hash.hexdigest())
print("sha512-size: ",sha512hash.digest_size)
print("sha512-lenght: ",str(sha512hash.digest_size * 8))
print("sha512-block-size: ",sha512hash.block_size)

```

### Probability of a Collission

The values are obviously the same as my neighbours, because it is a hash and not an encryption with different keys!    

The Probability of a Collission is best shown here:  




**The Formula is:** $n = 2^{(m+1)/2} \cdot \sqrt{(\ln{(\frac{1}{1-p})}}$    

Angenähert $2^{\frac{m}{2}}$





```python
import numpy as np

def number_hashes_for_collision(message_digest_length, probability_threshold):
    n = 2 ** ((message_digest_length+1)/2) * np.sqrt(np.log(1/(1-probability_threshold)))
    return n #n = hashes die es braucht für eine kollision mit w'keit p

print('MD5, p = 0.5:  ' + str(number_hashes_for_collision(128,0.5)))
print('MD5, p = 0.9:  ' + str(number_hashes_for_collision(128,0.9)))
print('SHA1, p = 0.5:  ' + str(number_hashes_for_collision(160,0.5)))
print('SHA1, p = 0.9:  ' + str(number_hashes_for_collision(160,0.9)))
print('SHA256, p = 0.5:  ' + str(number_hashes_for_collision(256,0.5)))
print('SHA256, p = 0.9:  ' + str(number_hashes_for_collision(256,0.9)))
print('SHA512, p = 0.5:  ' + str(number_hashes_for_collision(512,0.5)))
print('SHA512, p = 0.9:  ' + str(number_hashes_for_collision(512,0.9)))
print('SHA3, p = 0.5:  ' + str(number_hashes_for_collision(512,0.5)))
print('SHA3, p = 0.9:  ' + str(number_hashes_for_collision(512,0.9)))
```

    MD5, p = 0.5:  2.171938135516356e+19
    MD5, p = 0.9:  3.958608607783506e+19
    SHA1, p = 0.5:  1.4234013764919992e+24
    SHA1, p = 0.9:  2.5943137371969984e+24
    SHA256, p = 0.5:  4.006518692980012e+38
    SHA256, p = 0.9:  7.3023439875766e+38
    SHA512, p = 0.5:  1.3633476639602231e+77
    SHA512, p = 0.9:  2.4848588961634497e+77
    SHA3, p = 0.5:  1.3633476639602231e+77
    SHA3, p = 0.9:  2.4848588961634497e+77


## Exercise 2: True random number generator  

Check if Your computer can generate true random numbers, possibly through some special device? Find  
out the underlying physical principle (thermal noise, etc.). How can You use the random number generator  
in the power shell (Windows) or some shell (bash, sh, etc.) on Linux or MAC OS X?  
How are true random numbers generated on smart cards? Do some research on the internet!  

---
 
**Windows:** https://en.wikipedia.org/wiki/CryptGenRandom  
**True-Randomness**: Pseudorandom   

PowerShell

    Get-Random sets a default seed for each session based on the system time clock when the session starts.

---

**Linux**: /dev/random  
**True-Randomness**: Verwendet den "Noise" von Systemtreibern (CPU clock, GPU clock, Voltage Level...)  
**Example**: cat /dev/urandom > ~/urandom_test2   

--- 

**Smartcard:** Almost all - if not all - smart cards have a true random number generator (TRNG) on it. Most often the TRNG depends on thermal noise or clock drift, but other entropy sources are possible. A more technical evaluation of this can be found e.g. here   
[https://csrc.nist.gov/csrc/media/events/random-bit-generation-workshop-2016/documents/presentations/sessionvi-2-viktor-fischer-presentation.pdf])  
**True Randomness**: Allgemein werden "Hardware Random Number Generators" (hrng) verwendet bei smartcards
https://en.wikipedia.org/wiki/Hardware_random_number_generator.  
Diese messen "Noise" wie Thermisches Rauschen oder den Photoelektrischen Effekt.


## Exercise 3: Linear congruential random number generator

Compute the period of a linear congruential number generator if $m$ = 11, $b$ = 5, $a$ = 3 and $x_{0}$ = 7 is  
used. Write down the sequence of random number! What is the maximal size of the period? Adapt the paramters, such that the period is maximal!  

---

Formel gemäss Folie Nr 37 :

$x_{0} = s_{0} = 7$

$s_{i} = (a \cdot s_{i-1} + b) \mod m$  

**Example**

$s_{1} = (3 \cdot s_{0} + 5) \mod 11 = (3 \cdot 7 + 5) \mod 11 = 4$   

Das Maximum können wir mittels Python berechnen:


```python
def lcrn(a, sx, b, m):
    res = ((a * sx + b) % m)
    print(res)
    return res
    

sx = lcrn(3,7,5,11)
x = 1
while x<22:
    sx = lcrn(3,sx,5,11)
    x=x+1
```

    4
    6
    1
    8
    7
    4
    6
    1
    8
    7
    4
    6
    1
    8
    7
    4
    6
    1
    8
    7
    4
    6


Die momentane Period ist bei **5** (nach 5 wiederholt sich das Muster.)

---

Um die Period maximal zu machen muss folgendes gelten:  
- gcd(b,m) = 1 (erfüllt)
- jeder primfaktor von m dividiert a-1 (nicht erfüllt)
- falls eine Zahl m teilt, teilt diese Zahl auch a-1 (nicht erfüllt)

Um diese Bedingungen zu erfüllen müssten wir also lediglich **a** anpassen, z.B. auf 12


```python
sx = lcrn(12,7,5,11)
x = 1
while x<22:
    sx = lcrn(12,sx,5,11)
    x=x+1
```

    1
    6
    0
    5
    10
    4
    9
    3
    8
    2
    7
    1
    6
    0
    5
    10
    4
    9
    3
    8
    2
    7


Mit unserer angepassten Formel erhalten wir nun eine Maximale Periode von **11**!

## Aufgabe 4: LFSR  

Construct an LFSR of length 5 which produces the sequence of bits (1, 0, 1, 1, 0, 0, 1, 0, 1, 0,...). What
is the period of this LFSR? What is the maximal period? Try to improve this LFSR such that it has maximum period!  

**Python Way**:


```python
def lfsr5(seed, taps):
    sr, xor = seed, 0
    while 1:
        for t in taps:
            xor += int(sr[t-1])
        xor %= 2
        sr, xor = str(xor) + sr[:-1], 0
        yield sr
        if sr == seed:
            break
                
a = lfsr5('10110', (5,3,2,1)) #IV
[next(a) for j in range(31)]
```




    ['01011',
     '00101',
     '00010',
     '00001',
     '10000',
     '11000',
     '01100',
     '00110',
     '10011',
     '01001',
     '00100',
     '10010',
     '11001',
     '11100',
     '11110',
     '11111',
     '01111',
     '10111',
     '11011',
     '11101',
     '01110',
     '00111',
     '00011',
     '10001',
     '01000',
     '10100',
     '01010',
     '10101',
     '11010',
     '01101',
     '10110']



Period is 15 which can be improved to 31 by adding c2 = 1 as an example! To make computations easy,
use the following python code

### Paper Way (raten und zeichnen):
**Gegeben**: 
- LFSR Länge: 5
- Output: 1011001010



**Gegeben**: LFSR Länge & Output  
- LFSR Länge: 4
- Output: 00011110



### Paper Way 2 (mathematischer):

Dieser Weg sollte besser verständlich sein und beinhaltet alle wesentlichen Schritte.  







## Exercise 4:Is random really random (optional)

Nope

## Exercise 5:Probability for a collision

There are 40 people in a room. You bet, that there are at least 2 people with the same birthday. What is the probability, that You win? Use the exact formula as well as the approximation




```python
from sympy import *
i = symbols('i',integer=True)
p = 1 - product((365-i)/365,(i,1,39))
p.evalf()
```




$\displaystyle 0.891231809817949$



**Formel:**


$ 1 - \frac{365!}{(365 - n)! \cdot 365^{n}} =  1 - \frac{365!}{(365 - 40)! \cdot 365^{40}} = 0.891$
  
**Mathematischer Hintergrund**: Im **Urnenmodell** entspricht diese Annahme einer Ziehung von $n$ Kugeln mit Zurücklegen aus einer Urne, die 365 Kugeln mit der Beschriftung „1. Januar“, „2. Januar“ usw. bis „31. Dezember“ enthält. 

---

**Allgemein Formel für W'Keit (p) von Kollision berechnen.**

$p = 1 - e^{\frac{-n(n-1)}{(2*m)}} = 1 - e^{\frac{-40(40-1)}{(2*365)}} = 0.882$

n = Anzahl effektiver Werte (z.B. Personen)  
m = Anzahl möglicher Werte (z.B. Tage im Jahr)



## Exercise 6:Probability of a collision

Suppose You use a hash function of length 128 bits. How many hash values would You have to compute in order to find a collision with probability at least 90%?   Use the approximate forumula from Slide 14/58.  

$n = 2^{(m+1)/2} \cdot \sqrt{(\ln{(\frac{1}{1-p})}}$  

where m=128 and p=0.9.


```python
import math
import numpy as np
m = 128
p = 0.9

n = 2**((m+1)/2) * ( math.sqrt(np.log(1/(1-p)) ) )
print (n)
```

    3.958608607783506e+19


How much storage would You need, if You need 16 bytes for each hash?


```python
byte = n * 16
kilobyte = byte/1024
megabyte = kilobyte/1024
gigabyte = megabyte/1024
terabyte = gigabyte/1024
petabyte = terabyte/1024
exabyte = petabyte/1024

print("byte: ",byte)
print("kilobyte: ",kilobyte)
print("megabyte: ",megabyte)
print("gigabyte: ",gigabyte)
print("terabyte: ",terabyte)
print("petabyte: ",petabyte)
print("exabyte: ",exabyte)
```

    byte:  6.33377377245361e+20
    kilobyte:  6.185325949661728e+17
    megabyte:  604035737271653.1
    gigabyte:  589878649679.3488
    terabyte:  576053368.827489
    petabyte:  562552.1179955947
    exabyte:  549.367302730073


Conclusion: It's not worth it :)


```python

```

f1b87de70ef51c78598ce678d849a01d5f64ef4a
ipynb
Jupyter Notebook
SW04/Exercises_Sol_sw04.ipynb
daveschafer/hslu-hs19-movk
29d1fbb12fb663778201da76cff1909a2aebb5cb
MIT
SW04/Exercises_Sol_sw04.ipynb
daveschafer/hslu-hs19-movk
29d1fbb12fb663778201da76cff1909a2aebb5cb
MIT
SW04/Exercises_Sol_sw04.ipynb
daveschafer/hslu-hs19-movk
29d1fbb12fb663778201da76cff1909a2aebb5cb
MIT
Qwen/Qwen-72B
1. YES
2. YES