RSA: from prime numbers to electronic signature

We find out how and where you can get an electronic signature using the example of the RSA cryptosystem.

Content

Introduction
Definitions and notation
Description of the RSA cryptosystem
1. Asymmetric Cryptographic Systems
2. Generating keys
3. Encryption and decryption
4. Receiving message signature over RSA
Electronic signature of documents
Conclusion

Introduction

Surely you have come across such a concept as "electronic signature". If you turn to federal law , you can find the following definition:

« - , ( ) , »

, , , , - , . , , .

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

, , RSA, , 1978 . . , .

(The picture shows Lev Landau, the author of the "theoretical minimum") — ( , «»)

, :

– ,
– ,
– , ()
– , .
– .
– .
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