2019-12-02

RSA 暗号を Python で書く

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

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

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

概要

十分に大きい素数 $p, q$ より,共通鍵 $n=p\cdot q$ を求める.

$\phi(n) = (p-1)(q-1)$ を求める.

$\phi(n)$ と互いに素な数として素数 $k$ を求める.

拡張ユークリッドの互除法を用いて,一次不定方程式 k $d + 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)

改善点

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

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

あまり早くない,公開鍵用の素数生成.

$\phi(n)$ と互いに素な数として素数 $k$ を求める.

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

結び

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

ということで RSA の Python での実装でした.

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

2019-12-01

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

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

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

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

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

公開鍵暗号通信

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

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

Bob が Alice に暗号鍵を送る.Alice が送信するデータを暗号化する.
Alcie が Bob に暗号化したデータを送る.
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 暗号の安全性です.なんとなく因数分解の困難さが暗号の難しさに貢献していることがわかりました.

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

2018-12-23

MoSyaMoSyaを公開します！

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

やったぜ!

長いことかかりました。なんとなくWebアプリをつくってみようと思ってから何ヶ月か。だらだらしてたのもあるんですが。

なんとなく形にできたのが嬉しいです。

作ったのはこれ

Home -MoSyaMoSya

絵の模写をするときにグリットだしたり白黒にしたりします。

Python Flask Pure.cssなんかを使いました。

やってないぜ！

SPAっぽくしようと思ってJavaScriptに手を出していました。ホントはこっちを完成させて公開したかったんですけど。。今の今まで不具合が治らなくて。。。見送りです。ほんとつらい。というか日本語にしてないのも。。

バージョンアップは近日公開します!

オオハタの研究ノート

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

RSA 暗号を Python で書く

RSA 暗号を Python で書く

概要

コード

改善点

結び

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

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

公開鍵暗号通信

RAS 暗号

概要

復号鍵 d の存在について

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

MoSyaMoSyaを公開します！

やったぜ!

やってないぜ！