エルガマル暗号を実装してみる
こんにちは。今回は久しぶりに暗号の話に戻ります。公開鍵暗号方式の一つであるエルガマル暗号を取り上げます。この数回は初等整数論を迷走していましたが、前回の原始根を用いて鍵を生成する暗号のアルゴリズムということで紹介していきます。
エルガマル暗号とは
エルガマル暗号は、エジプトの暗号学者エルガマルさんが公表した暗号です。Wikipediaのページですが、エルガマルさんのページへのリンクを貼っておきます。
https://en.wikipedia.org/wiki/Taher_Elgamalと公表した人を紹介したところで仕方ないので、アルゴリズムを整理していきます。
エルガマル暗号に用いる鍵生成アルゴリズム
次のアルゴリズムにより、エルガマル暗号に用いる鍵を生成します。
- \(k\)ビットのランダムな素数\(p\)と、法\(p\)における原始根\(g(1 \lt g \lt p)\)を選びます。（調べた文献によって、「\(p\)は大きな素数をランダムに選ぶ」としている場合も多く見られましたが、今回は\(k\)ビットとしました）
- \(0 \leq x \leq p-2\)の範囲からランダムに整数\(x\)を選びます。
- \(y \equiv g^x \bmod p\)を計算します。
- 公開鍵を\( (p,g,y)\)、秘密鍵を\(x\)とするとき、これらがエルガマル暗号の鍵になります。
離散対数問題
上のアルゴリズムでは指数と剰余の計算で鍵を作っています。このような計算で秘密鍵が見つけられてしまう心配がありますが、困難であることを厳密さは欠きますが触れておきたいと思います。
例として素数を\(p=11\)とします。このとき、原始根のうちの1つ\(g=2\)を選びます。次にランダムに\(x=8\)を選びます。
このとき、\(2^8 = 256\)は簡単に計算できます。それにより、\(2^8 \equiv 256 \equiv 4 \bmod 11\)となり、\(y=3\)が求められます。\(y=3\)を求めるのは\(x=8\)を知っていれば簡単です。
逆に、\(y \equiv 2^x \bmod 11\)となる\(x\)を求めるのはどうでしょうか。
\[2^1 \equiv 2 \bmod 11\]
\[2^2 \equiv 4 \bmod 11\]
\[2^3 \equiv 8 \bmod 11\]
\[2^4 \equiv 5 \bmod 11\]
\[2^5 \equiv 10 \bmod 11\]
\[2^6 \equiv 9 \bmod 11\]
\[2^7 \equiv 7 \bmod 11\]
\[2^8 \equiv 3 \bmod 11\]
\[2^9 \equiv 6 \bmod 11\]
\[2^{10} \equiv 1 \bmod 11\]
のように位数が\(p-1\)で解は必ず存在するのですが、単純に増加したり減少したりするわけではなく値が不規則に変化するため、\(x\)を求めるのは難しいと考えられます。\(p=11\)程度ならば、しらみつぶしに調べれば求められますが、素数\(p\)の値が大きければ困難になります。
\(y=g^x\)の解は\(x = \log_{g} y\)で容易に求められますが、\(y \equiv g^x \bmod p\)の解を求めるのは困難です。この方程式の解\(x\)を求める問題を離散対数問題といいます。離散対数問題により、鍵を公開して容易に暗号化できても、秘密鍵がわからなければ復号するのは難しいということになります。
暗号化するアルゴリズム
さて、暗号のアルゴリズムに戻ります。次に暗号化するアルゴリズムです。平文を\(m(0 \lt m \lt p)\)として、公開鍵\((p,g,y)\)を用いて暗号化します。
- \( 0 \leq r \leq p-2\)から整数\(r\)をランダムに選びます。
- \(c_1 \equiv g^r \bmod p\)、\(c_2 \equiv my^r \bmod p\)を計算します。
- これにより計算された組\((c_1,c_2)\)が暗号文になります。
復号アルゴリズム
暗号文の組\((c_1,c_2)\)、公開鍵のうち\(p\)、秘密鍵\(x\)を用いて、次により復号結果\(m’\)が得られます。
- \(m’ \equiv c_2{c_1}^{p-1-x} \bmod p\)により求められた\(m’\)が復号結果になります。
エルガマル暗号を実装する
毎度のPythonで実装します。原始根を求めるには、ライブラリsympyを用いることにします。
import random
import sympy
def code( word ):
result = []
for letter in word:
result.append( ord(letter) )
return result
def make_prime( M, N ):
while True:
n = random.randint( M, N )
i = 2
flag = True
while i*i <= n and flag:
if n % i == 0:
flag = False
i += 1
if flag:
return n
def calc_mod( a, b, p ):
result = 1
for i in range(b):
result = ( result * a ) % p
return result
def key_generate( k ):
a = 1 << (k-1)
b = 1 << k
p = make_prime( a, b )
g = sympy.primitive_root(p)
x = random.randint( 0, p-1 )
y = calc_mod( g, x, p )
return ( p, g, y ), x
def encrypt( m, pk ):
cipher = []
p, g, y = pk
r = random.randint( 0, p-1 )
c1 = calc_mod( g, r, p )
for l in m:
c2 = ( ord(l) * calc_mod( y, r, p ) ) % p
cipher.append( c2 )
return ( c1, cipher )
def decrypt( c, pk, sk ):
decode = ''
c1, c2 = c
p, g, y = pk
x = sk
d = calc_mod( c1, p-1-x, p )
for cc in c2:
m = ( cc * d ) % p
decode += chr( m )
return decode
if __name__ == '__main__':
pk, sk = key_generate(8)
plain_text = 'You can always become better.'
plain_code = code( plain_text )
cipher = encrypt( plain_text, pk )
decode = decrypt( cipher, pk, sk )
decode_code = code( decode )
print( '公開鍵 ( p, g, y ) = ', pk )
print( '秘密鍵 x = ', sk )
print( '平文（文字コード） = ', plain_code )
print( '暗号 ( c1, c2 ) = ', cipher )
print( '復号（文字コード） = ', decode_code )
print( "復号 m'=", decode )
実行結果は次になります。
公開鍵 ( p, g, y ) = (167, 5, 44)
秘密鍵 x = 108
平文（文字コード） = [89, 111, 117, 32, 99, 97, 110, 32, 97, 108, 119, 97, 121, 115, 32, 98, 101, 99, 111, 109, 101, 32, 98, 101, 116, 116, 101, 114, 46]
暗号 ( c1, c2 ) = (111, [96, 146, 23, 12, 58, 99, 83, 12, 99, 124, 149, 99, 108, 64, 12, 162, 17, 58, 146, 20, 17, 12, 162, 17, 127, 127, 17, 1, 59])
復号（文字コード） = [89, 111, 117, 32, 99, 97, 110, 32, 97, 108, 119, 97, 121, 115, 32, 98, 101, 99, 111, 109, 101, 32, 98, 101, 116, 116, 101, 114, 46]
復号 m'= You can always become better.
乱数を用いているので、もう一度実行してみます。
公開鍵 ( p, g, y ) = (241, 7, 217)
秘密鍵 x = 152
平文（文字コード） = [89, 111, 117, 32, 99, 97, 110, 32, 97, 108, 119, 97, 121, 115, 32, 98, 101, 99, 111, 109, 101, 32, 98, 101, 116, 116, 101, 114, 46]
暗号 ( c1, c2 ) = (208, [71, 140, 115, 188, 190, 118, 104, 188, 118, 32, 187, 118, 18, 43, 188, 154, 21, 190, 140, 68, 21, 188, 154, 21, 79, 79, 21, 7, 210])
復号（文字コード） = [89, 111, 117, 32, 99, 97, 110, 32, 97, 108, 119, 97, 121, 115, 32, 98, 101, 99, 111, 109, 101, 32, 98, 101, 116, 116, 101, 114, 46]
復号 m'= You can always become better.
乱数を用いても正しく暗号化・復号できる理由にも触れた方がよさそうに思いますが、割愛することにします。
とはいえ、暗号の話は南京錠と鍵に喩えられますが、いつもお茶を濁して済ませているような気がしています。以前取り上げたバーナム暗号のように共通鍵で暗号化と復号ができたり、今回のエルガマル暗号やＲＳＡ暗号のように公開鍵により暗号化できるけれど復号ができなかったり、というようなことを簡単な数値を用いた計算でよいので、経験できないかと思っています。
・・・やっぱり難しいのかな・・・
今回はこれでおしまいにします。それではまた。