RSA：プライムナンバーから電子署名まで

RSA暗号システムの例を使用して、電子署名を取得する方法と場所を確認します。

コンテンツ

前書き
定義と表記
RSA暗号システムの説明
1. 非対称暗号システム
2. キーの生成
3. 暗号化と復号化
4. RSAを介してメッセージ署名を受信する
文書の電子署名
結論

前書き

きっとあなたは「電子署名」のような概念に出くわしたでしょう。連邦法に目を向けると、次の定義が見つかります。

« - , ( ) , »

, , , , - , . , , .

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

, , RSA, , 1978 . . , .

（写真は「理論上の最小値」の作者であるLev Landauを示しています） — ( , «»)

, :

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