UNIVERSITI PUTRA MALAYSIA

CRYPTANALYSIS OF EL-GAMAL AAs CRYPTOSYSTEM

ARIF BIN MANDANGAN

IPM 2011 17

© COPYRIG

HT UPM

CRYPTANALYSIS

OF EL-GAMAL CRYPTOSYSTEM

By

ARIF BIN MANDANGAN

Thesis Submitted to the School of Graduate Studies, Universiti Putra Malaysia,

in Fulfilment of the Requirements for the Degree of Master of Science

April 2011

© COPYRIG

HT UPM

ii

Abstract of thesis presented to the Senate of Universiti Putra Malaysia

in fulfilment of the requirement for the degree of Master of Science

CRYPTANALYSIS OF EL-GAMAL CRYPTOSYSTEM

By

ARIF BIN MANDANGAN

April 2011

Chair: Muhammad Rezal Kamel Ariffin, PhD

Institute: Institute for Mathematical Research

In this research, we strengthen the security of the El-Gamal Cryptosystem, simply

referred as the -cryptosystem. The key exchange protocol of the -cryptosystem

is analogous to the Diffie-Hellman key exchange protocol. The encryption and

decryption processes of the -cryptosystem are efficient since the operations involved

are the simple addition and subtraction modulo 1.

Unfortunately, the -cryptosystem was successfully attacked by the passive adversary

attack. This attack is manipulating the weaknesses of the public key and

encrypting/decrypting keys structure. The hard mathematical problem of the -

cryptosystem has been reduced to the Discrete Logarithm Problem Modulo 1 which can

be solved by using the passive adversary attack.

© COPYRIG

HT UPM

iii

As a solution, we redefined the structure of the public key and encrypting/decrypting

keys. We propose a new secret parameter that plays an important role in the computation

of the encrypting/decrypting keys. Without the correct combination of the secret

parameters, the adversary will not be able to compute the encrypting/decrypting keys.

The Discrete Logarithm Problem Modulo 1 for the strengthened –cryptosystem is

more difficult than the previous one. Now the adversary needs to find two secret

parameters and this task could not be done via the passive adversary attack.

Furthermore we propose some attacks which aim to get the secret parameters which are

used in the calculation of the encrypting/decrypting keys. Those attacks are the

exhaustive search attack on the secret parameters and the linear Diophantine equation

attack. We show that these attacks fail to get the correct secret parameters efficiently.

Finally we redefined the hard mathematical problem of the strengthened -

cryptosystem. To break the security of the strengthened -cryptosystem, one needs to

find the private key. By choosing sufficiently large private key size, it is computationally

infeasible to reveal the value of the private key via the exhaustive search attack.

Therefore, the -cryptosystem has a potential to be a secure cryptosystem.

© COPYRIG

HT UPM

iv

Abstrak tesis yang dikemukakan kepada Senat Universiti Putra Malaysia

sebagai memenuhi keperluan untuk ijazah Master Sains

ANALISISKRIPTO BAGI SISTEMKRIPTO EL-GAMAL

Oleh

ARIF BIN MANDANGAN

April 2011

Pengerusi: Muhammad Rezal Kamel Ariffin, PhD

Institut: Institut Penyelidikan Matematik

Dalam kajian ini, kami memperkuatkan keselamatan Sistemkripto El-Gamal , secara

ringkasnya dirujuk sebagai sistemkripto- . Tatacara pertukaran kekunci bagi

sistemkripto- adalah analog kepada tatacara pertukaran kekunci Diffie-Hellman.

Proses-proses enkripsi dan dekripsi adalah cekap memandangkan operasi-operasi yang

terlibat adalah penambahan dan penolakan modulo 1 yang ringkas.

Malangnya, sistemkripto- telah berjaya diserang dengan serangan musuh pasif.

Serangan ini dibangunkan dengan memanipulasi kelemahan-kelemahan struktur kekunci

awam dan kekunci mengenkripsi/mengdekripsi. Masalah bermatematik payah bagi

sistemkripto- telah diturunkan kepada Masalah Logaritma Diskrit Modulo 1 yang

boleh diselesaikan dengan menggunakan serangan musuh pasif.

© COPYRIG

HT UPM

v

Sebagai penyelesaian, kami menakrifkan semula struktur kekunci awam dan kekunci

mengenkripsi/mengdekripsi. Kami mengajukan satu parameter sulit baharu yang

