RSA

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

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

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

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

החיסרון העיקרי באלגוריתמים סימטריים להצפנה הוא שהמפתח הסודי נדרש להצפנה ולפענוח ולכן יש צורך להעבירו לידי המקבל בדרך כלשהי ובכך לסכנו בחשיפה. ב-1976 פרסמו ויטפילד דיפי ומרטין הלמן מאמר מפורסם המתאר את התפיסה של המפתח הפומבי, שבה המקבל מפרסם מפתח הצפנה פומבי בעזרתו מבוצעת ההצפנה עבורו, ואילו הפענוח מתבצע אך ורק באמצעות המפתח הפרטי שברשותו, שמעולם לא נחשף. כשנה לאחר מכן ב-1977, רונלד ריבסט (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 בה מנצלים את משפט השאריות הסיני כדי לחלק את מפתח הפענוח הסודי לשני מפתחות קטנים. מחשבים את \ 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 בדרך כלשהי כדי להבטיח שלא יסכן את ביטחון ההצפנה (ראו ריפוד). וכן כדי להבטיח את שלמות ושייכות המפתחות מקובל לרשום אותם אצל צד שלישי מהימן כמו רשות אישורים (ראה מפתח פומבי).

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

Postscript-viewer-shaded.png ערך מורחב – בעיית RSA

הרעיון של 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).

ביטחון השיטה מתבסס על בעיית RSA כדלקמן; נתון שלם חיובי \ 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).


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

לפי האלגוריתם מפתח הפענוח \ 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 }5580) באופן דומה מוצאים את 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=15\cdot 8059 + 2571.

כמובן שהדוגמה להמחשה בלבד, חובה על הראשוניים \ 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. אם כי לא ידוע על דרכים יעילות לשבירת האלגוריתם בשל שינויים אילו. ראו המאמר של דן בונה וחובב שחם Fast Variants of RSA‏[3] שפורסם במגזין Cryptobytes של RSA, קיץ 2002.

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

הצפנת 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 והיא בעיקרון פלט חלקי של פונקציית גיבוב כמו SHA-2. השיטה מפורטת בתקן PKCS#1 v2.2.
  • כשהמסר קטן ניתן לתקוף את ההצפנה בהתקפת מוצפן-נבחר, שבה התוקף מצפין מראש את כל האפשרויות של m ואז בחיפוש קל ימצא את c המתאים ובכך יפענח את הטקסט המוצפן מבלי לתקוף את השיטה עצמה.

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

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

כדי ליישם את 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 או "Left to right exponentiation". הרעיון הוא שאפשר לחשב את \ a^k\ \mbox{mod}\ n באמצעות סדרת הריבועים \ a, a^2, a^4, a^8,... עד \ a^k, אפשר להכין סדרה כזו באופן רקורסיבי על ידי העלאות חוזרות בריבוע של \ a_i וצמצום ב-\ n ואז לפי חוקי החזקות אפשר לקבל את \ a^k כמכפלה של ערכים מתוך הסדרה אותם אפשר לקבל על ידי הייצוג הבינארי של המעריך, דהיינו כאשר מופיע אחד במעריך יש לכלול את האיבר במכפלה. הטבלה הבאה מדגימה את חישוב 22^{195}\ \mbox{mod}\ 1237 כאשר הפרמטר \ k מכיל את הייצוג הבינארי של המעריך והתוצאה היא מכפלת ערכי \ a בעמודות בהן \ k_i=1 כלומר \ a^k \equiv (a_1\cdot a_2\cdot a_7 \cdot a_8) \ \mbox{mod}\ 1237=87:

\ i 1 2 3 4 5 6 7 8
k 1 1 0 0 0 0 1 1
a 22 484 463 368 591 447 652 813
b 22 752 752 752 752 752 452 87

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

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. בלולאה הראשית סורקים את סיביות \ k מימין לשמאל (מהספרה הכי פחות משמעותית לספרה הכי משמעותית), מעלים את \ a בריבוע בכל סבב וכל פעם שהסיבית הנוכחית היא 1 בנוסף מכפילים ב-\ b. התוצאה הסופית נשמרת ב-\ b.

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

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

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

Postscript-viewer-shaded.png ערך מורחב – התקפת ערוץ צדדי

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

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

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

Postscript-viewer-shaded.png ערך מורחב – התקפת אדם באמצע

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

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

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

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

  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. ^ Fast Variants of RSA (survey)
  4. ^ 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.