RSA

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

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

[עריכה] היסטוריה

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

[עריכה] זכויות

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

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

[עריכה] בסיס מתמטי

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

[עריכה] הכנת מפתחות RSA

בוחרים שני ראשוניים גדולים $\ p$ ו- $\ q$ .
מחשבים את $\ n = pq$ .
מחשבים את פונקציית אויילר: $\ \phi (n)=(p-1)(q-1)$ (מבוטא "פִי של $\ n$ " ומסומן כאן בקיצור $\ \phi$ ).
בוחרים שלם $\ e$ הנמוך מ- $\ n$ שהוא זר ל- $\ \phi$ .
מחשבים את $\ d$ המקיים את יחס השקילות: $\ de \equiv 1 \ (\mbox{mod }\phi)$ .

[עריכה] פירוט הפרמטרים

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

[עריכה] הצפנה ופענוח

הצפנה

אליס משדרת לבוב את מפתחות ההצפנה ( $\ 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}$

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

[עריכה] הוכחה לנכונות האלגוריתם

כאמור $\ ed \equiv 1 \ (\mbox{mod } \phi)$ , כלומר קיים שלם $\ k$ המקיים $\ ed=1+k \phi$ . לפי משפט פרמה: $\ 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=97, q=127$ ומחשבת את: $\ n=97 \cdot 127=12319$ ואת פונקציית אוילר: $\ \phi=96 \cdot 126=12096$ וכן בוחרת את $\ e=11$ , כיוון שמתקיים $\ \mbox{gcd}(12096,11)=1$ . בעזרת אלגוריתם אוקלידס המורחב מתקבל $\ (3299 \cdot 11) \equiv 1 \ (\mbox{mod } \phi)$ כיוון ש- $\ 3299 \cdot 11 \mbox{ mod }12096 = 1$ , יוצא ש- $\ d=3299$ הינו מפתח הפענוח המתאים. אליס שולחת את $\ 12319$ ואת $\ 11$ לבוב ושומרת בסוד את $\ 3299$ .

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

$\ 128^{11} \mbox{ mod }12319 = 3557$

ושולח את $\ c=3557$ לאליס.

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

$\ 3557^{3299} \mbox{ mod }12319=128=m$ .

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

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

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

בהפעלת הפונקצייה ההופכית $\ 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$ . פונקציית היתירות מבטלת את האסוציאטיביות של המסרים ועל כן מונעת בעיה זו.

[עריכה] בטיחות

שיטת RSA מתבססת על בעיית RSA (נקראת גם 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)$ (פירושו $\ m^e$ שקול ל- $\ c$ מודולו $\ n$ ). הבעיה היא מציאת שורש ממעלה $\ e$ של $\ m$ (מודולו $\ n$ ). המגבלות שהוטלו על הפרמטרים מבטיחים כי לכל $\ c$ קיים אך ורק $\ m$ יחיד המקיים שקילות זו, מאחר והפונקציה החד-כיוונית $\ f(m)=m^e \mbox{ mod }n$ היא תמורה ב- $\ \mathbb{Z}_n$ . הקושי נעוץ בעובדה שתוצאת הפונקציה האמורה אינה לינארית ולמעשה מתנהגת כפונקציה אקראית. חיפוש סדרתי של ערך כזה מחייב במקרה הגרוע בדיקת כל המעריכים האפשריים ועל כן אינה מעשית.

[עריכה] פירוק לגורמים

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

בנובמבר 2005 הצליח צוות מתמטיקאים לפרק לגורמים בעזרת האלגוריתם Number field sieve את המודולוס RSA-200 (בגודל 663 סיביות) מתוך מספרי האתגר של מעבדות RSA, המספר הגדול ביותר שפורק לגורמים נכון להיום. המאמץ נמשך כמעט שלוש שנים, תוך שימוש במספר גדול של מחשבים שעבדו במקביל. כיום ניתן לבנות מחשבים יעודיים המסוגלים לפרק מספרי RSA בגודל 512 סיביות בזמן קצר יחסית. חלק מהמומחים חוששים שבטווח הארוך, הופעת מחשבים קוונטים תהפוך את שיטת ההצפנה הזו ללא בטוחה. נכון להיום, לא קיימים מחשבים קוונטים, ושימוש במודולוס בגודל 2048 סיביות (או 4096 סיביות למי שחוששים במיוחד), נותנת רמת בטיחות מספקת לכל צורך מעשי.

[עריכה] יעילות

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

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

[עריכה] פרמטרים

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

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

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

[עריכה] מספרים ראשוניים

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

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

$\ p-1$ מכיל גורם ראשוני גדול $\ r$ .
$\ p+1$ מכיל גורם ראשוני גדול כלשהו.
$\ r$ האמור גם הוא, מכיל גורם ראשוני גדול כלשהו.

ניתן להכין מספרים כאלו בעזרת אלגוריתם גורדון (Gordon) למשל. הסיבות לתנאים אלו הם: הראשון והשני נועדו לסכל שימוש באלגוריתם פירוק לגורמים על המודולוס, כמו פולארד רו ודומיו המנצלים את $p \pm 1$ . השלישי נועד לסכל את מתקפת מחזוריות (ראה להלן). אין הוכחה כי ראשוניים חזקים מספקים שיפור משמעותי בבטיחות RSA, לעומת ראשוניים אקראיים רגילים. אולם כיוון שהכנתם אינה דורשת מאמץ מיוחד, אין סיבה שלא להשתמש בהם.

[עריכה] ריפוד

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

במקרה ש- m = 0, m = 1 או m = n-1 תוצאת ההצפנה תהיה תמיד m עצמו. דבר שרצוי להימנע ממנו.
כאשר מצפינים עם מעריך e קטן כגון e = 3 ערכים קטנים של m עלולים להניב תוצאות קטנות הנמוכות מהמודולוס מה שמאפשר חישוב שורש ממעלה שלישית שלהם ופענוח המסר בקלות.
כמו כן במקרה שהמסר קטן ניתן לתקוף את הצופן במתקפת צופן נבחר (Chosen ciphertext), שבה התוקף מצפין מראש את כל האפשרויות של m כדי לבדוק את תוצאתם, בסבירות גבוהה הוא יעלה על c מתאים ובכך יפענח את הצופן מבלי לתקוף את השיטה עצמה.

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

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

כאמור מפתח הפענוח $\ d$ נקרא הופכי כפלי של $\ e$ (מודולו $\ n$ ). מציאת הופכי כפלי נעשית באמצעות אלגוריתם אוקלידס המורחב. הגרסה הבסיסית מתוארת להלן:

  Input:   a, b (a >= b).
  Output:  d = ax + by. (d is Gcd(a, b))
  1. if b = 0 then 
        d = a, x = 1, y = 0.
        Goto: 5.
  2. x1 = 0, x2 = 1, y1 = 1, y2 = 0
  3. While b > 0 do:
     3.1 q = a / b, r = a mod b, 
         x = x2 - q * x1, 
         y = y2 - q * y1.
     3.2 a = b, b = r, 
         x2 = x1, x1 = x, 
         y2 = y1, y1 = y
  4. d = a, x = x2, y = y2
  5. return d, x, y

תהליך ההצפנה והפענוח לעיל מערב חישוב העלאה בחזקות גדולות. חישוב חזקות גדולות באריתמטיקה מודולרית נעשית באמצעות אלגוריתמים המיוחדים לכך. דוגמה בסיסית לאלגוריתם כזה נקראת Repeated square and multiply, שיטה רקורסיבית לחישוב חזקות גדולות על ידי פירוק החזקה לסדרה של העלאות בריבוע והכפלות, כדלהלן:

  Input: a, k, n (a < n, k is t binary digits long).
  Output: a^k mod n
  1. b=1
  2. if k = 0 then return b.
  3. if k_0 = 1 then b = a.
  4. For i from 1 to t do:
     4.1 a = a^2 mod n.
     4.2 if k_i = 1 then b = a * b mod n.
  5. return b.

עוברים על k המייצג את סיביות המעריך החל מהסיבית הנמוכה ביותר כלפי מעלה. בכל שלב מעלים את a בריבוע ובנוסף אם הסיבית הנוכחית היא 1 מכפילים את a ב-b, כאשר התוצאה הסופית היא b.

[עריכה] התקפות

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

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

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

[עריכה] הפצת מפתחות

נדמה כאילו הצפנת RSA היא הפתרון המושלם, למעשה אין זה כך. הצפנת RSA לבדה אינה פותרת את בעיית האימות והבטחת השלמות. במילים אחרות, תוקף אקטיבי המסוגל להשתלט על ערוץ התקשורת שבין אליס ובוב, ליירט מסרים לשנותם ולשולחם ליעדם, מסוגל להונות את המשתתפים ולקרוא את כל התשדורות המוצפנות. בהתקפה זו הנקראת Man in the middle, התוקף מיירט את מפתח ההצפנה שאליס שולחת לבוב ומחליפו באחר, כך שבוב יצפין את המסר עבור אליס במפתח הלא נכון בלא ידיעתו. כמו כן התוקף יירט את המסר המוצפן שבוב שולח לאליס, יפענחו יקרא את תוכנו ואז יצפינו במפתח הנכון וישלח אותו ליעדו, כאשר בוב ואליס אינם מודעים למתרחש. במילים אחרות, בוב חייב להיות בטוח שהמפתח הפומבי אכן שייך לאליס. כמו כן אליס אינה יכולה לדעת מיהו המקור למסר שקיבלה ללא אמצעים נוספים כדי להבטיח זאת. על כן יש צורך להבטיח את שלמות ואותנטיות מפתח ההצפנה. זאת עושים באמצעות שיטות אימות ידועות, ביניהן העזרות בצד-שלישי נאמן (כמו רשות אישורים 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$ .

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

[עריכה] תכונת המחזוריות

בשל העובדה שהצפנת 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.