I nte rna t io na l J o urna l o f   Rec o nfig ura ble a nd   E m bedd e d Sy s t em s   ( I J RE S)   Vo l.   9 ,   No .   3 ,   No v em b er   2 0 2 0 ,   p p .   235 ~ 241   I SS N : 2 0 8 9 - 4 8 6 4 ,   DOI : 1 0 . 1 1 5 9 1 /ijre s . v 9 . i 3 . p p 235 - 2 4 1          235       J o ur na l ho m ep a g e :  h ttp : //ij r es.ia esco r e. co m   Efficien t  a da ptati o n of t he   K a ra tsu ba  alg o rithm f o r  implem enti ng  on  FP G A very  larg e  sca le multiplie rs f o r  cryp tog ra phic alg o rithms       Wa lder  Andre   De p a rtme n t  o f  El e c tri c a l  a n d   Co m p u ter E n g i n e e rin g ,   Ro y a l  M il it a ry   Co l leg e   o f  Ca n a d a ,  Ca n a d a       Art icle  I nfo     AB S T RAC T   A r ticle  his to r y:   R ec eiv ed   Ju l   11 ,   2 0 20   R ev is ed   Sep   2 8 ,   2 0 20   Acc ep ted   Oct   8 ,   2 0 20       He re ,   we   p re se n t  a   m o d ifi e d   v e rs io n   o f   t h e   Ka ra tsu b a   a lg o r it h m   t o   fa c il it a te  th e   F P G A - b a se d   imp lem e n tatio n   o f  th re e   sig n e d   m u lt ip li e rs:  3 2 - b i t  ×   3 2 - b it ,   128 - b it   x   1 2 8 - b it ,   a n d   5 1 2 - b it   ×   5 1 2 - b it .   We  a lso   imp lem e n t  t h e   c o n v e n t io n a l   32 - b it   ×   3 2 - b it   m u lt i p li e r  fo r  c o m p a ra ti v e   p u rp o se s.  Th e   Ka ra tsu b a   a lg o rit h m   is  p re fe ra b le  f o r   m u lt i p li c a ti o n s  w it h   v e ry   larg e   o p e ra n d s   su c h   a s 6 4 - bi t   ×   6 4 - b it ,   1 2 8 - b it   ×   1 2 8 - b it ,   2 5 6 - b it   ×   2 5 6 - b it ,   5 1 2 - b it   ×   5 1 2 - b it   m u lt i p li e rs  a n d   u p .   Ex p e rime n tal  re su lt s sh o w t h a t  t h e   Ka ra tsu b a   m u lt ip li e r  u se s les s h a rd wa re   in   th e   F P G A  c o m p a re d   to   th e   c o n v e n ti o n a l  m u l ti p l ier.  T h e   Xili n x   x c 7 k 3 2 5 tfb g 9 0 0   F P G A  u si n g   th e   G e n e sis  2   d e v e lo p m e n t  b o a rd   is  u se d   t o   imp lem e n t  th e   p r o p o se d   sc h e m e .   Th e   re su l ts  o b tain e d   a re   p ro m isin g   f o r   a p p li c a ti o n s  th a t  re q u ire  ra p id   imp lem e n tatio n   a n d   re c o n fig u ra ti o n   o f   c ry p to g ra p h ic alg o rit h m s.   K ey w o r d s :   128 - b it ×   1 2 8 - b it m u ltip lier     512 - b it ×   5 1 2 - b it m u ltip lier   C r y p to g r ap h ic  k ey     FP GA   Kar atsu b a  m u ltip lier   T h is i s  a n   o p e n   a c c e ss   a rticle   u n d e r th e   CC B Y - SA   li c e n se .     C o r r e s p o nd ing   A uth o r :   W ald er   An d r e ,   Dep ar tm en t o f   E lectr ical  an d   C o m p u ter   E n g in ee r in g ,   R o y al  Militar y   C o lleg e ,   B o x   1 7 0 0 0 ,   Statio n   Fo r ce s ,   Kin g s to n ,   On tar io ,   K 7 K  7 B 4 ,   C an ad a .   E m ail:  wald er . an d r e@ p o ly m tl.c a       1.   I NT RO D UCT I O N   T h e  n ee d   to   p r o tect  d ata  an d   in f o r m atio n   is   cr u cial;  it  ca n   m ak e  th e  d if f e r en ce   b etwe en   life   an d   d ea th .   Mo r e  p a r ticu lar ly ,   in   th e  m ilit ar y   f ield ,   win n i n g   a   wa r   r elies  h ea v ily   o n   th e   p r o tectio n   o f   in f o r m atio n   [ 1 ] .   T h e  u s e  o f   en cr y p tio n   k e y s   is   o n e  o f   t h e  m ea n s   u s ed   t o   p r eser v e   th e  au th e n ticity ,   c o n f id en tiality ,   n o n - d en ial,   a n d   in teg r ity   o f   th e  d ata.   E n cr y p ted   m ess ag es  u s e  cr y p to g r ap h ic   k ey s ,   w h ich   ar e  a  b in a r y   n u m b e r   r an g in g   f r o m   0   to   n .   Fig u r e  1   b elo w  s h o ws an   ex am p le  o f   a   b lo ck   d ia g r am   to   e n cr y p t a   m e s s ag e .           Fig u r e  1 .   Me s s ag e  en cr y p tio n   p r o ce s s   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :  2 0 8 9 - 4 8 6 4   I n t J Reco n f ig u r a b le  &   E m b ed d ed   Sy s t,  Vo l.  9 ,   No .   3 ,  No v e m b er   2 0 2 0 :   235   –   2 4 1   236   T h e  lo n g er   th e   cr y p t o g r a p h ic  k ey ,   t h e  m o r e   r o b u s t  its   d ec r y p tio n .   T h e  le n g th   o f   th e   k ey   d ep en d s   o n   th e  ty p e   o f   in f o r m atio n   p r o tec tio n   d esire d   to   ac h iev e.   T h er e f o r e,   t h e  n at u r e  o f   t h e  m is s io n   an d   th e  o p er atio n   h ea v ily   in f lu e n ce   th e  len g th   o f   a  k ey .   An d   f in ally ,   it d ep en d s   o n   th e  s ev er ity   o f   th e  d a m ag e   th at  co u ld   o cc u r   if   th e  in f o r m atio n   is   in ter ce p te d   an d   d ec r y p ted .   Mo s t  o f   th e  cr y p t o g r ap h ic  alg o r ith m s   a r e  v er y   d if f icu lt  to   d ec ip h er ;  th e  th e o r etica l  f o u n d atio n s   ar e  s u b s tan tial  [ 2 ] .   As  with   an y   en cr y p tio n   alg o r ith m ,   we  p er f o r m   a  lo t  o f   ar ith m etica l o p er atio n s ,   an d   we  n ee d   t o   f in d   m eth o d s   to   a cc eler ate  th ese  b asic  ar ith m eti c  o p er atio n s .   T h ese   m eth o d s   ar e  g ea r ed   to war d s   t h e  m u ltip licatio n   o f   lar g e  n u m b er s .   Key s   ar e  r an g in g   in   len g th   f r o m   6 4   b its   to   4 0 9 6   b its   d ep e n d in g   o n   th e  s ec u r ity   lev el  we  wan t  to   ac h iev e  an d   th e  ty p e  o f   th e  k ey   g en er ato r   u s ed   t o   g en er ate  th em .   As we   s aid   b ef o r e,   th e  lo n g e r   th e  cr y p to g r ap h ic  k ey s ,   th e  s tr o n g er   th e  cr y p to g r ap h ic  alg o r ith m   will  b e.   Fo r   in s tan ce ,   we  h a v e  th e   alg o r ith m s   AE S - 1 2 8 ,   DH,   DSA,   R SA - 307 2 ,   SH A - 2 5 6 ,   an d   E C DH,   E C DSA - 2 5 6   p r esen t  a  s ec u r ity   lev el  o f   1 2 8   b is .   T h e  alg o r ith m s   AE S - 1 9 2 ,   SHA - 3 8 4 ,   E C DH,   E C D SA - 3 8 4   p r o v id e   a  s ec u r ity   lev el   o f   1 9 2   b its ,   an d   f i n ally ,   th e  al g o r ith m s   AE S - 2 5 6 ,   SHA - 5 1 2 ,   E C DH,   an d   E C DSA - 5 2 1   ex h ib it a   s ec u r ity   lev el  o f   2 5 6   b i ts   [ 3 ] .   Har ik a  et  al .   h av e  p r esen ted   a  cr itical  r ev iew  o f   f o u r   m u ltip li ca tio n   alg o r ith m s ,   wh ich   ar e  s h if t - An d - Ad d   Mu ltip lier ,   C ar r y   Sav e  A d d er ,   B o o th   Mu ltip lier ,   an d   a  m o d if ied   v er s io n   o f   t h e  B o o t h   m u ltip lier .   B ased   o n   th is   a r ticle,   th e   C ar r y   Sav e   Ad d er   wa s   f o u n d   t o   b e   m o r e  e f f icien t  in   ter m s   o f   e x ec u tio n   t im e  an d   less   s p ac e  in   th e   FP GA  th an   th e   o t h er   m u ltip licatio n   alg o r ith m s   m e n tio n ed   ab o v e.   Dif f er en t   m u lt ip licatio n   alg o r ith m s   ex is t,  s u ch   as  Gr id ,   W allac e - tr ee ,   Ved ic,   L attice,   C o m b in a tio n al,   Seq u e n tial,  A r r ay   an d   Mo n tg o m er y ,   an d   Kar atsu b a  [ 4 ,  5 ] .   Sev er al  ar ticles  p r o p o s ed   im p lem en tatio n   m eth o d s   o n   FP GA  o f   th e  Kar atsu b a  alg o r ith m .   Yan g   h as  i n tr o d u ce d   a  s ch e m e  f o r   im p lem e n tin g   a  2 5 6 - b it  x   2 5 6 - b it  m u ltip lier ,   w h ich   ex h ib its   5 0 %   ef f icien cy   co m p ar ed   to   tr ad iti o n al  im p lem en tatio n s   [ 6 ] .   I n   th is   ar ticle,   a   n ew  s ch em e   f o r   im p lem e n tin g   t h e  Kar atsu b a  m u ltip lier .   T h e  Kar atsu b a   m u ltip lier   is   v er y   ef f icien t   in   m u ltip ly in g   v er y   lar g e   n u m b er s ,   wh ich   co n s titu tes  an   ex ce llen t  a s s et   in   ac h iev in g   co m p lex   cr y p to g r ap h ic  p r o ce s s o r s   [ 7 - 9 ] .   T h e  c o n v e n tio n al  m u ltip l icatio n   m eth o d   h as  a  co m p l ex ity   O( N 2 ) ,   wh ile   Kar atsu b a  h as  a  co m p lex ity   o f   O( N log3/log2 ) .   T h e  f o llo win g   s ec tio n   will  p r esen t  th e  th eo r etica l  f o u n d atio n s   f o r   th e  Kar atsu b a  alg o r ith m   an d   u s ed   th e  f in d in g   to   im p lem en t  a  th ir d - d eg r ee   Kar atsu b a  m u ltip lier .   Sectio n   3   will in tr o d u ce   th e  p r o p o s ed   s c h em e;  s ec tio n   4   will sh o w  th e  ex p er im en tal  r esu lts .       2.   T H I RD - D E G RE E   K ARA T S UB A  ANA L YS I S   Her e,   we  p r esen t  th e  t h eo r et ical  f o u n d atio n   f o r   d e v elo p i n g   a  th ir d - d e g r ee   Kar atsu b a   m u ltip lier   f o r m u la.   W e  will  b e   u s in g   it  t o   im p lem e n t  3 2 - b it   ×  3 2 - b it   Kar atsu b a  m u ltip lier ,   1 2 8 - b it   ×  1 2 8 - b it  Ka r atsu b a  m u ltip lier ,   an d   5 1 2 - b it  ×   5 1 2 - b it  Kar atsu b a  m u ltip lie r   in to   FP GA.   W eim er s k ir ch   laid   o u t  a  m o r e  in - d ep th   ex am in atio n   o f   t h e  Kar atsu b a  alg o r ith m   [ 10 ] .   L et   A( x )   an d   B ( x )   th e  two   o p er a n d s   o f   th e  t h ir d - d eg r ee   Kar atsu b a  m u ltip lier s .      ( ) = 3 3 + 2 2 + 1 1 + 0 0     ( 1 )     ( ) = 3 3 + 2 2 + 1 1 + 0 0     ( 2 )     ( ) = A ( ) ( )   ( 2 )     ( 3)     = ∑ + ∞ + =     ( 4 )     ( ) = ( 0 0 ) 0 + ( 0 1 + 1 0 ) 1 + ( 0 2 + 2 0 + 1 1 ) 2 + ( 0 3 + 3 0 + 1 2 + 2 1 ) 3 + ( 1 3 + 3 1 + 2 2 ) 4 + ( 2 3 + 3 2 ) 5 + ( 3 3 ) 6     ( 5 )     L et     =     ( 6 )     , = ( + ) ( + )     ( 7)     W ith   i ,  j   =  0 ,   1 ,   2 ,   3 .     B y   ap p ly in g   s o m e  b asic a lg eb r a  to   ( 5 ),   it f o llo ws     ( ) = ( 0 0 ) 0 + ( 0 1 + 1 0 + 0 0 + 1 1 − ( 0 0 + 1 1 ) ) 1 + ( 0 2 + 2 0 + Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J Reco n f ig u r a b le  &   E m b ed d ed   Sy s t   I SS N:  2089 - 4 8 6 4       E fficien t a d a p ta tio n   o f th e   K a r a ts u b a   a lg o r ith m  fo r   imp leme n tin g   o n   …   ( Wa ld er A n d r e )   237   0 0 + 2 2 − ( 0 0 + 2 2 ) + 1 1 ) 2 + ( 0 3 + 3 0 +   0 0 + 3 3 − ( 0 0 + 3 3 ) + 1 2 + 2 1 + 1 1 + 2 2 − ( 1 1 + 2 2 ) ) 3 + ( 1 3 + 3 1 + 1 1 + 3 3 − ( 1 1 + 3 3 ) + 2 2 ) 4 + ( 2 3 + 3 2 + 2 2 + 3 3 − ( 2 2 + 3 3 ) ) 5 + ( 3 3 ) 6     ( 8 )     Af ter   e q u alin g   ( 5 )   an d   ( 8 ) ,  an d   b y   id e n tific atio n   it f o llo ws:     0 1 + 1 0 = 0 1 + 1 0 + 0 0 + 1 1 − ( 0 0 + 1 1 )     ( 9 )     A f ter   a p p ly in g   ( 6 )   an d   ( 7 )   to   t h e  R HS  o f   ( 9 ) ,   it  f o llo ws:     0 1 + 1 0 = 0 , 1 − ( 0 + 1 )     ( 1 0 )     Fo r   th e  co ef f icien t f o r   x 2 ,   it f o llo ws :     0 2 + 2 0 + 1 1 =   0 2 + 2 0 + 0 0 + 2 2 − ( 0 0 + 2 2 ) + 1 1     ( 1 1 )     Ap p ly in g   ( 6 )   a n d   ( 7 )   to   t h e  R HS   o f   ( 1 1 )   to   h a v e:     0 2 + 2 0 + 1 1 =   0 , 2 − ( 0 + 2 ) + 1     ( 1 2 )     Fo r   th e  co ef f icien t f o r   x 3 ,   it f o llo ws :     0 3 + 3 0 + 1 2 + 2 1   =   0 3 + 3 0 +   0 0 + 3 3   − ( 0 0 + 3 3 )   +   1 2 + 2 1 + 1 1 + 2 2 − ( 1 1 + 2 2 )   ( 1 3 )     Ap p ly in g   ( 6 )   a n d   ( 7 )   to   R HS   of   ( 1 3 )   to   h a v e :     0 3 + 3 0 + 1 2 + 2 1 =   0 , 3 + 1 , 2 − ( 0 + 3 ) − ( 1 + 2 )     ( 1 4 )     Fo r   th e  co ef f icien t f o r   x 4 ,   it f o llo ws :     1 3 + 3 1 + 2 2 =   1 3 + 3 1 + 1 1 + 3 3 − ( 1 1 + 3 3 ) + 2 2     ( 1 5 )     Ap p ly in g   ( 6 )   a n d   ( 7 )   to   ( 1 3 )   R HS  to   h av e :     1 3 + 3 1 + 2 2 =   1 , 3 − ( 1 + 3 ) + 2     ( 1 6 )     An d   f in ally ,   f o r   t h e  co ef f icien t f o r   x 5 ,   it f o llo ws :     2 3 + 3 2 = 2 3 + 3 2 + 2 2 + 3 3 − ( 2 2 + 3 3 )     ( 1 7 )     A f ter   a p p ly in g   ( 6 )   an d   ( 7 )   to   ( 1 7 )   R HS ,   it f o llo ws:       2 3 + 3 2 = 2 , 3 − ( 2 + 3 )     ( 1 8 )     R ep lacin g   ( 10 ) ,  ( 12 ) ,  ( 14 ) ,  ( 16 ) ,   an d   ( 18 )   b y   th eir   v al u es in   ( 8 )   y ield s   in to       ( ) = 0 + ( 0 , 1 − 0 − 1 ) 1 + ( 0 , 2 − 0 − 2 + 1 ) 2 + ( 0 , 3 + 1 , 2 − 0 − 3 − 1 − 2 ) 3 + ( 1 , 3 − 1 − 3 + 2 ) 4 + ( 2 , 3 − 2 − 3 ) 5 + 3 6     ( 19)     W e  h av e  p r esen ted   a   n ew   s ch em e  to   im p lem en t   ( 1 9 ) .   Fig u r es  2   an d   3   p r esen t  th e   f ir s t  tw o   s tep s   in   ca lcu latin g   th e  M i   an d   M i ,   j   w ith   i,  j  =  0 ,   1 ,   2 ,   3   to   im p lem e n t   th e  Kar atsu b a  alg o r ith m .   O n ce   th ese  two   s tep s   p ass ,   wh at  f o llo ws  is   th e   u s e   o f   ad d e r s   an d   s h if t  r eg is ter s   to   im p lem en t  t h e  r est  o f   t h e   eq u atio n .   Fig u r e  2   p r esen ts   th e  s ep ar atio n   o f   t h e   o p er a n d   A( x ) ,   wh ic h   is   o f   len g th   N  in t o   f o u r   s u b g r o u p s   to   g iv e  th e   a 0 ,   a 1 ,   a 2 ,  an d   a 3 .   T h e  s am e  s tep   is   r ep ea ted   o n   th e   B ( x )   o p er an d   to   ac h iev e  b 0 ,   b 1 ,   b 2 ,   an d   b 3 .   F ig u r e  3   s h o ws  th e  g en er atio n   o f   th e   v ar iab les M n   an d   M n,   m .         Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :  2 0 8 9 - 4 8 6 4   I n t J Reco n f ig u r a b le  &   E m b ed d ed   Sy s t,  Vo l.  9 ,   No .   3 ,  No v e m b er   2 0 2 0 :   235   –   2 4 1   238   B elo w,   we  p r esen t o u r   m o d if i ed   v er s io n   o f   th e  Kar atsu b a  al g o r ith m .     /*   Let A   a n d   B   tw o   b in a r y  n u mb ers   o f siz e  n w id th   */   m in _ s td v ec   =  8     p r o ce d u r e  k a r atsu b a( A,   B )        if   ( A  <  lim it)  o r   ( B   <  lim it)            r etu r n   A  ×   B               a 0   =  A( ( n wid t h /m in _ s td v ec ) - 1   d o wn to   0 )                 a 1   =  A( ( n wid t h /m in _ s td v ec ) * 2 - 1   d o wn t o   ( n wid t h /m in _ s td v ec ) )               a 2   =  A( ( n wid t h /m in _ s td v ec ) * 3 - 1   d o wn t o   ( n wid t h /m in _ s td v ec ) * 2 )             a 3   =  A( ( n wid t h /m in _ s td v ec ) * 4 - 1   d o wn t o   ( n wid t h /m in _ s td v ec ) * 3 )                                         b 0   =  B ( ( n wid th /m i n _ s td v ec ) - 1   d o wn to   0 )                 b 1   =  B ( ( n wid th /m i n _ s td v e c) * 2 - 1   d o wn t o   ( n wid t h /m in _ s td v ec ) )               b 2   =  B ( ( n wid th /m i n _ s td v ec ) * 3 - 1   d o wn t o   ( n wid t h /m in _ s td v ec ) * 2 )             b 3   =  B ( ( n wid th /m i n _ s td v ec ) * 4 - 1   d o wn t o   ( n wid t h /m in _ s td v ec ) * 3 )               /*   4   K A   ca lls   to   co m p u te   M 0 , M 1 , M 2 , M 3 ;   M 1,   2 , M 1,   3   a n d   M 2,   3   */             k ar atsu b a( a 0   , b 0 , M 0 )                 k ar atsu b a( a 1   , b 1 , M 1 )              k ar atsu b a( a 2   , b 2 , M 2 )                 k ar atsu b a( a 3   , b 3 , M 3 )                   a' 0, 1  = a 0   +   a1             a' 0, 2  = a 0   +   a 2             a' 0, 3   = a 0   + a 3             a' 1, 2  = a 1   +   a 2             a' 1, 3  = a 1   +   a 3               a' 2, 3  = a 2   +   a 3                 b' 0, 1  = b 0   +  b 1             b' 0, 2  = b 0   +  b 2             b' 0, 3   = b 0   + b 3             b' 1, 2  = b 1   +  b 2             b' 1, 3  = b 1   +  b 3               b' 2, 3  = b 2   +  b 3                   /*   6   K A   ca lls   to   co m p u te   */             k ar atsu b a( a' 0, 1 ,   b ' 0, 1 , M 0,   1 )             k ar atsu b a( a' 0, 2 ,   b ' 0, 2 , M 0,   2 )             k ar atsu b a( a' 0, 3 ,   b ' 0, 3 , M 0,   3 )              k ar atsu b a( a' 1, 2 ,   b ' 1, 2 , M 1,   2 )              k ar atsu b a( a' 1, 3 ,   b ' 1, 3 , M 1,   3 )              k ar atsu b a( a' 2, 3 ,   b ' 2, 3 , M 2,   3 )               te r m 7   = M 3                                                               x 6             te r m 6   = M 2,   3  −   M 2   −   M 3                                 x 5             te r m 5   = M 1,   3  −   M 1   −   M 3   + M 2                    x 4             te r m 4   = M 0,   3  −   M 0   −   M 3   + M 1,   2  −   M 1   −   M 2     x 3             te r m 3   = M 0,   2  −   M 0   −   M 2   + M 1                    x 2               te r m 2   = M 0,   1   −   M 0   −   M 1                                   x 1               te r m 1   = M 0                                                               x 0               r esu lt =   ter m 7 _ s lr   +  ter m 6 _ s lr   +  ter m 5 _ s lr   +  ter m 3 _ s lr   +   ter m 4 _ s lr   +  ter m 2 _ s lr   +  ter m 1 _ s lr     en d   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J Reco n f ig u r a b le  &   E m b ed d ed   Sy s t   I SS N:  2089 - 4 8 6 4       E fficien t a d a p ta tio n   o f th e   K a r a ts u b a   a lg o r ith m  fo r   imp leme n tin g   o n   …   ( Wa ld er A n d r e )   239       Fig u r e  2 .  Gen e r ic  n - b it ×   n - b it th ir d - d e g r ee   Kar atsu b a  i n p u t  p r ep r o ce s s in g             Fig u r e  3 .  C ( X)   g e n er atio n   f o r   a  32 - b it ×   3 2 - b it  Kar atsu b a   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :  2 0 8 9 - 4 8 6 4   I n t J Reco n f ig u r a b le  &   E m b ed d ed   Sy s t,  Vo l.  9 ,   No .   3 ,  No v e m b er   2 0 2 0 :   235   –   2 4 1   240   3.   RE SU L T S  A ND   AN AL Y SI S   Sectio n   3 . 1   an d   3 . 2   s h o w  th e   s im u latio n   an d   im p lem en tati o n   r esu lts   f o r   3 2 - b it  x   3 2 - b it,  1 2 8 - b it  x   128 - b it,  an d   5 1 2 - b it x   5 1 2 - b it  m u ltip li er s .      3 . 1 .   Sim ula t io n r esu lt s   Fo r   th e  s ak e  o f   v is ib ilit y ,   we  p r esen t a   s h o r ten ed   p ar t o f   th e  s im u latio n s   in   Fig u r e  4 ,   Fig u r e  5 ,   an d   Fig u r e  6 .   T h e  r esu lts   f o r   t h e  th r ee   im p lem en ted   m u ltip lier s   a r e  co n s is ten t a n d   g i v e  th e  ex p ec ted   v alu es .           Fig u r e  4 .  Kar atsu b a   m u ltip lier   32 - b it ×   3 2 - b it si m u latio n   r es u lts           Fig u r e  5 .  Kar atsu b a   m u ltip lier   128 - b it ×   1 2 8 - b it si m u latio n   r esu lts           Fig u r e  6 .  Kar atsu b a   m u ltip lier   5 1 2 - b it ×   5 1 2 - b it si m u latio n   r esu lts       3 . 2 .   I m plem ent a t io n r esu lt s   As  s h o wn   in   Fig u r e  7 ,   th e  i m p lem en tatio n   o n   FP GA  o f   th e  3 2 - b it  ×  3 2 - b it  d o es  n o t  d is p lay   an y   er r o r .   Of   th e  5 0 0   lim ited   I O  ca p ab ilit y ,   o n ly   6 4   ar e   b o u n d e d ,   an d   1 8 4 4 / 2 0 3 8 0 0   s lice  L UT s   ar e  u s ed .   R eg ar d in g   1 2 8 - b it  x   1 2 8 - b it.  B y   q u ad r u p lin g   th e  m u ltip lier   s ize,   we  m u ltip ly   b y   a  f ac t o r   o f   1 0   th e  s ize  o f   th e   s lice  L UT s   u s ed ,   as d ep icted   i n   Fig u r e  8 .   T h e  im p lem en tatio n   o f   th e  1 2 8 - b it x   1 2 8 - b it m u lt ip lier   ex ce ed ed   th e   I O  ca p ab ilit ies  o f   th e  FP GA,   a s   s h o wn   in   Fig u r e  8 .   An d   it  g o t  wo r s e  with   th e  im p lem en tati o n   o f   th e  5 1 2 - b it  x   512 - b it  m u lt ip lier ,   as  s h o wn   i n   Fig u r e   9 .   T h is   r esu lt   is   n o t   a   s u r p r is e  a n d   d o es  n o t  d ep en d s   o n   th e   s ch em e   b u t  r ath er   th e  ca p ac ity   o f   th e  FP GA  u s ed .           Fig u r e  7 .  Kar atsu b a   m u ltip lier   3 2 - b it ×   3 2 - b it im p lem en tatio n   r esu lts       Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J Reco n f ig u r a b le  &   E m b ed d ed   Sy s t   I SS N:  2089 - 4 8 6 4       E fficien t a d a p ta tio n   o f th e   K a r a ts u b a   a lg o r ith m  fo r   imp leme n tin g   o n   …   ( Wa ld er A n d r e )   241       Fig u r e  8 .  Kar atsu b a   m u ltip lier   1 2 8 - b it ×   1 2 8 - b it im p lem en ta tio n   r esu lts             Fig u r e  9 .  Kar atsu b a   m u ltip lier   5 1 2 - b it ×   5 1 2 - b it im p lem en ta tio n   r esu lts         4.   CO NCLU SI O N   I n   th is   p ap er ,   we  h av e  p r o p o s ed   a  m o d if ied   v er s io n   o f   th e   Kar atsu b a  alg o r ith m   as  well   as  a  n ew   s ch em e  to   f ac ilit ate  FP GA  im p lem en tatio n .   R esu lts   o b tain ed   f r o m   3 2 - b it  x   3 2 - b it  Kar atsu b a  m u ltip lier ,   1 2 8 - b it  x   1 2 8 - b it  Kar atsu b a  m u lt ip lier ,   an d   5 1 2 - b it  x   5 1 2 - b it  Kar atsu b a  m u ltip lier   h av e  m et  th e  ex p ec tatio n .     T h ey   ar e   p r o m is in g   f o r   ap p licatio n s   th at  r eq u ir e  t h e  r ap id   im p lem en tatio n   an d   r ec o n f ig u r atio n   o f   cr y p to g r ap h ic  alg o r ith m s .   T h e  n ex t  s tep   is   to   u s e  th ese   m u ltip lier s   to   im p lem en t  a  co m p lete   cr y p to g r a p h ic  al g o r ith m   o n   FP GA .       ACK NO WL E DG E M E NT S   T h e  au th o r   wo u ld   lik e   to   t h an k   C MC  Mic r o s y s tem s   f o r   p r o v id in g   d esig n   to o ls ,   m at er ials ,   an d   s u p p o r t .       RE F E R E NC E S   [1 ]   W.   An d re   a n d   O .   Co u il lard ,   " De s ig n   a n d   imp lem e n tatio n   o f   a   n e w  a rc h it e c tu re   o f  a   re a l - ti m e   re c o n fi g u ra b le  d i g it a l   m o d u lat o r  (DM)   in to   Q P S K,8 - P S K,  a n d   1 6 - P S K  o n   F P G A,"   In ter n a ti o n a l  J o u rn a l  o f  Rec o n fi g u ra b le  a n d   Emb e d d e d   S y ste ms ,  v o l.   7 ,   n o .   3 ,   p p .   1 7 3 - 185 ,  2 0 1 8 .   [2 ]   K .  Kw a n g jo ,  " Cry p t o g ra p h y :  A  n e w  o p e n   a c c e ss   jo u r n a l , "  Cry p t o g ra p h y ,   v o l.   1 ,   n o .   1 ,   p p .   1 - 4,     2 0 1 6 .   [O n li n e ].   Av a il a b le:  h tt p s:// p d fs . se m a n ti c sc h o lar. o rg / d 7 8 d / 5 9 fc 0 8 d e 0 b 1 b 2 f4 3 2 4 9 c c 0 a 5 8 6 a 8 fe b f5 e 6 d . p d f.   [3 ]   Cisc o   S e c u rit y ,   " Ne x t  G e n e ra ti o n   Cr y p t o g ra p h y , "   T o o ls   Cisc o ,   2 0 1 5 .   [ On l in e ] .   Av a il a b le:   h tt p s:/ /t o o ls.cisc o . c o m /se c u rit y /ce n ter/re so u rc e s/n e x t _ g e n e ra ti o n _ c r y p t o g ra p h y .   [4 ]   K.  Ha rik a ,.   e t   a l ,   " A n a ly sis  o f  d if fe re n t  m u lt i p li c a ti o n   a lg o rit h m s  &   F P G A  imp lem e n tatio n , "   IOS R  J o u rn a l  o f  V L S I   a n d   S i g n a l  Pr o c e ss in g   (IOSR - JV S P )  v ol .   4 ,   n o .   2 ,   p p .   29 - 35 , 2 0 1 4 .   [5 ]   P .   M o n tg o m e ry ,   " M o d u lar  m u lt i p li c a ti o n   wit h o u t  tri a l  d i v isio n , "   M a th e ma t ics   o f  c o mp u ta ti o n ,  v o l.   4 4 ,   n o .   1 7 0 ,   p p .   519 – 5 2 1 ,   1 9 8 5 .   [6 ]   D.  Ya n g   e t  al .,  " Eff icie n t  F P G A  imp lem e n tatio n   o f  m o d u lar  m u lt ip li c a ti o n   b a se d   o n   M o n t g o m e ry   a lg o rit h m , "   M icr o p r o c e ss o rs   a n d   M icr o sy ste ms ,  v ol .   4 7 ,   p p .   2 0 9 - 2 1 5 ,  2 0 1 6 .   [7 ]   Jo a c h im  v o n   z u r  G a th e n   a n d   Ja m sh id   S h o k ro ll a h i,   " Eff icie n t  F P G A - b a s e d   Ka ra tsu b a   m u lt i p li e rs  fo r  p o l y n o m ials  ove r   F 2 , "   In ter n a ti o n a l  W o rk sh o p   o n   S e lec ted   Are a s  in   Cry p t o g r a p h y   S AC  2 0 0 5 :  S e lec ted   Are a s  i n   Cry p to g ra p h y   p p   3 5 9 - 3 6 9 ,  2 0 0 5 .   [8 ]   D.  S u z u k i,   " H o w  t o   m a x imiz e   th e   p o ten t ial  o f   F P G A  re so u rc e s  fo r  m o d u lar  e x p o n e n ti a ti o n , "   Cry p to g ra p h ic   Ha rd wa re   a n d   Emb e d d e d   S y ste ms - CHES   2 0 0 7 ,   p p .   2 7 2 – 2 8 8 ,   2 0 0 7 .   [9 ]   J.  S a m a n ta ,.   e t  a l,   " M o d i fied   Ka ra tsu b a   m u lt i p li e r  f o r  k e y   e q u a ti o n   s o lv e r  in   RS   C o d e , "  i n   R a d i o e lec tro n ics   a n d   Co mm u n ica ti o n s S y ste ms ,   v o l.   58 ,   n o .   10 ,   p p .   4 5 2 - 4 6 1 ,   2 0 1 5 .   [1 0 ]   A.  Weim e rsk irch   a n d   C.   P a a r,   " G e n e r a li z a ti o n s  o f  th e   Ka ra tsu b a   a lg o rit h m   fo r  e fficie n t  imp lem e n t a ti o n s, "   IACR   Cry p to l.   e Pri n t  Arc h ,   p p .   1 - 1 7 ,   2 0 0 6 .   [On li n e ].   Av a il a b le:  h t tp :/ /ep r in t. iac r. o r g / 2 0 0 6 / 2 2 4 . p d f .   Evaluation Warning : The document was created with Spire.PDF for Python.