Free ebooks ==> www.Ebook777.com Lecture Notes in Electrical Engineering 375 Jason C. Hung Neil Y. Yen Kuan-Ching Li Editors Frontier Computing Theory, Technologies and Applications www.Ebook777.com Free ebooks ==> www.Ebook777.com Lecture Notes in Electrical Engineering Volume 375 Board of Series editors Leopoldo Angrisani, Napoli, Italy Marco Arteaga, Coyoacán, México Samarjit Chakraborty, München, Germany Jiming Chen, Hangzhou, P.R China Tan Kay Chen, Singapore, Singapore Rüdiger Dillmann, Karlsruhe, Germany Haibin Duan, Beijing, China Gianluigi Ferrari, Parma, Italy Manuel Ferre, Madrid, Spain Sandra Hirche, München, Germany Faryar Jabbari, Irvine, USA Janusz Kacprzyk, Warsaw, Poland Alaa Khamis, New Cairo City, Egypt Torsten Kroeger, Stanford, USA Tan Cher Ming, Singapore, Singapore Wolfgang Minker, Ulm, Germany Pradeep Misra, Dayton, USA Sebastian Möller, Berlin, Germany Subhas Mukhopadyay, Palmerston, New Zealand Cun-Zheng Ning, Tempe, USA Toyoaki Nishida, Sakyo-ku, Japan Bijaya Ketan Panigrahi, New Delhi, India Federica Pascucci, Roma, Italy Tariq Samad, Minneapolis, USA Gan Woon Seng, Nanyang Avenue, Singapore Germano Veiga, Porto, Portugal Haitao Wu, Beijing, China Junjie James Zhang, Charlotte, USA www.Ebook777.com About this Series “Lecture Notes in Electrical Engineering (LNEE)” is a book series which reports the latest research and developments in Electrical Engineering, namely: • • • • • Communication, Networks, and Information Theory Computer Engineering Signal, Image, Speech and Information Processing Circuits and Systems Bioengineering LNEE publishes authored monographs and contributed volumes which present cutting edge research information as well as new perspectives on classical fields, while maintaining Springer’s high standards of academic excellence Also considered for publication are lecture materials, proceedings, and other related materials of exceptionally high quality and interest The subject matter should be original and timely, reporting the latest research and developments in all areas of electrical engineering The audience for the books in LNEE consists of advanced level students, researchers, and industry professionals working at the forefront of their fields Much like Springer’s other Lecture Notes series, LNEE will be distributed through Springer’s print and electronic publishing channels More information about this series at http://www.springer.com/series/7818 Jason C Hung Neil Y Yen Kuan-Ching Li • Editors Frontier Computing Theory, Technologies and Applications 123 Free ebooks ==> www.Ebook777.com Editors Jason C Hung Department of Information Technology Overseas Chinese University Taichung Taiwan Kuan-Ching Li Providence University Taichung Taiwan Neil Y Yen Aizu-Wakamatsu, Fukushima Japan ISSN 1876-1100 ISSN 1876-1119 (electronic) Lecture Notes in Electrical Engineering ISBN 978-981-10-0538-1 ISBN 978-981-10-0539-8 (eBook) DOI 10.1007/978-981-10-0539-8 Library of Congress Control Number: 2016934668 © Springer Science+Business Media Singapore 2016 This work is subject to copyright All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed The use of general descriptive names, registered names, trademarks, service marks, etc in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication Neither the publisher nor the authors or the editors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissions that may have been made Printed on acid-free paper This Springer imprint is published by Springer Nature The registered company is Springer Science+Business Media Singapore Pte Ltd www.Ebook777.com Preface The International Conference on Frontier Computing—Theory, Technologies, and Applications (FC) was first proposed in early 2010 at an IET executive meeting This conference series aims at providing an open forum to reach a comprehensive understanding of the recent advances and emergence of information technology, science, and engineering, with themes in the scope of Communication Network Technology and Applications, Communication Network Technology and Applications, Business Intelligence and Knowledge Management, Web Intelligence, and any related field that prompts the development of information technology This will be the fourth event of the series, in which fruitful results can be found in the digital library or conference proceedings of FC 2010 (Taichung, Taiwan), FC 2012 (Xining, China), FC 2013 (Gwangju, Korea) Each event brings together researchers from worldwide to have excited and fruitful discussions as well as future collaborations The papers accepted for inclusion in the conference proceedings primarily cover the topics: database and data mining, networking and communications, web and Internet of things, embedded system, soft computing, social network analysis, security and privacy, optics communication, and ubiquitous/pervasive computing Many papers have shown their great academic potential and value, and in addition, indicate promising directions of research in the focused realm of this conference series We believe that the presentations of these accepted papers will be more exciting than the papers themselves, and lead to creative and innovative applications We hope that the attendees (and readers as well) will find these results useful and inspiring to their field of specialization and future research On behalf of the organizing committee, we would like to thank the members of the organizing and the program committees, the authors, and the speakers for their dedication and contributions that made this conference possible We would like to thank and welcome all participants to the capital city of Thailand—Bangkok Bangkok is a country with a long and remarkable history To get a picture of Southeast Asia, this city will certainly be an entry Though most of the countries may share some similar characteristics, you will find that the culture of Thailand v vi Preface is very rich from different perspectives, such as art, religion, nomadic lifestyle, food, and music Bangkok is a world-class and well-known city, with modern facilities and stable weather We encourage the participants to take this chance to see and experience Thailand, especially the remote counties and the nomadic lifestyle there We also sincerely hope that all participants from overseas and from Thailand enjoy the technical discussions at the conference, build a strong friendship, and establish ties for future collaborations We convey our sincere appreciations to the authors for their valuable contributions and to the other participants of this conference The conference would not have been possible without their support Thanks are also due to the many experts who contributed to making the event a success July 2015 Jason C Hung Neil Y Yen Kuan-Ching Li Organization Steering Chairs Kuan-Ching Li, Providence University, Taiwan Jason C Hung, Overseas Chinese University, Taiwan Neil Y Yen, The University of Aizu, Japan General Chairs C.S Raghavendra, University of Southern California, USA Yi Pan, Georgia State University, USA Hamid R Arabnia, The University of Georgia, USA Hong Shen, University of Adelaide, Australia Jen-Shiun Chiang, Tamkang University, Taiwan Qingguo Zhou, Lanzhou University, China Vice General Chairs Han-Chieh Chao, National Ilan University, Taiwan Zheng Xu, Tsinghua University, China Yasuji Sawada, Tohoku University of Technology, Japan Eiko Yoneki, University of Cambridge, UK Kurosh Madani, University of Paris-EST, France Program Chairs Keqiu Li, Dalian University of technology, China Hai Jiang, Arkansas State University, USA vii viii Organization Kehan Zeng, University of Macau, Macau Meng-Yen Hsieh, Providence University, Taiwan Zhou Rui, Lanzhou University, China Vice Program Chairs Deqiang Han, Beijing University of Technology, China Hsuan-Fu Wang, Chung Chou University of Science and Technology, Taiwan Jun-Hong Shen, Asia University, Taiwan Fang-Biau Ueng, National Chung Hsing University, Taiwan Workshop Chairs You-Shyang Chen, Hwa Hsia University of Technology, Taiwan Wei-Chen Wu, Hsin Sheng College of Medical Care and Management, Taoyuan County, Taiwan Chengjiu Yin, Kyushu University, Japan Yan Pei, University of Aizu, Japan Publicity Chairs Vladimír Smejkal, Brno University of Technology, Czech Republic Fei Wu, Zhejiang University, China Francisco Isidro Massetto, Federal University of ABC, Brazil Riz Sulaiman, Universiti Kebangsaan Malaysia, Malaysia Wei Tsang Ooi, National University of Singapore, Singapore Yusuke Manabe, Chiba Institute of Technology, Japan Soumya Banerjee, Birla Institute of Technology, India Tran Thien Phuc, Hochimin City University of Technology, Vietnam Jindrich Kodl, Authorised expert in security of information systems, cryptology and informatics, Czech Republic Poonphon Suesaowaluk, Assumption University of Thailand, Thailand Jenn-Wei Lin, Fu Jen University, Taiwan International Advisory Committees Jinannong Cao, Hong Kong Polytechnic University, Hong Kong Su-Ching Chen, University of Florida, USA Fatos Xhafa, Technical University of Catalonia, Spain Free ebooks ==> www.Ebook777.com Organization ix Jianhua Ma, Hosei University, Japan Runhe Huang, Hosei University, Japan Qun Jin, Waseda University, Japan Victor Leung, University of British Columbia, Canada Qing Li, City University of Hong Kong, Hong Kong Jean-Luc Gaudiot, University of California, Irvine, USA www.Ebook777.com 1216 C.-H Zheng and H.-L Huang agricultural enterprises recognize that innovative technologies will bring greater-than-expected profits, will they adopt new technology However, this is not conducive to the timely promotion of new technology Therefore, the government should provide supportive policies (i.e., financial subsidies, patent protection, etc.) to motivate entities to adopt new technology so as to accelerate the promotion of technology 3.2 Active Technology Diffusion Strategies in Market-Led Industry Clusters Market-led clusters, especially leading enterprises, collaborative enterprises, farmers and relevant entities have to work together to participate in innovative diffusion networks First, leading enterprises should actively implement active technology research strategies through close cooperation with other enterprises and farmers, constantly update their knowledge, adopt latest innovative technologies, and facilitate the establishment of innovative industry clusters After leading enterprises obtain new technology achievements, they have to manage to work with collaborative enterprises and farmers to accelerate the application of technology At the same time, the leading enterprises can use market mechanisms to provide collaborative enterprises and farmers with business opportunities, latest technology and training They can encourage industrial chains to work together to apply new technology just in the clusters, and make clusters have exclusive advantages in production shortly Secondly, collaborative enterprises and farmers have to be active in adopting new agricultural technology Agricultural technology is highly regional Agricultural enterprises and farmers have to have the ideas about local agriculture On the one hand, they have to contribute their knowledge of agricultural technology; support and actively participate in research and development of new technology and adopt latest technology On the other hand, clusters have different highly specialized divisions, including research, planting, processing, marketing, and transportation They are a part of the whole They should actively develop their own professional skills, and improve their technical proficiency Weakness of Zhang-Wang Scheme Without Using One-Way Hash Function Zhi-Pan Wu Abstract Zhang and Wang proposed a signature scheme without using one-way hash function and message redundancy It based on Chang-Chang scheme and gives an improvement which overcomes the known forgery attack In this paper, we show this scheme can not suffer forgery attack where it does not use the one-way hash function We believe the one-way hash function still demands message recovery and redundancy Keywords Digital signature Forgery attack Á One-way hash function Á Message redundancy Á Introduction With the growth of the Internet, the digital signature is becoming very important in the electronic commerce, it provides the cryptographic services on authentication and data integrity where also agree between signer and verifier, there are several digital signature scheme have been proposed [1] In Shieh et al [5] proposed two multi-signature schemes based on Nyberg-Rueppel scheme [4], one is parallel multi-signature scheme, and other is serial multi-signature scheme They proposed scheme enables the specified verifier to verify and to recover the message, it applied to smaller bandwidth of data communications Further, one-way hash function and message redundancy scheme are not used But this scheme was insecure, it easy suffered forgery attack, hence many paper cryptanalysis and improvement [7] on Shieh et al signature scheme Recently, Zhang and Wang [8] presented a new digital signature scheme with message recover without using one-way hash function and message redundancy, and claimed that their scheme can resist forgery However, in this paper, we discover their scheme still insecure, it does not resist Z.-P Wu (&) Department of Computer Science, Huizhou University, Huizhou 516007, China e-mail: hz_wzp@163.com © Springer Science+Business Media Singapore 2016 J.C Hung et al (eds.), Frontier Computing, Lecture Notes in Electrical Engineering 375, DOI 10.1007/978-981-10-0539-8_125 1217 1218 Z.-P Wu forgery attack The paper is organized as follows: Sect reviews Zhang’s scheme, Sect analyzes the security of Zhang’s scheme Section points out a weakness security and presents our conclusion Review of Zhang-Wang Scheme In Zhang and Wang [8] proposed a signature scheme without using one-way hash functions In their scheme, p and g, where p is a large prime number and g is a primitive element in GF (p) The signer randomly selects his private key x, where gcdðx; p 1ị ẳ 1, and computes public key y  gx ðmod pÞ There are two phases The signature generation and verification phase are described below 2.1 Signature Generation Phase Suppose the signer wants to sign the message M, then execute the follow steps: Step The signer computes s  y ỵ MịMmod p1ị mod pị: 1ị Step The signer chooses a random number k ZpÀ1 and computes r  M Á s Á gÀk ðmod pÞ: ð2Þ Step The signer computes t where s þ t  xÀ1 Á ðk À r È sÞðmod p À 1Þ: ð3Þ Step The signer sends the triple parameters (s, r, t) of M to the verifier 2.2 Verification Phase The verifier receives the signature (s, r, t) from the signer, and can then verify the validity of signature in the as following steps: Step The verier computes M  ys ỵ t r Á grÈs Á sÀ1 ðmod pÞ: ð4Þ Weakness of Zhang-Wang Scheme … 1219 Step The verifier checks s  y ỵ MịMmod p1ị mod pị: 5ị If the rule holds, it shows that the signature (s, r, t) is valid Proof M  ys ỵ t r grẩs s1 mod pị:  ys ỵ t Á M Á s Á gÀk Á grÈs Á sÀ1 mod pị:  gkrẩs M gk ỵ rẩs ðmod pÞ: ð6Þ  Mðmod pÞ: Misuse Order of Operation Problem The Zhang-Wang scheme does not appear to be true, as pointed out below According to [2] and [6], the addition has higher precedence than bitwise exclusive-or Therefore the addition should be applied first, and then processes bitwise exclusive-or operation in a computer programming language such as C++ and so on This rule is known as a precedence rule or order of operation We set ðk À r ¼ uị and k ỵ r ẳ uị, and recompute follow equation Proof ? M  ys ỵ t r Á grÈs Á sÀ1 ðmod pÞ: ? ðgx Þx À1 ÁðkÀrÈsÞ Á r Á grÈs Á sÀ1 ðmod pÞ: ?  gðkÀrÈsÞ Á r Á grÈs Á sÀ1 ðmod pÞ: ?  guÈs Á M Á s Á gÀk Á grÈs Á sÀ1 ðmod pÞ: ð7Þ ?  guÈs M gk ỵ rẩs mod pị: ?  guÈs Á M Á gðÀuÞÈs ðmod pÞ: 6 Mðmod pÞ: Correction equation xÀ1 Á ðk À r È sÞðmod pÞ is used instead of xÀ1 Á ðk À ðr È sÞÞðmod pÞ by Eq (3) Thus, if one wants to force bitwise exclusive-or to precede addition, one writes ðk À ðr È sÞÞ 1220 Z.-P Wu Proof M  ys ỵ t r grẩs s1 ðmod pÞ:  ðgx Þx À1 ÁðkÀðrÈsÞÞ Á M Á s Á gÀk Á sÀ1 ðmod pÞ:  gkÀðrÈsÞ Á M Á gÀk Á grÈs ðmod pÞ: ð8Þ  Mðmod pị: The other revision is M  ys ỵ t Á r Á grÈs Á sÀ1 ðmod pÞ is instead of M  Á r Á gkÀðkÀrÈsÞ Á sÀ1 ðmod pÞ by Eq (4) y We also assume k r ẳ uị and k ỵ r ẳ uị and recompute the equation sỵt Proof M  ys ỵ t r gkkrẩsị s1 mod pÞ:  ðgx Þx À1 ÁðkÀrÈsÞ Á r Á gkÀðkÀrÈsÞ Á sÀ1 ðmod pÞ:  gðkÀrÈsÞ Á M Á s Á gÀk Á gkÀðkÀrÈsÞ Á sÀ1 ðmod pÞ: g ðuÈsÞ ÁMÁg Àk k Ág Ág ÀðuÈsÞ ð9Þ ðmod pÞ:  Mðmod pÞ: Our Attack Method In this section, we will point out a weakness for the Zhang-Wang scheme If attacker Eve wants to fake a message to Bob, she does not need to guess a password or challenge discrete logarithm problem Even if the Zhang-Wang scheme used bitwise exclusive-or (XOR) operation to resist an algebra attack, a leak still exists in which the number system of two complementary numbers is the most common method of representing on the computer [3] In the follow, we describe the practical issue that two variables bitwise exclusive-or operation problem 4.1 Two’s Complement System The two’s complement-complement system has the advantage of not requiring that the addition and subtraction circuitry examine the signs of the operands to determine whether to add or subtract The two’s complement of zero is zero: inverting gives all ones, and adding one changes the ones back to zero The zero’s one complement is ð11111111Þ2 , then add one to become ð00000000Þ2 , so it is itself Weakness of Zhang-Wang Scheme 1221 0ị10 1ị10 ẳ 0ị10 The ð10000000Þ2 one’s complement is ð01111111Þ2 , then add one to become 10000000ị2 128ị10 1ị10 ẳ 128ị10 Also the two’s complement of the most negative number representable (e.g a one as the most-significant bit and all number bits zero) is itself Notation: ⊕ express the bitwise exclusive-or operation ()10 express a decimal number system ()2 express a binary number system [Pr] express probability > < are odd numbers; theẵPr ẳ 4: r; sị ) one odd and even; theẵPr ẳ 12: > : are even numbers; theẵPr ẳ 14: For Example: 193ị10 ẳ 11000001ị2 249ị10 ẳ 11111001ị2 193ị10 ẩ 249ị10 ẳ 00111000ị2 193ị10 ẩ 249ị10 ẳ 56ị10 193ị10 ẳ 1111111100111111ị2 249ị10 ẳ 1111111100000111ị2 193ị10 ẩ 249ị10 ẳ 0000000000111000ị2 193ị10 ẩ 249ị10 ẳ 56ị10 4.2 XOR Operation The XOR operation is a common component in design of digital logic It is used on adder, cryptosystem or other applications We describe the XOR boolean algebra as below There are some denitions: 0ẳ1 10ị 1ẳ0 11ị Aẩ1ẳA 12ị Aẩ0ẳA 13ị AẩAẳ0 14ị 1222 Z.-P Wu AẩAẳ1 15ị A ẩ B ẳ AB ỵ AB 16ị Theorem Let ⊕ be an operation on the set X It is called commutative if A È B ¼ B È A for all A; B X Proof According to Eq (16), A ẩ B ẳ AB ỵ AB (known denition) B ẩ A ẳ BA ỵ BA, therefore AB þ AB ¼ BA þ BA We obtain A È B ¼ B È A Thus, the XOR matches commutative law Theorem Let ⊕ be an operation in the set X It is called associative if ðA È BÞ ẩ C ẳ A ẩ B ẩ Cị for all A; B X Proof ðA È BÞ È C ẳ AB ỵ ABị ẩ C: ẳ AB ỵ ABị ẩ C: ẳ AB ỵ ABịC ỵ AB ỵ ABịC: ẳ AB ỵ ABịC ỵ AB ỵ ABịC: ẳ ABị ABịC ỵ ABC ỵ AB C ẳ A þ BÞðA þ BÞC þ ABC þ AB Á C ẳ AAC ỵ ABC ỵ B AC ỵ BBC þ ABC þ AB Á C AA ¼ and BB ẳ ẳ ABC ỵ B AC ỵ ABC ỵ AB C Computing A ẩ B ẩ Cị A ẩ B ẩ Cị ẳ A ẩ BC ỵ BCị ẳ ABC ỵ BCị ỵ ABC ỵ BCị ẳ ABC ỵ ABC ỵ ABCị BCị ẳ A BC ỵ ABC ỵ AB ỵ CịB ỵ Cị ẳ A BC ỵ ABC ỵ ABB ỵ AB C ỵ ACB ỵ ACC ẳ A BC þ ABC þ ABC þ AC Á B * ABC þ B Á AC þ ABC þ AB Á C ẳ A BC ỵ ABC ỵ ABC ỵ AC B ) A ẩ Bị ẩ C ẳ A È ðB È CÞ Here, the XOR matches associative law Weakness of Zhang-Wang Scheme … 1223 bits zfflfflfflfflfflfflfflfflffl}|fflfflfflfflfflfflfflfflffl{ Theorem Let A = B, A È B ¼ 0000 .0000 bits zfflfflfflfflfflfflfflfflffl}|fflfflfflfflfflfflfflfflffl{ Proof According to (14), A È A ¼ 0, therefore A È B ¼ 0000 .0000 bits zfflfflfflfflfflfflfflfflffl}|fflfflfflfflfflfflfflfflffl{ Theorem If A, B are odd numbers, Aị ẩ Aị ẳ 1111 .1110 , Bị ẩ Bị ẳ bits z}|{ 1111 .1110 A ẩ Bị ẳ A ẩ Bị Proof According to Theorem 3, A if = B, then bits zfflfflfflfflfflfflfflfflffl}|fflfflfflfflfflfflfflfflffl{ A ẩ Bị ẩ A ẩ Bị ẳ 0000 .0000 From Theorem commutative law and Theorem associative law, we rewrite this equation ðA È BÞ È A ẩ Bị ẳ A ẩ Aị ẩ B ẩ ÀBÞ According to Theorem 4, bits zfflfflfflfflfflfflfflfflffl}|fflfflfflfflfflfflfflfflffl{ A È ÀA ¼ B È ÀB From Theorem 3, ðA È BÞ ẩ A ẩ Bị ẳ 0000 .0000 We get A ẩ Bị ẳ A ẩ Bị Theorem If A, B are even numbers, 4jA; B and 8-A; B A ẩ Bị ẳ A ẩ Bị Proof We assume A and B are n bits even numbers, when 4jA and 8-A, bits zfflfflfflfflfflfflfflfflffl}|fflfflfflfflfflfflfflfflffl{ A ¼ à à à à 100 bits When and 8-B, bits bits zfflfflfflfflfflfflfflfflffl}|fflfflfflfflfflfflfflfflffl{ à à à à 000 4jB zfflfflfflfflfflfflfflfflffl}|fflfflfflfflfflfflfflfflffl{ B ¼ à à à à 100 Suppose bits zfflfflfflfflfflfflfflfflfflffl}|fflfflfflfflfflfflfflfflfflffl{ ÀA ¼ #### .100 , z}|{ A ẩ Bị ẳ |||| .000 : A ẩ Bị ẳ bits and z}|{ B ẳ #### .100 bits zfflfflfflfflfflfflfflfflffl}|fflfflfflfflfflfflfflfflffl{ ðA È BÞ È ðÀA ẩ Bị ẳ 000 È bits zfflfflfflfflfflfflfflfflfflffl}|fflfflfflfflfflfflfflfflfflffl{ |||| .000 ¼ Therefore ðA ẩ Bị ẳ A ẩ Bị 4.3 Our Attack From above statement, the attacker Eve can easily fake the valid signature ðr ; s0 ; tÞ in the following steps Step Eve sets r ¼ Àr Step Eve sets s0 ¼ Às Step Eve sends ðr ; s0 ; tÞ signatures to Bob, and successful executes the forgery attack 1224 Z.-P Wu Proof ? M 00  ys Á ðr Þ gr ẩs ị sị1 mod pị: ỵt  gs ỵ t M s0 ị Á gÀk Á gðr Ès Þ Á ðs0 ÞÀ1 ðmod pÞ: 0 0 0  gkÀðr ẩs ị M gk ỵ r ịẩs ị ðmod pÞ:  M0 ð17Þ ðmod pÞ: Conclusion Several programming languages use precedence levels that conform to the order of operation used in mathematical precedence In general, the arithmetic is always higher than bitwise logical operation on precedence If a designer/developer misused or misunderstood this situation, it may cause a dangerous problem We clearly described some examples of this case in the paper It is a good way to prevent multiplicative property of algebra attack using the XOR operation However, according to our analysis, the Zhang-Wang scheme is still insecure Acknowledgements The authors would like to thank the reviewers for their comments that help improve the manuscript The author also thanks Chenglian Liu for his useful suggestion References Chang CC, Chang YF (2004) Signing a digital signature without using one-way hash functions and message redundancy schemes IEEE Commun Lett 8(8):485–487 Kruse RL, Ryba AJ (2000) Data structures and program design in C++ Prentice Hall, NJ Liu C, Chen S, Sun S (2012) Security of analysis mutual authentication and key exchange for low power wireless communications Energy Procedia 17(Part A):644–649 Nyberg K, Rueppel RA (1994) Message recovery for signature schemes based on the discrete logarithm problem In: Advances in Cryptology—EUROCRYPT’94 Shieh SP, Lin CT, Yang WB, Sun HM (2000, July) Digital multisignature schemes for authenticating delegates in mobile code systems IEEE Trans Veh Technol Wikipedia: Order of operations Website (2009) http://en.wikipedia.org/wiki/Order_of_ operations Zhang F et al (2005) Cryptanalysis of Chang et al signature scheme with message recovery IEEE Commun Lett 9(4):358–359 Zhang J, Wang Y (2005) An improved signature scheme without using one-way hash functions Appl Math Comput 170(2):905–908 Weakness of an ElGamal-Like Cryptosystem for Enciphering Large Messages Jie Fang, Chenglian Liu and Jieling Wu Abstract In 2002, Hwang et al proposed an ElGamal-like cryptosystem for enciphering large message where it modified from ElGamal cryptosystem They believe their scheme is based on the difficulty of finding the composite exclusive-or operation Although, they used bitwise exclusive-or to against multiplicative attack For this scheme, it is still insecure In this paper, we give a proof to certain that we claimed Keywords Discrete logarithms Á Elgamal cryptosystem Á Bitwise Exclusive-OR Introduction A well-known public key cryptosystem ElGamal algorithm was proposed in 1985 which it based on discrete logarithms problem The assumption is variety with RSA assume on factoring large integer numbers In 2002, Hwang et al [2] presented an ElGamal-like cryptosystem which it improved the original method to encrypt a large plaintext Their method are both the Diffie–Hellman distribution and the ElGamal scheme Lyuu et al [5] firstly gave an attack that they assume if the number of plaintexts n exceeds the order of modulus q and the prime p is chosen to be of the form 2eq, where e is a positive integer and q is prime number After, Wang et al also demonstrated a vulnerable in 2006 They mentioned to select the J Fang (&) School of Electronics and Information Engineering, Fuqing Branch of Fujian Normal University, Fuqing 350300, China e-mail: fangjie_1@foxmail.com C Liu Department of Computer Science, Huizhou University, Huizhoou 516007, China e-mail: chenglian.liu@gmail.com J Wu Department of Economics and Management, Huizhou University, Huizhoou 516007, China e-mail: jieling.wu@hotmail.com © Springer Science+Business Media Singapore 2016 J.C Hung et al (eds.), Frontier Computing, Lecture Notes in Electrical Engineering 375, DOI 10.1007/978-981-10-0539-8_126 1225 1226 J Fang et al prime p such that the smallest positive integer T for 2T ỵ  2mod p À 1Þ is as large as possible upon on Carmichael number assumption In this paper, we simply showed a variety method which the exclusive-or be used in some situation case of cryptosystem is dangerous Section briefly review the ElGamal-like scheme, and Sect is our comment The conclusion draws in final section Review of Hwang–Chang–Hwang’s Scheme In 2002, Hwang et al [2] proposed an elgamal-like cryptosystem for enciphering large messages scheme, Lyuu et al [5] and Wang et al [6] pointed out some attacks, and then propose a practical anonymous user authentication scheme with security The detailed as below: 2.1 The ElGamal Cryptosystem The ElGamal [1] cryptosystem was proposed in 1985, it based on discrete logarithms Let p is a large prime number, and g is primitive root where g Zp , and compute the public key yi  gx ðmod pÞ The x denotes secret key Here p, g and y are public information, the xi and r are private information If user ui want to deliver the message m (0 ≤ m ≤ p − 1) to uj, ui randomly selects an integer r and then encrypts m as below: b  gr ðmod pÞ: ð1Þ c  m Á yri ðmod pÞ: ð2Þ ui sends (b, c) to uj When uj receives (b, c), uj decrypts c as follows: m  c Á ðbxj ÞÀ1 ðmod pÞ: ð3Þ The cipher c depends on both plaintext m and the random integer r, a different random number r will obtain a different ciphertext c from same plaintext m There are two restriction in the ElGamal cryptosystem; one is random number r can not be repeated and others is message m must be less than p − 2.2 Hwang et al.’s Scheme Assume p is a large prime number such as 513 bits and g is a primitive element of GF(p) Each user ui randomly choose his private key xi Zp and computes the public key yi  gxi ðmod pÞ p, g and yi are published information Any user wants to deliver the message mi to ui by following steps: Weakness of an ElGamal-Like Cryptosystem for Enciphering … 1227 Step Break plaintext mi into t pieces m1, m2, …, mt, each piece of length being 512 bits Step:2 Generate two random numbers r1 and r2, where < r1, r2 ≤ p − 1, and compute b1 and b2 as follows: b1  gr1 ðmod pÞ: ð4Þ b2  gr2 ðmod pÞ: ð5Þ Step Compute Cj, j = 1, 2, …, t as follows: j Cj  mj Á ðyri i È ðyri Þ2 Þðmod pÞ: ð6Þ Step Send {b1, b2, Cj, j = 1, 2, …, t} to the receiver through a public channel After receiving {b1, b2, Cj, j = 1, 2, …, t} from the sender, the receiver recovers the plaintext mi from following: j mj  Cj Á ðbx1i È ðbx2i Þ2 ÞÀ1 ðmod pÞ: ð7Þ Our Comment In this section, we will introduce two point views; one is logical bitwise exclusive-or operation, the other one is order of operations in computer system We introduce the precedence properties in some programming languages 3.1 The Exclusive-OR Operation Issue The XOR operation is a common component in design of digital logical It is used on adder, cryptosystem or other application We described the XOR boolean algebra as below Notation: È : express bitwise exclusive-or operation ()10: express decimal number system ()2: express binary number system [Pr]: express probability There are some axioms known of definition: 0¼1 8ị 1ẳ0 9ị 1228 J Fang et al Aẩ1ẳA 10ị Aẩ0ẳA 11ị AẩAẳ0 12ị AẩAẳ1 13ị A ẩ B ẳ AB ỵ AB 14ị Theorem Let be an operation on the set X It is called commutative if A È B ¼ B È A for all A, B ∊ X Proof According to Eq (14), A È B ẳ AB ỵ AB (known denition), B ẩ A ẳ BA ỵ BA, therefore AB ỵ AB ẳ BA þ BA We obtains A È B ¼ B È A Thus, the XOR matches commutative law Theorem Let È be an operation in the set X It is called associative if A ẩ Bị ẩ C ẳ A È ðB È CÞ for all A, B ∊ X Proof A ẩ Bị ẩ C ẳ AB ỵ ABị ẩ C: ẳ AB ỵ ABị ẩ C: ẳ AB ỵ ABịC ỵ AB ỵ ABịC: ẳ AB ỵ ABịC ỵ AB ỵ ABịC: ẳ ABị ABịC ỵ ABC ỵ AB C: ẳ A ỵ BịA ỵ BịC þ ABC þ AB Á C: ¼ AAC þ ABC þ B Á AC þ BBC þ ABC þ AB Á C: AA ¼ and BB ¼ 0: ¼ ABC ỵ B AC ỵ ABC ỵ AB C: Computing A ẩ B ẩ Cị: ẳ A ẩ B ẩ Cị ẳ A ẩ BC ỵ BCị: ẳ ABC ỵ BCị ỵ ABC ỵ BCị: ẳ ABC ỵ ABC ỵ ABCị BCị: ẳ A BC ỵ ABC ỵ AB ỵ CịB ỵ Cị: ẳ A BC ỵ ABC ỵ ABB ỵ AB C ỵ ACB ỵ ACC: ẳ A BC ỵ ABC ỵ ABC ỵ AC B: * ABC ỵ B AC ỵ ABC ỵ AB C ẳ A BC ỵ ABC ỵ ABC ỵ AC B: ) A ẩ Bị ẩ C ẳ A ẩ B ẩ CÞ: Here, the XOR matches associative law Weakness of an ElGamal-Like Cryptosystem for Enciphering … 1229 bits zfflfflfflfflfflfflfflfflffl}|fflfflfflfflfflfflfflfflffl{ Theorem Let A = B, A È B ¼ 0000 .0000 bits zfflfflfflfflfflfflfflfflffl}|fflfflfflfflfflfflfflfflffl{ Proof According to Eq (12), A È A ¼ 0, therefore A È B ¼ 0000 .0000 bits zfflfflfflfflfflfflfflfflffl}|fflfflfflfflfflfflfflfflffl{ Theorem If A, B are both odd numbers, Aị ẩ Aị ẳ 1111 .1110 , Bị ẩ bits z}|{ Bị ẳ 1111 .1110 A ẩ Bị ẳ A ẩ Bị Proof According to Theorem 3, if A = B, then A ẩ Bị ẩ A ẩ Bị bits z}|{ ẳ 0000 .0000 From Theorem commutative law and Theorem associative law, we rewrite this equation (A ⊕ B) ⊕ ( − A ⊕ − B) = (A ⊕ − A) ⊕ (B ⊕ − B) According to Theorem 4, A ⊕ − A = B ⊕ − B bits zfflfflfflfflfflfflfflfflffl}|fflfflfflfflfflfflfflfflffl{ From Theorem 3, ðA È BÞ È A ẩ Bị ẳ 0000 .0000 ) A ẩ Bị ẳ A ẩ Bị: Theorem If A, B are even numbers, 4|A, B and 8-A; B (A ⊕ B) = ( − A ⊕ − B) Proof We assume A and B are n bits numbers, when 4|A and 8-A, bits zfflfflfflfflfflfflfflfflffl}|fflfflfflfflfflfflfflfflffl{ A ¼ à à à à 100 : bits zfflfflfflfflfflfflfflfflffl}|fflfflfflfflfflfflfflfflffl{ When 4jB and 8-B; B ¼ à à à à 100 : bits z}|{ A ẩ Bị ẳ à 000 : bits zfflfflfflfflfflfflfflfflffl}|fflfflfflfflfflfflfflfflffl{ Assume À A ¼ à à à à 100 ; bits and zfflfflfflfflfflfflfflfflffl}|fflfflfflfflfflfflfflfflffl{ À B ¼ à à à à 100 : bits z}|{ A ẩ Bị ẳ à à à 000 : bits bits zfflfflfflfflfflfflfflfflffl}|fflfflfflfflfflfflfflfflffl{ z}|{ A ẩ Bị ẩ A ẩ Bị ẳ à à à 000 È Ã Ã Ã 000 ẳ 0: ) A ẩ Bị ¼ ðÀA È ÀBÞ: 3.2 Security Analysis To Chien’s scheme, it exists a vulnerable which it combines XOR operation with two’s complement number system in computer, the related article be found in [3, 4, 7] In the follows, we describe the practical issue that two variables bitwise exclusive-or operation problem 1230 J Fang et al  à < both odd numbers; the pr ¼Â14 : à prà ¼ 12 : ðyri ; ðyri Þ2 Þ ) one odd and even numbers;  : both even numbers; the pr ¼ 14 : j For Example (Tables and 2) j The attacker Eve can easy to fake the valid parameters (yri ; ðyri Þ2 ) where ? j yri È ðyri Þ2j ðÀyri i È Àðyri Þ2 Þ She does follow steps: Step Eve sets Àr ¼ Àyri j Step Eve sets s ẳ yri ị2 Cj  mj Á ðr È sÞðmod pÞ ð15Þ ?  mj Á ðÀr È ÀsÞðmod pÞ: ? From Theorems to 5, we obtain Cj  mj Á ðr È sÞðmod pÞ  mj Á ðÀr È ÀsÞ ðmod pÞ are both odd numbers or even numbers where they matches specified rules Now, it clearly describes from Eq (15) Eve may forge successful for her attack Table Example of both odd numbers 187ị10 ẳ 10111011ị2 241ị10 ẳ 11110001ị2 187ị10 ẩ 241ị10 ẳ 01001010ị2 187ị10 ẩ 241ị10 ẳ 74ị10 87ị10 ẳ 1111111101000101ị2 241ị10 ẳ 1111111100001111ị2 187ị10 ẩ 241ị10 ¼ ð0000000001001010Þ2 ðÀ187Þ10 È ðÀ241Þ10 ¼ ð74Þ10 Table Example of both even numbers 108ị10 ẳ 01101100ị2 116ị10 ẳ 01110100ị2 108ị10 ẩ 116ị10 ẳ 00011000ị2 108ị10 ẩ 116ị10 ẳ 24ị10 108ị10 ẳ 1111111110010100ị2 116ị10 ẳ 1111111110001100ị2 108ị10 ẩ 116ị10 ẳ 00011000ị2 108ị10 ẩ 116ị10 ẳ 24ị10 ... themselves, and lead to creative and innovative applications We hope that the attendees (and readers as well) will find these results useful and inspiring to their field of specialization and future... http://www.springer.com/series/7818 Jason C Hung Neil Y Yen Kuan-Ching Li • Editors Frontier Computing Theory, Technologies and Applications 123 Free ebooks ==> www.Ebook777.com Editors Jason C Hung Department... laws and regulations and therefore free for general use The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate