בתשובה להאייל האלמוני, 29/01/08 13:19
 |
|
 |
||
|
||||
 |
AKS פורסם לראשונה רק בשנת 2002. חשוב להדגיש שעד כמה שאני יודע, אף אחד לא משתמש בו בפועל; הוא מהווה תוצאה תיאורטית חשובה מאוד, אבל הוא איטי מדי לצרכים מעשיים, בהתחשב באלטרנטיבות. הסיכוי לשגיאה של מילר-רבין (ושל כל אלגוריתם הסתברותי בעל ערך אחר) הוא קטן *כרצוננו*. פירוש הדבר הוא שאפשר, באמצעות הגדלה לא משמעותית של זמן הריצה, להקטין משמעותית את ההסתברות לטעות. במקרה של מילר רבין, כל "בדיקה" שהאלגוריתם מבצע מותירה הסתברות של 1/4 לטעות (רק אם המספר לא ראשוני; אם הוא ראשוני, האלגוריתם תמיד מצליח). פירוש הדבר הוא שאחרי שתי בדיקות ההסתברות לטעות תהיה 1/16, אחרי שלוש, 1/64, ובאופן כללי - כל נסיון נוסף מקטין את ההסתברות לטעות פי 4. מהר מאוד אפשר להגיע להסתברויות נמוכות בצורה קיצונית לטעות - ההסתברות שמשהו יתפקשש בחומרה עצמה כבר תהיה גדולה יותר. אם בטעות מיוצר מספר לא ראשוני, אז יש סיכוי לא רע שזה יתגלה כבר בהצפנות הראשונות, בגלל שיהיה קושי לפענח חלק מההודעות (לא את כולן), אז תמיד אפשר לעשות כמה הרצות מבחן ולראות מה קורה. מה שחשוב להדגיש בכל הסיפור הזה הוא שייצור המפתח של RSA הוא דבר די חד פעמי, ולכן אפשר להקדיש לו המון זמן. תקשורת שוטפת מוצפנת בעזרת שיטות הצפנה סימטריות (שהן מהירות הרבה יותר מ-RSA), וה-RSA משמש רק להחלפה בטוחה של מפתחות אקראיים עבור השיטות הללו. |
 |
 |
 |
|
|
|
||
|
||||
|
הנה רעיון נחמד להבטיח שההצפנה תמיד תעבוד, גם אם המספרים אינם ראשוניים: כאשר אתה מריץ את מבחן מילר-רבין, תבדוק את כל הראשוניים הקטנים (נניח ה- 64 הראשונים). אח"כ תקודד את ההודעה שאתה רוצה לשלוח באמצעות הכפלה או אי הכפלה בראשוני הקטן המתאים (אתה שולח 64 ביט להודעה במקום, נניח, 512, כי כל ביט עולה לך יותר מביט בשידור, אם אתה רוצה שהמודולו לא ייכנס לפעולה כדי שהצד השני יוכל לשחזר את החזקות בצורה טריביאלית). מכיוון שבדקת עבור כל הראשוניים הנ"ל שכל אחד מהם בחזקת p-1 שווה ל- 1, מובטח לך שזה יקרה גם למכפלה כלשהי שלהם (וגם ל- q, וגם ל- pq). השימושיות של הרעיון היא כמובן נמוכה מהשימושיות של אלגוריתם דטרמיניסטי לראשוניות (יש שיגידו שהשימושיות היא שלילית, כי באלגוריתם המקורי לפחות יש סיכוי שתוך כדי השימוש השוטף תגלה שמשהו לא בסדר, בעוד שפה אתה טומן את הראש בחול), אבל זה עדיין רעיון נחמד לדעתי. אגב, כדאי לציין שלפעמים, במקום להשתמש ב- RSA כדי *להעביר* מפתח מצד א' לצד ב', אפשר להשתמש פרוטוקול דיפי-הלמן [ויקיפדיה] כדי *לתאם* מפתח בין שני הצדדים (כלומר, זה לא שמישהו בוחר את המפתח ואז מעביר אותו לשני; משתמשים בפרוטוקול שבסופו יש לכל אחד מהצדדים מפתח, שאף אחד מהם לא בחר, ושלא ידוע לאף אחד אחר מלבדם). |
|
|
|
|
|
|
||
|
||||
|
לא הבנתי שום דבר מהרעיון, אני חושש. דיפי הלמן זה סיפור בפני עצמו. כמובן שזו שיטה מקסימה, ויש לה שימושים פרקטיים רבים; אבל יש לה את הסכנות שלה (בפרט, היא חשופה בצורה קיצונית למתקפת Man-in-the-middle). כשמגיעים לשימושים מעשיים, לרוב מה שיש הוא מיש-מש אחד גדול של הרבה שיטות. למשל, פרוטוקול IKE שמשמש להסכמה על מפתח הצפנה (סימטרי) משותף משתמש גם בדיפי הלמן כדי לייצר סוד משותף, וגם (באחד מאופני התפעול שלו) בחתימות מבוססות מפתח פומבי כדי למנוע את המתקפות הסטנדרטיות על דיפי-הלמן. |
|
|
|
|
|
|
||
|
||||
|
ניקח מספר "חשוד כראשוני" 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 מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |