对ECC算法实现的选择明文攻击方法

doi:10.3969/j.issn.1000-436x.2014.05.011

Abstract

Abstract:

Chosen-message side-channel analysis attacks for public-key cryptosystems based on scalar multiplications was proposed, where special input point P is chosen to have the features of special y-coordinate to generate noticeable variations on power consumption or other side-channel information, between point doubling and addition operations, rendering distinguishable key bit information. Experimental results demonstrate that the proposed chosen message with simple side channel analysis method could effectively generate the noticeable variations. The method applies to the prime filed ECC cryptographic algorithms.

Key words: Elliptic curve cryptosystem, scalar multiplication, chosen message attack, side channel analysis

Peng LUO,Hui-yun LI,Kun-peng WANG,Ya-wei WANG. Chosen message attacks method against ECC implementations[J]. Journal on Communications, 2014, 35(5): 79-87.

Figures/Tables 10

步骤	运算式	步骤	运算式
1	T₁=y₂-y₁	6	x₃=x₃-x₁
2	T₂=x₂-x₁	7	x₃=x₃-x₂
3	$T_{2} = T_{2}^{- 1}$	8	T₁=x₁-x₃
4	$T_{2} = T_{1} T_{2}^{- 1}$	9	y₃=T₁T₂
5	$x_{3} = T_{2}^{2}$	10	y₃=y₃-y₁

步骤	运算式	步骤	运算式
1	T1=X₂Z₁	12	C=CT₇
2	T₂=X₁Z₂	13	C=C-T₁
3	T₃=T₁-T₂	14	X ₃=T₃C
4	T₄=Y₂Z₁	15	T₂=T₂T₆
5	T₅=Y₁Z₂	16	T₆=T₆T₃
6	T₄=T₄-T₅	17	T₅=T₆T₅
7	$T_{6} = T_{3}^{2}$	18	Y ₃=T₂-C
8	T₁=T₁+T₂	19	Y₃=Y₃T₄
9	T₁=T₆T₁	20	Y₃=Y₃-T₅
10	T₇=Z₁Z₂	21	Z ₃=T₆T₇
11	$C = T_{4}^{2}$

步骤	运算式	步骤	运算式
1	$T_{1} = Z_{1}^{2}$	13	T₂=T₂T₄
2	T₂=T₁X₂	14	$X_{3} = T_{6}^{2}$
3	$T_{3} = Z_{2}^{2}$	15	X ₃=X₃-T₂
4	T₄=T₃X₁	16	T₄=T₄T₅
5	T₅=T₂-T₄	17	T₁=T₁+T₃
6	T₁=T₁Z₁	18	T₄=T₄T₁
7	T₁=T₁Y₂	19	Y₃=T₂-2X₃
8	T₃=T₃Z₂	20	Y₃=Y₃T₆
9	T₃=T₃Y₁	21	Y₃=(Y₃-T₄)/2
10	T₆=T₁-T₃	22	Z ₃=Z₁Z₂
11	T₂=T₂+T₄	23	Z ₃=Z₃T₅
12	$T_{4} = Z_{5}^{2}$

步骤	运算式	步骤	运算步骤
1	$T_{1} = Z_{2}^{2}$	10	T₃=T₃X₂
2	T₂=T₁Z₂	11	T₁=2T₃
3	T₁=x₁T₁	12	$X_{3} = T_{2}^{2}$
4	$T_{2} = y_{1} T_{2}$	13	X ₃=X₃-T₁
5	T₁=X₂-T₁	14	X ₃=X₃+T₄
6	T₂=Y₂-T₂	15	T₃=T₃-X₃
7	Z₃=T₁Z₂	16	T₃=T₃T₂
8	$T_{3} = T_{1}^{2}$	17	T₄=T₄Y₂
9	T₄=T₁T₃	18	Y₃=T₃-T₄

模乘编号	$y_{1} ＜ \frac{1}{2} p$ 点的能耗	$y_{1} ＞ \frac{1}{2} p$ 点的能耗	ΔO
M1	34.210 846	34.193 375	-0.000 5
M2	31.655 19	31.637 566	-0.000 6
M3	27.302 038	27.287 497	-0.000 5
M4	28.069 105	28.116 11	0.001 7
M5	27.624 77	27.602 726	-0.000 8
M6	29.530 966	29.529 814	0.000 0
M7	29.179 401	29.161 39	-0.000 6
M8	29.386 608	29.377 132	-0.000 3
M9	24.827 814	24.828 201	0.000 0
M10	28.082 44	28.057 52	-0.000 9
M11	30.132 78	30.145 34	0.000 4

