Séance 2 : RSA

Séance 2 : RSA#

Exercice 1 : RSA « brut »#

Le but de cet exercice est d’implémenter le chiffrement RSA brut avec des paramètres réels. En particulier :

  • on choisira l’exposant public \(e\) égal à \(2^{16}+1 = 65537\), quitte à regénérer des nombres premiers

  • le chiffrement et déchiffrement seront déterministes (pour la conversion sémantiquement sûre, voir exercice suivant)

Question 1. Écrire une fonction rsa_keygen(t) qui retourne une paire de clés publique/privée du chiffrement RSA. Cette fonction prend en entrée un paramètre t, la taille en bits du module RSA (l’entier \(n = pq\)) qui sera construit. On peut supposer t pair pour simplifier.

from Crypto.Util.number import getPrime, isPrime
from math import gcd

def rsa_keygen(t):
    assert(t >= 10)
    p = getPrime(t//2)
    q = getPrime(t//2)
    while p == q:
        q = getPrime(t)
    n = p*q
    phi = (p-1)*(q-1)
    e = 2**16 + 1
    if gcd(e, phi) != 1:
        return rsa_keygen(t)
    d = pow(e, -1, phi)
    return ((n, e), d)
    
print(rsa_keygen(24))
print(rsa_keygen(256))
print(rsa_keygen(2048))

((9367231, 65537), 5325473)
((59004559899509058264758863937270464994446534055130698059568788197323356707779, 65537), 36374906221828356073863430135550930416178483558641309108962069037952208790337)

((17485954246123339306304155668260420240173101241070250833912382891754494044652353725792158708369635642850132675549815550547567033904951327905803700199896626245772619788290299349419631817239560956140117098514686759281955007387696416721991771951759557510897339573820270791002474233995320207606733218033289496035007993311499884299409839748644147220210237318600597757621595276183752356481188904827244278896681358054035607220827406005326180435592985978784076851991485129237507578934921493283331531730815114865916783146887186178303815425914719105996960824584941367508746226767479359016671979319466641738612148963424242930893, 65537), 16539044079049903976672444597160793595188217338777525805156793730168875243601478596127444558255900853395700509513434645274311996241819474712375601080171385136990603101096160582141754079177348742682966548708796600918104688923028601854873216042017050688702630353875992886349106196757585929003863141728299270338914720340614380337036770564310655588301558456631830049922509046034686459078730981025621989828463151446139821725148160312013028185194698006285051594389465595381213910960141443185323511998959353506830238045184480409362654443848285790910101209324951376397320207082303388382368962407098592703188664881041101092465)

Question 2. Écrire une fonction rsa_encrypt(m, pk), qui prend en entrée un message m sous forme d’entier, et qui retourne un chiffré de RSA par la clé publique pk.

def rsa_encrypt(m, pk):
    return pow(m, pk[1], pk[0])

Question 3. Écrire une fonction rsa_decrypt(c, pk, sk), qui prend en entrée un chiffré RSA c sous forme d’entier, et qui retourne le déchiffré de c par la paire de clés pk/sk.

def rsa_decrypt(c, pk, sk):
    return pow(c, sk, pk[0])

Question 4. Test.

  1. Créer une paire de clés publique/privée pour \(t = 2048\).

  2. Calculer le chiffré de \(n+1\), puis le déchiffrer. Que remarquez-vous ? Modifier la fonction de chiffrement en fonction.

  3. Vérifier, sur une centaine de tests, que le déchiffrement du chiffré d’un message aléatoire se déroule correctement.

pk, sk = rsa_keygen(2048)
print("Clé publique :", pk)
print("Clé privée   :", sk)

Clé publique : (23036353234643543815051223483429540122732329869621255184811093357807662017349793056257671778624761270613809400134720982133240816694720078991767433077330994588294563449223753051453731947052006103160806817405040613995074284618541338421968820983597511711554886621436169810922732970671071627140114917314830157805333900959945454611971264954256491010197336463851891965666949157279532437499274102298944454568554688536547142870119168637196216994957042671591395372901376376191850711179858511293408068055566992334329421502878923944739802540539297973137707979786786672667948084724637621758083801461412230498052987861220579044051, 65537)
Clé privée   : 23018426658587776527342484719103206806494794602163930558807074776529175196731137343517248181867053978171352402112125032210467493508559120692965532790669354892794265560459995000190718071999750853282704353946419421824029702344168913558769095487005304666720834113422479152815754326828597533834285449063566652639275496171667221445384931406498607032854467319112595371199300531557005941886287768283143734252521594108830722295178693740966697978695857470932406847706161955216054614089439762279233071298624501827769693693216148895076828914669751509968849126308560891592797215209898580593694754581197326472933613273609867946673

m = pk[0]+1
c = rsa_encrypt(m, pk)
res = rsa_decrypt(c, pk, sk)
print(m == res, res)

False 1

On remarque que le déchiffré du chiffré de \(n+1\) vaut \(1\), et ne correspond donc pas au message initial. En effet, RSA n’est valide que si le message est strictement inférieur au module.

def rsa_encrypt(m, pk):
    assert (0 <= m < pk[0]) 
    return pow(m, pk[1], pk[0])

import random

for _ in range(100):
    m = random.randint(0, pk[0]-1)
    if (m != rsa_decrypt(rsa_encrypt(m, pk), pk, sk)):
        print("Erreur")

Exercice 2 : déchiffrement accéléré pour RSA#

Nous avons vu en cours qu’il est possible d’accélérer la procédure de déchiffrement, en effectuant les calculs sur des entiers de taille plus petite.

Rappelons la méthode (voir le cours si nécessaire) :

  1. Dans la génération des clefs, les données suivantes sont calculées :

    • l’entier \(d_p = d \mod (p-1)\)

    • l’entier \(d_q = d \mod (q-1)\)

    • l’entier \(i_q = q^{-1} \mod p\)

  2. La clé privée \(d\) est remplacée par les cinq entiers \((d_p, d_q, i_q, p, q)\)

  3. Lors du déchiffrement, au lieu de calculer \(c^d \mod n\), on calcule successivement :

    • l’entier \(m_p = c^{d_p} \mod p\)

    • l’entier \(m_q = c^{d_q} \mod q\)

    • la combinaison linéaire entière (sans réduction \(\mod n\)) : \(m = m_q + q \cdot (i_q \cdot (m_p - m_q) \mod p)\)

Question 1. Dans le même contexte que pour l’exercice 1, écrire une fonction rsa_keygen_fast(t) qui effectue la génération de ces nouvelles clefs RSA.

def rsa_keygen_fast(t):
    assert(t >= 10)
    p = getPrime(t//2)
    q = getPrime(t//2)
    while p == q:
        q = getPrime(t)
    n = p*q
    phi = (p-1)*(q-1)
    e = 2**16 + 1
    if gcd(e, phi) != 1:
        return rsa_keygen_fast(t)
    d = pow(e, -1, phi)
    dp = d % (p-1)
    dq = d % (q-1)
    iq = pow(q, -1, p)
    
    return ((n, e), (dp, dq, iq, p, q))
    
# vérification partielle
pk, sk = rsa_keygen_fast(1024)
n, e = pk
dp, dq, iq, p, q = sk
print(1 == (e * dp) % (p-1) and 1 == (e * dq) % (q-1))

True

Question 2. Écrire une fonction rsa_decrypt_fast(c, sk), qui prend en entrée un chiffré RSA c sous forme d’entier, et qui retourne le déchiffré de c par la nouvelle clé privée sk.

def rsa_decrypt_fast(c, sk):
    dp, dq, iq, p, q = sk
    mp = pow(c, dp, p)
    mq = pow(c, dq, q)
    m = mq + q * ( (iq * (mp - mq)) % p )
    return m

Question 3. Vérifier sur des exemples que le déchiffrement est correct. On pourra utiliser la fonction de chiffrement de l’exercice 1.

import random
pk, sk = rsa_keygen_fast(2048)

for _ in range(100):
    m = random.randint(0, pk[0]-1)
    if (m != rsa_decrypt_fast(rsa_encrypt(m, pk), sk)):
        print("Erreur")

Question 4. En faisant la moyenne des temps d’exécution sur des centaines de déchiffrement, donner une valeur expériementale du facteur de réduction de temps de calcul obtenu par cette accélération. On donnera la valeur obtenue pour \(t = 1024\), et on pourra également tracer les temps de calculs en fonction \(t\).

import time
import matplotlib.pyplot as plt


T = [ 50 * i for i in range(1,40) ]
times_classic = []
times_fast    = []
N = 100

for t in T:
    
    pk, sk = rsa_keygen(t)
    total_time = 0
    for _ in range(N):
        m = random.randint(0, pk[0]-1)
        c = rsa_encrypt(m, pk)
        start = time.time()
        mm = rsa_decrypt(m, pk, sk)
        total_time += (time.time() - start)
    times_classic.append(total_time/N)

    pk, sk = rsa_keygen_fast(t)
    total_time = 0
    for _ in range(N):
        m = random.randint(0, pk[0]-1)
        c = rsa_encrypt(m, pk)
        start = time.time()
        mm = rsa_decrypt_fast(m, sk)
        total_time += (time.time() - start)
    times_fast.append(total_time/N)

plt.plot(T, times_classic, color='blue')
plt.plot(T, times_fast, color='red')
plt.show()
print(f"Pour t = {T[-1]}, le facteur de gain est de {times_classic[-1] / times_fast[-1]}")
_images/b3a7713a53a43f14ca122506b54db5d0bf0df305d0cb9cf21c0940466ecc95e5.png 
Pour t = 1950, le facteur de gain est de 3.5154448508577607

Ci-dessus, on a tracé en fonction de \(t\) :

  • en bleu le temps moyen (sur \(N = 100\) échantillons) de déchiffrement « classique » d’un chiffré RSA ;

  • en rouge le temps moyen (sur \(N = 100\) échantillons) de déchiffrement « accéléré » d’un chiffré RSA.

Puis, on donne affiche le facteur de gain pour la plus grande valeur de \(t\).

Contenu