RSA暗号化
RSA暗号（RSAあんごう）とは、桁数が大きい合成数の素因数分解が現実的な時間内で困難であると信じられていることを安全性の根拠とした公開鍵暗号の一つである。暗号とデジタル署名を実現できる方式として最初に公開されたものである。
Wikipedia引用 https://ja.wikipedia.org/wiki/RSA%E6%9A%97%E5%8F%B7
:::note info
今回はpythonを使用します。
:::
まず素数pとqを用意します。
import random as rnd
prime = []
divisor = []
for Number2 in range(1,1000,1):
for Number1 in range(1,Number2+1,1):
if (Number2 / Number1) % 1 == 0:
divisor.append(Number1)
if len(divisor) == 2:
prime.append(Number2)
divisor = []
p = prime[rnd.randint(0,len(prime))]
q = prime[rnd.randint(0,len(prime))]
これは1000までの数字で割ってその数字の約数が2つなら約数リストに入れて、pとqはその中のどれかをランダムで指定しています。
一応こんなめんどくさいことしなくてもこんなのでもいけます。
import random as rnd
prime = []
for i in range(1,1000):
t = False
for j in range(2,i):
if i%j == 0:
t = True
if t == False:
prime.append(i)
でもいけます。正直言ってこっちのほうが楽です。
さあ、次いきましょう次は(素数)$*$(素数)=Nです。
これは簡単ですね
N = p*q
です。その次は理屈は全体的にわかってはいませんが。(p-1)(q-1)のsを作るみたいです。
s = (p-1)*(q-1)
ですね。どんどんいきましょう。次はs,eの最大公約数が1になるeを探さなければいけません。このときfor文を使うと安直すぎるのでランダムで、できるだけ分かりづらくしてみました。今回は関数を使用します。
def GCD(m,n):
x = max(m,n)
y = min(m,n)
if x % y == 0:
return y
else:
while x%y!=0:
z = x%y
x = y
y = z
else:
return z
while GCD(s,e) != 1:
e = rnd.randint(0,1000)
になります。GCDは(Greatest Common Divisor)の略です。
軽く説明すると例えば22と11の最大公約数は11です。
maxはその中の一番大きい数字で、minは一番小さい数字です。それをわって答えあまりが出ないのならばyの倍数ということになるのでyを戻します。
逆に倍数ではないとき例えば24,14とかです。
その場合その式に当てはめると、24%14は10です。
zは10になり、xは11になり、yは10になります。
そして11%10は1です。
zは1になり、xは10になり、yは1です。
.
.
.
となります。それは大まかな説明です。
次にed%s=1になるdの値を求めます。
dはランダムでやったら掛かりそうなのでこれはwhile文で一から試します。
while (e*d)%s!=1:
d = d + 1
こうですね。至ってシンプルです。
ここまでで、p,q,s,N,e,dが揃いました。
N,eは公開鍵です。暗号化をした文章ファイルを渡そうとしている人に送ってください。これはあくまで暗号化専用の鍵です。
dは秘密鍵です。これは解読専用の値です。なのでこれがないと盗聴したひとは困惑します。なのでdは絶対に公開しないでください。
次に文字を打ったものをリストに変換し、Unicodeで数値に変換します。
コードはこのとおりです。
wp = input("word:")
wpl = list(wp)
wps = []
for i in range(0,len(wpl)):
wps.append(ord(wpl[(len(wpl)-1)-i]))
print("word number:",wps)
です。wpに打った文字を一文字一文字リストに入れていき、それを数値化し、一番目のものを数値化して一番うしろに持ってくると変な感じになるのであえてiを引くことで逆からしています。
次にお待ちかね数値を暗号化する方法です。これは$c=(M^e)mod(N)$で暗号化します。
for j in range(0,len(wps)):
c = 1
for i in range(0,e):
c = (c*int(wps[(len(wps)-1)-j]))%N
cwps.append(c)
print("encoding word number:",cwps)
剰余の定理でさっきのやつを限られたスペースで計算しています。
今回は詳しく触れません。
あとは解読ですね。今度はここでdを使います。
cpwn = []
for j in range(0,len(cwps)):
cp = 1
for i in range(0,d):
cp = (cp*int(cwps[(len(cwps)-1)-j]))%N
cpwn.append(cp)
print("ward number:",cpwn)
w = ""
for i in range(0,len(cpwn)):
w = chr(cpwn[i]) + w
print("answer:"+w)
今度は$c=(M^e)mod(N)$に対し、$cp=(M^d)mod(N)$的な感じでやっています。原理はよくわかっていません。
最後に全体のコードを載ってけ置きます。
import random as rnd
prime = []
divisor = []
for Number2 in range(1,1000,1):
for Number1 in range(1,Number2+1,1):
if (Number2 / Number1) % 1 == 0:
divisor.append(Number1)
if len(divisor) == 2:
prime.append(Number2)
divisor = []
e = 100
d = 0
def GCD(m,n):
x = max(m,n)
y = min(m,n)
if x % y == 0:
return y
else:
while x%y!=0:
z = x%y
x = y
y = z
else:
return z
p = prime[rnd.randint(0,len(prime))]
q = prime[rnd.randint(0,len(prime))]
N = p*q
s = (p-1)*(q-1)
while GCD(s,e) != 1:
e = rnd.randint(0,1000)
while (e*d)%s!=1:
d = d + 1
print("p=" + str(p) + " q=" + str(q) + " N=" + str(N) + " s=" + str(s) + " e=" + str(e) + " d=" + str(d))
print("send N="+str(N)+" e="+str(e))
print("important d="+str(d))
wp = input("word:")
wpl = list(wp)
wps = []
cwps = []
for i in range(0,len(wpl)):
wps.append(ord(wpl[(len(wpl)-1)-i]))
print("word number:",wps)
for j in range(0,len(wps)):
c = 1
for i in range(0,e):
c = (c*int(wps[(len(wps)-1)-j]))%N
cwps.append(c)
print("encoding word number:",cwps)
cpwn = []
for j in range(0,len(cwps)):
cp = 1
for i in range(0,d):
cp = (cp*int(cwps[(len(cwps)-1)-j]))%N
cpwn.append(cp)
print("ward number:",cpwn)
w = ""
for i in range(0,len(cpwn)):
w = chr(cpwn[i]) + w
print("answer:"+w)