技術メモ

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

RSA暗号を実装してみる（プログラム編）

数学 Python 暗号理論

前回まではRSA暗号の原理を説明してきたけれど、いよいよ本題。実際コーディングに取り掛かる。理論では簡単に説明されるところでも実際にコーディングしてみると難しいところがある。
RSA暗号を実装してみる（知識編） - 技術メモ
RSA暗号を実装してみる（理論編） - 技術メモ

RSA暗号の暗号化復号化の手順（復習）

(A1) A は異なる２つの巨大な素数 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 のみを公開する。
(B1) B が A に送りたい平文を P (＜ｎ)とする。B は C = P^{e} \pmod{n} を計算して、C を A へ送る。
(A6) 暗号文 C を受信した A は D = C^{d} \pmod{n} によって復号化する。

D=Pとなる理由は理論編で。

実際のコード

from math import sqrt, log10
import random

class RSA:
    def __init__(self,
                 upper_limit,
                 randomseed=None):
        random.seed(randomseed)
        primes = self.prime_list(upper_limit)
        self.p = [0,0]
        p = [int(pow(10, random.random() + log10(upper_limit) - 1)) - 1 for i in range(2)]
        for i,x in enumerate(p):
            while not primes[x-2]:
                x = x-1
            self.p[i] = x
        self.n = self.p[0] * self.p[1]
        self.euler = (self.p[0] - 1) * (self.p[1] - 1)
        x = int(pow(10, random.random() + log10(upper_limit) - 1)) - 1
        while not primes[x-2]:
            x = x-1
        self.e = x
        self.d = self._set_public_key()

    @staticmethod
    def prime_list(n):
        def mark(primes,x):
            for i in xrange(2*x, n, x):
                primes[i-2] = False
        primes = [(i%2!=0 and i%3!=0 and i%5!=0) for i in range(2,n)]
        primes[0] = primes[1] = primes[3] = True
        for x in xrange(7, int(sqrt(n))+1):
           if primes[x-2]: mark(primes,x)
        return primes

    @staticmethod
    def pow_mod(x, y, z):
        n = 1
        while y:
            if y & 1:
                n = n * x % z
            y >>= 1
            x = x * x % z
        return n

    def _set_public_key(self):
        def xgcd(b, n):
            x0, x1, y0, y1 = 1, 0, 0, 1
            while n != 0:
                q, b, n = b // n, n, b % n
                x0, x1 = x1, x0 - q * x1
                y0, y1 = y1, y0 - q * y1
            return  b, x0, y0
        g,x,_ = xgcd(self.e, self.euler)
        d = x % self.euler
        return d

    def encrypt(self, plain):
        cipher = self.pow_mod(plain, self.e, self.n)
        return cipher

    def encrypt_with_external_pubkey(self, plain, e, n):
        cipher = self.pow_mod(plain, e, n)
        return cipher

    def decrypt(self, cipher):
        plain = self.pow_mod(cipher, self.d, self.n)
        return plain

    def decrypt_with_external_seckey(self, cipher, d, n):
        plain = self.pow_mod(cipher, d, n)
        return plain

    def get_secret_keys(self):
        return [self.p, self.euler, self.d]

    def get_public_keys(self):
        return [self.n, self.e]


def decrypt_test():
    rsa = RSA(1000000)
    plain = int(random.random()*100000000)
    print("plain:%d"%plain)
    cipher = rsa.encrypt(plain)
    print("cipher:%d"%cipher)
    replain = rsa.decrypt(cipher)
    print("replain:%d"%replain)
    pubkeys = rsa.get_public_keys()
    seckeys = rsa.get_secret_keys()
    print("public keys -- n:%d, e:%d"%(pubkeys[0],pubkeys[1]))
    print("secret keys -- (p, q):(%d, %d), euler:%d, d:%d"%(seckeys[0][0], seckeys[0][1], seckeys[1], seckeys[2]))

if __name__=="__main__":
    decrypt_test()

実行結果

plain:94192148
cipher:805896119
replain:94192148
public keys -- n:71467294553, e:415111
secret keys -- (p, q):(343393, 208121), euler:71466743040, d:28686310711

ちゃんと元の平文が再現されていることがわかる。うまくいったネ。
たしかに71467294553の素因数分解は難しそう…。実際には300桁くらいの素数ペアを使うので、600桁以上の数を素因数分解しなければいけなくなるらしい。
そりゃ安全なわけだ…

解説

素数リストの作成

素数のリスト作成にはエラトステネスの篩を使った。※参考サイトの欄に載せておきます。
実際にSSHなどで使われている素数は300桁ほどあり、こんな方法じゃ余裕でオーバーフローしてしまう。そこで素数を探し出すには確率的素数判定法なるものを使うのだが、自分自身よくわかっていないので、解説はまたいつかということで。確率的素数判定法 vs. エラトステネスの篩 - 技術メモ

素数ペアの選定

素数のペアを出してくる際には、2つともできるだけ大きい素数であることが望ましい。そこで、桁数を絞る工夫をしてある。上限値の対数を取って±1以内に収まるようにした。末尾で１を引く処理をしいるのは、万が一乱数が0.999999999999...となった場合インデックス外になってしまってエラーを吐くから。
秘密鍵のeにはある程度大きい数を使った方が良いらしいが、直接互いに素な大きい数を探し出す高速な方法がわからず、予め求めた素数リストから抜き出すようにした。

公開鍵の作成

公開鍵の作成には拡張ユークリッド互除法を使う。※参考サイトの欄に乗せておきます。

暗号化復号化

暗号化復号化には馬鹿でかい数の指数を扱うのでpow(e,d)%nじゃ時間もメモリも足りない。そこでベースを掛けるたびに剰余を計算する方法をとる。
※参考サイトをそのまま参考にしたので下の欄に乗せておきます。
※pythonではどうやらx^y%zの計算はpow(x,y,z)でできるらしい！さすがpython！



関連記事：


参考にしたサイト：

http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/ExEuclid.html
2014-06-10
http://blanktar.jp/blog/2013/10/python-modular-exponentiation.html

RSA暗号を実装してみる（理論編）

数学 暗号理論

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

RSA暗号の原理

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

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

フェルマーの小定理

p が素数，a が任意の自然数のとき
（１）\begin{eqnarray} a^{p}≡a \pmod{p} \end{eqnarray}
特に，a が p と互いに素な自然数のとき
（２）\begin{eqnarray} a^{p−1}≡1\pmod{p} \end{eqnarray}

証明

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

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

aがpと互いに素な時、a,2a,3a,4a...(p-1)a をpで割った余りは1,2,3,4...(p-1) と一致する。
なぜならば、もしある自然数1\leq s,t\leq p-1, s\neq tがsa \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暗号で以下の性質が利用される。

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

証明

aがnと互いに素でない時、明らかである

aがnと互いに素な時、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 は異なる２つの巨大な素数 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 (＜ｎ)とする。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)を知るにはｎの素因数分解ができなければいけない。このｎの素因数分解はｎが巨大になればなるほど難しくなってくるが、このことが復号鍵を類推することを難しくしている。



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


関連記事：

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

RSA暗号を実装してみる（知識編）

暗号理論

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

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

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

暗号とは

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

１．「ある規則」を使って平文を暗号文に（暗号化）、暗号文を平文に（復号化）できる。
２．暗号文から「ある規則」を類推することが難しい。

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

RSA暗号の周辺知識

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

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

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

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

f:id:swdrsker:20161222030558p:plain

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

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

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

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

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

引用：＠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を利用した暗号化（サーバ編）