技術メモ

役に立てる技術的な何か、時々自分用の覚書。幅広く色々なことに興味があります。

RSA暗号を実装してみる(理論編)

知識編で説明したように、RSA暗号の最大の特徴は暗号鍵から復号鍵を類推することが難しいというところにある。今回は、この特徴が数学的にどのように実現できているのかについて見ていく。
RSA暗号を実装してみる(知識編) - 技術メモ
RSA暗号を実装してみる(プログラム編) - 技術メモ

RSA暗号の原理

RSA暗号では暗号化の規則から復号化の規則を類推することが難しい。
その難しさの理由は、大きな2素数の積を素因数分解するのが事実上不可能というところを基礎とする。

この仕組みはフェルマーの小定理オイラー関数から成り立っているが、このことを順を追って説明していこう。

フェルマーの小定理

p素数a が任意の自然数のとき
(1)\begin{eqnarray} a^{p}≡a \pmod{p} \end{eqnarray}
特に,ap と互いに素な自然数のとき
(2)\begin{eqnarray} a^{p−1}≡1\pmod{p} \end{eqnarray}

証明

証明には数学的帰納法と鳩の巣原理を用いた方法がある。ここでは鳩ノ巣原理を使ったエレガントな方法で証明する。

apと互いに素でない時、すなわちa = np(n自然数)と表すことができる時、
(np)^p \equiv pとなり(1)の式は明らか。

apと互いに素な時、a,2a,3a,4a...(p-1)apで割った余りは1,2,3,4...(p-1) と一致する。
なぜならば、もしある自然数1\leq s,t\leq p-1, s\neq tsa \equiv taを満たすとすると、
(s-t)a\equiv 0となり、1\leq s,t\leq p-1, s\neq tに反するからである。
したがって,

\begin{eqnarray}
a\times 2a\times 3a \cdots \times(p-1)a &\equiv& 1\times 2\times 3 \cdots \times(p-1) \\
(p-1)!\times a^{p-1} &\equiv& (p-1)! \\
a^{p-1} &\equiv& 1
\end{eqnarray}


オイラー関数

自然数nに対して、n未満でnと互いに素な自然数の個数を\varphi(n)で表し、オイラー関数と呼ぶ。
例えば、12未満で12と互いに素な自然数\{1, 5, 7, 11\}なので\varphi(12) = 4

オイラー関数には以下のような性質がある。

(1)素数pに対して、\varphi(p)=p-1
(2)互いに素な自然数n,mに対して、\varphi(nm) = \varphi(n)\varphi(m)

これらより

異なる素数p,qに対して\varphi(pq) = (p-1)(q-1)

となる

RSA暗号に用いる定理

これまで説明したようなフェルマーの小定理オイラー関数を使って、RSA暗号で以下の性質が利用される。

異なる2つの素数p, qについて、n=pqとする。
自然数d, ede \equiv 1 \pmod{\varphi(n)}ならば、任意の自然数aに対して、a^{de}\equiv a \pmod{n}が成り立つ。

証明

anと互いに素でない時、明らかである

anと互いに素な時、nの約数p,qとも互いに素であり、
a^{de}\equiv a \pmod{p}かつa^{de}\equiv a \pmod{q}を示せば十分である。

まず、de \equiv 1 \pmod{\varphi(n)}より、
de-1=k(p-1)(q-1) (kは非負整数)と表せる。
したがって、
\begin{eqnarray}
a^{de} = (a^{de-1})\times a = (a^{(p-1)(q-1)})^{k} \times a 
\end{eqnarray}
フェルマーの小定理から以下が成り立つ

(a^{(p-1)})^{k(q-1)}\times a \equiv a \pmod{p} \\
(a^{(q-1)})^{k(p-1)}\times a \equiv a \pmod{q}
よって
a^{de}\equiv a \pmod{p}かつa^{de}\equiv a \pmod{q}が示された。

RSA暗号の暗号化・復号化の手順

