RSA

RSA היא מערכת הצפנת מפתח ציבורי דטרמיניסטית מעשית הראשונה שהומצאה והיא עדיין בשימוש נרחב במערכות אבטחת מידע מודרניות, תקשורת מחשבים ומסחר אלקטרוני. ב־RSA, כבכל מערכת מפתח ציבורי, מפתח ההצפנה אינו סודי והוא שונה ממפתח הפענוח שנשמר בסוד, על כן היא נקראת אסימטרית. האסימטריה ב־RSA נובעת מהקושי המעשי שבפירוק לגורמים של מספר פריק שהוא כפולה של שני ראשוניים גדולים, שהיא בעיה פתוחה בתורת המספרים. השם RSA נובע מראשי התיבות של שמות המשפחה של הממציאים, רון ריבסט, עדי שמיר ולאונרד אדלמן, שפרסמו את האלגוריתם לראשונה ב־1977. ישנן עדויות שהאלגוריתם היה ידוע עוד קודם לכן לשירותי המודיעין של ארצות הברית והממלכה המאוחדת ונשמר בסוד מטעמים של ביטחון לאומי.

ערך זה עוסק בשיטת הצפנה. אם התכוונתם למשמעות אחרת, ראו RSA (פירושונים).

ב-RSA השולח משתמש במפתח ההצפנה הציבורי של הנמען כדי להצפין עבורו מסר כך שרק הנמען מסוגל לפענחו באמצעות המפתח הפרטי המתאים שברשותו. המפתח הציבורי כולל שלם ${\displaystyle e}$ יחד עם השלם הפריק ${\displaystyle n}$ שהוא כפולה של שני ראשוניים גדולים שווים באורכם בקירוב, הנקרא מודולוס. הצפנה היא העלאת המסר בחזקת ${\displaystyle e}$ מודולו ${\displaystyle n}$ ואילו פענוח נעשה על ידי הפעולה ההפוכה אותה הנמען מבצע על ידי העלאת הטקסט המוצפן בחזקת ההופכי הכפלי של ${\displaystyle e}$ שהוא המפתח הסודי ${\displaystyle d}$ (שאותו אפשר לכתוב גם: ${\displaystyle e^{-1}}$) במילים אחרות פענוח שקול להוצאת שורש ממעלה ${\displaystyle e}$ מודולו ${\displaystyle n}$.

בידיעת הגורמים הראשוניים חישוב המפתח הסודי ${\displaystyle d}$ מתוך המפתח הציבורי ${\displaystyle e}$ הוא מלאכה קלה, כפי שיתואר בהמשך ואילו ללא ידיעת הגורמים הראשוניים לא ידועה דרך יעילה לחישובו בזמן סביר. לכן "הקושי" נמדד במספר הפעולות האלמנטריות הנדרש כדי לפרק את המודולוס לגורמים. ההבדל בפקטור העבודה בין העלאה בחזקה מודולרית לבין חישוב שורש מודולרי שהן פעולות הופכיות, הוא המקור לפונקציה החד־כיוונית שבבסיס RSA. שבירת מערכת ההצפנה, דהיינו פענוח המידע ללא ידיעת הגורמים הראשוניים של ${\displaystyle n}$ נקרא בעיית RSA. היא נחשבת לבעיה קשה אם כי אין הוכחה שהיא קשה לפחות כפירוק לגורמים. אלגוריתם RSA נחשב איטי יחסית ועל כן אינו מתאים להצפנה ישירה של מידע בכמות גדולה. במקום זאת, במערכת הצפנה היברידית, RSA משמש לשיתוף והעברה של מפתח להצפנה סימטרית, אשר בתורו משמש להצפנת המידע עצמו עם אלגוריתם מועדף כמו AES.

RSA שאבה השראה מרעיון המפתח הציבורי שנהגה כשנה קודם לכן על ידי ויטפילד דיפי ומרטין הלמן והוא האלגוריתם האסימטרי הראשון ששימש גם להצפנה וגם לחתימה דיגיטלית. RSA היה לפורץ דרך בתולדות ההצפנה המודרנית והמצאתו העלתה את בעיית פירוק לגורמים לחזית המחקר בתורת המספרים היישומית, שכן ביטחונו מסתמך על כך שלא ניתן לפתור בעיה זו בפרק זמן סביר. אלגוריתם RSA אינו פוסט־קוונטי, כלומר עם המצאת מחשב קוונטי מעשי בקנה מידה גדול, צופן RSA לא יהיה בטוח יותר לשימוש משום שבעיית פירוק לגורמים תהיה קלה לפתרון באמצעות אלגוריתם שור.

היסטוריה

עדי שמיר בכנס בנושא המאגר הביומטרי, אפריל 2012

החיסרון העיקרי בצפנים סימטריים הוא שהמפתח הסודי נדרש הן להצפנה והן לפענוח ולכן יש צורך להעבירו לידי השולח בדרך כלשהי ובכך לסכנו בחשיפה. ב־1976 פרסמו ויטפילד דיפי ומרטין הלמן מאמר המתאר את התפיסה של ההצפנה האסימטרית, שבה הנמען מפרסם מפתח הצפנה פומבי בעזרתו מבוצעת הצפנת מסרים הנשלחים אליו, ואילו הפענוח מתבצע אך ורק באמצעות המפתח הפרטי שברשותו, שמעולם לא נחשף. כשנה לאחר מכן ב־1977, רונלד ריבסט, עדי שמיר ולאונרד אדלמן מ־MIT פרסמו לראשונה במגזין סיינטיפיק אמריקן את RSA, שיישם לראשונה את המודל של דיפי והלמן באופן מעשי. אלגוריתם RSA זיכה את ממציאיו בפרס טיורינג לשנת 2002.

זכויות יוצרים

RSA נרשם כפטנט בארצות הברית בשנת 1983 ותוקפו פג בספטמבר 2000. בדצמבר 1997 פרסם מטה התקשורת של המודיעין הבריטי GCHQ מסמך בו נטען כי רעיון המפתח הפומבי היה ידוע להם כעשור לפני שהתפרסם. הם גילו לטענתם גם את RSA וגם את דיפי־הלמן, אך שמרו את הדבר בסוד. גם ה־NSA טען שגילה את RSA הרבה לפני שנודע לציבור, אולם התגלית סווגה כסוד לאומי. המתמטיקאי הבריטי קליפורד קוקס שעבד בסוכנות הביון הבריטית, פרסם מסמך^[1] בו נטען כי ב־1973 המציא אלגוריתם הצפנה דומה ל־RSA. ייתכן שבקהיליית המודיעין המצאות אלו היו ידועות שנים רבות לפני שהציבור התוודע להן. בכל מקרה ספק אם לממצאים אלו הייתה תועלת מעשית כלשהי באותה עת.

הכנה

בגרסת RSA הבסיסית, תחילה להכנה:

1. בוחרים שני מספרים ראשוניים גדולים ${\displaystyle \ p}$ ו־${\displaystyle \ q}$
2. מחשבים את ${\displaystyle \ n=pq}$
3. מחשבים את ${\displaystyle \ \phi (n)=(p-1)(q-1)}$. הפונקציה ${\displaystyle \phi }$ נקראת פונקציית אוילר המייצגת את סדר החבורה.
4. בוחרים שלם ${\displaystyle 1<e<\phi (n)}$ שהוא זר ל־${\displaystyle \phi (n)}$ (בעבר היה נהוג לבחור e=3, אך התגלו בו פרצות אבטחה. היום נהוג לבחור e=65537)
5. מחשבים ${\displaystyle \ d}$ המקיים את הקונגרואנציה: ${\displaystyle de\equiv 1\ ({\mbox{mod }}\phi (n))}$. כלומר מקיים את: ${\displaystyle de\ {mod}\ \phi (n)=1}$.

פירוט הפרמטרים

• ${\displaystyle \ p}$ ו־${\displaystyle \ q}$ בשלב 1 צריכים להיות ראשוניים גדולים כדי להקשות על פירוק לגורמים ואקראיים כדי להקשות על ניחושם. האסטרטגיה המומלצת היא להגריל מספר אקראי אי־זוגי באורך הרצוי באמצעות מחולל פסאודו-אקראי ובדיקת ראשוניותו באמצעות אלגוריתם לבדיקת ראשוניות. אפשר להסתפק באלגוריתם הסתברותי כגון מילר־רבין אם הפרמטרים נבחרו כראוי. משפט המספרים הראשוניים מבטיח שתוך מספר קטן יחסית של הגרלות (בערך כמספר הספרות של המספר), נתקלים בראשוני.
• ${\displaystyle n}$ נקרא מודולוס. החישובים מתבצעים בחוג ${\displaystyle \ \mathbb {Z} _{n}}$ שבו מחושבת השארית של כל פעולה אריתמטית במספר n (ראו חשבון מודולרי). ${\displaystyle n}$ משמש כמפתח פומבי ונדרש להצפנה ופענוח.
• ${\displaystyle e}$ הוא מפתח פומבי המשמש להצפנה ויכול להיות כל שלם טבעי הנמוך מ־${\displaystyle n}$ ובלבד שיהיה זר ל־${\displaystyle \ \phi (n)}$ כלומר שאין לו מחלק משותף עם ${\displaystyle \phi (n)}$ מלבד 1. מסמנים זאת: ${\displaystyle {\mbox{gcd}}(\phi (n),e)=1}$ (הפונקציה gcd מציינת מחלק משותף מרבי). זאת כדי להבטיח כי ההצפנה תהיה תמורה ייחודית (כלומר עבור כל מסר מוצפן ${\displaystyle \ c}$ יהיה מסר מפוענח יחיד ${\displaystyle \ m}$ המתאים לו). רצוי לבחור ${\displaystyle \ e}$ קטן ככל האפשר כדי להקל על תהליך ההצפנה.
• ${\displaystyle d}$ הוא מפתח פרטי המשמש לפענוח וצריך להישמר בסוד. ${\displaystyle d}$ הוא הופכי כפלי מודולרי של ${\displaystyle e}$ (מודולו ${\displaystyle \phi (n)}$) וניתן לסמנו: ${\displaystyle e^{-1}}$. להכנת ${\displaystyle \ d}$ אפשר להיעזר באלגוריתם אוקלידס המורחב (להלן)
• הראשוניים ${\displaystyle p}$ ו־${\displaystyle q}$ לא נחוצים לתהליך ההצפנה והפענוח על כן רצוי להשמידם.

פרמטרים מתקדמים

• בתקן PKCS (גרסה 2), שונה מעט תהליך הכנת המפתחות. במקום לחשב את ${\displaystyle \ \phi (n)=(p-1)(q-1)}$ מחשבים את ${\displaystyle \ \lambda (n)={\mbox{LCM}}(q-1,p-1)}$, שהוא האקספוננט של חבורת אוילר ${\displaystyle \ U_{n}}$ (הפונקציה ${\displaystyle \ {\mbox{LCM}}}$ היא הכפולה המשותפת המינימלית). במקרה זה ${\displaystyle \ d}$ צריך לקיים את יחס השקילות ${\displaystyle \ ed\equiv 1\ ({\mbox{mod }}\lambda \left(n\right))}$.
• תקן PKCS תומך בגרסה מתקדמת הנקראת RSA-CRT בה מנצלים את משפט השאריות הסיני כדי לחלק את מפתח הפענוח הסודי לשני מפתחות קטנים. מחשבים את ${\displaystyle \ d_{P}}$ כך שמתקיים ${\displaystyle \ e\cdot d_{P}\equiv 1\ ({\mbox{mod }}(p-1))}$ ו־${\displaystyle \ d_{Q}}$ כאשר ${\displaystyle \ e\cdot d_{Q}\equiv 1\ ({\mbox{mod }}(q-1))}$ ובאופן דומה מחשבים את מקדם CRT שהוא ההופכי הכפלי של ${\displaystyle \ q}$ מודולו ${\displaystyle \ p}$ המסומן בקיצור ${\displaystyle \ q^{-1}}$. הראשוניים ומקדם ה־CRT נדרשים להצפנה ופענוח ועל כן יש לשומרם בסוד. כמו כן תהליך הפענוח שונה במעט (להלן).
• התקן תומך גם בגרסת "Multi-prime" שבה מספר הגורמים הראשוניים של המודולוס ${\displaystyle \ n}$ גדול משניים. במקרה זה, עבור הראשוניים ${\displaystyle \ r_{1},r_{2},...,r_{u}}$ כאשר ${\displaystyle \ u\geq 3}$ מחשבים את המעריכים ${\displaystyle \ d_{i}}$ כך שמתקיים ${\displaystyle \ e\cdot d_{i}\equiv 1\ ({\mbox{mod }}(r_{i}-1))}$ וכן ${\displaystyle \ t_{i}}$ הנקראים מקדמי ${\displaystyle \ {\mbox{CRT}}}$ כך שמתקיים ${\displaystyle \ R_{i}\cdot t_{i}\equiv 1\ ({\mbox{mod }}r_{i})}$ כאשר ${\displaystyle \ R_{i}}$ הוא כפולה של כל הראשוניים למעט ${\displaystyle \ r_{i}}$. בשיטה זו יש לשמור את כל השלישיות ${\displaystyle \ r_{i},d_{i},t_{i}}$. וכן תהליך הפענוח שונה בהתאם (להלן).

הצפנה ופענוח

אליס משדרת לבוב את מפתחות ההצפנה (${\displaystyle \ e,n}$) ושומרת בסוד את המפתח ${\displaystyle \ d}$. אם בוב מעוניין לשלוח את המסר ${\displaystyle \ m}$ לאליס תחילה עליו להפוך את ${\displaystyle \ m}$ לערך מספרי הנמוך מ־${\displaystyle \ n}$ בדרך מוסכמת כלשהי.

הצפנה

${\displaystyle {\boldsymbol {c=m^{e}{\mbox{ mod }}n}}}$.

להצפנה בוב פשוט מעלה את ${\displaystyle m}$ בחזקת ${\displaystyle e}$ ונוטל את השארית מחילוק ב־${\displaystyle n}$. את הטקסט המוצפן ${\displaystyle c}$ הוא יוכל לשדר לאליס בערוץ פתוח ונגיש לכל.

פענוח

לפענוח אליס משחזרת את המסר ${\displaystyle m}$ מתוך הטקסט המוצפן ${\displaystyle c}$ בעזרת המפתח הסודי ${\displaystyle d}$ בדרך זו:

${\displaystyle \ {\boldsymbol {m=c^{d}{\mbox{ mod }}n}}}$

גרסאות מתקדמות

RSA-CRT

בגרסת CRT המופיעה בתקן, תהליך ההצפנה נותר זהה אך תהליך הפענוח שונה והוא מורכב משלושה שלבים:

1. משתמשים במפתחות הפענוח מתהליך ההכנה לעיל, כדי לחשב את ${\displaystyle \ m_{1}=c^{d_{P}}{\mbox{ mod }}p}$ וכן ${\displaystyle \ m_{2}=c^{d_{Q}}{\mbox{ mod }}q}$.
2. מחשבים את ${\displaystyle \ h=(m_{1}-m_{2})\cdot q^{-1}\ {\mbox{mod }}p}$ כאשר ${\displaystyle \ q^{-1}}$ הוא הופכי כפלי מודולרי של ${\displaystyle \ q}$ מודולו ${\displaystyle \ p}$
3. התוצאה תהיה ${\displaystyle \ m=m_{2}+q\cdot h}$

היות שפעולת העלאה בחזקה מודולרית היא הפעולה הארוכה והאיטית ביותר בכל התהליך. היתרון בשיטה זו כאמור שהיא נעשית מודולו ${\displaystyle p}$ ו־${\displaystyle q}$ כל אחד בנפרד. היות שהם קטנים מהמודולוס בחצי מושג שיפור בפקטור של 2 בקירוב.

RSA Multi-primes

בגרסת Multi-Prime שבה מספר הגורמים גדול משניים, שוב ההצפנה זהה לגרסה הבסיסית ואילו הפענוח מתבצע כדלהלן:

1. תחילה עבור הגורמים ${\displaystyle \ r_{1},r_{2},...,r_{u}}$ כאשר ${\displaystyle \ u\geq 3}$ מחשבים את ${\displaystyle \ m_{i}=c^{d_{i}}{\mbox{ mod }}r_{i}}$ כאשר ${\displaystyle d_{i}}$ הם מפתחות הפענוח שהוכנו קודם (פרמטרים מתקדמים לעיל).
2. מחשבים את ${\displaystyle \ h=(m_{1}-m_{2})\cdot r_{2}^{-1}\ ({\mbox{mod }}r_{1})}$.
3. מחשבים את ${\displaystyle \ m=m_{2}+r_{2}\cdot h}$.
4. מציבים ${\displaystyle \ R=r_{1}}$ ועבור ${\displaystyle \ i=3}$ עד ${\displaystyle \ u}$ מחשבים את:
   1. ${\displaystyle \ R=R\cdot r_{i-1}}$ (כפולת כל הראשוניים למעט ${\displaystyle \ r_{i}}$)
   2. ${\displaystyle \ h=(m_{i}-m)\cdot t_{i}\ ({\mbox{mod }}r_{i})}$
   3. ${\displaystyle \ m=m+R\cdot h}$

יש לזכור שכל הפעולות מבוצעות מודולו ${\displaystyle \ n}$. מכיוון שהפרמטרים ביישום מעשי בדרך כלל גדולים, חישוב חזקות בסדר גודל כזה נעשה בשיטות לחישובים מודולריים מרובי ספרות (ראו חשבון מודולרי).

השיטה הבסיסית המתוארת כאן אינה בטוחה לשימוש לפי מודל ביטחון מחמיר שנקרא עמידות נגד התקפת מוצפן-נבחר לכן במרבית המקרים אין להשתמש בה כך. תחת זאת, התקן מפרט שיטות להכנה בטוחה של המסר להצפנה באופן כזה שההצפנה תהיה בטוחה ולא תדליף מידע שלא במתכוון (ראו ריפוד). בנוסף, כדי למנוע התקפה אקטיבית על המערכת מצד גורם זדוני שיכול לשנות מסרים בדרכם, רצוי להבטיח את שלמות המפתחות ושייכותם לבעליהם. מקובל לרשום את המפתח הציבורי אצל צד שלישי מהימן כמו רשות אישורים (ראו מפתח פומבי).

בסיס מתמטי

ערך מורחב – בעיית RSA

ביטחון שיטת RSA מתבסס על בעיית RSA כדלקמן; נתון שלם חיובי ${\displaystyle pq}$, מכפלת שני ראשוניים שונים שווים בגודלם בקירוב, נתון שלם חיובי ${\displaystyle e}$ הנמוך מ־${\displaystyle pq}$ המקיים ${\displaystyle \ {\mbox{gcd}}((p-1)(q-1),e)=1}$ (פירושו ש־${\displaystyle e}$ זר ל־${\displaystyle (p-1)(q-1)}$) ונתון שלם ${\displaystyle c}$ כלשהו. מצא את ${\displaystyle m}$ המקיים את המשוואה: ${\displaystyle m^{e}\equiv c\ ({\mbox{mod }}pq)}$. במילים אחרות הבעיה היא מציאת שורש ממעלה ${\displaystyle e}$ של ${\displaystyle c}$ (מודולו ${\displaystyle pq}$).

הרעיון מאחורי אלגוריתם הפענוח של RSA מבוסס על משפט אוילר הקובע: עבור כל ${\displaystyle \ a}$ ו־${\displaystyle n}$ טבעיים הזרים זה לזה (שאין להם מחלק משותף מלבד 1) מתקיים: ${\displaystyle a^{\phi (n)}\equiv 1\ ({\mbox{mod }}n)}$. הפונקציה ${\displaystyle \phi (n)}$ נקראת פונקציית אוילר ומייצגת את מספר הטבעיים הזרים ל־${\displaystyle n}$ וקטנים ממנו. אם מכפילים את שני אגפי השקילות האמורה ב־${\displaystyle a}$ מתקבל: ${\displaystyle a^{\phi (n)+1}\equiv a^{\phi (n)}\cdot a\equiv a\ ({\mbox{mod }}n)}$.

הוכחת נכונות

לפי האלגוריתם מפתח הפענוח ${\displaystyle \ d}$ מקיים את השקילות ${\displaystyle \ ed\equiv 1\ ({\mbox{mod }}\phi )}$,

כלומר ${\displaystyle ed-1}$ הוא כפולה כלשהי של ${\displaystyle \phi }$ שהוא בעצם ${\displaystyle (p-1)(q-1)}$, בניסוח אחר קיים שלם ${\displaystyle \ k}$ המקיים ${\displaystyle \ ed=1+k(p-1)(q-1)}$ לכן ${\displaystyle c^{d}}$ הוא פתרון של המשוואה ${\displaystyle m^{e}\equiv c{\text{ (mod }}pq)}$ כי עבור כל שלם ${\displaystyle c}$ הנמוך מ־${\displaystyle pq}$ מתקיים:

${\displaystyle (c^{d})^{e}\equiv c^{de}{\text{ (mod }}pq)}$, ${\displaystyle \equiv c^{1+k(p-1)(q-1)}{\text{ (mod }}pq)}$, ${\displaystyle \equiv c\cdot (c^{(p-1)(q-1)})^{k}{\text{ (mod }}pq)}$, ${\displaystyle \equiv c\cdot 1^{k}{\text{ (mod }}pq)}$ ${\displaystyle \equiv c{\text{ (mod }}pq)}$

לפי חוקי החזקות, היות שמתקיים ${\displaystyle de=1+k(p-1)(q-1)}$, חוקי החזקות שוב, נובע ממשפט אוילר ‎

והפתרון הוא יחיד כיוון שאם קיים פתרון אחר נניח ${\displaystyle u}$ שגם הוא פתרון של ${\displaystyle c\equiv m^{e}}$ אז:

${\displaystyle u\ \equiv u^{de-k(p-1)(q-1)}{\text{ (mod }}pq)}$, ${\displaystyle \equiv (u^{e})^{d}\cdot (u^{(p-1)(q-1)})^{-k}{\text{ (mod }}pq)}$, ${\displaystyle \equiv (u^{e})^{d}\cdot 1^{-k}{\text{ (mod }}pq)}$, ${\displaystyle \equiv c^{d}{\text{ (mod }}pq)}$

היות ש־${\displaystyle de=1+k(p-1)(q-1)}$, לפי חוקי החזקות לפי משפט אוילר היות ש־${\displaystyle u}$ הוא פתרון של ${\displaystyle m^{e}\equiv c{\text{ (mod }}pq)}$.

דוגמה במספרים קטנים

נניח שאליס בוחרת את הראשוניים

${\displaystyle p=5581,q=8059}$ ומחשבת את: ${\displaystyle n=5581\cdot 8059=44977279}$

ואת פונקציית אוילר: ${\displaystyle \phi ={\mbox{lcm}}(5580,8058)=7493940}$

וכן בוחרת את ${\displaystyle e=257}$, שימו לב שמתקיים ${\displaystyle \ {\mbox{gcd}}(7493940,257)=1}$ כנדרש.

בעזרת אלגוריתם אוקלידס המורחב מתקבל

${\displaystyle (291593\cdot 257)\equiv 1\ ({\mbox{mod }}7493940)}$

לכן ${\displaystyle d=291593}$ יהיה מפתח הפענוח המתאים. אליס שולחת את

${\displaystyle \ 44977279}$ ואת ${\displaystyle \ 257}$ לבוב ושומרת בסוד את ${\displaystyle 291593}$.

אם בוב מעוניין להצפין את המסר ${\displaystyle \ m=123456}$ עבור אליס הוא מחשב את:

${\displaystyle c=123456^{257}{\mbox{ mod }}44977279=10526715}$

ושולח את ${\displaystyle \ c}$ לאליס.

כשאליס מקבלת את ${\displaystyle \ c}$ היא משחזרת את ${\displaystyle \ m}$ בעזרת המפתח הסודי:

${\displaystyle m=10526715^{291593}{\mbox{ mod }}44977279=123456}$.

בגרסת CRT מחשבים תחילה את מפתחות הפענוח ${\displaystyle d_{P}=1433}$ כי מתקיים ${\displaystyle 1433\cdot 257\equiv 1\ ({\mbox{mod }}5580)}$ באופן דומה מוצאים את ${\displaystyle d_{Q}=1505}$.

ואז לפענוח מחשבים את ${\displaystyle m_{1}=10526715^{1433}{\mbox{ mod }}5581=674}$ וכן ${\displaystyle m_{2}=10526715^{1505}{\mbox{ mod }}8059=2571}$

מחשבים את ההופכי הכפלי של ${\displaystyle q}$ מודולו ${\displaystyle p}$ שהוא ${\displaystyle q^{-1}=1268}$ ואז ${\displaystyle h=3684\cdot 1268\ ({\mbox{mod }}5581)=15}$. שימו לב שהיות ש־${\displaystyle m_{1}-m_{2}=-1897}$ הוא מספר שלילי לכן לפי הכלל בחשבון מודולרי (מודולו ${\displaystyle p}$ במקרה זה) הוא שקול למעשה ל־${\displaystyle p-1897=3684}$.

מה שנותר הוא לחשב את ${\displaystyle m=15\cdot 8059+2571}$.

הדוגמה היא להמחשה בלבד, בפועל חובה על הראשוניים ${\displaystyle \ p}$ ו־${\displaystyle \ q}$ להיות הרבה יותר גדולים מהדוגמה המובאת כאן. זאת כדי למנוע ניסיון לתקוף את האלגוריתם על ידי פירוק ${\displaystyle n}$ לגורמים באמצעות אלגוריתם פירוק לגורמים ידוע (ראו פירוק לגורמים) ואז לחשב את מפתח הפענוח ${\displaystyle d}$ באותה דרך שבה מחשב אותו המקבל.

חתימה דיגיטלית

אלגוריתם RSA יכול לשמש גם כחתימה דיגיטלית. כיוון שפונקציית ההצפנה היא התאמה על המפתחות יכולים להחליף תפקידים והחתימה מתבצעת על ידי היפוך סדר ההצפנה והפענוח לעיל. כדי לחתום על המסר אליס מצפינה אותו באמצעות המפתח הסודי שלה ושולחת את התוצאה לבוב, כדי לאמת את החתימה בוב מפענח את המסר באמצעות המפתח הפומבי (של אליס). אולם אין לחתום על מסמך בשיטת RSA בצורה ישירה אלא יש צורך תחילה לקודד את המסר באמצעות פונקציית יתירות כלשהי או פונקציית גיבוב לפני החתימה ואת החתימה לבצע על תוצאת הפונקציה במקום על המסר עצמו כדלהלן:

אם אליס מעוניינת לשלוח את המסר ${\displaystyle m}$ כשהוא חתום על ידה לבוב, היא מבצעת:

${\displaystyle \ {\bar {m}}=R(m)}$

${\displaystyle \ s={\bar {m}}^{d}{\mbox{ mod }}n}$ (בדיוק כמו בתהליך הפענוח לעיל).

כאשר ${\displaystyle \ R}$ היא פונקציית היתירות האמורה והחתימה היא ${\displaystyle \ s}$. שימו לב אף על פי שהמטרה בחתימה הדיגיטלית אינה סודיות, כיוון שאליס בעצם הצפינה את המסר היא לא צריכה לשלוח אותו כיוון שבוב מסוגל לשחזרו מתוך החתימה. על כן השיטה המתוארת אפשרית רק כשהמסר קצר (קטן מהמודולוס), כדי לחתום על מסר גדול יותר, נוקטים בשיטה אחרת, תחילה משתמשים בפונקציית גיבוב על המסר ואת החתימה מבצעים על תוצאת פונקציית הגיבוב במקום על המסר עצמו. במקרה זה אליס תצטרך לשלוח גם את המסר עצמו בנפרד.

לאימות החתימה, בוב מחשב את:

${\displaystyle \ {\bar {m}}=s^{e}{\mbox{ mod }}n}$ (בדיוק כמו תהליך ההצפנה לעיל)

${\displaystyle m=R^{-1}({\bar {m}})}$

בוב משיג עותק אותנטי של מפתח האימות של אליס (המקביל למפתח ההצפנה ${\displaystyle \ e}$) באמצעותו מפענח את ${\displaystyle \ {\bar {m}}}$ ובהפעלת הפונקציה ההופכית ${\displaystyle \ R^{-1}}$ משחזר את המסר המקורי. בוב יכול להיות משוכנע כי רק אליס שהיא בעלת המפתח הפרטי המתאים, יכולה הייתה להיות המקור למסר ובמיוחד שלא שונה על ידי גורם כלשהו במהלך המשלוח.

