RSA

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

היסטוריה[עריכת קוד מקור | עריכה]

החיסרון העיקרי באלגוריתמים סימטריים להצפנה הוא שהמפתח הסודי נדרש להצפנה ולפענוח ולכן יש צורך להעבירו לידי המקבל בדרך כלשהי ובכך לסכנו בחשיפה. ב-1976 פרסמו ויטפילד דיפי ומרטין הלמן מאמר מפורסם המתאר את התפיסה של המפתח הפומבי, שבה המקבל מפרסם מפתח הצפנה פומבי בעזרתו מבוצעת ההצפנה עבורו, ואילו הפענוח מתבצע אך ורק באמצעות המפתח הפרטי שברשותו, שמעולם לא נחשף. כשנה לאחר מכן, רונלד ריבסט (Ronald Rivest), עדי שמיר (Adi Shamir) ולאונרד אדלמן (Leonard Adelman) מ-MIT פרסמו לראשונה את RSA (שמו נגזר מראשי תיבות שמותיהם), שיישם לראשונה את המודל של דיפי והלמן באופן מעשי. אלגוריתם RSA זיכה את ממציאיו בפרס טיורינג לשנת 2002.

זכויות יוצרים[עריכת קוד מקור | עריכה]

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

הצפנה ופענוח[עריכת קוד מקור | עריכה]

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

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

פירוט הפרמטרים[עריכת קוד מקור | עריכה]

  • \ p ו-\ q בשלב 1 צריכים להיות אקראיים ראשוניים וגדולים. האסטרטגיה המומלצת היא בחירת מספר אקראי אי-זוגי בגודל הרצוי באמצעות מחולל מספרים אקראיים בטוח ובדיקת ראשוניותו באמצעות אלגוריתם בדיקת ראשוניות. אפשר להסתפק באלגוריתם הסתברותי כגון מילר-רבין במידה והפרמטרים נבחרים בקפידה באופן שיבטיח סיכוי קלוש לטעות. משפט המספרים הראשוניים מבטיח שתוך מספר קטן יחסית של הגרלות (בערך כמספר הספרות של המספר), נתקלים בראשוני.
  • \ n נקרא מודולוס ומהווה את קבוצת השלמים הטבעיים \ \mathbb{Z}_n כאשר פעולות אריתמטיות סגורות תחת \ n, כלומר תוצאת פעולות חיבור וכפל היא השארית מחילוק ב-\ n (ראו חשבון מודולרי). \ n משמש כמפתח פומבי ונדרש להצפנה ופענוח.
  • הפרמטר \ e נקרא מפתח פומבי המשמש להצפנה ויכול להיות כל שלם טבעי הנמוך מ-\ n ובלבד שיהיה זר ל- \ \phi כלומר שאין לו מחלק משותף עם \ \phi מלבד 1. מסמנים זאת: \ \mbox{gcd}(\phi,e)=1 (הפונקציה gcd מציינת מחלק משותף מרבי). זאת כדי להבטיח כי ההצפנה תהיה תמורה ייחודית (כלומר עבור כל \ c יהיה \ m יחיד המתאים לו). רצוי לבחור \ e קטן ככל האפשר כדי להקל על תהליך ההצפנה.
  • הפרמטר \ d נקרא מפתח פרטי המשמש לפענוח וצריך להישמר בסוד. \ d הוא הופכי כפלי מודולרי של \ e (מודולו \ n) וניתן לסמנו: \ e^{-1}. להכנת \ d אפשר להיעזר באלגוריתם אוקלידס המורחב (להלן)
  • הראשוניים \ p ו-\ q בגרסת RSA הבסיסית לא נחוצים לתהליך ההצפנה והפענוח על כן רצוי להשמידם.
  • בתקן PKCS (גרסה 2), שונה מעט תהליך הכנת המפתחות. במקום לחשב את \ \phi=(p-1)(q-1) מחשבים את \ \lambda(n)=\mbox{LCM}(q-1, p-1), שהוא האקספוננט של חבורת אוילר \ U_n (הפונקציה \ \mbox{LCM} היא הכפולה המשותפת המינימלית). במקרה זה \ d צריך לקיים את היחס \ ed \equiv 1 \ (\mbox{mod } \lambda \left(n\right)).
  • תקן PKCS תומך בגרסה מתקדמת הנקראת RSA-CRT בה מנצלים את משפט השאריות הסיני כדי לייעל את תהליך הפענוח. במקרה זה בתהליך ההכנה, עבור הראשוניים \ p ו-\ q מחשבים את \ d_P כך שמתקיים \ e \cdot d_P \equiv 1 \ (\mbox{mod } (p-1)) ו-\ d_Q כאשר \ e \cdot d_Q \equiv 1 \ (\mbox{mod } (q-1)) ובאופן דומה מחשבים את מקדם CRT שהוא ההופכי הכפלי של \ q מודולו \ p המסומן בקיצור \ q^{-1}. אותם יש לשמור בסוד. כמו כן תהליך הפענוח שונה במעט, ראה להלן.
  • התקן תומך גם בגרסת "Multi-prime" שבה מספר הגורמים הראשוניים של המודולוס \ n גדול משניים. במקרה זה, עבור הראשוניים \ r_1,r_2,...,r_u כאשר \ u \ge 3 מחשבים את המעריכים \ d_i כך שמתקיים \ e \cdot d_i \equiv 1 \ (\mbox{mod } (r_i - 1)) וכן \ t_i הנקראים מקדמי \ \mbox{CRT} כך שמתקיים \ R_i \cdot t_i \equiv 1 \ (\mbox{mod } r_i) כאשר \ R_i הוא כפולה של כל הראשוניים למעט \ r_i. בשיטה זו יש כמובן לשמור את כל השלישיות \ r_i,d_i,t_i. וכן תהליך הפענוח שונה בהתאם.

הצפנה[עריכת קוד מקור | עריכה]

אליס משדרת לבוב את מפתחות ההצפנה (\ e, n) ושומרת בסוד את המפתח \ d. אם בוב מעוניין לשלוח את המסר \ m לאליס תחילה עליו להפוך את \ m לערך מספרי הנמוך מ-\ n בדרך מוסכמת כלשהי ואז מחשב את:

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

בוב מעלה את \ m בחזקת \ e ומצמצם מודולו \ n ואת הטקסט המוצפן \ c יוכל לשדר לאליס בערוץ פתוח (שאינו מאובטח).

פענוח[עריכת קוד מקור | עריכה]

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

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

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

  1. תחילה מחשבים את \ m_1 = c^{d_P} \mbox{ mod } p וכן \ m_2 = c^{d_Q} \mbox{ mod } q
  2. מחשבים את \ h = (m_1 - m_2) \cdot q^{-1} \ \mbox{mod } p כאשר \ q^{- 1} הוא הופכי כפלי מודולרי של \ q מודולו \ p
  3. התוצאה תהיה \ m = m_2 + q \cdot h

היות שפעולת העלאה בחזקה מודולרית הינה הפעולה הארוכה והאיטית ביותר בכל התהליך. היתרון בשיטה זו כאמור שהיא נעשית מודולו \ p ו-\ q כל אחד בנפרד. היות שהם קטנים מהמודולוס בחצי מושג שיפור בפקטור של 2 בקירוב. בגרסת Multi-Prime שבה מספר הגורמים גדול משניים, מפענחים את \ c בדרך הבאה:

  1. תחילה עבור הגורמים \ r_1,r_2,...,r_u כאשר \ u \ge 3 מחשבים את \ m_i = c^{d_i}\mbox{ mod } r_i.
  2. מחשבים את \ h = (m_1 - m_2) \cdot r_2^{-1} \ (\mbox{mod }r_1).
  3. מחשבים את \ m = m_2 + r_2 \cdot h.
  4. מציבים \ R = r_1 ועבור \ i=3 עד \ u מחשבים את:
  1. \ R = R \cdot r_{i-1} (כפולת כל הראשוניים למעט \ r_i)
  2. \ h = (m_i - m) \cdot t_i \ (\mbox{mod }r_i)
  3. \ m = m + R \cdot h
יש לזכור שכל הפעולות מבוצעות מודולו \ n.

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

בסיס מתמטי[עריכת קוד מקור | עריכה]

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

בעיית RSAP[עריכת קוד מקור | עריכה]

ביטחון השיטה מתבסס על בעיית RSAP כדלקמן: נתון שלם חיובי \ n=pq, מכפלת שני ראשוניים שונים שווים בגודלם בקירוב, נתון שלם חיובי \ e הנמוך מ-\ n המקיים \ \mbox{gcd}((p-1)(q-1),e)=1 (פירושו ש-\ e זר ל-\ (p-1)(q-1)) ונתון שלם \ c כלשהו. מצא את \ m המקיים את המשוואה: \ m^e \equiv c \ (\mbox{mod }n). במילים אחרות הבעיה היא מציאת שורש ממעלה \ e של \ c (מודולו \ n). המגבלות שהוטלו על הפרמטרים מבטיחים כי לכל \ c קיים אך ורק \ m יחיד המקיים שקילות זו, היות שהפונקציה החד-כיוונית \ f(m)=m^e \ \mbox{mod }n היא תמורה ב-\ \mathbb{Z}_n. הקושי נעוץ בעובדה שתוצאת הפונקציה האמורה אינה לינארית ולמעשה מתנהגת כפונקציה אקראית. חיפוש סדרתי של הפונקציה ההופכית \ f^{-1}(c)\ \mbox{mod }n מחייב במקרה הגרוע בדיקת כל המעריכים האפשריים.

הוכחת נכונות[עריכת קוד מקור | עריכה]

לפי האלגוריתם מפתח הפענוח \ d מקיים את השקילות

\ ed \equiv 1 \ (\mbox{mod } \phi),
כלומר קיים שלם \ k המקיים \ ed=1+k \phi או \ ed=1+k(p-1)(q-1).

לפי משפט פרמה:

\ m^{p-1} \equiv 1 \ (\mbox{mod }p)

אם נעלה את שני אגפי שקילות זו בחזקת \ k(q-1) ונכפיל ב-\ m נקבל:

\ m^{1+k(p-1)(q-1)} \equiv m \ (\mbox{mod }p)

במקרה ש-\ m זר ל-\ p (במקרה ש-\ m אינו זר ל-\ p כגון אם \ m הוא כפולה של \ p, השקילות האחרונה נכונה גם כן, כיוון שאז שני האגפים שקולים ל-0). בכל מקרה מזה נובע כי:

\ m^{ed} \equiv m \ (\mbox{mod }p) ומאותה הטענה,
\ m^{ed} \equiv m \ (\mbox{mod }q)

היות ש-\ p ו-\ q הם ראשוניים שונים, לכן לפי משפט השאריות הסיני (CRT), חישוב מערכת שקילויות זו מניב \ m^{ed} \equiv m \ (\mbox{mod }n). לכן:

