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
Top Related