017 Pythonでビットコインを学ぶ (教科書的RSA 1)
017 Use python to learn bitcoin (Textbook RSA 1)

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

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

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

Please refer to the video for details.

前回の続きです。

Continued from last time.

それでは教科書的RSAの仕組みを学習していきましょう。

Now let's learn how textbook RSA works.

実際にRSA暗号を使って署名や通信の暗号化を行う際にはパディングを行います。

When actually signing or encrypting communications using RSA encryption, padding is done.

つまり、所謂教科書的RSAとはパディング無しのRSAを指します。

In other words, the so-called textbook RSA is RSA without padding.

まず手順１です。図を見てください。

Step one. Look at the diagram.

それではPythonで十分大きな二つの異なる素数pとqを作成してみましょう。

Now let's using python for create two different primes, p and q, which are large enough.

所々で前回までの動画シリーズで紹介したものが出てきますので、前回までの動画シリーズを復習してみてください。

In some places, there you'll find the scripts from the previous video series introduced will appear, so please review the previous video series.

import secrets
import sympy

secretsモジュールのrandbitsメソッドは、引数に指定したビット数のランダムなビット列を生成します。

The randbits method in the secrets module generates a random sequence of bits with the number of bits specified in the argument.

secrets.randbits(1024)
57485880443856632600823725036542498172709092638104800683675748906961195127969410592478642721615984511105677008428640773845395544861451040244856868680270387311980686676236653892929122145016209955012752865364892930852238312969569773911577848485665730847374336093071239116720945931020347482961389082717898505832

ビット数を1024にしましょう。これで1024ビット掛ける1024ビットは2048ビットになります。

Let's set the number of bits to 1024. Now 1024 bits multiplied by 1024 bits is 2048 bits.

bit_length = 1024
bin(secrets.randbits(bit_length))
'0b1000110000111110100010011100101011100001001110100001001011110110010010001111010110001100000001100000100110111011011110010100011011110001000110110110010011010100001110011011001101011110011010111010100100101000011001100011111010010100010011011100000010100111010110010000011101001000010101100000000100100101011111000110001000010100001000100011110000110100010000001000001001011000001111001001100111001100011011100010101010110101111001110011011111000100010010100010101000011111001001000011010001100010101110101110000000111011010100110111011111011011101111011010001001110110000110001010001000111111111111110110010110110100111001101011001101010010100000100001000100011001001100011100010000001100111000000101010000011111110000101111010111111100100011110001101101101110000001010010111100111101111101101011101001011000011010010000111000000100011010001100001100010010010111011000001000001000101100101011010100111110001011011000001011100000010101101111101000101100101011010010111110111010111110000101010011100010111100100101100111101101'

これを仮のpとします。

Let this be the temporary p.

p = secrets.randbits(bit_length)

このpを素数にする為に工夫をします。

Then, we'll do a little bit of work to make this p a prime number.

このランダムビッツを常に1024ビッツ以上にしたいので、1023ビット目を1にして1024ビット長に合わせます。

Since we want this random bits to always be at least 1024 bits, we'll set 1023th bit to 1 to make it 1024 bits long.

testp = "0b" + "0" + ("1" * (bit_length - 2)) + "0"
testp
len(format(int(testp, 2), 'b'))
bin(1 << bit_length - 1)
len(bin(1 << bit_length - 1)[2:])
bin(int(testp, 2) | (1 << bit_length - 1))
len(bin(int(testp, 2) | (1 << bit_length - 1))[2:])

そして0ビット目を1にして奇数にします。（2以外の素数は奇数しかないので）

Then, 0th bit is set to 1 to make it odd. (Because there's only an odd number of prime numbers other than 2)

bin((1 << bit_length - 1) | 1)
testp = int(testp, 2)
testp |= ((1 << bit_length - 1) | 1)
bin(testp)
len(bin(testp)[2:])

そしてsympyモジュールのisprimeメソッドでpが素数かどうかを判定します。

It then uses the isprime method in sympy module to determine if p is prime.

sympy.isprime(testp)
False

ワイル文を使って、1024ビッツの素数pを作成しましょう。

Let's use While statement to create a prime p of 1024 bits.

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

同じ様にqも作成します。

Create q as well.

十分に大きな二つの異なる素数pとqを作成できたので、手順2をPythonで行ってみましょう。

Now that we have created two sufficiently large different primes, p and q, so let's do step 2 in Python.

とはいってもやることは簡単なので一瞬で終わります。

That said, it's easy to do, so it ends in a second.

次に手順３をPythonで行ってみましょう。

Next, let's do step 3 in Python.

オイラーのトーシェント関数（またの名をファイ関数）を素数に対して行うと以下の式になります。

When Euler's totient function (also known as the phi function) is applied to prime numbers, the following equation is obtained.

オイラーのトーシェント関数（またの名をファイ関数）を図で簡単に説明します。

Let's take a quick overview of Euler's totient function (also known as the phi function) using several diagrams.

例としてファイ関数に９を入れてみましょう。

As an example, let's put 9 in the phi function.

９以下の正の整数は１から９まであります。

Positive integers less than or equal to 9 can range from 1 to 9.

すると９と互いに素な関係の正の整数はこの中では６つあります。

Then there are six positive integers that are relatively prime to 9 in the relationship between 9.

つまり、ファイ関数に９を入れた結果は６となるわけです。

That is, if you put 9 in the phi function, the result is 6.

互いに素であることを確かめるには最大公約数を使用します。

Use the greatest common divisor to make sure that these integers are relatively prime.

つまり与えられた整数以下で、最大公約数が1の整数同士を見つければいいわけです。

In other words, all you have to do is find integers that are less than or equal to a given integer and have the greatest common divisor of 1.

Pythonを使って確かめてみましょう。

Let's test it with Python.

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

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