ElGamal暗号の高速化法
通常のElGamal暗号は，pを素数としてpの剰余類上に構築し，暗号の安全性の根拠を離散対数問
題の困難性におきます。しかし，この暗号は，RSA暗号と同じように，合成数N=pqの剰余類上に構築し，素因数分解の困難性を安全性の根拠におく
ElGamal 暗号です。
N=pqの剰余類上に構築することにより，中国人剰余定理を用いて復号処理を高速化する方法を考えました。さらに，公開鍵の数を増やし，暗号化
の冪乗の指数を小さくしても安全であると考えられる方法を考えました。
これによりElGamal暗号が「世界最速の公開鍵暗号」となります。
また，「離散対数問題の解が求まれば，Ｎ＝pqを素因数分解できる」ことが示されます。したがって，その対偶
Ｎ＝pqの素因数分解できない ⇒ 離散対数問題の解は求まらない
が示されたことになり，素因数分解の困難性を安全性の根拠におくことになります。
鍵作成
・ 素数p，qを秘密鍵として N=pq を計算する。
・ 乱数a0 を生成する。
・ ap= mod p， aq= mod q とする。
自然数 mp，mq (mp≠mq)
を秘密鍵として，bp=apmp mod p と bq=aqmq
mod q を計算する。
中国人剰余定理により，b0 mod p = bp かつ b0
mod q = bq を満たすb0を求める。
次に，Nと同じ程度のbit数の大きな乱数n1，n2，…を選んで，a1=a0n1
，a2=a0n2 ， …と b1=b0n1
，b2=b0n2 ， … を計算する。
・ N，a0，a1 ，a2， …，b0，b1
，b2， … を公開鍵とする。
暗号処理
・ Nが2048bit程度の数の場合，合計が112bit 以上の自然数の乱数 r0，r1 ，r2，
…を生成する。
・ e=a0r0a1r1a2r2
… と f=b0r0b1r1b2r2
… を計算する。
・ ｆ から共通鍵を作成し，共通鍵暗号でメッセージMを暗号化してM’を得る。
・ e，M’ を受信者に送信する。
復号処理
・ ep= mod p と eq= mod q を求める。
・ xp=epmp mod p と xq=eqmq
mod q を計算する。
・ 中国人剰余定理により，x mod p = xp かつ x mod q = xq
を満たすxを求める。このとき，x=f が成り立つ。
・ xから共通鍵を作成し，共通鍵暗号でメッセージM’を復号してM を得る。
暗号化の高速化
公開鍵のペアをa0，a1 ，a2， …，b0，b1
，b2， …と増やせば，同じ安全性で暗号化の計算量を減らすことができる。しかし，公開鍵の数を増やすと鍵の配送に時間がかかるため，公開鍵のペアの数を
増やしたくない。
そこで，公開鍵をNとa0，a1 ，b0，b1
だけとしたとき， e=a0ra1sにおけるr，sの値は，
2048bitの暗号で112bit程度あれば安全であると考えられるが，112回の繰り返しでそれを実現する技法を示す。
flag(i)を0，1，2，3の値をとる2bitの乱数の列として，次のアルゴリズムによりeを求める。
LET e1=a0
LET e2=a1
FOR i=1 TO 112
LET x=e1*e2
LET e1=e2
IF flag(i)=0 OR flag(i)=1 THEN
LET e2=x
ELSEIF flag(i)=2 THEN
LET e2=x*e2
ELSE
LET e2=x*x
END IF
NEXT i
処理速度
RSA暗号の暗号化処理では，冪乗の指数の値は3か65537を使うため，計算量は極めて少ない。また，RSA暗号では，復号に中国人剰余定理を用いるた
め，計算量はElGamal暗号の復号の1/4となる。
一方，この暗号では，指数mp，mq を極端に小さくとれば，計算量は極めて少ない。
暗号化では，「暗号化の高速化法」を用いれば，2048bitの暗号で冪乗の計算量を112bit程度に抑えられるから，通常のElGamal暗号に対す
る計算量の比は
112/2048≓0.055倍となる。さらに，暗号化の冪乗の指数の合計を，3072bitの暗号では128bit程度に，7680bitの暗号では
192bit程度に抑える。
以下に，
通常のElGamal暗号の復号の冪乗の計算量を1として，冪乗の計算量の見積もりを示します。
冪乗の計算量の見積もり
| 暗号強度 |
法のbit数 |
RSA暗号 |
ElGamal暗号 |
高速ElGamal暗号 |
| 暗号化 |
復号 |
暗号化 |
復号 |
暗号化 |
復号 |
| 112bit |
2048bit |
僅少 |
0.25 |
2 |
1 |
0.11 |
僅少 |
| 128bit |
3072bit |
僅少 |
0.84 |
6.8 |
3.4 |
0.28 |
僅少 |
| 192bit |
7680bit |
僅少 |
13.2 |
105 |
53 |
2.6 |
僅少 |
ただし，RSA暗号や署名では，法とする数より小さい数を掛けるため，計算量は上記より減少する。
また，積の計算量は法のbit数の2乗で見積もってい
るが，Karatsuba法を用いれば計算量は減少する。その場合でも，同じ暗号強度で比べれば，各暗号の計算量の比は変わらない。
安全性について
離散対数問題 ar=b2 を解けて，2つの偶数の解 r1，r2が
求まったとする。このとき，α＝ar1/2，β＝ar2/2
は方程式 x2＝b2 の解であるから，α＋βとN および α－βとN
の最大公約数を求めれば，条件によりN＝pqの素因数が求まる。これにより
離散対数問題の解が求まる ⇒ N＝pqの素因数分解ができる
が示されたことになる。したがって，その対偶
Ｎ＝pqの素因数分解できない ⇒ 離散対数問題の解は求まらない
が示されたことになり，素因数分解の困難性を安全性の根拠におくことになる。
解説 ElGamal暗号の高速化 ElGamal2.pdf
記述の欠陥を見つけられた場合は，メールにて以下にお知らせ頂ければ幸
甚に存じます。(メールアドレスは，スパムメール対策のために画像になっています。)
暗号化と復号のコード
以下に，十進BASICでの暗号化と復号のコードと出力結果を示す。
!ElGamal暗号
LET p=8423 !安全素数
LET q=7823
LET pq=p*q
LET a=314159 !公開鍵
LET n=1234567
LET b=ruijyou(a,n,pq)
LET b=MOD(b^2,p*q)
CALL dlog(a,b,pq,s,t)
LET x=ruijyou(a,s/2,pq)
LET y=ruijyou(a,t/2,pq)
PRINT gcd(MOD(x+y,pq),pq)
PRINT gcd(MOD(x-y,pq),pq)
END
EXTERNAL FUNCTION GCD(a,b) !互除法
DO
LET r=MOD(a,b)
IF r=0 THEN EXIT DO
LET a=b
LET b=r
LOOP
LET GCD=b
END FUNCTION
EXTERNAL SUB dlog(a,b,N,s,t) !離散対数
LET t=a
LET flag=0
FOR i=2 TO 2*N
LET t=MOD(a*t,N)
IF t=b THEN
PRINT a;b;i;"あった"
IF MOD(i,2)=0 THEN
LET flag=flag+1
IF flag=1 THEN LET s=i
IF flag=2 THEN
LET t=i
EXIT FOR
END IF
END if
END if
NEXT I
IF flag=0 THEN PRINT a;b;"なかった"
END SUB
EXTERNAL FUNCTION ruijyou(a,r,N) !累乗の計算
LET s=1
FOR i=1 TO r
LET s=MOD(s*a,N)
NEXT I
LET ruijyou=s
END function
314159 16489241 2469134 あった
314159 16489241 35407576 あった
8423
7823
以下に，暗号化と復号のコードと出力結果を示す。
!ElGamal暗号
LET p=8423 !安全素数
LET q=7823
LET pq=p*q
LET a=3141593 !公開鍵
LET n=1234567
LET b=ruijyou(a,n,pq)
LET a1=MOD(a,p)
LET a2=MOD(a,q)
LET m1=2 !秘密の乱数
LET m2=3
LET c1=ruijyou(a1,m1,p)
LET c2=ruijyou(a2,m2,q)
LET c=Chinese(c1,c2,p,q) !公開鍵を作成
LET d=ruijyou(c,n,pq)
LET m=Chinese(m1,m2,p-1,q-1) !周期から指数を求める。これで求まらない場合もある。
PRINT m
PRINT ruijyou(a,m,pq);c !一致を確認
PRINT
CALL dlog(a,c,pq)
CALL dlog(b,c,pq)
CALL dlog(a,d,pq)
CALL dlog(b,d,pq)
print
LET e=Fibonacci(a,b,20,2236067977499,pq)
LET f=Fibonacci(c,d,20,2236067977499,pq)
LET x1=ruijyou(MOD(e,p),m1,p)
LET x2=ruijyou(MOD(e,q),m2,q)
LET x=Chinese(x1,x2,p,q)
PRINT f;x !一致を確認
END
EXTERNAL SUB dlog(a,b,N) !離散対数
LET t=a
LET flag=0
FOR i=2 TO N
LET t=MOD(a*t,N)
IF t=b THEN
LET flag=1
PRINT a;b;i;"あった"
END if
NEXT I
IF flag=0 THEN PRINT a;b;"なかった"
END SUB
EXTERNAL FUNCTION ruijyou(a,r,N) !累乗の計算
LET s=1
FOR i=1 TO r
LET s=MOD(s*a,N)
NEXT I
LET ruijyou=s
END function
EXTERNAL FUNCTION Chinese(a1,a2,p,q) !中国人剰余定理
CALL ExGCD(p,q,s,t,c)
LET x=a1*t*q+a2*s*p
LET Chinese=MOD(x/c,p*q/c)
End function
EXTERNAL SUB ExGCD(a,b,s,t,c) !拡張ユークリッドの互除法（再帰版）
IF b=0 THEN
LET s=1
LET t=0
LET c=a
ELSE
LET q=INT(a/b)
LET r=MOD(a,b)
CALL ExGCD(b,r,s1,t1,c)
LET s=t1
LET t=s1-t1*q
END IF
END SUB
EXTERNAL FUNCTION Fibonacci(a,b,bit,r,n) !漸化式
LET e1=a
LET e2=b
FOR i=1 TO bit
LET x=MOD(e1*e2,n)
LET e1=e2
LET flag=MOD(r,4)
LET r=INT(r/4)
IF flag=0 OR flag=1 THEN
LET e2=x
ELSEIF flag=2 THEN
LET e2=mod(x*e2,n)
else
LET e2=mod(x*x,n)
end if
next i
LET Fibonacci=x
END FUNCTION
5983833
20408025 8962976
3141593 8962976 なかった
52353760 8962976 なかった
3141593 48352149 なかった
52353760 48352149 なかった
42728613 42728613