Python RSA

ここは C# のコーナーなのですが、特別に Python を使った RSA のプログラムを紹介します。

Python を使った暗号化と複合化

非常に簡単なソースコードですが、暗号化と複合化の Python のプログラムです。 (^_^;)
# から後はコメントです。

m = 123             #暗号化する文字列
e = 17              #公開鍵
n = 3233            #公開鍵（素数の積）
d = 2753            #秘密鍵
c = pow(m,e)%n      #pow(m,e) ＝ m の e 乗
print('暗号化文字列C = ', c)
m = pow(c,d)%n
print('複合化文字列M = ', m)

Python の説明は、参考書や他の URL を参照して下さい。
送りたい数字を 123 とします。
17 と 3233 が公開鍵で、3233 は二個の素数の積です。
2753 が秘密の鍵です。

このプログラムの実行結果です。

c:\DATA\Python>python ende_code.py
暗号化文字列C =  855
複合化文字列M =  123

123 を暗号化して 855 を送ります。
855 を複合化して、元の 123 を取得します。
このとき問題となるのが c = pow(m,e)%n で、pow(m,e) は m の e 乗です。
暗号化のときは 123 の 17 乗を、複合化のときは 855 の 2753 乗を計算します。
所で 855 の 2753 乗は何桁の整数になるのでしょう？
この計算をやってくれる事が Python の凄いところです。 ＼(^o^)／

秘密の鍵を求める

公開鍵を構成する二個の素数が見つかれば秘密の鍵が解ります。
あまり公にしない方が良いのかも知れませんが、ネットで検索すれば私でも見つけられるのですから問題ないでしょう。

p = 43
q = 53
e = 1241

n = p*q
phi = (p-1)*(q-1)

# Took from SO
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    g, y, x = egcd(b%a,a)
    return (g, x - (b//a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('No modular inverse')
    return x%m

d = modinv(e, phi)

print('【例1】(素数P,素数Q,公開鍵E)=(61,53,17)なら、秘密鍵D=2753')
print('【例2】(素数P,素数Q,公開鍵E)=(43,53,1241)なら、秘密鍵D=1649')
print('素数P =', p)
print('素数Q =', q)
print('公開鍵N(P*Q) =', n)
print('オイラー関数Phi =', phi)
print('公開鍵E =', e)
print('秘密鍵D =', d)

43, 53 が公開鍵を構成する２個の素数です。
1241 が二個目の公開鍵です。
プログラムを実行すると、秘密の鍵 1649 が見つかります。

[Previous Chapter ↑] 公開鍵方式の暗号

超初心者のプログラム入門(C# Frame Work)