離散対数問題について
概要
- 素数を使用した暗号の基礎
- 整数, \(q\), ((k))を選択
- \(q\)はとても大きな素数が理想
\(m = b^k \mod q\)
- \(m\); 有限巡回群
- \(b\); 生成元
-
\(q\); 法
- \(b\), \(q\), \(m\)がわかったとしても、\(k\)を満たす数字を高速に求める方法は見つかっていない
- これを利用して各種暗号が作成される
ElGamal暗号
- 大きな素数\(q\)を選択する
- 整数\(k\)を適当に選ぶ
- \(h = b^k\)とする
- 公開鍵は\( q,b,h \)となる
- 秘密鍵は\(k\)となる
暗号化
- 整数\(r\)を適当に選ぶ
- \(c_1 = b^r\)
- \(c_2 = m \times h^r\)
- \(m\)は暗号化したい情報
- \( c_1, c_2 \)が暗号文
復号
\[m = \frac{c2}{c_1^x} = m \times \frac{ (g^x)^r }{ (g^r)^x }\]pythonによる実例
# ElGamal暗号
p = 524287 # 素数、法
b = random.randint(1, p) # 基数
h = pow(b, 578, p)
print("秘密鍵", 578)
print("公開鍵", p, b, h)
# 暗号化
message = 123 # 暗号化したい情報
r = random.randint(1, p)
c1 = pow(b, r, p)
c2 = message * pow(h, r, p)
crypt = (c1, c2)
print(crypt) # (1958, 14815596)
# 復号
assert c2 // pow(c1, 578, p) == message