Movatterモバイル変換

[0]ホーム
URL:

לדלג לתוכן
ויקיפדיההאנציקלופדיה החופשית
חיפוש

RSA

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

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

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

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


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

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

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

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

הצפנה ופענוח

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

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

הצפנה

[עריכת קוד מקור |עריכה]
c=me mod n{\displaystyle {\boldsymbol {c=m^{e}{\mbox{ mod }}n}}}.

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

פענוח

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

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

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

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

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

RSA-CRT

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

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

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

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

RSA Multi-primes

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

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

  1. תחילה עבור הגורמים r1,r2,...,ru{\displaystyle \ r_{1},r_{2},...,r_{u}} כאשר u≥3{\displaystyle \ u\geq 3} מחשבים את mi=cdi mod ri{\displaystyle \ m_{i}=c^{d_{i}}{\mbox{ mod }}r_{i}} כאשרdi{\displaystyle d_{i}} הם מפתחות הפענוח שהוכנו קודם (פרמטרים מתקדמים לעיל).
  2. מחשבים את h=(m1−m2)⋅r2−1 (mod r1){\displaystyle \ h=(m_{1}-m_{2})\cdot r_{2}^{-1}\ ({\mbox{mod }}r_{1})}.
  3. מחשבים את m=m2+r2⋅h{\displaystyle \ m=m_{2}+r_{2}\cdot h}.
  4. מציבים R=r1{\displaystyle \ R=r_{1}} ועבור i=3{\displaystyle \ i=3} עד u{\displaystyle \ u} מחשבים את:
    1.  R=R⋅ri−1{\displaystyle \ R=R\cdot r_{i-1}} (כפולת כל הראשוניים למעט ri{\displaystyle \ r_{i}})
    2.  h=(mi−m)⋅ti (mod ri){\displaystyle \ h=(m_{i}-m)\cdot t_{i}\ ({\mbox{mod }}r_{i})}
    3.  m=m+R⋅h{\displaystyle \ m=m+R\cdot h}

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

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

בסיס מתמטי

[עריכת קוד מקור |עריכה]
ערך מורחב –בעיית RSA

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

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

הוכחת נכונות

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

RSA-CRT[2]‎
ב־1982 פותחה גרסת RSA-CRT בה תהליך הכנת המפתחות והפענוח דורשים מספר התאמות: מחשבים שני מפתחות פענוח dp{\displaystyle \ d_{p}} ו־ dq{\displaystyle \ d_{q}} באופן שמתקיים e⋅dp≡1 (mod (p−1)){\displaystyle \ e\cdot d_{p}\equiv 1\ ({\mbox{mod }}(p-1))} וכן e⋅dq≡1 (mod (q−1)){\displaystyle \ e\cdot d_{q}\equiv 1\ ({\mbox{mod }}(q-1))}. לפענוח תחילה מחשבים את m1=cdp mod p{\displaystyle \ m_{1}=c^{d_{p}}{\mbox{ mod }}p} ואת m2=cdq mod q{\displaystyle \ m_{2}=c^{d_{q}}{\mbox{ mod }}q}. נעזרים באלגוריתם של הרווי גארנר לחישוב CRT, כדי לחלץ את m{\displaystyle \ m} מתוך מערכת השקילויות כך: h=(m1−m2)⋅q−1 mod p{\displaystyle \ h=(m_{1}-m_{2})\cdot q^{-1}{\mbox{ mod }}p} (כאשר q−1{\displaystyle \ q^{-1}} הוא הופכי כפלי של q{\displaystyle \ q} מודולו p{\displaystyle \ p}). המסר m{\displaystyle \ m} יהיה m2+q⋅h{\displaystyle \ m_{2}+q\cdot h}. כיוון שהמפתחות dp{\displaystyle \ d_{p}} ו־ dq{\displaystyle \ d_{q}} קטנים בחצי מהמודולוס זמן הפענוח מתקצר בפקטור של 2 כמעט, זאת מבלי לאבד מביטחון האלגוריתם.
Batch RSA[3]‎
גרסת RSA שלעמוס פיאט שבה, אם המפתח הפומבי קטן מאוד, ניתן לפענח מספר מסרים שהוצפנו תחת אותו מודולוס בבת אחת. רעיון זה שימושי במערכות דוגמת שרתSSL המבצע פעולותHandshake בתדירות גבוהה. במקרה כזה ניתן לשנות את ארכיטקטורת השרת כך שימתין לקבלת מספר בקשות פענוח ואז יפענח את כל המסרים במחיר של פעולת פענוח אחת, בתנאי שהמודולוס זהה ומפתחות ההצפנה קטנים (ושונים). שיטה זו משפרת את יעילות אלגוריתם RSA בפקטור של כמעט 3.5 אם מבצעים שמונה פענוחים בבת אחת. כדי להסביר כיצד זה פועל, ידוע שבעיית RSA היא מציאת שורש ממעלה כלשהי מודולו שלם פריק N{\displaystyle \ N}. כלומר:
 Md (mod N)=M1/e (mod N){\displaystyle \ M^{d}\ ({\mbox{mod }}N)=M^{1/e}\ ({\mbox{mod }}N)}.
