###### 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")
```
Sign in with Wallet
Connect another wallet