כדי ליישם את RSA במחשב אין די בדרך הרגילה באמצעות יחידת החישוב במעבד, כיוון שאורך מקסימלי של מספר שניתן לעיבוד בדרך קונבנציונלית אינו עולה על גודלו של האוגר הגדול ביותר. ככל שהמחשבים השתפרו, הצורך באריתמטיקה מודולרית במספרים גדולים בהרבה רק הלך וגדל. משום כך הפתרון הוא אריתמטיקה מרובת ספרות (Multi-precision), כלומר חישוב ספרה אחר ספרה בנפרד כאשר כל ספרה תופסת קרוב לאוגר שלם. בדרך זו החישוב יותר איטי, אך אורך המספרים אינו מוגבל (בגבולות הזיכרון הזמין במחשב). קיימות ספריות לחישובים אריתמטיים מרובי ספרות לשפות התכנות הנפוצות כמו FreeLIP לשפת C של ארג'ן לנסטרה, שסייעה באתגר הראשון כנגד RSA, פירוק RSA-129 ב־1994 או המחלקה BigInteger של Java.
מרכיב חשוב בהכנת RSA הוא יצירת מפתח הפענוח formula_20 שנקרא הופכי כפלי מודולרי של formula_34 (מודולו formula_56). כדי למצוא מספר כזה צריך לפתור את משוואת אוקלידס formula_246 עבור שלם formula_128 כלשהו. אפשר לבצע זאת באמצעות אלגוריתם אוקלידס המורחב. להלן הגרסה הבסיסית:
MultiplicativeInverse(a, b)
y1 = 1, y2 = 0;
While (b &gt; 0)
q = a/b;
y = y2 –(q * y1);
r = a % b;
a = b, b = r;
y2 = y1, y1 = y;
return y2;
הצפנה ופענוח דורשים פעולות העלאה בחזקה עם מעריך גדול. הדרך הנאיבית לחישוב חזקה אינה יעילה במקרה זה. קיימים מספר אלגוריתמים לחישוב חזקות גדולות באריתמטיקה מודולרית. להלן תיאור שיטה רקורסיבית בסיסית שנקראת Square and Multiply או "העלאה בחזקה משמאל לימין". הרעיון הוא שאפשר לחשב את formula_248 באמצעות סדרת הריבועים formula_249 עד formula_250, אפשר להכין סדרה כזו באופן רקורסיבי על ידי העלאות חוזרות בריבוע: formula_251. לפי חוקי האריתמטיקה מודולו formula_2 אפשר לבצע את הצמצום המודולרי לאחר כל העלאה בריבוע במקום לבצע את הצמצום בסוף ובכך להימנע מהתנפחות התוצאה. לפי חוקי החזקות אפשר לקבל את formula_253 כמכפלה של ערכים מתוך הסדרה האמורה, אותם אפשר לקבל על ידי הייצוג הבינארי של המעריך, דהיינו כאשר הסיבית הנוכחית היא אחד יש לכלול את האיבר המתאים במכפלה. הטבלה הבאה מדגימה את formula_254. הפרמטר formula_255 בטבלה מכיל את הייצוג הבינארי של המעריך: formula_256 כאשר הסיבית הימנית היא הסיבית הכי פחות משמעותית והסיבית השמאלית היא הסיבית המשמעותית ביותר. התוצאה תהיה מכפלת ערכי formula_121 בעמודות בהן formula_258 כלומר
את החישוב הזה קשה לעשות בדרך הישירה כמו באמצעות מחשבון כי תוצאת הביניים של ההעלאה בחזקה לפני החילוק היא באורך כאלף ספרות עשרוניות שזה מספר ארוך מדי מכדי להכילו במשתנה אחד. להלן פסאודו קוד של האלגוריתם:
Square_and_multiply(a, k, n)
b = 1;
while (k &gt; 0)
if ((k &amp; 1) == 1)
b = ((b * a) % n);
a = ((a * a) % n);
k »= 1;
return b;
formula_128 המייצג את formula_261 סיביות המעריך formula_262. בלולאה הראשית סורקים את סיביות formula_128 מימין לשמאל (מהספרה הכי פחות משמעותית לספרה הכי משמעותית), מעלים את formula_116 בריבוע בכל סבב וכל פעם שהסיבית הנוכחית היא 1 בנוסף מכפילים ב־formula_265. התוצאה הסופית נשמרת ב־formula_265.
החלק הקשה באלגוריתם הוא הצמצום המודולרי. בשיטה הנאיבית מחלקים חילוק ארוך ב־formula_2 ונוטלים את השארית. השימוש בחילוק גוזל זמן עיבור ולכן במספרים גדולים מאוד אינו מומלץ אם רוצים להגיע לביצועים אופטימליים. קיימות שיטות יעילות יותר לצמצום מודולרי כמו שיטת "חלון הזזה" שיטת Barrett ושיטת מונטגומרי. האחרונה נחשבת ליעילה ונפוצה במימושים מעשיים. לשיפור נוסף בביצועים יש המיישמים את פעולות הכפל במספרים הגדולים (מגודל מינימלי שנקבע לפי המערכת) בשיטת קרצובה או טום־קוק בסגנון הפרד ומשול.
התקפות.
התקפת ערוץ צדדי.
Timing Attack היא התקפת ערוץ צדדי שעושה שימוש בעובדה שמהירות ההצפנה תלויה בקלט. אם לתוקף יש גישה למערכת (כמו כרטיס חכם או מעגל משולב במכשיר) שבו מתבצעים ההצפנה והפענוח, אך אין לו גישה למפתח הפענוח עצמו המוטמע במערכת. עדיין ביכולתו לחלץ את המפתח באמצעות מדידת הפרשי הזמן בעת פענוח מספר מסוים של טקסטים מוצפנים. יתרה מזו, אם מיישמים אחת מהגרסאות הממוטבות של RSA שעושה שימוש בגורמים הראשוניים, הדבר עלול להוביל לפרצה מסוימת כיוון שניתן למדוד את המידע שדולף מהמערכת בזמן חישוב מערכת הקונגרואנציות של CRT בגלל התלות בסיביות של המספרים הראשוניים. כמו כן אם ארעה שגיאת חומרה במהלך החישוב וחלק מסיביות הפרמטרים השתבשו עקב כך, יש סכנה שמידע פנימי ידלוף.
ישנן דרכים להתמודד עם זה. למשל להבטיח שתהליך הפענוח יתרחש בזמן קבוע על ידי השהיה מכוונת. אולם בדרך זו יעילות המערכת נפגעת. גישה אחרת הנקראת Blinding מנצלת את תכונת הכפליות של RSA (להלן). במקום לפענח את הטקסט המוצפן ישירות, בוחרים formula_268 אקראי כלשהו ואז מחשבים את: formula_269 והתוצאה תהיה formula_270. ניתן להסיר את הערך האקראי מהמסר על ידי הכפלה ב־formula_271 (ההופכי של formula_268 מודולו formula_56). בצורה זו הפענוח אינו תלוי בטקסט המוצפן המתקבל ועל כן התקפת תזמון תכשל במקרה כזה. כמו כן יש לוודא תמיד שהודעות השגיאה של המערכת לא יסגירו מידע פנימי, על ידי בדיקה תמידית של תקפות ערכים וכן לוודא שהזמן הדרוש לכל פעולה יהיה קבוע ללא תלות בשגיאה או בנקודת הזמן בו ארעה.
התקפת האדם שבתווך.
הצפנת RSA אינה פותרת את בעיית האימות והבטחת השלמות. במילים אחרות, תוקף אקטיבי המסוגל להשתלט על ערוץ התקשורת שבין אליס ובוב יכול בהתקפת אדם באמצע ליירט את מפתח ההצפנה שאליס שולחת לבוב, להחליפו באחר כך שבוב יצפין את כל המסרים עבור אליס במפתח הלא נכון. בדרך דומה מיירט ומשנה את המסרים שבוב שולח לאליס, מפענח את תוכנם, חוזר ומצפינם במפתח המקורי של אליס ושולחם ליעדם. כאשר בוב ואליס אינם מודעים למתרחש. במילים אחרות, בוב חייב להיות בטוח שהמפתח הפומבי שייך לאליס וכן אליס אינה יכולה לדעת מיהו מקור המסר שקיבלה ללא אמצעים נוספים כדי להבטיח זאת. הבטחת שלמות ואותנטיות מפתחות ההצפנה והמסרים נעשים בפרוטוקולים שונים חלקם נעזרים בצד־שלישי נאמן (כמו רשות אישורים CA) וחתימה דיגיטלית.
פרס טיורינג
פרס טיורינג (באנגלית: ACM A.M. Turing Award) הוא פרס בין־לאומי בתחום מדעי המחשב. הוא ניתן על ידי ה־ACM, האגודה למכונות מחשוב, בגין הישג יוצא דופן בתחום מדעי המחשב. בתחום זה שקול הפרס מבחינת יוקרתו לפרס נובל, אשר אינו מוענק בתחומי המתמטיקה ומדעי המחשב. (הפרס המקביל בתחום המתמטיקה הוא מדליית פילדס). הפרס קרוי על שמו של אלן טיורינג, מתמטיקאי בריטי שנחשב לאבי מדעי המחשב התאורטיים והבינה המלאכותית.
הפרס ניתן מדי שנה, החל משנת 1966. משנת 2007 חולק לזוכים פרס כספי של 250,000 דולר שמומן על ידי החברות אינטל וגוגל.
החל משנת 2014, גובה הפרס הוא מיליון דולר, במימון חברת גוגל.
בארבעים שנותיו הראשונות נמנו רק גברים עם מקבלי הפרס. בשנת 2006 ניתן הפרס לראשונה לאישה - פרנסס אלן, על תרומתה בתחום המהדרים ומיטוב הקוד שהם יוצרים.
התפלגות הזוכים בפרס לפי מדינות.
התפלגות הזוכים בפרס לפי מדינות (נכון לשנת 2017) היא:
נכון לשנת 2014, שבעה עשר מתוך 62 הזוכים הם ממוצא יהודי (27.4%), בהם חמישה ישראלים:
ניקולאוס קופרניקוס
ניקולאוס קוֹפֶּרניקוּס (חתם את שמו כ:Niklas Koppernigk, בגרסה הלטינית: Nicolaus Copernicus; 19 בפברואר 1473 - 24 במאי 1543) היה אסטרונום, מתמטיקאי ואיש אשכולות בן תקופת הרנסאנס, נתין נסיכות-הבישוף של וארמייה. ידוע כמי שפיתח את המודל ההליוצנטרי (שלפיו כוכבי הלכת סובבים את השמש), באופן מפורט מספיק כדי שיהיה שימושי מבחינה מדעית. שימש כאיש כנסייה, מושל, משפטן, אסטרולוג ורופא, בעוד האסטרונומיה הייתה עיסוק צדדי ותחביב שלו. התאוריה שלו לגבי מיקומהּ של השמש במרכז מערכת השמש, בניגוד למודל הגאוצנטרי (ששם את כדור הארץ במרכז) ששלט בכיפה עד אז, נחשבת לאחת התגליות החשובות ביותר בהיסטוריה. היא נקודת התחלה בסיסית באסטרונומיה המודרנית ובמדע המודרני בכלל, וניתן לומר כי פתחה את המהפכה המדעית המודרנית. התאוריה שלו השפיעה גם על תחומים רבים אחרים בחיים האנושיים.
ביוגרפיה.
קופרניקוס נולד ב-1473 בעיר טורון שבפרוסיה המלכותית, אז ברית נחלות אוטונומיות שהייתה כפופה לממלכת פולין. אביו, ניקלאס, אזרח קרקוב (בירת פולין דאז), עבר לשם ב-1460 ונעשה לאזרח מכובד בטורון לאחר המלחמה עם האבירים הטבטונים. הוא היה סוחר נחושת עשיר, שמת כשקופרניקוס היה בן עשר. על אמו, ברברה ווצנרודה, ידוע אך מעט, אך כנראה היא מתה עוד לפני בעלה. דודו מצד האם, לוקאס ווצנרודה, איש כנסייה ואחר-כך הנסיך-בישוף של וארמייה, גידל אותו ואת שלושת אחיו לאחר מות אביהם. אחיו אנדריאס נעשה לכומר בפראואנבורג. אחותו, ברברה, נעשתה לנזירה בנדיקטינית, ואחותו האחרת, קתרינה, נישאה לאיש עסקים, ברתל גֶרטנר.