\ c^d \equiv (m^e)^d \equiv m^{ed} \equiv m \ (\mbox{mod }n).

דוגמה במספרים קטנים[עריכת קוד מקור | עריכה]

נניח שאליס בוחרת את הראשוניים \ p=5581, q=8059 ומחשבת את: \ n=44977279 ואת פונקציית אוילר: \ \phi=\mbox{lcm}(5580,8058)=7493940 וכן בוחרת את \ e=257 כמפתח פומבי, שים לב שמתקיים \ \mbox{gcd}(7493940,257)=1. בעזרת אלגוריתם אוקלידס המורחב מתקבל \ (291593 \cdot 257) \equiv 1 \ (\mbox{mod } 7493940) לכן \ d=291593 יהיה מפתח הפענוח המתאים. אליס שולחת את \ 44977279 ואת \ 257 לבוב ושומרת בסוד את \ 291593.

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

\ c=123456^{257} \mbox{ mod }44977279=10526715 ושולח את \ c לאליס.

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

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

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

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

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

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

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

חתימה דיגיטלית[עריכת קוד מקור | עריכה]

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

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

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

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

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

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

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

פונקציית היתירות הכרחית כיוון שללא השימוש בה, יהיה קל למצוא מסר אחר שעבורו החתימה של אליס תהיה תקפה מבלי לדעת את המפתח הפרטי שלה. זאת בשל הכיפליות של RSA. כדי לראות מדוע נניח כי \ R(m)= m, אם אליס חתמה על שני מסמכים שונים \ m_1 ו-\ m_2 אזי כפולה של החתימות: \ s_1 = m^d_1 \mbox{ mod }n ו-\ s_2 = m^d_2 \mbox{ mod }n על המסרים הנ"ל תהיה חתימה תקפה עבור המסר \ m = m_1m_2. פונקציית היתירות מבטלת את האסוציאטיביות של החתימות ועל כן מונעת בעיה זו.

גרסאות מתקדמות[עריכת קוד מקור | עריכה]

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

