Published Date : 2021年8月25日3:36

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

#### 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.

 ① 動画の説明 ① Video Description ページの最後へ Go to the end of the page.

##### ① 動画の説明① Video Description

Continued from last time.

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.

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.

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.