פונקציית היתירות הכרחית כיוון שללא השימוש בה יהיה קל למצוא מסר אחר שעבורו החתימה של אליס תהיה תקפה ללא ידיעת המפתח הפרטי שלה. זאת בשל הכיפליות של RSA. כדי לראות מדוע נניח כי ${\displaystyle R(m)=m}$ (פונקציית הזהות), אם אליס חתמה על שני מסמכים שונים ${\displaystyle \ m_{1}}$ ו־${\displaystyle \ m_{2}}$ אזי כפולה של החתימות: ${\displaystyle \ s_{1}=m_{1}^{d}{\mbox{ mod }}n}$ ו־${\displaystyle \ s_{2}=m_{2}^{d}{\mbox{ mod }}n}$ על המסרים הנ"ל תהיה חתימה תקפה עבור המסר ${\displaystyle \ m=m_{1}m_{2}}$. פונקציית היתירות מבטלת את האסוציאטיביות של החתימות ועל כן מונעת בעיה זו.

גרסאות מתקדמות

החסרון העיקרי בגרסה הבסיסית הוא בגודל מפתח הפענוח שחייב להיות מטעמי ביטחון קרוב לגודלו של ${\displaystyle n}$. היות שאלגוריתם RSA מערב העלאה בחזקה מודולרית, זמן ההצפנה והפענוח תלויים ישירות במספר סיביות המפתחות. מאז המצאת RSA נעשו מספר ניסיונות לצימצום גודל המפתחות ולשפר בכך את יעילות האלגוריתם. הדרך הפופולרית ביותר היא ניצול משפט השאריות הסיני (CRT). הרעיון הוא לפצל את מפתח הפענוח למספר מפתחות קטנים, חישוב העלאה בחזקה עם כל אחד מהם בנפרד ואז שילוב התוצאות בעזרת אלגוריתם CRT מתוך מערכת השקילויות שנוצרת. חישוב CRT זניח יחסית לפעולת העלאה בחזקה מודולרית, על כן שיטה זו משפרת משמעותית את תהליך הפענוח. משפט השאריות הסיני מאפשר פענוח מהיר יותר במיוחד בפלטפורמה מרובת מעבדים, בה ניתן לחשב העלאה בחזקה מודולרית באופן מקבילי.

RSA-CRT^[2]‎

ב־1982 פותחה גרסת RSA-CRT בה תהליך הכנת המפתחות והפענוח דורשים מספר התאמות: מחשבים שני מפתחות פענוח ${\displaystyle \ d_{p}}$ ו־${\displaystyle \ d_{q}}$ באופן שמתקיים ${\displaystyle \ e\cdot d_{p}\equiv 1\ ({\mbox{mod }}(p-1))}$ וכן ${\displaystyle \ e\cdot d_{q}\equiv 1\ ({\mbox{mod }}(q-1))}$. לפענוח תחילה מחשבים את ${\displaystyle \ m_{1}=c^{d_{p}}{\mbox{ mod }}p}$ ואת ${\displaystyle \ m_{2}=c^{d_{q}}{\mbox{ mod }}q}$. נעזרים באלגוריתם של הרווי גארנר לחישוב CRT, כדי לחלץ את ${\displaystyle \ m}$ מתוך מערכת השקילויות כך: ${\displaystyle \ h=(m_{1}-m_{2})\cdot q^{-1}{\mbox{ mod }}p}$ (כאשר ${\displaystyle \ q^{-1}}$ הוא הופכי כפלי של ${\displaystyle \ q}$ מודולו ${\displaystyle \ p}$). המסר ${\displaystyle \ m}$ יהיה ${\displaystyle \ m_{2}+q\cdot h}$. כיוון שהמפתחות ${\displaystyle \ d_{p}}$ ו־${\displaystyle \ d_{q}}$ קטנים בחצי מהמודולוס זמן הפענוח מתקצר בפקטור של 2 כמעט, זאת מבלי לאבד מביטחון האלגוריתם.

Batch RSA^[3]‎

גרסת RSA של עמוס פיאט שבה, אם המפתח הפומבי קטן מאוד, ניתן לפענח מספר מסרים שהוצפנו תחת אותו מודולוס בבת אחת. רעיון זה שימושי במערכות דוגמת שרת SSL המבצע פעולות Handshake בתדירות גבוהה. במקרה כזה ניתן לשנות את ארכיטקטורת השרת כך שימתין לקבלת מספר בקשות פענוח ואז יפענח את כל המסרים במחיר של פעולת פענוח אחת, בתנאי שהמודולוס זהה ומפתחות ההצפנה קטנים (ושונים). שיטה זו משפרת את יעילות אלגוריתם RSA בפקטור של כמעט 3.5 אם מבצעים שמונה פענוחים בבת אחת. כדי להסביר כיצד זה פועל, ידוע שבעיית RSA היא מציאת שורש ממעלה כלשהי מודולו שלם פריק ${\displaystyle \ N}$. כלומר:

${\displaystyle \ M^{d}\ ({\mbox{mod }}N)=M^{1/e}\ ({\mbox{mod }}N)}$.

בתהליכי הפענוח והכנת החתימה המתוארים לעיל, יש צורך להעלות את ${\displaystyle \ M}$ בחזקת ${\displaystyle \ d}$ כלומר לחשב את ${\displaystyle \ M^{1/e}}$. אם למשל ${\displaystyle \ e_{1}=3,e_{2}=5}$, ונתונים ${\displaystyle \ M_{1},M_{2}}$ שעבורם צריך לחשב את ${\displaystyle \ m_{1}^{1/3}}$ ואת ${\displaystyle \ M_{2}^{1/5}}$, אפשר לחשב תחילה את:

${\displaystyle \ M=M_{1}^{5}\cdot M_{2}^{3}\ ({\mbox{mod }}N)}$ ואת,

${\displaystyle \ I=M^{1/15}\ ({\mbox{mod }}N)}$.

ואז לפתור את המשוואות הנ"ל כדלהלן:

${\displaystyle \ {\frac {I^{6}}{M_{1}^{2}\cdot M_{2}}}=M_{2}^{1/5}\ ({\mbox{mod }}N)}$,

${\displaystyle \ {\frac {I}{M_{2}^{1/5}}}=M_{1}^{1/3}\ ({\mbox{mod }}N)}$.

יוצא שרק בחישוב ${\displaystyle \ I=M^{1/15}}$ נדרשת העלאה בחזקה מודולרית מלאה, בנוסף למספר קבוע קטן של פעולות כפל וחילוק מודולריים. החסכון הוא ששתי העלאות בחזקה מודולו ${\displaystyle \ N}$ בוצעו כמעט במחיר של העלאה בחזקה מודולרית אחת. הטריק המתואר מסתמך על העובדה שהמעריכים זרים זה לזה. אפשר להוסיף שיפורים לשיטה זו כמו CRT האמור. החסרון העיקרי הוא בצורך במפתחות הצפנה קטנים מאוד. כאשר מפתח הצפנה גדול, Batch RSA לא תהיה יעילה בשל התקורה הרבה הנוספת.

Multi-prime RSA

