自己紹介

プログラミングの好きな大学生です。
勉強の過程で試したことや、自分なりの発見を記事にしたいと思います。
誤りや改善点などあればアドバイス下さると嬉しいです。

はじめに

Qiita はじめての投稿です。
下手な部分が多々あると思いますが、ご容赦いただけると幸いです。
また、最後にソースコードを載せております、効率の良い書き方があればアドバイスいただけると嬉しいです。

さて私は、この間購入した『暗号技術入門第3版』読んでいる途中です。
特に以前からRSAについてどんな仕組みなんだろうと気になっていたこともあり、簡単に作ってみようと思いました。実用上はC/C++でないとパフォーマンスが出ないことは簡単に予測できますが、サクッと作れるPythonを使います。ところどころに汚いコードや不揃いな命名がありますが、許してください。

注意 詳しく調べたわけでもないので、実装は適当な部分もあります。鵜呑みにしないでください。

RSAとは？

よく使われる公開鍵暗号のアルゴリズムのこと。
対称鍵（暗号化と復号化に使うカギが同じ）と違い、暗号化と復号化に使用する鍵が異なります。

下に示すのは自作したRSAの動作結果です。
秘密鍵・共通鍵 N, E, D = 16459 733 1897を生成した後
p_num = 3939 を Eで暗号化 e_num = 14764 して　Dで復号化 d_num = 3939　できました。

# 共通鍵の生成
p q 109 151
Calc N and L ...
=  16459 2700
Calc E ...
=  733
Calc D...
=  1897

N, E, D =  16459 733 1897

# 整数の暗号化
p_num     3939
e_num     14764
d_num     3939

アルゴリズム

RSAのアルゴリズムは非常にシンプルで驚きました。
鍵生成の方法は後回しにし、まずは暗号化・複合化を説明します。

変数名	意味
message	平文
encrypted	暗号文
decrypted	復号文
N	2つの素数の積
E ※	公開鍵（暗号化鍵)
D ※	秘密鍵（復号化鍵)

※ (E, N) のペアを公開鍵、(D, N) のペアを秘密鍵と呼びますが、説明のためEとDそれぞれに名前を付けます

暗号化

encrypted = (message ** E) % N

復号化

decrypted = (encrypted ** D) % N

DESやAESといった対称鍵アルゴリズムはビット列をこねくり回したりXORを取ったりと複雑なのですが（1行の数式じゃ無理）
こちらは数式で表せます。シンプルな分、脅威になりうる問題が分かりやすいため、安全性の証明ができるのだと思います。
さて、これをみて どうやって攻撃すればいいんだ？ と疑問に持つ方は多いと思います。（私もそうでした）

結論を言うと、Nを素因数分解できれば D が求められます。
鍵生成の手順の説明後に説明したいと思います。

鍵を生成する

それでは簡単に秘密鍵と公開鍵を、順を追って作ってみます。
私が実際に作ったプログラムを抜粋しながら説明したいと思います。

(1) 2つの素数を生成する

# 8bitの素数を使用する
BIT_RESOLUTION = 2 ** 8

# 100 ~ 2**8 までの素数リストを「エラトステネスのふるい」で生成する
prime_nums = seachPrimeNumpy(100, BIT_RESOLUTION)

# 素数を2つ取り出す
p, q = np.random.choice(prime_nums , 2, replace=False)

ここのBIT_RESOLUTIONの2乗が鍵の長さになるため、約16bitの鍵ができます。

(2) 2つの素数から N を計算する

N = P * q

(3) 2つの素数からLを計算する

# L = lcm(p - 1, q - 1)
L = (p - 1) * (q - 1) // math.gcd((p - 1), (q - 1))

(p - 1)と(q - 1)の最小公倍数を求めます。
これはEとDのための中間変数として使います。

(4) 暗号化鍵 E を求める

while True:
    E = np.random.randint(1, L, dtype=np.uint64)
    if math.gcd(E, L) == 1:
        break

1 < E < L の範囲から、E と L の最大公約数が 1（ E と Lが互いに素）になる値を探しています。
こんなメチャクチャな実装で大丈夫か不安でしたが、一瞬で見つかります。

