当前位置:网站首页>RSA et sa certification [original]

RSA et sa certification [original]

2021-09-15 07:42:49 Helesheng

DescriptionRSALes étapes de la mise en oeuvre sont décrites dans de nombreux articles,Mais expliquez et prouvez le principe,Et pourquoi il n'y a pas beaucoup d'articles conçus de cette façon.Je suis un peu faible,J'ai peur de comprendre.R.S.A.La conception originale de la trémie à trois,Écrivez simplement ce que vous comprenez,La famille Boda sourit..

Les contenus originaux suivants sont les bienvenus pour la réimpression,Mais veuillez indiquer la source.: https://www.cnblogs.com/helesheng

Un.、Théorèmes fondamentaux de la théorie des nombres utilisés

R.S.A.Les trois doivent être des fans d'Euler, le Dieu des maths,Parce que tous les principes et théorèmes utilisés sont nommés d'après Euler.

1、Euler, fonction

Moins demDans le livre de,TousmLe nombre de nombres de réciprocité est défini comme“Euler, fonction”,C'est écrit comme:Φ(m).SimLe facteur de masse est décomposé en: (Parmi euxPiEst un nombre premier,eiEst un entier positif),Φ(m) Est calculé comme suit::

 

 2、Théorème d'Euler

Sigcd(a,m)=1(aEtmIntermassique),Oui.:

Éclairement:

1) Le théorème d'Euler est “Anneau”À“Domaine” Une transition importante vers , Il suffit de diviser l'opération de multiplication à gauche en produit de deux opérations de multiplication , Les deux parties démontées peuvent être comprises comme “Domaine”Dans“Yuan” Et sa multiplication “Élément inverse”, De cette façon, l'élément inverse du module sur l'anneau existe ,“Anneau”Peut devenir“Domaine”C'est. Mais il faut noter que la condition d'existence du théorème d'Euler est gcd(a,m)=1Cette condition. Pour satisfaire à cette condition ,Cryptographie(cryptology) Si vous travaillez sur un champ limité , Il y a souvent des choix mEst un nombre premier, Ou très proche du nombre premier ;Eta Ce qui est nécessaire est inférieur à m N'importe quel nombre de , En texte clair ou chiffré . Mais techniquement ,RSA Il ne travaille pas dans le domaine de Galois ,Parce queRSA Le module de n C'est deux nombres premiers p、qProduit de.n Très proche d'un nombre premier , Pour prouver RSAHeure, Une preuve spéciale est requise gcd(a,n)Non.1Situation.

2) Le Petit théorème de Fermat est le théorème d'Euler “ Cas particuliers dans des cas particuliers ”, Il est décrit comme :Quandp C'est un nombre premier quand , Ou .Preuve:SipEst un nombre premiergcd(a,p)=1; Et la fonction Euler Φ(m)=p-1. Au théorème d'Euler , On obtient le Petit théorème de Fermat .

2.、RSAProcessus

Step 1. Choisissez deux grands nombres premiers pEtq,QuandnPour7680Bits(960Octets) Le nombre d'heures ,pEtqEnviron3072Bits, La possibilité de trouver un nombre premier dans un nombre impair de cette longueur est d'environ :

 À peu près1065 Un des nombres impairs a un premier .

Calculn=p*q.

Step 2.CalculnLa fonction Euler deΦ(n).

Parce quen On sait que les deux facteurs qualitatifs de pEtq,Formule de substitution(1)Oui.Φ(n)=(p-1)(q-1).

Step 3.Sélectionner unΦ(n) Le nombre de tautomères e.

a)ExigenceseAvecΦ(n) La raison de la qualité mutuelle est de s'assurer eModèlen L'existence d'inversions multiplicatives . Et l'inverse de multiplication est la clé privée d.

 

 

b)e Sera la clé publique ,e Peu de valeur ,En général, il y a3、17、65537 Plusieurs options . Parce que la clé publique e Beaucoup plus petit que la clé privée d, La partie qui détient la clé publique , Qu'il s'agisse de cryptage (AvecRSA Faire un échange de clés ) Ou décrypter (AvecRSA Signer numériquement ) Est beaucoup plus rapide que la clé privée dDu côté.

