オオハタの研究ノート

考えたこととか勉強したこととか、書いていきます。

SketchRNN を作った

SketchRNN を作った

この記事は群馬大学電子計算機研究会 IGGG Advent Calendar 2019 - Adventar 15 日目の記事です。一週間遅れの.

B3 であるということもあり,研究室ではあまり成果を要求されることはないので ゆるりとやっており,その一環として SketchRNN を作りました.

結果はこんな感じです.

f:id:KenjiOhata:20191222192536p:plain

モデル概要

SketchRNN は Google の Magenta プロジェクトの一環として作られたスケッチ生成のための モデルです.

中身の基本はは seq2seq の VAE になっています.筆の動きを表す,ストロークデータを 入力することで,ストロークを再現するように学習します.

左が入力で右が出力になります.

f:id:KenjiOhata:20191222192539p:plain

SketchRNN では ニューラルネットワークの出力はストロークデータではなく, ストロークデータを生成するような確率分布のパラメータを出力します. これにより,ランダム性を残しながらスケッチ生成ができます.

詳細は論文を参照ください. https://arxiv.org/abs/1704.03477

Julia -> Pytorch

SketchRNN の作成に取り掛かったのは 11 月中旬くらいでした. 最初の段階では Julia と Flux.jl で実装することを考えていました.

Julia 採用理由として

Python のようにライブラリを通して行列演算をすることの煩わしさがないことや, exp などから標準であること,Unicode の利用で コードの見た目がかなり簡潔になることか挙げられます.

また,Julia 自体にも興味があったので速度の面や実用さを知りたかったというのもあります.

結果として,Pytorch で書き直すことになりました.

自分が書いたコードが GPU で動かなかったからです. 公式サンプルは動きますが,僕の書いたコードはエラーが残ってしまいました. 追求すれば解決できるかもしれませんでしたが,GPU で動かすことに時間を費やすことは SketchRNN 実装とは違うので本筋を見失わないうちに Pytorch に移行しました.

ただ,Julia はマクロ機能や Unicode などほんとにいい言語だと思いました. Flux.jl もまだバージョン 1 にもなっていない(2019/12 現在)のでまだ,成長を待つ段階 なのだと思いました.

オンプレ機械学習いいな

初めてオンプレでまともに機械学習をしました. 今までは Google Colab を使用して来ましたが,時間制約のおかげで, 12 時間毎に操作が要求されたり,その間のコンピュータの使用が制限されるなど ろくなものではなかったので,オンプレ最高でした.研究室に感謝です.

今回作成した SketchRNN-Pytorch のレポジトリはこちらにおいておきます.

github.com

RSA 暗号を Python で書く

RSA 暗号を Python で書く

この記事は群馬大学電子計算機研究会 IGGG Advent Calendar 2019 - Adventar 2 日目の記事です。

アドベントカレンダーを 2 日連続でやるって決めたのは自分だったのですが,なかなか大変でした. というのも,一応研究室での活動として SketchRNN というものを Julia で実装しているのですが,どうにもうまく行かず,,. 時間ばかりが溶けるということになりました.

さて,本題ですが,先日 に引き続き RSA 暗号の話をします.

概要

  1. 十分に大きい素数p, qより,共通鍵n=p\cdot qを求める.
  2. \phi(n) = (p-1)(q-1)を求める.
  3. \phi(n)と互いに素な数として素数kを求める.
  4. 拡張ユークリッドの互除法を用いて,一次不定方程式 kd + v\phi(n) = 1を解き,秘密鍵$v$を獲る.

コード

コードです.

def gcd(a: int, b: int) -> int:
    """
    最大公約数を求める

    >>> gcd(18,12)
    6
    >>> gcd(35,14)
    7
    """
    assert a > 0 and b > 0
    if a < b:
        return gcd(b, a)

    return gcd(b, a % b) if a % b != 0 else b


def ex_euclid(a, b):
    """
    一次不定方程式 ax+by = gcd(a,b)を解く
    (a > b)

    returns
    -------
    n : int
        n = gcd(a,b)
    x : int
        解x
    y : int
        解y
    """
    assert a > b and b > 0

    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q = m // n
        x1, y1, m, x2, y2, n = x2, y2, n, x1-q*x2, y1-q*y2,  m-q*n

    return (n, x2, y2)


def is_prime(p: int) -> bool:
    """
    素数判定

    >>> is_prime(13)
    True
    >>> is_prime(4)
    False
    >>> is_prime(1)
    False
    """

    assert p > 0

    if p == 1:
        return False

    i = 2
    while i * i <= p:
        if p % i == 0:
            return False
        i += 1

    return True


def find_a_prime_less_than(n: int) -> int:
    """
    n より小さい素数の中で最大の素数を探す

    >>> find_a_prime_less_than(13)
    11
    >>> find_a_prime_less_than(7)
    5
    """

    for i in range(n-1, 1, -1):
        if is_prime(i):
            return i

    raise ValueError


def gen_key(p=643, q=499):
    """
    RSA暗号鍵を生成

    return
    ------
    n :int
        共通鍵
    k :int
        公開鍵
    d :int
        秘密鍵
    """
    assert is_prime(p) and is_prime(q)

    n = p * q
    phi_n = (p-1)*(q-1)  # Eular function
    k = find_a_prime_less_than(phi_n)

    _, _, d = ex_euclid(phi_n, k)

    # 一次不定方程式の解であることを利用する
    while d <= 0:
        d += phi_n

    return (n, k, d)


def power_mod(a: int, k: int, n: int) -> int:
    """
    a^k mod n を計算する

    >>> power_mod(15,5,91)
    71
    >>> power_mod(71,29,91)
    15
    """
    return (a ** k) % n


