Published Date : 2021年8月29日3:45
ニコニコ動画にアップした動画のまとめ記事です。
This is a summary blog post about a video I uploaded to NicoNico.
細かい部分は動画を参考にしてください。
Please refer to the video for details.
目次
Table of Contents
前回の続きです。
Continued from last time.
では拡張ユークリッドの互除法の概要を説明していきます。
I will explain the outline of the extended Euclidean algorithm.
その前に図を見ながら前回説明したユークリッドの互除法の簡単な復習を行いましょう。
Before we do that, let's do a quick review of The Euclidean algorithm I described in my previous video by looking at the diagram.
例えばgcd(102, 78)をaが102、bが78の長方形として考えてみましょう。
For example, consider gcd(102, 78) as a rectangle with a=102 and b=78.
そうすると、図が示す通り、102を78で割ると78×1+余り24となり、一辺が78の正方形を長方形の中に描くことができます。
As you can see, 102 divided by 78 equals 78 x 1 plus a remainder of 24, so you can draw a square with sides of 78 in the rectangle.
一辺が78の正方形の中に描かれた線の本数は式（78×〇）の、〇の中の数（今回の場合は一ですね）に相当します。
The number of lines drawn in the square with sides of 78 is equal to the number in 〇 in expression (78 × 〇). (in this case, 1).
そうすると次は余り24の辺とb=78の辺の長方形が残ります、その長方形の中に辺が24の正方形が3つ入るような長方形を描きましょう。
Next, you will have a rectangle with sides 24 (this is the number of the previous remainder) and b = 78. Draw a rectangle that has 3 squares with sides of 24 in the rectangle.
すると式（24 x 3 + 6）の6の部分が78割る24の余りとして残されます。
The 6 part of expression(24 x 3 + 6) is left as the remainder of 78 divided by 24.
そしたら最後に24を6で割ると（式6 x 4 余り０）となり、6が102と78の最大公約数となることが確認できます。
Finally, 24 is divided by 6 (expression 6 x 4 remainder 0), and 6 is the greatest common divisor of 102 and 78.
前回の動画で登場した、eとdを掛けた値をφ(n)で割った余りが1となるdの式を変形してみましょう。
Try to deform the equation for d in which e times d is divided by φ(n) and the remainder is 1 that appeared in my previous video.
先ほどのユークリッドの互除法を使った式と似ていないでしょうか？
Isn't it similar to the Euclidean algorithm I described earlier?
物事を簡単にするため、二つの異なる素数pとqを11と17にして、φ(n)の値も160という小さい数字で実際に計算してみましょう。
To simplify things, let's take two different primes, p and q, and make them 11 and 17, and actually calculate the value of φ(n) with the small number 160.
φ(n)の値(160)と互いに素なeの値は3にします。
Let e, which is a relatively prime for φ (n), be 3.
ちなみに160にXを掛けていますが、これは160の倍数を意味しています。
By the way, I multiply 160 by x, which means a multiple of 160.
拡張ユークリッドの互除法では(式ax+by=gcd(a,b))を満たす整数解x,yが存在するので、今回の場合xはd、yがxになります。
In the extended Euclidean algorithm, there exists an integer solution x, y that satisfies (Equation ax + by = gcd(a, b)), so in this case x becomes d and y becomes x.
では変形し終わった一次不定方程式3d + (-160x) = 1の整数解をユークリッドの互除法を用いて、つまり拡張ユークリッドの互除法として計算してみましょう。
Now Let's try compute the integer solution of the transformed an indeterminate equation (3d + (-160x) = 1) using Euclidean's algorithm, that is, the extended Euclidean algorithm.
やり方は簡単です。ax+by=1の式のaとbに対してユークリッドの互除法を適用します。
It's easy to do. We simply apply the Euclidean algorithm to a and b in the expression ax + by = 1.
そして導き出されたそれぞれの式をaとbに当てはめていきます。
Then we apply each of these expression to a and b.
別の整数解のペアを求める簡単な方法は、ax+byの式の右辺が0となるようなxとyを求めて（aにbを掛けて、bにaを掛けた値を引いた式にする）その式を足します。
A simple way to find another pair of integer solutions is to calculate x and y so that the right-hand side of the expression ax + by is zero, and then add it (a times b minus b times a equals zero).
この場合(d: -53, x: -1)も(d: 107, x: 2)も共に式3d - 160x = 1となる条件を満たします。
Both (d: -53, x: -1) and (d: 107, x: 2) satisfy the condition that expression 3d - 160x = 1.
これでdの値を求めることができました。
You have now determined the value of d.
そして手順6の通りに公開鍵を(e,n)として、秘密鍵を(d,n)とし、公開鍵を使って暗号化されたメッセージを秘密鍵を使って復号化していきます。
Then, as in step 6, the public key is set to (e, n), the private key is set to (d, n), and the message encrypted using the public key is decrypted using the private key.
ではPythonを使って先ほどの図の式の通りに計算すると、本当に暗号化と復号化ができるかどうかを確かめてみましょう。
Let's use Python to try to see if you can really encrypt and decrypt it by using the formula in the previous diagram.
メッセージをバイトオブジェクトに変換します。
Converts a message to a byte object.
p,q,n,phiN,e,dの値をそれぞれ変数に代入していきます。
The values of p, q, n, phiN, e and d are assigned to the variables.
関数に渡す引数の先頭にアスタリスクを付けるとトゥープルやリストがそのまま引数として使用できます。
To use a tuple or list as an argument to a function, precede the argument passed to the function with an asterisk.
関数に引数で渡す時は再度アスタリスクを付けます。
Use asterisks again when passing arguments to the function.
これで暗号化と復号化ができることが確認できました。
Now you can confirm that encryption and decryption are possible.
ではPythonを使って先ほどの拡張ユークリッドの互除法を試してみましょう。
Now, Let's use Python to try the extended Euclidean algorithm described earlier.
message = "hello rsa"
b_message = bytes(message, "utf-8")
b_message
b'hello rsa'
b_message.hex()
'68656c6c6f20727361'
b_message[0]
104
b_message.hex()[:2]
'68'
int(b_message.hex()[:2], 16)
104
d = 107
e = 3
p = 11
q = 17
n = p * q
phiN = (p - 1) * (q - 1)
public_key = (e, n)
secret_key = (d, n)
def encrypto(b, *args):
e, n = args
return (b ** e) % n
b_message[0]
104
b = b_message[0]
b
104
encrypto(b, *public_key)
59
[encrypto(b, *public_key) for b in b_message]
[59, 118, 80, 80, 100, 43, 130, 4, 113]
[chr(encrypto(b, *public_key)) for b in b_message]
[';', 'v', 'P', 'P', 'd', '+', '\x82', '\x04', 'q']
cipher_text = "".join([chr(encrypto(b, *public_key)) for b in b_message])
cipher_text
';vPPd+\x82\x04q'
def decrypto(c, *args):
d, n = args
return (c ** d) % n
C = [encrypto(b, *public_key) for b in b_message]
C
[59, 118, 80, 80, 100, 43, 130, 4, 113]
D = [decrypto(c, *secret_key) for c in C]
D
[104, 101, 108, 108, 111, 32, 114, 115, 97]
decrypted_message = "".join([chr(m) for m in D])
decrypted_message
'hello rsa'
これはPythonスクリプトで拡張ユークリッドの互除法を組み立てるための簡単な模式図です。
This is a simple diagram for building an extended Euclidean algorithm in a Python script.
ユークリッドの互除法と同様に、aとbの値をb, b%aといった具合にスワッピングしていきます。
As with Euclidean algorithm, the values of a and b are swapped as b, b%a, and so on.
拡張されている箇所は二つの整数値が同様に上から順にスワッピングされている点です。
The extension is that the two integer values are also swapped from top to bottom.
より詳しくアルゴリズムの流れを観察するためにまずはprint関数を使った拡張ユークリッドの互除法の関数を作成してみましょう。
To see the flow of the algorithm in more detail, let's first create a function for the extended Euclidean algorithm using the print function.
まず始めに、ユークリッドの互除法と同様にaをbで割った余りのrとbがaとbに入れ替わります。
First, as in Euclidean algorithm, the remainder of a divided by b, that is r, and b, is replaced by a and b.
そしてaをbで割った商を使ってx,yの値を入れ替えていきます。
We then use the quotient of a divided by b to swap the x and y values.
ユークリッドの互除法と同様にbが0になるまで上記の作業を繰り返します。
Repeat until b equals 0, as in Euclidean algorithm.
以上です。お疲れ様です。
That's all. Thank you for your hard work.