RSA-CRT ‏[1]‎ 
ב-1982 פותחה גרסת RSA-CRT בה תהליך הכנת המפתחות והפענוח דורשים מספר התאמות: מחשבים שני מפתחות פענוח \ d_p ו-\ d_q באופן שמתקיים \ e \cdot d_p \equiv 1 \ (\mbox{mod }(p-1)) וכן \ e \cdot d_q \equiv 1 \ (\mbox{mod }(q-1)). לפענוח תחילה מחשבים את \ m_1=c^{d_p} \mbox{ mod }p ואת \ m_2=c^{d_q} \mbox{ mod }q. נעזרים באלגוריתם של הרווי גארנר לחישוב CRT, כדי לחלץ את \ m מתוך מערכת השקילויות כך: \ h=(m_1-m_2) \cdot q^{-1} \mbox{ mod }p (כאשר \ q^{-1} הוא הופכי כפלי של \ q מודולו \ p). המסר \ m יהיה \ m_2+q \cdot h. כיוון שהמפתחות \ d_p ו-\ d_q קטנים בחצי מהמודולוס זמן הפענוח מתקצר בפקטור של 2 כמעט, זאת מבלי לאבד מביטחון האלגוריתם.
Batch RSA ‏[2]‎ 
גרסת RSA של עמוס פיאט שבה, אם המפתח הפומבי קטן מאוד, ניתן לפענח מספר מסרים שהוצפנו תחת אותו מודולוס בבת אחת. רעיון זה שימושי במערכות דוגמת שרת SSL המבצע פעולות Handshake בתדירות גבוהה. במקרה כזה ניתן לשנות את ארכיטקטורת השרת כך שימתין לקבלת מספר בקשות פענוח ואז יפענח את כל המסרים במחיר של פעולת פענוח אחת, בתנאי כמובן שהמודולוס זהה ומפתחות ההצפנה קטנים (ושונים). שיטה זו משפרת את יעילות אלגוריתם RSA בפקטור של כמעט 3.5 אם מבצעים שמונה פענוחים בבת אחת. כדי להסביר כיצד זה פועל, ידוע שבעיית RSA היא מציאת שורש ממעלה כלשהי מודולו שלם פריק \ N. כלומר:
\ M^d \ (\mbox{mod }N) = M^{1/e} \ (\mbox{mod }N).
בתהליכי הפענוח והכנת החתימה המתוארים לעיל, יש צורך להעלות את \ M בחזקת \ d כלומר לחשב את \ M^{1/e}. אם למשל \ e_1=3, e_2=5, ונתונים \ M_1, M_2 שעבורם צריך לחשב את \ m^{1/3}_1 ואת \ M^{1/5}_2, אפשר לחשב תחילה את:
\ M = M^5_1 \cdot M^3_2 \ (\mbox{mod }N) ואת,
\ I=M^{1/15} \ (\mbox{mod }N).
ואז לפתור את המשוואות הנ"ל כדלהלן:
\ \frac{I^6}{M^2_1 \cdot M_2}=M^{1/5}_2 \ (\mbox{mod }N),
\ \frac{I}{M^{1/5}_2}=M^{1/3}_1 \ (\mbox{mod }N).
יוצא שרק בחישוב \ I=M^{1/15} נדרשת העלאה בחזקה מודולרית מלאה, בנוסף למספר קבוע קטן של פעולות כפל וחילוק מודולריים. החסכון הוא ששני העלאות בחזקה מודולו \ N בוצעו כמעט במחיר של העלאה בחזקה מודולרית אחת. הטריק המתואר מסתמך על העובדה שהמעריכים זרים זה לזה. אפשר להוסיף שיפורים לשיטה זו כמו CRT האמור. החסרון העיקרי הוא בצורך במפתחות הצפנה קטנים מאוד. כאשר מפתח הצפנה גדול, Batch RSA לא תהיה יעילה בשל התקורה הרבה הנוספת.
Multi-prime RSA 
גרסה זו מבוססת על שינוי מבנה המודולוס. מיישמים את RSA עם מודולוס במבנה \ n=pqr או \ n=r_1\cdot r_2\cdots r_u כאשר \ u \ge 3. מכינים מפתחות פענוח מתאימים כמספר הגורמים, מפענחים עם כל מפתח במפרד ואז מחשבים את מערכת הקונגרואנציות באמצעות אלגוריתם CRT. במקרה של שלושה גורמים, אם המודולוס בגודל 2048 סיביות, כל גורם ראשוני יהיה בערך בגודל 683 סיביות. חישוב חזקה מודולרית בסדר גודל כזה מהיר במידה ניכרת מאשר חישוב החזקה עם המודלוס עצמו. משיקולי ביטחון במקרה שהמודולוס בגודל 1024 סיביות מספר הגורמים המקסימלי יכול להיות 3. RSA multi-prime מהירה יותר מהגרסה הבסיסית בפקטור של 2 בקירוב. תקן PKCS #1 תומך בגרסה זו.
Multi-power RSA 
בגרסה זו המודולוס הוא מהצורה: \ N=p^{b-1}q כאשר \ p ו-\ q הם בגודל \ n/b סיביות (n הוא מספר סיביות המודולוס). במקרה של 1024 סיביות משיקולי ביטחון, לכל היותר \ b=3. בפענוח משתמשים בשיטת Hensel lifting שהיא יעילה יותר מהעלאה בחזקה מודולית רגילה. בשיפורים קלים multi-power יעילה יותר מהשיטה הבסיסית בפקטור של 2.3 לפחות.
Rebalanced RSA 
הרעיון בשיטה זו הוא לפתור את חוסר האיזון הקיים בגרסה הבסיסית של RSA בין גודל מפתח ההצפנה לבין גודל מפתח הפענוח. משיקולי יעילות מפתח ההצפנה בדרך כלל קטן משמעותית. עובדה שלא תמיד רצויה היות שעלול להווצר עומס יתר בצד המפענח לעומת הצד המצפין. במיוחד הדבר חשוב במכשיר נייד שאמור לייצר חתימת RSA שלאחר מכן תאומת על ידי שרת מהיר. כאן דווקא תהליך יצירת החתימה (המקביל לפענוח) צריך להיות קל יותר כיוון שנעשה בסביבה מוגבלת במשאבים. גרסת Rebalanced RSA דומה ל-RSA-CRT המתוארת לעיל, מלבד זאת שבגרסה זו מקזזים מגודל מפתח הפענוח על חשבון מפתח ההצפנה. השוני הוא בעיקר באלגוריתם הכנת המפתחות. אם השיטה מיושמת נכון ניתן להגיע למפתחות פענוח בסדר גודל של 160 סיביות כל אחד (במקרה של מודולוס בגודל 1024 סיביות). התקורה הנוספת מתהליך הכנת המפתחות וכן חישוב CRT בשלב הסופי של הפענוח נמוכה ביותר. חסרונה של השיטה הוא בעיקר בעובדה שהמפתח הפומבי גדול יותר, עקב כך לא בכל המערכות ניתן לישמה. יש מערכות המגבילות את גודל מפתח ההצפנה משיקולי יעילות. שיטה זו יעילה יותר מהגרסה הבסיסית של RSA בפקטור של 3 לפחות.
Unbalanced RSA 
הצעה של עדי שמיר שבה הגורמים הראשוניים אינם שווים בגודלם (מכאן השם). הרעיון הוא שכדי להקשות על שבירת RSA בדרך של פירוק לגורמים רצוי שהמודולוס יהיה גדול ככל האפשר, אולם זה פוגע ביעילות השיטה במיוחד בסביבה מוגבלת במשאבים. אולם אם \ p קטן, נניח 1000 סיביות ו-\ q גדול פי חמש, אזי משיגים שיפור בביטחון השיטה ועדיין תהליכי ההצפנה והפענוח נותרים באותה רמת סיבוכיות (בתנאי שהמסר קטן מ-\ p). זאת כיוון שיעילות אלגוריתמים המנצלים קיומם של גורמים קטנים אינה גבוהה והאלגוריתמים הכלליים פחות יעילים כאשר המודולוס גדול. בשיטה זו ההצפנה זהה, כל עוד המעריך \ e גדול מספיק כדי ש-\ m^e מספיק גדול. לפענוח מנצלים את CRT כדי לחשב את: \ c^d\ \mbox{mod }n כך: תחילה מצמצמים \ d'\equiv d\ \mbox{mod }\phi(p) ואת \ r\equiv c\ \mbox{mod }p ואז מחשבים את \ m = r^{d'}\ \mbox{mod }p. אך יש להיזהר מפני התקפת מוצפן-נבחר שבה התוקף מצליח לחלץ מידע מסוים לגבי סיביות המפתח, כאשר מנסים לפענח את \ m > p התוצאה תהיה \ \tilde m \ne m במקרה זה מתקבלת הודעת שגיאה מהמערכת. באמצעות חישוב CRT וחיפוש בינארי ניתן למקד את החיפוש עד כדי חשיפת המפתח כולו במספר קטן של ניסיונות.