גרסה זו מבוססת על שינוי מבנה המודולוס. מיישמים את RSA עם מודולוס במבנה ${\displaystyle \ n=pqr}$ או ${\displaystyle \ n=r_{1}\cdot r_{2}\cdots r_{u}}$ כאשר ${\displaystyle \ u\geq 3}$. מכינים מפתחות פענוח מתאימים כמספר הגורמים, מפענחים עם כל מפתח במפרד ואז מחשבים את מערכת הקונגרואנציות באמצעות אלגוריתם CRT. במקרה של שלושה גורמים, אם המודולוס בגודל 2048 סיביות, כל גורם ראשוני יהיה בערך בגודל 683 סיביות. חישוב חזקה מודולרית בסדר גודל כזה מהיר במידה ניכרת מאשר חישוב החזקה עם המודלוס עצמו. משיקולי ביטחון במקרה שהמודולוס בגודל 1024 סיביות מספר הגורמים המקסימלי יכול להיות 3. RSA multi-prime מהירה יותר מהגרסה הבסיסית בפקטור של 2 בקירוב. תקן PKCS #1 תומך בגרסה זו.

Multi-power RSA

בגרסה זו המודולוס הוא מהצורה: ${\displaystyle \ N=p^{b-1}q}$ כאשר ${\displaystyle \ p}$ ו־${\displaystyle \ q}$ הם בגודל ${\displaystyle \ n/b}$ סיביות (n הוא מספר סיביות המודולוס). במקרה של 1024 סיביות משיקולי ביטחון, לכל היותר ${\displaystyle \ b=3}$. בפענוח משתמשים בשיטת למת הנזל (Hensel lifting) שהיא יעילה יותר מהעלאה בחזקה מודולרית רגילה. בשיפורים קלים multi-power יעילה יותר מהשיטה הבסיסית בפקטור של 2.3 לפחות.

Rebalanced RSA

הרעיון בשיטה זו הוא לפתור את חוסר האיזון הקיים בגרסה הבסיסית של RSA בין גודל מפתח ההצפנה לבין גודל מפתח הפענוח. משיקולי יעילות מפתח ההצפנה בדרך כלל קטן משמעותית. עובדה שלא תמיד רצויה היות שעלול להיווצר עומס יתר בצד המפענח לעומת הצד המצפין. במיוחד הדבר חשוב במכשיר נייד שאמור לייצר חתימת RSA שלאחר מכן תאומת על ידי שרת מהיר. כאן דווקא תהליך יצירת החתימה (המקביל לפענוח) צריך להיות קל יותר כיוון שנעשה בסביבה מוגבלת במשאבים. גרסת Rebalanced RSA דומה ל־RSA-CRT המתוארת לעיל, מלבד זאת שבגרסה זו מקזזים מגודל מפתח הפענוח על חשבון מפתח ההצפנה. השוני הוא בעיקר באלגוריתם הכנת המפתחות. אם השיטה מיושמת נכון ניתן להגיע למפתחות פענוח בסדר גודל של 160 סיביות כל אחד (במקרה של מודולוס בגודל 1024 סיביות). התקורה הנוספת מתהליך הכנת המפתחות וכן חישוב CRT בשלב הסופי של הפענוח נמוכה ביותר. חסרונה של השיטה הוא בעיקר בעובדה שהמפתח הפומבי גדול יותר, עקב כך לא בכל המערכות ניתן לישמה. יש מערכות המגבילות את גודל מפתח ההצפנה משיקולי יעילות. שיטה זו יעילה יותר מהגרסה הבסיסית של RSA בפקטור של 3 לפחות.

Unbalanced RSA

הצעה של עדי שמיר שבה הגורמים הראשוניים אינם שווים בגודלם (מכאן השם). הרעיון הוא שכדי להקשות על שבירת RSA בדרך של פירוק לגורמים רצוי שהמודולוס יהיה גדול ככל האפשר, אולם זה פוגע ביעילות השיטה במיוחד בסביבה מוגבלת במשאבים. אולם אם ${\displaystyle \ p}$ קטן, נניח 1000 סיביות ו־${\displaystyle \ q}$ גדול פי חמישה, אזי משיגים שיפור בביטחון השיטה ועדיין תהליכי ההצפנה והפענוח נותרים באותה רמת סיבוכיות (בתנאי שהמסר קטן מ־${\displaystyle \ p}$). זאת כיוון שיעילות אלגוריתמים המנצלים קיומם של גורמים קטנים אינה גבוהה והאלגוריתמים הכלליים פחות יעילים כאשר המודולוס גדול. בשיטה זו ההצפנה זהה, כל עוד המעריך ${\displaystyle \ e}$ גדול מספיק כדי ש־${\displaystyle \ m^{e}}$ מספיק גדול. לפענוח מנצלים את CRT כדי לחשב את: ${\displaystyle \ c^{d}\ {\mbox{mod }}n}$ כך: תחילה מצמצמים ${\displaystyle \ d'\equiv d\ {\mbox{mod }}\phi (p)}$ ואת ${\displaystyle \ r\equiv c\ {\mbox{mod }}p}$ ואז מחשבים את ${\displaystyle \ m=r^{d'}\ {\mbox{mod }}p}$. אך יש להיזהר מפני התקפת מוצפן־נבחר שבה התוקף מצליח לחלץ מידע מסוים לגבי סיביות המפתח, כאשר מנסים לפענח את ${\displaystyle \ m>p}$ התוצאה תהיה ${\displaystyle \ {\tilde {m}}\neq m}$ במקרה זה מתקבלת הודעת שגיאה מהמערכת. באמצעות חישוב CRT וחיפוש בינארי ניתן למקד את החיפוש עד כדי חשיפת המפתח כולו במספר קטן של ניסיונות.

סוגיית ביטחון גרסאות אילו היא שאלה פתוחה. לא ברור לגמרי האם טכניקות אילו מחלישות או מחזקות את ביטחון אלגוריתם RSA. אם כי לא ידוע על דרכים יעילות לשבירת האלגוריתם בשל שינויים אילו. ראו המאמר של דן בונה וחובב שחם Fast Variants of RSA^[4] שפורסם במגזין Cryptobytes של RSA, קיץ 2002.

ריפוד

ערך מורחב – ריפוד אופטימלי להצפנה אסימטרית

הצפנת RSA מכונה דטרמיניסטית משום שהאלגוריתם אינו מערב שימוש במספרים אקראיים בניגוד לשיטות הצפנה הסתברותיות (כמו אל־גמאל). משמעות הדבר היא שבהצפנת אותו מסר פעמים נוספות (עם מפתח הצפנה זהה) תתקבל תמיד תוצאה זהה. הצפנה דטרמיניסטית פגיעה מעצם טבעה להתקפת מוצפן־נבחר, בה מניחים שהתוקף מסוגל לבחור טקסטים אותם הוא מעוניין להצפין ולנתח את תוצאת הצפנתם, אך אין לו גישה למפתח הפענוח עצמו. כתוצאה מכך, ייתכן מצב שהתוקף יוכל לנחש או לחשוף מידע חלקי או מלא אודות הצופן. כמו כן ישנם מקרי קצה שבהם המסר המיועד להצפנה עלול להוות נקודת תורפה כגון אם הוא קטן מאוד או בעל מבנה ייחודי. במקרה כזה הטקסט נקרא "חלש" כי הוא מסכן את ביטחון ההצפנה. למשל:

