הצטרפות לדואר חשמלי | הסרת מנוי מדואר חשמלי | שלח מכתב | דף ראשי

האם הצפנת RSA נשברה?
05/06/2003 | דואר חשמלי | גיליון מספר 14

משה הלוי *

[email protected]

למאמר המקור

0003.html

המתימטיקה של הצפנת RSA

מתוך נספח י (יוד) בספר "סודות ההצפנה" של סיימון סינג בהוצאת ידיעות אחרונות.

הטקסט עבר מספר תיקונים מתבקשים שבספר נכתבו בצורה שגויה.

(1)

אליס בוחרת שני מספרים ראשוניים עצומים, p ו q. על המספרים הראשונים להיות עצומים, אבל לשם הפשטות נניח שאליס בוחרת p=17, q=11. היא חייבת לשמור על מספרים אלה בסוד.

(2)

אליס כופלת את שני המספרים שבחרה זה בזה, ומקבלת מספר נוסף, N. במקרה זה N=187. כעת היא בוחרת מספר נוסף e, ובמקרה זה היא בוחרת e=7.

(e ו (p-1)*(q-1) צריכים להיות ראשוניים יחסית, כלומר המספר היחיד המחלק את שניהם הוא 1, אבל זהו עניין טכני).

(3)

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

(4)

כדי להצפין הודעה יש להמיר תחילה את ההודעה למספר, M. לדוגמה, מלה מומרת לספרות בינריות על פי קוד ASII, ואפשר להתייחס לספרות הבינריות כאל מספר עשרוני. אחר כך M מוצפן כך שהוא נותן C, על פי הנוסחה:

C = M^e (mod N)

(5)

תארו לעצמכם שבוב רוצה לשלוח לאליס כאילו נשיקה, סתם כך, את האות "X" על פי קוד ASCII אות זו מיוצגת על ידי המספר 1011000 המקביל למספר 88 העשרוני. לכן M=88.

(6)

כדי להצפין הודעה זו, בוב מחפש תחילה את המפתח הציבורי של אליס ומגלה ש N=187 ו e=7. נתונים אלה מספקים לו את הנוסחה הדרושה כדי להצפין הודעות לאליס. עבור M=88, הנוסחה היא:

C = 88⁷ (mod 187)

(7)

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

7 = 4 + 2 + 1

88⁷ (mod 187) = [88⁴ (mod 187) * 88² (mod 187) * 88¹ (mod 187)] (mod 187)

88¹ (mod 187) = 88 (mod 187) = 88

88² (mod 187) = 7,744 (mod 187) = 77 (mod 187) = 77

88⁴ (mod 187) = 59,969,536 (mod 187) = 132 (mod 187) = 132

88⁷ (mod 187) = (88¹ * 88² * 88⁴) (mod 187) = (88 * 77 * 132) (mod 187)

88⁷ (mod 187) = 894,432 (mod 187) = 11 (mod 187)

C = 11

כעת בוב שולח לאליס את הטקסט המוצפן, C=11.

(8)

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

(9)

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

e * d = 1 ( mod (p-1)*(q-1) )

7 * d = 1 ( mod (17-1)*(11-1) )

7 * d = 1 ( mod 16*10 )

7 * d = 1 ( mod 160 )

d = 23

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

(הערה נוספת: האלגוריתם של אוקלידס ידוע במדעי המחשב כאלגוריתם gcd, ראשי תיבות של greatest common divisor, המחלק המשותף הגדול ביותר של שני מספרים. - מ.ה)

(10)

כדי לפענח את ההודעה אליס פשוט משתמשת בנוסחה הבאה:

M = C^d (mod 187)

M = 11²³ (mod 187)

M = [11¹ (mod 187) * 11² (mod 187) * 11⁴ (mod 187) * 11¹⁶ (mod 187)] (mod 187)

M = 11 * 121 * 55 * 154 (mod 187)

M = 88 = “X” in ASCII

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