RSA暗号

RSA暗号とは、桁数が大きい合成数の素因数分解問題が困難であることを 安全性の根拠とした公開鍵暗号の一つである。 暗号とデジタル署名を実現 できる方式として最初に公開されたものである。by Wikipedia.

RSA暗号は、暗号化理論の中では有名であり、名前を聞いたことがある人も多いと思います。 しかし、原理まで把握している人は意外と少ないのではないでしょうか。この書類では、RSA暗号の基本 を説明し、皆さんの頭の中のモヤモヤを解消することを目標としています。1つモヤモヤが解消されると 新たなモヤモヤが生まれるのが世の常ってものですので、結果的にモヤモヤを解消するという目的は達成されない でしょう。

理解するにあたって、それなりの初等整数論の基礎が必要かもしれませんが、 多分理解できると思います。

Contents

概要

暗号化する前の文(平文)を $P$ 、暗号化後の文(暗号文)を $C$ とします。

$P, C$ は文字などを符号化した数字です。当然、暗号文がただ一人にしか復号できないことが求められます。 RSA暗号ではこのことを暗号鍵 $k$ 、公開鍵 $m$ を用いて、以下のように式で表現します。 $k,\ m$ は 公開されています。

RSA暗号では公開鍵 $m$ は素数 $p, q$ を用いて以下のように定義します。 $p, q$ は誰にも公開してはいけませんよ。

$$m=pq$$

$$P^k\equiv C\ ({\rm mod}\ m)$$

復号の際、復号鍵 $u$ を用いて $C$ から $P$ が復号可能だと仮定すると、 その式は以下のようにできます。

$$C^u\equiv P\ ({\rm mod}\ m)$$

ここまでで以下のことがわかります。

$$\left(P^k\right)^u\equiv P\ ({\rm mod}\ m)$$

任意の $P$ に対して、上式が成り立つような都合のいい $u$ が存在すれば、 $u$ を知っている人 のみが復号できるというわけです。

なんだかすごそうに紹介しましたが、よく読むと以下の疑問が残ります。

復号鍵 $u$ は存在するか

概要で示したように、

$$P^{k\cdot u}\equiv P\ ({\rm mod}\ m)$$

が成り立つ $k\cdot u$ が存在するかが、問題になります。つまり、任意の数 $P$ に対して $k\cdot u$ 乗し、 $m$ で割った余りをとると $P$ に戻るような $k, u$ が存在する。そんな都合のいい数があるのかということです。

実はあります。奥様。

オイラーの定理を使うだけであらフシギ!そんな都合のいい数が見つかるんですよ!お得でしょ??

では、オイラーの定理から式を導出してみましょう。ちなみに上の式を暗号化の条件式と呼ぶことにしましょう。

オイラーの定理

正整数 $a,m$ に対して $a,m$ が互いに素であるとき、以下が成り立つ。

$$a^{\varphi(m)}\equiv 1\ ({\rm mod}\ m)$$

$\varphi(m)$ はオイラー関数である。

オイラー関数とは、「 $m$ より小さい正の整数のうち、 $m$ と互いに素であるものの個数」を表す関数です。

$m=15$ だった場合、 $m$ より小さく、 $m$ と互いに素であるものは1,2,4,7,8,11,13,14なので、 $\varphi(15)=8$ となります。 $m$ が素数だった場合、当てはまる数は $1,2,\cdots,m-1$ なので、 $\varphi(m)=m-1$ です。 オイラーの定理がフェルマーの小定理の拡張であることは置いておいて、 $m=p$( $p$ は素数)だった場合、 オイラーの定理より、

$$a^{p-1}\equiv 1\ ({\rm mod}\ p)$$

となります。なんだか暗号化の条件式に似ていると思いませんか? ここで突然ですが、オイラーの定理の式で、 $a$$P$ に置き換え、式を $v$ 乗し、両辺に $P$ を掛けます。

$$P^{\varphi(m)\cdot v+1}\equiv P\ ({\rm mod}\ m)$$

