Int ern at i onal  Journ al of Ele ctrical  an d  Co mput er  En gin eeri ng   ( IJ E C E)   Vo l.   9 , No .   5 ,  Octo ber   201 9 , pp.  3576 ~3 583   IS S N: 20 88 - 8708 ,  DOI: 10 .11 591/ ijece . v9 i 5 . pp3576 - 35 83          3576       Journ al h om e page :  http: // ia es core .c om/ journa ls /i ndex. ph p/IJECE   A new digital  si gn ature schem e with m essage r ecover y    usin g hybrid  probl ems       Ned al Ta hat 1 , Ra nia  Sh aq b oua 2 ,   Em ad E.  Ab d allah 3 ,   M ohamm ad  Bs oul 4 ,  W as fi   Shata n awi 5   1,2 Depa rtment   of   Mathe m atics,   Facult y   of   Scie n c es,   Th e  Hash emite   Univ ersity ,   Jo rda n   3, 4 Facul t y   of  Pri nce   Al - Hus sein   Bin  Abdull ah  II   for  Inform at ion   Te chno log y ,   Th e   Hashem it e   Uni ver sit y ,   Jordan   5 Depa rtment of  Mathe m at i cs  an d  gene r al c ourse s Princ e  Sul ta n   Univer sit y ,   Saud i  A rab i a       Art ic le  In f o     ABSTR A CT    Art ic le  history:   Re cei ved   N ov   15 , 201 8   Re vised  A pr 9 ,  201 9   Accepte d  Apr 18 , 201 9       W e  pre sent  a  new  digi ta l  signa ture   sche m e  with  m essage   rec over y   and  i ts   aut hen ti c at ed  e ncr y p ti on  base d   on  el li ptic  cu rve   discre t e  lo gar it hm   and  quadr atic  residu e.   The   m ai n  idea   is  to  provide   a  highe r  le v el   of  sec uri t y   th an   al l  oth er  techniq ues  tha t  use  signat ure s  with  sin gle   har d  probl e m   inc ludi ng  fac tor ing,   discrete   loga ri thm,  re siduosit y ,   or  el l ipt ic   cur v es.   Th e  proposed  digi tal  signa tur e  sc hemes  do   not  invol v e  a n y   m odula r   ex ponent i at ion   oper ations  tha t  l ea ve  no  gap  for  at t ac ker s .   The   se cur ity   an aly sis  demons tra te s   the   improved  p erf orm anc e   of  t he  proposed  s c hemes  in  comp ari son  with   exi sting   techniq ues  in te rm s of t he  ab il i t y   to   resi st t he   m os t  comm on  at tacks.   Ke yw or d s :   Digital   sig natu re   Ell ipti c curve   Au t hen ti cat ed   encr y ption   Me ssage reco ve ry   One - w ay  h as h functi on   Finit e fiel d   Copyright   ©   201 9   Instit ut e  o f Ad vanc ed   Engi n ee r ing  and  S cienc e .    Al l   rights re serv ed .   Corres pond in g  Aut h or :   Ned al   Tahat,     Dep a rtm ent o f M at hem a ti cs, F acult y o f  Scie nces,   The Has hem it e  Unive rsity ,   P.O. Bo x 1 50459, Za rq a  13 115,  J orda n.   Em a il : ned al @ hu.edu. jo       1.   INTROD U CTION     Digital   sign at ure  with  m essa ge  rec ov e ry  ha s  beco m e  one  of   the  m os t  i m po rtant  asp ect s  of   data   secur it y.  It  is  us e d  to  al low  a  m essage  owner   to  se nd  on ly   a  sign at ur e  of   his  m essage.  The  ve rifier s  us e  the   receive d  signa ture  f or  ver i ficat ion   first  an d  then  to  recover   the  or igi nal  m ess age  f ro m   the  sign at ure.  I n  [1 - 3]   Nybe rg   a nd  Ruep pel  prese nted  se ver a l  sig na ture  sc hem es  base d  on  the  di screte  log a rith m   pr oble m   (D LP)  t o  recover  t he  e ncr y pted  m essages  f r om   the   receive d  sig natu res.   Lat e r,  Horster  et   a l.  [4 ]   pr opos e d  an   authe ntica te d  encr y ption   sc he m e  m od ifie d  from   Nyber g  a nd  Rue pp el   al gorithm s,  wh e re   on ly   the  desi gnat ed   ver ifie rs  can  re trie ve  an d  ver i fy  the  m essages  from   the  signa tures.   The refo re,  the  sc hem e  can  be  cl assi fied  as   a com bin at ion  of the  data e nc ryptio n  sc hem e  and the  d i gital  sig natur e  sc he m e.    In  orde r  t o  rec ov e r  t he  or igi na l  m essage  f rom   the  s ig natu r e,  the  m essage  cannot  be  has he d  to   re duce   it s  siz e.  Howe ver,  if  the  m essage  is  la r ge,   i t  sh ould  be  di vid e d  int o  a  s equ e nce  blo c ks,  an d  eac h  blo ck  is   encr y pted  a nd  sign e d  as  a  sign at ur e  blo c k  ind ivi du al ly .  C on s eq ue ntly ,  each  m essage  bl ock   c onta ins  so m e  data  redu nd a nc y.  The  re dundant  data  is  em plo ye d  to  cor rectl y  li nk   al l  the  data  blo c ks   to gethe r.   T he  m ai n  dr a w back  of  the  ab ove  sc hem e  is  the  hi gh  cost  of  c om m un ic at ion s.   H wang  et   al .  [ 5]  pro pose d  a n  authe ntica te d  encr y ption  sc hem e  with  m essage  li nka ges  base d  on  H ors te r  et   al .  sche m e  [4 ] .  Since   the n,  sever al  im pr ov ed  a uth e ntica te d  e ncr y ption  sc hem es h ave  be en pr opos e d [ 6 - 8] to  inc rease  the p e rfo rm ance.   Gira ult  in  [9 ]   pr ese nts  the  c oncept  of   the  se lf - certi fie d  publ ic   keys .  A  pu blic  key  is  ob t ai ned   f r om   the   sig natu re  of  the  us e r' s  pr i vate  key,   with   his/her   ide ntit y  signe d  by  th e  syst e m   authorit y.  The  public  key  of  each  us e r  does   no t  nee d  to  be   com pan ie d  by   a  separ at e  cert ific at e.  The  pr oof  of  the  publ ic   key  can  i m plici tly   com pu te d  with   the  sign at ure  ver ific a ti on.  T hu s ,  the  stora ge   sp ace  and   c om pu ta ti on s  cos t  is  red uced   by   us ing  Evaluation Warning : The document was created with Spire.PDF for Python.
Int   J  Elec  &  C om p  En g     IS S N: 20 88 - 8708       A n ew   dig it al s ignature  sch e m e wi th m es sage  recovery  usi ng  hybri d pr ob l ems   ( Ne dal T ahat )   3577   sel f - certi fie d  public  keys.  Cl e arly ,  the  syst e m   autho rity   does  not  kn ow  th e  us e r' s  pr iv at e  key,  wh ic h  is  chosen   by u s er  pri vate ly .    Seve ral  dig it al   sign at ur e  sc he m es  us ing   sel f - certi fi ed  public  keys  [ 10 ]   have  been   pro pose d  ba sed   on   Gira ult’s  al go r it h m   [9 ] .  Var i ou s   a uth e ntica te d  e ncr y ption  schem es  are  pr esented   to  al l ow  on ly   th e  s pe ci fied   receiver  t o  veri fy  and   to  rec ov e r  the  ori gi nal  m essage.  Obviously ,  al l  te chn iq ues  de pends  on   the  f ac t  that   there  is  a   tr us te d  syst em   authorit y  (S A ).  I n  th e  real  world,  S A  is  not  guara nteed  t o  be  t otall y  reli able.  E ncina s   et   al .  [11]  s howed  that  the re   is  a  m ajo r  w eakn e ss  in   [ 10]   and   al l  relat ed  sc hem es  [ 12 - 16]   aff ect in g  both   the au t hen ti cat ion o f  t he  sig n e r' s p ubli c k ey  a nd the  secu rity  o f  the syste m .    Ell ipti c  curves   for  c rypto gra ph ic   syst em s  are  intr oduce d  in  [ 17 ,  18] .  Ell ipti c  curves   pro vid es   a  s m al le r  key  siz e  with  si m pler  cal culat ion s  and   t he  sam e  l evel  of   secu rity   [1 9 - 21 ] .  T he  cod i ng   a nd  dec od i ng  can   be  ca rr ie d ou t m or e e ff ic i ently  in  the  ell ipti c cu rv es  poi nt gr oup, m aki ng it  a v e ry e xc it ing  f eat ur e   The  a bove   pro blem s  including  th e  li m it ed  r obus t ness  a gai ns t  at ta cks   an d  the  high  c om pu ta ti on  cost,   m ot ivate d  the  auth or s  to  intr oduce  a  dig it a l  sign at ur e   sc hem e  with  m es sage  rec ov e ry  base d  on   tw o  hard  pro blem s.  The  cl ue  is  to  us e  the  el li ptic  cur ve  over  Z _n   ba sed  on  el li pti c  cur ve  discret e  log arit hm   pr ob le m   (ECDL P)  an d  quad rati c  res idu e  pro blem   ( QRP).  T his   idea  is   no ve l  and  nev e r  be en  us e d  for  dig it al   sign at ur e a ppr oach e s.       2.   BACKG ROU ND   In this sect io n,  we   descr i be  s om e elem entary  too ls  on elli ptic cu rv es .   Def ini ti on:   Le t    be  a  f ie ld  w it h  c har act e risti c > 3, the n  a n  el li ptic cur ve  ca n be e xpresse d as:     2 = 3 +  +     (1)     Wh e re   , ∈   an d  4 3 + 27 2 ≠ 0 .  The  set   ( )   co ns i sts  of  al l  poin t  ( , ) , , ∈   w hic h  sat isfie s  the   de fining   ( 1)  t oget her  with   a   s pecial   po i nt    c al le d  the   po i nt   at   i nf i nity .  L et     be   a   point   on   the  el li ptic  curve  def i ned   i n  ( 1).  I f     is  the  sm al le st  po sit ive  integ er   sat isf ie s  the  e qu at io n    = ,  then     is  the b a se  po i nt  of ord e r    [17] - [ 23 ] .   The ne w digit al  sign at ur e  sch e m e b ased  on bot h  EC DLP a nd Q RP  is  giv e n  as  foll ows.   -   ECDLP:  Let     and    be  t w o  e ll ipti c  curve  points  on  (1).  The n  fin d  a   posit ive  inte ger    s uch  tha t      = .   -   QRP:  Let     ,   are   two  stron g  pri m es  of   la rg e   siz e  an d    is  an  inte ger.  T he n,   c om pu te     su c h  that   ≡ 2 ( mod    ) .       3.   THE  PROPO SED SCHE M ES   In   t his  sect ion,  we  pro po se   new   el li ptic  c urve  dig it al   sign at ur e  sc hem es  with  m essage  rec ov ery  base d  on   tw o  ha rd   pr ob le m s.  We  discu ss  in  detai ls  two  authen ti cat ed  enc r ypti on   schem es  on e  of  them   i s  wit h  m essage  li nk a ge.   T he  propos ed  th ree  schem es  co ns ist   of   t he   syst e m   initializat ion   phase  i nclu ding  the  s yst e m   par am et ers.  T he re ar e  th ree  pa rtic ipa nts i n  th e tru ste d  S A, a  sign e r    and a  ve rifier   .    First, S A  c hoose s the  f ollow i ng syst em  p aram et ers:   -   The  fiel d  =   of   order     ,  w her e     be  a  la rg e  pri m e   nu m ber   and   − 1   ha ve  two  pri m e   factor s  ̅     and  ̅   -   Tw o  c oeffici en ts   , ∈   that de fine  the e qu at io n  2 = 3 +  + ( mod   )   over  .   -   = ̅ ̅ ,  s o  t hat  / ( 1 ) np   is  th e  r oo t   points   of  el li ptic  c urve   co ns tr uct  a   ci rcu la ti ng  s ubgr oup.  G  is   a   gen e rati ng ele m ent f or s ubgr oup  a nd it s r a nk e qu al s   .    -   ( .) h   is a   sec ur e  h as h functi on.    -   ( , , , , )   are  publishe d and (   , )   are  all  d isc ard e d.    -   Each  us e r     sel ect s h is  pr i vate  key  ∈ ∗   and com pu te s  his pu blic  = 2   ( mod   )     3. 1 .    Digit al  sig nat ure scheme  wi th  mes sage re cov er y   The  pr opos e d  schem e  is  co m po s ed  in  t wo   phases:   the  sig na ture  ge ne rati on  phase,  a nd  the  m essage  recovery  phase .     3. 1. 1.  Sig natu re gener ati on  pha se   Suppose t hat a  sign e r  wan ts  to  sig n  a m essag e   . T he  sig nat ure ge ner at io n p r ocess  is  g i ven  by:    -   Sele ct   a ra ndom   integer  ∈ [ 1 , − 1 ]   -   Com pu te     Evaluation Warning : The document was created with Spire.PDF for Python.
                          IS S N :   2088 - 8708   In t J  Elec  &  C om p  En g,   V ol.  9 , N o.   5 ,  Oct ober  20 19  :   3 5 7 6   -   3 5 8 3   3578   = − 1     (    ) = ( , )     (2)      -   Encr y pt the m essage    to  fin d  a  ciph e rtext      =   − 1 ( ) ( mo d   )     (3)     -   Ca lc ulate         = ( − 1 −   2     ( ) ) (    ) .    (4)     The pai r  ( , )   is  the  sig natur e  of m essage   . F inall y, the  sen der del ivers  ( , )   to t he re cei ver .     3. 1. 2.  Me ssag e reco ver y  ph as e   Af te r   re cei ving  t he  dig it al   sign at ur e   ( , ) ,   any  ve rifier   ca n  us e   ' s  public  ke y  to  recove r   the m essage    a s foll ow s .   -   Com pu t es      (  + ( ) ) (    ) = = ( , )     (5)     -   Decr y pt the ci ph e r  te xt     to  fin d  the  p la inte xt    su c h  t hat      =   (  )   (    )     (6)     -   Check  that the   form at  o f  m ess age   .   It could  b e  proven  that th e  propose d  sc hem e  works c orrectl y.     Theorem   1.   The   m essage  is  rec ov e re d  correct ly   from   the   di gital   sign at ur e ( , ) thr ough   ( 6)   Pr oof .     Fr om  ( 5),  w e  have      (  + ( ) ) (    ) = ( − 1 −   2     ( ) ) + ( )   = − 1 + ( −   2     ( ) ) + ( )   2       = − 1 (    )     =   =   ( , )     The n  the  m ess age    is o btained  b y ca lc ulati ng        ( ) =   − 1 ( ) ( ) (    ) =       3.2 .     Au t hen tica ted   encry pt i on  sc heme   In   this  subsect i on,  we  present   an  authe ntica te d  encr y ptio n  schem e  that  com bin e  the  data   encr ypti on   and  the  dig it al   sign at ur e   sche m e.  In   oth e r  w ords,  the  si gn e r  can   ge ne rate  a  dig it al   sig nat ur e  f or   m essag e    and   t hen   deliv er  it   to  a  desig nated  ver ifie r.   Upo n  recei ving  the  dig it al   sign at ur e ,  only   the  de sig nated  ver ifie r     can  retrieve  and  ver ify  t he  m e ssage   . D et ai ls  of  t he  si gn at ure ge ner at io n p hase a nd the  m essage  rec ov e r y   ph a se are  d e scr ibed  a s foll ows :     3.2.1. E ncry pti on   an d  signa t ure g e nera tio n p h as e   Assum e  that    wan ts   to   gen e r at e  a  si gn at ur e   f or  a   m essage    an d  sen d  it   to   .  T he   sig na ture   gen e rati ng  pro cedure is  sta te d  as  foll ows:   -   Sele ct  a r a ndom   integer  ∈ [ 1 , − 1 ]   -   Com pu te       = − 1 ( + ) (    ) = ( , )     (7)     -   Encr y pt the m essage    to  fin d  a  ciph e rtext       =   − 1 ( ) ( mo d   )     (8)       Evaluation Warning : The document was created with Spire.PDF for Python.
