授業中先生にバレない最強の暗号-RSA暗号-

小学校から中学校くらいだと、授業中先生に悟られることのないように友達と無駄話をしたり、先生の悪口を言ったりしたいですよね。

古くから生徒、児童たちはバビ語とか手紙とか、強者はモールス信号使ったりとかいろいろ工夫して授業中のおしゃべりに必死です。女の子が手紙を謎の折り方で畳んで渡してきて、「あの子まで回して!」とか言われた記憶もあるかと思います。

しかし、先生を侮ることなかれ、先生たちも子供の頃そう言うことをしてきた経験があるので、そんな子供が思いつくような暗号では内容が筒抜けです。

そこでQiitaを見るような優秀な児童、生徒の諸君に最強の暗号を教授したいと思います。その名も

RSA暗号!!!!!

RSA暗号は現代のセキュリティに大きく貢献している暗号化方式で、皆さんのパスワードやLINEなどの個人情報が盗まれないのもRSA暗号のおかげなんです。
暗号には、解読に必要な鍵が必要で、カエサル暗号では換字表、エニグマならプラグボード等の設定が鍵にあたり、それがないと解読できません。しかし、これらの暗号も現代の計算技術があれば一瞬で鍵を突破されてしまいます。

RSA暗号は数学で習う「素数」を使った暗号化技術で、巨大な素数の合成数の素因数分解が困難であることを利用した暗号です。日常の安全は素数によって守られています。

実はMathworksのFile Exchangeに解説を載せたことがあるんですが、Qiitaの方が読みやすいので再掲です。

概要

暗号化する前の文(平文)を $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$ が都合よすぎないか。そんな $u$ 存在するのか。
• 秘密鍵 $p,q$ から $u$ を計算できるのか。
• $u$ が $p,q$ から計算可能でも、公開されている $k$ や $m$ から $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$ とします。これらを見つける方法は

• 直感
• ユークリッドの互除法
• あるテクニックを使う

があります。今回は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 % 公開鍵

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

euler = (p-1)*(q-1) % オイラー関数
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 = 44    13    91    91    13   128    51   111     5   128   116   129    51    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 = 74 97 98 98 97 32 116 104 101 32 72 117 116 116

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

見事複合できました。

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

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

公開鍵 $m$ の桁数は大きくなくてはいけない。1024bit以下は非推奨。
$p,q$ のどちらも大きい数でなくてはいけない。素因数分解されやすいため。
$p,q$ が近い数ではいけない。フェルマー法で素因数分解可能。
$p.q$ を有名な素数にしない(メルセンヌ素数など)。
公開鍵 $m$ の生成時に同じ数を使いまわさない。
複合鍵 $u$ 、暗号化鍵 $k$ が小さすぎたり大きすぎたりしてはいけない。
etc...
なお、自作のRSA暗号を実用に用いようとするのはやめておいた方が良いです。この書類はあくまで 原理理解のためのものであり、実際の暗号はさらに注意深く計算されます。

まとめ

RSA暗号は鍵を見つけるのが大変難しいので、授業中の秘密のおしゃべりに最適だとお分かりいただけたと思います。
是非ご活用ください。