Published Date : 2021年9月11日3:21

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


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



前回の続きです。

Continued from last time.

それでは、Pythonを使って手順毎にスクリプトを書いて理解していきましょう。

Now you'll learn how to script each step using Python.

その前に前回の動画で作成した、pとq、nとphiN、そしてeとdを作成する関数を用意しておきましょう。

Before you do that, you'll need the functions you created in my previous video to create p and q, n and phiN, and e and d.

それから、暗号化と復号化のメソッドも作成しましょう。

You'll also create encryption and decryption methods.

そして、前回作成したi2osp関数、xor関数、MGF関数を用意しましょう。

Then, prepare the i2osp, xor, and MGF functions you created last time.

準備ができたら、公開鍵と秘密鍵を作成しておきましょう。

When you are ready, create the public and private keys.

public_key, private_key = rsa_generate_keys()
e, n = public_key
d, _ = private_key

では、seed(r)とDB(データブロック)を作成しましょう。

Let's create a seed (r) and a DB (data block).

最初に、バイト文字列のM(メッセージ)を作成しましょう。

First, create an M (Message) of the byte string.

M = "RSA暗号をOAEPのパディング方式で暗号化、復号化する方法です。".encode('utf-8')

そして、RSAの法であるnから、kの値を求めます。

It then computes the value of k from the RSA modulus of n.

このkは最終的に作成されるEMの値のバイト文字列の長さに相当します。

This k corresponds to the length of the byte string of the resulting EM value.

k = n.bit_length() // 8

M(メッセージ)の長さを変数に代入しましょう。

Let's assign the length of M (message) to a variable.

length_message = len(M)

seedの値とDBの先頭に用意するハッシュ値の長さは、sha256なら32バイトに設定します。

Set the length of the seed value and the hash value at the beginning of the DB to 32 bytes for sha256.

length_hash = 32

メッセージの長さが(k - (length_hash * 2) - 2)より大きいなら例外を発生させます。

Raises an exception if the message length is greater than (k - (length_hash * 2) - 2).

assert length_message <= (k - (length_hash * 2) - 2)

(k - length_hash - 1)はDBの長さです。

(k - length_hash - 1) is the length of the DB.

そしてDBのラベルハッシュ値の長さ(length_hash)と区切りバイト文字列[01]の1バイトを合わせて(k - (length_hash * 2) - 2)となります。

Then, the length of the DB label hash value (length_hash) and one byte of the delimiter string [01] are combined to produce (k - (length_hash * 2) - 2).

次にseedまたはrと呼ばれるランダムなバイト文字列を作成します。

It then creates a random byte string called seed or r.

seed = os.urandom(length_hash)

このseedの長さは、扱うハッシュアルゴリズムがsha1なら20バイト、

The length of the seed corresponds to the length of the byte string of the hash value,

sha256なら32バイト等、ハッシュ値のバイト文字列の長さに相当します。

such as 20 bytes for sha1 and 32 bytes for sha256.

今回使うハッシュ関数はsha256にします。

The hash function used this time should be sha256.

つまりseedとDBの先頭に配置する、ラベルのハッシュ値は32バイトです。

That is, the hash value of the label placed at the beginning of DB and length of seed is 32 bytes.

次にkからEMの先頭の1バイトの[00]とseedの32バイトを引いたバイト文字列の長さのデータブロック(DB)を作成します。

It then creates a data block (DB) of the length of k minus the first 1 byte [00] of EM minus the 32 bytes of seed.

まずはDBの先頭に配置するラベルハッシュをsha256で作成します。

First, create a label hash to be placed at the beginning of DB using sha256.

特にラベルに対するオプション指定が無ければ空文字から生成されるデフォルトのハッシュ値となります。

If no option is specified for the label, the default hash value is generated from the empty character.

lHash = hashlib.sha256(b'').digest()

そして、DBの中のパディング領域であるps(padding string)を作成します。

It then creates ps (padding string), a padding area in DB.

