単一換字式暗号実装
Discussion
単一換字式暗号実装
この暗号を実装したのですが、この暗号はどういった場面で応用されるのでしょうか？
一応、実装内容を提示させて頂きます。
手順
鍵生成
1. 素数pとqを選ぶ
2. n=pqとphi=gcd(p−1,q−1)を計算する。phi=オイラー関数 3. phiと互いに素でかつphiより小さい数eを選ぶ。
4. d=1/e mod (phi)を計算する。秘密鍵をdを公開鍵e,Nとする。 暗号化(暗号文は数字にします。)
5. c=m^e mod (N)を計算して、cを出力する。
復号
6. m=c^d mod (N)を計算して、mを出力する。
ライブラリ
import random
import math
素数判定と取得
十分に大きい素数p,qを求めます。
ここでは11からNまでの素数をランダムに生成します。 S=2に関しては素数判定の際の方法で割り切れるかを判定しています。そして次の素数を判定します。
def sympy_prime( N ):
while True:
n = (random.randint( 11, N ))
s = 2
flag = True
while s*s <= n and flag:
if n % s == 0:
flag = False
s += 1
if flag:
return n
鍵生成
Kをセキュリティパラメーターとします。 オイラー関数ではpが素数であるとき𝜑(p)=p−1であること、および、p,qが互いに素であるとき(共通の素因数を持たない) 𝜑(pq)=𝜑(p)𝜑(q)が成り立ちます。
その次に、𝜑(N)と互いに素であるe(1<e<𝜑(N))をランダムに生成します。
次にed≡1 mod 𝜑(N)となるdを求めます。この値を求めるには、拡張ユークリッドの互除法を使用します。
d=1/e mod (phi)を計算する。
そしてdが求まります。
dが秘密鍵、N,eが公開鍵となります。
def generate_keys( k ):
b = 1 << int( k/2 )
e = 7
flag = True
while flag:
p = sympy_prime( b )
q = p
while p == q:
q = sympy_prime( b )
N = p * q
phi = ( p-1 ) * ( q-1 )
d = gcd( phi, e )
if phi%e != 0:
flag = False
return ( N, e ), d
暗号化
公開鍵で暗号化をします。
具体的に平文をmとします。
そしてC ≡m^e mod (N)を求めます。
暗号化時Cは、 m^eをNで割ったときの余りが送りたいメッセージmを暗号化して送る数字になります。
複号化
秘密鍵で複合化をします。
暗号化された𝑐を復号するには、m′≡c^d mod (N)を求めたものが復号された値になります。
def encrypt( m, public_key ):
cipher = []
N, e = public_key
for l in m:
c = ord(l)
for s in range( e-1 ):
c = ( c*ord(l) ) % N
cipher.append( c )
return cipher
def decrypt( c, public_key, private_key ):
decode = ''
N = public_key[0]
for c1 in c:
m = c1
for s in range( private_key-1 ):
m = ( m*c1 ) % N
decode += chr( m )
return decode
if __name__ == '__main__':
public_key, private_key = generate_keys(8)
plain_text = 'sato'
cipher = encrypt( plain_text, public_key )
decode = decrypt( cipher, public_key, private_key )
print( 'N =', public_key[0] )
print( 'e =', public_key[1] )
print( 'd =', private_key, '\n' )
print( 'plain → cipher → decode' )
for s in range( len(plain_text) ):
print( plain_text[s], ord(plain_text[s]), '(', format(ord(plain_text[s]), '08b'), ')→',
cipher[s], '(', format(cipher[s], '08b'), ')→',
ord(decode[s]), '(', format(ord(decode[s]),'08b'), ')', decode[s] )
実装結果:satoが復号化されました。
N = 143
e = 7
d = 103
plain → cipher → decode
s 115 ( 01110011 )→ 80 ( 01010000 )→ 115 ( 01110011 ) s
a 97 ( 01100001 )→ 59 ( 00111011 )→ 97 ( 01100001 ) a
t 116 ( 01110100 )→ 129 ( 10000001 )→ 116 ( 01110100 ) t
o 111 ( 01101111 )→ 45 ( 00101101 )→ 111 ( 01101111 ) o
