In e na ional Jou nal o Ne wo k Secu i y & I s Applica ions (IJNSA) Vol. 11, No.3, May 2019
DOI: 10.5121/ijnsa.2019.11305 53
METHODS TOWARD ENHANCING RSA ALGORITHM
: A SURVEY
Eng . Shaheen Saad Al-Kaabi and D . Sami B ahim Belhaoua i
College o Science and Enginee ing, Hamad Bin Khali a Uni e si y (HBKU),
Doha, Qa a
ABSTRACT
C yp og aphy de ines di e en me hods and echnologies used in ensu ing communica ion be ween wo
pa ies o e any communica ion medium is secu e, especially in p esence o a hi d pa . This is achie ed
h ough he use o se e al me hods, such as enc yp ion, dec yp ion, signing, gene a ing o pseudo- andom
numbe s, among many o he s. C yp og aphy uses a key, o some so o a passwo d o ei he enc yp o
dec yp a message ha needs o be kep sec e . This is made possible using wo classes o key-based
enc yp ion and dec yp ion algo i hms, namely symme ic and asymme ic algo i hms. The bes known and
he mos widely used public key sys em is RSA. This algo i hm comp ises o h ee phases, which a e he key
gene a ion phase, enc yp ion phase, and he dec yp ion phase. Owing o he ad ancemen in compu ing
echnology, RSA is p one o some secu i y isks, which makes i less secu e. The ollowing pape p e iew
di e en p oposals on di e en me hods used o enhance he RSA algo i hm and inc ease i s secu i y. Some
o hese enhancemen s include combining he RSA algo i hm wi h Di ie-Hellman o ElGamal algo i hm,
modi ica ion o RSA o include h ee o ou p ime numbe s, o line s o age o gene a ed keys, a secu ed
algo i hm o RSA whe e he message can be enc yp ed using dual enc yp ion keys, e c.
K
EYWORDS
C yp og aphy, RSA Algo i hm, Enc yp ion, Dec yp ion, C yp osys em, Secu i y, Public Key, P i a e Key
1. I
NTRODUCTION
The use o c yp og aphy o conceal in o ma ion da es back housands o yea s ago. Ini ially,
c yp og aphy was applied in he secu ing o mili a y sec e s. Fo ins ance, o communica e o his
commande s and soldie s in he ba le ield, Julius Caesa used Caesa ciphe ex o conceal
in o ma ion om he enemies o unau ho ized pa ies. Since hen, he encoded messages ha e
been used by go e nmen , p i a e en i ies, and mili a ies a ound he wo ld o p o ec sensi i e
in o ma ion. F om hese applica ions, c yp og aphy can be de ined as me hods o echniques used
in ensu ing ha exchange o in o ma ion be ween wo pa ies emain secu e, and he in o ma ion
i sel emains con iden ial, au hen ic, and main ains high le el o in eg i y [8].
This is achie ed h ough he use o se e al me hods, such as enc yp ion, dec yp ion, signing,
gene a ing o pseudo- andom numbe s, among many o he s. C yp og aphy is ancho ed in ou
majo p inciples whose main objec i es include ensu ing con iden iali y, da a in eg i y,
au hen ici y, and non- epudia ion. C yp og aphy ensu es con iden iali y by de ining a se o ules
ha limi access o ce ain in o ma ion. On he o he hand, da a in eg i y is upheld by ensu ing
consis ency and accu acy o da a du ing i s en i e li e-cycle. On he o he hand, au hen ica ion
helps o ensu e ha he in o ma ion o da a is ue and is om he expec ed sou ce. Unde non-
epudia ion, c yp og aphy ensu es ha an au ho o a gi en s a emen o piece o da a canno deny
i . C yp og aphy he e o e plays a c ucial ole in ensu ing ha he da a is con iden ial, au hen ic,
In e na ional Jou nal o Ne wo k Secu i y & I s Applica ions (IJNSA) Vol. 11, No.3, May 2019
54
and main ains i s in eg i y while on ansi o s o age. This is achie ed h ough he con e sion o
da a un o di e en o ms ha a e incomp ehensible (ciphe ex o code). The p ocess h ough
which da a is con e ed in o ciphe ex is called enc yp ion, while he p ocess h ough which he
ciphe ex con e ed o comp ehensible in o ma ion (plain ex ) is called dec yp ion. Bo h
enc yp ion and dec yp ion p ocesses a e done using sec e in o ma ion such as passwo ds o keys.
1.1. S
YMMETRIC AND
A
SYMMETRIC CRYPTOGRAPHY
As indica ed in he discussion abo e, c yp og aphy uses a key, o some so o a passwo d o
ei he enc yp o dec yp a message ha needs o be kep sec e . This is made possible using wo
classes o key-based enc yp ion and dec yp ion algo i hms, namely symme ic, also known as
sec e -key, and asymme ic, which is also known as public –key.
1.1.1. S
YMMETRIC KEY CRYPTOGRAPHY
Be o e he 1970s, he symme ic key enc yp ion, also known as he sec e -key enc yp ion, o
con en ional sys em was he only enc yp ion echnology in use, and s ill, emain by a he mos
widely used me hod o enc yp ion. Be o e he ad en o compu e s, he ciphe ex used in
symme ic key enc yp ion was called he classical enc yp ion algo i hms. Cu en ly, and wi h he
ad en o compu ing echnology, symme ic enc yp ion uses bi s and by es as he enc yp ion
keys, oge he wi h a ious enc yp ion algo i hms o ans o m plain ex in o ciphe ex . The
eco e y p ocess o plain ex om he ciphe ex in symme ic key c yp og aphy is done using
he same key used in enc yp ion, and a di e en dec yp ion algo i hm. This is made possible by
sha ing he sec e key be ween he sende and he ecei e . This also implies ha in case a hi d
pa y gains access o he key, he/she can easily dec yp he in o ma ion. As such, i is c ucial o
ensu e ha he key is kep as sec e as possible. The igu e below illus a es he enc yp ion and
dec yp ion p ocess in symme ic key c yp og aphy:
Figu e 1. Symme ic key C yp og aphy
Some o he mos common symme ic key algo i hms include Da a Enc yp ion S anda d (DES),
T iple Da a Enc yp ion S anda d (TRIPLEDES), Ad anced Enc yp ion S anda d (AES), RC2,
RC4, RC5, RC6, Blow ish, and Two ish. T iple DES algo i hm was de eloped in esponse o he
inc ease in he compu a ional powe ha made b u e- o ce a acks easible. As such, his
algo i hm was designed o maximize he secu i y o DES agains such a acks. On he o he hand,
In e na ional Jou nal o Ne wo k Secu i y & I s Applica ions (IJNSA) Vol. 11, No.3, May 2019
55
AES make i possible o selec a key wi h ei he 128, 192, o 256 bi leng h. Each o hese keys
enc yp s using di e en ounds o p ocessing; he 128, 192, and 256 bi key enc yp in 10, 12, and
14 ounds o p ocessing espec i ely.
1.1.2. A
SYMMETRIC KEY CRYPTOGRAPHY
Unlike symme ic key c yp og aphy, asymme ic key c yp og aphy uses wo sepa a e keys, whe e
one is a p i a e key o da a dec yp ion, and he o he one is a public key o da a enc yp ion. This
implies ha he public key is published o anyone o see, bu he p i a e key is kep a sec e . As
such, anybody wi h access o he public key enc yp s he da a, bu only he in ended pe son (wi h
p i a e key) can dec yp he da a. The igu e below is an illus a ion o how asymme ical
c yp og aphy wo ks:
Figu e 2. Asymme ic key C yp og aphy
One o he key ad an ages o asymme ic c yp og aphy as compa ed o symme ic c yp og aphy
is he ac ha asymme ic elimina es he need o he sende and he ecei e o sha e he p i a e
key. This he e o e means ha only he public key is ansmi ed du ing he communica ion
be ween he wo pa ies. Some examples o a eas in which asymme ic is applied include
Elgamal, RSA, Di ie-Hellman, and DSA.
2. RSA
A
LGORITHM
A he momen , he bes known and he mos widely used public key sys em is RSA. I was
de eloped in 1978 by Ronald Ri es , Adi Shami , and Leona d Adleman. RSA is based on
numbe heo y, was he i s algo i hm known o be sui able o signing as well as enc yp ion, and
one o he i s g ea ad ances in public key enc yp ion. RSA is a public key c yp og aphic
sys em ha uses he concep o numbe heo y. I s secu i y, he e o e, depends on he complexi y
o p ime ac o iza ion o la ge numbe s [14], which is a well-known ma hema ical p oblem wi h
no known e ec i e solu ion. This makes RSA one o he mos widely used echnique o
In e na ional Jou nal o Ne wo k Secu i y & I s Applica ions (IJNSA) Vol. 11, No.3, May 2019
56
asymme ic key c yp og aphy in enc yp ion and digi al signa u e s anda ds. Gene ally, RSA
algo i hm comp ises o h ee phases, which a e he key gene a ion phase, enc yp ion phase, and
he dec yp ion phase.
2.1. K
EY
G
ENERATION
The key gene a ion phase comp ises o a p ocess h ough which c yp og aphic keys a e
gene a ed, be o e being used o enc yp ion and dec yp ion o da a. Bo h p i a e and public key
a e gene a ed and used in c yp og aphy in RSA algo i hm which is a ailable o e e yone by
means o a digi al ce i ica e. Any da a o be sen using RSA algo i hm is enc yp ed using he
public key. Howe e , i is only a pe son wi h a co esponding public key can be able o dec yp
he da a using he p i a e key. The s eps in ol ed in in key gene a ion a e as ollows:
a. Choose wo di e en p ime numbe s p and q .
b. Calcula e he common module n such ha n = p . q.
c. Calcula e he Eule ’s
d. Selec in ege e which is he enc yp ion (public) key such ha :
e. Calcula e d is he dec yp ion (p i a e) key such ha
. So, he public key is PU = [ e , n ] , and he p i a e key is PR = [ d , n ].
I is necessa y o gene a e la ge andom p imes in se ing up he RSA algo i hm. In essence,
Randomized Polynomial Time Mon e Ca lo app oach, such as SOLOVAY-STRASSEN, o
MILLER-RABIN app oach can be used o es whe he he la ge andom numbe s selec ed a e
p ime numbe s (p imali y es ing algo i hms). Randomized Polynomial Time Mon e Ca lo
algo i hms a e as p imali y es e ha can help in es ing he selec ed numbe s in polynomial in
in log2 n [18]. P ime numbe heo em (() ≈ / ln, whe e ()= p imes ≤ ) can be used in his
case o de e mine he numbe o andom in ege s ha need o be es ed be o e inding p ime. I p
is conside ed as a andomly selec ed in ege be ween 1 and N, hen he p obabili y ha p is p ime
is 1/ ln. So, we can adequa ely gene a e a la ge andom “p obable P ime” [18].
2.2. E
NCRYPTION
The p ocess o encoding a message is de ined by he enc yp ion scheme used. In an enc yp ion
scheme, he message o he in o ma ion ha need o be sen is p esen ed in plain ex o ma . The
plain ex message is hen enc yp ed using an enc yp ion algo i hm o gene a e ciphe ex ha can
only be comp ehensible i dec yp ed. The plain ex is enc yp ed in blocks, each block ha ing a
alue less han common module n. The enc yp ion algo i hm is gi en by:
C = M
e
mod n
Whe e: M : Block o plain ex
C : Block o ciphe ex
e : Public key
2.3. D
ECRYPTION
The p ocess h ough which ciphe ex is decoded o ge he plain ex message in a o ma ha can
be comp ehended is called dec yp ion. Only indi iduals wi h access o he p i a e key can
dec yp he da a in RSA algo i hm. As such, anybody else wi hou he p i a e key can in e cep
In e na ional Jou nal o Ne wo k Secu i y & I s Applica ions (IJNSA) Vol. 11, No.3, May 2019
57
he message bu canno comp ehend he ex wi hou dec yp ing i using he p i a e key. The
dec yp ion algo i hm is gi en by:
M = C
d
mod n
Whe e: M : Block o plain ex
C : Block o ciphe ex
d : P i a e key
Figu e 3. Flow Design o RSA Algo i hm
2.4. RSA
A
LGORITHM LIMITATIONS
:
Acco ding o Gup a and Sha ma, some o he limi a ions associa ed wi h RSA include he ac
ha i any o p, q, e, and d is known, hen he o he alues can be calcula ed, and he e o e,
elimina ing he sec ecy [1]. Also, RSA equi es ha he leng h o he message be less han bi
leng h, o he wise he algo i hm is likely o ail. Compa ed o o he symme ic c yp og aphic
sys ems, RSA is ela i ely slow, owing o he ac ha i uses public key. Also, he size o he
p oduc o he wo p ime numbe s selec ed (N=P X Q) limi s he leng h o he plain ex ha can
be enc yp ed, as well as he ac ha ini ializa ion o each o he RSA p ocess equi ed andom
selec ion o wo la ge p ime numbe (P and Q) [1].
Ano he 2013 s udy by Pa ida and Bha iya iden i ied se e al limi a ions associa ed wi h RSA
[3]. These included he issue o speed as desc ibed by Gup a and Sha ma and compu a ional cos
due o he need o wo di e en keys. The e is also he issue o loss o p i a e key, which may
b eak he secu i y. He e, RSA is c i icized based on i s applica ion o p i a e key [3]. Pa ida and
Bha iya poin ou ha du ing he dec yp ion p ocess, he p i a e key is used, as such, i any
unau ho ized pe son knows he alue o he p i a e key, hen he en i e secu i y o RSA algo i hm
is comp omised [3]. O he esea che s such as Minni e al a gues ha RSA, as i
In e na ional Jou nal o Ne wo k Secu i y & I s Applica ions (IJNSA) Vol. 11, No.3, May 2019
58
is, is p one o ma hema ical ac o iza ion a acks and he e o e needs u he enhancemen s [4]. In
line wi h his, Jaju and Chowhan also obse ed ha he execu ion ime o RSA algo i hm was
ela i ely highe as compa ed o ha o o he algo i hms [2].
Panda and Cha opadhyay ound ou ha RSA algo i hm was easy o ac o ize since modulo n
used is he p oduc o wo p ime numbe s only and he e o e making i easy o ob ain he
dec yp ed o iginal message [5]. O he esea che s who pinpoin ed se e al limi a ions in ega d o
RSA algo i hm included Ma hu e al.[6] who del ed in o imp o ing he model by enhancing
secu i y and elimina ion o edundan messages using K-nea es neighbo algo i hm.
2.5. F
ACTORING
RSA
MODULUS
Fac o ing he public modulus is he mos e iden way o a ack RSA c yp osys em. Some o he
algo i hms ha a e conside ed o be he mos e ec i e on ac o ing e y la ge numbe s include
Numbe Field Sie e (NFS), Quad a ic Sie e (QS), and Ellip ic Cu e Fac o ing Algo i hm
(ECFA) [18]. Till he mid-1990s, he Quad a ic Sie e was he mos used algo i hm. Howe e , he
Numbe Field Sie e, which is he ecen ly de eloped algo i hm o he h ee, was p o en o be he
as es in e m o i s asymp o ic unning ime [18].
In he ea ly 1990s, RSA publishes a se ies o challenges and se aluable p ices in a ange o
10k$ o 200k $ o ac o ing algo i hms on he In e ne . In his ega d, a s udy by Kleinjung e
al.(2009) poin s ou some implica ion o RSA ollowing he use o NFS o ac o ou he a
numbe wi h 768-bi and RSA -768[17]. The i s s ep in his p ojec was he selec ion o
polynomial. This ook hal a yea and 80 p ocesso s. The nex s ep was sie ing using hund eds o
machines, ollowed by p epa a ion o he sie ing da a o he ma ix s ep, which ook a couple o
weeks on a ew p ocesso s be o e he inal s ep o debugging. Fo 2 1039 -1 he ma ix s eps we e
pe o med on di e en clus e s, while he majo pa s was compu ed a wo di e en loca ions on
ou clus e s ha we e unning in pa allel o each o he . Whe e he compu a ion in ol ed a
consecu i e sequence o ma ix ime’s ec o mul iplica ion, he block wiedemann algo i hm o
he ma ix was used o acili a e i . As a esul o inc eased independen pa alleliza ion ha
ensued, a numbe o challenges ha needed o be add essed be o e handing mo e complex issues
we e encoun e ed. The i s s ep was o show how lexibili y could be a ained in he numbe , as
well as di e en clus e s could con ibu e o achie ing a scalable solu ion. This helped in sol ing
a ma ix s ep ha would ha e o he wise been nine imes ha de .
App oxima ely one e aby e o memo y was equi ed du ing one o he sub-s eps. This implied
ha much la ge ma ices we e wi hin each in he nea u u e o he ma ix equi ed o a 1024-
bi NFS ac o iza ion
Fac o iza ion o RSA-768 was done using he Mo ison-B illha app oach. The pape also
desc ibes he a ious s eps equi ed o sol e NFS. The i s s ep in his case was o ac o a
composi e in ege n. This was achie ed by de e mining he solu ion o he in ege (x; y) o he
cong uence o squa e x2 º y2 mod n. A his poin , he au ho only hoped ha n had been ac o ed
by w i ing i as a p oduc GCD o (x –y, n).
The chances o inding a non- i ial ac o o n using his me hod o a andom pai a e a a ound
0.5[17]. The Mo ison-B illha app oach sol es he equa ion x2 º y2 mod n by combining he
cong uencies o smoo h squa es. The pape also comp ises o discussion on he implica ion o
moduli la ge han RSA-768. To assis in comple ion o he p ojec , he au ho sough he
assis ance o well-in o med con ibu o s who dedica ed hei ime and compu a ional esou ces o
see he p ojec h ough. This is despi e he ac ha i was possible o un NFS as a BOINC
In e na ional Jou nal o Ne wo k Secu i y & I s Applica ions (IJNSA) Vol. 11, No.3, May 2019
59
p ojec . This in e u n allowed he au ho s o a ge a easonable comple ion da e ha is easily
manageable despi e he in ensi e o e sie ing. The au ho also insis s on communica ion o a ai
amoun o da a o he cen al s o age a ea. This was based on he ac ha mos clien s ail o
communica e du ing such p ojec . This can be achie ed h ough o ganiza ional e o s ha may
help in occasional eco e y om e o s ha may esul s om unplugged ne wo k cables, se e s
ha ha e been swi ched o , o aul y aids and cons an ly inc easing he backup d i es. [17].
Fo ha , i is assumed nowadays ha 1024 bi numbe will be ac o ed by 2020 and will be no
secu ed enough o s and agains he ac o iza ion a acks. As a esul , i is belie ed ha using
2048 bi key leng h in RSA should be secu ed o a longe ime [8].
3. E
NHANCEMENT PROPOSALS FOR
RSA
ALGORITHM
3.1. A
HYBRID ENCRYPTION ALGORITHM BASED ON
RSA
AND
D
IFFIE
-H
ELLMAN
.
In hei wo k, Gup a and Sha ma sugges ed a new hyb id enc yp ion algo i hm based on RSA and
Di ie-Hellman algo i hm o add ess some o he majo secu i y issues iden i ied in he RSA
algo i hm [1]. The Di ie-Helaman algo i hm (DH) was ounded by Whi ield Di ie and Ma in
Hellman in 1976. I is as ounding and ex ensi e algo i hm ha has been applied on he in e ne o
secu e di e en connec i i y p o ocols. Examples o such p o ocols include SSL, IPsec, and SSH
[1, 9, 11]. The me hod o DH lies on secu ely in e changing a sha ed sec e be ween wo pa ies
on a public ne wo k and each pa y has public and p i a e key in o de o co espond on a sha ed
sec e alue [10]. The main aim o his p oposal in combining hese wo algo i hms is o achie e
be e and mo e secu e c yp osys em, aking ad an age o he secu i y o public key sys em and
he speed o he sec e key sys em. The s eps in ol ed in he algo i hm included:
1. Choose wo la ge p ime numbe s P and Q.
a. Calcula e N = P x Q.
b. Selec public key ( Enc yp ion key ) E such ha i is no a ac o o ( P - 1 ) and ( Q -
1 ).
c. Selec he p i a e key ( Dec yp ion key ) D such ha he ollowing equa ion is ue (
D x E ) mod ( P – 1 ) x ( Q – 1 ) = 1.
d. Suppose R, S and G is au oma ic gene a ed p ime cons an s.
e. And pu he alue o E and D om abo e as sec e numbe such ha A=E and B=D.
2. Now calcula e ollowing as public numbe
X = GA mod R
Y = GB mod R
3. Calcula e session key wi h o mula
KA = YA mod R
KA = (GB mod R) A mod R
KA = (GB)A mod R
KA = GBA mod R.
KB = XB mod R
KB = (GA mod R)B mod R
KB = (GA)B mod R
KB = GAB mod R
Such ha KA = KB = K.
The sende will use K o he enc yp ion o he plain ex PT. The sende will hen send he
enc yp ed PT o he ecei e as ciphe ex CT. Once he ecei e ecei ed he ciphe ex CT,
he/she uses k o dec yp i o he eco e y o he plain ex PT.
In e na ional Jou nal o Ne wo k Secu i y & I s Applica ions (IJNSA) Vol. 11, No.3, May 2019
60
Figu e 4. Flow design o a hyb id RSA & Di ie-Hellman algo i hm
This hyb id algo i hm ends o be easy o use s o communica e secu ely o e he public
ne wo k, especially o messages o iles ha need o be exchanged con iden ially. Au ho s
men ioned ha he usabili y o hei p oposed algo i hm is applied wi h ew concep s and ideas
ha can be ex ended in he u u e. The e iciency can be e ised in e m o ime complexi y o
be e unc ionali y o he algo i hm, also he key size used o enc yp ion and dec yp ion can be
u he educed o be e pe o mance [1].
3.2. C
OMBINATION
O
F
RSA
A
ND
E
LGAMAL
A
LGORITHM
.
Iswa i also p oposed ano he enhancemen o he RSA algo i hm by combining i wi h he
ElGamal algo i hm [7]. ElGamal is a well-known public key c yp osys em algo i hm. Ini ially, i
was used only o digi al signa u e. La e on, i has been de eloped and modi ied in o de o be
used o enc yp ion and dec yp ion [7]. The secu i y s eng h o he ElGamal algo i hm lies on he
di icul y o compu ing he disc e e loga i hm [13]. I s pai o key gene a ion can be summa ized
as ollows:
1. Choose a andom p ime numbe p
2. Choose wo andom numbe , g and x , whe e ( g < p ) and ( x < p ) .
3. Calcula e y = g
x
mod p.
4. y is he public key and x is he p i a e key
In he Au ho p oposal, 256-bi p ime numbe s we e used o he sake o dec easing he
compu a ional ime equi ed o he key gene a ion ins ead o 1024-bi p ime numbe s ha a e
used in he o iginal RSA algo i hm. By combining RSA and ElGamal, he secu i y ac o s and
In e na ional Jou nal o Ne wo k Secu i y & I s Applica ions (IJNSA) Vol. 11, No.3, May 2019
61
complexi y is main ained e en i small bi p ime numbe s a e used due o bo h ac o iza ion and
disc e e loga i hm calcula ion di icul ies. The ollowing is he summa y o he algo i hm:
1. Selec wo p ime numbe s p and q
2. = p . q
3. Ø ( ) = (p -1).(q-1)
4. Gene a e Random numbe PK ( enc yp ion key ), whe e GCD (PK, Ø ( )) = 1.
5. Compu e dec yp ion key SK = PK-1 mod Ø ( ).
Now, ElGamal algo i hm will be used in he p ocess o he key gene a ion :
6. PK = g , and SK = x
7. Gene a e a andom numbe pEl , whe e ( PK < pEl ) and ( SK < pEl ).
8. Calcula e public key o ElGamal algo i hm ( y = PK
SK
mod pEl ) . whe e GCD (y, Ø( ))
= 1.
9. Recalcula e p i a e key again o RSA algo i hm ( SK = y-1 mod Ø( ) ).
3.3. M
ODIFIED
RSA
CRYPTOSYSTEM BASED ON OFFLINE STORAGE AND PRIME NUMBER
.
Pa ida and Bha iya also p oposed new algo i hm concep o imp o e he pe o mance o he
adi ional RSA algo i hm du ing exchange o in o ma ion be ween wo pa ies ac oss a ne wo k
[3]. The p oposed modi ica ion comp ised o he a chi ec u al design and an enhanced o m o
RSA algo i hm h ough he use o a hi d p ime numbe o make a modulus n which is no easily
decomposed by in ude s [3]. The ollowing is he summa y o he p oposed algo i hm:
1. Selec he andom alues p, q and
2. Calcula e ( n = p . q . ).
3. Calcula e Ø (n) = (p-1).(q-1).( -1).
4. Calcula e e such ha GCD (e, Ø (n)) =1 and 1<e<Ø(n).
5. Enc yp he message M whe e M<n and enc yp wi h public key e such ha C= Me mod n.
6. Calcula e p i a e key d = e
-1
(mod Ø (n)).
7. Dec yp he message M such ha M=C
d
mod n.
The s o age o he keys o he p oposed sys em is done o line be o e he p ocess is ini ialized.
This leads o enhancemen o he speed equi ed o enc yp ion and dec yp ion, as compa ed o
he adi ional RSA [3]. Two ables we e c ea ed in a da abase engine o ha eason o sa e he
keys. The i s able con ains he alue o p, q, n1, and Ø (n), while he second able con ains he
alue o e, d, , e1, and d1. The ollowing igu e shows he mechanism o e ching he alues
om/ o he da a base.
In e na ional Jou nal o Ne wo k Secu i y & I s Applica ions (IJNSA) Vol. 11, No.3, May 2019
68
he MRSA in ela ion o RSA indica ed ha he ime o key gene a ion o MRSA is highe han
ha o he adi ional RSA algo i hm. The inc eased amoun o ime equi ed o key gene a ion
means an inc ease in he ime equi ed o he a acke o b eak he sys em.
This, he e o e, is o g ea impo ance in enhancing he secu i y h ough inc eased complexi y as
compa ed o he adi ional RSA. As such, as compa ed o he adi ional RSA, MRSA is mo e
secu e due o i s added le el o complexi y.
3.10. E
NCRYPTION
A
LGORITHM
U
SING
D
UAL
M
ODULUS
In he bid o add ess he weakness obse ed in RSA algo i hm, Goel, (2017) p oposed a no el
RSA-based algo i hm capable o esis ing a acks ha a e common in RSA [16]. Some o he key
ea u es o his algo i hm include a double mod ope a ion-based enc yp ion using wo p i a e
keys, a double mod ope a ion-based dec yp ion using wo public key, and mo e han wo la ge
p ime numbe s o gene a ing modulus alue. The h ee men ioned ea u es a e aimed a
enhancing he secu i y o he message by inc easing he ime equi ed o key gene a ion,
enc yp ion, and dec yp ion. The dual modulus scheme is used oge he wi h he wo la ge public
and p i a e keys, and he e o e making i ha de o ac o ize hem o gain access o he p i a e key
[16].
Key Gene a ion
- Fou andom p ime numbe s p1 and p2, q1 and q2 a e selec ed
- Compu e n1 =p1 x p2 and n2 = q2 x q2
- Compu e Ø1 = LCM ((p 1 -1), ((p2-1)) and φ2 = LCM ((q1-1), (q2-1))
- Two in ege s e1 and e2 a e selec ed such ha 1 < e1< φ1 and 1<e2
- Sec e exponen s d1 and d2 a e compu ed such ha e1 x d1 mod φ1 = 1 and e2 x d2 mod
φ2 = 1.
- The public key is (n1, n2, e1, e2) and he p i a e key is (n1, n2, d1, d2).
- Values d1, d2, p1, p2… q1, q2… φ1 and φ2 a e kep sec e .
Enc yp ion
- Sende Ob ain he ecipien ’s public key (n1, n2, e1, e2).
- Plain ex message ep esen ed as a posi i e in ege m (0<= m < n1 < n2)
- Compu es he ciphe ex c = ((m
e1
mod n1)
e2
mod n2).
- Sends he ciphe ex c o he ecei e
Dec yp ion
- The in e media e alue C2 can be e alua ed as
C2
d2
mod n2 = (C1
e2
mod n2) d2 mod n2 = C1 (by RSA) (Since C2 is e e sible ciphe
ex )
- Now, C1
d1
mod n1 = (m
e1
mod n1)
d1
mod n1 = m (by RSA) (Since C1 is e e sible)
The wo algo i hms ha e simila i ies and di e ences. Some o he simila i ies be ween he wo
include he ac ha bo h o hem a e asymme ic algo i hms using wo pai s o keys. One o he
keys is used o enc yp he da a such ha i can only be dec yp ed using he o he pai . Ano he
simila i y is ha bo h algo i hms use a simila p ocess o gene a e he key. Howe e , hey canno
gene a e om each o he . The ollowing is a summa y o he p oposed algo i hm [16].
On he o he hand, some o he di e ences include he ac ha RSA uses wo di e en keys o
enc yp and dec yp while he p oposed algo i hm uses ou di e en keys o he same. This
In e na ional Jou nal o Ne wo k Secu i y & I s Applica ions (IJNSA) Vol. 11, No.3, May 2019
69
inc eases he complexi y o he algo i hm, which in e u n enhances i s secu i y. The use o dual
p i a e keys helps o ensu e ha i an in ude de ec s a single p i a e key e en hen i will be
impossible o dec yp he ciphe ex , as he second key is s ill secu e. In addi ion, i a b u e o ce
a ack is launched on he wo keys, he ime akes o compu e key will inc ease exponen ially.
This means ha he double p ocess used in he p oposed amewo k inc eases he complexi y o
ac o iza ion. In case an a acke de ec s a single key, i will s ill be impossible o dec yp he
message [16].
4. C
ONCLUSION
upholding he con iden iali y, in eg i y, a ailabili y, and non- epudia ion o in o ma ion and da a
sen ac oss ne wo ks equi es mo e han jus c yp og aphy. O e he yea s, he RSA algo i hm has
been applied in di e en a eas o enhance he secu i y o in o ma ion h ough enc yp ion and
dec yp ions. Howe e , he ad ancemen in compu ing echnology and hacking me hods ha e
ende ed he o iginal RSA algo i hm ine ec i e in da a p o ec ion. I is in ligh o his ha
di e en esea che s ha e ocused on he me hod o enhance he RSA algo i hm h ough he
addi ion o mo e complexi y o he algo i hm.
5. A
CKNOWLEDGMENTS
A bigges hanks o all acul y o he college o science and enginee ing in Hamad bin Khali a
Uni e si y (HBKU), especially o D . Sami B ahim Belhaoua i o his usual mo i a ion and
suppo . And special hanks o my amily who a e he g ea suppo e s du ing my mas e ’s deg ee
jou ney.
R
EFERENCES
[1] S. Gup a and J. Sha ma, "A hyb id enc yp ion algo i hm based on RSA and Di ie-Hellman," 2012
IEEE In e na ional Con e ence on Compu a ional In elligence and Compu ing Resea ch, Coimba o e,
2012, pp. 1-4. doi: 10.1109/ICCIC.2012.6510190
[2] S. A. Jaju and S. S. Chowhan, "A Modi ied RSA algo i hm o enhance secu i y o digi al signa u e,"
2015 In e na ional Con e ence and Wo kshop on Compu ing and Communica ion (IEMCON),
Vancou e , BC, 2015, pp. 1-5. doi: 10.1109/IEMCON.2015.7344493
[3] R. Pa ida and R. Bha iya, "Modi ied RSA c yp osys em based on o line s o age and p ime
numbe ," 2013 IEEE In e na ional Con e ence on Compu a ional In elligence and Compu ing
Resea ch, Ena hi, 2013, pp. 1-6. doi: 10.1109/ICCIC.2013.6724176
[4] R. Minni, K. Sul ania, S. Mish a and D. R. Vincen , "An algo i hm o enhance secu i y in RSA," 2013
Fou h In e na ional Con e ence on Compu ing, Communica ions and Ne wo king Technologies
(ICCCNT), Ti uchengode, 2013, pp. 1-4. doi: 10.1109/ICCCNT.2013.6726517
[5] P. K. Panda and S. Cha opadhyay, "A hyb id secu i y algo i hm o RSA c yp osys em," 2017 4 h
In e na ional Con e ence on Ad anced Compu ing and Communica ion Sys ems (ICACCS),
Coimba o e, 2017, pp. 1-6. doi: 10.1109/ICACCS.2017.8014644
[6] S. Ma hu , D. Gup a, V. Goa and M. Ku i, "Analysis and design o enhanced RSA algo i hm o
imp o e he secu i y," 2017 3 d In e na ional Con e ence on Compu a ional In elligence &
Communica ion Technology (CICT), Ghaziabad, 2017, pp. 1-5. doi: 10.1109/CIACT.2017.7977330
[7] N. M. S. Iswa i, "Key gene a ion algo i hm design combina ion o RSA and ElGamal algo i hm,"
2016 8 h In e na ional Con e ence on In o ma ion Technology and Elec ical Enginee ing (ICITEE),
Yogyaka a, 2016, pp. 1-5. doi: 10.1109/ICITEED.2016.7863255
[8] Ba aka , Mohamed, Ch is ian Ede , and Timo Hanke. "An In oduc ion o C yp og aphy." (2018).
In e na ional Jou nal o Ne wo k Secu i y & I s Applica ions (IJNSA) Vol. 11, No.3, May 2019
70
[9] Vishal Ga g, Rishu, Imp o ed Di ie-Hellman Algo i hm o Ne wo k Secu i y Enhancemen ,
In .J.Compu e Technology & Applica ions, Vol 3 (4), 1327-1331
[10] Emmanual B esson, Dynamic g oup Di i-hellman key exchange unde s anda d assump ion,
P oceeding o EUROCRYPT, LNSC 2332, page no. 321-336, 2002.
[11] Da id A. Ca s, A Re iew o he Di ie-Hellman Algo i hm and i s Use in Secu e In e ne P o ocols
SANS Ins i u e Reading Room.
[12] Thanga el M, e al., An Enhanced and Secu ed RSA Key Gene a ion Scheme (ESRKGS), Jou nal o
In o ma ion Secu i y and Applica ions (2014).
[13] T. Elgamal, "A public key c yp osys em and a signa u e scheme based on disc e e loga i hms," in
IEEE T ansac ions on In o ma ion Theo y, ol. 31, no. 4, pp. 469-472, July 1985.doi:
10.1109/TIT.1985.1057074
[14] Ri es , Ronald L., Adi Shami , and Leona d Adleman. "A me hod o ob aining digi al signa u es and
public-key c yp osys ems." Communica ions o he ACM 21.2 (1978): 120-126.
[15] Islam, M.A., Islam, Md.A., Islam, N. and Shabnam, B. (2018) A Modi ied and Secu ed RSA Public
Key C yp osys em Based on “n” P ime Numbe s. Jou nal o Compu e and Communica ions, 6, 78-
90.
[16] Manu and A. Goel, "Enc yp ion algo i hm using dual modulus," 2017 3 d In e na ional Con e ence
on Compu a ional In elligence & Communica ion Technology (CICT), Ghaziabad, 2017, pp. 1-4. doi:
10.1109/CIACT.2017.7977331.
[17] Kleinjung, Tho s en, e al. "Fac o iza ion o a 768-bi RSA modulus." Annual C yp ology
Con e ence. Sp inge , Be lin, Heidelbe g, 2010.
[18] Rosen, Kenne h H. Disc e e ma hema ics and i s applica ions. New Yo k: McG aw-Hill, 2011.
A
UTHOR
Eng . Shaheen Saad Al-Kaabi, 30 yea s old. B.S. in Elec ical Enginee ing, Uni e si y
o Colo ado a Den e ( UCD ) M.S. in Cype secu i y, Hamad Bin Khali a Un i s y
( HBKU )
