はじめに
大学の授業の延長でRSA暗号のアルゴリズムを書く機会があったので、Pythonの勉強にとやってみました。
数学の難しいことは今回は無視します
目標
100桁の素数を扱う
参考にしたサイト
Python で公開鍵暗号アルゴリズム RSA を実装してみる
素数判定いろいろ - フェルマーテスト・ミラーラビン素数判定法
参考というかこの二つのコピぺ…
なので詳しいことは省きます。
公開鍵と秘密鍵について
暗号文 = {平文}^{E}\mod N
平文 = {暗号文}^{D}\mod N
このようなE,D,Nという３つの鍵を生成していきます。
E,Nが公開鍵
D,Nが秘密鍵 になります。
素数生成
鍵生成につかう素数を生成する処理を書いていきます。
素数判定
素数生成には、ランダムな数を生成して素数かを判定にかけていくのを繰り返す方法を取ります。
以下は素数判定の処理です。ミラーラビンの素数判定法を用いています。
素数判定
import random
def CheckEven(n):#偶数かどうかを判定。偶数だったらTrue
if n & 1 == 0:
return True
else:
return False
def CheckPrime(n):#素数かどうか判定。素数だったらTrue
if n == 2: return True
if n <= 1 or CheckEven(n):return False
d = (n - 1) >> 1
while CheckEven(n):
d >>= 1
for i in range(100):
a = random.randint(1,n-1)
t = d
y = pow(a,t,n)
while t != n -1 and y != 1 and y != n - 1:
y = pow(y,2,n)
t <<= 1
if y != n - 1 and CheckEven(t):
return False
return True
素数の取得
上記の素数判定を使い素数を生成します
import random
def GetRandomPrime(max):#max未満のランダムな素数を返す。存在しない場合は-1を返す
if(max <= 1):return -1
while(True):
rand = random.randint(2,max)
if(CheckEven(rand)):rand += 1
if(CheckPrime(rand)):break
return rand
鍵生成
生成した2つの素数で鍵を生成します。
鍵生成
import math
def LCM(x,y):#最小公倍数
return x * y // math.gcd(x,y)
def ExtendedEuclid(x,y):#拡張ユークリッドの互除法
#if(x<0 or y<0):return 0
c0, c1 = x, y
a0, a1 = 1, 0
b0, b1 = 0, 1
while c1 != 0:
m = c0 % c1
q = c0 // c1
c0, c1 = c1, m
a0, a1 = a1, (a0 - q * a1)
b0, b1 = b1, (b0 - q * b1)
return c0, a0, b0
def Congruence(a,m):#一次合同式 (ax≡1 mod m) を解く
i,D,k = ExtendedEuclid(a,m)
return D % m
def GenerateKeys(p,q):#二つの素数から秘密鍵と公開鍵を生成
N = p * q
L = LCM(p-1,q-1)
E = 0
D = 0
for i in range(2,L):
if math.gcd(i,L)==1:
E = i
break
D = Congruence(E,L)
return (E,N),(D,N)
暗号化と復号化
暗号化
暗号化
def Encryption(plainText,publicKey):#公開鍵で暗号化
E,N=publicKey
plainInteger = [ord(char) for char in plainText]
encrytedInteger = [pow(i,E,N) for i in plainInteger]
encrytedText = ([str(i) for i in encrytedInteger])
return encrytedText
暗号文を文字列にしようとすると、素数が大きすぎる数値の場合オーバーフローします。(chr関数の限界)
なので今回は暗号文を数字にするという選択を取りました。
復号
def Decryption(encryedText,privateKey):#秘密鍵で復号化
D,N = privateKey
encrytedInteger = [int(char) for char in encrytedText]
decrytedInteger = [pow(i,D,N) for i in encrytedInteger]
decrytedtext = ''.join([chr(char) for char in decrytedInteger])
return decrytedtext
まとめ
import random
import math
import sys
def LCM(x,y):#最小公倍数
return x * y // math.gcd(x,y)
def ExtendedEuclid(x,y):#拡張ユークリッドの互除法
c0, c1 = x, y
a0, a1 = 1, 0
b0, b1 = 0, 1
while c1 != 0:
m = c0 % c1
q = c0 // c1
c0, c1 = c1, m
a0, a1 = a1, (a0 - q * a1)
b0, b1 = b1, (b0 - q * b1)
return c0, a0, b0
def Congruence(a,m):#一次合同式 (ax≡1 mod m) を解く
i,D,k = ExtendedEuclid(a,m)
return D % m
def CheckEven(n):#偶数かどうかを判定。偶数だったらTrue
if n & 1 == 0:
return True
else:
return False
def CheckPrime(n):#素数かどうか判定。素数だったらTrue
if n == 2: return True
if n <= 1 or CheckEven(n):return False
d = (n - 1) >> 1
while CheckEven(n):
d >>= 1
for i in range(100):
a = random.randint(1,n-1)
t = d
y = pow(a,t,n)
while t != n -1 and y != 1 and y != n - 1:
y = pow(y,2,n)
t <<= 1
if y != n - 1 and CheckEven(t):
return False
return True
def GetRandomPrime(max):#max未満のランダムな素数を返す。存在しない場合は-1を返す
if(max <= 1):return -1
while(True):
rand = random.randint(2,max)
if(CheckEven(rand)):rand += 1
if(CheckPrime(rand)):break
return rand
def GenerateKeys(p,q):#二つの素数から秘密鍵と公開鍵を生成
N = p * q
L = LCM(p-1,q-1)
E = 0
D = 0
for i in range(2,L):
if math.gcd(i,L)==1:
E = i
break
D = Congruence(E,L)
return (E,N),(D,N)
def Encryption(plainText,publicKey):#公開鍵で暗号化
E,N=publicKey
plainInteger = [ord(char) for char in plainText]
encrytedInteger = [pow(i,E,N) for i in plainInteger]
encrytedText = ([str(i) for i in encrytedInteger])
return encrytedText
def Decryption(encryedText,privateKey):#秘密鍵で復号化
D,N = privateKey
encrytedInteger = [int(char) for char in encrytedText]
decrytedInteger = [pow(i,D,N) for i in encrytedInteger]
decrytedtext = ''.join([chr(char) for char in decrytedInteger])
return decrytedtext
if __name__ == '__main__':
digit = 100
p = GetRandomPrime(10**digit)
q = GetRandomPrime(10**digit)
publicKey,privateKey = GenerateKeys(p,q)
plainText = input("Please Text\n")
if plainText=="":
print("Error")
sys.exit()
encrytedText = Encryption(plainText,publicKey)
decrytedText = Decryption(encrytedText,privateKey)
print(f"PlainText:{plainText}\n")
print(f"PrivateKey:{publicKey}\n")
print(f"PrivateKey:{privateKey}\n")
print(f"CipherText:{encrytedText}\n")
print(f"DecryptedText:{decrytedText}\n")
実行結果
Please Text
ラーメンが食べたい
PlainText:ラーメンが食べたい
PublicKey:(7, 3256246514908134461560844416172948693059964695740362565531354626726793008293305382286137360139295703389105453434058728503812353652300630827782592235443720107723421545472681683724937965762001585166901)
PrivateKey:(37214245884664393846409650470547985063542453665604143606072624305449062951923490083270141258734807976814115935464608905363007422962129186323704137362511259854020596685072744440665469796949650034143, 3256246514908134461560844416172948693059964695740362565531354626726793008293305382286137360139295703389105453434058728503812353652300630827782592235443720107723421545472681683724937965762001585166901)
CipherText:['48247310478029687759617926041', '48762139823773858563840000000', '48031938219604998024439786017', '48517689398796624507678451611', '44168532975957272720125640704',
'140590950498374689006135359609375', '45306184782427361419232901769', '44645851508690182993911930527', '43968869292455023510757851136']
DecryptedText:ラーメンが食べたい
うまくいきました。
最後に
今回はほとんどを他の記事に頼った感じになってしまいましたが、目標の素数100桁が達成できました
100桁の素数を二つ生成しても１秒かかりません。
参考にさせていただいた記事に感謝を。では。