Int   J  Elec  &  C om p  En g     IS S N: 20 88 - 8708       A n ew   dig it al s ignature  sch e m e wi th m es sage  recovery  usi ng  hybri d pr ob l ems   ( Ne dal T ahat )   3579   -   Ca lc ulate s      = ( − 1 −   2     ( ) ) (    )    (9)     Finall y,    deli ve rs  the  d i gital  sign at ur e   ( , )   to      3.2.2. Si gna tur e v eri fic at i on and mess age  recov er y ph ase   Af te r   recei ving  the   di gital   sign at ur e   ( , ) ,    can  r ecov e r  t he  m e ssage    by  us in g  his/her   pri va te   key    and the  pu blic valu es    as  fo ll ows:   -   Com pu te s      ( + ) + ( ) ( 2 + 1 ) (    ) = = ( , )     (10)     -   Decr y pt the ci ph e rtext    to  fin d  the  p la inte xt    su c h  t hat      =   (  )   (    )     (11)     -   Checks  that t he  for m at  o f  m e ssage    is c orrec t or n ot.   The follo wing  theo rem  is u sed  to  pr ov e  the  correct ness  of t his sc hem e.     Theorem   2.   T he  desig nate d  ver ifie r  can  c orrectl y  ve rify  t he  m essage    f r om   the  di gital   s ign at ur e   ( , )   by (1 0)  a nd  (11)   Pr oo f .   From  (10), we  ha ve     ( + ) + ( ) ( 2 + 1 ) (    )   = ( − 1 −   2     ( ) ) ( + ) ⨁ ( ) ( 2 + 1 )   =   − 1 ( + ) + ( −   2     ( ) ) + ( −   2     ( ) 2 ) + 2     ( )   2 ) + 2     ( )   = − 1 ( + ) (    )   =     = ( , )     Accor ding to  (11),  the m essage    can  be de rived b y ca lc ulati ng       ( ) =   − 1 ( ) ( ) (    ) =       This the orem  i s th us   pro ven.     3.3.    Au t hen tica ted   encry pt i on  sc heme w ith  me ssage li nk ag e     The  basic   aut he ntica te d  enc ry ption  schem e  is  only   app li e d  to  sm aller  m essages.  A  la r ge  m essage  has  to  be  di vid e d  into  sm al le r  bl ocks  first  a nd  then  eac h  bloc k  is  signe d  a nd   e ncr y pted  i nd i viduall y.  In  this   schem e,  if  the  sm a ll er  blo cks   hav e  bee n  re orde red,  m od ifie d,   delet ed,   or  rep li cat ed  dur ing   the  t ran sm issi on   then  t he  si gn at ur e  is m od ifie d as w el l. Th e  det ai ls pr oc ed ure is as the  foll ows:     3.3.1.  Sign atu re and encr yption  g e nera tio n p h as e   W it hout  l os s   of  gen e rali ty ,  a ssu m e  that    de sires  to   c reate  a  m essage    th at   is  to   be   se nt   to .   The  m essage  i s  com po se d   of  the  se quence   of   { 1 , 2 , … , } ,  w he re  ∈   f or  = 1 , 2 , … , .     f ulfill s   the foll owin g  s te ps  to  g e ner at e the si gn at ur e s b l ock s  for t he  m essage  .   -   Ma ke  ∘ = 0   an d  sel e ct  a r a ndom  integer   ∈ [ 1 , − 1 ]   and com pu te s      = − 1 ( + ) (    ) = ( , )     (12)     -   Com pu te s        = − 1 ( − 1 ⊕ ) (    )     (13)     for   = 1 , 2 , … , ,   wh e re  ⊕       ℎ   bit   wi se   exclusiv e   or   o perator .   -   Ca lc ulate s     = ( 1 ∥ 2 ∥ ⋯ ∥ )   = ( − 1 −   2     ( ) ) (    )    (1 4 )     Wh e re  " ∥ "   de note s the c oncat ena ti on   op e rato r.    Evaluation Warning : The document was created with Spire.PDF for Python.
                          IS S N :   2088 - 8708   In t J  Elec  &  C om p  En g,   V ol.  9 , N o.   5 ,  Oct ober  20 19  :   3 5 7 6   -   3 5 8 3   3580     deliver   the  si gnat ure  blo c ks   ( , , 1 , 2 , … , )   to    via  a  public  cha nn el .   N ote   that    is  us e d  a s   a li nk in g pa ra m et er b et wee n t he  ℎ and   ( + 1 ) ℎ   blo c ks.     3.3.2. Mess age  reco very ph ase   Af te r   rec ei ving   t he  si gn at ure  blo c ks  ( , , 1 , 2 , … , ) ,   can  retrieve   th e  m essage  bl ocks   { 1 , 2 , … , }   by the  foll owing st eps .   -   Ca lc ulate     ́ = ( 1 ∥ 2 ∥ ⋯ ∥ )   an d confirm  that    ́ =   is t ru e .   -   Com pu te       ( + ) + ( ) ( 2 + 1 ) (    ) = = ( , )     (15)     Re cov e r  the  m essage  blo c ks   { 1 , 2 , … , }   as foll ows     = ( − 1 ⊕ ) ( mod   )     (16)   for   = 1 , 2 , … , and   ∘ = 0     The pr opose d s chem e cou ld  be p rove n  that i t  works c orrectl y by the  f ollowi ng  t heorem .     Theorem   3.   I n  th e  m essage  rec ov e ry  ph a se,  the   de sig na te d  ver ifie r   can  recove r  the   m essage  bloc ks   { 1 , 2 , … , }   by  us in g  E qs.  (15) an d ( 16).   Proof .   F r om   (1 5) w e  h a ve     ( + ) + ( ) ( 2 + 1 ) ( mod   )   = ( − 1 −   2     ( ) ) ( + ) + ( ) ( 2 + 1 )   = − 1 ( + ) + ( −   2     ( ) ) + ( −   2     ( ) 2 ) + 2     ( )   2 ) +   2     ( )       = − 1 ( + ) ( mod   )   =   = ( , )     Accor ding to  E q.   ( 16),  t he  m e ssage    can  be d erive d by cal cu la ti ng     ( − 1 ⊕   ) (    ) = − 1 ( − 1 ⊕ ) ( − 1 ⊕ ) =     Ther e f or e,     can  g et  the  m essage   . T his the or e m   is t hu s  pro ve n.       4.   SECURIT Y A NA L YS I S     In  this  sect io n,  the  r obus t nes s  of  the   p r opose d  sc hem e  is  te ste d.   T he   di ff ic ulti es  ass oc ia te d  with   the  una uthoriz ed  at ta ckers  ar e  base d  on  t he   so luti on  of   t he  ECD LP  a nd  qua dr at ic   re sidu e  pro blem   QRP.   The  sec uri ty   cause d  f ro m   ECDLP  a nd  QRP  is  s uffic ie nt  unde r  rea so na ble  c om pu ta ti on al   c omplexit y.   So m e  po ssi ble  at ta cks  by  w hich  a n  a dvers ary  ( Adv)  m a y  try   to  ta ke   dow n  the   ne w   el li ptic  curve   dig it al   sign at ur es  w it h m essage r eco ve ry  will  b e  an a ly zed as  f ollo w s:   Atta c k   1.  A n  Adv   at tem pts  to  der i ve  t he  use r' s  pr i vate  key    from   al l  public  inf orm ation   avail able.   An  Adv   can   der i ve    from   ≡ 2 (    ) .  I t  is  obvious   t hat  to   fin d    t he  A dv  has   to  so l ve  both   the  EC DLP  a nd  QRP .  A n  A dv  wa nts  t o  get  the  si gn e r' s  pri vate  key    f r om  the   sig ne r' s  sign at ur e     an d    in  the  m essage  re cov e ry  sc hem e ,  he/s he  s hould  first  obta in     ,    and   ,  A dv  need   t o  s olv e  t he  EC DLP   t o  obta i n  − 1   an d  the n  obt ai n   2   (    )   by  c om puti ng   2 ≡ ( − − 1 ) ( ) − 1 (    ) .  T he  A dv  nee ds  t o  know  t he  sec r et   ra ndom     in  add it io n  t o  so l ve  t he  ha rd  E CDLP.   I f   the   Adv   kn ow  the   ra ndom   nu m be r    he   m us t  so lve  th e  dif ficult   Q RP  an d  the n  obta in    from   2   (    ) .  This   is  bec ause  fin ding     is  com pu ta ti on al ly   equ i valent  t o  fact or i ng  th e  com po sit e  num ber     .  Sim il a rly   the  sec ond  schem e  and   t hir d  schem e the Ad v  sti ll  f aci ng t he  sam e d ifficul ti es.   Atta c k  2.   A n  Adv  im per son at es  the  sig ner' s  sign at ur e  wi thout  kn ow i ng  the  sig ner ' s  pri vate  key .   In   the  first  pr opose d  sc he m e,  Adv  ca n  know  the  sign at ur e  , ,  the  sign e r' s  public  key    and   t he  m essage  .   If   he  trie s  to  i nv e nt  sig ner ' s  sign at ur e,  he  ne eds  to  sel ect   a  rand om   nu m ber     ́ an d  a  m es sage  . ́   Howe ve r,   he  ca nnot  ge ne rate    ́   by  c ompu ti ng   =   = ́ ́ − 1 (    ) = (   ́ ,   ́ )   becau se   the  A dv  do es   no t   kn ow  the sig ner ' s  pr i vate k ey   .    Atta c k  3.  I n  t he  aut hen ti cat e d  enc ryptio n  s chem e,  an  A dv  at tem pts  to  decr ypt  the  m essage    fr om   the d igit al  sig na ture  ( , )   without   ' s  pr i vate  key   . The Adv do es  not kno w   , h e/ sh e  cannot obta in    to  Evaluation Warning : The document was created with Spire.PDF for Python.
Int   J  Elec  &  C om p  En g     IS S N: 20 88 - 8708       A n ew   dig it al s ignature  sch e m e wi th m es sage  recovery  usi ng  hybri d pr ob l ems   ( Ne dal T ahat )   3581   recover  =   (  )   (    )   by   cal culat ing   ( + ) + ( ) ( 2 + 1 ) (    ) = ( , ) .   The  A dv   at tem pts  to  fin d  ( + ) + ( ) ( 2 + 1 ) = − 1 ( + ) (    )   from   = ( − 1 −   2     ( ) )   a nd   then  cal c ulate s  =   (  ).   Th us ,  h e/ s he need s to  kn ow the  pri vate  key     by  so l ving  ECDLP  and  Q RP.    In  the   a uth e ntica te d   e ncr y ption  sc hem e  with  m essage   li nkage ,  he   ca nnot  get  ,   a nd   1 , 2 , … .   If   he  wan ts  t o  decr y pt  the  i th   ci ph e r  te xt  bloc k,   he  m us t  know   t he  ver ifie r' s  pr i vate  key    and   t he n  com pu te s   the v al ue    from   − 1 ( + ) = ( , ) .   T he Adv  will  f ai l t o get the c on te nt of t he  m essage  blo c ks.   Atta c k  4 .  A n  Adv  rec orde rs,  m od ifie s,  de le te s  or   re plica te s  the  m essage  blo c ks .  He/she   sh ould  al s o  m od ify   the  sign at ur e    by   com pu ti ng  the  e quat io ns   = ( 1 ∥ 2 ∥ ⋯ ∥ )   and   ≡ ( − 1 −   2     ( ) ) (    ) .  If  he  can not   exec ute  t he  m od ific at ion ,  r eorder ,  delet io n  or  rep li cat io n  of  t he  m essage   blo c ks ,  h e/ s he wil l no t  pass  th e v e rificat ion e qu at io n    ́   . = ?   Atta c k  5.   Sup po s e the  d if fic ulty  o f  co m pu t ing   ECDL P  ha s b ee n bro ken.    If   a n  A dv  br e aks  t he  EC D LP  a nd  get  a cces s  to   , , ,  a nd  the  sig ner ' s  public  key   ,  he  can  der i ve   the    − 1     fr om   the  equ at io n   ≡ − 1     (    ) .  I f  he  wan ts  t o  get  t he   sign e r' s  pr i va te   key    from   ≡ ( − 1 −   2     ( ) ) (    )   he  m us t  br ea k  t he  dif ficult y  of  QRP   sim ult aneously .  It  is   extrem el y  har d  to  get   the  sig ne r' s  pr i vate  key     by  c om pu ti ng   2 ≡ ( − − 1 ) ( ) − 1 (    ) ,  wh e re  fi nd i ng    is   com pu ta ti on al ly  eq ui valent t o fact ori ng th e c om po sit e num ber.    Atta c k  6 .  S uppose  t he  diffi culty   of   c ompu ti ng  QRP  ha s  bee n  brok e n .  T he refor e ,  an  A dv  ca n  unde rtake   ≡ ( − 1 −   2     ( ) ) (    )   wh i ch   is   relat ed   th e  facto rin g  ass um ption .  Alth ough   an   A dv  ca n  so lve   the   di ff i culty   of  QRP,   he   ca nnot  sti l l  get  t he  si gne r' s  pr i vate  key    fr om   the  e qu at ion .   Be cause   the   equ at io ns co nt ai ns  tw o u nkno wn v a riables    a nd   .   Atta c k  7 .   A n  A dv,  with out   ' s  pr ivate   ke y   ,  at tem pts  to  f orge  th e  dig it al   sig natu re  to  i m per sonat e   .  S uppose  a n  A dv  wa nts  to   f orge  a  valid  sig na ture  for  a  give n  m essage    ́   th at   can  pa ss  th e   ver ific at io n  eq uation.  I f  the  Adv  determ ines    first,  he  will   hav e  to  s olve   ( )   to  obta in  th e  value  of   .  Howe ver,  this  process  is  as  di ff ic ult  as  br ea king  the  one - way   hash   func ti on .  O n  the  ot her   ha nd,  if  th e  Adv  fixes  t he  inte ge r    first,  he/s he has t o ob ta in  th e v al ue  of    by s olv in g EC DL P .       5.   PERFO M ANCE EV ALU A TION   In   this  sect ion ,   we  evaluate  the  perf or m ance  of   the  pro posed  schem es.  The  f ollow i ng   no ta ti ons  are   us e d  to  an al yz e the c om pu ta ti on al  c om plexity :    -      is t he  ti m e com plexit y for e xecu ti ng t he  m odular  exp on e ntiat ion ;   -      is t he  ti m e fo r e xecu ti ng t he m od ular  m ultip li cat ion ;    -    −    is t he  ti m e com plexit y for e xecu ti ng t he  a ddit ion   of  tw o  el li ptic cur ve po i nts;    -    −    is t he  ti m e com plexit y for e xecu ti ng t he  m ulti plica ti on   on ell ipti c curve  po i nts;    -      is t he  ti m e com plexit y for e xecu ti ng t he  m odular  squa re;    -   ℎ is t he  ti m e fo r e xecu ti ng t he o ne - way  hash fu nction.     To  descr i be  th e  eff ic ie ncy  pe rfor m ance  in  te rm s  of    ,  we  c onve rt  va rio us  op e rati ons  unit s  to  the  tim e  com plexity  f or exec uting t he   m od ular  m ultip li cat ion   [8 ] .      ≈ 240    ;    −  ≈ 29  ;    −  ≈ 0 . 12      First  sc hem e,  in  t he   sig natu re   ge ne rati on  phase,  t he  sig ner  needs  (  −  + 4  +  + 2 ℎ ) ≈ 33  +  + 2 ℎ   to   perf or m   the  proce ss  of  this  ph ase .  In  t he  m essage  r e cov e ry  a nd  ve rificat ion  phas e,   the  ve r ifie r  s hould  pe rfor m   (2   −  +  −  +  + 2 ℎ ) ≈ ( 59 . 12  + 2 ℎ )   to  com plete   the  processes  the  m essage r ec ov ery.    Seco nd  sc hem e,  in   t he  a uth e ntica te d  e ncr y ption  sc hem e,  the  si gn e r   re quires   (  −  +  −  + 4  +  + 2 ℎ ) ≈ ( 33 . 12  +  + 2 ℎ )   to   gen e rate  the  si gn at ur e .   T he  ti m e  re qu i red  by  t he  desig nated  ve rifier  to  r ecov e r  the   m essage  is  ( 2  −  + 2  −  + 2  +  + 2 ℎ ) ≈   ( 60 . 24    +  + 2 ℎ ) .   Thir d  sch em e,   if  there  are    blo c ks .  T he  a uth e ntica te d  e ncr y ption   sc he m e  with  m essage  li nk a ge   requires  (  −  +  −  +  + ( + 4 )  + ( + 2 ) ℎ ) ≈ ( ( + 33 . 12 )    +  + ( + 2 ) ℎ ) to  gen e rate  t he  m essage  blo c ks ,   w hile  ver i fyi ng  a nd  ret r ie vin g  th e  m essage   bl ocks  requires   ( 2  −  + 2  −  +  + ( + 1 )  + ( + 2 ) ℎ ) ≈ ( ( + 59 . 24 )  +  + ( + 2 ) ℎ ) .   The  ef fici enc y  per f or m ance  rev eal s  that   the  m od ular   m ulti plica t ion   operati on  dom inate s  ou r   pro po se d  sche m es  in  te rm s  of  ti m e  com plexit y.  N ote  that,  i n  our   pro posed   al gorithm s  no  m odula r   expo nen ti at io n o per at io n  is  use d givin g o ur s chem es a clea r a dv a ntage  ove r  o the r  sc hem es.     Evaluation Warning : The document was created with Spire.PDF for Python.
                          IS S N :   2088 - 8708   In t J  Elec  &  C om p  En g,   V ol.  9 , N o.   5 ,  Oct ober  20 19  :   3 5 7 6   -   3 5 8 3   3582   6.   CONCL US I O N     In  this   pap e r,   we  pro posed n ew  el li ptic cur ve  di gital  sign a ture  sc hem es  with m essage r ecov e ry b ase d  on  EC DLP   an d  QRP.   Mult ip le   le vels  of  sec ur it y  are   use d  to  am plify  the  diff ic ulty   of  breakin g  t he  pro po s ed   syst e m .  It  requ ires  breaki ng  ECDLP ,  QR P   and   a  one - way   has h  f unct ion.   The  m ai n  at tract ive  featu res   of   t he   Ell ipti c  cur ve  c rypto gr a phy  ar e  si m plici t y  and   easi nes s  of  a chievin g  e nc oding .  The  pro po sed  sc hem es  req ui re   m ini m al  op erat ion   f or  sig ning   and   ver i fyi ng   the  signa ture .  The  ef fecti ve ne ss  an d  the  sec ur it y  of   t he  pro po s ed   schem es  are  e valuated  by  cond ucting  se ve ral  at ta cks.   The  res ults  cl ea rly   sh owed  th e  ro bust ness  of  the   pro po se d  s che m es.       REFERE NCE S     [1]   K.  Ny b erg ,   R.   A .   Rueppe l ,   " A  new  signat ure   sche m e  base d  on  the   DSA  givi ng  m e ss age   rec over y , "   Proce edi ngs  of  the   1st   ACM   Co nfe renc e  On Co mputer  and  Com municat ions S ecur it y ,   Fairf ax, VA,  1993.   [2]   K.  N y be rg  and  R.   A.  Ruepp el,  " Mess age   rec ov er y   for  signa tur e  sche m es  base d  on  discrete   lo gar it hm   proble m , "   Adv anc es  in   Cry ptol ogy   –   EU ROCR Y PT'94 ,   Spri nger ,   B e rl in ,   199 4 ,   pp .   175 – 190 .   [3]   K.  N y b erg ,   R.   A.  Rueppel,   " Mess age   re cove r y  for  signa ture   sc hemes  base d  on   the  discrete   log ari thm, "   Design s   Codes  Cryptograph y ,   vol . 7,   no.   1 - 2 ,   pp .   61 - 81 ,   1 996.   [4]   P.  Hors te r,   M.   Miche ls,   H.  Pete rsen,  " Authent i ca t ed  en cr ypti on  sche m es   with  low  com m unic at ion  cost s, "  El e ct ronics  Le tt e rs ,   vol.   30,   no.   1 5,   pp .   1212 - 121 3,   1994 .   [5]   S.  J.  Hw ang,   C.   C.   Chang,   W .   P.  Yang,   " Authent icate d  en cr y ption  sche m es  with  m essage   li nkage , "   Information   Proce ss ing  Let ter s ,   vol.   58,   no.   4,   pp.   189 - 194,   19 96.   [6]   S.  Araki ,   S.  Ue har a,   K.  Im amu ra,   " The   li m it ed   ver ifier  signat u re  and  it s  app lication, "   IEI DE  Tr ansacti on  on  Fundament als ,   v ol.   82 ,   no .   1 ,   pp .   63 - 68,   1999 .   [7]   W .   B.   L ee,  C.   C .   Chang ,   " Authe nti c at ed   enc r y p tion  sche m es  wit h  li nkag e  b et we en  m essage   blo c ks, "   Informat ion  Proce ss ing  Let ter s,   vol. 63, no. 5, pp.   247 - 250,   19 97.   [8]   Y.  M.  Tseng,   J.  K.  Jan ,  " An   eff ic i ent   aut h e nti c at ed  en cr y pt ion  sche m e  with  m essage   li nkage s  and  low   comm unic at ion costs, "   Journal   o f  Information   Scienc e   and  Engi ne ering ,   vo l. 18, n o.   1 ,   pp .   41 - 46 ,   2002.   [9]   M.  Gira ult,  " Se lf - ce r ti fi ed  public  ke y s , "   Ad van ce s  in  Cryptol o gy  –   EUROCR Y PT_91,   Spring er,   Ber li n ,   1991 ,    pp.   491 – 497 .   [10]   Y.  M.  Tseng,   J.  K.  Jan  and  H.  Y .   Chie n,   " Digi ta l   signat ure   with  m essage   rec over y   using  self - c ertifie d  public  ke y s   and  i ts va r ia nts, "   Applied Mathem ati cs  and  Com putat ion ,   vol .   13 6,   no .   2 - 3 ,   pp .   2 03 - 214,   2003 .   [11]   L.   H.  En ci nes,   A .   M.  D.  Re y   and J .   M.  Masque,   " A wea kness i n  aut hent i cate d  en c r y pt ion  sche m e based  on  Tseng  et  al . ' s sch emes, "  I nte rnational   Jou rnal  of  N et work   Sec urit y ,   vol.   7,   n o.   2 ,   pp .   185 – 1 87,   Sep   2008 .   [12]   Y.  F.  Ch ang,  C .   C.   Chang   and   H.  F.   Huang,  " Digit al  signat u re  with   m essage   re cove r y   usin g  self -   ce r ti fi ed     publi c  ke y s  wit hout  trustworthy   s y st em  aut hority , "   Applied  Mathe mati cs  and  Computati on ,   vol.   161,   no.   1,     pp.   211 - 227 ,   20 05.   [13]   S.  J.  Hw ang,  " Im prove m ent   of  Tseng  et   al ’s   aut h ent i ca t ed  enc r y pt ion  sche m e, "   Appl i ed  Mathe mati cs  an d   Computati on,   vo l.   165 ,   no .   1 ,   pp .   1 - 4,   2005 .   [14]   Z.   Shao,   " Im prove m ent   of  digi t a l  signat ure   wi th  m essage   rec over y   using  self - ce rt i fie d  public  ke y s  and  it s  var i ant s, "   Appl ie d   Math emati cs  and   Computati on ,   vol .   159 ,   no.   2 ,   pp .   391 - 3 99,   2004 .   [15]   Q.  Xie,   and  X.  Y.  Yu,  " Cr y p ta n aly s is  of  Tseng ,   et   al . ’s  aut h ent i c at ed  enc r y pt ion  sche m es, "  Appl i ed  Mathe mat ic s  and  Computati o n,   vol .   158 ,   no .   1 ,   pp .   1 - 5 ,   2004 .   [16]   J.  Zha ng ,   W .   Zo u,   D.  Chen ,   and   Y.  W ang,   " On  t he  sec uri t y   of  a  digi tal  signa ture   with  m essage   re cove r y   using  se l f - ce rt ifi ed   publ ic   ke y , "   In formatica ,   vol .   29 ,   pp .   34 3 - 346,   2005 .   [17]   N.  Koblitz,   " Elli pti c   cur ve   cr y p to s y stems , "   Math e matic s of   Computati on ,   vol .   48 ,   n o.   77 ,   pp .   203 - 2 09,   1987 .   [18]   V.  Mill er,   " Us e   of  el li ptic  cur v e  in  cr y ptogra ph y , "   Ad vances  in  Cryptol ogy - Pro ce ed ing  of  CR Y PTO'   85  Lect ure   Note s in   Comput er  Scienc es ,   218 ,   Springer - Verl ag e ,   1986 ,   pp .   417 - 426.   [19]   A.  Mene ze s   and N.  Koblitz,   Ellip ti c   curv e   publ ic  ke y   cry p tosy stem ,   Kluwer   Aca d e m ic   Publishers ,   1993.   [20]   I.   Bl ake,  G.   Sero uss i,   and   N.  Sm a rt,   El l ipt i c  curv e s in  cry p tography ,  C ambridge  U nive rsit y   Pr ess ,   1999.   [21]   J.  Silve rm an ,   Th e  arithme ti c   of   ellipt i c curve s ,   Springer - Verl ag, 19 86.   [22]   D.  Johns on,   D.  A.  Mene ze sand  S.  Vanstone ,  " T he  e ll ip ti c   cur v e  digi tal  sign at ure   al gorit hm , "   Inte r nati onal  Journa l   of  Information   S ec urit y,  vol. 1, n o.   1 ,   pp .   36 - 63 ,   2001.   [23]   N.  Koblit z ,   A.  Mene ze s   and  S.  Vanstone,   " The   stat e  of  e ll iptic  c urve   cr y ptogr ap h y , "   Designs  Code  Cryptography ,  vol.   19 ,   no .   2 - 3 ,   pp.   173 - 193 ,   20 00.                     Evaluation Warning : The document was created with Spire.PDF for Python.
