公開鍵暗号

公開鍵暗号は公開鍵と秘密鍵の2つを用いた暗号方式で署名や鍵交換などに利用されます．

$x$ が与えられたときに $y=f(x)$ となる $y$ を計算するのは簡単ですが，$y$ から $x$ を求めるのが困難であるような問題を利用することでセキュリティを担保しています．

RSA

RSA は素因数分解の困難性を利用した暗号方式です． 2つの素数 $p, q$ について，合成数である $n = pq$ を計算するのは簡単ですが， $n$ から因数である $q, p$ を求めるのが困難であることを利用しています．

アルゴリズム

RSA を用いて安全にメッセージをやり取りする際のアルゴリズムを説明します．ここではメッセージを受信する人を Alice 送信する人を Bob とします．

鍵の生成

Alice は以下の操作で鍵を生成します．

1. 2つの大きな素数 $p, q$ を選び，$N = pq$ を計算する．
2. $\gcd((p-1)(q-1), e) = 1$ となる自然数 $e$ を選ぶ．
3. $ed \equiv 1 \pmod{(p-1)(q-1)}$ となる $d$ を求める．
4. $key_p = (N, e)$ を公開鍵，$key_s = d$ を秘密鍵とする．

暗号化

Bob は $key_p = (N,e)$ と平文 $M \in {0,1,2, \dots , N-1}$ を入力として暗号文

$$C = M^e \pmod N$$

を求めます．

復号

Alice は $key_s = d$ と $C$ から

$$M' \equiv C^d \pmod N$$

を求めます．ここで $M = M'$となるため，メッセージを復元できます．

署名のアルゴリズム

署名は安全性の要件のうち，認証（authentication）と否認不可（non-requdiation）を満たすことができます．

認証（authentication）：正当な署名者であることを証明する

否認不可（non-requdiation）：署名者はその署名を後で否定することができない

署名

署名者: Alice，受け手: Bob

1. Alice は公開鍵 $key_p = (N, e)$ と秘密鍵 $key_s = d$ を作成する．
2. Alice はメッセージ $M \in {0,\dots,N-1}$ に対して署名 $\sigma^e \equiv M^d \pmod N$ を計算し，$(M, \sigma)$ を Bob に送信する．
3. Bob は受信した $(M, \sigma)$ と公開鍵 $(N,e)$ を用いて $\sigma^e \equiv M \pmod N$ が成立すれば受理，そうでなければ否認する．

RSA 暗号の性質より

$$\sigma^e = (M^d)^e = M^{ed} \equiv M \pmod N$$