では、実際にどのように暗号化復号化するのだろうか。
受信側Aから送信側Bにメッセージ P を送ることを考える。(メッセージは何かしらの符号化で数字になってるとする)

(A1) A は異なる2つの巨大な素数 p, q を選ぶ。そして、n = pq を計算する。
(A2) n に対するオイラー数 ϕ(n) = (p − 1)(q − 1) を計算する。
(A3) ϕ(n) 以下で、ϕ(n) と互いに素となる自然数 e を探す。
(A4) ϕ(n) 以下で、ed ≡ 1 (mod ϕ(n))を満たす自然数 d を求める。
(A5) p, q, ϕ(n), d を秘匿して、n と e のみを公開する。
それでは、BがAに暗号を用いて通信を行うにはどうすればよいか。
(B1) B が A に送りたい平文を P (<n)とする。B は  C = P^{e} \pmod{n} を計算して、C を A へ送る。
(A6) 暗号文 C を受信した A は D = C^{d} \pmod{n} によって復号化する。

上で説明した性質から D=P が成立するため、暗号・復号ができている。
(
\begin{eqnarray}
D &\equiv& C^{d} 
  &\equiv& (P^{e})^{d} 
  &=& P^{de} 
  &\equiv& P
\end{eqnarray})

復号化の困難性について

暗号鍵・復号鍵の具体的な内容についてはわかったと思うが、どうして暗号鍵から復号鍵を見つけることが難しいのだろう。
その理由は、e とn からd を導き出すことが難しいからだ。
d を知るには \varphi(n)を知らなければいけないが、 \varphi(n)を知るにはnの素因数分解ができなければいけない。このnの素因数分解はnが巨大になればなるほど難しくなってくるが、このことが復号鍵を類推することを難しくしている。



難しそうに書いてみたけれど、ひとつひとつ見てみるとそんなに複雑ではない気もする。次は実際にコーディングに取り掛かる。


関連記事:

参考サイト:
情報数理:暗号理論入門 高畑弘(pdf)
フェルマーの小定理の証明と例題 | 高校数学の美しい物語
RSA 暗号がようやく分かった気がしたのでまとめてみる - tsujimotterのノートブック

RSA暗号を実装してみる(知識編)

WEPキーに脆弱性があって突破されてしまうということを知ってから、最近暗号理論に興味をもって勉強していた。その中で、RSA暗号すげえってなったから実装してみたいと思う。単純そうに見えて奥深い。

今回はまず暗号について勉強した知識をまとめる。数学的なことやプログラムは後日書いていこうと思う。

続編
(RSA暗号を実装してみる(理論編) - 技術メモ
,RSA暗号を実装してみる(プログラム編) - 技術メモ)

暗号とは

そもそも暗号とは何か。
一言で言えば、第三者から通信内容を知られないように通信すること。
その上で満たすべき2つの条件がある。

1.「ある規則」を使って平文を暗号文に(暗号化)、暗号文を平文に(復号化)できる。
2.暗号文から「ある規則」を類推することが難しい。

※最近話題になったWEPkeyの突破は2.の条件が満たされていなかったことが原因っぽい。暗号文がたくさんあれば「ある規則」が類推できるようになってしまう。

RSA暗号の周辺知識

RSA暗号とは公開鍵暗号の一種。現在でも幅広く使われている暗号方式。

公開鍵暗号と対をなすのが共通鍵暗号といって、これは単純な暗号方式。
暗号化にも復号化にも同じ鍵を使うというもの。
だから、送信側と受信側のどちらも同じ鍵を持ち、それを秘密にする。

一方で公開鍵暗号は、公開する鍵と秘密にする鍵のペアがあり、それぞれ別々に暗号と復号の役割を担っている。
暗号化のための鍵は公開しているため、誰でも暗号化ができる。
逆に復号化の鍵は秘密にしているので、鍵を持つ者しか復号化できない。
この特徴によって、受信側が誰からも安全にデータを受け取ることを可能にしている。

