董學(xué)東，張妍

1.大連大學(xué)信息工程學(xué)院，遼寧大連 116622

2.遼寧師范大學(xué)數(shù)學(xué)學(xué)院，遼寧大連 116029

二次整數(shù)環(huán)上的ElGamal密碼體制和簽名方案

董學(xué)東1，張妍2

1.大連大學(xué)信息工程學(xué)院，遼寧大連 116622

2.遼寧師范大學(xué)數(shù)學(xué)學(xué)院，遼寧大連 116029

1 引言

ElGamal公鑰密碼體制和簽名方案是1985提出的[1]，ElGamal簽名方案的變型被美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究所采納為數(shù)字簽名算法（Digital Signature Al，DSA），它的安全性主要基于有限域上離散對(duì)數(shù)問(wèn)題的難解性。文獻(xiàn)[2]提出了有限域上多項(xiàng)式形式的ElGamal體制。文獻(xiàn)[3]提出了基于四元整數(shù)環(huán)的RSA公鑰密碼方案。受到這些啟發(fā)，本文利用文獻(xiàn)[4]的一個(gè)結(jié)果提出了二次數(shù)域的代數(shù)整數(shù)環(huán)上的ElGamal公鑰密碼體制和ElGamal簽名方案，其安全性基于代數(shù)整數(shù)環(huán)上離散對(duì)數(shù)問(wèn)題的難解性。

2 預(yù)備知識(shí)

設(shè)m是沒(méi)有平方因子的整數(shù)并且m≠1，又設(shè)

3 ElGamal公鑰密碼體制

3.1 密鑰生成的過(guò)程

3.2 加密過(guò)程

假設(shè)用戶A發(fā)送消息給用戶B，用戶A獲取用戶B的公鑰(α，γ)，將明文消息ω寫(xiě)成a+bδm，0≤a，b＜pn，用戶A隨機(jī)地選取k，計(jì)算c1=αk(modpn)，c2=γkω(modpn)，于是得到密文(c1，c2)，將其發(fā)送給用戶B。

3.3 解密過(guò)程

3.4 安全性分析

3.5 實(shí)例

就可以得到明文ω。

4 ElGamal簽名方案

4.1 系統(tǒng)初始化

設(shè)H是一個(gè)安全的單向Hash函數(shù)，其函數(shù)值屬于正整數(shù)集合。

4.2 簽名過(guò)程

假設(shè)用戶A想對(duì)一個(gè)消息ω簽名，首先計(jì)算消息ω離散值u=H(ω)其次，選取一個(gè)秘密的隨機(jī)數(shù)k，(k，p)=1，計(jì)算ζ≡αk(modpn)，s≡k-1(u-h)(modpn-1)，這里k-1是指k模pn-1的逆，簽署的消息是三元組(ω，s，ζ)。

4.3 驗(yàn)證過(guò)程

4.4 安全性分析

假定系統(tǒng)攻擊者想對(duì)消息偽造簽名，他就必須獲得秘密數(shù)h≡ks-u(modpn-1)。系統(tǒng)攻擊者選擇一個(gè)值u和ζ≡αk(modpn)，然后試圖從關(guān)系式αu≡γζs(modpn)中找到相應(yīng)的s進(jìn)而計(jì)算秘密數(shù)h≡ks-u(modpn-1)，那么他必須計(jì)算離散對(duì)數(shù)logζγ-1αu，而這是公認(rèn)的數(shù)學(xué)難題。需要說(shuō)明的是，在計(jì)算簽名時(shí)所使用的隨機(jī)值k不能泄露。如果泄露出去，那么計(jì)算h≡ks-u(modpn-1)就是容易的事。一旦h被泄露，系統(tǒng)攻擊者就能隨意地偽造簽名了。對(duì)于兩個(gè)不同的消息簽名要使用不同的k值，如果在兩個(gè)不同的消息簽名中使用同一個(gè)k，則有s1≡k-1(u1-h)(modpn-1)，s2≡k-1(u2-h)(modpn-1)，于是以k為未知量的同余方程k(s1-s2)≡u(píng)1-u2(modpn-1)有(s1-s2，pn-1)個(gè)解。這(s1-s2，pn-1)個(gè)解就是秘密的隨機(jī)數(shù)k的候選值。從等式ζ≡αk(modpn)檢測(cè)出唯一正確的那一個(gè)k，再?gòu)膆≡(ks1-u1)≡(ks2-u2)(modpn-1)就得到了密鑰h，他就可以在任何文檔上偽造簽名了。

5 結(jié)束語(yǔ)

本文提出了二次數(shù)域的代數(shù)整數(shù)環(huán)上的ElGamal公鑰密碼體制和ElGamal簽名方案。加密、解密的計(jì)算過(guò)程相對(duì)簡(jiǎn)單，其安全性基于離散對(duì)數(shù)問(wèn)題的難解性。

[1]ElGamal T.A public key cryptosystem and a signature scheme based on discrete logarithms[J].IEEE Transactions on Information Theory，1985，31：469-472.

[2]張青坡，陳彩云，陳魯生，等.有限域上多項(xiàng)式形式的ElGamal體制及數(shù)字簽名方案[J].通信學(xué)報(bào)，2005，26（5）：69-72.

[3]汪麗，邢偉，徐光忠.基于四元整數(shù)的ElGamal公鑰密碼體制[J].計(jì)算機(jī)應(yīng)用，2008，28（5）：1156-1157.

[4]Dong X，Cheong B，Erry G，et al.Groups of algebraic integers used for coding QAM signals[J].IEEE Transactions on Information Theory，1998，44（5）：1848-1860.

DONG Xuedong1,ZHANG Yan2

1.College of Information Engineering,Dalian University,Dalian,Liaoning 116622,China
2.School of Mathmatics,Liaoning Normal University,Dalian,Liaoning 116029,China

A new ElGamal public key cryptosystem and digital signature scheme are presented over algebraic integral rings of quadratic number fields.Their securities depend on difficulty of discrete logarithmic computations in the algebraic integral rings.

ElGamal Public Key Cryptosystem（PKC）;digital signature scheme;algebraic integral ring

提出了二次數(shù)域的代數(shù)整數(shù)環(huán)上的ElGamal公鑰密碼體制和ElGamal簽名方案，其安全性基于離散對(duì)數(shù)問(wèn)題的困難性。

ElGamal公鑰密碼；簽名方案；代數(shù)整數(shù)環(huán)

A

TP309.7

10.3778/j.issn.1002-8331.1201-0031

DONG Xuedong,ZHANG Yan.ElGamal cryptosystem and digital signature scheme over integral rings of quadratic number fields.Computer Engineering and Applications,2013,49（19）：73-74.

國(guó)家自然科學(xué)基金（No.10171042）；遼寧省教育廳高?？蒲许?xiàng)目（No.L2010234）。

董學(xué)東（1961—），男，博士，教授，主要研究領(lǐng)域?yàn)榫幋a密碼學(xué)；張妍（1978—），女，博士研究生，講師。E-mail：dongxu-edong@dl.cn

2012-01-04

2012-03-01

1002-8331（2013）19-0073-02

CNKI出版日期：2012-06-01http://www.cnki.net/kcms/detail/11.2127.TP.20120601.1458.053.html