楕円曲線上のElGamal暗号のpythonプログラム

鍵生成

  1. 楕円曲線$E/F_p$と位数$l$のベーズポイント$G$を生成する．($p,l$は素数)
  2. 秘密鍵$x$を乱数にて生成し，$E$上で$Y=xG$を計算する．

ここで，秘密鍵$x$，公開鍵$E,G,Y$

暗号化

$m$を送信したいメッセージとする．

  1. $r$を乱数で生成し，$U=rG=(u_x,u_y)$を計算．
  2. 公開鍵$Y$を用いて，
    $V = xU =(v_x,v_y)$
    $c=v_x\oplus m$
    を計算．$\oplus$は排他的論理和．
  3. $(U,c)$を暗号文として，送信．

復号化

  1. 以下のように復号する．
    $V=xU=(v_x,v_y)$,
    $m=v_x\oplus c$

プログラム

# Random number
r = 3
# Secret Key
key = 3
# Base point
g = [2,2]
# Digits
l = 5
# y^2 = x^3 + ax +b
a = 0
b = 1

def Mod(x,y):
  if x < 0:
    x = x+y
  return x%y

def invMod(x,y):
  count = 1
  while True:
    tmp = x*count
    if tmp%y == 1:
      return count
    count += 1

def Ellipse(p,r):
    for _ in range(r):
        s = Mod(Mod((3*p[0]*p[0]+a),l)*invMod((2*p[1]),l),l)
        x = Mod(s*s-p[0]-p[0],l)
        y = Mod(s*(p[0]-x)-p[1],l)
    return [x,y]

def encrypt(G,Y, m):
    U =Ellipse(G,r)
    V =Ellipse(Y,r)
    # XOR
    c = V[1] ^ m
    return U,c

def decrypt(U, c, key):
    V = Ellipse(U,key)
    m = V[1] ^ c
    return m

def main():
    # Public Key
    Y = g
    Y = Ellipse(Y, key) 
    print("公開鍵：",[a,b], g,Y)
    # Pingwen
    message = 4
    print("平文：", message)
    # Encryption
    U,c = encrypt(g, Y, message)
    print("暗号文：",U,c)
    # Decryption
    decrypt_message = decrypt(U, c, key)
    print("復号化メッセージ", decrypt_message)
    
if __name__ == "__main__":
    main()
Tags: