Published Date : 2021年9月17日9:08

025 Pythonでビットコインを学ぶ (RSA-OAEP 5 yield)
025 Use python to learn bitcoin (RSA-OAEP 5 yield)


This blog has an English translation


ニコニコ動画にアップした動画のまとめ記事です。

This is a summary blog post about a video I uploaded to NicoNico.

細かい部分は動画を参考にしてください。

Please refer to the video for details.


目次

Table of Contents




① 動画の説明
① Video Description



00:01 - 前回の続きです。

00:01 - Continued from last time.

00:03 - 前回の動画ではRSA-OAEPで暗号化した[C]を、同じくRSA-OAEPを使用して復号化し、[D]を導き出しました。

00:03 - In my previous video, [C] encrypted with RSA-OAEP was decrypted with RSA-OAEP to derive [D].

00:05 - では長いメッセージの場合はどうなるのかテストしてみましょう。

00:05 - Let's test what happens with long messages.

00:11 - 例えば、249KBのバイナリデータを暗号化しようとします。

00:11 - For example, try to encrypt 249 KB of binary data.

00:18 - このように、当然メッセージの長さの上限を越えてしまっているので、例外が発生しテストは失敗します。

00:18 - Thus, the test fails with an exception because of it obviously exceeds the maximum message length.

00:21 - そこで、今回はyield文を使ってこの問題を解決していきましょう。

00:21 - So, this time, we'll use the yield statement to solve this problem.

00:23 - まずはyield文の動作の仕組みを簡単な関数で理解してみましょう。

00:23 - Let's start with a simple function to understand how the yield statement works.

00:25 - yield文は直前の処理の結果を関数の外に返すのはreturn文と一緒ですが、その直後にまたyield文がある場合、

00:25 - The yield statement is similar to the return statement in that it returns the result of the previous process out of the function,

00:27 - 関数内の処理は終わらず、また別の直前の処理の結果を関数の外へ返していきます。

00:27 - but if there is another yield statement after that, it does not end processing in the function and returns the result of the another previous process out of the function.

00:29 - ご覧の通り、yield文を使った関数はジェネレーターというオブジェクトになっています。

00:29 - As you can see, functions that use the yield statement are objects called generators.

00:33 - ジェネレーターはリスト関数やループ等を使用することによって関数の結果が得られます。

00:33 - Generators use list functions, loops, and so on, to obtain the results of a function.

00:52 - ご覧の通り、一度結果を取り出したジェネレーターオブジェクトは再度使用すると、空のリストになります。

00:52 - As you can see, once the generator object is retrieved, it becomes an empty list when used again.

00:55 - 結果を再利用する場合は、再度ジェネレーターオブジェクトを作成するか、結果を変数へ格納しましょう。

00:55 - If you want to reuse the results, create the generator object again or store the results in a variable.

01:00 - 同じような処理内容を持つ関数をreturn文を使って実験してみましょう。

01:00 - Let's experiment with a similar function using the return statement.

01:09 - ご覧の通り、先ほどの説明通り、return文は直前の処理の結果のみを関数を外へ返す為、返される結果は一つになります。

01:09 - As you can see, the return statement returns only the result of the previous process, so only one result is returned.

01:11 - 今度は関数内でfor-loopを使用し、その中でyield文を使って試してみましょう。

01:11 - Now try using for-loop in your function and the yield statement in it.

01:54 - ご覧の通り、この方法は長いメッセージを使用したrsa-oaepに応用できそうな気がします。

01:54 - As you can see, this method seems to be applicable to rsa-oaep with long messages.

01:57 - ジェネレーターに似たような機能で、range関数がありますが、range関数はジェネレーターではありません。

01:57 - Similar to generators, the range function exists, but the range function is not a generator.

02:18 - 例えば、yield文を使わなくても、別の処理の関数を用意して、それをForLoop等と併用して長いメッセージの処理を行うこともできます。

02:18 - For example, without using the yield statement, you could have a function for another process and use it in conjunction with ForLoop, etc. to handle long messages.

02:30 - ただ今回はこの方法を採用しないのは、yield文を使うメリットととして、メモリの節約があるからです。

02:30 - The reason I don't use this method this time, however, is that the benefit of using the yield statement is memory savings.

02:32 - そのことをwindowsのwslを使って確認してみましょう。

02:32 - Let's confirm that by using wsl of windows.

02:34 - wslを使う理由はwindowsだと、pythonのresourceモジュール(メモリの使用状況を確認するためのモジュール)が使えないからです。

02:34 - The reason for using wsl is that the python resource module (a module for checking memory usage) is not available in windows.

02:35 - なので、resourceモジュールを使用してメモリの使用状況を確認するためには、ubuntu等のlinuxシステムを使用するか、ubuntu等が使用できるwslを使用しましょう。

02:35 - So, to use the resource module to check memory usage, use a linux system, such as ubuntu, or use wsl, which can use ubuntu.

02:37 - ただし、pythonでは別のメモリ監視のモジュールがありますが、自分が使用した限りだと、resourceモジュールが使いやすかったです。

02:37 - However, python has a another memory monitoring module, but as far as I could use it, the resource module was easier to use.

02:39 - まずは長いメッセージが格納されたファイルを作成しておきます。

02:39 - First, create a file containing long messages.

