前回は公開鍵暗号について簡単にまとめました。
今回はpythonで公開鍵暗号を実装してみたいと思います。
公開鍵と秘密鍵を作り、暗号化と復号化のテストという流れになります。
実際公開鍵と秘密鍵を作ることができればほぼ終わりですね。

実装

早速プログラムを。
まずはエントリーポイントとなる部分から。

#MakerKey.py

import UtilCalc
import random
import sys

##　鍵を作る
def generateKey(keySize=1024):
  p,q = 0,0
  while p == q:
    p = UtilCalc.generatePrime()
    q = UtilCalc.generatePrime()

  n = p*q # 行程2

  pMin = p-1
  qMin = q-1
  l = pMin*qMin/UtilCalc.gcd(pMin, qMin) # 行程3

  e = 0
  while True:
    e = random.randrange(2**(keySize-1),2**(keySize))
    if 1 < e and e < l and UtilCalc.gcd(e,(p-1)*(q-1)) == 1: # 行程4
      break

  d = UtilCalc.findModInverse(e,l) # 行程5

  publicKey = (n,e) # 行程6
  privateKey = (n,d) #　行程6

  return (publicKey,privateKey)

##　エントリーポイント
##　鍵をつくる関数を呼び戻り値をファイルに書き込んだりする
def main(file = "rsa_key.txt"):
  print("Making Key...")
  keySize = 1024
  publicKey,privateKey = generateKey(keySize)

  f = open("public_%s"%(file),"w")
  f.write("%s,%s,%s"% (keySize,publicKey[0],publicKey[1]))
  f.close()

  f = open("private_%s"%(file),"w")
  f.write("%s,%s,%s"%(keySize,privateKey[0],privateKey[1]))
  f.close()

  print("Generated Key File")

if __name__ == '__main__':
    file = "rsa_key.txt"
    if len(sys.argv) > 1:
        file = sys.argv[1]
    main(file)

そしてこちらが素数や鍵を作るにあたって助けとなる便利な関数群です。

#UtilCalc.py
import random

## 素数の判定に使う
def millerRabin(num):
  if num % 2 == 0 or num < 2:
    return False

  if num == 3:
    return True

  s = num - 1
  t = 0
  while s % 2 == 0:
    s = s // 2
    t += 1

  for trials in range(5):
    a = random.randrange(2,num-1)
    v = pow(a,s,num)
    if v != 1:
      i = 0
      while v != (num-1):
        if i == t -1:
          return False
        else:
          i = i + 1
          v = (v ** 2) % num

  return True

## 素数を作る
def generatePrime(key=1024):
  while True:
    num = random.randrange(2**(key-1),2**(key))
    res = millerRabin(num)
    if res == True:
      return num

## 最小公倍数を求める
def gcd(x,y):
  while x != 0:
    x,y = y%x,x
  return y

## モジュラ逆数を求める
def findModInverse(a,m):
  if gcd(a,m) != 1:
    return None
  u1,u2,u3 = 1,0,a
  v1,v2,v3 = 0,1,m
  while v3 != 0:
    q = u3 // v3
    v1,v2,v3,u1,u2,u3 = (u1 - q * v1),(u2 - 1 * v2),(u3 - q * v3),v1,v2,v3
  return u1 % m

プログラムの流れとしては前回まとめた行程通りにほぼ動いていると思います。
ただ手間がかかるところとして素数を求める部分とモジュラ逆数を求める部分ですかね。

素数はミラーラビン素数判定法というアルゴリズムで求めています。
こちらは確率的素数判定法と呼ばれているらしく、絶対ではないが高確率で素数を見つけることができるものらしいです。

公開鍵暗号についての記事なので数学的な背景にはあまり深入りしないようにしたいと思います。
こんな感じで実行します。

ファイル名を指定すると作られるファイルの名前が、
private_{指定されたファイル名}　<-秘密鍵
public_{指定されたファイル名}　<-公開鍵
になります

$ python MakeKey.py sample_key.txt
Making Key...
Generated Key File

動作確認

実際に作成した鍵で暗号化と復号化をしてみましょう。
だいたいこんなプログラムになりますかね

f = open("private_sample_key.txt", "r")
privates = f.read().split(",")
f.close()

f = open("public_sample_key.txt", "r")
publics = f.read().split(",")
f.close()

modulas = int(privates[1])
privateEx = int(privates[2])
publicEx = int(publics[2])

target = 1234567890
print("target",target)
enc = pow(target, publicEx, modulas)
print("encrypt message", enc)
clear = pow(enc, privateEx, modulas)
print("clear message", clear)

$ python testPublic.py
('target', 1234567890)
('encrypt message', 3087344792070113732449191532099075258861568268386064775647535663231917861402920336288733110186410702637254305136732504685212751191909848918346807152211925936965763249491627780376631525663562845978244325296236007263025716470375785178159202425082610295334209075176581969793541149495719727096657950405042726831000180744064753186184026078252735607150738889169940072019126957955752541240136891770775411266575590192101955779722932358881468449551612065229327758806315283500497783743050927641276635205554186948765851364915378762131281832686580860328030412080513070945315067147835874324627924608668759993348127224908045711202L)
('clear message', 1234567890L)

正しく復号化されていれば成功です。
おそらく問題ないかと思います。

今回は稚拙ながら公開鍵暗号をプログラムしました。
機会があったら他の暗号方式にも触れてみたいと思います