בתהליכי הפענוח והכנת החתימה המתוארים לעיל, יש צורך להעלות את M{\displaystyle \ M} בחזקת d{\displaystyle \ d} כלומר לחשב את M1/e{\displaystyle \ M^{1/e}}. אם למשל e1=3,e2=5{\displaystyle \ e_{1}=3,e_{2}=5}, ונתונים M1,M2{\displaystyle \ M_{1},M_{2}} שעבורם צריך לחשב את m11/3{\displaystyle \ m_{1}^{1/3}} ואת M21/5{\displaystyle \ M_{2}^{1/5}}, אפשר לחשב תחילה את:
 M=M15⋅M23 (mod N){\displaystyle \ M=M_{1}^{5}\cdot M_{2}^{3}\ ({\mbox{mod }}N)} ואת,
 I=M1/15 (mod N){\displaystyle \ I=M^{1/15}\ ({\mbox{mod }}N)}.
ואז לפתור את המשוואות הנ"ל כדלהלן:
 I6M12⋅M2=M21/5 (mod N){\displaystyle \ {\frac {I^{6}}{M_{1}^{2}\cdot M_{2}}}=M_{2}^{1/5}\ ({\mbox{mod }}N)},
 IM21/5=M11/3 (mod N){\displaystyle \ {\frac {I}{M_{2}^{1/5}}}=M_{1}^{1/3}\ ({\mbox{mod }}N)}.
