RSA: de números primos a assinatura eletrônica

Descobrimos como e onde você pode obter uma assinatura eletrônica usando o exemplo do criptosistema RSA.

Conteúdo

Introdução
Definições e notação
Descrição do criptossistema RSA
1. Sistemas criptográficos assimétricos
2. Gerando chaves
3. Criptografia e descriptografia
4. Recebendo assinatura de mensagem por RSA
Assinatura eletrônica de documentos
Conclusão

Introdução

Certamente você já encontrou um conceito como "assinatura eletrônica". Se você recorrer à lei federal , poderá encontrar a seguinte definição:

« - , ( ) , »

, , , , - , . , , .

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

, , RSA, , 1978 . . , .

(A imagem mostra Lev Landau, o autor do "mínimo teórico") — ( , «»)

, :

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