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

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

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

בוחרים שני שלמים ראשוניים גדולים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ q} השקולים ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 3} מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 4} .
מחשבים את $\ n=pq$
בעזרת אלגוריתם אוקלידס המורחב מוצאים שלמים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ b} המקיימים את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ ap+bq=1} .
המפתח הפומבי הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} והמפתח הפרטי הוא $\ (p,q,a,b)$ .

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

הצפנה

להצפנת המסר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m} המצפין משיג לידיו עותק של המפתח הפומבי ופועל כדלהלן:

מחלק את המסר ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t} לבלוקים, כל אחד בגודל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ h} סיביות, כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ h=\mbox{lg lg }n} (הלוגריתם בבסיס 2 של מספר סיביות המודולוס בקירוב).
בוחר גרעין אקראי סודי $\ x_{0}$ , שהוא שארית ריבועית מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} (אפשר להשיג זאת על ידי בחירת שלם אקראי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r\in\mathbb{Z}^*_n} וחישוב הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x_0=r^2\mbox{ mod }n} ).
ההצפנה מבוצעת באופן רקורסיבי ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t} סבבים כאשר בכל סבב: א. הוא מחשב את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x_i=x^2_{i-1}\mbox{ mod }n} , ב. מצפין את בלוק המסר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m_i} כדלהלן: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ c_i=p_i\oplus m_i} , כאשר ערכו של $\ p_{i}$ הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ h} הסיביות הנמוכות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x_i} .
מחשב את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x_{t+1}=x^2_t\mbox{ mod }n} .
הטקסט המוצפן הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (c_1,c_2,...,c_t,x_{t+1})} .

פענוח

המקבל משתמש במפתח הפרטי שבידיו כדי לחשב את $\ d_{1}=((p+1)/4)^{t+1}{\mbox{ mod }}(p-1)$
ואת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ d_2=((q+1)/4)^{t+1}\mbox{ mod }(q-1)}
ואז מחשב את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ u=x^{d_1}_{t+1}\mbox{ mod }p}
ואת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v=x^{d_2}_{t+1}\mbox{ mod }q}
ואז מחלץ את הגרעין ההתחלתי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x_0=vap+ubq\mbox{ mod }n} .
הוא מפענח את המסר באותה הדרך בה הוצפן, עבור כל בלוק מוצפן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ c_i} מחשב את הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle \ x_{i}=x_{t-1}^{2}{\mbox{ mod }}n} ואז משתמש ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ h} הסיביות הנמוכות כדי לחבר ב-XOR עם בלוק הטקסט המוצפן: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m_i=p_i\oplus c_i} כדי לקבל את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m_i} .

הוכחה לנכונות האלגוריתם

ראשית ממשפט השאריות הסיני נובע, היות ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x_t} הוא שארית ריבועית מודולו $\ n$ , הוא שארית ריבועית מודולו הגורמים הראשוניים של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} . ולפי תכונות סימן לז'נדר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x^{(p-1)/2}_t\equiv 1\ (\mbox{mod }p)} .

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 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}

באופן דומה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x^{(p+1)/4}_t\equiv x_{t-1}\ (\mbox{mod }p)} וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x^{((p+1)/4)^2}_{t+1}\equiv x_{t-1}\ (\mbox{mod }p)} וכן הלאה.

מזה נובע ש:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ u\equiv x^{d_1}_{t+1}\equiv x^{((p+1)/4)^{t+1}}_{t+1}\equiv x_0\ (\mbox{mod }p)}

וגם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v\equiv x^{d_2}_{t+1}\equiv x_0\ (\mbox{mod }q)}

ולבסוף כיוון ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ ap+bq=1} לכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ vap+ubq\equiv x_0\ (\mbox{mod }p)} כנ"ל לגבי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ q} . לכן אם מחשבים את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ vap+ubq\mbox{ mod }n} מתקבל הגרעין ההתחלתי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x_0} . אם הגרעין ההתחלתי ידוע הפענוח טריוויאלי, כיון שכל מה שנדרש הוא פעולת XOR חוזרת על הטקסט המוצפן בדיוק כפי שנעשה עם המקור.

דוגמה להמחשה

לצורך הכנת מפתחות המקבל בוחר ראשוניים מתאימים נניח הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p=643} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ q=859} ומחשב את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n=pq=552337} ואז מחשב את משוואת אוקלידס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 171\cdot 643+-128\cdot 859=1} כך ש- $\ a=171,b=-128$ . המפתח הפומבי הוא אם כן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 552337} והמפתח הפרטי הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (643,859,171,-128)} .

כעת אם השולח מעוניין להצפין את המסר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m=\mbox{9C5B82}} (בייצוג הקסדצימלי, בסה"כ 24 סיביות). הוא מחשב תחילה את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \left\lfloor\log_2(552337)\right\rfloor=19} ואז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ h=\left\lfloor\log_2(19)\right\rfloor=4} ואז מחלק את סיביות המסר לשישה בלוקים בני ארבע סיביות כל אחד ומתקבל:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m_1=1001,m_2=1100,m_3=0101,m_4=1011,m_5=1000,m_6=0010}

כעת בוחר גרעין התחלתי אקראי, נניח הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x=201036} (שהוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 21403^2\mbox{ mod }552337} ). הצפנת המסר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m} מוצגת בטבלה הבאה, כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p_i} מייצג את ארבע הסיביות הנמוכות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x_i} , בכל שלב לאחר העלאת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x_i} בריבוע מחשבים את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ c_i=p_i\oplus m_i} :


הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ i}	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x_i=x^2_{i-1}\mbox{ mod }n}	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m_i} בסיביות	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p_i} בסיביות	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ c_i} בסיביות
1	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 422669}	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 1001=9}	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 1101=\mbox{D}}	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 0100=4}
2	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 99607}	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 1100=\mbox{C}}	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 0111=7}	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 1011=\mbox{B}}
3	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 477255}	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 0101=5}	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 0111=7}	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 0010=2}
4	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 155302}	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 1011=\mbox{B}}	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 0110=6}	$\ 1101={\mbox{D}}$
5	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 363762}	$\ 1000=8$	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 0010=2}	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 1010=\mbox{A}}
6	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 522228}	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 0010=2}	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 0100=4}	הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 0110=6}

לסיום מחשב גם את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x_7=166864} ואת הטקסט המוצפן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (c=\mbox{4B2DA6},x_7=166864)} הוא שולח למקבל.

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ d_1=(644/4)^7\mbox{ mod }642=479} ואת

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ d_2=(860/4)^7\mbox{ mod }858=305} ואז

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v=166864^{305}\mbox{ mod }859=30} וכן

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ u=166864^{479}\mbox{ mod }643=420}

ואז משחזר את הגרעין ההתחלתי כך: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x_0=30\cdot 171\cdot 643+420\cdot-128\cdot859\mbox{ mod }552337(=-351301)=201036} . בעזרת הגרעין ההתחלתי הוא משחזר את הרצף הפסאודו אקראי, בדיוק כפי שעשה זאת המצפין ומכאן שחזור המסר קל כיוון ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m_i=c_i\oplus p_i} לכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m=\mbox{4B2DA6}\oplus \mbox{D77624}=\mbox{9C5B82}} .

ביטחון ויעילות

ערך מורחב – ביטחון סמנטי

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

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

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

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

מספר בלום; המודולוס ייקרא מספר בלום אם הוא שלם פריק שהוא כפולה של שני ראשוניים שונים השקולים ל-3 מודולו 4. כלומר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p\equiv3\ (\mbox{mod }4)} אם קיים שלם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t} כלשהו המקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p=4t+3} . אלגוריתם בלום גולדווסר מיישם גרסה מובנית של המחולל הפסאודו האקראי BBS כאשר הסיביות הנמוכות של השארית הריבועית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x_i=x^2_{i-1}\mbox{ mod }n} בכל סבב, משלימות את הרצף הפסאודו אקראי לצורך הצפנת המסר. השארית הריבועית האחרונה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x_{t+1}=x^2_t\mbox{ mod }n} נשלחת באופן גלוי כאמור אל המקבל לצורך שחזור הגרעין ההתחלתי. בהנחה שפירוק לגורמים היא בעיה קשה, ניתן להוכיח כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ h} הסיביות הנמוכות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x_t} בטוחות סימולטנית, כלומר אין דרך יעילה לחשב אותם מלבד ניחוש, מה שאומר שהמחולל נחשב לבטוח (כל עוד פירוק לגורמים היא בעיה קשה). כמובן הגדרה זו מוגבלת לביטחון חישובי בלבד.

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

הצפנת בלום גולדווסר יעילה מבחינה חישובית כיוון שהטקסט המוצפן המתקבל אינו גדול משמעותית מטקסט המקור, אלא במספר קבוע של סיביות (כגודל השלם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x_{t+1}} בסיביות). תהליך ההצפנה יעיל ודורש רק הכפלה מודולרית (מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} ) אחת כדי להצפין הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ h} סיביות, כלומר עבור מודולוס בגודל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k} סיביות ומסר בגודל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ l} סיביות תהליך ההצפנה לוקח הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(\frac{lk^2}{\mbox{log}\ k})} פעולות בסיסיות. לעומת RSA למשל שדורשת העלאה בחזקה מודולרית מלאה במידה והמעריך נבחר אקראית. ללא אופטימיזציה העלאה בחזקה מודולרית מלאה דורשת בממוצע הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 3k/2} פעולות כפל מודולריות כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k} שווה ללוגריתם בבסיס 2 של המודולוס. כמו כן תהליך הפענוח של אלגוריתם בלום גולדווסר דורש (בנוסף בשלב ההכנה) רק שלוש העלאות בחזקה מודולריות ללא תלות באורך המסר, יתר הפעולות דומות להצפנה, כלומר בסה"כ הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(k^3)+O(\frac{lk^2}{\mbox{log}\ k})} . מה שאומר שעבור מסרים גדולים, שיטת בלום גולדווסר יעילה יותר מ-RSA.

ראו גם

הצפנת פייליר

קישורים חיצוניים

הספר Handbook of Applied Cryptography.
המאמר של מנואל בלום ושפי גולדווסר an efficient Probabilistic Public-Key Encryption Scheme which hides all partial information 1984.

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0