• כאשר ${\displaystyle m=1}$ או ${\displaystyle m=0}$ או ${\displaystyle m=n-1}$ תוצאת ההצפנה תהיה תמיד ${\displaystyle m}$ עצמו.
• כאשר מצפינים עם מעריך קטן כגון ${\displaystyle e=3}$ ערכים קטנים של ${\displaystyle m}$ עלולים להניב תוצאות קטנות הנמוכות מהמודולוס מה שמאפשר חישוב שורש ממעלה שלישית ללא תלות במודולוס.

סכימה של אלגוריתם OAEP של בלייר ורוגווי לריפוד בטוח של מסר המיועד להצפנה בשיטת RSA. האלגוריתם מקבל כקלט את: 1) המסר 2) גרעין התחלתי אקראי (בטוח) לצורך פונקציית המיסוך 3) ערך אופציונלי ${\displaystyle L}$ המשמש כקלט לפונקציית הגיבוב שהפלט שלה משורשר לגוש המידע (ערך ברירת המחדל של ${\displaystyle L}$ הוא מחרוזת אפסים). הסימן ${\displaystyle \oplus }$ מייצג XOR והפונקציה MGF היא קיצור של Mask Generation Function והיא בעיקרון פלט חלקי של פונקציית גיבוב כמו SHA-2. השיטה מפורטת בתקן PKCS#1 v2.2.

• כשהמסר קטן ניתן לתקוף את ההצפנה בהתקפת מוצפן־נבחר, שבה התוקף מצפין מראש את כל האפשרויות של ${\displaystyle m}$ ואז בחיפוש קל ימצא את ${\displaystyle c}$ המתאים ובכך יפענח את הטקסט המוצפן מבלי לתקוף את השיטה עצמה.

כדי להימנע ממסר חלש וכדי לסכל התקפת טקסט מוצפן נבחר שמנצלת חולשה זו, מקובל לרפד את המסר באמצעות אלגוריתם ריפוד מוסכם לפני ההצפנה. שיטת הריפוד עצמה לא חייבת להיות סודית. אפשר לשרשר מחרוזת אקראית למסר לפני ההצפנה כך שמבנהו המקורי מיטשטש ובזמן הפענוח פשוט מסירים את המחרוזת האקראית. תקן PKCS #1 יישם שיטת ריפוד פשוטה כזו. לפני ההצפנה המסר רופד באפסים ובמספר אקראי באורך מוגדר כלשהו. ב־1998 הראה דניאל בלייכבכר ממעבדות בל ששיטת ריפוד כזו אינה בטוחה כלל ואפשר לפרוץ אותה בקלות. ב־1995 ניסחו מיהיר בלייר ופיליפ רוגווי את רעיון מודל אורקל אקראי^[5] והראו שבאמצעותו אפשר ליישם כל שיטת הצפנה אסימטרית (דטרמיניסטית) באופן שתהיה בעלת ביטחון סמנטי. על בסיס רעיון זה פותח אלגוריתם OAEP המשתמש במחולל מספרים אקראיים בטוח ופונקציית גיבוב קריפטוגרפית בשילוב עם RSA להצפנה בטוחה. ב־1998 תקן הצפנת מפתח־פומבי PKCS #1 תוקן ואלגוריתם OAEP שולב בתקן כשיטת הריפוד התקנית להצפנת מפתח פומבי הנקראת RSA-OAEP (ראו תרשים).

אלגוריתמים

כדי ליישם את RSA במחשב אין די בדרך הרגילה באמצעות יחידת החישוב במעבד, כיוון שאורך מקסימלי של מספר שניתן לעיבוד בדרך קונבנציונלית אינו עולה על גודלו של האוגר הגדול ביותר. ככל שהמחשבים השתפרו, הצורך באריתמטיקה מודולרית במספרים גדולים בהרבה רק הלך וגדל. משום כך הפתרון הוא אריתמטיקה מרובת ספרות (Multi-precision), כלומר חישוב ספרה אחר ספרה בנפרד כאשר כל ספרה תופסת קרוב לאוגר שלם. בדרך זו החישוב יותר איטי, אך אורך המספרים אינו מוגבל (בגבולות הזיכרון הזמין במחשב). קיימות ספריות לחישובים אריתמטיים מרובי ספרות לשפות התכנות הנפוצות כמו FreeLIP לשפת C של ארג'ן לנסטרה, שסייעה באתגר הראשון כנגד RSA, פירוק RSA-129 ב־1994 או המחלקה BigInteger של Java.

