RSA
אלגוריתמים

כדי ליישם את RSA במחשב אין די בדרך הרגילה באמצעות יחידת החישוב במעבד, כיוון שאורך מקסימלי של מספר שניתן לעיבוד בדרך קונבנציונלית אינו עולה על גודלו של האוגר הגדול ביותר. ככל שהמחשבים השתפרו, הצורך באריתמטיקה מודולרית במספרים גדולים בהרבה רק הלך וגדל. משום כך הפתרון הוא אריתמטיקה מרובת ספרות (Multi-precision), כלומר חישוב ספרה אחר ספרה בנפרד כאשר כל ספרה תופסת קרוב לאוגר שלם. בדרך זו החישוב יותר איטי, אך אורך המספרים אינו מוגבל (בגבולות הזיכרון הזמין במחשב). קיימות ספריות לחישובים אריתמטיים מרובי ספרות לשפות התכנות הנפוצות כמו FreeLIP לשפת C של ארג'ן לנסטרה, שסייעה באתגר הראשון כנגד RSA, פירוק RSA-129 ב־1994 או המחלקה BigInteger של Java.
מרכיב חשוב בהכנת RSA הוא יצירת מפתח הפענוח  \ d שנקרא הופכי כפלי מודולרי של  \ e (מודולו  \ n). כדי למצוא מספר כזה צריך לפתור את משוואת אוקלידס  \ de+k\phi (n)=1 עבור שלם  \ k כלשהו. אפשר לבצע זאת באמצעות אלגוריתם אוקלידס המורחב. להלן הגרסה הבסיסית:
MultiplicativeInverse(a, b)
{
 y1 = 1, y2 = 0;

 While (b > 0)
 {
 q = a/b;
 y = y2 –(q * y1);
 r = a % b;
 a = b, b = r;
 y2 = y1, y1 = y;
 }
 return y2;
}
הצפנה ופענוח דורשים פעולות העלאה בחזקה עם מעריך גדול. הדרך הנאיבית לחישוב חזקה אינה יעילה במקרה זה. קיימים מספר אלגוריתמים לחישוב חזקות גדולות באריתמטיקה מודולרית. להלן תיאור שיטה רקורסיבית בסיסית שנקראת Square and Multiply או "העלאה בחזקה משמאל לימין". הרעיון הוא שאפשר לחשב את  \ a^{k}\ {\mbox{mod}}\ n באמצעות סדרת הריבועים  \ a,a^{2},a^{4},a^{8},... עד  \ a^{k}, אפשר להכין סדרה כזו באופן רקורסיבי על ידי העלאות חוזרות בריבוע:  a_{i}=a_{i-1}^{2}{\text{ mod }}n. לפי חוקי האריתמטיקה מודולו  n אפשר לבצע את הצמצום המודולרי לאחר כל העלאה בריבוע במקום לבצע את הצמצום בסוף ובכך להימנע מהתנפחות התוצאה. לפי חוקי החזקות אפשר לקבל את  a^{k} כמכפלה של ערכים מתוך הסדרה האמורה, אותם אפשר לקבל על ידי הייצוג הבינארי של המעריך, דהיינו כאשר הסיבית הנוכחית היא אחד יש לכלול את האיבר המתאים במכפלה. הטבלה הבאה מדגימה את  245^{3125}{\mbox{ mod }}10237. הפרמטר  k בטבלה מכיל את הייצוג הבינארי של המעריך:  \{1,1,0,0,0,0,1,1,0,1,0,1\}_{2} כאשר הסיבית הימנית היא הסיבית הכי פחות משמעותית והסיבית השמאלית היא הסיבית המשמעותית ביותר. התוצאה תהיה מכפלת ערכי  a בעמודות בהן  k_{i}=1 כלומר
|  i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  {\boldsymbol {k}} | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 |
|  {\boldsymbol {a}} | 245  | 8840 | 6579  | 1205 | 8608  | 2258  | 538 | 2808 | 2374 | 5526 | 9942  | 5129 |
|  {\boldsymbol {b}} | 245 | 245 | 4646 | 4646 | 7046 | 1570 | 1570 | 1570 | 1570 | 1570 | 7752 | 9737 |
את החישוב הזה קשה לעשות בדרך הישירה כמו באמצעות מחשבון כי תוצאת הביניים של ההעלאה בחזקה לפני החילוק היא באורך כאלף ספרות עשרוניות שזה מספר ארוך מדי מכדי להכילו במשתנה אחד. להלן פסאודו קוד של האלגוריתם:
Square_and_multiply(a, k, n)
{
 b = 1;
 while (k > 0)
 {
 if ((k & 1) == 1)
 b = ((b * a) % n);
 a = ((a * a) % n);
 k >>= 1;
 }
 return b;
}
\ k המייצג את  \ t סיביות המעריך  \ k_{1},k_{2},...,k_{t}. בלולאה הראשית סורקים את סיביות  \ k מימין לשמאל (מהספרה הכי פחות משמעותית לספרה הכי משמעותית), מעלים את  \ a בריבוע בכל סבב וכל פעם שהסיבית הנוכחית היא 1 בנוסף מכפילים ב־ \ b. התוצאה הסופית נשמרת ב־ \ b.
החלק הקשה באלגוריתם הוא הצמצום המודולרי. בשיטה הנאיבית מחלקים חילוק ארוך ב־ n ונוטלים את השארית. השימוש בחילוק גוזל זמן עיבור ולכן במספרים גדולים מאוד אינו מומלץ אם רוצים להגיע לביצועים אופטימליים. קיימות שיטות יעילות יותר לצמצום מודולרי כמו שיטת "חלון הזזה" שיטת Barrett ושיטת מונטגומרי. האחרונה נחשבת ליעילה ונפוצה במימושים מעשיים. לשיפור נוסף בביצועים יש המיישמים את פעולות הכפל במספרים הגדולים (מגודל מינימלי שנקבע לפי המערכת) בשיטת קרצובה או טום־קוק בסגנון הפרד ומשול.