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

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

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

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

Please refer to the video for details.

前回の続きです。

Continued from last time.

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

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.

様々な整数同士の最大公約数を確かめてみましょう。

Let's examine the greatest common divisor of the various integers.

このように、最大公約数が1の整数同士は互いに素であるといえます。

Thus, integers with the greatest common divisor of 1 are relatively prime.

mathモジュールのgcdメソッドを使えばより簡単に最大公約数を調べることができます。

The gcd method in the math module makes it easier to find the greatest common divisor.

import math

math.gcd(10,1)
math.gcd(10,2)
math.gcd(10,3)

for i in range(1,11):
    print(f"gcd(10, {i}) -> {math.gcd(10,i)}")
 
gcd(10, 1) -> 1
gcd(10, 2) -> 2
gcd(10, 3) -> 1
gcd(10, 4) -> 2
gcd(10, 5) -> 5
gcd(10, 6) -> 2
gcd(10, 7) -> 1
gcd(10, 8) -> 2
gcd(10, 9) -> 1
gcd(10, 10) -> 10

前回の動画の図で説明に使われた例題を試してみましょう。

Let's try the example used in my previous video illustration.

このように９と互いに素な9以下の正の整数は６つあることが分かります。

As you can see, there are six positive integers less than or equal to 9, which is a relatively prime.

では簡単なphi関数を作成してみましょう。

Let's create a simple phi function.

では例題を使って関数を試してみましょう。

Let's try out the function we created using an example.

def phi_func(num):
    if num <= 0:
        print("0 or not a positive integer.")
        return
    if not isinstance(num, int):
        print("Not an integer.")
        return
    count = 0
    for i in range(1, num):
        if math.gcd(num, i) == 1:
            count += 1
    return count

phi_func(9)
6

では関数の内部で何が行われているか、詳しく観察できるような別のphi関数を作成してみましょう。

Let's create another phi function that allows us to look closely at what's going on inside the function.

phi_func2(9)
The greatest common divisor of 9 and 1 is 1.
The greatest common divisor of 9 and 2 is 1.
The greatest common divisor of 9 and 3 is 3.
The greatest common divisor of 9 and 4 is 1.
The greatest common divisor of 9 and 5 is 1.
The greatest common divisor of 9 and 6 is 3.
The greatest common divisor of 9 and 7 is 1.
The greatest common divisor of 9 and 8 is 1.

For a given positive integer 9,
the number of natural numbers 1 to 9
inclusive which are relatively prime with 9 is 6.

phi_func2(6)
The greatest common divisor of 6 and 1 is 1.
The greatest common divisor of 6 and 2 is 2.
The greatest common divisor of 6 and 3 is 3.
The greatest common divisor of 6 and 4 is 2.
The greatest common divisor of 6 and 5 is 1.

For a given positive integer 6,
the number of natural numbers 1 to 6
inclusive which are relatively prime with 6 is 2.

phi_func2(21)
The greatest common divisor of 21 and 1 is 1.
The greatest common divisor of 21 and 2 is 1.
The greatest common divisor of 21 and 3 is 3.
The greatest common divisor of 21 and 4 is 1.
The greatest common divisor of 21 and 5 is 1.
The greatest common divisor of 21 and 6 is 3.
The greatest common divisor of 21 and 7 is 7.
The greatest common divisor of 21 and 8 is 1.
The greatest common divisor of 21 and 9 is 3.
The greatest common divisor of 21 and 10 is 1.
The greatest common divisor of 21 and 11 is 1.
The greatest common divisor of 21 and 12 is 3.
The greatest common divisor of 21 and 13 is 1.
The greatest common divisor of 21 and 14 is 7.
The greatest common divisor of 21 and 15 is 3.
The greatest common divisor of 21 and 16 is 1.
The greatest common divisor of 21 and 17 is 1.
The greatest common divisor of 21 and 18 is 3.
The greatest common divisor of 21 and 19 is 1.
The greatest common divisor of 21 and 20 is 1.

For a given positive integer 21,
the number of natural numbers 1 to 21
inclusive which are relatively prime with 21 is 12.

このようにしてphi関数にnを入れてその値を求めるわけですが、元々のnはかなり大きな数です。

So we put n into the phi function and get its value, but the original n is a fairly large number.

整数を一つずつ計算していくと、大分時間がかかります。

Calculating integers one by one takes a lot of time.

しかし解決策は簡単です。先ほど作成したphi関数に小さな素数を入れて計算をしてみてください。

But the solution is simple. Put a small prime number in the phi function you just created.

そうすると、かならず元の素数の数から1を引いた値になるはずです。

Then, the value should always be the original prime number minus one.

最大公約数の定義と素数の性質を考えれば分かります。

You can tell by considering the definition of the greatest common divisor and the nature of primes.

素数は1とその数以外に約数を持たないからです。

Because prime numbers have no divisor other than 1 and itself.

なので、素数pとqを掛けた値をphi関数に入れて計算した結果は(p - 1)掛ける(q - 1)となります。

Therefore, the result calculated by putting the value that multiplied by two primes p and q to the phi function is (p - 1) times (q - 1).

では、手順4へ進みましょう。

Let's go to step 4.

このeの値とnの値が暗号化に使われます。（つまり公開鍵になります。）

The values of e and n are used for encryption. (That is, the public key.)

このeの値は65537がよく使われるようですが、十分に大きくて、一より大きくphiN未満であり、phiNと互いに素の関係であればどんな値でもいいです。

The value of e is used often 65537, but it can be any value that is large enough, greater than 1 and less than phiN, and relatively prime to phiN.

ではこの値eの候補がどのようなものになるのかを確かめてみましょう。

Now let's see what the candidate for this value e looks like.

但し素数であれば条件に合うとは限りません。

However, if it is a prime number, it does not necessarily meet the condition.

そのことが正しいかどうか試してみましょう。

Let's see if it's correct.

続いて、手順5へ進みましょう。

Then go to step 5.

この方法で導きだしたdはnと共に復号化に使われます。（つまり秘密鍵です。）

The d derived in this way is used for decryption along with n. (That is, the private key.)

ではこの値を計算するにはどのようにすればいいでしょうか？

So how do we calculate this value?

その疑問の解決策は拡張ユークリッドの互除法と呼ばれるアルゴリズムを使うことです。

The solution is to use an algorithm called the extended Euclidean algorithm.

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

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