הצפנת בלום-גולדווסר

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

סכימת בלום-גולדווסר (Blum-Goldwasser) היא סכימת הצפנה אסימטרית הסתברותית שהוצעה על ידי מנואל בלום ושפי גולדווסר ב-1984. היא היעילה מבין סכימות ההצפנה ההסתברויות הידועות ויעילה יותר בהשוואה ל-RSA מהיבט של מהירות והתנפחות הצופן וכן נחשבת לבטוחה סמנטית בהנחה שבעיית פירוק לגורמים של מספר שלם קשה לפתרון. סכימת בלום גולדווסר מנצלת את רעיון המחולל הפסבדו אקראי Blum-Blum-Shub (ידוע גם בשם BBS), כדי ליצור רצף סיביות פסבדו אקראי, המשמש לאחר מכן לחיבור ב-XOR עם המסר בדומה לפנקס חד פעמי. התוצאה ביחד עם הגרעין ההתחלתי כשהוא מוצפן מועברים למקבל שמשתמש במידע הסודי המצוי ברשותו הנקרא דלת צונחת (Trapdoor), כדי לחלץ את הגרעין ההתחלתי שהוזן למחולל ומשם הדרך לשחזור המסר קלה. אפשר לראות בשיטה זו מעין שילוב של צופן זרם עם מפתח פומבי. בדומה להצפנת רבין, הצפנת בלום-גולדווסר פגיעה להתקפת טקסט מוצפן נבחר ומסיבה זו לא זכתה לתשומת לב רבה מבחינה מעשית.

אלגוריתם הכנת מפתח עבור הצפנת בלום-גולדווסר[עריכת קוד מקור | עריכה]

  1. בוחרים שני שלמים ראשוניים גדולים \ p ו-\ q השקולים ל-\ 3 מודולו \ 4.
  2. מחשבים את \ n=pq
  3. בעזרת אלגוריתם אוקלידס המורחב מוצאים שלמים \ a ו-\ b המקיימים את \ ap+bq=1.
  4. המפתח הפומבי הוא \ n והמפתח הפרטי הוא \ (p,q,a,b).

תהליך הצפנת בלום-גולדווסר[עריכת קוד מקור | עריכה]

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

להצפנת המסר \ m המצפין משיג לידיו עותק של המפתח הפומבי ופועל כדלהלן:

  1. מחלק את המסר ל-\ t לגושים, כל אחד בגודל \ h סיביות, כאשר \ h=\mbox{lg lg }nלוגריתם בבסיס 2 של מספר סיביות המודולוס בקירוב).
  2. בוחר גרעין אקראי סודי \ x_0, שהוא שארית ריבועית מודולו \ n (אפשר להשיג זאת על ידי בחירת שלם אקראי \ r\in\mathbb{Z}^*_n וחישוב \ x_0=r^2\mbox{ mod }n).
  3. ההצפנה מבוצעת באופן רקורסיבי ב-\ t סבבים כאשר בכל סבב: א. הוא מחשב את \ x_i=x^2_{i-1}\mbox{ mod }n, ב. מצפין את גוש המסר \ m_i כדלהלן: \ c_i=p_i\oplus m_i, כאשר ערכו של \ p_i הוא \ h הסיביות הנמוכות של \ x_i.
  4. מחשב את \ x_{t+1}=x^2_t\mbox{ mod }n.
  5. הטקסט המוצפן הוא \ (c_1,c_2,...,c_t,x_{t+1}).

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

  1. המקבל משתמש במפתח הפרטי שבידיו כדי לחשב את \ d_1=((p+1)/4)^{t+1}\mbox{ mod }(p-1)
  2. ואת \ d_2=((q+1)/4)^{t+1}\mbox{ mod }(q-1)
  3. ואז מחשב את \ u=x^{d_1}_{t+1}\mbox{ mod }p
  4. ואת \ v=x^{d_2}_{t+1}\mbox{ mod }q
  5. ואז מחלץ את הגרעין ההתחלתי \ x_0=vap+ubq\mbox{ mod }n.
  6. הוא מפענח את המסר באותה הדרך בה הוצפן, עבור כל גוש מוצפן \ c_i מחשב את \ x_i=x^2_{t-1}\mbox{ mod }n ואז משתמש ב-\ h הסיביות הנמוכות כדי לחבר ב-XOR עם גוש הטקסט המוצפן: \ m_i=p_i\oplus c_i כדי לקבל את \ m_i.

