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

みなさん、こんにちは。最近はもっぱらプログラミング言語Pythonにはまっています。全くのプログラミング言語初心者の私でしたが、なんとか簡単な計算くらいはできるようになった気がしています。

そんなPythonとセキュリティを組み合わせて何かできないかなぁと思っていたところ、以前書いた、RSAの基本を書いた記事

を思い出し、よっしゃこれをPythonで実装してみるか!と思い立ったので今回記事にしてみました。

調べてみると、このRSAを実装することによってPythonの基本的な部分を網羅できるのではないかということで、少しずつ解説してきたいと思います。RSAを実装していくことで、pythonやアルゴリズムの基本的な考えを解説します。

RSAの基礎基本

 さて、以前の記事を参考に、もう一度RSA暗号の基本を思い出してみましょう。
RSA暗号とは、秘密鍵と公開鍵の二つを用いた暗号化の方式です。考案した人たちの頭文字をとってRSAと名付けられたそうです。

平文を「公開鍵」を使って、暗号化します。公開鍵はその名前の通り、公開しても構いません これを使って暗号化しているわけですから、これをどうこうやっても元の平文にはたどり着けません。

この公開鍵とペアになっているのが、「秘密鍵」です。この秘密鍵は公開鍵で暗号化された平文を複合するものですから、公開してはなりません。その名の通り、「秘密」にしておかなければならないのです。

rsa

RSAを作るためのフロー

さあ、それではこのRSA鍵のペア(秘密鍵と公開鍵)を作っていきましょう。RSAを作るための数式ですが、以下のように以前も紹介しました。
(数式の詳しい説明は省略します。https://se-cure.info/?p=245をご覧ください。)

暗号文 = 平文E mod N

平文 = 暗号文D mod N

という基本の数式と、二つの”素数”を考えてみましょう。

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

というような流れになるかと思います。

素数を出力するプログラム

それではやっとこさ、Pythonでプログラミングしていきましょう。最初のお題は素数を出力するプログラムです。これを使って、pとqを求めていきましょう。素数なんて手計算で求められるんですが、練習ということで。素数は無限にあるので、簡単に0~10000までの数の中で、素数だけを出力するプログラムを作ってみましょう!

素数とは、

Wikipedia
「1と自分自身以外に正の約数を持たない自然数で、1 でない数。または、正の約数の個数が 2 である自然数」

とのことでしたので、あるaをa-1までの数で割り切れた数字が素数だと言えそうですね。

untitled-diagram

さて、これをpythonで書いてみましょう。


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

# 素数を判定する関数
def prime_1(x):
    for y in range(2,x-1):
        if x % y == 0:
            return False
    return True
            
# 素数なら出力
for i in range(2,10001):
    if prime_1(i) == True:
        print(i)

2
3
5
7
11
13

9973

あまり、立派なコードとは言えないですが、こんな感じで書くことができますね。実行してみるとわかると思いますが、このプログラムでは出力までに少々時間がかかります。

実は、出力された数をみると「2」以外の数字は全て奇数となっていますね。ということなので、a-1までの奇数だけを割ればいいわけですので、こんな感じで書き換えることにしました。

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

# xまでの素数をリストに格納する
def prime_2(x):
    primes=[2,3]
    for x in range(5,x,2):
        for y in range(0,len(primes)):
            if x % primes[y] == 0:
                break
        else:
            primes.append(x)
    print(primes)

prime_2(10000)

prime_2関数のxに値を入れて、その値までの素数を出力するプログラムを書いてみました。xまでの数の奇数に対して、2と3から始まる素数を割って、割り切れなければ素数と判断しています。

さて、これで任意の数までの素数を求めることができるようになりました。他にも素数を求めるアルゴリズムはありますので、ぜひ自分で見つけて実装してみてください。

次回は、最大公約数をpythonで求めようと思います。

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