Published Date : 2021年9月5日3:09

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


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(最適非対称暗号化パディング)を使ったRSA-OAEPを実装していきましょう。

Now let's implement RSA-OAEP using OAEP (Optimal Asymmetric Encryption Padding) in a textbook RSA.

まず図を使ったアニメーションで簡単にOAEPの仕組みの全体像を理解しておきましょう。

Let's start with a graphic animation to get a quick overview of how OAEP works.

そしてその後、Pythonを使ってこれらの手順のスクリプトを書きながら細かく理解しましょう。

Then, you'll learn more about these steps by scripting them with Python.

簡単に説明すると、seedと呼ばれるランダムなバイト文字列を作成して、

Briefly, we create a random byte string called seed

メッセージと1バイトの[01]のバイト文字列と、[00]のバイト文字列でのパディング領域と、

to create a data block consisting of a message, a one-byte [01] byte string,

ハッシュ値で構成されるデータブロックを作成します。

multiple padding areas consisting of byte string [00], and a hash value.

これらの全体の長さはkとなり、このkはRSAの法であるnと同じ長さです。

Their total length is k, which is the same length as the RSA modulus of n.

つまり、全体の長さはk = nで、その内訳は最後の処理でEMの先頭に付け足す1バイトの[00]のバイト文字列とハッシュ値の長さ(hLen)を持つseedと、それらの値をkから引いた(k - hLen - 1)の長さを持つDBとなります。

That is, the total length is k = n, it consists of a byte string of [00], which is a byte to be added to the beginning of EM in the last process, and a seed with the length of the hash value (hLen), and DB of length k minus those values (k - hLen - 1).

そしてそれらにMGF(マスク生成関数)とxor演算を適用してmaskedSeedとmaskedDBを作成します。

We then apply MGF (mask generation function) and xor operations to them to create maskedSeed and maskedDB.

最後にそれらの先頭に1バイトの[00]のバイト文字列を加えて、EM(Encoded Message)を作成します。

Finally, add a byte string of [00] of 1 byte to the beginning of them to create EM (Encoded Message).

そして、そのEMを通常通りRSA暗号化してC(Cypher text)を作成します。

Then, the EM is RSA encrypted as usual to create a C (Cypher text).

復号化する際はRSAの復号化メソッドを使ってD(Decoded text)を得て、復号化されたEMからDBに復元し、メッセージを取得します。

When decrypting, use the RSA decryption method to get the D (Decoded text), restore the decrypted EM to DB, and get the messages.

EMからDBを復元するには、EMのmaskedDBとmaskedSeedを使ってseedを復元して、そのseedとmaskedDBを使ってDBを復元します。

To restore DB from EM, restore the seed using EM's maskedDB and maskedSeed, and then restore DB using the seed and maskedDB.