公開鍵暗号の特徴として、暗号鍵から復号鍵を推測することが事実上不可能ということがある。
これが共通鍵暗号公開鍵暗号の違うところで、暗号はできるが復号ができないという点が公開鍵方式を実現している。

f:id:swdrsker:20161222030558p:plain

どうしてこんな面倒くさいことが必要なのか?

共通鍵方式だと
1.そもそも鍵の受け渡しの途中で傍受されてしまうとダメ
2.多人数間で通信する場合でも2者間の共通鍵が必要
という弱点があるためだ。

安全に双方向通信ができるハイブリッド方式

そこで、公開鍵暗号共通鍵暗号を組み合わせたハイブリッド方式というものがある。
ハイブリッド方式はこのような方法で双方向通信を可能にする。

1.クライアントがSSLでのアクセスをサーバ要求します。
2.サーバは、サーバの公開鍵を含む証明書をクライアントに送ります。
3.クライアントは、証明機関の公開鍵を使って、証明書を復号、検証を行い、サーバ側の公開鍵を手に入れます。
4.クライアントは、一時的な共通鍵を生成し、サーバの公開鍵で暗号化して、サーバに送ります。
5.サーバは、クライアントから暗号化された共通鍵を受け取り、自分の秘密鍵で復号し、共通鍵を手に入れます。
6.同じ共通鍵で、クライアントとサーバは通信を始めます。

引用:@IT:連載 XML Webサービスのセキュリティ実装 第3回 SSLを利用した暗号化(サーバ編)

公開鍵方式のみで、最初に公開鍵Aを使って新しく作成した公開鍵Bと秘密鍵Bを受け渡すという方法も考えられるが、このハイブリッド方式を使うのは計算時間の問題もある。公開鍵方式の場合、共通鍵方式に比べ格段に暗号化復号化に時間がかかるのだ。
そのため、大規模なデータをやり取りする必要がある場合にもハイブリッド方式を使うことがある。


参考サイト:
ハイブリッド暗号方式 : 情報セキュリティスペシャリスト(情報処理安全確保支援士) - SE娘の剣 -
cryptography - How does WEP wireless security work? - Information Security Stack Exchange
@IT:連載 XML Webサービスのセキュリティ実装 第3回 SSLを利用した暗号化(サーバ編)



pythonでニューロンのシミュレーション(Brianについて)2

スパイキングニューロンのシミュレータを触ってみる記事の2回目。
以前の投稿の続きとして、サンプルにはないものを書いてみた。

izhikevichモデルニューロンの集団発火

サンプルではLIFモデルだったが、izhikevichモデルで同じものを作ってみる。
プログラムはこのサイトのものをほぼパクらせて参考にさせていただいた。この場を借りて感謝したい。Thank you!!!
Google グループ
Google グループ

手を加えたところ

  1. brianからbrian2に対応させるために細かいところを改変
  2. 内部の結合を追加
  3. モニタで可視化


ニューロン数は2000。興奮抑制バランスは4:1。
結合率はizhikevichの公開プログラムを参考に1ニューロンに結合するシナプスが100くらいになるようにした。あとの各種パラメータはほとんど元のプログラムまま。
Polychronization: Computation With Spikes(Izhikevich 2006)

実際のコード

from brian2 import *

