二次整數環上的ElGamal密碼體制和簽名方案

董學東，張妍

1.大連大學信息工程學院，遼寧大連 116622

2.遼寧師范大學數學學院，遼寧大連 116029

二次整數環上的ElGamal密碼體制和簽名方案

董學東1，張妍2

1.大連大學信息工程學院，遼寧大連 116622

2.遼寧師范大學數學學院，遼寧大連 116029

1 引言

ElGamal公鑰密碼體制和簽名方案是1985提出的[1]，ElGamal簽名方案的變型被美國國家標準技術研究所采納為數字簽名算法（Digital Signature Al，DSA），它的安全性主要基于有限域上離散對數問題的難解性。文獻[2]提出了有限域上多項式形式的ElGamal體制。文獻[3]提出了基于四元整數環的RSA公鑰密碼方案。受到這些啟發，本文利用文獻[4]的一個結果提出了二次數域的代數整數環上的ElGamal公鑰密碼體制和ElGamal簽名方案，其安全性基于代數整數環上離散對數問題的難解性。

2 預備知識

設m是沒有平方因子的整數并且m≠1，又設

3 ElGamal公鑰密碼體制

3.1 密鑰生成的過程

3.2 加密過程

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

3.3 解密過程

3.4 安全性分析

3.5 實例

就可以得到明文ω。

4 ElGamal簽名方案

4.1 系統初始化

設H是一個安全的單向Hash函數，其函數值屬于正整數集合。

4.2 簽名過程

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

4.3 驗證過程

4.4 安全性分析

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

5 結束語

本文提出了二次數域的代數整數環上的ElGamal公鑰密碼體制和ElGamal簽名方案。加密、解密的計算過程相對簡單，其安全性基于離散對數問題的難解性。

[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]張青坡，陳彩云，陳魯生，等.有限域上多項式形式的ElGamal體制及數字簽名方案[J].通信學報，2005，26（5）：69-72.

[3]汪麗，邢偉，徐光忠.基于四元整數的ElGamal公鑰密碼體制[J].計算機應用，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

提出了二次數域的代數整數環上的ElGamal公鑰密碼體制和ElGamal簽名方案，其安全性基于離散對數問題的困難性。

ElGamal公鑰密碼；簽名方案；代數整數環

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.

國家自然科學基金（No.10171042）；遼寧省教育廳高校科研項目（No.L2010234）。

董學東（1961—），男，博士，教授，主要研究領域為編碼密碼學；張妍（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