RSA暗号で「ふっかつのじゅもん」を作る(1)

オッス、オラ、トンヌラ！
前回は、高速素数判定を作りましたが、今回はRSA暗号を使って、昔懐かしの「ふっかつのじゅもん」を作ってみましょう。

あ、「今さらRSAかよ」と思いました？
自分でRSAを実装してみると、色々知らない事が出てきて面白いですよ。
あとRSAは、暗号化以外にも応用が利くんで覚えておいて損はしませんよ。

RSA暗号とはなにか？

ゲームプログラマは基本的にゲームばっかやってるんで、一般的な情報処理知識に欠けている場合がほとんどです。
まずはRSA暗号の説明から始めましょう。

RSA暗号とは、２つの鍵「公開鍵」と「秘密鍵」を使う暗号方式です。
「公開鍵」は暗号化キーです、みんなに公開してかまいません。
「秘密鍵」は復号化キーです、みんなにバレてはいけません厳重に保管してください、間違ってもネット上には流してはいけません。

データを送ってもらう友達に「公開鍵」だけ渡し、公開鍵でデータを暗号化して送ってもらいます。
暗号化されたデータを復号化できるのは「秘密鍵」を持っているあなただけで、暗号化した友達も、データを横取りしようとしてるハッカーにも復号はできないのです。
このように暗号化キーだけを外部に出し、復号化キーは外部に出さない事で、強固なセキュリティを実現しています。

鍵を作ってみよう

それではRSA暗号の鍵を作ってみましょう。
まずは２つの素数p,qを用意しますが、計算が分かりやすいように小さい素数にしてみます。
p=193,q=11としましょう、次に２つの素数p,qの乗算した値をnとします。

#coding:utf8

p = 193
q = 11
n = p * q

次に(q-1,p-1)の最小公倍数をlとして求めます。
p=193,q=11の場合だと最小公倍数は960になります。

def gcd(a, b):
    """最大公約数を求める"""
    while b:
        a, b = b, a%b
    return a

def lcm(a, b):
    """最小公倍数を求める"""
    return a * b / gcd(a,b)

l = lcm(p - 1,q - 1)  #l = 960

lより小さく、かつlと「素の関係」の適当な数eを選びます。
但し、3は強度が弱いので3以外の数を選んでください、ここでは「77」を選んでみます。

e = 77
print gcd(e,l) #=> 1

次に「ed = 1 (mod l)」を満たすdを求めます、これはeとlが求まっていれば計算で求める事ができます。
eとlは素の関係ですので「gcd(e, l) = 1」ですよね、ここで「拡張ユークリッドの互除法」を使って「ex + ly = 1」のxとyを求めます。
(「ex + ly = 1」を変形すると「ex = ly-1」になるよ！）
求まったxがdとなります、もし「x < 0」になった場合はdにlを足します。

def gcd2(a, b):
    """拡張ユークリッド互除法"""
    if b == 0:
        u = 1
        v = 0
    else:
        q = a / b
        r = a % b
        (u0, v0) = gcd2(b, r)
        u = v0
        v = u0 - q * v0
    return (u, v)

d = gcd2(e,l)[0]
if d < 0:
    d += l

これで暗号化に必要なパラメータe,d,nが揃いました。

「公開鍵」はeとn、「秘密鍵」はdとnの値を使います。

それぞれの値は、e=77,d=773,n=2123となっているはずです。
暗号化は「x^e mod n」とするだけです、さっそく暗号化してみましょう。

#暗号化
org = [13,16,246,21,65,32]

crp = [pow(x,e,n) for x in org]
#crp => [1965, 586, 1589, 1902, 890, 967]

元データと関係ない値になりましたね、それでは復号してみましょう。
復号は「x^d mod n」するだけです。

#復号化
print [pow(x,d,n) for x in crp]
#[13, 16, 246, 21, 65, 32]

おー、復号化できました！！

長くなってしまったので、「ふっかつのじゅもん」の作成は次回に続きます。

RSA暗号で「ふっかつのじゅもん」を作る(2) -RSA暗号鍵の生成 - Pashango’s Blogへ続きます。