RSA暗号
a λ ( n ) = ( a p − 1 ) q − 1 ≡ 1 ( q − 1 ) ( mod p ) = 1 a λ ( n ) = ( a q − 1 ) p − 1 ≡ 1 ( p − 1 ) ( mod q ) = 1 {\displaystyle {\begin{aligned}a^{\lambda (n)}=(a^{p-1})^{q-1}\equiv 1^{(q-1)}{\pmod {p}}=1\\a^{\lambda (n)}=(a^{q-1})^{p-1}\equiv 1^{(p-1)}{\pmod {q}}=1\end{aligned}}}
よって ( a λ ( n ) − 1 ) {\displaystyle (a^{\lambda (n)}-1)} は p, q で割り切れるから a λ ( n ) ≡ 1 ( mod n ) {\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}} となり
a ′ ≡ ( a λ ( n ) ) x ⋅ a ( mod n ) ≡ 1 x ⋅ a ( mod n ) = a {\displaystyle a'\equiv (a^{\lambda (n)})^{x}\cdot a{\pmod {n}}\equiv 1^{x}\cdot a{\pmod {n}}=a}
RSA暗号が実現した公開鍵暗号方式は、従来の暗号方式(共通鍵暗号)とは異なり、暗号化は公開鍵を使って誰でもできるが、復号は秘密鍵を持つ本人だけしかできない方式である。この復号は「本人だけしかできない」という性質を利用すると、デジタル署名(あるいは認証機能)が実現できる。
そのためには、公開鍵・秘密鍵を次のように使用する。
暗号の場合 平文 → 公開鍵(暗号化)→ 暗号文、暗号文→ 秘密鍵(復号)→ 平文
署名の場合 文書 → 秘密鍵(署名生成)→ 署名値、署名値→ 公開鍵(署名検証)→ 文書
公開鍵と秘密鍵の役割は通常の場合においては上記の通り、公開鍵は暗号化に使われ、秘密鍵は復号に用いられるが、RSA暗号においては平文と暗号文の定義域が同じ(平文空間=暗号文空間である)ため、任意の文書(メッセージ)を暗号文とみなして復号することができる。つまり秘密鍵を用いて任意の文書について署名値を生成でき、公開鍵を用いてその署名値を暗号化して元の文書と一致するかを調べることで署名の検証ができる。
ただし、RSA暗号と同様に、生RSAでは、署名の潜在的偽造等の好ましくない性質があるため、パディングなどが必要である。また、暗号文空間よりも大きなメッセージを扱うためにハッシュ関数と組み合わせて使用する。
このようなパディングなども含めたものとして、
RSA_PSS with SHA-1
などがある。