בתשובה לגדי אלכסנדרוביץ', 29/01/08 23:39
 |
|
 |
||
|
||||
 |
ניקח מספר "חשוד כראשוני" p. נבדוק האם כל המספרים 2,3,5,7 ועד הראשוני ה- n מקיימים n^(p-1)=1 מודולו p. נוודא שאותו דבר מתקיים עבור מספר "חשוד כראשוני" q. נוודא גם שמכפלת כל n המספרים האלו קטנה מ- pq. כעת, נניח שאנחנו רוצים להעביר הודעה בת n ביטים. נקודד את ההודעה באמצעות מספר שמהווה את מכפלת כל הראשוניים שעבורם הביט הוא 1 (ניסוח שקול: נעלה כל ראשוני בחזקת הביט שלו ונכפיל). נקרא למספר הנ"ל A. נשים לב ש- A מקיים בהכרח A^(p-1)=1 מודולו p וכנ"ל עבור q, כי A הוא מכפלה של מספרים שמקיימים תנאי זה. נצפין את ההודעה "בדרך הרגילה". הפענוח "בדרך הרגילה" בהכרח ייתן את המספר A. מכיוון שמכפלת כל n הראשוניים היתה קטנה מ- pq, בהכרח כך גם A, שהוא מכפלה של קבוצה חלקית שלהם. לכן, הצד המפענח יכול פשוט לבדוק אם A מתחלק ב- 2,3,5 וכו', ולקבל את n ביטי ההודעה המקוריים. כמובן שהשיטה בזבזנית, כי כדי להעביר הודעה של n ביטים היינו צריכים להעביר הודעה של יותר ביטים. אפשר לייעל ע"י כך שלמספרים קטנים יותר נרשה חזקות גדולות יותר (באמת מעניין לחשב כמה מידע אפשר לשדר בדרך זאת עם, נניח, מספר pq של 1024 ביט). חסרון נוסף של השיטה הוא כמובן שאנחנו סתם יורים לעצמנו ברגל: לו היינו מצפינים הודעות רגילות, ואחד המספרים (p או q) לא היה ראשוני (אלא "במקרה" עבר את המבחנים שלנו), היה סיכוי שנצפין הודעה "רעה" והפענוח ייתן הודעה שונה. כך היינו עולים על הבעיה. השיטה הזאת מבטיחה שלא נעלה על הבעיה, וזה לא כל כך חכם. מה שאהבתי בדיפי הלמן זה את האפשרות לתאם מפתח מבלי שאף אחד "תכנן" את המפתח הזה. אני לא מכיר פרוטוקולים "אמיתיים", אבל אם הייתי מתכנן אחד אני מניח שהייתי משתמש בשילוב של כמה שיטות . |
 |
 |
 |
|
|
|
||
|
||||
|
אני עדיין לא מבין. הבנתי את הרעיון הבסיסי, אבל לא למה זה עובד. אתה אומר "נצפין בדרך הרגילה" ו"נפענח בדרך הרגילה" - אבל איך אתה עושה את זה? כדי לבנות מפתחות הצפנה ופענוח שעובדים, אתה צריך לדעת את פונקצית אוילר של pq; כדי לדעת אותה, אתה צריך לדעת את p,q *ולדעת שהם ראשוניים*. אם הם לא ראשוניים, אנחנו באותו ברוך כמו כל מי שמנסה לפרוץ מבחוץ; החישוב של פונקצית אוילר של מספר קשה בדיוק כמו הפירוק שלו לגורמים. אז מה שקורה (לדעתי; לא בדקתי אף פעם מימוש "אמיתי" של RSA) הוא שמחשבים את פונקצית אוילר פשוט בעזרת הנוסחה (p-1)(q-1) שנכונה רק עבור ראשוניים. אם אין לך ראשוניים, תקבל d שייתכן מאוד שלא יעבוד (עשיתי כמה ניסויים עצמיים בזה - מקבלים d שלפעמים עובד ולפעמים לא). אני לא רואה למה השיטה שאתה מציע פותרת את הבעיה הזו (כמובן שייתכן שהיא פותרת ואני פשוט מפספס את החשבון).
|
|
|
|
|
|
|
||
|
||||
|
אז השיטה ברורה. עכשיו רק נשאר להסביר למה היא עובדת. אם כן, נניח שעבור A מסוים אנחנו יודעים ש- A^(p-1)=1 מודולו p, וש- A^(q-1)=1 מודולו q. עכשיו, את מפתחות ההצפנה והפענוח d,e בונים כך שיתקיים de=1 מודולו (p-1)(q-1). אם ההודעה המקורית היתה A, ההודעה המפוענחת תהיה A^de. נבדוק מה קורה מודולו p ומודולו q בנפרד. מודולו p: A^(de) = A^(k*(p-1)*(q-1)+1) = (A^(p-1))^(k*(q-1))*A = 1^(k*(q-1))*A = A ואותו הדבר מודולו q. ממשפט השאריות הסיני(1) נובע שנקבל חזרה את A, ולכן הפענוח יצליח.----------------- (1) עכשיו שמתי לב שבעצם יש פה דרישה נוספת - ש- p ו- q יהיו זרים (כלומר, אם במקרה נפלנו בשניהם על מספרים פריקים, ואם במקרה שני המספרים הפריקים אינם זרים זה לזה - נדפקנו). אפשר פשוט לוודא שהם זרים (אלגוריתם GCD הוא פולינומיאלי בגודל הקלט). לחליפין, אפשר לפתור בדרך אחרת: במקום לבדוק ש- 2,3,5 וכו' עוברים את מבחן פרמה, תבדוק ש- a^de=a מודולו pq, עבור כל המספרים האלו. אז מובטח לך שזה יהיה נכון גם עבור כל מכפלה שלהם. |
|
|
|
|
|
|
||
|
||||
|
אחלה. עכשיו אני נוטה להסכים שמדובר בשיטה לא משהו, אבל שהיא עובדת. | |
|
|
|
|
|
||
|
||||
|
אני בטוח שאחרי השרשור הזה נחה דעתו והתבססה הבנתו של מוס גולמי :-) | |
|
|
|
|
|
||
|
||||
|
לדעתי נחה הבנתו (היא לא התקדמה לשום מקום) והתבססה דעתו (על משתתפי הדיון). | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |