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

introduction
Définitions et notation
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
Signature électronique de documents
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 , :

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.$

, m ≡ m′ . , () , , .

:

:

, m ≡ m′ :

:

$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.$

, m ≡ m′, .

" "!

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

, . :

:

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

, , , . , , . , , .

, , , . " " -, .

!

Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone
: . / . . , . . , . . , . . ; . . . . – .: , 2016
. . - — .: , 2006.
NIST Special Publication 800-57 Part 3 Revision 1
.. . – .: -, 2010. -

All Articles