הוכחה לנכונות האלגוריתם[עריכת קוד מקור | עריכה]

ראשית ממשפט השאריות הסיני נובע, היות ש-\ x_t הוא שארית ריבועית מודולו \ n, הוא שארית ריבועית מודולו הגורמים הראשוניים של \ n. ולפי תכונות סימן לז'נדר \ x^{(p-1)/2}_t\equiv 1\ (\mbox{mod }p).

שנית, ניתן לראות ש-

\ x^{(p+1)/4}_t\equiv (x^2_t)^{(p+1)/4}\equiv x^{(p+1)/2}_t\equiv x^{(p-1)/2}_t x_t\equiv x_t\mbox{ mod }p

באופן דומה \ x^{(p+1)/4}_t\equiv x_{t-1}\ (\mbox{mod }p) וכן \ x^{((p+1)/4)^2}_{t+1}\equiv x_{t-1}\ (\mbox{mod }p) וכן הלאה.

מזה נובע ש:

\ u\equiv x^{d_1}_{t+1}\equiv x^{((p+1)/4)^{t+1}}_{t+1}\equiv x_0\ (\mbox{mod }p)

וגם \ v\equiv x^{d_2}_{t+1}\equiv x_0\ (\mbox{mod }q)

ולבסוף כיוון ש-\ ap+bq=1 לכן \ vap+ubq\equiv x_0\ (\mbox{mod }p) כנ"ל לגבי \ q. לכן אם מחשבים את \ vap+ubq\mbox{ mod }n מתקבל הגרעין ההתחלתי \ x_0. אם הגרעין ההתחלתי ידוע הפענוח טריוויאלי, כיון שכל מה שנדרש הוא פעולת XOR חוזרת על הטקסט המוצפן בדיוק כפי שנעשה עם המקור.

דוגמה להמחשה[עריכת קוד מקור | עריכה]

לצורך הכנת מפתחות המקבל בוחר ראשוניים מתאימים נניח \ p=643 ו-\ q=859 ומחשב את \ n=pq=552337 ואז מחשב את משוואת אוקלידס \ 171\cdot 643+-128\cdot 859=1 כך ש-\ a=171,b=-128. המפתח הפומבי הוא אם כן \ 552337 והמפתח הפרטי הוא \ (643,859,171,-128).