EM全体の長さであるkからメッセージの長さとseedの長さ、ラベルハッシュの長さ、1バイトの区切りバイト文字列[01]、

Then, calculates the length of the entire EM (k) minus the length of the message and the length of the seed, the length of the label hash,

そしてEMの先頭の1バイトのバイト文字列[00]を引いたバイト長を計算し、そのバイト長の分だけのゼロのバイト列をPSに代入します。

the one-byte delimiter string [01], and the first one-byte [00] of the EM, and sets the PS to the number of zero bytes that the calculated byte length.

ps = b'\x00' * (k - length_message - (length_hash * 2) - 2)

そしてこれまで作成したlHash、ps、1バイトの区切りバイト文字列[01]、そしてMを連結させたDBを作成します。

Then, DB is created by concatenating the previously created lHash, ps, the single-byte delimiter string [01], and M.

DB = lHash + ps + b'\x01' + M

EMの先頭の1バイトのバイト文字列[00]とseedの長さ32バイトとDBの長さを足し合わせると、kになることを確認します。

Verify that the first 1 byte [00] of EM plus 32 bytes of seed length plus DB length equals k.

assert len(DB) + len(seed) + 1 == k

ではDBとseedの作成が終わりましたので、まずはseedとDBの長さを引数として、MGF(マスク生成関数)に渡してデータブロック(DB)のマスクを作成します。

Now that we have created the DB and the seed, we first create a mask for the data block (DB) by passing the length of the DB and seed value as arguments to the MGF (mask generation function).

そしてDBとdbMask同士でxor演算をして、maskedDBを作成します。

It then create maskedDB by performing an XOR operation of DB and dbMask.

次に今度は、maskedDBとseedの長さであるlength_hashを使い、MGF(マスク生成関数)でseedのマスクを作成します。

Now we use maskedDB and length_hash which is the length of seed, and create a mask of seed with MGF (mask generation function).

そしてseedとseedMask同士でxor演算をして、maskedSeedを作成します。

It then create maskedSeed by performing an XOR operation of seed and seedMask.

最後に先頭に1バイトのバイト文字列[00]とmaskedSeedとmaskedDBを連結させたEM(Encoded Message)を作成します。

Finally, create an Encoded Message (EM) that is a concatenation of the leading one-byte string [00], maskedSeed, and maskedDB.

EMとkの長さが一致するかを確かめます。

Ensure that the EM and k lengths match.

では今度はこのEMをRSA暗号化メソッドで暗号化していきます。

Now let's encrypt this EM with the RSA encryption method.

暗号化の作業の前にバイト文字列から整数型に変換する関数をこのサイト(https://datatracker.ietf.org/doc/html/rfc3447#section-4.1)に倣って、作成しましょう。

Before we do any encryption, let's create a function that converts a byte string to an integer, following the example of this site (https://datatracker.ietf.org/doc/html/rfc3447#section-4.1).

ちなみに、この[os]はオクテットストリングで、8ビット長のビット文字列、つまり1バイト長のバイト文字列を表しています。

By the way, [os] means [octet string] that represents bit string of 8-bit length or byte string of 1-byte length.

そしてipはインテジャープリミティブ、つまり使用するプログラミング言語(今回の場合pythonを使用していますが)であらかじめ用意されている最も基本的な整数型という意味です。

And [ip] stands for integer primitive, which is the most basic integer type provided by programming language (in our case python).

ではEMから整数に変換されたmの値を使って、今まで通りRSA暗号化メソッドで暗号化しましょう。

Let's continue encrypting with the RSA encryption method using the m value converted from EM to an integer.

cは整数なので、バイト文字列に変換しましょう。

Since c is an integer, convert it to a sequence of bytes.

これで、RSA-OAEPによる暗号化を概要はつかめたと思うので、次は復号化の作業です。

Now that you have an overview of RSA-OAEP encryption, the next step is decryption.

とは言っても、やることは暗号化の作業の逆を行えばいいわけです。

That said, all you have to do is reverse the encryption process.



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

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