RSA: des nombres premiers à la signature électronique

Nous découvrons comment et où obtenir une signature électronique à l'aide de l'exemple du cryptosystème RSA.





Contenu
  1. introduction





  2. Définitions et notation





  3. Description du cryptosystème RSA





    1. Systèmes cryptographiques asymétriques





    2. Générer des clés





    3. Cryptage et décryptage





    4. Réception de la signature de message via RSA





  4. Signature électronique de documents





  5. Conclusion









introduction

Vous avez sûrement rencontré un concept tel que la «signature électronique». Si vous vous tournez vers la loi fédérale , vous pouvez trouver la définition suivante:





« - , ( ) , »





, , , , - , . , , .





, , . , (DSA, 34.10-2012, RSA-PSS ..), .





, , RSA, , 1978 . . , .





(La photo montre Lev Landau, l'auteur du "minimum théorique")
( , «»)





, :





  • – ,





  • – ,





  • – , ()





  • – , .





  • – .





  • – .





  • a b , 1.





  • φ(n) – , , n .





, , . , .





, , RSA, ,





. :





. ( ). , , . , , , . , , . , RSA.





. , , , , "" . : ? ? ? .









. y=f(x), x, x . , y=f(x, k), x, k x y , k – .





:









c \ equiv f (m) \ equiv m ^ e \ mod \ n, \\ m \ equiv f ^ {- 1} (c) \ equiv c ^ d \ mod \ n, \\ d \ equiv e ^ {- 1} \ mod \ \ varphi (n).





φ(n) n. , , . , , . c, m, n, e, d.





. c m. . , m , c – . c e, m, n, . (e, n) . .





. d , m c. , .





, , – . n , :









n = pq,





p q – . n :









\ varphi (n) = (p - 1) (q - 1).





n . , d , e. p q, , . n. , n ( ), , n ( , RSA, n 2048 ).





. e:









e ∈ [3, \ varphi (n) - 1], \\ GCD (e, \ varphi (n)) = 1.





d:









d ≡ e ^ {- 1} \ mod \ \ varphi (n).





, , .





. (e, n), d, .





, ...

m (m ∈ [1, n − 1]). , e n. :









c ≡ m ^ e \ mod \ n.





, . , c ∈ [1, n − 1], m. , d:









m ′ ≡ c ^ d \ mod \ n.





, mm′ . , () , , .





:





:





, mm′ :









:









c ≡ m ^ e \ mod \ n, \\ m ≡ c ^ d \ mod \ n.





, m . (e, n) d, , . d , . "" m d:









s ≡ m ^ d \ mod \ n.





. , , , . , m, s (e, n). , s e:









m ′ ≡ s ^ e \ mod \ n.





, mm′, .





" "!





, "". – . , , - ( , -, ). , - ( ) , .





, . :





:





- SHA-256, , , PGP. PGP , .





, , , . , , . , , .





, , , . " " -, .





!





  1. Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone





  2. : . / . . , . . , . . , . . ; . . . . – .: , 2016





  3. . . - — .: , 2006.





  4. NIST Special Publication 800-57 Part 3 Revision 1





  5. .. . – .: -, 2010. -
















All Articles