def encrypt(data: int, k: int, n: int) -> int:
    """
    RSA暗号による暗号化を行なう

    >>> encrypt(15,5,91)
    71
    """
    assert data > 0 and k > 0 and n > 0
    return power_mod(data, k, n)


def decrypt(data: int, d: int, n: int) -> int:
    """
    RSA暗号による復号化を行なう

    >>> encrypt(71,29,91)
    15
    """
    assert data > 0 and d > 0 and n > 0
    return power_mod(data, d, n)

改善点

  1. 素数生成の部分が自動化されていない.

素数表何かを使うことで解決できそう.実用では 2019 年現在 2048bit 位の大きさが要求されています.

  1. あまり早くない,公開鍵用の素数生成.
  1. \phi(n)と互いに素な数として素数kを求める.

のステップで,今回のプログラムでは\phi (n)以下から線形探査していますが,遅いです. 本番では 65537 が使われることが多いそうです.

結び

コードを貼り付けるだけになってしまったような気がしますね. Python3 の整数型はオーバーフローしないので, 脳死で書けるのがいいですね.

ということで RSAPython での実装でした.

拡張ユークリッドアルゴリズムについてはまたいつか記事書きます.

RSA 暗号の数学的背景を理解する

RSA 暗号の数学的背景を理解する

この記事は群馬大学電子計算機研究会 IGGG Advent Calendar 2019 - Adventar 1 日目の記事です。

もう冬ですね.アドベントカレンダーの季節です.内容は RSA 暗号です.

RSA 暗号は公開鍵暗号の一つで,因数分解の難しさを根拠にしている暗号です. この記事の目標としては,RSA 暗号の概略がわかり,「因数分解の難しさがどう暗号の難しさに寄与しているのか」を理解することです.

まずは RSA 暗号が使われている.公開鍵暗号通信について概略を理解します.

公開鍵暗号通信

ネットワーク上でデータを送信する際に,データを暗号化せずに送信したのでは, 中継するコンピュータによって通信が傍受されてしまう可能性があります. 公開鍵暗号通信は上記のような通信の問題を解決する暗号化による通信方式の一つです.

Alice が Bob にデータを送ることを考えます.

  1. Bob が Alice に暗号鍵を送る.Alice が送信するデータを暗号化する.
  2. Alcie が Bob に暗号化したデータを送る.
  3. Bob が複合鍵を使って Alice から送られてきたデータを復号化する.

このような通信を行います.

暗号鍵と暗号データから元データが推測できない種類の暗号を用いれば通信の秘匿性を保証できます.

RSA 暗号は 2019 年現在現役で公開鍵暗号通信に使われている暗号です.

RAS 暗号

概要

RAS 暗号は指数演算と剰余演算を暗号化と復号化に用いる暗号化方式です.

整数xを用いて暗号化後yを計算するには整数鍵(k, n)を用いて y \equiv x^{k} \mod n とします.

復号化する際には暗号鍵に対応する複合鍵(d,n)を用いて
{ y^{d} \equiv x^{k\cdot d} \mod n }

 \equiv x \mod n と計算します.

復号鍵 d の存在について

復号化する際の都合のいい(d,n)は必ず存在します.

p,qを十分大きい素数とする.n = p,qとおく.

復号化する際は x^{k\cdot d} \equiv x \mod n である.

ここでオイラーの定理を用いる.

オイラーの定理
正の整数 a,m に対して a,m が互いに素のとき,以下の式が成り立つ. a^{\phi(m)} \equiv 1 \mod m ただし,\phi(\cdot)オイラー関数とする.

この定理より以下の式が成り立つ. x^{\phi(n)} \equiv 1 \mod n また,n素数の積であるということと,フェルマーの小定理を用いることによって, 任意のxに対して上記の式が成り立つことが知られている.

これにより,ある整数uを用いて次式が成り立つ x^{u\cdot \phi(n)+1} \equiv x \mod n

復号化する際の式と比較すると,dについて.次式を満たせば所望のdとして十分である. kd = u\phi(n)+1 ここでv = -uとおくと次のように書き直せる. kd + v\phi(n)=1[tex:

ここでkは,鍵生成の際に自由に生成できる数であるから自由に制約をもたせることができる. k\phi(n)=(p-1)(q-1)と互いに素な数として生成することにする. 具体的にはk素数とする.

すると拡張ユークリッドの互除法により,次式を満たす整数k,vが存在する. これらが不定一次方程式の解であることを考えるとk,vは正の整数としても良い.

以上より, n = pq, k は素数とすることにより,任意の暗号文xについて復号鍵鍵dが必ず存在することが示されました.

復号鍵を求めるには一次不定方程式を解けばいいいわけですが,これには拡張ユークリッド互除法のアルゴリズムを用います. これは長くなるのでまたどこかで.

この暗号の安全性について

なんとなくメインの部分です.

三者視点から見て,暗号を解読するには \alpha x^{k} \equiv x \mod n となる\alphaを求めれば良いです.

復号鍵という視点から暗号を解くことを考えると \alpha = x^{d}という形をしていることが推測できます. dを求める際には生成した方法を考えて以下の一次不定位方程式を解けば良いです.

kd + v\phi(n)=1

しかし,第三者視点では鍵を生成する際とは異なりn=pqとしたp,qを知らないので\phi(n)は 容易に求まりません. \phi(n)を求めるには実際にnと互いに素な数を数えていくか,因数分解をするしかないですが, ここでp,qを十分に大きい値とすることでnは大きくなる. その場合,どちらの方法とも時間がかかる処理なので,現実的な時間で\phi(n)を求めることができません. ひいては復号鍵dを現実的な時間で求めることができないことを意味します.

以上が RAS 暗号の安全性です.なんとなく因数分解の困難さが暗号の難しさに貢献していることがわかりました.

明日のアドベントカレンダーも僕です...