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.
Implémentez le cryptage RSA 256 bits avec la configuration minimale.
Veuillez consulter wikipedia pour plus de détails et n'écrivez que le flux.
Vous êtes maintenant prêt. Le cryptage est
Le déchiffrement est OK avec $ m = c ^ d \ pmod n $.
Il n'y a pas de calcul aussi difficile, mais le point est
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 $
Comme
Divisez chacun par 21 $ $ et prenez trop s'il dépasse 21 $ lors du calcul.
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
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 **.
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.
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
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.
Vous pouvez utiliser la méthode de division mutuelle euclidienne étendue.
À l'origine pour les nombres naturels $ 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
Diviser les deux côtés par $ (p-1) (q-1) $
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
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é.