Exercices

Exercice 1

Utilisation des bibliothèques cryptographiques du module sympy.

Documentation : https://docs.sympy.org/latest/modules/crypto.html

Décoder la phrase RYTVJKGCLJWRTZCVRMVTLEDFULCVHLZWRZKKFLKRMFKIVGCRTV, sachant qu'elle a été chiffrée par décalage (shift en anglais...)

Correction 
1
2
3
4
5
6
7
from sympy.crypto.crypto import decipher_shift

msg = 'RYTVJKGCLJWRTZCVRMVTLEDFULCVHLZWRZKKFLKRMFKIVGCRTV'

for cle in range(26):
    phrase = decipher_shift(msg, cle)
    print(phrase)

Exercice 2

Chiffrage affine

Principe du chiffrage affine :

  • Chaque lettre est codée par son rang, en commençant à 0 (A->0, B->1, ..., Z->25)
  • On applique à chaque rang la transformation affine \(f(x) = (ax+b)\, \%26\)

où \(a\) et \(b\) sont deux nombres entiers. Attention, a doit être premier avec 26.

Rappel sur les nombres premiers entre eux

Deux nombres sont dits premiers entre eux si leur PGCD vaut 1.

Exemples :

  • 8 et 15 sont premiers entre eux (ils n'ont aucun diviseur commun autre que 1)
  • 8 et 12 ne sont pas premiers entre eux (leur PGCD vaut 4).

Q1. Codez votre fonction affine(msg, a, b)

Correction 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def rang(lettre):
    return ord(lettre) - 65

def affine(msg, a, b):
    sol = ''
    for lettre in msg:
        rg = rang(lettre)
        nv_rg = (a*rg + b) % 26 #chiffrement affine
        nv_lettre = chr(nv_rg + 65)
        sol += nv_lettre
    return sol

Q2. Comparez vos résultats avec ceux obtenus par la fonction encipher_affine() de sympy.

Q3. Décodez la phrase UCGXLODCMOXPMFMSRJCFQOGTCRSUSXC, sachant qu'elle contient le mot TRAVAIL et que \(a\) et \(b\) sont inférieurs à 20.

Aide

L'instruction gcd du module math permet de calculer le PGCD de deux nombres.

Correction 
1
2
3
4
5
6
7
8
9
from sympy.crypto.crypto import decipher_affine
from math import gcd

for a in range(1,20):
    if gcd(a,26) == 1:
        for b in range(1,20):
            p = decipher_affine('UCGXLODCMOXPMFMSRJCFQOGTCRSUSXC', (a, b))
            if 'TRAVAIL' in p:
                print(p)

Exercice 3

Cryptographie RSA presque à la main

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import Crypto
import libnum
from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Random import get_random_bytes 

bits = 256
msg = "en NSI on fait de la crypto"

p = ...
q = ...

n = ...
phi = ...

e = 65537  
d = ...  # on calcule l'inverse de e modulo phi

M = bytes_to_long(msg.encode('utf-8')) # on convertit le message msg en un nombre

chiffre = ...  # message chiffré (sous forme de nombre)

clair = ...   # message déchiffré (sous forme de nombre) 
print(long_to_bytes(res)) # message déchiffré (sous forme de texte)
  • Pour générer un grand nombre premier, on utilise la fonction Crypto.Util.number.getPrime(bits, randfunc=get_random_bytes).
  • Pour inverser un nombre \(x\) modulo \(n\), on utilise la fonction libnum.invmod(x, n).
  • Pour calculer a à la puissance b modulo n, on utilise pow(a, b, n).
Correction 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import Crypto
import libnum
from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Random import get_random_bytes 

bits = 256
msg = 'en NSI on fait de la crypto'

p = Crypto.Util.number.getPrime(bits, randfunc=get_random_bytes)
q = Crypto.Util.number.getPrime(bits, randfunc=get_random_bytes)

n = p * q
phi = (p - 1) * (q - 1)

e = 65537  # 65537 est un nombre premier, donc forcément premier avec phi
d = libnum.invmod(e, phi)  # on calcule l'inverse de e modulo phi

M = bytes_to_long(msg.encode('utf-8'))

c = pow(M, e, n) # M puissance e modulo n
res = pow(c, d, n)

print(long_to_bytes(res))

Exercice 4

En vous servant du code précédent, déchiffrez le message 58152918114477529438769495136495430966050302170947748011925859233600631318929939319619808279389222131229963717435870597641010567365311762267359794338657867540621133550787677728203831932548041236152866441194127191404729294628415184239755221703677388875259927092794165578604353985011899152968982365630138088486380827379488939561996226754182 sachant que :

  • \(e\) vaut 65537.
  • \(p\) et \(q\) sont respectivement les 13èmes et 14èmes nombres de Mersenne.

Exercice 5

module RSA dans les règles de l'art

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
import binascii

keyPair = RSA.generate(1024)

pubKey = keyPair.publickey()

pubKeyPEM = pubKey.exportKey()

privKeyPEM = keyPair.exportKey()


msg = b'vive la crypto en NSI !'
encryptor = PKCS1_OAEP.new(pubKey)
encrypted = encryptor.encrypt(msg)
print("Encrypted:", binascii.hexlify(encrypted))


decryptor = PKCS1_OAEP.new(keyPair)
decrypted = decryptor.decrypt(encrypted)
print('Decrypted:', decrypted)