RSA: dari bilangan prima hingga tanda tangan elektronik

Kami mencari tahu bagaimana dan di mana Anda bisa mendapatkan tanda tangan elektronik menggunakan sistem kriptografi RSA sebagai contoh.

Kandungan

pengantar
Definisi dan notasi
Deskripsi dari sistem kriptografi RSA
1. Sistem Kriptografi Asimetris
2. Menghasilkan kunci
3. Enkripsi dan dekripsi
4. Menerima tanda tangan pesan melalui RSA
Tanda tangan elektronik dokumen
Kesimpulan

pengantar

Tentunya Anda telah menemukan konsep seperti "tanda tangan elektronik". Jika Anda beralih ke hukum federal , Anda dapat menemukan definisi berikut:

« - , ( ) , »

, , , , - , . , , .

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

, , RSA, , 1978 . . , .

(Gambar menunjukkan Lev Landau, penulis "teori 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