RSA暗号とは

情報処理

RSA暗号とは

RSA暗号とは、公開鍵暗号(非対象鍵暗号)の一種で、桁数が大きい合成数の素因数分解が困難であることを安全性の根拠とした暗号化方式です。RSAは、発明者であるリベスト(Rivest)、シャミア(Shamir)、エーデルマン(Adleman)の3人の頭文字をつなげたものです。

暗号化と複合化

送信者は受信者の公開鍵(暗号化鍵)で平文から暗号文を作成し、受信者は自分の秘密鍵(複合化鍵)で暗号文を平文に戻します。平文と暗号文、及び、暗号化鍵と複合化鍵の関係は以下で表されます。

送信者(暗号化) 受信者(複合化)
平文($M$)→ 暗号文($C$) 暗号文($C$)→ 平文($M$)
暗号化鍵($e,n$) 複合化鍵($d,n$)
$C=M^e\pmod{n}$ -① $M=C^d\pmod{n}$ -②

 鍵の作成

暗号化鍵と複合化鍵は以下のように作成します。

  1. 2つの大きな素数 $p$ と $q$ を適当に選択し、$n=pq$ を計算する
  2. $(p-1)(q-1)$ より小さく、互いに素である奇数 $e$ を適当に選択する
  3. $ed$ を $(p-1)(q-1)$ で割って余りが1になる数 $d$ を求める
    これを式で書くと、$ed\pmod{(p-1)(q-1)}=1$ となります
  4. 暗号化鍵($e,n$)を公開する(公開鍵)

暗号化鍵の($e,n$)は公開されているので、$p$ と $q$ が求めることができれば、複合化鍵 $d$ を得ることができます。しかし、$n$ から$p$ と $q$ を求めること($n=pq$)は計算量的に困難とされています。

複合化できることの証明

暗号化鍵と複合化鍵で、以下の条件を仮定し、

$$ed\pmod{(p-1)(q-1)}=1  -③$$

①で求めた暗号文($C$)に対し、②により平文($M$)に戻せること(次式)を証明します。

$$C^d\pmod{n}=M^{ed}\pmod{n}=M  -④$$

1つ目のイコール

④の1つ目のイコールが成り立つことを示します。①より、

$$C^d\pmod{n}=(M^e\pmod{n})^d\pmod{n}$$

任意の整数 $\alpha,\beta$ に対し、$M^e\equiv\alpha n+\beta$ と置くと、この右辺は、

$$((\alpha n+\beta)\pmod{n})^d\pmod{n}=\beta^d\pmod{n}$$

一方、

$$M^{ed}\pmod{n}=(\alpha n+\beta)^d\pmod{n}=\beta^d\pmod{n}$$

であることから、1つ目のイコールは成り立つことが分かります。

2つ目のイコール

④の2つ目のイコールが成り立つことを示します。③より、ある整数 $k$ に対し $ed=1+k(p-1)$ であるため、

$$M^{ed}\pmod{p}=MM^{k(p-1)}\pmod{p}=M\pmod{p}$$

となります。最後の項で、フェルマの小定理 $M^{p-1}\pmod{p}=1$ を使っています。従って、以下が得られます。

$$(M^{ed}-M)\pmod{p}=0$$

$q$ についても同様に考えると以下になります。

$$(M^{ed}-M)\pmod{q}=0$$

$p$ と $q$ は素数であるため以下が求められます。

$$(M^{ed}-M)\pmod{pq}=0$$

②より $M\lt n$($n=pq$)であるため、$M\pmod{pq}=M$ となり、2つ目のイコールが成り立つことが分かります。

 

情報処理
情報量、公開鍵暗号、ディフィ・ヘルマン鍵交換、量子コンピュータ、量子ビット、量子テレポーテーション
数理の散策路
力学、電磁気・相対論、熱・統計力学、量子力学、物性物理、機械学習、情報処理、金融、物理数学

Wikipedia

 

タイトルとURLをコピーしました