מרכיב חשוב בהכנת RSA הוא יצירת מפתח הפענוח ${\displaystyle \ d}$ שנקרא הופכי כפלי מודולרי של ${\displaystyle \ e}$ (מודולו ${\displaystyle \ n}$). כדי למצוא מספר כזה צריך לפתור את משוואת אוקלידס ${\displaystyle \ de+k\phi (n)=1}$ עבור שלם ${\displaystyle \ 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 או "העלאה בחזקה משמאל לימין". הרעיון הוא שאפשר לחשב את ${\displaystyle \ a^{k}\ {\mbox{mod}}\ n}$ באמצעות סדרת הריבועים ${\displaystyle \ a,a^{2},a^{4},a^{8},...}$ עד ${\displaystyle \ a^{k}}$, אפשר להכין סדרה כזו באופן רקורסיבי על ידי העלאות חוזרות בריבוע: ${\displaystyle a_{i}=a_{i-1}^{2}{\text{ mod }}n}$. לפי חוקי האריתמטיקה מודולו ${\displaystyle n}$ אפשר לבצע את הצמצום המודולרי לאחר כל העלאה בריבוע במקום לבצע את הצמצום בסוף ובכך להימנע מהתנפחות התוצאה. לפי חוקי החזקות אפשר לקבל את ${\displaystyle a^{k}}$ כמכפלה של ערכים מתוך הסדרה האמורה, אותם אפשר לקבל על ידי הייצוג הבינארי של המעריך, דהיינו כאשר הסיבית הנוכחית היא אחד יש לכלול את האיבר המתאים במכפלה. הטבלה הבאה מדגימה את ${\displaystyle 245^{3125}{\mbox{ mod }}10237}$. הפרמטר ${\displaystyle k}$ בטבלה מכיל את הייצוג הבינארי של המעריך: ${\displaystyle \{1,1,0,0,0,0,1,1,0,1,0,1\}_{2}}$ כאשר הסיבית הימנית היא הסיבית הכי פחות משמעותית והסיבית השמאלית היא הסיבית המשמעותית ביותר. התוצאה תהיה מכפלת ערכי ${\displaystyle a}$ בעמודות בהן ${\displaystyle k_{i}=1}$ כלומר

${\displaystyle 245^{3125}\equiv (a_{1}\cdot a_{3}\cdot a_{5}\cdot a_{6}\cdot a_{11}\cdot a_{12}){\mbox{ mod }}10237\equiv (245\cdot 6579\cdot 8608\cdot 2258\cdot 9942\cdot 5129){\text{ mod }}10237\equiv 9737}$

${\displaystyle i}$	1	2	3	4	5	6	7	8	9	10	11	12
${\displaystyle {\boldsymbol {k}}}$	1	0	1	0	1	1	0	0	0	0	1	1
${\displaystyle {\boldsymbol {a}}}$	245	8840	6579	1205	8608	2258	538	2808	2374	5526	9942	5129
${\displaystyle {\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;
}

${\displaystyle \ k}$ המייצג את ${\displaystyle \ t}$ סיביות המעריך ${\displaystyle \ k_{1},k_{2},...,k_{t}}$. בלולאה הראשית סורקים את סיביות ${\displaystyle \ k}$ מימין לשמאל (מהספרה הכי פחות משמעותית לספרה הכי משמעותית), מעלים את ${\displaystyle \ a}$ בריבוע בכל סבב וכל פעם שהסיבית הנוכחית היא 1 בנוסף מכפילים ב־${\displaystyle \ b}$. התוצאה הסופית נשמרת ב־${\displaystyle \ b}$.

החלק הקשה באלגוריתם הוא הצמצום המודולרי. בשיטה הנאיבית מחלקים חילוק ארוך ב־${\displaystyle n}$ ונוטלים את השארית. השימוש בחילוק גוזל זמן עיבור ולכן במספרים גדולים מאוד אינו מומלץ אם רוצים להגיע לביצועים אופטימליים. קיימות שיטות יעילות יותר לצמצום מודולרי כמו שיטת "חלון הזזה" שיטת Barrett ושיטת מונטגומרי. האחרונה נחשבת ליעילה ונפוצה במימושים מעשיים. לשיפור נוסף בביצועים יש המיישמים את פעולות הכפל במספרים הגדולים (מגודל מינימלי שנקבע לפי המערכת) בשיטת קרצובה או טום־קוק בסגנון הפרד ומשול.

התקפות

התקפת ערוץ צדדי

ערך מורחב – התקפת ערוץ צדדי

Timing Attack היא התקפת ערוץ צדדי שעושה שימוש בעובדה שמהירות ההצפנה תלויה בקלט. אם לתוקף יש גישה למערכת (כמו כרטיס חכם או מעגל משולב במכשיר) שבו מתבצעים ההצפנה והפענוח, אך אין לו גישה למפתח הפענוח עצמו המוטמע במערכת. עדיין ביכולתו לחלץ את המפתח באמצעות מדידת הפרשי הזמן בעת פענוח מספר מסוים של טקסטים מוצפנים. יתרה מזו, אם מיישמים אחת מהגרסאות הממוטבות של RSA שעושה שימוש בגורמים הראשוניים, הדבר עלול להוביל לפרצה מסוימת כיוון שניתן למדוד את המידע שדולף מהמערכת בזמן חישוב מערכת הקונגרואנציות של CRT בגלל התלות בסיביות של המספרים הראשוניים. כמו כן אם ארעה שגיאת חומרה במהלך החישוב וחלק מסיביות הפרמטרים השתבשו עקב כך, יש סכנה שמידע פנימי ידלוף.

ישנן דרכים להתמודד עם זה. למשל להבטיח שתהליך הפענוח יתרחש בזמן קבוע על ידי השהיה מכוונת. אולם בדרך זו יעילות המערכת נפגעת. גישה אחרת הנקראת Blinding מנצלת את תכונת הכפליות של RSA (להלן). במקום לפענח את הטקסט המוצפן ישירות, בוחרים ${\displaystyle \ r}$ אקראי כלשהו ואז מחשבים את: ${\displaystyle \ (cr^{e})^{d}{\mbox{ mod }}n}$ והתוצאה תהיה ${\displaystyle \ mr{\mbox{ mod }}n}$. ניתן להסיר את הערך האקראי מהמסר על ידי הכפלה ב־${\displaystyle \ r^{-1}}$ (ההופכי של ${\displaystyle \ r}$ מודולו ${\displaystyle \ n}$). בצורה זו הפענוח אינו תלוי בטקסט המוצפן המתקבל ועל כן התקפת תזמון תכשל במקרה כזה. כמו כן יש לוודא תמיד שהודעות השגיאה של המערכת לא יסגירו מידע פנימי, על ידי בדיקה תמידית של תקפות ערכים וכן לוודא שהזמן הדרוש לכל פעולה יהיה קבוע ללא תלות בשגיאה או בנקודת הזמן בו ארעה.

התקפת האדם שבתווך

ערך מורחב – התקפת אדם בתווך

הצפנת RSA אינה פותרת את בעיית האימות והבטחת השלמות. במילים אחרות, תוקף אקטיבי המסוגל להשתלט על ערוץ התקשורת שבין אליס ובוב יכול בהתקפת אדם באמצע ליירט את מפתח ההצפנה שאליס שולחת לבוב, להחליפו באחר כך שבוב יצפין את כל המסרים עבור אליס במפתח הלא נכון. בדרך דומה מיירט ומשנה את המסרים שבוב שולח לאליס, מפענח את תוכנם, חוזר ומצפינם במפתח המקורי של אליס ושולחם ליעדם. כאשר בוב ואליס אינם מודעים למתרחש. במילים אחרות, בוב חייב להיות בטוח שהמפתח הפומבי שייך לאליס וכן אליס אינה יכולה לדעת מיהו מקור המסר שקיבלה ללא אמצעים נוספים כדי להבטיח זאת. הבטחת שלמות ואותנטיות מפתחות ההצפנה והמסרים נעשים בפרוטוקולים שונים חלקם נעזרים בצד־שלישי נאמן (כמו רשות אישורים CA) וחתימה דיגיטלית.

ראו גם

• פונקציה חד־כיוונית
• בעיית RSA

קישורים חיצוניים

• המאמר המקורי של ריבסט, שמיר ואדלמן A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, המכון הטכנולוגי של מסצ'וסטס, קיימברידג' מסצ'וסטס, אפריל 1977
• תקן PKCS #1 להצפנת RSA, באתר מעבדות RSA
• נימוקי הוועדה, להענקת פרס טיורינג ל־RSA
• תמי לפידות וד"ר דלית לוי, הסבר תמציתי ובהיר (עברית) על שיטת RSA, הצפנה בכלל, ומקבלי פרס טיורינג
• סדרת מאמרים של מעבדות RSA, המסבירים את עקרונות אלגוריתם RSA, הבסיס המתמטי, היתרונות והתועלת שבשיטה
• נצה מובשוביץ־הדר, הרצאה על מספרים ראשוניים והצפנה, יסודות ה־RSA
• עודד בראש, התקפות על מערכת ההצפנה RSA, באתר פרויקט UnderWarrior
• גרסאות מהירות של RSA, מגזין CryptoBytes (כרך 5) ינואר 2002
• RSA, באתר אנציקלופדיה בריטניקה (באנגלית)
• RSA, באתר MathWorld (באנגלית)

הערות שוליים

1. Cocks' November 1973 internal GCHQ note on his discovery
2. J-J. Quisquater and C. Couvreur. Fast decipherment algorithm for RSA public-key cryptosystem. Electronic Letters, vol 18:905–907, 1982
3. עמוס פיאט, אוניברסיטת תל אביב, אפריל 1996
4. Fast Variants of RSA (survey)
5. M. Bellare and P. Rogaway. "Optimal Asymmetric Encryption" In A. De Santis, ed, Proceedings of Eurocrypt ‘94 vol. 950 of Lecture Notes in Computer Science (LNCS), pp. 92–111. Springer-Verlag,1994.