e La raison pour laquelle ces nombres ont été choisis , En plus d'être premier , Et à cause de ces chiffres 3(b101)、17(b1_0001)、65537(b1_0000_0001)Dans la représentation binaire de1 Le nombre de , Ça calcule xe Ce sera particulièrement facile .

c)Tout au long deRSAEn cours de calcul,Calculd C'est la seule fois que Φ(n) La place du moule , Il est utilisé ailleurs n Comme modèle .

Step 4.Utilisation de la clé publiqueeEt la clé privéed Effectuer le cryptage et le décryptage

a) La formule ci - dessus ne précise pas xEty Qui est le texte clair et qui est le texte chiffré , C'est - à - dire que les deux peuvent être utilisés comme texte clair et chiffré .

b)RSA J'ai trouvé un “Correspondance individuelle”Relations cartographiques pourf:Parce queePlus petit, Et public ,Alors...xMapping toyC'est facile;yMapping toxC'est difficile.,dPlus grande, Et je ne sais pas p、q Difficile à obtenir . Une telle cartographie fAppelé Cartographie unidirectionnelle .

Trois、RSAPreuve

PreuveRSAProcessus, Équivalent à la preuve :Parmi eux

n=p×q,nSeulementp、q Deux facteurs qualitatifs .

SelonnEtx La situation de :

Situation I:QuandxNe contient paspEtq Deux facteurs qualitatifs ,nEtxIntermassique,gcd(n,x)=1. Selon le théorème d'Euler, il y a :

 

SelondDéfinitions,dEte Antithèse Φ(n) L'inverse ,Oui.:

 

 

  Écrivez la formule ci - dessus sous une autre forme :

 

  Pour le remplacer par (2),Oui.:

 

 Situation II:QuandnEtx Quand il n'y a pas de réciprocité ,Parce quen=p×q,xPeut être écrit comme:x=r×pOus×q( Mais ça ne peut pas être écrit comme x=r×p×q, Parce que ça va faire x > n).Sans perdre de vue la généralité,Hypothèsesx=r×p.Parce que, Selon le théorème d'Euler et la fonction d'Euler il y a :

 

 

SelondDéfinitions,Il y a aussi(5)Équation,Et(6) La formule devient : 

 

 

Où la formule de calcul de la fonction Euler est utilisée

Oui.(7) La formule ci - dessus a : 

 

 

 Jusqu'ici., Ça prouve qu'il y a ,Terminé.!

Quatre、RSAIdées de conception

Spéculer sans réfléchir R.S.A. Trois idées de conception , En utilisant le théorème d'Euler n Un logarithme d'inversion réciproque sur un anneau en tant que module xEty Comme texte clair et cryptographique ,xEty Chacun est l'autre e Sous - puissance et dSecondaire.Si vous le savez.n Décomposition du facteur de masse (p×q)De, Peut être calculé facilement par la fonction Euler eEtd, Sinon, l'autre partie ne peut en informer qu'une seule , Cela donne une cartographie unidirectionnelle , Qui constitue ce qu'on appelle “Chiffrement asymétrique”.

En plus,IneEtd La complexité de la segmentation , Ce n'est pas égal . Le concepteur fait connaître la clé du côté de la Factorisation qualitative d C'est beaucoup plus compliqué que e,Pour deux raisons::Un., La partie qui connaît la décomposition du facteur premier peut passer par le reste du théorème chinois CRTCalcul accéléré;Deux., Je ne connais pas beaucoup de factorisation qualitative “Asymétrie” Le correspondant , L'addition peut être effectuée avec une force de calcul plus faible 、Décrypter.

Une clé plus simple e Appelé clé publique , Une clé plus complexe d Appelé clé privée .

 

版权声明
本文为[Helesheng]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/09/20210915073956247P.html

随机推荐