Int   J  Elec  &  C om p  En g     IS S N: 20 88 - 8708       A n ew   dig it al s ignature  sch e m e wi th m es sage  recovery  usi ng  hybri d pr ob l ems   ( Ne dal T ahat )   3583   BIOGR AP H I ES   OF  A UTH ORS        Nedal  Tah at ,  He  re ce iv ed  th e  B. Sc.   d egr e e  in  m at hemati cs  fro m   Yarm ouk  Uni ver sit y ,   Jordan,   i n   1994,   th e  M.Sc .   degr e e  in  Pure   Mathe m at i cs  fro m   Al  al - Ba y t   U nive rsit y , Jord an,  in  1998 ,   and  th e   Ph.D.  deg r ee   in   Applie d  Num ber   Th eor y   (Cr yptogra ph y )  from   Nati on al   Univ e rsit y   of  Mal a y s i a   (UK M)  in  2010.   He  is  an  As socia t e  Profess or  at  Depa rtment  Ma the m at i cs,   Hash emite   Univer si t y.   His  m ai n  rese arc h  int er ests  are  cr y pto log y   and   num ber   the or y .   He  has  publi s hed  m or e  tha n  35  pape rs,   aut hor ed /c oau thore d,   and   m ore   th an  15   re fer ee d   journ al a n d  conf er ence  p a per s.         Ran ia  Sh aq boua ,   She  r ec e ive d  t he  B. Sc .   degr ee  in  m at hemat ic s  f rom   Yarm ouk  U nive rsit y ,   Jordan ,   in  1999,   th e  M. Sc.   degr ee   in   Pure  Mathe m atic s  from   Univer sit y   of   Jordan,   I N  2005.   She  is   an  As sistant   Lectu r er  a t  Dep art m ent Mat hemat ic s,   Hashem it e  Univ er sit y .           Alaa  Ab dallah   is  cur ren tly   an  As socia te   Profes sor  in  the  Depa r tment  of  Com pute r  Sci ence  a t  th e  Hashem it e  Univ ersity   (HU ),   Jor dan.   He  r ec e ived  his  PhD   in  Com pute r  Scie nc e  from   Concordi a  Univer sit y   in  2008,   where   he  worked  on  routi ng  al gorit hm s  for  mobi le   ad  hoc  netw orks.  He  rec eived  his  BS   from   Yar m ouk  Univer sit y ,   Jordan,   and  MS   from   the   Univer sit y   of  Jordan  in  2000  and  200 4,   respe ctively .   Pri or  to  joi n ing  HU ,   he  was  a  net work  rese arc her   at   consult ing  p riva t e  compan y   in  Montrea l  (2008 2011).   His  cur r e nt  rese arc h  int e r ests  inc lud e  rou t ing  protoc o ls  fo r  ad  ho c  ne tworks ,   par allel a nd   distr ibut ed   s y st ems ,   and  m ult imedi a s ec urity .         Mohammad  Bs oul   is  an  As socia t e  Profess or  in  the   Com pute r  Scie nc e  Depa r t m ent   of  Hashem it e  Univer sit y .   He  rec e ive d  his  BS c  in  Com pute r  Scie nc e  from   Jordan  Univer sit y   of  Sc ie nc e  a nd  Te chno log y ,   Jordan,   his  Master   from   Univer sity   ofW este rn  S y dne y ,   Aus tra lia,   and  his  PhD  fr om   Loughbo rough  Univer sit y ,   UK .   His  rese arc h  i nte rests  include   wire le ss   sensor  net works ,   gri d   computing,   d istr ibut ed   s y st ems ,   and  per fo rm anc e   evalua t ion.            Wasfi  Sh ata na w i ,   PhD,   is  a  profe ss or  of  Math emati cs  in  the   Depa rtment  of  Ma the m at i cs  at   Prince  Sulta n  Un ive rsi t y .   Shat ana wi  co m ple te d  his  Ph D  stud y   from   C arl e ton  Univer si t y /Ca nad a  in   20 01.   He  publi shed  m ore   tha n  120  pape rs  in  high   standa rd  journ al s.  Shat ana wi  is  one  of  the   m os t   infl uentia l  scie n ti fic   m inds  in  t he  world.   Profe ss or  Shata nawi  is  highly   ci t ed  r e sea rch ers  for  four   conse cutive  y e ar s  2015,   2016,   2017  and  2018  ac c ording  to  Cla r iv at e  Anal y t i c  (pre viousl y   Thoms on   Reut ers). Shat an awi  is  an edi tor   i n  m an y   rep u ta bl e  journ al s.     Evaluation Warning : The document was created with Spire.PDF for Python.