Cracking un bit N RSA numéros modulo

Question

Ceci est lié à mon post précédent , où ma seule option était d'avoir un algorithme RSA qui semblait relativement faible. Supposons que je veux encoder un nombre de 35 bits (de 0 jusqu'à 34.359.738.367) avec un modulo 36 bits (entre 34.359.738.368 jusqu'à 68719476735).

http://en.wikipedia.org/wiki/RSA je peux voir que mon n est compris entre 34359738368 68719476735 jusqu'à un indicatrice aléatoire (de la forme p-1 * q-1). Je prends un au hasard et d e. J'encode un numéro et montrer que sur l'interface utilisateur.

Aux fins de la discussion supposons qu'un utilisateur peut voir jusqu'à 1000 ces sorties. Peut-il utiliser des algorithmes comme ceux de Polla ou quoi que ce soit de semblable à craquer ma d, e ou n et commencer ainsi prédire de nouveaux numéros? Si oui, comment est difficile que ça va être? (En sachant juste dire 1000 séries d'entrées / sorties)

A titre d'exemple (considérer 6 sorties comme échantillon d'entrée / format de sortie),

1. 10001621865,31116156015
2. 10001621866,33031668326
3. 10001621867,37351399313
4. 10001621868,06071714212
5. 10001621869,01188523761
6. 10001621870,18341011998

Quelqu'un peut-il me dire ce que mon n, d, e était? (N entre 34359738368 68719476735 jusqu'à)

Je veux simplement savoir comment il est piratable, donc si vous pouviez me donner des informations sur la durée, la vitesse, combien de sorties n'il faut voir, quels algorithmes peut-on utiliser, etc. Il sera grand.

PS: l'utilisateur ne voit pas le "e" comme l'algorithme standard RSA. Il ne peut voir les ensembles de sortie d'entrée.

AJOUTÉE DÉTAILS Je suis en train de présenter un séquentiel utilisateur-id de db à l'utilisateur. Parce qu'il est séquentiel, je ne veux pas un utilisateur de deviner l'identifiant d'un autre utilisateur en faisant quelques inscriptions. Pour éviter cela, je dois démener à un <= 12 chiffres. Il y avait beaucoup de contraintes autour de ce qui ont été expliquées dans cette question.

En outre la valeur de n, d et e ne soit pas connue de l'utilisateur. Le maximum qu'un utilisateur peut voir est quelques échantillons d'entrée ouput (par l'enregistrement de façon répétée)

Accepter la réponse affichée par Accipitridés puisque l'algorithme « Jacobi » peut être utilisé pour casser ce en quelques secondes. Sans le savoir n, e ou p.

Answer 1

Un attaquant peut deviner un facteur p et de n mod e (p-1). Chaque proposition peut être vérifiée en procédant à un message m, le calcul de m ^ e mod p, et en comparant ensuite avec c mod p, où c est le texte chiffré correspondant. Depuis mod p et e (p-1) sont peut-être 20 bits chacun, cela signifie que la sécurité du régime ne dépasse pas 40 bits.

40 bits est seulement un très haut brut lié. Un attaquant peut faire beaucoup mieux. Par exemple, il peut deviner un facteur p. Puis il calcule les symboles Jacobi des messages et des cryptogrammes. Si un message m est un p mod résidu quadratique alors le cryptogramme doit être un mod résidu quadratique p et vice versa. Par conséquent, si cette relation n'est pas satisfaite pour une paire de message / cryptogramme il peut rejeter la conjecture pour p. Ou l'attaquant peut calculer des logarithmes discrets entre message et cryptogramme. Cela donne un candidat beaucoup plus rapide pour e mod (p-1).

Cela devrait donner un niveau de sécurité de 20-30 bits exigent donc quelques secondes pour briser. Si vous étendez votre nombre d'échantillons à 20 je pourrais essayer quelques repères.

