---
# System prepended metadata

title: Homework 3
tags: [Cryptographie]

---

###### tags: `Cryptographie`
# Homework 3
> Fait en collabration entre M. Mozerski, M. Marachly et M. Meier
## exercise 1

### a)
```
Données
p = 3; q= 11; e = 7; M = 5
```
1) $N = p*q = 33$

2) $φ(N) = φ(p*q) = φ(p) * φ(q)= (p-1)*(q-1) = 2 * 10 = 20$

3) $e*d = 1modφ(N) => d = e^{-1}modφ(N)$
$d = 7^{-1}mod20 => 7*d mod20=1mod20 => d = 35$

>il faut que 7 * qqchose entier mod20 = 1mod20
>voir Homework1 exercice 3

4) 
>Clé privée: KR = {d=3, p=3, q=11}
>Clé public: KU = {e=7, N=33}

Encrypthage:
$C=M^emodN => C=5^7mod^33 =5^3*5^3*5mod33=26*26*5mod33=26*130mod33=26*31mod33=14$
>C=14

Decrypthage:
$M = C^dmodN => M = 14^3mod33 = 5$

### b)

```
Données
p = 5; q= 11; e = 3; M = 9
```
1) $N = 55$
2) $φ(N) = 4 * 10 = 40$
3) $d = 3^{-1}mod40 => 3 * d mod40 = 1mod40$
$3*d mod40 = 1mod40 => d = 27$
4) 
>Clé privée: KR = {d=27, p=5, q=11}
>Clé public: KU = {e=3, N=55}

Encrypthage:
$C=M^emodN => C=9^3mod55 = 9^2*9mod55= 26*9mod55 = 14$
>C=14

Decrypthage:
$M = C^dmodN => M = 14^{27}mod55 = 9$

### c)
```
Données
p = 7; q= 11; e = 17; M = 8
```
1) $N = 77$
2) $φ(N) = 6 * 10 = 60$
3) $d = 17^{-1}mod60 => 17 * d mod60 = 1mod60$
$17*d mod40 = 1mod40 => d = 53$
4) 
>Clé privée: KR = {d=53, p=7, q=11}
>Clé public: KU = {e=17, N=77}

Encrypthage:
$C=M^emodN => C=8^{17}mod77 = 57$
>C=57

Decrypthage:
$M = C^dmodN => M = 57^{53}mod77 = 8$
>M=8

### d)
```
Données
p = 11; q= 13; e = 11; M = 7
```
1) $N = 143$
2) $φ(N) = 10 * 12 = 120$
3) $d = 11^{-1}mod120 => 11 * d mod120 = 1mod120$
$11*d mod120 = 1mod120 => d = 11$
4) 
>Clé privée: KR = {d=11, p=11, q=13}
>Clé public: KU = {e=11, N=143}

Encrypthage:
$C=M^emodN => C=7^{11}mod143 = 106$
>C=106

Decrypthage:
$M = C^dmodN => M = 106^{11}mod143 = 7$
>M=7

### e)
```
Données
p = 17; q = 31 ; e = 7 ; M = 2
```
1) $N = 527$
2) $φ(N) = 16 * 30 = 480$
3) $d = 7^{-1}mod480 => 7 * d mod480 = 1mod480$
$7*d mod480 = 1mod480 => d = 343$
4) 
>Clé privée: KR = {d=343, p=17, q=31}
>Clé public: KU = {e=7, N=527}

Encrypthage:
$C=M^emodN => C=2^7mod527 = 128$
>C=128

Decrypthage:
$M = C^dmodN => M = 128^{343}mod527 = 2$
>M=2

## Exercice 2
```
Données
C=10; e= 5; N=35
In a public-key system using RSA, you intercept the ciphertext C = 10 sent to a user whose public key is e = 5, n = 35. What is the plaintext M?
```
$d=e^-1modφ(N)$
$φ(N) = φ(35) = φ(5*7) => φ(5) * φ(7) = 4 * 6 = 24$

$d=5^{-1}mod24 = 5$
>15 mod 24
>20 mod 24
>25 mod 24 => bingo

$M = C^dmodN = 10^5mod24 = 10^2*10^2*10mod24 = 4*4*10mod24 = 16*4mod24 = 16$ 

## Exercice 3
```
Données
p = 5; q = 7
```
### a)
$N=5*7=35$
$\phi(N)=4*6=24$
### b)
>d n'est pas bien parce que:

$e*d = 1modφ(N) => e = d^{-1}modφ(N) => e = 3^{-1}mod24$ => n'existe pas car gcd(3,24) != 1
>Alice d=11
> e1 = 11 ou e2 = 13

$e = 11^{-1}mod24 => e = 11$
> donc e1 est correct

### c)
> M=33 
> public key = {e=11, N=35}
> He will use the public key to encrypt the message

$C=M^emodN=33^{11}mod35=17$

>the ciphertext is 17

### d)
>Using the private key ={d=11, p=5, q=7}

### e)
> she needs to send M+M'

### f)
> he needs to decrypte the ciphertext and then substract the Alice's signature