def izhikevich_model():
    def draw_normals(n,start,stop):
        mu,sigma,numbers = start+(stop-start)/2, (stop-start)/6, zeros(n)
        for i in range(n):
            s = -1
            while (s<start) or (s>stop) :
                s = numpy.random.normal(mu,sigma,1)
                numbers[i]=s
        return numbers

    n = 2000 # number of neurons
    R = 0.8  # ratio about excitory-inhibitory neurons

    eqs = Equations(''' 
    dv/dt = (0.04/ms/mV)*v**2 + (5/ms) * v + 140*mV/ms - u + I_syn/ms + I_in/ms : volt
    du/dt = a*((b*v) - u) : volt/second
    dx/dt = -x/(1*ms) : 1
    I_in = ceil(x)*(x>(1/exp(1)))*amplitude : volt
    dI_syn/dt = - I_syn/tau : volt
    a : 1/second
    b : 1/second
    c : volt
    d : volt/second
    amplitude : volt
    tau : second
    ''')
    
    #reset specification of the Izhikevich model
    reset = '''
    v = c
    u += d
    '''
    
    #2nd: Define the Population of Neurons P
    P = NeuronGroup(n, model=eqs, threshold='v>30*mvolt', reset=reset, method='euler')
    
    #3rd: Define subgroups of the neurons (regular spiking/fast spiking)
    Pe = P[:int(n*R)]
    Pi = P[int(n*R):]

    #4th: initialize starting neuronal p"""!!!<<<nicht wie im Paper>>>!!!"""arameters for the simulation
    Pe.a = 0.02/msecond
    Pe.b = 0.2/msecond
    Pe.c = (15*draw_normals(int(n*R),float(0),1) - 65) * mvolt
    Pe.d = (-6*draw_normals(int(n*R),float(0),1) + 8) * mvolt/msecond
    Pe.tau = draw_normals(int(n*R),float(3),15) * msecond
    Pi.a = (0.08*draw_normals(n-int(n*R),float(0),1) + 0.02) * 1/msecond
    Pi.b = (-0.05*draw_normals(n-int(n*R),float(0),1) + 0.25) * 1/msecond
    Pi.c = -65 * mvolt
    Pi.d = 2 * mvolt/msecond
    Pi.tau = draw_normals(n-int(n*R),float(3),15) * msecond
    P.x = 0
    P.v = draw_normals(n,float(-50),float(-25)) * mvolt
    P.amplitude = draw_normals(n,0,8) * mvolt
    
    #5th: Connect synapses
    Ce = Synapses(Pe, P, on_pre='I_syn+=1.5*mV')
    Ce.connect(p=0.05)
    Ci = Synapses(Pi, P, on_pre='I_syn-=8*mV')
    Ci.connect(p=0.05)
    
    #6th: Run & monitor
    M = SpikeMonitor(P)
    V = StateMonitor(P,'v',record=True)
    run(500*ms)
    subplot(211)
    plot(M.t/ms, M.i, '.')
    subplot(212)
    plot(V.t[:200]/ms, V.v[0][:200]/mV, 'r')
    plot(V.t[:200]/ms, V.v[100][:200]/mV, 'g')
    plot(V.t[:200]/ms, V.v[200][:200]/mV, 'b')
    show()

    
if __name__=="__main__":
    izhikevich_model()

実行結果

f:id:swdrsker:20161207230552p:plain
以前の記事のLIFモデルのように発火が続かないがパラメータによるところが大きいから気にしなくてもいいと思う。
下の図は適当にとってきたニューロンの膜電位。ラスタープロットだとめっちゃ発火してるように見えるけど、実際はそんな発火してないよねってことを確認したかった。

    '''
    dx/dt = -x/(1*ms) : 1
    I_in = ceil(x)*(x>(1/exp(1)))*amplitude : volt
    '''

の部分は外部刺激に対応する項だけど今回は使わなかった。
I_synとI_inをなんでこんな形で書き分けるのか謎。全部I_synで良くない?誰か教えて欲しい。

感想

brianは書き方が独特すぎてしんどい。(自由度が高いとしょうがないよね。)
サンプルを見ながら試行錯誤するか、最悪ソースを直接見に行くかしないと解決しないことがあってつらいね。
変数に単位があるっていうのは嫌いじゃないんだけどもっと良い方法はなかったのかね。1*second って…
それと、サンプルがだいたい

from brian2 import *

の形で書かれてて、いつか変数名で問題起こしそうでひやひやする…


関連記事:
pythonでスパイキングニューロンのシミュレーション (Brianについて) - 技術メモ