memainkan peranan penting dalam pengiraan kekunci mengenkripsi/mengdekripsi.

Tanpa gabungan parameter sulit yang betul, pihak musuh tidak akan dapat mengira

kekunci mengenkripsi/mengdekripsi.

Masalah Logaritma Diskrit Modulo 1 bagi sistemkripto- yang telah diperkuatkan

adalah lebih susah berbanding sebelum ini. Sekarang, pihak musuh perlu mencari dua

parameter sulit dan tugas ini tidak dapat dilakukan melalui serangan musuh pasif.

Seterusnya kami turut mengajukan beberapa serangan yang bertujuan untuk

mendapatkan parameter-parameter sulit yang digunakan dalam pengiraan kekunci

mengenkrip/mengdekrip. Serangan-serangan tersebut adalah serangan carian

menyeluruh terhadap parameter-parameter sulit dan serangan persamaan Diofantus

linear. Kami menunjukkan bahawa serangan-serangan ini gagal untuk mendapatkan

parameter-parameter sulit yang betul secara cekap.

Akhirnya kami menakrifkan semula masalah bermatematik payah bagi sistemkripto-

yang telah diperkuatkan. Untuk memecahkan keselamatan sistemkripto- yang telah

diperkuatkan, seseorang perlu mencari kekunci peribadi. Dengan memilih saiz kekunci

peribadi yang cukup besar, mendedahkan kekunci peribadi melalui serangan carian

menyeluruh adalah tidak dapat terlaksana secara pengiraan. Maka, sistemkripto-

adalah berpotensi untuk menjadi suatu sistemkripto yang selamat.

© COPYRIG

HT UPM

vi

ACKNOWLEDGEMENTS

First and foremo st, all praise to the almighty ALLAH S.W.T for His blesses and

merciful those enable me to enrich my knowledge.

I am sincerely grateful to my supervisor, Dr. Muhammad Rezal Kamel Ariffin, for his

patience and kindness for supervising me and his willingness to share his knowledge.

Sincere appreciation to my co-supervisors, Assoc. Prof. Dr. Mohd. Rushdan Md. Said

and Assoc. Prof. Dr. Azmi Jaafar for giving advice on my research.

To my lovely wife Mrs. Che Haziqah Che Hussin and my dearest son Muhammad

Danish Darwish, a lot of thanks and love for giving me soul, energy and moral boast to

complete this journey. To my parents, family, lecturers, Prof. Dr. Mohd. Harun Abdullah

and Assoc. Prof. Dr. Jumat Sulaiman, thank you very much for giving continuous moral

support. Also to my friends especially Zahari Mahad, Mrs. Aniza Abd. Ghani and Mohd.

Azlan Daud, thanks for supporting me along this journey.

I want to thank Universiti Putra Malaysia especially Institute for Mathematical Research

for providing good research environment. Last but not least, a lot of appreciation to

Universiti Malaysia Sabah and Ministry of Higher Education (MOHE) Malaysia for

encouragement and financial support.

Thanks for this amazing journey. May Allah S.W.T blessing all of you. Wassalam.

© COPYRIG

HT UPM

vii

I certify that an Examination Committee has met on 07 April 2011 to conduct the final

examination of Arif bin Mandangan on his thesis entitled “Cryptanalysis on the El-

Gamal cryptosystem” in accordance with the Universities and University

Colleges Act 1971 and the Constitution of the Universiti Putra Malaysia [P.U.(A) 106]

15 March 1998. The Committee recommends that the student be awarded the Master of

Science.

Members of the Examination Committee were as follows:

Siti Hasana Sapar, PhD

Faculty of Science

Universiti Putra Malaysia

(Chairperson)

Zanariah Abdul Majid, PhD

Faculty of Science

Universiti Putra Malaysia

(Internal Examiner)

Eddie Shahril Ismail, PhD

Faculty of Science and Technology

Universiti Kebangsaan Malaysia

(External Examiner)

Hailiza Kamarul Haili, PhD

Associate Professor

School of Mathematical Sciences

Universiti Sains Malaysia

(External Examiner)

SHAMSUDDIN SULAIMAN, PhD

Professor and Deputy Dean

School of Graduate Studies

Universiti Putra Malaysia

Date:

© COPYRIG

HT UPM

viii

This thesis was submitted to the Senate of Universiti Putra Malaysia and has been

accepted as fulfillment of the requirement for the degree of Master of Science. The