## Exercice 4
```
p = 283, q = 47, h = 5
A = 24, k = 15
H(M) = 41
Calculate the public key of Alice.
```


### a)
> public key $y=g^xmodp$

$g=h^{\frac{(p-1)}{q}}modp => g = 5^{\frac{282}{47}}modp = 60$

Généré le x (**a dans ce cas là**) aléatoirement entre 0 < x < q. x est la clé secret.
Donc x = 24

y est la clé publique.
$y=g^xmodp=60^{24}mod283 = 158$

### b)
```
r=19, s=30
```
                              
$r=(g^kmodp)modq => r = (60^{15}mod283)mod47 = 19$
>$r = 19$
$s=(H(M)+r*x)*k^{-1}modq => s = (41+19*24)*15^{-1}mod47 = (41+19*24)*22 mod 47 = 497*22mod47 = 30$
>$s = 30$

### c)
```
Demontrer que v=r
DSA: Verification of the signed document slide 31
```
$w=s^{-1}modq= 30^{-1}mod47 = 11$
$u1 = H(M)*wmodq = 41*11mod47 = 28$
$u2 = r*wmodq = 19*11mod47 = 21$
$v = (g^{u1}y^{u2}modp)modq = (60^{28}*158^{21}mod283)mod47 = 106 * 158^{21}mod283 mod 47 = 106*42 mod283 mod 47  = 207 mod 47 = 19 $
>$v = 19$
>$v=r => 19 = 19$

## Exercice 5
`
Données:
Implement the Miller-Rabin primality test in Python
`


```python=
import math
from random import seed
from random import randint
import sys

def miller_rabin(n):
    if n % 2 == 0:
        return False
    k = int(math.log2(n)) + 1
    kmax = 0
    for i in range(k, 0, -1):
        if (n-1)%(2**i) == 0 and ((n-1)//(2**i))%2 == 1:
            kmax = max(kmax, i)
    q = (n-1)//2**kmax
    seed(1)
    a = randint(2, n-2)

    if (a**q)%n == 1:
        return True
    
    for j in range(0, kmax):
        if (((a**2)**j)*a**q)%n == n-1:
            return True
    return False

if __name__ == "__main__":

    try:
        n = sys.argv[2]
    except:
        n = 28901

    print(miller_rabin(n))
```

## Exercice 6
`
Données:
Test the ElGamal encryption
`
### a)
```
Données
P=71, G=33, x=62, M=15 and y=31
```
1) $h = G^xmodp = 33^{62}mod71 = 10$
> Clé public (p=71,g=33,h=10)
2) y est un nombre aléatoire entre {1, ..., p-1=70}. 
> y = 31
3) $s = h^ymodp = 10^{31}mod71 = 58$
> s = 58
4) $c1 = G^ymodp = 33^{31}mod71 = 62$
5) $c2 = M*smodp = 15*58mod71 = 18$
> c1 utile pour décrypthé
> c2 (le message crypthé) = 18
> On envoie (c1, c2) au destinataire.


### b)
`
Données
P=23, G=11, x=6, M=10 and y=3
`

1) $h = G^xmodp = 11^{6}mod23 = 9$
2) y est un nombre aléatoire entre {1, ..., p-1=22}.
> y = 3
3) $s = h^ymodp = 9^{3}mod23 = 16$
> s = 16
4) $c1 = g^ymodp = 11^{3}mod23 = 20$
5) $c2 = M*smodp = 10*16mod23 = 22$
> c1 utile pour décrypté
> c2 (le message crypté) = 22
> On envoie (c1, c2) au destinataire.

### c)
`
Données
P=11, G=2, x=8, M=5 and y=9
`

1) $h = G^xmodp = 2^{8}mod11 = 3$
2) y est un nombre aléatoire entre {1, ..., p-1=10}.
> y = 9
3) $s = h^ymodp = 3^{9}mod11 = 4$
> s = 4
4) $c1 = g^ymodp = 2^{9}mod11 = 6$
5) $c2 = M*smodp = 5*4mod11 = 9$
> c1 utile pour décrypté
> c2 (le message crypté) = 9
> On envoie (c1, c2) au destinataire.


```python=
if __name__ == "__main__":
    p = 102407
    g = 97007
    x = 23451
    m = 1263121437
    y = 12523

    h = (g**x)%p
    s = (h**y)%p

    c1 = (g**y)%p
    c2 = (m*s)%p

    print(f"{c1}, {c2}")
```

## Exercice 7
`
Données:
Make a Python code to sign and verify messages using the ElGamal Signature scheme and try it with larger numbers.
`

```python=
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

if __name__ == "__main__":

    p = 102407
    k = 13427
    g = 97007
    h_m = 1263121437%(p-1)

    #private Key
    A = 23451

    #public Key
    y = (g**A)%p
    
    r = (g**k)%p
    s = ((h_m-A*r)%(p-1)*modinv(k,p-1))%(p-1)

    if (g**h_m)%p == ((y**r)*(r**s))%p:
        print("Excellent")
    else:
        print("Failed")
```