暗号化の条件式と、乗数を比較するとこうなります。

$$k\cdot u=\varphi(m)\cdot v+1$$

ここまでを整理すると、上式はオイラーの定理から導かれたものなので、 整数 $u,v$ が存在し、 $u>0$ であれば、暗号文を復号できるということです。 ちょっと式を変形します。

$$k\cdot u-\varphi(m)\cdot v=1$$

今の高校教育過程を勉強した方ならわかるでしょう。そうです一次不定方程式です。

一次不定方程式の整数解

$a,b$ を互いに素な整数としたとき、以下の方程式を満たす整数解 $u,v$ が存在する。

$$au+bv=1$$

$a=k,b=\varphi(m),v\rightarrow -v$と置き換えれば完全に同じ式です。 $k$ は 適当に選んだ数で、 $\varphi(m)$ と互いに素であれば、 $u,v$ が必ず存在することが示せます。

まだ終わりません。まだ $u\leq 0$ の可能性があります。でも安心してください。整数解には一般解 が存在し、解は無数に存在します。一般解を求めるには、まず方程式を満たす $u,v$ を1組求める必要があります。 その1組の解を $u_0,v_0$ とします。これらを見つける方法は

  1. 直感
  2. ユークリッドの互除法
  3. あるテクニックを使う

があります。今回は3つ目を使います。ユークリッドの互除法を知らない方は、現行の高校数学Iをご覧くださいませ。

テクニックは簡単で、「 $a,b$ が互いに素なら、 $a,2a,\cdots,(b-1)a$$b$ で割った 余りは全て異なるので、余りが1になるものが存在する。」というものです。これは背理法で簡単に証明できます。

というわけで、余りが1となるものを $sa$ とおき、 $b$ で割った商を $t$ とすると、

$$sa=bt+1$$

となりますので、 $s,t$ は一次不定方程式の解になります。 目的を見失いそうですが、今は一次不定方程式の一般解を求めようとしています。 $u_0,v_0$ が解なので、 以下の式が成り立ちます。

$$au_0+bv_0=1$$

元の式との差を取ると

$$a(u-u_0)+b(v-v_0)=0$$

$a,b$ は互いに素ですから、 $u-u_0=bl,\ v-v_0=al$ ( $l$ は整数) と置けます。よって一般解は

$$u=bl+u_0$$

$$v=al+v_0$$

となります。ずいぶん話が飛びましたが、これで復号鍵 $u$ が正整数として必ず存在することがわかりました。 その条件として、 $k$$\varphi(m)$ と互いに素である必要があり、 $m=pq$ ( $p,q$ は素数)でした。 $\varphi(m)=(p-1)(q-1)$ となります。そして大事なことは、「復号鍵 $u$ を求めるには、mを素因数分解するか、 あらかじめ $p,q$ を知っているか」しかありません。 $p,q$ の選び方によっては素因数分解はものすごく 難しいので、あらかじめ $p,q$ を知っている人以外ほぼ復号できないわけです。

暗号化の例

まず平文 $P$ は以下のようにします。アルゴリズム上、mでmodを取るので、平文の数は全てmより小さい数である必要があります。 実際のRSA暗号では、mがものすごく大きいため、あまり意識することはありません。

P=[74 97 98 98 97 32 116 104 101 32 72 117 116 116]; % 平文

$P$$k$ 乗して $m$ で割った余りを取りますが、 $m=pq$ ( $p,q$ は素数)で、$k$ と $\varphi(m)=(p-1)(q-1)$ は互いに素なので、適当に $k$ を選びます。

p=7; % 素数1
q=19; % 素数2
m=p*q % 公開鍵
m =

   133

$k$$\varphi(m)$ と互いに素なので、とりあえず $k=5$ とする。

euler=(p-1)*(q-1) % オイラー関数
k=5 % 暗号化鍵
euler =

   108


k =

     5

$k$ が求められたので、暗号化はできます。暗号文 $C$ は以下のようになります。暗号化鍵 $k$ が大きいと 桁数が多くなりすぎて計算結果が正しく出ないので、 $P$ を1回づつかけて、その都度modを取るようにしています。

