בתשובה להאייל האלמוני, 12/06/08 21:32
 |
|
 |
||
|
||||
 |
הצפנה עם סודיות מוחלטת דורשת כתנאי הכרחי החלפת מפתחות מראש, ומפתח שאיננו קצר מההודעה המוצפנת. זה הופך אותה ללא-רלוונטית בתחומים רבים, אבל בתחומים שהיא כן רלוונטית, מכונה כמו שתיארת (דמיונית לחלוטין - אני כאן עם גדי לגמרי) לא פוגעת בסודיות בכלל. הצפנה ללא סודיות מוחלטת חשופה מפני מכונות טיורינג (דמיונית) לאותן התקפות כמו המכונה האפילו יותר דמיונית שלך (שמסוגלת לחשב בזמן קבוע, אבל נדרש זמן יותר [הרבה יותר] מפולינומי באורך המפתח לבנות אותה - ויותר חשוב, למספר אטומים העולה על זה שנמצא ביקום, כבר לקלטים באורך לא גדול במיוחד - זאת מבלי בכלל להכנס לזמן האסימפטוטי). דרך אגב, לתוך כל הצפנה ראויה לשמה מובנה אלמנט של אקראיות (למיטב זכרוני, זה לא פרט אמפירי, אלא מוכח על ידי משפטים [לגבי הטענות הקודמות בהודעה שלי - אני זוכר כמעט בוודאות שהן מוכחות על ידי משפטים]), כך שבכל מקרה, אתה לא לומד בוודאות מה הייתה ההודעה שהוצפנה, אלא יכול פשוט להבדיל בין שני פענוחים אפשריים בהסתברות הגדולה מחצי באופן לא-זניח (אך למטרות פרקטיות - שהינו פעמים רבות נמוך). דיסקליימר: 1. את המועד ב' בקורס בקריפטוגרפיה אני עושה ביום חמישי, ועוד לא הספקתי לעבור מחדש על החומר. 2. השעה כרגע ארבע לפנות בוקר. 3. שתיתי. |
 |
 |
 |
