《椭圆曲线单向消息恢复签名》由会员分享，可在线阅读，更多相关《椭圆曲线单向消息恢复签名（3页珍藏版）》请在金锄头文库上搜索。
1、计算机科学2 0 0 2 V 0 1 2 9 N 9 - 8 ( 增刊) 椭圆曲线单向消息恢复签名 D i r e c t e dM e s s a g eR e c o v e r yS i g n a t u r eS c h e m eB a s e do nE l l i p t i cC u r v e 韩益亮杨晓元武光明孙军 ( 武警工程学院电子技术系西安7 1 0 0 8 6 ) A b s t r a c t D i g i t a lS i g n a t u r ei s ak e yt e c h n o l o g yi ni n f o r m a t i o ns
2、e c u r i t ya n dn e t w o r ks e c u r i t yU S i n g D i r e c t e dD i g i t a lS i g n a t u r ei sas p e c i a ls c h e m et h a tm u s tb ev e r i f i e db ys p e c i f i cu s e r I nt h i sp a p e r ，w ed e s i g naD i r e c t e dM e s s a g eR e c o v e r yS i g n a t u r es c h e m eb a s
3、e do nE l l i p t i cC u r v eC r y p t o s y s t e m s ，a n da n a l y z et h es e c u r i t yo ft h en e ws c h e m e T h es i g n a t u r ei sn o to n l ya na u t h o r i t ys c h e m e ， b u ta l s oa ne n c r y p t i o ns c h e m e I td o e s n tr e q u i r ei n t e r a c t i v ei d e n t i f i
4、 c a t i o n K e y w o r d sE l l i p t i cc u r v e s ，D i g i t a ls i g n a t u r e ，D i r e c t e ds i g n a t u r e ，S u b l i m i n a lc h a n n e l s 1 引言 了时空开销。 数字签名技术是公钥密码学发展的一个方向， 在认证领域内有重要的应用。目前的数字签名算法 大都基于数学中的困难问题，其中最常见的是因子 分解和离散对数，随着计算机技术和计算理论的发 展，这两类问题必须不断增大数据规模才能保证安 全性，因而时间、空间复杂度不断增大。
5、在许多应用 场合已很难满足要求。椭圆曲线相比之下具有很大 的优越性，是一种能够适应未来通信技术和信息安 全技术发展的新型密码体制。 数字签名系统由签名者、验证者、签名消息、数 字签名、签名算法和密钥几个要素组成。签名者使用 自己的私钥对消息签名，将数字签名和消息作为一 个整体发送数字签名和签名者的秘密信息相关，与 验证者无关，任何人只要拥有签名者公钥都可以进 行验证。在单向签名【1 3 中，签名者用自己的私钥和验 证者的公钥同时进行签名，于是数字签名既和签名 者相关又和验证者相关，因而只有特定的验证者才 能进行验证。 具有消息恢复特性的数字签名同时具有消息认 证和加密的功能，签名过程为签名加密
6、过程，签名验 证过程为验证解密过程，签名数据同时又是消息的 密文数据。本文第3 部分基于椭圆曲线密码理论，设 计了一种具有消息恢复的单向数字签名算法，分析 了安全性和复杂性。该算法中存在宽带阈下信道，即 便在签名消息受到第三方监控的情况，仍可以利用 随机数传递秘密信息，由此可以实现隐蔽通信。和一 般签名算法相比较，该算法不需要交互式验证，节省 2 椭圆曲线密码的有关问题 椭圆曲线是代数几何中的一个复杂问题，在 1 9 8 5 年由K o b l i t z 和M i l l e r 分别引入密码学，是近 年来研究的一个热点，由于该体制需要很小的数据 规模就可以达到很高的安全性，因此应用前景十分
7、 广阔。 选取有限域F q 上的椭圆曲线【2 3 ，当c h a r 3 时，W e i r s t r a s s 方程为： E ( F q ) ：y 2 = z 3 十口z + 6 ( 口，b E F q ，4 a 3 + 2 7 b 2 O ) 做如下定义： 点集F ： ( z ，y ) I Y 2 一z 3 + a x + b ) U O 占) ，O 占为 一个无穷远点。 点加p ：P = ( z 。，y 。) ，Q = ( z 。，弛) ，则尸| Q = c z 。，y 。， Y 毛s 三A ：；2 _ Y t I 2L Z l 一Z 3 J P Q P = Q 此时代数系统( F
8、。o ) 为交换群。若尸Q R ， 则P = R o ( 一Q ) ，本文记作P = ReQ 。 在椭圆曲线的有关计算中，点的多次倍加，s 即时求s P 的运算比较复杂，一种快速算法 可适 当减小运算量，若n 为模乘运算的数据规模，算法复 杂度为O ( n 2 l o g s ) 。 5 具有消息恢复的单向签名方案 5 1 系统初始化 参数选取：选取一条椭圆曲线E ( F q ) ：y 2 = z 3 + * ) 国家8 6 3 计划项目8 6 3 3 0 1 3 - 2 B 韩益亮教师。研究方向：信息安全技术扬晓元教授，硕士研究生导师，研究方向为：密码学、计算机安 全与信息理论 2 9 3
9、羔拳嚣寄，J、，【 一 盘z + b ( a ，6 F q ，4 a 3 + 2 7 b 2 o ) ，F q 为素数域 2 。 GE # E ( F q ) 作为基点，7 1 一o r d ( G ) 为基点的 阶，即n G 一0 E 。 # E ( F q ) 为曲线的阶，要求包含有大紊因子。 上述有效椭圆曲线域参数以一个六元组T 嘲公 开，T = q ，a ，b ，G ，n ，h ，整数h 为余因子，h = # E ( F q ) n 。 5 2 算法描述及分析 设签名者为T ，特定的验证者为V 。 密钥生成：s T ，却 1 ，行一1 ( 分别为T 和V 的私钥，各自相应的公钥分别为P
10、 r = s rG ，P y = 即 G 。 消息预处理：待签名消息M 为二进制串，将优 按l o g qb i t 分段，M = m l ，m 2 ，m d 。 假设已有良好的嵌入算法，将r t l ，嵌入到椭圆曲 线上成为点P m ，( 厂( 巩) ，y ) ，i = 1 ，2 ，d ，厂( ) 为某 个可逆函数，于是明文转换成为d 个椭圆曲线上的 点。 签名生成：签名者T 选取随机数K ，7 “ 1 1 ，按以下步骤完成对一个消息段的签名。 计算1 C = P m f o ( s r + h ) P ，一( x c ，y c ) ，其中 ( z c ，Y c ) 为点C 的坐标。 2 R
11、 = t c G 3 y = 符+ 幻s r m o d ，l ( C ，R ，y ) i 为对第i 个消息段的签名，每个三元 组( C ，R ，y ) 包含五个数据( x c ，y c ，7 C R ，Y 置，y ) 。 对所有消息段的签名完成后，级联成S = ( C ， 尺，y ) 。，( C ，R ，y ) 。，( C ，R ，y ) a ) ，作为对消息M 整 体的数字签名，发送给验证者V ，无需发送消息M 。 目前常用的普通数字签名一般基于因子分解和 离散对数问题，先对消息进行一次h a s h 变换，再对 定长的h a s h 值进行签名，运算量和数据量与消息长 度无关，签名的数据
12、量大约为2 6 k b i t ，但必须将消 息同时传送才能验证，于是对于d l o g qb i t 的消息， 总的数据量为d l o g q + 2 6 kb i t ，该算法签名数据 量为d ( 4 1 0 9 q + 九) b i t ，签名消息长度小于2 kb i t 时， 数据量小于普通数字签名。该算法作了2 次倍加和1 次点加，复杂度为O ( d n 2 l o g 九) ，如果按目前n 19 0 b i t 取值，其运算量在实际应用中是可行的。 签名验证：验证者V 将签名S 分为d 组，对每 个分组按方程y G = R o z c P r 验证是否成立。所有 分组均验证成立，则
13、签名S 验证通过。 该验证算法作了2 次倍加和1 次点加，运算量和 与签名算法相当。 消息恢复：验证者V 将签名S 分为d 组，对每 个分组用方程P m ，一C G 即( P T o 尺) 恢复消息出点 P 优i ，再懈码得到一个消息段m i = 广1 ( P m ，) 。 依次恢复所有数据，共得到d 个消息段，合并 2 9 4 后可还恢复出消息M 。 该方案除具有单向签名的特征外，还兼具加密 功能，只有特定的验证者才能完成验证和解密。该算 法作了1 次倍加和2 次点加，复杂度仍为0 ( d n 2 l o g 以) ，但运算量小于签名运算。 安全性分析：对于签名的分析，彤和s 丁为证明签 名
14、者T 身份的秘密信息，攻击者必须分析出确定的 值才能成功伪造签名。在Y 和z c 已知时，由式可 得S T 一妨1 ( y 一是) 或霄一y - - z c s 了，为关于席和s 丁的不 定方程，无法得到唯一确定解。如果随机猜测或穷搜 索，只要能确定心和s 丁其中之一，就可攻破算法，攻 击者可以随机猜测一个，代入式检验，如果R 一 G ，则芹一弗，猜测成功，攻击者能成功猜测出或 s T 的概率为2 一，在基点选取合适，九足够大时，可认 为是不能发生的。 在解密运算中要求验证者的私钥s y 参与运算， 只有特定的验证者V 才能通过签名数据恢复出消 息。解密方程P m = C e 印( P 丁尺)
15、 为关于P m 和s v 的不定方程，攻击者只要能确定即就能译出明文， 但公开的参数中只有验证者的公钥P y 与s v 相关， 通过P y s y G 来攻击即是椭圆曲线离散对数问题， 在曲线选取合适时该问题是属N P C 类，因而解密算 法可以保证安全性。 5 5 阈下信道分析 阈下信道是指存在于密码协议中用来传输秘密 消息的数学结构，阈下信道的利用与防止是现代公 钥密码学中的一个研究课题。如果签名者可以将秘 密信息隐藏于签名之中，接收者能够按照事先约定 的协议恢复出阈下信息，而且这种秘密信息很难被 其他人检测到，这就是阈下信道的模式。与文件加密 相比较，这样的阅下信道是一种更安全的隐蔽通信
16、 方式。G J S i m m o n s 最早发现在E L G a m a l 和D S A 数字签名方案中存在阈下信道 6 。 该签名算法存在方式I 宽带阈下信道，即收发 双方在共享签名者的私钥时，能利用签名中的所有 附加信息来传递大量秘密信息。实现隐蔽通信的协 议如下： 1 ) 签名者和验证者事先约定密钥s 丁 2 ) 签名者根据需要选定数 1 ，l 一1 ，按 S = s i g ( M ，K ) 对消息M 签名 3 ) 验证者按弗一y 一靳5 T ，确定片，恢复出阈下信 息 按以上协议，验证者得到签名时就能立即确定 心，而第三方无法识别这种秘密通信。通过这种方式， 签名者和验证者即使将消息M 公开，也能传递七b i t 的秘密信息，如果对每个消息分段签名时选取不同 的片值，则这个阅下信道容量可达
