Mettre en œuvre RSA

Le mémo que j'ai étudié. Il n'y avait pas beaucoup d'articles sur la mise en œuvre de RSA qui fonctionne bien avec de grands nombres premiers.

Objectif

Implémentez le cryptage RSA 256 bits avec la configuration minimale.

Comment faire RSA

Veuillez consulter wikipedia pour plus de détails et n'écrivez que le flux.

  1. Déterminez le nombre de bits. (256 bits cette fois) 2.Faites de grands nombres premiers $ p, q $. (128 bits, la moitié de 256)
  2. n=pq
  3. Déterminez un nombre mutuellement premier $ e $ inférieur à $ (p-1) (q-1) $.
  4. Trouvez $ d $, qui est $ ed \ equiv 1 \ pmod n $.

Vous êtes maintenant prêt. Le cryptage est

  1. Rendre clair $ m $ ($ m <n $)
  2. Le code $ c $ est $ m ^ e \ pmod n $

Le déchiffrement est OK avec $ m = c ^ d \ pmod n $.

Il n'y a pas de calcul aussi difficile, mais le point est

Le calcul de la puissance est lourd

En RSA, les puissances sont multipliées par des centaines de chiffres, de sorte que la multiplication exponentielle ne peut pas être faite docilement. ** Le calcul exponentiel rapide ** le rend plus rapide. De plus, puisque ce que nous voulons trouver est le surplus de l'obscurité, pas l'obscurité elle-même, nous pouvons également optimiser ce point. Supposons que vous vouliez calculer le reste de $ a $ élevé à la puissance $ b $ de $ n $. Commencez par convertir $ b $ en nombre binaire. Soit chaque chiffre du nombre binaire $ b_i $ $ a^b = a^{\sum 2^{i}b_i}=\prod a^{2^ib_i} $ Ce sera. ici, $ a^{2^{i+1}}=a^{2^i}*a^{2^i} $ Ainsi, vous pouvez calculer le chiffre suivant avec une multiplication. De plus, vous voulez calculer la valeur de puissance divisée par $ n $, donc si vous en prenez trop à chaque étape de la multiplication, vous n'avez qu'à gérer des valeurs inférieures à $ n $. Par exemple, si $ a = 3, b = 11, n = 21 $, alors $ b = (1011) _2 , c'est-à-dire $ b=2^3+2^1+2^0 $$

Comme $ a^b=3^{2^3+2^1+2^0}=3^{2^3}*3^{2^1}*3^{2^0} $

3^{2^0}=3
3^{2^1}=3^{2^0}*3^{2^0}=9
3^{2^2}=3^{2^1}*3^{2^1}=81
3^{2^3}=3^{2^2}*3^{2^2}=6561

Divisez chacun par 21 $ $ et prenez trop s'il dépasse 21 $ lors du calcul. $ 3*9*6561\equiv (3*9)*9\equiv 6*9\equiv 12 $

main.py


def modular_exp(a, b, n):
    res = 1
    while b != 0:
        if b & 1 != 0:
            res = (res * a) % n
        a = (a * a) % n
        b = b >> 1

    return res

Comment faire un grand nombre premier

Apparemment, il est assez difficile de générer directement des nombres premiers. En pratique, il semble facile de ** générer des nombres aléatoires jusqu'à ce qu'il atteigne un nombre premier **.

Génération aléatoire

Puisque le nombre de bits est spécifié, il n'y a pas de problème si 0,1 est disposé au hasard pour ce nombre.

main.py


def gen_rand(bit_length):
    bits = [random.randint(0,1) for _ in range(bit_length - 2)]
    ret = 1
    for b in bits:
        ret = ret * 2 + int(b)
    return ret * 2 + 1

Les bits maximum et minimum sont mis à 1 à la place. En effet, le bit maximum est un nombre impair de sorte que le nombre de chiffres n'est pas réduit. La raison pour laquelle c'est étrange est que je veux des nombres premiers maintenant, et les nombres pairs ne sont pas des nombres premiers.

Jugement du nombre premier