(5) 復号化鍵 D を求める

while True:
    D = np.random.randint(1, L)
    if ((E * D) % L) == 1:
        break

1 < E < L の範囲から ((E * D) % L) == 1 の条件に当てはまる値を探します。
因みに一番時間がかかるのがここでした。後でここは改良しましたが、それでも 2 ~ 6秒ほどかかります。

やっと鍵のセット ( N, E, D ) がそろいました！

どうやって破るか

まず、前提として送信者と受信者、攻撃者は以下の情報を持っています。

	N	E	D
受信者	○	○	○
送信者	○	×	○
攻撃者	○	×	○

公開鍵 E は文字通り誰でも手に入るものですし、 N は暗号化に必要なものであるため攻撃者はこのペアを持っています。
また、暗号を破るということは、攻撃者が秘密鍵 D を手に入れることです。

すなわち、( N, E ) から D を求める ことが攻撃者の目的となります。
そんなことが可能か考えてみます。

まず、Dの計算手順を見直してみましょう

while True:
    D = np.random.randint(1, L)
    if ((E * D) % L) == 1:
        break

なるほど、L があれば求められそうです。
次は L の求め方を見てみましょう。

L = (p - 1) * (q - 1) // math.gcd((p - 1), (q - 1))

ふむふむ、p と q が分かれば解けそうです。

# 素数を2つ取り出す
p, q = np.random.choice(prime_nums , 2, replace=False)

p と q とは何だったか見てみると、素数であったことが分かります。

N = P * q

そして、p と q を掛けたものが N でした。

よって、結論は

N を素因数分解することで、複合鍵 D が得られる

ということです。
端的に言えば、N の素因数分解の難しさと、RSAを破る難しさは同じです。

自作したRSAで使用していた鍵を使って、
N から D が求められるのか試してみます。

N = 16459
E = 733
D = 1897

プログラム

import math
import numpy as np