כעת אם השולח מעוניין להצפין את המסר \ m=\mbox{9C5B82} (בייצוג הקסדצימלי, בסה"כ 24 סיביות). הוא מחשב תחילה את \ \left\lfloor\log_2(552337)\right\rfloor=19 ואז \ h=\left\lfloor\log_2(19)\right\rfloor=4 ואז מחלק את סיביות המסר לשישה גושים בני ארבע סיביות כל אחד ומתקבל:

\ m_1=1001,m_2=1100,m_3=0101,m_4=1011,m_5=1000,m_6=0010

כעת בוחר גרעין התחלתי אקראי, נניח \ x=201036 (שהוא \ 21403^2\mbox{ mod }552337). הצפנת המסר \ m מוצגת בטבלה הבאה, כאשר \ p_i מייצג את ארבע הסיביות הנמוכות של \ x_i, בכל שלב לאחר העלאת \ x_i בריבוע מחשבים את \ c_i=p_i\oplus m_i:

\ i \ x_i=x^2_{i-1}\mbox{ mod }n \ m_i בסיביות \ p_i בסיביות \ c_i בסיביות
1 \ 422669 \ 1001=9 \ 1101=\mbox{D} \ 0100=4
2 \ 99607 \ 1100=\mbox{C} \ 0111=7 \ 1011=\mbox{B}
3 \ 477255 \ 0101=5 \ 0111=7 \ 0010=2
4 \ 155302 \ 1011=\mbox{B} \ 0110=6 \ 1101=\mbox{D}
5 \ 363762 \ 1000=8 \ 0010=2 \ 1010=\mbox{A}
6 \ 522228 \ 0010=2 \ 0100=4 \ 0110=6
לסיום מחשב גם את \ x_7=166864 ואת הטקסט המוצפן \ (c=\mbox{4B2DA6},x_7=166864) הוא שולח למקבל.

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

\ d_1=(644/4)^7\mbox{ mod }642=479 ואת
\ d_2=(860/4)^7\mbox{ mod }858=305 ואז
\ v=166864^{305}\mbox{ mod }859=30 וכן
\ u=166864^{479}\mbox{ mod }643=420

ואז משחזר את הגרעין ההתחלתי כך: \ x_0=30\cdot 171\cdot 643+420\cdot-128\cdot859\mbox{ mod }552337(=-351301)=201036. בעזרת הגרעין ההתחלתי הוא משחזר את הרצף הפסבדו אקראי, בדיוק כפי שעשה זאת המצפין ומכאן שחזור המסר קל כיוון ש- \ m_i=c_i\oplus p_i לכן \ m=\mbox{4B2DA6}\oplus \mbox{D77624}=\mbox{9C5B82}.

בטיחות ויעילות[עריכת קוד מקור | עריכה]

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

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

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

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

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

מספר בלום; המודולוס בשיטת בלום גולדווסר נקרא מספר בלום, ההגדרה של מספר בלום היא: שלם פריק שהוא כפולה של שני ראשוניים שונים השקולים ל-3 מודולו 4. כלומר \ p\equiv3\ (\mbox{mod }4) אם קיים שלם \ t כלשהו המקיים \ p=4t+3. למעשה אלגוריתם בלום גולדווסר מיישם גרסה מובנית של המחולל הפסבדו האקראי BBS כאשר הסיביות הנמוכות של השארית הריבועית \ x_i=x^2_{i-1}\mbox{ mod }n בכל סבב, משלימות את הרצף הפסבדו אקראי לצורך הצפנת המסר. השארית הריבועית האחרונה \ x_{t+1}=x^2_t\mbox{ mod }n נשלחת באופן גלוי כאמור אל המקבל לצורך שחזור הגרעין ההתחלתי. בהנחה שפירוק לגורמים היא בעיה קשה, ניתן להוכיח כי \ h הסיביות הנמוכות של \ x_t בטוחות סימולטנית, כלומר אין דרך יעילה לחשב אותם מלבד ניחוש, מה שאומר שהמחולל נחשב לבטוח (כל עוד פירוק לגורמים היא בעיה קשה). כמובן הגדרה זו מוגבלת לבטיחות חישובית בלבד.

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

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

הצפנת בלום גולדווסר יעילה מאוד מבחינה חישובית כיוון שהטקסט המוצפן המתקבל אינו גדול משמעותית מטקסט המקור, אלא במספר קבוע של סיביות (כגודל השלם \ x_{t+1} בסיביות). תהליך ההצפנה יעיל למדי ודורש רק הכפלה מודולרית (מודולו \ n) אחת כדי להצפין \ h סיביות, כלומר עבור מודולוס בגודל \ k סיביות ומסר בגודל \ l סיביות תהליך ההצפנה לוקח \ O(\frac{lk^2}{\mbox{log}\ k}) פעולות בסיסיות. לעומת RSA למשל שדורשת העלאה בחזקה מודולרית מלאה במידה והמעריך נבחר אקראית. ללא אופטימיזציה העלאה בחזקה מודולרית מלאה דורשת בממוצע \ 3k/2 פעולות כפל מודולריות כאשר \ k שווה ללוגריתם בבסיס 2 של המודולוס. כמו כן תהליך הפענוח של אלגוריתם בלום גולדווסר דורש (בנוסף בשלב ההכנה) רק שלוש העלאות בחזקה מודולריות ללא תלות באורך המסר, יתר הפעולות דומות להצפנה, כלומר בסה"כ \ O(k^3)+O(\frac{lk^2}{\mbox{log}\ k}). מה שאומר שעבור מסרים גדולים, שיטת בלום גולדווסר יעילה יותר מ-RSA.

קישורים חיצוניים[עריכת קוד מקור | עריכה]