Published Date : 2021年9月14日9:05

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


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.

前回の動画ではRSA-OAEPで暗号化した[C]を導き出しました。

In the previous video, we derived [C] encrypted with RSA-OAEP.

今回はその[C]をRSA-OAEPで復号化してく作業をします。

This time, we will decrypt [C] with RSA-OAEP.

その前に、前回の作業内容を動画を見て復習してみましょう。

Before you do that, let's review what we did last time by watching a video.

ではRSA-OAEPの復号化の作業に入ります。

Now let's start decrypting RSA-OAEP.

最初にラベルハッシュを作成します。これは暗号化の際に使用したハッシュ値と同じでなければなりません。

First, create a label hash. This must be the same hash value used for encryption.

_lHash = hashlib.sha256(b'').digest()
print(len(_lHash))
_length_hash = len(_lHash)
print(_length_hash)

準備ができたら、まずは通常通りRSAの復号化メソッドを使って[C]を復号化し、[D]を導き出します。

When you are ready, the first step is to decrypt [C] using RSA's decryption method to derive [D] as usual.

print(len(C))
print(k)
assert len(C) == k
_c = os2ip(C)
print(_c)
_m = rsa_decrypto(private_key, _c)
print(_m)
_EM = i2osp(_m, k)
print(_EM)
print(_EM[:1])
print(_EM[1:1 + _length_hash])
print(_EM[1 + _length_hash:])

今回その[D]は、OAEPによって作成された[EM]になります。

This time, [D] is the EM created using OAEP.

そして、EMを先頭の1バイトのバイト列の[00]と、maskedSeed、maskedDBの三つに分けます。

Then, EM is divided into three parts, the first 1 byte [00] of EM, maskedSeed, and maskedDB.

バイト列の[00]はEMの先頭の1バイトなので、リストのスライス機能を使って[ : 1 ]とします。

Since [00] in the byte string is the first byte of the EM, when using the list slicing feature the notation is [ : 1 ].

次にmaskedSeedの長さはlength_hashと同じ、つまり32バイトなので、リストのスライス機能を使って[ 1 : 1 + length_hash ]とします。

Then, because maskedSeed is the same length as length_hash, or 32 bytes, when using the list slicing feature the notation is [ 1 : 1 + length_hash ].

そうすると、最後のmaskedDBはリストのスライス機能を使って[ 1 + length_hash : ]となります。

The last maskedDB is then [ 1 + length_hash : ] using the list slicing feature.

上記のリストスライスを組み合わせて、EMを先頭の1バイトのバイト列の[00]と、maskedSeed、maskedDBの三つに分けます。

Combine the list slices above to divide EM into three parts, the first byte [00] of EM, maskedSeed, and maskedDB.

最初のバイト列の[00]はEMが正しくOAEPによって作られたことの確認の為のものなので、使用されません。

The [00] in the first byte string is used to confirm that EM was created correctly by OAEP, so it is not used.

pythonでは使われない変数は分かりやすくするために[ _ ]を使用することになっています。

Variables not used in python are supposed to use [ _ ] for clarity.

_, _maskedSeed, _maskedDB = _EM[:1], _EM[1:1 + _length_hash], _EM[1 + _length_hash:]
print(_maskedSeed)
print(_maskedDB)

MGF(マスク生成関数)を使ってseedMaskを作成し、そのseedMaskとmaskedSeedのXORでseedを復元します。

Use MGF (mask generation function) to create a seedMask, and XOR its seedMask and maskedSeed to restore the seed.

復元したseedと元のseedが一致しているかどうかを確かめてみましょう。

Let's see if the restored seed matches the original seed.

_seedMask = MGF1(_maskedDB, _length_hash)
print(_seedMask)
_seed = xor(_maskedSeed, _seedMask)
print(_seed)

次に、復元したseedとDBの長さをMGF(マスク生成関数)に引数としてして渡し、maskDBを作成します。

You then create maskDB by passing the restored seed and DB length as arguments to the MGF (mask generation function).

そして、そのmaskDBとmaskedDBのXORでDBを復元します。

You then restore the DB with the XOR of maskDB and maskedDB.

_dbMask = MGF1(_seed, k - _length_hash - 1)
print(_dbMask)
_DB = xor(_maskedDB, _dbMask)
print(_DB)

復元したDBを、lHash, PS, [01], Mに分けて、Mの値を取り出します。

Divide the restored DB into lHash, PS, [01], M and retrieve the M value.

lHashの長さはlength_hashと同じなので、32バイトです。

Because lHash is the same length as length_hash, it is 32 bytes.

なので、今までと同じようにリストのスライスを使い、DB[ : length_hash ]のように取り出します。

So, as before, use slices from the list and retrieve it as DB[ : length_hash ].

復元されたlHashと元のlHashの値が同じかどうかを確かめます。

Verify that the values of the restored lHash and the original lHash are the same.

_lHash = _DB[:_length_hash]
print(_lHash)
print(lHash)
assert lHash == _lHash

では、DBの残りのPS, [01]を取り除き、Mの値を取り出す作業を行いましょう。

Now remove the rest of PS and [01] from the DB and retrieve the M value.

その方法は簡単で、ループを使い、残りのDBの要素を一つずつ参照し、PSがあるなら0なので、

The method is simple: use a loop, refer to the remaining DB elements one by one, and terminate the loop

0ならインデックスをインクリメントし、最終的[01]が区切り文字なので、要素が1ならインデックスをインクリメントして、ループを終了させます。

by incrementing the index if it is 0, because PS is present, and incrementing the index if it is 1, because the final [01] is the delimiter.

idx = _length_hash
print(_DB[3])
_DB[3] == 0
_DB[3] == 1
print(_DB[60])
_DB[60] == 0
_DB[60] == 1
print(_DB[137])
_DB[137] == 0
_DB[137] == 1
print(_DB[138])
_DB[138] == 0
_DB[138] == 1
print(_DB[-1])
_DB[-1] == 0
_DB[-1] == 1
while idx < len(_DB):
    if _DB[idx] == 0:
        idx += 1
        continue
    elif _DB[idx] == 1:
        idx += 1
        break
    else:
        raise Exception()
print(idx)
print(_DB[idx:])

では取り出したMの値が元のMの値と等しいかどうかを確かめてみましょう。

Let's see if the retrieved M value is equal to the original M value.

_M = _DB[idx:]
print(_M)
print(M)
assert M == _M
print(_M.decode('utf-8'))
print(M.decode('utf-8'))
assert _M.decode('utf-8') == M.decode('utf-8')

では今まで説明したrsa-oaepの暗号化と復号化の手順を、それぞれ関数としてまとめて作成しましょう。

Let's create functions these are summarized the rsa-oaep encryption and decryption steps I have demonstrated to you so far.

ではこれまでに作成した関数を使って、rsa-oaepの暗号化と復号化のテストをしてみましょう。

Now let's test the encryption and decryption of rsa-oaep using the functions we've created.

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

Let's test what happens with long messages.



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

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