Mise à jour: Puisque vous ne me donnez 20 échantillons pour exécuter une expérience, je devais les produire moi-même. Avec les exemples suivants

m = 10001621865  c = 31116156015
m = 10001621866  c = 33031668326
m = 10001621867  c = 37351399313
m = 10001621868  c = 6071714212
m = 10001621869  c = 1188523761
m = 10001621870  c = 18341011998
m = 10001621871  c = 7620400191
m = 10001621872  c = 36106912203
m = 10001621873  c = 37615263725
m = 10001621874  c = 7795237418
m = 10001621875  c = 34774459868
m = 10001621876  c = 4555747045
m = 10001621877  c = 33123599635
m = 10001621878  c = 34836418207
m = 10001621879  c = 33962453633
m = 10001621880  c = 6258371439
m = 10001621881  c = 7500991556
m = 10001621882  c = 5071836635
m = 10001621883  c = 911495880
m = 10001621884  c = 39558568485

en entrée, l'algorithme décrit ci-dessus trouve des facteurs 201821 et 206153  à 20ms. Comme cela est décrit cela n'a pas besoin de connaître e, bien que votre choix de e = 65537 est facile à deviner et peut être exploité aussi bien.

La force de RSA est qu'il est basé sur la difficulté de factoriser de grands entiers. Ici, vous supprimez cette difficulté et ce qui reste sont toutes les faiblesses (à savoir les relations mathématiques) de RSA. Construire un chiffrement par bloc basé sur RSA est une idée horrible. Je ne vois vraiment pas pourquoi vous ne voulez pas utiliser une construction Luby-Rackoff comme je l'ai proposé plus tôt.

Answer 2

RSA est vulnérable contre une attaque Chosen-cryptogramme. C'est-à-dire que nous voulons briser cryptogramme y, nous pouvons utiliser l'une des paires de cryptogramme-plaintext pour le briser.

Comment briser:

choisir un x0 et y0, où x0 et y0 est une paire-cryptogramme qui plaintext a été fourni.

y1 = y0 * y mod n y1 est une autre des 1000 ciphertexts donnée à l'utilisateur qui satisfait à ces critères. x1 est le déchiffrement de y1, qui est également donnée, cela signifie:

x1 = y1 ^ d mod n (ce qui nous a été donné, nous savons déjà x1)

x1 = (y0 * y) ^ d mod n x1 = y0 ^ d * y ^ d mod n Ξ x0 * x

x1 * x0 ^ -1 = x

x est le déchiffrement de y.

Ceci est bien sûr dépendant si y0 ou non * mod yn produit un autre cryptogramme que nous avons déjà, et puisque nous avons seulement 1000 ces paires de travailler avec, il est peu probable mais pas impossible à briser. Il vous suffit de choisir très soigneusement vos paires.

Je voudrais aussi ajouter que la taille de n vous travaillez avec une heuristique permet d'affacturage pour trouver la factorisation de n assez rapidement. En outre, RSA est vulnérable aux attaques de synchronisation, mais qui peut être facilement contournée.

Avec information ajouté: Sans savoir n, d, ou e, il n'y a absolument aucune information fournie à tous, ce qui signifie devinettes combinaisons de n, d ou e est aussi bon que deviner le texte brut lui-même. Pour trouver n et e, il y a au moins 43,359,738,367 combinaisons de n à deviner, ainsi que toutes les combinaisons e pourraient être. Il est pas facile pour quelqu'un, même avec 1000 paires de cryptogramme-être en mesure plaintext à craquer n et e.

Answer 3

Ceci est une idée horrible, 36 bits RSA ?? Pourquoi pas aller tout simplement avec un bloc ou d'un flux-chiffrement? De cette façon, vous obtenez 1:. Cartographie 1 et d'une manière beaucoup securer

Une autre solution que je recommande serait d'utiliser un hachage SHA comme UID et enregistrer le numéro séquentiel pour chaque utilisateur dans la base de données dans une colonne distincte.