יוצא שרק בחישוב I=M1/15{\displaystyle \ I=M^{1/15}} נדרשת העלאה בחזקה מודולרית מלאה, בנוסף למספר קבוע קטן של פעולות כפל וחילוק מודולריים. החסכון הוא ששתי העלאות בחזקה מודולו N{\displaystyle \ N} בוצעו כמעט במחיר של העלאה בחזקה מודולרית אחת. הטריק המתואר מסתמך על העובדה שהמעריכים זרים זה לזה. אפשר להוסיף שיפורים לשיטה זו כמו CRT האמור. החסרון העיקרי הוא בצורך במפתחות הצפנה קטנים מאוד. כאשר מפתח הצפנה גדול, Batch RSA לא תהיה יעילה בשל התקורה הרבה הנוספת.
Multi-prime RSA
גרסה זו מבוססת על שינוי מבנה המודולוס. מיישמים את RSA עם מודולוס במבנה n=pqr{\displaystyle \ n=pqr} או n=r1⋅r2⋯ru{\displaystyle \ n=r_{1}\cdot r_{2}\cdots r_{u}} כאשר u≥3{\displaystyle \ u\geq 3}. מכינים מפתחות פענוח מתאימים כמספר הגורמים, מפענחים עם כל מפתח במפרד ואז מחשבים את מערכת הקונגרואנציות באמצעות אלגוריתם CRT. במקרה של שלושה גורמים, אם המודולוס בגודל 2048 סיביות, כל גורם ראשוני יהיה בערך בגודל 683 סיביות. חישוב חזקה מודולרית בסדר גודל כזה מהיר במידה ניכרת מאשר חישוב החזקה עם המודלוס עצמו. משיקולי ביטחון במקרה שהמודולוס בגודל 1024 סיביות מספר הגורמים המקסימלי יכול להיות 3. RSA multi-prime מהירה יותר מהגרסה הבסיסית בפקטור של 2 בקירוב. תקן PKCS #1 תומך בגרסה זו.
Multi-power RSA
בגרסה זו המודולוס הוא מהצורה: N=pb−1q{\displaystyle \ N=p^{b-1}q} כאשר p{\displaystyle \ p} ו־ q{\displaystyle \ q} הם בגודל n/b{\displaystyle \ n/b} סיביות (n הוא מספר סיביות המודולוס). במקרה של 1024 סיביות משיקולי ביטחון, לכל היותר b=3{\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 בדרך של פירוק לגורמים רצוי שהמודולוס יהיה גדול ככל האפשר, אולם זה פוגע ביעילות השיטה במיוחד בסביבה מוגבלת במשאבים. אולם אם p{\displaystyle \ p} קטן, נניח 1000 סיביות ו־ q{\displaystyle \ q} גדול פי חמישה, אזי משיגים שיפור בביטחון השיטה ועדיין תהליכי ההצפנה והפענוח נותרים באותה רמתסיבוכיות (בתנאי שהמסר קטן מ־ p{\displaystyle \ p}). זאת כיוון שיעילות אלגוריתמים המנצלים קיומם של גורמים קטנים אינה גבוהה והאלגוריתמים הכלליים פחות יעילים כאשר המודולוס גדול. בשיטה זו ההצפנה זהה, כל עוד המעריך e{\displaystyle \ e}גדול מספיק כדי ש־ me{\displaystyle \ m^{e}} מספיק גדול. לפענוח מנצלים את CRT כדי לחשב את: cd mod n{\displaystyle \ c^{d}\ {\mbox{mod }}n} כך: תחילה מצמצמים d′≡d mod ϕ(p){\displaystyle \ d'\equiv d\ {\mbox{mod }}\phi (p)} ואת r≡c mod p{\displaystyle \ r\equiv c\ {\mbox{mod }}p} ואז מחשבים את m=rd′ mod p{\displaystyle \ m=r^{d'}\ {\mbox{mod }}p}. אך יש להיזהר מפניהתקפת מוצפן־נבחר שבה התוקף מצליח לחלץ מידע מסוים לגבי סיביות המפתח, כאשר מנסים לפענח את m>p{\displaystyle \ m>p} התוצאה תהיה m~≠m{\displaystyle \ {\tilde {m}}\neq m} במקרה זה מתקבלת הודעת שגיאה מהמערכת. באמצעות חישוב CRT וחיפוש בינארי ניתן למקד את החיפוש עד כדי חשיפת המפתח כולו במספר קטן של ניסיונות.

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

ריפוד

[עריכת קוד מקור |עריכה]
ערך מורחב –ריפוד אופטימלי להצפנה אסימטרית

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

סכימה של אלגוריתם OAEP של בלייר ורוגווי לריפוד בטוח של מסר המיועד להצפנה בשיטת RSA. האלגוריתם מקבל כקלט את: 1) המסר 2) גרעין התחלתיאקראי (בטוח) לצורך פונקציית המיסוך 3) ערך אופציונליL{\displaystyle L} המשמש כקלט לפונקציית הגיבוב שהפלט שלה משורשר לגוש המידע (ערך ברירת המחדל שלL{\displaystyle L} הוא מחרוזת אפסים). הסימן⊕{\displaystyle \oplus } מייצג XOR והפונקציה MGF היא קיצור של Mask Generation Function והיא בעיקרון פלט חלקי שלפונקציית גיבוב כמוSHA-2. השיטה מפורטת בתקן PKCS#1 v2.2.
  • כשהמסר קטן ניתן לתקוף את ההצפנה בהתקפת מוצפן־נבחר, שבה התוקף מצפין מראש את כל האפשרויות שלm{\displaystyle m} ואז בחיפוש קל ימצא אתc{\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 הוא יצירת מפתח הפענוח d{\displaystyle \ d} שנקרא הופכי כפלי מודולרי של e{\displaystyle \ e} (מודולו n{\displaystyle \ n}). כדי למצוא מספר כזה צריך לפתור את משוואת אוקלידס de+kϕ(n)=1{\displaystyle \ de+k\phi (n)=1} עבור שלם k{\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;}returny2;}

