סיבוכיות האלגוריתם המתואר היא formula_43. על כן הדרך העדיפה היא לבחור מספרים ראשוניים בעלי מבנה ייחודי המקל על חישוב השורש הריבועי, כפי שמובא במאמר של רבין. אם formula_9 מקיים formula_45 כלומר formula_46 כנ"ל לגבי formula_10, חישוב השורשים הריבועיים יהיה קל יותר באופן משמעותי, כדלהלן:
התוצאה היא: formula_55 ו-formula_56 (מודולו formula_1).
שימו לב שבידיעת formula_58 ו-formula_59 אפשר לפרק את formula_8 לגורמים כמו שציין רבין, כי formula_61 שווה לאחד הגורמים של formula_8.
דוגמה.
נבחר את הראשוניים formula_63, (שניהם שקולים ל-formula_64 מודולו formula_65, במילים אחרות formula_66 וכן formula_67). אז formula_68, כך שהמפתח הפרטי של אליס הוא formula_69, והמפתח הפומבי הוא formula_70. (את הגורמים של 47897 אפשר למצוא בזמן קצר, אבל דוגמה זו ממחישה את עיקרי השיטה).
בוב מעוניין להצפין את המסר formula_71 עבור אליס (למען הפשטות, נניח שהוא בוחר לבנות את המסר כמתואר להלן, כלומר משרשר את המסר פעמיים formula_72), כדי להצפין את המסר הוא מחשב את formula_73 ושולח את formula_74 לאליס.
כאשר אליס מקבלת את formula_75 היא מחשבת את השורשים הריבועיים שלו כדלהלן:
אמנם אליס אינה יכולה לדעת מה שלח בוב אולם מהתבוננות בערכים שהתקבלו, קל לראות כי formula_85 נראה שונה מהיתר, בכך שהוא מורכב מערך שחוזר על עצמו פעמיים, משמע זהו הפתרון הנכון, על כן formula_86.
ביטחון.
המשימה של תוקף פוטנציאלי, קרי שחזור formula_14 מתוך הטקסט המוצפן formula_75 היא בעיה קשה. למעשה בעיה זו נקראת בעיית שורש ריבועי מודולו שלם פריק. הבעיה הכללית מוגדרת כדלהלן:
היכולת להוציא שורש ריבועי מודולו formula_8 שקולה חישובית ליכולת לפרק את formula_8 לגורמים. על כן, כל עוד בעיית פירוק לגורמים נותרת בעיה קשה, שיטת רבין תהיה בטוחה, בתנאי שהמודולוס הוא מספר גדול (כ-2,000 סיביות לפחות) כלומר מעבר ליכולת לפרקו לגורמים בזמן סביר.
אם נסמן formula_96 (מודולו formula_8) הוא 'שארית ריבועית'. משפט רבין אומר שאם אפשר למצוא שורש ריבועי של formula_7 עבור 1% מכל השאריות הריבועיות ב-formula_99 אזי אפשר לפרק לגורמים את formula_8 בזמן פולינומי. ההוכחה היא, נניח שנתונה קופסה שחורה formula_101 כך כאשר מזינים קלט formula_7 מחזירה את השורש הריבועי שלו באחוז אחד מהמקרים, אזי אפשר לבצע את הניסוי הבא: בוחרים formula_103 אקראי כלשהו ב-formula_104 ומזינים ל-formula_101 את formula_106 (מודולו formula_8) אם התוצאה אינה formula_103 או formula_109 אזי אפשר לפרק את formula_8 בגלל העובדה שאם נתונים formula_111 כך שמתקיים formula_112 אך formula_113 (מודולו formula_8) אזי formula_115 הוא גורם ראשוני לא טריוויאלי של formula_8. Gcd היא מחלק משותף מקסימלי. מספר הניסיונות הממוצע הוא 2, היות שכמחצית מהאלמנטים ב-formula_104 הם שורשים ריבועיים, מכאן שהסיכויים לפרק את formula_8 הם 50%. לכן מספיק יהיה להוכיח שאפשר לפרוץ את הצפנת רבין רק ב-1% סיכויי הצלחה כדי לפרק את formula_8 לגורמים ומכאן שאם פירוק לגורמים היא בעיה קשה, הצפנת רבין תהיה קשה גם היא.
ההוכחה נכונה רק אם האלמנטים נבחרו באקראי. כלומר רק אם המסר שהוצפן נבחר באקראי בהסתברות שווה מתוך כל המסרים האפשריים. במציאות מסרים אינם לגמרי אקראיים, אם המסר הוא בעל יתירות מסוימת או מבנה מיוחד ייתכן שיהיה אפשר לנחש חלק ממנו או לקבל מידע מסוים לגביו למרות שחישוב שורש ריבועי מודולו formula_8 היא בעיה קשה. למשל אפשר לנחש את הסיבית הנמוכה ביותר (LSB) באמצעות סימן יעקובי. לכן מעצם ההגדרה הצפנת רבין אינה בטוחה סמנטית.
שיטת רבין מוכחת כבטוחה רק כנגד יריב פסיבי, אך פגיעה להתקפה אקטיבית שנקראת התקפת מוצפן-נבחר (שבה היריב מסוגל לבחור את הטקסט אותו הוא מעוניין להצפין). בהתקפה כזו היריב יכול לחשוף את הגורמים הראשוניים של formula_1 כדלהלן: היריב בוחר formula_14 אקראי כלשהו מחשב את formula_15 ואז מבקש מהמקבל לפענח עבורו את formula_75. מכיוון שהמקבל לא מכיר את formula_14 שנבחר על ידי התוקף יש סיכוי שהתוצאה שתוחזר לא תהיה formula_14 אלא אחת מהתוצאות האחרות האפשריות אם נקרא לתוצאה שהוחזרה formula_85 כאשר formula_128 אזי formula_129 הוא אחד הגורמים של formula_1 (הפונקציה gcd מייצגת מחלק משותף מרבי). בסוג כזה של התקפה מניחים כי התוקף מסוגל לדרוש מהצד המפענח (למשל שרת) לפענח עבורו כל מסר שידרוש.
צופן רבין חשוף כמובן לאותן התקפות היעילות כנגד RSA. ניתן למנוע התקפות אילו על ידי בניית המסר באופן בטוח. השיטות הידועות לבניית מסרים (כמו OAEP) הנהוגות ב-RSA מתאימות גם להצפנת רבין.
יתירות.
החסרון העיקרי של הצפנת רבין הוא בעובדה שתוצאת ההצפנה היא אחת מארבע אפשרויות (פתרונות שורש ריבועי מודולו formula_1), הבעיה היא לזהות איזו מהן היא הנכונה. ניתן בקלות להתגבר על מכשלה זו על ידי הוספת יתירות מסוימת למסר המקורי לפני ההצפנה. לדוגמה אם המסר המיועד להצפנה הוא מהצורה formula_132 (|| מסמל שרשור) רוב הסיכויים שרק אחד מארבעת הפתרונות האפשריים יהיה בעל מבנה זה ועל כן ניתן יהיה לזהותו בקלות. שיטה זו תמנע את ההתקפות המתוארות. למשל אם התוקף יבקש לפענח את השורש הריבועי של formula_133 שהוא עצמו הכין עם היתירות האמורה. המערכת תחזיר עבורו את formula_14 עצמו, עובדה שאין בה כל מידע חדש שעשוי לסייע לו בהתקפה. אולם יש לשים לב כי בשיטה זו ההוכחה כי הצפנת רבין שקולה לפירוק לגורמים לא תהיה תקפה.
עוצבת נתיבי האש
השיטה הסוקרטית
השיטה הסוקרטית, או ויכוח סוקרטי, היא שיטת מחקר דיאלקטית, המיושמת בעיקר לבחינת מושגי יסוד במוסר ואשר תוארה לראשונה על ידי אפלטון בדיאלוגים הסוקרטיים. מסיבה זו סוקרטס, שאפלטון שם בפיו תפקיד מרכזי בדיאלוגים, נחשב לרוב כאביה של השיטה וכמייסדה בתחום הפילוסופיה של המוסר בעולם המערבי.
השיטה הדיאלקטית היא שיטה למחקר פילוסופי שבה משתתפים בדרך כלל שני דוברים, האחד מנחה את השיחה והשני שוקל הנחות מסוימות המונחות לפניו לצורך קבלתן או דחייתן. השיטה מיוחסת לסוקרטס, אשר החל לנהל שיחות מעין אלה עם בני עירו האתונאים, לאחר שביקר אצל האורקל מדלפי.
"דיאלוג סוקרטי יכול להתרחש בין שני אנשים כל אימת שהם חפצים לענות על שאלה [באשר לנושא כלשהו] אשר ניתנת למענה אך ורק על יסוד כוח המחשבה והתבוננות, שבו מתחילים מאמיתות מוצקות ושואלים מגוון שאלות עד אשר הפרטים שבדוגמה מתבררים ומהווים בסיס ליצירת הכללה."
הדיאלוג מורכב מסדרת שאלות סביב נושא מרכזי ומתן מענה על ידי בן השיח. הדיאלוג בדרך כלל מאופיין בעימות בין שתי נקודות השקפה. הדרך הטובה ביותר "לנצח" בעימות היא להביא את היריב לידי סתירה עצמית בדרך המוכיחה את טענתו של מי ששואל את השאלות.
בכתבי אפלטון מופיע בדרך כלל סוקרטס כבן השיח החקרן, השואל שאלות, ומנגד מופיעה דמות ידועה כזו או אחרת מבני אתונה. המונח "בחינה סוקרטית" בא לתאר מצב שבו השאלה המקורית נענית בתשובה המתייחסת לשאלה כאילו היא הייתה התשובה. תגובה זו מאלצת את השואל לנסח שאלה חדשה לאור ההתקדמות בדו-שיח.
השיטה.
אִלֵּנְכוֹס (מיוונית: ἔλεγχος, חקירת שתי וערב לצורך דחיית עמדה) היא הכלי המרכזי של השיטה הסוקרטית. בדיאלוגים המוקדמים של אפלטון, אלנכוס היא השיטה שבה משתמש סוקרטס כדי לחקור את הגדרתם של מונחי יסוד כגון צדק, או מידה טובה. על פי הפילוסוף בן זמננו ולאסטוס השיטה עוקבת אחר הצעדים הבאים:
בחינה אלנכטית אחת עשויה להוביל לבחינה חדשה, מדוקדקת יותר, של המונח הנמצא במוקד השיחה. כך למשל השיח בדוגמה מעלה עשוי להמשיך לבחינת התיזה כי "אומץ הוא סבילות נבונה של הנשמה". רוב הדיאלוגים הסוקרטיים מורכבים מסדרה של חקירות אלנכטיות ובדרך כלל הדיאלוג מסתיים באפוריה (יוונית: ἀπορία, מצב של בלבול, תהיה) כלומר שני הצדדים מגיעים לכלל הודאה בכך שאינם יודעים את התשובה. בכך מודגמת הסיסמה של סוקרטס "אני יודע שאינני יודע".
השיטה הסוקרטית נמצאת במוקד ויכוח פילוסופי באשר לשאלה האם היא שיטה חיובית, המובילה לרכישת ידע, או שיטה שלילית שכל מטרתה סתירת הנחתו של בן השיח באשר לידע כלשהו.
בבסיסה השיטה הסוקרטית היא שיטה שלילית של פסילת הנחות, תוך ניסיון להגיע להנחות חדשות שאינן סובלות מן הסתירות שזיהינו בהנחות המוצא. שיטתו של סוקרטס היא בחיפוש אחר הנחות היסוד, או אקסיומות, המעצבות באופן בלתי מודע את דעותיו של האדם, ולהפוך אותן למוקד השיח והבחינה. השיטה הבסיסית היא בסדרת שאלות, חלקן שאלות היגיון (לוגיקה) וחלקן שאלות עובדתיות, המסייעות לבן השיח לחשוף את אמונותיו באשר לנושא מסוים.
יישום השיטה.
סוקרטס יישם את שיטתו לבחינת מושגים החסרים הגדרה מוצקה, לדוגמה, מושגי יסוד מתחום המוסר, המידה הטובה, צדקה, חוכמה, צניעות, אומץ וצדק. בחינה שכזו קוראת תיגר על אמונותיו המוסריות של בן השיח ומבליטה סתירות באמונות אלה, עד אשר בן השיח מגיע למצב של אפוריה, דהיינו בלבול. לנוכח חוסר המוצא אליו מגיעה השיחה, מביע אף סוקרטס את אי ידיעתו. לדעת סוקרטס עצם המודעות לאי הידיעה תורמת לחוכמה וליתרון על פני אלה אשר טוענים בבורתם לידע כלשהו. אף שבמבט ראשון עמדה זו נראית כפרדוקס.