|
|
|
||
|
||||
|
זה נושא מעניין, אז אנסה להרחיב עליו, מהמעט שלמדתי: לא טריוויאלי להגדיר בטיחות של סכמת הצפנה - באותה סכמת הצפנה עשויה להשתמש בסיטואציות שונות (מצפינים אחת מתוך קבוצה קטנה של הודעות ידועות מראש [כן/לא, עכשיו/מחר], קבוצה גדולה [ספרים שכתובים באנגלית ושמורים בפורמט ידוע] או כל הודעה אפשרית?), בצורות שונות (שולחים עוד הודעות שמוצפנות באותו המפתח?), התוקף את ההצפנה עשוי להשתמש בכלים שונים (שהגדרת הבטיחות צריכה לקחת בחשבון את כולם, מבלי להניח מראש מה הם, לפני שהיא נותנת את חותמת הכשרות), וכן הלאה. הכי חשוב - מה נחשב לנפילה של סכמת ההצפנה? אם התוקף יודע שאותו המסר נשלח פעם שניה, האם זה כשלון? בסיטואציות מסויימות כן (למשל, אם ראינו שהמשחתת חזרה לנמל, סביר שזה גם מה שיקרה בפעם הבאה שתקבל את אותו המסר), באחרות לא (העותק של הארי פוטר נשלח לשני אנשים שונים בחברה המוציאה לאור? איך זה עוזר לי להתחיל להדפיס עותקים פיראטיים בסין?). וזו רק דוגמה אחת (אחרות: אורך ההודעה? היוניפורמיות של התוכן? שפת התוכן? האם התוכן הוא קידוד של תמונה כלשהי, טקסט באנגלית או קובץ וידאו? דמיון כלשהו להודעה קודמת [מתנהל משא ומתן על משכורת?]?). אז יש כמה מודלים בסיסיים שסכמת הצפנה עשויה להיות בטוחה עבורם או לא. ביניהם - הצפנה חד-פעמית, הצפנה רב-פעמית, הצפנה שבה לתוקף יש אפשרות, מבלי לדעת את המפתח, לבקש ולקבל הצפנה של מסר לבחירתו באמצעות אותו המפתח (מן הסתם יש כמה וריאנטים לכל אחד מאלה, אבל אני למדתי רק וריאנט אחד של כל אחד מאלה, והם נשמעו לי מוצלחים, אז אני מאמין שהם סטנדרטים שמקובלים על הרוב). בכדי להניח את המינימום האפשרי על צרכי התוקף ומה שמהווה עבורו שבירה של ההצפנה, מאמצים עמדה פסימית במיוחד - הצפנה חד-פעמית נחשבת כשבורה אם תוקף יכול לבחור שתי הודעות, ואז אחת מהן - הוא לא יודע איזו - מוצפנת, והוא מסוגל לנחש, בהנתן ההצפנה, איזו משתי ההודעות שלו הוצפנה. ההיגיון - אם אפילו כשהוא בוחר את ההודעות בעצמו, אף תוקף לא יכול להבחין, אז הרי שהסכימה טובה לכל הודעה תחת כל התקפה. כל מידע שהוא עשוי לרצות לשלוף מההודעה - שפת התוכן, מספר הפעמים שמופיעה האות ג' - אם אפשר היה לשלוף מהקובץ המוצפן, הרי שהוא יכל לבקש להצפין שתי הודעות שנבדלות בתכונה הזאת, ובאמצעות הדרך שכביכול יש לו לשליפת המידע הזה מהקובץ המוצפן, יכל היה להבחין איזו משתי ההודעות שבחר הוצפנה. אם נצליח להוכיח שאף תוקף (הגדרת התוקף מכילה בתוכה את זוג ההודעות שיבחר) לא מסוגל להבחין[*], הרי שהסכמה בטוחה. עכשיו, לגבי מה שאמרתי מקודם בקשר לכך שכל הצפנה ראויה לשמה מכילה אלמנט של אקראיות - המבחן לבטיחות של סכמת הצפנה שמתיימרת להיות בטוחה גם אם משתמשים בה, עם אותו המפתח, מספר פעמים, היא שהתוקף בוחר שני רצפים של הודעות, אחד מהרצפים מוצפן (כל הודעה ברצף מוצפנת בנפרד, אבל עם אותו המפתח) והצפנתו מוחזרת לתוקף, והוא אמור לנחש איזה משני הרצפים הוצפן. אם אין אלמנט של אקראיות, הרצה של אלגוריתם ההצפנה פעמיים על אותו הקלט תיתן את אותה התוצאה, ולכן התוקף יכול פשוט לתת רצף אחד שמורכב משתי הודעות שונות, ורצף שני שמורכב מאותו הודעה פעמיים, ובצורה זו להבחין איזה מהרצפים הוצפן - אם שתי ההודעות ברצף ההצפנה המוחזר לו זהות, זה השני, ואחרת, זה הראשון. באופן טריוויאלי, כל סכמת הצפנה שתהיה בטוחה להצפנות חוזרות ונשנות, חייבת להכיל אלמנט של אקראיות, כך שהצפנה כפולה של הודעה תיתן [בהסתברות גבוהה] תוצאות שונות (וכך, כמובן, לא ידע התוקף כשהודעה נשלחה פעמיים). (באופן דומה לגבי המודל השלישי - אם התוקף יכול לבחור מה להצפין, הוא יכול לבחור להצפין שוב את ההודעה הראשונה, ובמידה והיא זהה להצפנה שקיבל, זו ההודעה שלו שהוצפנה, ואחרת, זו השניה.) דוגמה לניסיון של ההגדרה להמנע מהנחות לגבי *יכולותיו* של התוקף - המודל השלישי שהזכרתי מדבר על תוקף שיש לו אפשרות לקבל הצפנה של הודעות לבחירתו. זה לא מצב סביר במיוחד, אבל זה מידול פסימי מאוד (ולכן מצויין) של יכולות שקשה מאוד למדל אחרת של תוקף בעולם האמיתי להשפיע על המתקשרים באופן מוצפן והמידע העובר ביניהם, ולהשתמש בכך לשם פיענוח התקשורת ביניהם. דוגמה דבילית משהו, אבל קצרה - אם יש לי את האפשרות להאט את התקשורת בין המתקשרים באופן מוצפן, אני עשוי לגרום למשפט "אני סובל מאיטיות בתקשורת" להתווסף לשיחה. איך נמדל השפעה שכזאת כשאנחנו מנסים להוכיח שסכמת הצפנה בטוחה? איך נתייחס לאינספור האפשרויות הנוספות? הכי פשוט ויעיל למדל את ההשפעה המירבית שיכולה להיות לתוקף - הוא קובע את *כל* מה שיאמר בהודעה אחת שמוצפנת עם אותו המפתח - ואם הסכמה בטוחה אפילו בפני זה, היא כמובן בטוחה בפני השפעות חלשות יותר, כמו העלאת הסיכוי שאומר משהו ספיציפי, ושימוש שלו במידע הזה להסקת המפתח. --- * היות ותמיד אפשר להטיל מטבע, ב"לא יכול לנחש איזו משתי ההודעות שבחר הוצפנה", הכוונה הייתה שלא יכול לעשות זאת עם הסתברות להצלחה גדולה מחצי (במקרה של סודיות מושלמת) או גדולה משמעותית מחצי (במקרה של סודיות חישובית - אותה אנסה להסביר רק אם מישהו רוצה). --- מי שהנושא מעניין אותו, יכול לקרוא יותר בספר הבא - http://www.amazon.com/Introduction-Cryptography-Chap... אני מקווה שהסברתי מעט מהנושא עם מינימום טעויות ובאופן סביר, ושהודעתי לא עושה שירות דוב למחברי הספר. |
|
|
|
|
|
|
||
|
||||
|
אין טעם להסתבך ולהתפלפל. בוא נהיה קונקרטיים: אם היו מוכיחים ש- RSA לא ב- BPP אבל כן ב- P/poly, האם היו ממשיכים להשתמש בו? | |
|
|
|
|
|
||
|
||||
|
למה לא? במה שונה עיבוד שדורש זמן לא-פולינומי לפני שההודעה אפילו נכתבה (ובטח שהוצפנה), מעיבוד שדורש זמן לא-פולינומי רק אחרי שהוצפנה ונשלחה? שני המקרים לא-סבירים כמעט באותה המידה (והאינטואיציה אומרת שיהיה יותר קל - סליחה, פחות קשה - לבצע דווקא את הראשון). חוץ מזה, כל עוד אין לך אלטרנטיבה שאיננה ב-P/Poly, צריך להשתמש במשהו, לא? |
|
|
|
|
|
|
||
|
||||
|
לא בהכרח - את העיבוד המקדים צריך לבצע רק פעם אחת, ואחר כך אפשר יהיה להשתמש בתוצאותיו הרבה פעמים, כך שמן הסתם אנו מתירים לו להיות כבד יותר (כך זה תמיד עם אפליקציות שמבוססות על עיבוד מוקדם). לדוגמה, נניח שיגלו שבהינתן פקטוריזציה של מספר פריק *כלשהו* בן 500 ספרות אפשר לפקטר *כל* מספר בן 500 ספרות (כן, מופרך, אבל זו דוגמה), אז ינבע מכך ש-RSA היא ב-P/poly, ואנשים ישמחו מאוד להפעיל את ה-Number field sieve בגרסה אולטרה ממוקבלת ברשת שתדרוש אולי חודש ריצה אבל תחסל את תקן ה-RSA הנוכחי (נניח שהוא בן 500 ספרות...). |
|
|
|
|
|
|
||
|
||||
|
לא בהכרח מה? אמרתי "סבירים כמעט באותה המידה" - למרות ה"כמעט" אתה לא מסכים? שים לב שאני מדבר על סבירות ההצלחה, ומוכן לצאת מנקודת ההנחה שמקדישים את כל מה שרק אפשר, בלי התחשבות בתועלת הצפויה. הרי בשני המקרים נדרשים משאבים שאנחנו אפילו לא יכולים להתקרב אליהם. אז מה זה משנה אם יש לנו נכונות להשקיע יותר ממה שממילא לא קרוב אפילו למספיק במכונה היותר כללית? "לדוגמה, נניח שיגלו שבהינתן פקטוריזציה של מספר פריק *כלשהו* בן 500 ספרות אפשר לפקטר *כל* מספר בן 500 ספרות (כן, מופרך, אבל זו דוגמה), אז ינבע מכך ש-RSA היא ב-P/poly" - במקרה הלא סביר הזה, למי בכלל אכפת מ-P/poly? הרי הבעיה כבר ב-BPP במקרה הזה, לא? את המשך אותה פסקה, דרך אגב, לא הבנתי. אולי גם לא את מה שלפני. |
|
|
|
|
|
|
||
|
||||
|
זהו, שניסיתי להמחיש עם הדוגמה שלא מדובר באותה "מידה" של סבירות. הנקודה המהותית היא שאם צריך למצוא "רמז" רק פעם אחת, אז למרות שההשקעה היא מטורללת אפשר להגיע אליה, בעוד שלהגיע לאותה רמת השקעה ב"יום יום" זה לא סביר. הבעיה לא בהכרח ב-BPP אם מתקיים מה שתיארתי. אתה עדיין צריך "רמז" בשביל כל גודל מספר, והחישוב של הרמז הוא עדיין קשה. |
|
|
|
|
|
|
||
|
||||
|
מפתיע אותי וכלל לא ברור לי למה אתה אומר על ההשקעה שאתה בעצמך הגדרת הרגע כמטורללת, בהנחה ששנינו חושבים על אותו סדר גודל, כ"אפשר להגיע אליה". על איזה רמז אתה מדבר? מה הבעיה למצוא את הפירוק של מספר כלשהו בן חמש-מאות ספרות (נגיד בינאריות)? פשוט מכפילים שני ראשוניים ששניהם בני 250 ספרות1, והרי לך מספר פריק בן 500 ספרות ופירוקו. --- 1 בערך. לא נתעכב על זה. |
|
|
|
|
|
|
||
|
||||
|
טוב, בטח התכוונת שקיים אחד ספיציפי כזה, אבל לא ידוע מי הוא. אז: 1. מאוד קשה לי לדמיין את זה (אבל כבר אמרת שגם לדעתך זו דוגמה מאוד מופרכת). 2. אני אניח שאתה מתכוון גם שלכל אורך, המספר הזה הוא שונה. אם אפשר למצוא את המספר הזה בזמן פולינומי, הרי שזו סדרה יוניפורמית (כמו שאמרת בעצמך לאלמוני), והבעיה ממילא ב-BPP. אם אי-אפשר בזמן פולינומי, החל מגודל מסוים, אי-אפשר לפני קץ היקום ובהסתברות ראויה לציון גם אם נשקיע את כל המשאבים שבעולם, אבל עדיין אפשרי לחבר'ה הישרים להשתמש בסכמה במשאבים סבירים (נו, כנראה. לא ידועים לי הקבועים של RSA, ואתה ממילא יכול להעביר את הדיון לכל סכמת הצפנה אחרת ונשאר עם אותו הפרנציפ), ואז מה אכפת לנו שיש גם את ההתקפה הלא-אפשרית הזאת על ההצפנה? אני חוזר על השאלה המקורית שלי - אם גם עם כל המשאבים שאפשר לדמיין אי-אפשר, מה זה משנה לי שיש גם נתיב התקפה שבו מישהו עשוי להיות יותר נכון להשקיע את המשאבים האלו? הם הרי עדיין לא מספיקים. |
|
|
|
|
|
|
||
|
||||
|
הכוונה הייתה שאפשר למצוא את המספר בזמן פולינומי, לא את הפירוק שלו. מאוד אכפת לנו שיש את ההתקפה הלא-אפשרית הזו על ההצפנה כי קיומה *מכריח* אותנו להגדיל את הקבועים שבהם אנחנו משתמשים. אם פתאום ניאלץ, במקום להשתמש ב-RSA של 2048 סיביות, להשתמש בכזה של 32768, זה מעיד על שינוי מהותי שההתקפה הלא-אפשרית גרמה. |
|
|
|
|
|
|
||
|
||||
|
סלח לי, לא הבנתי - להגדיל את הקבועים נאלצים מדי פעם, אבל מה הנקודה? | |
|
|
|
|
|
||
|
||||
|
כי אפשר, אם אתה לא עובד עם מחשב יחיד אלא עם עשרות אלפי מחשבים, ומוכן להשקיע פרק זמן שבדרך כלל היה נחשב בעינייך לא סביר. הרי בימינו *מצליחים* לפרק לגורמים מספרים, זה פשוט קשה. בקשר לפירוק - אה, כן, צודק, דוגמה גרועה. אבל זה הרעיון שחשוב. נסה לשחזר את הדוגמה שלי עם משהו שאי אפשר לייצר בקלות (או לחילופין, עם "צריך פירוק של מספר ספציפי שקל למצוא אותו אבל הפירוק שלו לא ידוע). |
|
|
|
|
|
|
||
|
||||
|
כל העניין בבעיות עם סיבוכיות לא-פולינומית, הוא שאפילו עם מיליארדי מחשבים, אי-אפשר לפתור מופעים גדולים מספיק שלהם. זה שמצליחים לפרק מספרים, אתה בוודאי יודע, זה ממש לא מרשים - אני יכול לפרק חלק בראש; גדולים יותר אפשר עם עשרות אלפי מחשבים; גדולים מספיק, במידה ובעיית הפירוק אכן לא פולינומית, אי-אפשר יהיה גם אם כל אטום בודד ביקום יהיה מעבד מרובה ליבות. אני בוודאי לא צריך להזכיר לך זאת, אבל לא יזיק שיופיע בפרוטוקול - גם עם בעיות ליניאריות, יש מופעים שאי-אפשר לפתור לפני מות היקום עם מיליארדי מחשבים. החלק המעניין, לצרכי קריפטוגרפיה, הוא שהשחקנים הישרים עדיין יכולים לפעול בזמן סביר, בעוד שלתוקף אין שום דרך מלבד זו הדורשת את המשאבים שאין, ולעולם לא יהיו, בנמצא. אני רוצה לחזור על הנקודה שלי, שנדמה לי (סלח לי) שהיא נכונה, פשוטה, ושחמקה ממך באופן מפתיע עד עכשיו (או שאתה מנסה לדבר על משהו אחר, ואני זה שמתבלבל) - יהי סט של בעיות שאפשר לפתור כל אחת מהן בנפרד, או את כולן ביחד. אתה אומר - יש יותר אינטרס לאנשים להשקיע בפתרון הכללי שפותר את כולן ביחד. אני אומר - כל עוד לא זה אפשרי ולא זה אפשרי - בכלל - מידת האינטרס לא משנה. בלתי-אפשרי נשאר בלתי-אפשרי גם אם עובדים בצוות. "נסה לשחזר את הדוגמה שלי עם משהו שאי אפשר לייצר בקלות" - עזור לי בבקשה. |
|
|
|
|
|
|
||
|
||||
|
העניין של "גדולים מספיק אי אפשר גם אם כל אטום ביקום יהיה מעבד מרובה ליבות" נכון, כמובן, גם לדברים עם סיבוכיות פולינומית, כך שאני מציע שתזנח לרגע את גישת ה"אם משהו הוא לא פולינומי, אין שום סיכוי לחשב אותו". הנקודה היא שיש סיכוי, עבור סט של ערכים שהם נמוכים מספיק. אנסה לחדד את הנקודה. אני מבדיל בין שלושה סוגי חישובים - כאלו שהם בלתי פיזיביליים בכלל, ועליהם לא מדברים; כאלו שהם קלים וכל מחשב ביתי עושה בצורה זריזה (לצורך הדיון, אלו הפולינומיים); וכאלו שהם "בינוניים" - במחשב ביתי זה ייקח יותר מדי זמן, אבל אם כל המחשבים בעולם יתאגדו וישתפו פעולה, ויחכו חודש חודשיים, החישוב יסתיים. עכשיו, בוודאי שיש הבדל מהותי בין הסיטואציה שבה בכל פעם שרוצים לפרוץ הודעה צריך לבצע חישוב "בינוני" שכזה, ובין הסיטואציה שבה מספיק שכל העולם יבצע פעם אחת את החישוב ה"בינוני" ואז כל אחד יוכל לפרוץ בקלות הודעות קצרות מספיק. המשמעות של זה פשוטה, והיא זו שניסיתי להסביר בהודעה האחרת שאליה הגבת - אם בעיה כלשהי היא כרגע בטווח ה"בינוני", אז למרות שהאלגוריתם שפותר אותה הוא אקספוננציאלי ואפשר להפוך אותה לבלתי אפשרית על ידי הגדלת פרמטר הבטיחות של ההצפנה, בכל זאת היא תגרום לנו לעשות משהו מעשי מאוד - להגדיל את פרמטר הבטיחות של ההצפנה, אולי בצורה לא טריוויאלית, בטח בקפיצה שלה לא ציפינו. הסיבה שבגללה פרמטר הבטיחות גדל בדרך כלל היא שהפתרון הנאיבי (שגם הוא לא פיזיבילי בהינתן פרמטר גדול מספיק) מתחיל להיות מאיים - ולכן גם אלגוריתמים לא יעילים אחרים מסוגלים להיות מאיימים. |
|
|
|
|
|
|
||
|
||||
|
(אמרתי בעצמי שגם לליניארי זה נכון עבור ערכים מסויימים. הסברתי למה עבור ליניאריים זה לא מעניין, ועבור לא-פולינומיים כן - כי השחקנים הישרים נשארים בזמן סביר.) "הנקודה היא שיש סיכוי, עבור סט של ערכים שהם נמוכים מספיק." - זו לא נקודה מעניינת, כי, לאור הפסקה הקודמת שלי, אין שום סיבה שלא לבחור בהצפנה דווקא את סט הערכים שאינם נמוכים מספיק. (כלומר, יש יתרונות לכך - הצפנה בשניות במקום בשעות - אבל זה לא מחויב המציאות. במידת הצורך, יהיה אפשר לעשות את ההקרבה הזאת, ולהשיג שוב סודיות טובה, במחיר הנוחות של הצפנה כמעט-מיידית.) -- כלומר, הנקודה שלך לאורך הדיון הייתה שיש תרחישים שבהם התקדמות אלגוריתמית דורשת הגדלה של קבוע הבטיחות הנפוץ בהצפנה? מן הסתם אני מסכים. |
|
|
|
|
|
|
||
|
||||
|
בדיוק. אם בגלל איזו תגלית תיאורטית שמעידה על תוצאה ''בלתי אפשרית'' לכאורה גורמת לצורך להצפין בשעות במקום בשניות - כנראה שבכל זאת מדובר במשהו בעל השלכות מעשיות. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |