RSA

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

כדי להכין מפתחות RSA בוחרים שני ראשוניים p ו־q, מחשבים n = p·q, ואז מחשבים פונקציית אוילר φ(n)=(p-1)(q-1). בוחרים מספר e שהוא זר ל־φ(n) (כלומר אין לו מכנה משותף עם φ). מחשבים את d שהוא ההופכי הכפלי של e מודולו φ(n). זוג (e,n) הוא המפתח הציבורי; d הוא המפתח הפרטי.

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

RSA איטי יחסית להצפנת נתונים גדולים. לכן משתמשים בו בדרך כלל להעברת מפתח סודי שנעשה בו שימוש להצפנה סימטרית מהירה (כמו AES). יש גרסאות מהירות יותר לפענוח, למשל RSA‑CRT, שמחשיב את הפעולה בנפרד עבור p ו‑q ומשלב חזרה. קיימות גם גרסאות Multi‑prime ו‑Rebalanced להאצת חישובים במערכות מעשיות.

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

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

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

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

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

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

מדריכים בוחרים שני מספרים ראשוניים p ו־q. מכפילים אותם לקבל n. מחשבים מספרים מיוחדים ועושים חישובים כדי לקבל שני מפתחות: אחד פרטי, אחד ציבורי.

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

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

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