est-ce une façon correcte de générer des clés Rsa?

Question

est ce code va me donner des valeurs correctes pour les clés RSA (en supposant que les autres fonctions sont correctes)? im avoir du mal à obtenir mon programme pour déchiffrer correctement, comme dans certains blocs ne sont pas déchiffre correctement

c'est en python:

import random 
def keygen(bits): 
    p = q = 3 
    while p == q: 
     p = random.randint(2**(bits/2-2),2**(bits/2)) 
     q = random.randint(2**(bits/2-2),2**(bits/2)) 
     p += not(p&1)        # changes the values from 
     q += not(q&1)        # even to odd 

     while MillerRabin(p) == False:   # checks for primality 
      p -= 2 
     while MillerRabin(q) == False: 
      q -= 2 
    n = p * q 
    tot = (p-1) * (q-1) 
    e = tot 
    while gcd(tot,e) != 1: 
     e = random.randint(3,tot-1) 
    d = getd(tot,e)      # gets the multiplicative inverse 
    while d<0:       # i can probably replace this with mod 
     d = d + tot 
    return e,d,n 

un jeu de clés générées:

e = 3daf16a37799d3b2c951c9baab30ad2d

d = 16873c0dd2825b2e8e6c2c68da3a5e25

n = dc2a732d64b83816a99448a2c2077ced

Answer 1

Je suppose que vous faites cela pour le plaisir et l'apprentissage, et non pour quelque chose qui a besoin de sécurité réelle.

Voici quelques choses que je remarquai (sans ordre particulier):

1. Vous n'êtes pas garanti que n aura une longueur bits. Il pourrait être aussi court que bits - 4.

2. random n'est pas un générateur de nombres aléatoires sécurisé. Il est courant (et tout aussi sûr) de sélectionner l'exposant public, e, en 65537. Il s'agit d'un nombre premier, de sorte que vous pouvez remplacer le contrôle coprime par un contrôle de diviseur.

3. Il est un peu étrange la recherche de e en définissant e = tot (le contrôle de coprime est lié à l'échec).

Sinon, cela semble bien. La clé semble bien fonctionner aussi. Avez-vous un exemple de bloc qui ne décrypte pas correctement? N'oubliez pas que vous ne pouvez chiffrer que les données dont la taille est inférieure à n. Donc, avec une clé de 128 bits (comme dans votre exemple), vous ne pouvez pas chiffrer tous les numéros de 128 bits.

Answer 2

Mathématiquement, votre n, e et d semblent respecter les règles RSA (par exemple pour tous les premiers r qui divise n, r ne divise pas n et d est un inverse de et modulo r-1). Cependant, RSA est un peu plus que cela; il exige également des règles de rembourrage, qui régissent la façon dont un message (une séquence d'octets) doit être transformé en un entier modulo n , et le dos. Le rembourrage standard (voir PKCS#1) implique au moins 11 octets sont ajoutés au message, et le résultat doit encore être plus par n. Par conséquent, avec un module de 128 bits comme celui que vous présentez, la longueur du message d'entrée maximale pour le chiffrement sera de 5 octets.En outre, certaines implémentations RSA refuseront de travailler avec des clés RSA qui sont beaucoup trop petites pour la sécurité. Un module de 128 bits peut être un facteur en quelques secondes (voir this page pour une applet Java de factorisation, qui utilise ECM et un tamis quadratique pour factoriser des nombres relativement petits tels que le vôtre). L'enregistrement actuel en factorisation est de 768 bits; une longueur de module d'au moins 1024 bits est recommandée pour la sécurité à court terme. Une implémentation RSA typique acceptera d'utiliser des clés de 512 bits, mais beaucoup rejetteront quoi que ce soit de plus court. Un autre problème possible est dans l'ordre relatif p et q. Les équations présentées dans PKCS # 1 supposent que p> q (sinon, il y a une soustraction supplémentaire à effectuer dans la partie CRT). Si vous avez p < q, alors certaines implémentations peuvent se tromper (j'ai rencontré cela avec l'implémentation standard RSA de Microsoft dans Windows). Il suffit de comparer p avec q et de les échanger si nécessaire.

Toujours au niveau de la pratique, certaines implémentations RSA généralisées refuseront une clé RSA de telle sorte que l'exposant public e ne correspond pas à l'intérieur d'un entier de 32 bits (ce qui inclut la mise en œuvre RSA utilisé dans Windows, en particulier par Internet Explorer pour se connecter aux sites Web HTTPS - alors quand j'écris "répandu" je le pense). La sécurité RSA ne semble pas être affectée par le choix de et, il est donc habituel de choisir un petit et, ce qui accélère la partie qui utilise la clé publique (c.-à-d. Chiffrement, par opposition au déchiffrement, ou vérification de signature) , par opposition à la génération de signature). e = 3 est sur le meilleur que vous pourriez faire, mais pour des raisons traditionnelles (y compris un malentendu historique sur une faiblesse alléguée), e = 65537 est souvent utilisé. Vous avez juste besoin d'avoir e relativement premier à p-1 et q-1. Dans une implémentation pratique, vous choisissez d'abord et d'abord, puis bouclez dans la génération pour p et q tant qu'ils ne correspondent pas à cette règle supplémentaire.

D'un point de vue de la sécurité:

• Votre processus de génération n'est pas uniforme, que certains entiers premiers seront sélectionnés plus souvent que d'autres. En particulier, un premier p tel que p + 2 est également premier ne sera presque jamais sélectionné. Avec une taille de module appropriée, ce ne devrait pas être un problème (ce type particulier de biais a été étudié et découvert comme n'étant pas un gros problème), mais c'est néanmoins une mauvaise relation publique.

• Votre n peut être un peu plus petite que la taille de votre cible, dans le cas où les deux p et q sont proches de la limite inférieure de leur gamme de production.Un moyen simple pour éviter que est de limiter la plage de [sqrt (2) * 2 ^b-1, 2 ^b] pour les deux p et q.

• Je ne peux pas se porter garant de la sécurité du module random que vous utilisez. Un cryptographiquement sécurisé générateur de nombres aléatoires n'est pas une chose facile à faire. De manière générale, la mise en œuvre correcte de RSA sans fuite d'informations confidentielles via différents canaux secondaires (synchronisation, utilisation de la mémoire cache ...) n'est pas une tâche facile. Si vous voulez la sécurité dans une configuration pratique, vous devriez vraiment vraiment utiliser un package existant. Je crois que Python a des moyens de s'interfacer avec OpenSSL.