Je veux déterminer si l'énorme nombre aléatoire $ p $ est un nombre premier. $ P $ est si grand qu'il est trop lent pour le diviser dans l'ordre. ** [Méthode de jugement du nombre premier de Mirror-Rabin](https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%A9%E3%83%BC%E2%80%93%E3% 83% A9% E3% 83% 93% E3% 83% B3% E7% B4% A0% E6% 95% B0% E5% 88% A4% E5% AE% 9A% E6% B3% 95) ** Semble être souvent utilisé. L'algorithme est également sur wikipedia, donc implémentez-le tel quel. En termes simples, nous vérifions les exigences pour les nombres premiers plusieurs fois et déterminons que s'ils passent tous, ce sont probablement des nombres premiers, et s'ils ne passent même pas un, ce sont des nombres synthétiques. ** Puisqu'il s'agit d'un algorithme probabiliste de jugement des nombres premiers, il peut juger un nombre composé comme un nombre premier. ** ** Cependant, il semble que le faux positif soit d'environ $ \ frac {1} {4} $ en une seule vérification, donc si vous le faites des dizaines de fois, ce sera presque 0 en pratique, donc il ne semble y avoir aucun problème.

main.py


def mr_primary_test(n, k=100):
    if n == 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    d = n - 1
    s = 0
    while d % 2 != 0:
        d /= 2
        s += 1

    r = [random.randint(1, n - 1) for _ in range(k)]
    for a in r:
        if modular_exp(a, d, n) != 1:
            pl = [(2 ** rr) * d for rr in range(s)]
            flg = True
            for p in pl:
                if modular_exp(a, p, n) == 1:
                    flg = False
                    break
            if flg:
                return False
    return True

Donc, la génération de nombres premiers est comme ça.

main.py


def gen_prime(bit):
    while True:
        ret = gen_rand(bit)
        if mr_primary_test(ret):
            break
    return ret

Comment décider e?

Peu importe s'il s'agit d'un nombre premier avec $ (p-1) (q-1) $, il est donc rapide d'en faire un nombre premier.

p = gen_prime(128)
q = gen_prime(128)
e = gen_prime(128)

Je pense que cela ne pose aucun problème. wikipedia a déclaré que $ 65537 $ est souvent utilisé. Il semble qu'un nombre fixe convienne.

ré?

Vous pouvez utiliser la méthode de division mutuelle euclidienne étendue. À l'origine pour les nombres naturels $ a, b $ $ ax+by=gcd(a,b) $

C'est un algorithme pour trouver $ x, y $ tel que (pgcd est l'engagement maximum) Utilisez ceci pour $ e, (p-1) (q-1) $. Puisque l'engagement maximum est 1 de la définition de $ e , $ ex+(p-1)(q-1)y=1 $$

Diviser les deux côtés par $ (p-1) (q-1) $ $ ex\equiv 1 $ Donc, ce $ x $ est $ d $. La méthode de division mutuelle euclidienne étendue était ici, donc je l'ai copiée. $ x_0 $ est $ d $.

main.py


def xgcd(b, n):
    x0, x1, y0, y1 = 1, 0, 0, 1
    while n != 0:
        q, b, n = b // n, n, b % n
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return b, x0, y0


def gen_d(e, l):
    _, x, _ = xgcd(e, l)
    return x % l

Courir

Le reste fonctionnera si vous préparez un texte brut.

main.py


bit_length = 128
p = gen_prime(bit_length)
q = gen_prime(bit_length)
e = gen_prime(bit_length)
d = gen_d(e, (p - 1) * (q - 1))
n = p * q

m = 123456789
c = modular_exp(m, e, n)  #Cryptogramme
m_ = modular_exp(c, d, n)  # 123456789

Cela a fonctionné même avec 1024 bits. (Cela a pris environ 20 secondes) En fait, il est dangereux de crypter le même texte brut plusieurs fois, il semble donc qu'un nombre aléatoire soit ajouté à la fin (supprimé au moment du décryptage), et si m est trop petit, il est complété.

Recommended Posts

Mettre en œuvre RSA
Mettre en œuvre REPL