C=ones(size(P)); % 初期値

for idk=1:k % =mod(C.^k,m)
    C=mod(C.*P,m);
end

C % 暗号文
C =

  1 列から 13 列

    44    13    91    91    13   128    51   111     5   128   116   129    51

  14 列

    51

復号の例

さあ後はこれを複合します。受信側は $p=11,q=17$ であることを知っていますので、 $\varphi(m)$ は容易に計算できます。受信側での $\varphi(m)$ の計算は今回省略します。これらの情報から 複合鍵 $u$ を計算します。 $u$ を求めるには、一次不定方程式 $ku+\varphi(m)(-v)=1$の 解( $u$ は正)を求めれば良いのでした。上で説明したテクニックを使います。

$k,\varphi(m)$ は互いに素なので、まず[ $k,2k,3k,\cdots,(\varphi(m)-1)k$ ]を作ります。長いので結果は省略します。

k_mul=k:k:(euler-1)*k; % kの倍数

これを $m$ で割ったあまりを求めます。

k_mul_mod=mod(k_mul,euler); % kの倍数の剰余
adr=find(k_mul_mod==1) % 剰余が1になるアドレス
adr =

    65

剰余が1になるものはただ1つであることが確認できました。よって以下のものが一次不定方程式の 解になります。

u0=k_mul(adr)/k % =adr
v0=(k_mul(adr)-1)/euler
u0 =

    65


v0 =

     3

一次不定方程式の一般解を求めましょう。上の説明より、解は $u=\varphi(m)l+u_0, v=kl+v_0$ となるのでした。したがって、 $l$ を1から順番に増加させて、正の $u$ を探しましょう。 (お気付きの通り、上で説明した方法だと確実に正の整数解が求まりますので、ユークリッドの互除法を使った方 のために以下のコードを示しておきます。)

l=0; % 初期値
u=u0; % 初期値

while u<0
    u=euler*l+u0;
    l=l+1;
end

disp(['u=' num2str(u)])
u=65

やっと複合です。暗号文 $C$$u$ 乗し、公開鍵 $m$ で割った余りを求めます。単純に累乗してしまうと桁数が多くなりすぎて計算結果が正しく出ないの で、わざとループを使って、1回Cをかけるごとにいちいちmodを取るという動作をしています。

P_decryp=ones(size(C)); % 初期値

for idu=1:u % P_decryp=mod(C.^u,m)
    P_decryp=mod(P_decryp.*C,m);
end

P % 平文
P_decryp % 複合後の数列
P =

  1 列から 13 列

    74    97    98    98    97    32   116   104   101    32    72   117   116

  14 列

   116


P_decryp =

  1 列から 13 列

    74    97    98    98    97    32   116   104   101    32    72   117   116

  14 列

   116

見事複合できました。

平文 $P$ が0や1の場合、平文と暗号文が一致するので、実際のRSA暗号では平文 $P$ にある数を加算して、 確実に暗号化できるように工夫されます。

また、RSA暗号では素因数分解の煩雑性を利用していますが、鍵の桁数が多くても素因数分解しやすい ことがあります。注意点の例は以下のとおり。

なお、自作のRSA暗号を実用に用いようとするのはやめておいた方が良いです。この書類はあくまで 原理理解のためのものであり、実際の暗号はさらに注意深く計算されます。

RSA暗号は、インターネット上のプライベートな通信(Twitter, LINE, Facebook等)に使われており、 個人間のやりとりが第三者に傍受されないのも、RSA暗号のおかげであり、ユークリッド、ガウス、フェルマー、 オイラーなどの業績がなければ開発されませんでした。定理の発見、証明から数百年後の社会をこんなにも便利に できるというのは、数学の大きな意義です。これを見ている高校生や中学生諸君(がどれほどいるかわからないが) は、数学なんて意味わからないとバカにしないでいただきたいです。我々の世界は数学によって プライバシーやセキュリティが保証されているのです。