OAEPに関してはこちらのサイト(https://datatracker.ietf.org/doc/html/rfc3447)が大変参考になりましたので、

As for OAEP, this site (https://datatracker.ietf.org/doc/html/rfc3447) was very helpful,

より詳しい内容は各自でこちらのサイト(https://datatracker.ietf.org/doc/html/rfc3447)を参考にしてください。

so please refer to this site (https://datatracker.ietf.org/doc/html/rfc3447) for more details.

OAEPをするメリットは、このような方法でメッセージをOAEPを行ってからRSA暗号で暗号化することによって暗号が強化されます。

The advantage of OAEP is that encryption is enhanced by encrypting it with RSA encryption after using OAEP to the message in this way.

なぜならseedはパディングする度に毎回ランダムなバイト列になり、

Because seed is a random byte sequence for each padding,

それにより通信される暗号されたバイト列は通信毎にランダム化され、同じメッセージが複数回暗号化されても、

The encrypted bytes that are transmitted are then randomized for each transmission, so that even if

毎回異なるメッセージに見えるようになるからです。

the same message is encrypted multiple times, they appear to be different messages each time.

また、異なるRSAキーを使用して同じメッセージを暗号化してメッセージを漏洩したり、

You can also avoid other weaknesses, such as using different RSA keys to encrypt the same message and leak it,

攻撃者が他の暗号文から派生したメッセージを作成したりするなど、その他の弱点も回避できるからです。

or allowing an attacker to create messages derived from other ciphertexts.

それでは、まずはMGFやxorを図やPythonを用いて理解していきましょう。

Let's start by understanding MGF and xor with diagrams and Python.

xor演算の復習から始めましょう。詳しくはこの動画シリーズの[003 Pythonで遊ぶ (ビットの論理演算)]を参考にしてください。

Let's start with a review of xor operations. For more information, see [003 Playing with Python (logical operations on bits)] in this video series.

簡単にいうと、XOR演算は比べるビット同士のうち、どちらかが1の場合のみ1になります。

Briefly, XOR operation is 1 if and only if its bits differ (one is 1, the other is 0).

ではビット列同士のXOR演算を行い、なぜこの演算方法がOAEPで使われるのかを確かめてみましょう。

Now let's perform an XOR operation between two bit sequences to see why this method is used in OAEP.

このように、例えばAとBのビット列同士のXOR演算を行って得たCというビット列があった場合、このCというビット列にBのビット列のXOR演算を行うと、Aのビット列が得られます。

Thus, for example, if there is a bit string C obtained by performing an XOR operation between bit strings A and B, the bit string A is obtained by performing an XOR operation on the bit string C and the bit string B.

ではPythonスクリプトを書いてそのことを確認してみましょう。

Let's write a Python script to see what happens.

この動画シリーズの[003 Pythonで遊ぶ (ビットの論理演算)]で使用したPythonスクリプトで試しましょう。

Try the Python script you used in [003 Playing with Python (logical operations on bits)] of this video series.

まずはOR演算とXOR演算の違いです。

First, the difference between OR operation and XOR operation.

pairs_bits = [(0,0),(0,1),(1,0),(1,1)]
print('OR (|) operation')
for b1, b2 in pairs_bits:
    print(f"{b1} | {b2} = {b1 | b2}")
print('XOR (^) operation')
for b1, b2 in pairs_bits:
    print(f"{b1} ^ {b2} = {b1 ^ b2}")

num_of_bits = 8
try:
    a = int(input('a: '))
    print('a:', format(a, f'0{num_of_bits}b'))
    b = int(input('b: '))
    print('b:', format(b, f'0{num_of_bits}b'))
except:
    print('Please input the numerical value!')

print('*' * 36)
print()
print('OR (|) operation')
print()
for b1, b2 in pairs_bits:
    print(f"{b1} | {b2} = {b1 | b2}")
print()
print('c = a | b')
c = 0
print('a:', format(a, f'0{num_of_bits}b'))
print('b:', format(b, f'0{num_of_bits}b'))
c = a | b
print('c:', format(c, f'0{num_of_bits}b'))
print()
print('*' * 36)

print('*' * 36)
print()
print('XOR (^) operation')
print()
for b1, b2 in pairs_bits:
    print(f"{b1} ^ {b2} = {b1 ^ b2}")
print()
print('c = a ^ b')
c = 0
print('a:', format(a, f'0{num_of_bits}b'))
print('b:', format(b, f'0{num_of_bits}b'))
c = a ^ b
print('c:', format(c, f'0{num_of_bits}b'))
print()
print('*' * 36)

そして、バイト文字列のAとBを用意します。

Then prepare byte strings A and B.

そして、AとB同士でXOR演算を行い、その結果であるCを得ます。

Then, the XOR operation is performed between A and B, and the result C is obtained.

Bを今回のMGFで作成するマスクに見立てると、CとBのXOR演算を行うことは、そのマスクを外してAのビット列を元に戻すことと同じです。

If you think of B as a mask created by MGF, XOR operation between C and B is the same as removing the mask and restoring A's bit string.

A = 0xC0
B = 0x3f
C = A ^ B

format(A, '08b')
Out[15]: '11000000'

format(B, '08b')
Out[16]: '00111111'

format(C, '08b')
Out[17]: '11111111'

format(C, '02x')
Out[18]: 'ff'

format(C ^ B, '08b')
Out[19]: '11000000'

A == C ^ B
Out[20]: True

今度は分かりやすくするため、変数名をDBとmaskとmaskedDBにして、もう一度先ほどの作業を繰り返してみましょう。

Now, for clarity, let's repeat the previous step with the variable names DB, mask, and maskedDB.

In [1]: DB = 0xcf03

In [2]: mask = 0xabcf

In [3]: maskedDB = DB ^ mask

In [4]: format(DB, '016b')
Out[4]: '1100111100000011'

In [5]: format(mask, '016b')
Out[5]: '1010101111001111'

In [6]: format(maskedDB, '016b')
Out[6]: '0110010011001100'

In [7]: format(maskedDB ^ mask, '016b')
Out[7]: '1100111100000011'

In [8]: DB == maskedDB ^ mask
Out[8]: True

このように、XOR演算を使ってマスクを行います。さらにマスクを外す時もXOR演算を行えばマスクされたバイト文字列をもとに戻すことができます。

In this way, the XOR operation is used to perform the mask. In addition, the masked byte string can be unmasked by performing an XOR operation.

次に、seed(r)と呼ばれるランダムなビット列とMGF(マスク生成関数)の仕組みについての簡単な説明を図を使って行います。

Next, I'll use a diagram to briefly explain random bits called seed (r) and and how work MGF (mask generation function).



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

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