סוגיית ביטחון גרסאות אילו היא שאלה פתוחה. לא ברור לגמרי האם טכניקות אילו מחלישות או מחזקות את ביטחון אלגוריתם RSA. אם כי לא ידוע על דרכים יעילות לשבירת האלגוריתם בשל שינויים אילו. ראו המאמר של דן בונה וחובב שחם "גרסאות מהירות של RSA" במגזין CryptoBytes של מעבדות RSA.

הקשר לפירוק לגורמים[עריכת קוד מקור | עריכה]

מקובל להניח שבעיית RSAP שקולה לבעיית פירוק לגורמים שנכון לשנת 2013 לא ידוע על דרך יעילה לפתרונה. לפי סברה זו כל דרך לפתרון בעיית RSAP תאפשר גם פתרון בעיית פירוק לגורמים באופן יעיל, אם כי איש לא הוכיח זאת מעולם מבחינה מתמטית. לעומת זאת קיימת הוכחה בכיוון ההפוך, כלומר אם תמצא דרך קלה לפירוק \ n לגורמים, אזי קל לראות שבעיית RSAP ניתנת לפתרון יעיל. כיוון שחישוב הפונקציה החד-כיוונית \ c=m^e \mbox{ mod }n בכיוון ההפוך יהיה קל אם הגורמים הראשונים של \ n ידועים שאז פשוט מחשבים את \ \phi ואת \ d באותה הדרך בה ביצעה זאת אליס.

כמו כן אפשר לראות שאם מפתח הפענוח \ d ידוע, ניתן בעזרתו לפרק לגורמים את המודולוס כדלהלן: היות ש-\ ed \equiv 1 \ (\mbox{mod }n) כלומר \ ed-1 = k \phi. ולפי משפט אוילר \ a^{\phi} \equiv 1 \ (\mbox{mod }n) לכל \ a ב-\ \mathbb{Z}^*_n, לכן גם \ a^{ed-1} \equiv 1 \ (\mbox{mod }n). אם נייצג את \ ed-1 כ-\ 2^st עם \ t אי-זוגי כלשהו, נוכל למצוא \ i < s וכן שלם \ a המקיימים \ a^{2^{i-1}t} \not\equiv \pm 1 \ (\mbox{mod }n) ולעומת זאת \ a^{2^i t} \equiv 1 \ (\mbox{mod }n). לפחות מחצית האלמנטים ב-\ \mathbb{Z}^*_n עונים על דרישה זו, כך שהסיכוי למצוא זוג ערכים \ (a, i) כאלו גבוה. ומכאן הדרך קלה כיוון שבהכרח \ \mbox{gcd}(a^{2^{i-1}t} - 1,n) הנו גורם לא טריויאלי של \ n.

למשל, בדוגמה לעיל \ ed-1 = 2^6 \cdot 567 חשבון פשוט מראה שאם \ a=2, i=4 מתקבל \ 2^{2^4 \cdot 567} שקול ל-\ 1 וכן \ 2^{2^3 \cdot 567} שקול ל-\ 10669 (מודולו \ 12319), אם נחשב את המחלק המשותף המרבי של \ 10668 ו-\ 12319 נקבל \ 127 שזה אחד מהגורמים הראשוניים של \ n.

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

לאחר המצאת RSA חודשו המאמצים למציאת אלגוריתמים יעילים לפירוק לגורמים. ב-1981 פיתח קארל פומרנץ את אלגוריתם הנפה הריבועית אשר נחשב עד ל-1993 לאלגוריתם היעיל ביותר (באופן אסימפטוטי) לפירוק לגורמים. ב-1993 הומצאה נפת שדה מספרים הידועה כיום כאלגוריתם הטוב ביותר בכל הזמנים לפירוק לגורמים של מספרים גדולים מאוד (בשל מורכבותה נפת שדה המספרים יעילה בעיקר מעל מאה ספרות עשרוניות). בנובמבר 2005 הצליח צוות מתמטיקאים לפרק לגורמים בעזרת אלגוריתם נפת שדה המספרים את המודולוס RSA-200 (200 ספרות עשרוניות) מתוך מספרי האתגר של מעבדות RSA. המאמץ נמשך כמעט שלוש שנים, תוך שימוש במספר גדול של מחשבים שעבדו במקביל. בדצמבר 2009 פרסם צוות מחקר ממוסדות אקדמאיים שונים, בראשות תורסטן קליינג'ונג כי הצליחו לפרק לגורמים את המספר RSA-768 (ממספרי האתגר של מעבדות RSA) בתהליך שנמשך כמעט שלוש שנים ונרתמו לצורכו אלפי מעבדים (אותו תהליך על מחשב בודד בעל עוצמת חישוב טובה, היה אורך כ-1500 שנה). האתגר הבא RSA-1024 (כ-300 ספרות עשרוניות) קשה פי כמה אלפים ‏[3]. בעבר הוצע פרס של כ-100,000 דולר למי שיצליח לפרקו.

עדי שמיר וערן טרומר פיתחו חומרה היפותטית (TWINKLE ו-TWIRL) להאצת תהליך הניפוי של אלגוריתם NFS. באמצעותה פירוק לגורמים של מודולוס RSA בגודל 1024 סיביות בר ביצוע בזמן סביר. במאמרם‏[4] נטען שניתן לבנות מערכת ייעודית מעשית לשבירת RSA בסדר גודל של 1024 סיביות בתוך כשנה ובעלות של כעשרה מיליון דולר. לא ידוע על מימוש מעשי של החומרה שהציעו.

בעקבות פרשת סנאודון, ישנם מומחי אבטחה המעריכים‏[5] כי נכון לשנת 2013 ארגונים בינלאומיים בעלי אמצעים כמו NSA מסוגלים לפצח מפתח כזה בעלות של כמיליארד דולר בזמן קצר בהרבה (כמספר שעות).

לפי חוק מור כל שנתיים בערך היכולת הטכנולוגית מכפילה עצמה. אולם קצב המיזעור הולך ודועך. בשנת 2007 צוטט מור כי בתוך עשר שנים לא יתאפשר מיזעור נוסף בהתאם לחוק שהגה. אלא אם כן תהיה פריצת דרך מהפכנית בתחום בתחום המחשבים הקוונטיים אזי תהפוך שיטת RSA ודומותיה ללא בטוחות. בשנת 2001 נעשה באוניברסיטת סטנפורד ניסיון לפרק לגורמים את המספר 15 במחשב קוונטי עם אלגוריתם שור. עם זאת הטכנולוגיה הקיימת כיום עדיין אינה מאפשרת בניית מחשב קוונטי בקנה מידה סביר.

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

פרמטרים[עריכת קוד מקור | עריכה]

משיקולי יעילות, במיוחד כאשר מיישמים את RSA בחומרה כמו כרטיס חכם, רצוי שהמעריך \ e (מפתח ההצפנה או מפתח האימות במקרה של חתימה דיגיטלית) יהיה קטן ככל האפשר. למשל אם \ e=3 או \ e=5 תהליך ההצפנה או האימות יהיה מהיר במיוחד בחומרה, אולם עלול להוות פרצת אבטחה בתנאים מסוימים. על כן מקובל להשתמש במעריך גדול יותר. המעריך \ e=2^{16}+1 נפוץ בישומים מעשיים, יתרונו במשקלו הבינארי הנמוך.

כמו כן חשוב שהמפתח הפרטי \ d (מפתח החתימה במקרה של חתימה דיגיטלית) יהיה גדול ככל האפשר. באוגוסט 1989 פרסם מיכאל ויינר התקפה ‏[6] כנגד RSA עם מפתח פרטי קטן. הוא הראה שאם \ d < n^{1/4} / 3 ניתן לחשב את המפתח הפרטי מתוך \ n ו-\ e באופן יעיל למדי, באמצעות מה שמכונה קירוב שברים משולבים או קירוב רציונלי.

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

מספרים ראשוניים[עריכת קוד מקור | עריכה]

כאמור חשוב שהמספרים הראשוניים ייבחרו באופן אקראי. למשל לא מומלץ להשתמש ברשימת מספרים ראשוניים מפורסמת, כיוון שבדרך זו מועבר מידע ליריב פוטנציאלי. בבחירת מספרים ראשוניים רצוי שיהיו לא רק אקראיים אלא גם קשים לניחוש. אילו הגדרות שונות, כיוון שאקראיות לבדה אינה מבטיחה קושי בניחוש. על כן השיטה המקובלת היא הפעלת מחולל אקראי בטוח ליצירת מספר אי-זוגי אקראי באורך הרצוי ובדיקת ראשוניותו, מכיוון שבדיקת ראשוניות קלה יותר מפירוק לגורמים. כמו כן רצוי ש-\ p ו-\ q יהיו בגודל זהה בקירוב, כלומר שלמודולוס \ n לא יהיו גורמים קטנים כלשהם. זאת כדי לסכל אפשרות שימוש באלגוריתם פירוק שמנצל את קיומם של גורמים קטנים. מצד שני רצוי שההפרש ביניהם לא יהיה קטן מדי. כי אם \ p \approx q, אזי גם \ p \approx \sqrt{n} ואז ניתן למצוא אותם בחיפוש קל, קרוב לשורש.

יש הממליצים להשתמש במספרים ראשוניים חזקים. \ p הוא מספר ראשוני חזק אם הוא מקיים את ההגדרות הבאות:

  • \ p-1 מכיל גורם ראשוני גדול \ r.
  • \ p+1 מכיל גורם ראשוני גדול כלשהו.
  • \ r האמור גם הוא, מכיל גורם ראשוני גדול כלשהו.
ניתן להכין מספרים כאלו בעזרת אלגוריתם גורדון (Gordon) למשל. הסיבות לתנאים אלו הם: הראשון והשני נועדו לסכל שימוש באלגוריתם פירוק לגורמים על המודולוס, כמו אלגוריתם rho של פולרד או אלגוריתמים אחרים (של פולרד) המנצלים את p \pm 1. השלישי נועד לסכל את מתקפת מחזוריות (ראו להלן).

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

ריפוד[עריכת קוד מקור | עריכה]

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

  • כאשר m = 1 או m = 0 או m=n-1 תוצאת ההצפנה תהיה תמיד m עצמו.
  • כאשר מצפינים עם מעריך קטן כגון e=3 ערכים קטנים של m עלולים להניב תוצאות קטנות הנמוכות מהמודולוס מה שמאפשר חישוב שורש ממעלה שלישית ללא תלות במודולוס.
סכימה של אלגוריתם OAEP של בלייר ורוגווי לריפוד בטוח של מסר המיועד להצפנה בשיטת RSA. האלגוריתם מקבל כקלט את: 1) המסר 2) גרעין התחלתי אקראי (בטוח) לצורך פונקציית המיסוך 3) ערך אופציונלי L המשמש כקלט לפונקציית הגיבוב שהפלט שלה משורשר לגוש המידע (ערך ברירת המחדל של L הוא מחרוזת אפסים). הסימן \oplus מייצג XOR והפוקנציה MGF היא קיצור של Mask Generation Function והיא מבוססת על פונקציית גיבוב כמו SHA2. השיטה מפורטת בתקן PKCS#1 v2.2.
  • כשהמסר קטן ניתן לתקוף את ההצפנה בהתקפת מוצפן-נבחר, שבה התוקף מצפין מראש את כל האפשרויות של m ואז בחיפוש קל ימצא את c המתאים ובכך יפענח את הטקסט המוצפן מבלי לתקוף את השיטה עצמה.

כדי להימנע ממסר חלש מקובל לרפדו באמצעות אלגוריתם ריפוד מוסכם לפני ההצפנה. שיטת הריפוד עצמה לא חייבת להיות סודית. אפשר לשרשר מספר אקראי כלשהו למסר עצמו לפני ההצפנה כך שהוא מטשטש את המבנה המקורי של המסר ומסכל את התקפת טקסט מוצפן נבחר האמורה. תקן PKCS #1 יישם שיטת ריפוד פשוטה כזו. לפני ההצפנה המסר רופד באפסים ובמספר אקראי באורך מוגדר כלשהו. ב-1998 הראה דניאל בלייכבכר ממעבדות בל ששיטת ריפוד כזו אינה בטוחה כלל ואפשר לפרוץ אותה בקלות. ב-1993[7] ניסחו מתמטיקאים מאוניברסיטת קליפורניה מודל אורקל אקראי (Random oracle model) שהושאל מתורת הסיבוכיות. באמצעותו אפשר ליישם כל שיטת הצפנה אסימטרית (דטרמיניסטית) באופן שתהיה בעלת "ביטחון מוכח" או "ביטחון סמנטי". הם פתחו אלגוריתם הנקרא OAEP (קיצור של Optimal asymmetric encryption padding) המשתמש במחולל מספרים אקראיים בטוח ופונקציית גיבוב קריפטוגרפית לריפוד המסר לפני ההצפנה. ב-1998 תקן הצפנת מפתח-פומבי PKCS #1 תוקן ואלגוריתם OAEP שולב בתקן כשיטת הריפוד התקנית להצפנת מפתח פומבי הנקראת RSA-OAEP (ראה תרשים).

אלגוריתמים[עריכת קוד מקור | עריכה]

כדי ליישם את אלגוריתם RSA במחשב, אין די בדרך הרגילה באמצעות יחידת החישוב במעבד, כיוון שאורך מקסימלי של מספר שניתן לעיבוד בדרך קונבנציונאלית אינו עולה על גודלו של האוגר הגדול ביותר (נכון ל-2013 128 סיביות). וככל שהמחשבים ישתפרו, הצורך באריתמטיקה מודולרית במספרים גדולים בהרבה, רק ילך ויגדל. משום כך הפתרון המקובל הוא אריתמטיקה מרובת ספרות (Multi-precision), כלומר חישוב ספרה אחר ספרה בנפרד כאשר כל ספרה תופסת קרוב לאוגר שלם. בדרך זו החישוב יותר איטי, אך אורך המספרים אינו מוגבל (בגבולות הזיכרון הזמין במחשב). קיימות ספריות לחישובים אריתמטיים מרובי ספרות לשפות התכנות הנפוצות כגון: Long Integer Package (או FreeLIP), ספריית תמיכה למספרים ארוכים בשפת C של ארג'ן לנסטרה, שסייעה באתגר הראשון כנגד RSA, פירוק RSA-129 (בגודל 426 סיביות) ב-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; 
}

RSA מערב חישובי העלאה בחזקה עם מעריך גדול. הדרך הנאיבית לא יעילה במקרה זה. קיימים מספר אלגוריתמים לחישוב מהיר של חזקות גדולות באריתמטיקה מודולרית. להלן תיאור שיטה רקורסיבית בסיסית. הרעיון הוא שאפשר לחשב את \ a^k\ \mbox{mod}\ n באמצעות סדרת הריבועים \ a, a^2, a^4, a^8,... עד \ a^k, אפשר להכין סדרה כזו באופן רקורסיבי על ידי העלאות חוזרות בריבוע של \ a_i וצמצום ב-\ n ואז לפי חוקי החזקות אפשר לקבל את \ a^k כמכפלה של ערכים מתוך הסדרה, אותם אפשר לקבל על ידי הייצוג הבינארי של המעריך, דהיינו כאשר מופיע אחד במעריך יש לכלול את האיבר במכפלה. הטבלה הבאה מדגימה את חישוב 22^{195}\ \mbox{mod}\ 1234 כאשר הפרמטר \ k מכיל את הייצוג הבינארי של המעריך והתוצאה היא מכפלת ערכי \ a בעמודות בהן \ k_i=1 כלומר \ a^k \equiv (a_1\cdot a_2\cdot a_7 \cdot a_8) \ \mbox{mod}\ 1234=44:

\ i 1 2 3 4 5 6 7 8
\ k 1 1 0 0 0 0 1 1
\ a 22 484 1030 894 838 98 966 252

להלן פסאודו קוד של האלגוריתם:

Square_and_multiply(a, k, n)
{
 b = 1;
 If(k = 0) return b;
 For (i = 1; i<=t; i++)
 {
 a = a * a mod n;
 If(k[i]) b = a * b mod n;
 }
 return b;
}

הפרמטר \ k המייצג את \ t סיביות המעריך \ k_1,k_2,...,k_t. בלולאה הראשית באלגוריתם מעלים את \ a בריבוע וכל פעם שהסיבית הנוכחית היא 1 מכפילים ב-\ b והתוצאה נשמרת ב-\ b.

החלק הקשה באלגוריתם הוא הצמצום המודולרי. בשיטה הנאיבית מחלקים חילוק ארוך ב-\ n ונוטלים את השארית אך השימוש בחילוק אינו מומלץ במספרים גדולים אם רוצים להגיע לביצועים אופטימליים. קיימות שיטות יעילות יותר לצמצום מודולרי כמו שיטת Barrett או שיטת מונטגומרי. האחרונה נחשבת ליעילה ונפוצה במימושים מעשיים.

התקפות[עריכת קוד מקור | עריכה]

התקפת תזמון[עריכת קוד מקור | עריכה]

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

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

התקפת האדם שבתווך[עריכת קוד מקור | עריכה]

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

תכונת הכפליות (Multiplicative)[עריכת קוד מקור | עריכה]

אם \ m_1, m_2 הנם מסרים כלשהם כאשר הטקסטים המוצפנים המקבילים להם הם \ c_1, c_2 בהתאמה. אזי מתקיימת הזהות הבאה:

\ (m_1 \cdot m_2)^e \equiv m^e_1 \cdot m^e_2 \equiv c_1 \cdot c_2 (\mbox{mod }n)

תכונה זו נקראת גם הומומורפיזם והיא מאפשרת התקפה שבה לתוקף ישנה גישה חלקית למערכת ההצפנה (כאשר אין לו גישה למפתחות ההצפנה אך הוא מסוגל להפעיל את המערכת כרצונו ולבחור את המסר להצפנה) אם \ c = m^e \mbox{ mod }n וברצונו לחשוף את \ c ביכולתו להסתירו על ידי הכפלת הטקסט המוצפן ב-\ x^e כלשהו כך: \ s = cx^e \mbox{ mod }n, אם המערכת תפענח עבורו את \ s בלא ידיעת הקשר שבינו לבין \ c הוא יקבל את: \ t = s^d \mbox{ mod }n. תוצאה זו מאפשרת חילוץ \ c בשל הזהות הבאה:

\ t \equiv s^d \equiv c^d(x^e)^d \equiv mx \ (\mbox{mod }n)

ולכן \ m = tx^{-1} \mbox{ mod }n. כלומר מסירים את \ x על ידי הכפלה בהופכי שלו כדי לקבל את הטקסט מקורי. למשל בדוגמה שניתנה לעיל, אם \ r=1804 אזי \ 1804^{11}\cdot 3557=1312 \ (\mbox{mod }12319). אם נחשב את r^{-1}=2711 \ (\mbox{mod }12319) אזי ניתן לחלץ את m על ידי \ (1312^{3299} \cdot 2711) \mbox{ mod }12319 = 128 = m.

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

התקפת המעגליות (Cycling attack)[עריכת קוד מקור | עריכה]

בשל העובדה שהצפנת RSA הנה תמורה ב-\ \mathbb{Z}_n, אם \ c = m^e \mbox{ mod }n קיים שלם \ k המקיים \ c^{e^k} \equiv c \ (\mbox{mod }n). מאותה סיבה \ c^{e^{k-1}} \equiv m \ (\mbox{mod }n). אם \ n קטן חיפוש סדרתי של \ k כזה אפשרי. אפשר להתחיל בערך נמוך ולקדם את \ k עד שהמשוואה האמורה מתקיימת. יתרה מזו, ניתן לייעל את ההתקפה על ידי מציאת השלם \ u העונה על הדרישה \ \mbox{gcd}(c^{e^u} - c, n) > 1. יש סיכוי טוב למצוא את \ u בפחות מהזמן הדרוש למצוא את \ k. אם \ c^{e^u} \equiv c מודולו אחד מהגורמים הראשוניים של \ n, אזי \ \mbox{gcd}(c^{e^u} - c, n) הוא גורם ראשוני של \ n וכאמור ידיעת הגורמים הראשוניים מספקת לחילוץ מפתח הפענוח. במקרה ש-\ \mbox{gcd}(c^{e^u} - c, n)=n אזי מתקיים בהכרח \ u=k וכאמור \ c^{e^{u-1}} \equiv m, במקרה כזה מתקבל \ m בלא צורך במפתח הפענוח כלל. למעשה אפשר לראות בשיטה זו כדרך שונה לפירוק \ n לגורמים. כאמור, פירוק לגורמים היא בעיה קשה כך שתכונה זו אינה מהווה איום משמעותי על אלגוריתם RSA.

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ J-J. Quisquater and C. Couvreur. Fast decipherment algorithm for RSA public-key cryptosystem. Electronic Letters, vol 18:905–907, 1982
  2. ^ עמוס פיאט, אוניברסיטת תל אביב, אפריל 1996
  3. ^ http://eprint.iacr.org/2010/006.pdf
  4. ^ http://tau.ac.il/~tromer/papers/cbtwirl.pdf
  5. ^ http://blog.erratasec.com/2013/09/tor-is-still-dhe-1024-nsa-crackable.html#.UkxIC2QwI0M
  6. ^ http://madchat.awired.net/crypto/codebreakers/ShortSecretExponents.pdf
  7. ^ 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.