Published Date : 2021年9月1日3:06

020 Pythonで遊ぶ (教科書的RSA 4)
020 Playing with Python (Textbook RSA 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.

では前回作成した拡張ユークリッドの互除法の関数を使ったdの値を求める関数を作成しましょう。

Now let's create a function that computes the value of d using the extended Euclidean algorithm function we created earlier.

整数値として計算したいので、剰余計算を使って正の整数を導き出します。

Because we want to calculate as an integer value, we use remainder computation to derive a positive integer.

何故剰余計算を行うかPythonを使って確かめてみましょう。

Let's see why we do modulo computations using Python.

マイナス53を160で割った余りは107になります。

The remainder of minus 53 divided by 160 is 107.

なぜそうなるかは剰余計算を時計の針としてイメージすれば解決します。

The solution is to imagine the remainder computation as a clock hand.

時計の長針も短針も12時になったら0としてカウントしてまた1から12(0)までを一周します。

The hands of the clock also count as 0 at 12 o'clock and go around 1 to 12 (0) again.

つまり何回転しても、逆向きに回転したとしても表される数は1から12(0)までです。

This means that no matter how many rotations you make, no matter how many rotations you make in the opposite direction, the number is between 1 and 12 (0).

この12の数を今回の160に置き換えたとしても原理はまったく同じです。

If we replace that 12 number with this 160, the principles are exactly the same.

つまり160から逆向きに53進むと107になります。160から逆向きに373((-160*2) + (-53))進んでも107です。

That is, if you go from 160 to 53 backwards, you get 107. even if 373 ((-160 * 2) + (-53)) backwards from 160 would still be 107.

-53 % 160
Out[33]: 107

53 % 160
Out[34]: 53

107 % 160
Out[35]: 107

-1 % 160
Out[36]: 159

-2 % 160
Out[37]: 158

-1 / 160
Out[38]: -0.00625

1 / 160
Out[39]: 0.00625

1 % 160
Out[40]: 1

-1 % 160
Out[41]: 159

161 % 160
Out[42]: 1

-161 % 160
Out[43]: 159

1/160
Out[44]: 0.00625

-1/160
Out[45]: -0.00625

-161/160
Out[46]: -1.00625

161/160
Out[47]: 1.00625

321 / 160
Out[48]: 2.00625

eの値を-53乗したらfloat値になりますが、最終的にnの値で剰余計算するので、eを107乗した値と同じになりますが、

The value of e to the minus 53 power is a float value, but it eventually does a remainder calculation with the value of n, therefore, it is the same as e raised to the power of 107,

その前の段階での(つまりeの-53乗の段階での)[AttributeError: 'float' object has no attribute 'to_bytes']を避ける為に正の整数値に直しています。

but we have changed it to a positive integer value in the previous step (i.e. e raised to the power of -53) to avoid [AttributeError: 'float' object has no attribute 'to_bytes'].

3**-53
Out[49]: 5.1590947003649566e-26

3**107
Out[50]: 1127130637840908780976740490797413723399509150616187

hex(3**-53)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-51-c54fcc63681abba> in <module>
----> 1 hex(3**-53)

TypeError: 'float' object cannot be interpreted as an integer

hex(3**107)
Out[52]: '0x30336cdd21fc65859bd9c8d0bb0268abc1144114a7b'

ではeとdとnを使ってメッセージの暗号化と復号化までを行う作業を、まずは小さい数値を使って確かめてみましょう。

Let's start using small numbers to see how to encrypt and decrypt messages using e, d, and n.

今までは[a ** b % c]といった式を使用していましたが、pythonのビルトイン関数のpow関数(pow(a, b, c))を使用すればより高速に計算できます。

Formerly you would use an expression such as [a ** b % c], but you can use the python built-in function pow (pow(a, b, c)) to do the calculation faster.

pow(3, 6, 999)
Out[53]: 729

3**6 % 999
Out[54]: 729

pow(3, 6, 999) == 3**6 % 999
Out[55]: True

今まで作成した関数を使って、公開鍵と秘密鍵を作成して、メッセージの暗号化と復号化をしてみましょう。

Let's use the functions we've created to create a public key and a private key to encrypt and decrypt the message.

では次に色々なタイプの入力データ(例えば文字列やバイトオブジェクト等)に対応できるような暗号化の関数を作成してみましょう。

Now let's create an encryption function that can handle different types of input data (For example, strings, byte objects, etc.).

では次に画像ファイルデータを暗号化して復号化してみましょう。

Now, let's encrypt and decrypt the image file data.

大きなファイルデータは決められたバイト数毎に複数のデータの塊に分けます。

Large file data is divided into chunks of data at a fixed number of bytes.

しかし、この方法では復号化に失敗しています。

However, this method fails to decrypt.

失敗した原因を探ってみましょう。

Let's find out why it failed.

復号化されたデータと元のデータの最後尾を見比べてみましょう。

Let's compare the end of the decoded data with the end of the original data.

どうやら、暗号化の際にデータの最後尾に不要なゼロの数がパディングされてしまっていたようです。

Apparently, the data was padded at the end with an unnecessary number of zeros when it was encrypted.

暗号化する際にチャンクデータのバイト数を固定してしまったことが原因のようです。

The reason seems to be that the number of bytes of chunk data was fixed when it was encrypted.

解決する方法として、データの総バイト数を数えて、それぞれのチャンクデータを適切なバイト数に調整します。

The solution is to count the total number of bytes of data and adjust each chunk to the appropriate number of bytes.

それからそのバイト数を数えた数が格納された配列を暗号化データと一緒に関数の外へ出力させます。

It then outputs an array containing the counted number of bytes, along with the encrypted data, out of the function.

あとは復号化の際にそのデータ数の配列を基に適切なバイト数で復号化していきます。

Then, at the time of decoding, it decodes with the appropriate number of bytes based on the array of the number of data.

とても長い文字列のメッセージでも試してみましょう。

Let's try a very long string message.

ただ、このやり方だとデータの総数やチャンクデータの数が外部に明るみになってしまいます。

However, with this method, the total number of data and the number of chunk data are exposed to the outside world.

例えば、十分に大きな素数p,qを用意したとしても、暗号化するメッセージの数がとても短いものだったらどうなるでしょうか?(チャンクデータの一部がとても短くなってしまうことを考慮しました)

For example, what happens if you have a sufficiently large prime p, q, but only a very small number of messages to encrypt? (I took into account that some chunk data would be very short.)

256バイトでチャンクデータを作った場合、このように大量のゼロがパディングされていることは外部からでも確認できます。

If you create chunked data with 256 bytes, you can see from the outside that a lot of zeros are padded like this.

このゼロの数を見て、おそらくメッセージが表示に短く、eの数が小さい数だと推測されます。

Looking at this number of zeros, we assume that the message is short and the number of e is small.

そうなると、暗号化されたCの数に(1/e)乗することによって、元のメッセージが解明されてしまいます。

Then, by doing C raised to the power of (1/e), the original message is unraveled.

もちろん、eの値が十分に大きければ問題はありませんが(例えば65537ようなデフォルトの値)、外部にデータの詳細を晒すのは危険です。

Of course, if the value of e is large enough (the default value is 65537, for example) then there is no problem, but exposing the details of the data to the outside world is dangerous.

教科書的RSAは他にc′≡c・2emodnを計算でき、暗号文に予測可能な変更を加えることができるとう脆弱性が存在します。

Another vulnerability is that textbook RSA can compute c′≡c・2emodn and make predictable changes to ciphertext.

それを避けるために今現在使われているRSA暗号はデータを暗号化する際にパディングを行います。

To avoid this, the RSA encryption currently in use performs padding when encrypting data.

マスク生成関数等、決められたアルゴリズムを使用して、パディングされるので、例えば先ほどのような方法でデータ数を数えて伝えるということは不要になります。

It is padded using a fixed algorithm, such as a mask generation function, so it is not necessary to count and convey the number of data as we did before.

PythonのサードパーティーモジュールであるcryptographyでRSAを使用すると、暗号化の際にパディング等のパラメータが使われていることが分かります。

Using RSA with Python's third-party module cryptography shows that parameters such as padding are used during encryption.

このモジュールはこの動画シリーズのパート1で使われているので、そちらも参考にしてみてください。

This module is used in Part 1 of my video series, so check it out.

駆け足でRSAの基本的な暗号化と復号化のやり方を説明していきましたが、より詳細な内容、パディングの詳細等は各自で調べてみてください。

I've done a quick tour of RSA's basic encryption and decryption methods, but please check the details by yourself more details, padding details, and more.

最後に大きな素数同士pとqを掛け合わせたnの値から、pとqを導き出すのがとても時間がかかるということを確かめてみましょう。

Finally, let's make sure that it takes a long time to derive p and q from the value n, obtained by multiplying large prime numbers p and q.

指定したビッツ数の素数pとq、そしてそれらを掛け合わせた値であるnを作成する関数を用意しましょう。

Let's create primes p and q of the specified number of bits and then provide a function to create n, which is the product of these primes.

まずは小さい値から試してみましょう。

Let's start with small values.

素因数分解をするにはsympyモジュールのfactorintメソッドを使用するのが一番簡単です。

The easiest way to do prime factorization is to use the factorint method in the sympy module.

ご覧の通り、小さい素数の場合、素因数分解に要する時間はとても短いです。

As you can see, for small prime numbers, the time required for prime factorization is very short.

では素因数分解に要する時間を測る関数を用意して、徐々にビッツ数を上げて検証してみましょう。

Now let's create a function that measures the time required for prime factorization and examine it by gradually increasing the bit length.

ほんの少しビッツ数を増やして時間を測ってみましょう。

Let's measure the time by increasing the bit length a little.

ご覧の通り、この程度のビット数なら素因数分解に要する時間は1秒もかかっていません。

As you can see, it takes less than a second to compute prime factorization of these bits.

しかし、少しずつビット数を増やしてみたらどうなるか確かめてみましょう。

But let's see what happens if we increase the number of bits little by little.

たった10ビッツ増やしただけで計算時間が約9倍遅くなりました。

With just 10 extra bits, it's about 9 times slower.

ご覧のとおり、20桁程度の素数同士でも素因数分解にかかる時間は1分以上を要しています。

As you can see, prime factorization takes more than 1 minute for prime numbers of about 20 digits.

これらの結果から、1024ビットのpとqを素因数分解で求めるのはとても膨大な時間を要することが理解できると思います。

From these results, you can see that it takes an enormous amount of time to obtain 1024 bits of p and q by prime factorization.



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

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