members of Supervisory Committee were as follows:

Muhammad Rezal Kamel Ariffin, PhD

Faculty of Science

Universiti Putra Malaysia

(Chairman)

Mohamad Rushdan Md. Said, PhD

Associate Professor

Faculty of Science

Universiti Putra Malaysia

(Member)

Azmi Jaafar, PhD

Associate Professor

Faculty of Computer Science and Information Technology

Universiti Putra Malaysia

(Member)

HASANAH MOHD GHAZALI, PhD

Professor and Dean

School of Graduate Studies

Universiti Putra Malaysia

Date:

© COPYRIG

HT UPM

ix

DECLARATION

I declare that the thesis is my original work except for quotations and citations which

have been duly acknowledged. I also declare that it has not been previously and is not

concurrently, submitted for any other degree at Universiti Putra Malaysia or at any other

institution.

ARIF BIN MANDANGAN

Date:

© COPYRIG

HT UPM

x

TABLE OF CONTENTS

Page

ABSTRACT ...................................................................................................................... ii

ABSTRAK ....................................................................................................................... iv

ACKNOWLEDGEMENTS ............................................................................................ vi

APPROVAL ................................................................................................................... vii

DECLARATION ............................................................................................................. ix

LIST OF TABLES ........................................................................................................ xiii

LIST OF FIGURES ...................................................................................................... xiv

LIST OF ABBREVIATIONS ....................................................................................... xv

CHAPTER

1 INTRODUCTION .................................................................................... 1

1.1 Cryptography ....................................................................................... 1

1.2 Public Key Cryptography .................................................................... 4

1.2.1 Diffie-Hellman Key Exchange ................................................... 4

1.2.2 El-Gamal Cryptosystem ............................................................ 6

1.2.3 RSA ........................................................................................... 8

1.2.4 Elliptic Curve Cryptography ..................................................... 9

1.3 Hard Mathematical Problem ............................................................. 10

1.4 Problem Statement ............................................................................ 12

1.5 Research Objective............................................................................. 12

1.6 Scope and Limitation of the Study .................................................... 13

1.7 Overview of the Thesis ...................................................................... 13

2 MATHEMATICAL BACKGROUND ................................................. 14

2.1 Introduction ........................................................................................ 14

2.2 Modular Arithmetic ........................................................................... 14

2.3 Modulo One Arithmetic .................................................................... 16

2.4 Parallelogram Law ............................................................................ 18

© COPYRIG

HT UPM

xi

3 CHAOS THEORY ................................................................................. 19

3.1 Chaos Theory .................................................................................... 19

3.1.1 Lyapunov Exponent ................................................................. 20

3.2 Chaotic Cryptosystems ..................................................................... 20

3.2.1 Symmetric chaotic cryptosystems ............................................. 21

3.2.2 Asymmetric chaotic cryptosystems .......................................... 22

3.3 The - Transformation ...................................................................... 24

3.3.1 Prime Orbit Theorem ............................................................... 25

4 EL-GAMAL CRYPTOSYSTEM ................................................ 29

4.1 Background ....................................................................................... 29

4.2 -Cryptosystem (2009) ................................................................. 38

4.3 Passive Adversary Attack ................................................................. 44

4.4 -Cryptosystem (2010) ................................................................. 49

4.5 -Cryptosystem (2010) Hard Mathematical Problem .................. 59

5 CRYPTANALYSIS ON -CRYPTOSYSTEM (2010) .................. 62

5.1 Introduction ....................................................................................... 62

5.2 Passive Adversary Attack ................................................................. 62

5.3 Extended Passive Adversary Attack ................................................. 66

5.4 Cryptanalysis on Secret Parameters .................................................. 68

5.4.1 Parameter ........................................................................ 69

5.4.2 Parameter ............................................................................. 70

5.4.3 Parameter ....................................................................... 71

5.4.4 Linear Diophantine equation with three variables ................... 71

5.5 Discussion ......................................................................................... 79

© COPYRIG

HT UPM

xii

6 CONCLUSION AND FUTURE WORK ............................................. 80

6.1 Conclusion ......................................................................................... 80

6.2 Future Work ....................................................................................... 81

BIBLIOGRAPHY .......................................................................................................... 82

APPENDIX ..................................................................................................................... 87

BIODATA OF STUDENT ............................................................................................. 94

LIST OF PUBLICATIONS ........................................................................................... 95