RSA 暗号を Python で書く

RSA 暗号を Python で書く

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

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

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

概要

1. 十分に大きい素数より,共通鍵を求める.
2. を求める.
3. と互いに素な数として素数を求める.
4. 拡張ユークリッドの互除法を用いて,一次不定方程式 kを解き,秘密鍵$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. と互いに素な数として素数を求める.

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

結び

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

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

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