def factorization(n):
    maxium = int(math.sqrt(n))
    for i in range(2, maxium):
        if n % i == 0:
            return i, (n // i)

    return None, None

if __name__ == "__main__":
    N = 16459
    E = 733

    p, q = factorization(N)
    print("p, q = ", p, q)

    L = (p - 1) * (q - 1) // math.gcd((p - 1), (q - 1))

    while True:
        D = np.random.randint(1, L)
        if ((E * D) % L) == 1:
            break

    print("D = ", D)

実行結果

p, q =  109 151
D =  1897

今回は16bitの鍵を使ったため、一瞬で求められました。
実際の鍵のビット数は 2048bit 以上を使うため上の比にならない程時間がかかります。
( というか、長すぎて宇宙が生まれ変わっても終わりません )

文字列を暗号化

1つの数字なんか暗号化してもつまんないですよね。
もちろん文字列も試しました。

プログラム

# 鍵は同じものを使う
N, E, D = 16459, 733, 1897

# 文字列の暗号化
p_text = "Hello World !!"
p_ary = [ord(i) for i in p_text]

e_ary = [encrypt(i, N, E) for i in p_ary]
e_text = "".join([chr(i) for i in e_ary])

d_ary  = [dencrypt(i, N, D) for i in e_ary]
d_text = "".join([chr(i) for i in d_ary])

print("p_text    ",p_text)
print("e_text    ",e_text)
print("d_text    ",d_text)

実行結果

p_text     Hello World !!
e_text     㭪ᮥ⁛⁛ᐔ㮳ખᐔ༷⁛㧓㮳!!
d_text     Hello World !!

いいですね。
... いや、まだまだです。

どういうことなのか。上図だと文字化けしていてわかりにくいため、文字列に直さず表示してみます。

p_text     [72,     101,  108,  108,  111,    32,   87,  111,  114,  108,   100,    32, 33, 33]
e_text     [15210, 7077, 8283, 8283, 5140, 15283, 2710, 5140, 3895, 8283, 14803, 15283, 33, 33]
d_text     [72,     101,  108,  108,  111,    32,   87,  111,  114,  108,   100,    32, 33, 33]

平文に2回含まれる " L = 108 " の暗号文に注目してください。

平文   [ ...,  108,  108, ... ]
暗号文 [ ..., 8283, 8283, ... ]

そうなんです、全く同じ値になっています！！
もちろん、" o " や " ! " も同様です。（" ! " が平文も暗号文も同じ値になっているのは偶然です）

これでは暗号の解読が出来ずとも、「なるほど... ココとココは同じ文字なんだな」という情報が伝わってしまいます。
さらに、文字を「入れ替える」という改竄が可能であったり、長文になるとアルファベットの登場する頻度から
完全に解読されてしまう恐れがあります。

これを解決するためには、暗号化の方法を改良する必要があります。

文字列を暗号化（改良版）

上で説明した暗号では、例え優秀な暗号アルゴリズムを使っていたとしても解読が容易になってしまいます。
そこで、暗号化を改良したいと思います。

先ず、改良前の暗号化方法を下に示します。なお、暗号化関数を単純に f(x) と書きます。
なお、使用する値は適当なものです。
※ f(x) = encrypt(message, N, E)

各値に対してそれぞれ暗号化を施しています。

暗号化の前に、1つ前の暗号文とXORを取ります。1番初めの値の前の暗号文はありませんから
初期ベクタ（ init ）というランダムな値を使います。

初めは 6 -> 4 でしたが、全てごちゃごちゃな暗号文になりました。
この改良を実装して動かしてみます。

# 文字列で表示
p_text     Hello World !!
e_text     ῳˆ㎞ᲇ᝖ჶаჍ௯ẁᓫ⠪ᅏ㤋ᚌ
d_text     Hello World !!

# リストで表示
p_text        　　[72,   101,  108,   108,   111,    32,    87,  111,  114,   108,  100,    32,   33,    33]
e_text  [10781,  4842, 15324, 5898, 13872,   403, 11226, 13661, 4684, 9720, 16236, 6284, 12466, 2746, 11393]
d_text        　　[72,   101,  108,   108,   111,    32,    87,  111,  114,   108,  100,    32,   33,    33]

上手くいきました！
もう一度 " L = 108 " の暗号文を確認してみます。

平文    [ ...,  108,   108, ... ]
暗号文  [ ..., 5898, 13872, ... ]

グッチャグッチャです。また、他の" o " や " ! " ちゃんとできてます。

ちなみに、初めのように各ブロック（リストの各値）を別々に暗号化する方法を ECB モードと呼び、
改良版のような方法を CBC モードと呼ぶようです。

おわりに

ずっと作ってみたかった RSA 公開鍵暗号を Python で動かせました。
パフォーマンスは、32bitの鍵を2~5秒で生成できたので一応満足です。

次は実際に使われているOpenSSLを詳しく調べてみたいです。
→ https://qiita.com/rby39/items/d3d7d39a95e4bb02044f

参考文献

『暗号技術入門第3版秘密の国のアリス』

ソースコード

import numpy as np
import math
import time
import random

BIT_RESOLUTION = 2**8

def calc_time(func):
    def wrapper(*args, **kargs):
        st = time.perf_counter()
        result = func(*args, **kargs)
        st = time.perf_counter() - st
        print("\n[ TIME ] %f s" % st)
        return result
    return wrapper

def seachPrimeNumpy(begign, N):
    # seachListには sqrt(N) で割り切れる値が N しかありえない
    # つまりこれ以上の値を調べる意味がない
    maxium = int(np.sqrt(N))

    # 2 ~ Nまでのリストを生成
    seachList = np.arange(3, N+1, 2, dtype=np.uint64)
    seachList = np.append(np.array([2], dtype=np.uint64), seachList)

    primeNum = np.array([], dtype=np.uint64)
    while seachList[0] <= maxium:
        # seachListで一番小さい値は確実に素数になっている
        primeNum = np.append(primeNum, seachList[0])
        tmp = seachList[0]

        # 一番小さい素数で割り切れるものをsearchリストから取り除きながら
        # tempで使用した値自身も削除する
        seachList = seachList[seachList % tmp != 0]

    # 最後まで取り除かれなかったものは素数
    primeNum = np.append(primeNum, seachList)
    primeNum = primeNum[primeNum >= begign]

    return primeNum

def gen_keys(p_nums):
    p, q = np.random.choice(p_nums, 2, replace=False)
    p, q = int(p), int(q)
    print("p q", p, q)

    print("Calc N and L ...")
    N = p * q
    L = (p - 1) * (q - 1) // math.gcd((p - 1), (q - 1))
    print("= ", N, L)

    print("Calc E ...")
    while True:
        E = np.random.randint(1, L, dtype=np.uint64)
        if math.gcd(E, L) == 1:
            break
    print("= ",E)

    x = 1000 * 10**3
    if L < x:
        x = L // 10
    x_part_list = np.arange(0, L-x, x, dtype=np.uint64)
    x_part_list = np.append(x_part_list, np.array([L-x], dtype=np.uint64))
    np.random.shuffle(x_part_list)

    print("Calc D...")
    for i, begin_num in enumerate(x_part_list):
        temp = np.arange(begin_num, begin_num+x, dtype=np.uint64)
        temp = temp[(E * temp) % L == 1]
        if len(temp) > 0:
            D = np.random.choice(temp, 1)[0]
            break

    print("= ",D)

    return N, E, D

def encrypt(ptext, N, E):
    # Numpyで自作した方法よりも100倍以上高速でした。
    return pow(int(ptext), int(E), int(N))

def dencrypt(dtext, N, E):
    return encrypt(dtext, N, E)

def encrypt_array(parray, N, E):
    init = random.randint(1, N)

    etext = encrypt(parray[0] ^ init, N, E)
    earray = [init, etext]
    for ptext in parray[1:]:
        etext = encrypt(ptext ^ etext, N, E)
        earray.append(etext)

    return earray

def dencrypt_array(earray, N, D):
    earray = [i for i in reversed(earray)]

    parray = []
    for etext, xor in zip(earray[:-1], earray[1:]):
        ptext = encrypt(etext, N, D) ^ xor
        parray.append(ptext)

    return [i for i in reversed(parray)]

@calc_time
def main():
    BIT_RESOLUTION = 2 ** 8

    prime_num = seachPrimeNumpy(100, BIT_RESOLUTION)

    # 鍵の生成
    print("# 共通鍵の生成")
    N, E, D = gen_keys(prime_num)
    print()
    print("N, E, D = ", N, E, D)

    # 数字の暗号化
    p_num    = 3939

    e_num = encrypt(p_num, N, E)
    d_num = dencrypt(e_num,    N, D)

    print()
    print("# 整数の暗号化")
    print("p_num    ", p_num)
    print("e_num    ", e_num)
    print("d_num    ", d_num)


    # 文字列の暗号化
    p_text = "Hello World !!"
    p_ary = [ord(i) for i in p_text]

    # e_ary = [encrypt(i, N, E) for i in p_ary]  # ECB
    e_ary = encrypt_array(p_ary, N, E) # CBC
    e_text = "".join([chr(i) for i in e_ary])

    # d_ary  = [dencrypt(i, N, D) for i in e_ary] # ECB
    d_ary = dencrypt_array(e_ary, N, D) # CBC
    d_text = "".join([chr(i) for i in d_ary])

    print()
    print("# 文字列の暗号化")
    print("p_text    ",p_text)
    print("e_text    ",e_text)
    print("d_text    ",d_text)

if __name__ == "__main__":
    main()

RSAをPythonで作ってみた

自己紹介

はじめに

RSAとは？

アルゴリズム

鍵を生成する

(1) 2つの素数を生成する

(2) 2つの素数から N を計算する

(3) 2つの素数からLを計算する

(4) 暗号化鍵 E を求める

(5) 復号化鍵 D を求める

どうやって破るか

プログラム

実行結果

文字列を暗号化

プログラム

実行結果

文字列を暗号化（改良版）

おわりに

参考文献

ソースコード