暗号と数学 ~ PythonでRSAを実装しよう!!~ その2

RSAをPythonを実装することで、その原理とついでにプログラミングも学んでしもうというこの企画。
前回の記事はこちらです。

前回のおさらい

前回は、

  • 2つの素数p,qを用意する
  • (q-1,p-1)の最小公倍数をLとして求める
  • Lより小さく、かつLと「素の関係」の適当な数Eを選ぶ
  • E * D = 1 (mod L)が満たされるDを求める
  • E,D,Nが求まるので、上の公式に当てはめる

という流れでRSAというものができているということを理解し、素数を求めるプログラムをPythonで書きました。
素数を求めるアルゴリズムはそれだけいくつも存在し、高速なものももちろんあります。
前回紹介したのは、その中でも一番初歩的なアルゴリズムで実装したものなので、実運用に耐えられるものではないということを誤認識ください。

最小公倍数(lcm)を求める

最小公倍数(lcm)とは、

最小公倍数(さいしょうこうばいすう、英: least common multiple)とは、 {\displaystyle 0} {\displaystyle 0}ではない複数の整数の公倍数のうち最小の自然数をさす。たびたび、L.C.M.等の省略形で記述される。 Wikipedia: 最小公倍数

とのことです。

例えば、2と3の最小公倍数であるなら、

  • 2 * 1 = 2
  • 2 * 2 = 4
  • 2 * 3 = 6

  • 3 * 1 = 3

  • 3 * 2 = 6
  • 3 * 3 = 9

となり、最小公倍数は6となります。まあ、簡単ですよね!

最大公約数(gcd)を求める

小さな数で計算すると簡単な最小公倍数なんですが、大きな数を求めるには少し複雑です。そこで、ひとまず最大公約数の求めるアプローチを考えてみましょう。

最大公約数(gcd)とは、

最大公約数(さいだいこうやくすう、英: greatest common divisor)とは、少なくとも1個が0ではない複数の整数の公約数のうち最大のものを指す。 Wikipedia: 最大公約数

とのことです。

12 と 8 の最大公約数は4です。

12 / 1 = 12
12 / 2 = 6
12 / 3 = 4
12 / 4 = 3
12 / 6 = 2
12 / 12 = 1

8 / 1 = 8
8 / 2 = 4
8 / 4 = 2
8 / 8 = 1

となり、 共通する割り切れる数の最大は4となるので、最大公約数は 4 となります。

最大公約数(gcd)を使って最小公倍数(lcm)を求める

ここで、元に戻って最小公倍数(lcm)を考えてみます。ここで思いつくのは、lcmはgcdの整数倍になるということです。
例えば、先ほどの12 と 8 の今度は最小公倍数(gcd)を考えてみましょう。

この最小公倍数は以下の式で書くことができます。

gcd = 12 * 8 / 4 = 24

つまり、最小公倍数(gcd)を求めるには、求めたい2つの数をかけた後に最大公約数(lcm)で割れば良いとうことですね。

最小公倍数(gcd)の求め方をPythonで書いてみる

さて、最小公倍数(gcd)の求め方はわかりましたので、これを求める関数を以下に書いてみます。

# /usr/bin/env python
# -*- coding: utf-8 -*-

# 最大公約数
def lcm(x,y):
    return x * y / gcd(x,y)

とまあ、とてもシンプルに書くことができました。
しかし、これだけでは不十分です。なぜならば、最大公約数(gcd)を求めなければいけないからです。

最大公約数(gcd)の求め方

最大公約数を求めるためには、数学の「ユークリッドの互除法」を用います。

ユークリッドの互除法(ユークリッドのごじょほう、英: Euclidean Algorithm)は、2 つの自然数または整式の最大公約数を求める手法の一つである。2 つの自然数(または整式) a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。 Wikipedia: ユークリッドの互除法

なんだか難しそうですね…。
とりあえず例を示してみます。

例えば、 390と273の最小公倍数(gcd)を求める場合。
ユークリッドの互除法を使えば以下のように書くことができます。

390 = 273 * 1 + 117
273 = 117 * 2 + 39
117 = 39 * 3 + 0

よって最小公倍数は39である。

ええーと思うかもしれませんが、この法則の証明はWikipedia先生にでも任せておくとして、これを用いてPythonで書いてみましょう。

ユークリッドの互除法をPythonで書いてみる

# /usr/bin/env python
# -*- coding: utf-8 -*-

# 最小公倍数
def lcm(x,y):
    while y > 0:
        x = y
        y = x%y
    return x

とこちらも非常にシンプルに書くことができます。

最小公倍数を求めるには、まとめ

まとめますと以下のようになります。

# /usr/bin/env python
# -*- coding: utf-8 -*-

# 最小公倍数
def lcm(x,y):
    while y > 0:
        x = y
        y = x%y
    return x

# 最大公約数
def lcm(x,y):
    return x * y / gcd(x,y)

これで、RSAを実装するための手段その2が完了しました。
次回はいよいよRSAの公開鍵と秘密鍵を作るところまでいっちゃいましょう!

  • このエントリーをはてなブックマークに追加
  • Pocket