הצפנה ופענוח דורשים פעולות העלאה בחזקה עם מעריך גדול. הדרך הנאיבית לחישוב חזקה אינה יעילה במקרה זה. קיימים מספר אלגוריתמים לחישוב חזקות גדולות באריתמטיקה מודולרית. להלן תיאור שיטה רקורסיבית בסיסית שנקראת Square and Multiply או "העלאה בחזקה משמאל לימין". הרעיון הוא שאפשר לחשב את ak mod n{\displaystyle \ a^{k}\ {\mbox{mod}}\ n} באמצעות סדרת הריבועים a,a2,a4,a8,...{\displaystyle \ a,a^{2},a^{4},a^{8},...} עד ak{\displaystyle \ a^{k}}, אפשר להכין סדרה כזו באופן רקורסיבי על ידי העלאות חוזרות בריבוע:ai=ai−12 mod n{\displaystyle a_{i}=a_{i-1}^{2}{\text{ mod }}n}. לפי חוקי האריתמטיקה מודולוn{\displaystyle n} אפשר לבצע את הצמצום המודולרי לאחר כל העלאה בריבוע במקום לבצע את הצמצום בסוף ובכך להימנע מהתנפחות התוצאה. לפיחוקי החזקות אפשר לקבל אתak{\displaystyle a^{k}} כמכפלה של ערכים מתוך הסדרה האמורה, אותם אפשר לקבל על ידי הייצוג הבינארי של המעריך, דהיינו כאשר הסיבית הנוכחית היא אחד יש לכלול את האיבר המתאים במכפלה. הטבלה הבאה מדגימה את2453125 mod 10237{\displaystyle 245^{3125}{\mbox{ mod }}10237}. הפרמטרk{\displaystyle k} בטבלה מכיל את הייצוג הבינארי של המעריך:{1,1,0,0,0,0,1,1,0,1,0,1}2{\displaystyle \{1,1,0,0,0,0,1,1,0,1,0,1\}_{2}} כאשר הסיבית הימנית היא הסיבית הכי פחות משמעותית והסיבית השמאלית היא הסיבית המשמעותית ביותר. התוצאה תהיה מכפלת ערכיa{\displaystyle a} בעמודות בהןki=1{\displaystyle k_{i}=1} כלומר

2453125≡(a1⋅a3⋅a5⋅a6⋅a11⋅a12) mod 10237≡(245⋅6579⋅8608⋅2258⋅9942⋅5129) mod 10237≡9737{\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}
i{\displaystyle i}123456789101112
k{\displaystyle {\boldsymbol {k}}}101011000011
a{\displaystyle {\boldsymbol {a}}}2458840657912058608225853828082374552699425129
b{\displaystyle {\boldsymbol {b}}}2452454646464670461570157015701570157077529737

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

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;}returnb;}

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

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

התקפות

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

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

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

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

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

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

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

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

ראו גם

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

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

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

הערות שוליים

[עריכת קוד מקור |עריכה]
  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.
מושגי יסוד
RC4 •Salsa20 •SOSEMANUK •גריין •E0 •A5/1 •A5/2 •A5/3 •A5/4 •MICKEY •HC-128 •SNOW •Trivium •Rabbit •ZUC •ChaCha
פרימיטיבים תאורטיים
בעיות מתמטיות ואלגוריתמים
SHA •MD5 •MD4 •SHA-1 •SHA-2 •SHA-3 •RIPEMD •Skein •BLAKE •Grøstl •SipHash
אימות וזיהוי
נושאים נלווים
אוחזר מתוך "https://he.wikipedia.org/w/index.php?title=RSA&oldid=40348054"
קטגוריות:
קטגוריה מוסתרת:
[8]ページ先頭
©2009-2026 Movatter.jp