02:54 - このファイルはおよそ24MBの容量があります。

02:54 - This file has approximately 24 MB of space.

03:13 - ではメモリの使用量がyield文を使うのとそうでない時と、どのように変わるのかを二つの関数を作成して試してみましょう。

03:13 - Now let's try creating two functions to see how memory usage changes when you use with and without the yield statement.

03:58 - では大きな容量のファイルを読み込み、そのデータにある処理を行う二つの関数を使ってメモリ使用量の変化を確認してみましょう。

03:58 - Now let's read a large file and see how the memory usage changes using two functions that do the work on that data.

04:15 - ご覧の通り、通常の関数と、yield文を使用した関数とでは、メモリの使用量に差が見られます。

04:15 - As you can see, there is a difference in memory usage between normal functions and functions that use the yield statement.

04:17 - つまり、yield文を使用したほうがメモリの節約になっていることが分かります。

04:17 - In other words, the yield statement saves more memory.

04:19 - 以上の結果を踏まえて、新しいRSA-OAEPの暗号化メソッドを作成してみましょう。

04:19 - With these results in mind, let's create a new version RSA-OAEP encryption method.

04:30 - 変更した箇所は、長いメッセージに対応するため、メッセージの長さの上限でメッセージを分割するだけです。

04:30 - The changes only split the message at the maximum message length to accommodate longer messages.

04:42 - では、普通のサイズのメッセージと長いサイズのメッセージを使って上手く動作するかどうかをテストしてみましょう。

04:42 - Now let's test if it works with regular and long messages.

06:11 - これで長いメッセージに対応したRSA-OAEPの暗号化メソッドが作成できたので、復号化メソッドも同様にyield文を使って作成しておきましょう。

06:11 - Now that you have an RSA-OAEP encryption method for long messages, so let's create a decryption method using the yield statement as well.

06:25 - 今回は工夫を凝らして、ランダムな日本語のひらがなとカタカナの長いメッセージを作成してみましょう。

06:25 - This time, let's try to create a long message with random Japanese hiragana and katakana.

08:16 - では全体のスクリプトをおさらいしましょう。

08:16 - Now, let's review the entire script.

import math
import os
import hashlib
import secrets
import sympy
import random


def ex_euclid(a, b):
    if a < b:
        b, a = a, b

    x0, x1 = 0, 1
    y0, y1 = 1, 0

    while b != 0:
        r = a % b
        q = a // b
        a, b = b, r
        x0, x1 = x1, (x0 - q * x1)
        y0, y1 = y1, (y0 - q * y1)
    return a, x0, y0


def inverse_mod(e, phiN):
    _, candidate_d, _ = ex_euclid(e, phiN)
    return candidate_d % phiN


def rsa_generate_keys():
    bit_length = 1024
    n = 0
    while n.bit_length() != 2048:
        p = secrets.randbits(bit_length)
        p |= (1 << bit_length - 1) | 1
        while not sympy.isprime(p):
            p = secrets.randbits(bit_length)
            p |= (1 << bit_length - 1) | 1

        assert sympy.isprime(p)
        assert len(bin(p)[2:]) >= bit_length

        q = secrets.randbits(bit_length)
        q |= (1 << bit_length - 1) | 1
        while not sympy.isprime(q):
            q = secrets.randbits(bit_length)
            q |= (1 << bit_length - 1) | 1

        assert sympy.isprime(q)
        assert len(bin(q)[2:]) >= bit_length

        n = p * q

    assert n.bit_length() == 2048

    phiN = (p - 1) * (q - 1)

    r_bits = random.choice([2**i for i in range(17, 33)])

    candidate_e = 0
    while math.gcd(candidate_e, phiN) != 1:
        candidate_e = random.randrange(r_bits, phiN)

    e = candidate_e

    assert math.gcd(e, phiN) == 1

    d = inverse_mod(e, phiN)

    public_key = (e, n)
    secret_key = (d, n)

    return public_key, secret_key


def i2osp(int_obj, byte_length):
    return int_obj.to_bytes(byte_length, 'big')


def os2ip(byte_string):
    return int.from_bytes(byte_string, 'big')


def xor(data, mask):
    assert len(data) == len(mask)
    masked = b''
    for idx, e_bytes in enumerate(data):
        masked += i2osp(e_bytes ^ mask[idx], 1)
    return masked


def MGF1(data, length_mask):
    mask = b''
    length_hash = 32
    for count in range(0, math.ceil(length_mask / length_hash)):
        byte_count = i2osp(count, 4)
        mask += hashlib.sha256(data + byte_count).digest()
    return mask[:length_mask]



~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~




public_key, private_key = rsa_generate_keys()
C_generator_object = rsa_oaep_encrypto(public_key, long_random_message)
list_of_C = [C for C in C_generator_object]
D_generator_object = rsa_oaep_decrypto_v2(private_key, list_of_C)
list_of_D = [D for D in D_generator_object]
assert b''.join(list_of_D).decode('utf-8') == long_random_message

08:58 - 今回はこれで終わりですが、各自で色々と工夫して、よりよいスクリプトを作成してみてください。

08:58 - That's all for now, but in order to make a better script, try different things out for yourself and fix them yourself.



以上です。お疲れ様です。

That's all. Thank you for your hard work.