References 10

[1]	KOCHER P , JAFFE J , JUN B . Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[A]. Proceedings of 16th International Advances in Cryptology Conference-CRYPTO‘96[C]. 1996.104-113.
[2]	YENS M , LIEN W C , MOONS J , et al. Power analysis by exploiting chosen message and internal collisions-vulnerability of checking mecha-nism for RSA decryption[A]. MYCRYPT 2005[C]. 2005.183-195.
[3]	MIYAMOTO A , HOMMA N , AOKI T , et al. Enhanced power analysis attack using chosen message against RSA hardware implementa-tions[A]. IEEE International Conference on Field Programmable Logic and Applications[C]. 2008.3282-3285.
[4]	HOMMA N , MIYAMOTO A , AOKI T , et al. Comparative power analysis of modular exponentiation algorithms[J]. IEEE Transaction on Computers, 2010.795-807.
[5]	YENSM , LIEN W C , CHEN C N . Modified doubling attack by ex-ploiting chosen ciphertext of small order[A]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sci-ences[C]. 2011.1981-1990.
[6]	FAN J , GIERLICHS B , VERCAUTEREN F . To infinity and beyond:combined attack on ECC using points of low order[A]. International Workshop on Cryptographic Hardware and Embedded Systems[C].CHES, LNCS, 2011.
[7]	HANKERSON D , MENEZES A , VANSTONE S . Guide to Elliptic Curve Cryptography[M]. New York, USA: Springer-Verlagn, 2003.
[8]	CORON J S . Resistance against differential power analysis for elliptic curve cryptosystems[A]. International Workshop on Cryptographic Hardware and Embedded Systems[C].CHES, LNCS, 1999.
[9]	CHEN T , LI H , WU K , YU F . Countermeasure of ECC against side-channel attacks: balanced point addition and point doubling op-eration procedure[A]. AsiaPacific Conference on Information Proc-essing 2009[C]. 2009.465-469.
[10]	LUO P , FENG D G , ZHOU Y B . Power model in power analysis at-tack[J]. Journal on Communications, 2012,33(Z1): 276-282.

Metrics

Recommended 0

No Suggested Reading articles found!

Chosen message attacks method against ECC implementations

RichHTML

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

Figures/Tables 10

References 10

Related Articles 10

Metrics

Recommended 0

[1]	Bin YU, Hai HUANG, Zhiwei LIU, Shilei ZHAO, Ning NA. Design and implementation of high-speed scalar multiplier for multi-elliptic curve [J]. Journal on Communications, 2020, 41(12): 100-109.
[2]	Ming XU,Liang SHI. Pseudo 4D projective coordinate-based multi-base scalar multiplication [J]. Journal on Communications, 2018, 39(5): 74-84.
[3]	. Chosen message attacks method against ECC implementations [J]. Journal on Communications, 2014, 35(5): 11-87.
[4]	. Hardware Trojans detection based on projection pursuit [J]. Journal on Communications, 2013, 34(4): 14-126.
[5]	Peng ZHANG,Xin-cheng WANG,Qing ZHOU. Hardware Trojans detection based on projection pursuit [J]. Journal on Communications, 2013, 34(4): 122-126.
[6]	Jin-zhong ZHANG,Ying-zhan KOU,Tao WANG,Shi-ze GUO,Xin-jie ZHAO. Fault analysis on elliptic curve cryptosystems with sliding window method [J]. Journal on Communications, 2012, 33(1): 71-78.
[7]	Xin-chun YIN,Hai-ling ZHANG,Ting YANG. Optimized fast multi-scalar multiplication algorithm based on MBNS [J]. Journal on Communications, 2010, 31(8A): 122-126.
[8]	Jian-hong SHI,Chen-hui JIN,Zhi-shu PAN. Seven element joint sparse form for pairs of integers and its application [J]. Journal on Communications, 2009, 30(12): 113-118.
[9]	Hong WANG,Bao LI,Wei YU. Montgomery algorithm on elliptic curves over finite fields of character three [J]. Journal on Communications, 2008, 29(10): 25-29.
[10]	Bao-hua ZHANG,Xin-chun YIN,Hai-ling ZHANG. EDSM:secure and efficient scalar multiplication algorithm on Edwards curves [J]. Journal on Communications, 2008, 29(10): 76-81.