אלגוריתם חתימה דיגיטלית רבין הוא מנגנון חתימה דיגיטלית עם שחזור, המבוסס על הצפנת מפתח פומבי של רבין. אלגוריתם רבין מבוסס על הפונקציה החד-כיוונית הנובעת מהקושי שבבעיית שורש ריבועי מודולו שלם פריק. האלגוריתם הומצא על ידי פרופסור מיכאל רבין (האוניברסיטה העברית בירושלים) במהלך ביקורו כפרופסור אורח, במכון הטכנולוגי של מסצ'וסטס בשנת 1979.
אלגוריתם חתימה דיגיטלית של רבין דומה לאלגוריתם חתימה דיגיטלית RSA ובנוי ממודולוס formula_1 כאשר formula_2 ו-formula_3 הם ראשוניים (גדולים), אולם כאן המעריך הפומבי formula_4 הוא שלם זוגי קטן formula_5 (בגרסה בסיסית). המפתח הפרטי של החותם הוא צמד הגורמים formula_6, המפתח הפומבי הוא formula_7. החתימה על המסר היא בעצם השורש הריבועי של המסר (לאחר המרתו למספר שלם בדרך מוסכמת) ואילו אימות החתימה הוא הבדיקה שאכן ערך זה הוא שורש ריבועי. הבדיקה האם שלם כלשהו הוא שורש ריבועי מודולו formula_7 קלה למדי בעוד שהפעולה ההפוכה קרי, מציאת שורש ריבועי מודולו formula_7 קשה מאוד, אם הגורמים הראשוניים שלו אינם ידועים.
מרחב החתימה של המסר מוגבל לקבוצה formula_10 (קבוצת השאריות הריבועיות מודולו formula_7). כלומר המסר חייב לייצג מספר שלם כזה שקיים עבורו שורש ריבועי מודולו formula_7. הבעיה היא שלא כל מסר עונה על דרישה זו, יכול להיות מסר שעבורו יהיה בלתי אפשרי לחשב שורש ריבועי מודולו formula_7. ניתן להתגבר על בעיה זו על ידי שרשור ערך אקראי קטן כלשהו למסר בתקווה שהתוצאה תהיה מספר שקיים עבורו שורש ריבועי מודולו formula_7. בממוצע מספר הניסיונות הדרושים עד שיימצא ערך כזה הוא 2. בשל חיסרון מהותי זה אלגוריתם רבין הבסיסי המתואר להלן אינו מעשי כל כך. להלן מתוארת גרסה משופרת של אלגוריתם רבין המבוססת על אלגוריתם ויליאמס (H. C. Williams) המבטלת בעיה זו.
בדומה ל-RSA גם אלגוריתם חתימה דיגיטלית של רבין מחייב שימוש בפונקציית יתירות בשל קיומה של בעיה מהותית הקרויה Existential forgery, כיוון שכל שלם formula_15 הוא חתימה תקפה עבור המסר formula_16, זאת ללא ידיעת המפתח הפרטי של החותם. בשל כך תוקף פוטנציאלי עלול לזייף ערך כלשהו ולטעון כי בידו חתימה תקפה עליו. אף על פי שלתוקף לא תהיה שליטה מלאה על תוכנו של המסר החתום, עובדה זו מהווה איום בלתי מבוטל.
פירוט האלגוריתם הבסיסי.
תהליך אימות ושחזור המסר המקורי m.
בהינתן המפתח הפומבי formula_7 והחתימה formula_27 בודקים כדלהלן:
הערה: לצורך אימות החתימה לא נדרש המסר המקורי כיוון שאלגוריתם החתימה מאפשר שיחזור המסר המקורי.
דוגמה במספרים קטנים.
יהיו הפרמטרים הבסיסיים: formula_32, formula_33, שניהם שקולים ל-formula_34 מודולו formula_35, ויהיה formula_36. מפתח החתימה אם כן הוא formula_37 מפתח האימות הוא formula_38. כדי לחתום על המסר formula_39, החותם מחשב את השורשים הרבועיים של formula_40 שהם: formula_41. החותם בוחר אחד מהם נניח formula_42. כדי לאמת את החתימה המאמת מחשב את formula_43. כיוון ש-formula_44 החתימה מתקבלת.
בטיחות.
גודל הראשוניים הוא גורם עיקרי בבטיחות האלגוריתם, בשל העובדה שפירוק המודולוס לגורמיו (כלומר מציאת formula_2 ו-formula_3), בעצם פורצת את האלגוריתם לחלוטין. על כן חובה שהם יהיו גדולים מספיק כדי לסכל ניסיון כזה. יכולת פירוק מספרים גדולים מצויה כיום בקצב שיפור תמידי, עקב שיפורים טכנולוגיים והתפתחויות בתורת המספרים, בעיקר באלגוריתמים לפירוק לגורמים (כמו אלגוריתם נפת שדה המספרים). ובשל איחוד משאבים וכוחות מיחשוב כלל עולמיים, היכולת הזו הולכת ומתעצמת. הערכה זהירה מניחה כי נכון להיום מודולוס בגודל 2048 סיביות, נמצא דרגה אחת מעל היכולת הנוכחית ועל כן בטוח לפחות למשך מספר שנים.
פונקציית יתירות.
כאמור פונקציית יתירות היא מרכיב קריטי באלגוריתם רבין. על כן ישנה חשיבות רבה בבחירת פונקציית יתירות בטוחה ככל האפשר. תקן איזו ISO/IEC 9796 מפרט פונקציה כזו. הרעיון הוא שימוש בפונקציה Shaddow function אשר מבצעת תמורה על שני חלקי כל בית במסר (ארבע סיביות כנגד ארבע סיביות) לפי טבלה קבועה. תוצאת הפונקציה משולבת בין בתי המסר לסירוגין. קיימות מספר שיטות הוספת יתירות עבור חתימה דיגיטלית.
גרסה משופרת של האלגוריתם.
בשל החיסרון האמור לעיל, פותחה גרסה משופרת של אלגוריתם רבין המבוססת על אלגוריתם וויליאמס, שמאפשרת לבנות את המסרים כך שיענו על הדרישה האמורה באופן דטרמיניסטי, כלומר שלכל מסר אפשרי יהיה שורש ריבועי מודולו formula_7. גרסה זו הושאלה מגרסת הצפנת מפתח פומבי שהציע לשיפור RSA שלדבריו מספקת בטיחות מוכחת. שיטה זו אומצה בתקן איזו ISO/IEC 9796. הרעיון של וויליאמס הוא שעבור כל שלם formula_48 הערך formula_49 הוא שורש ריבועי של formula_50 מודולו formula_7. לכן אם formula_52 אזי formula_53. אם formula_50 אינו שארית ריבועית מודולו formula_7 אזי formula_56. עובדה זו מאפשרת שיפור אלגוריתם החתימה של רבין כדלהלן.
פירוט האלגוריתם.
מרחב המסר המיועד לחתימה הוא formula_57 כמו כן formula_58 חייב להיות קטן מ-formula_59. כאשר פונקציית היתירות היא: formula_60.
תהליך חתימה על המסר m.
הערה: מעשית הסיכוי ש-formula_75 יהיה שווה אפס נמוך ביותר מאחר שמשמעות הדבר היא ש-formula_76 הוא אחד הגורמים הראשוניים של formula_7.
דוגמה במספרים קטנים לאלגוריתם המשופר.
יהיו הפרמטרים הבסיסיים: formula_90 וכן formula_91 כאשר שניהם מקיימים את התנאים האמורים לעיל. ויהיה formula_92. מפתח האימות הוא אם כן formula_93 ומפתח החתימה הוא formula_94. נניח שהמסר המיועד לחתימה הוא formula_95 ולאחר הפעלת פונקציית היתירות: formula_96. בחישוב סימן יעקובי מתקבל formula_97. החתימה על המסר היא אם כן: formula_98.
כדי לאמת את החתימה הבודק מחשב את formula_99, כיוון ש-formula_100 התוצאה תהיה formula_101, הפעלת הפונקציה ההופכית נותנת formula_102, כיוון ש-formula_44 החתימה מתקבלת.
בטיחות.
האלגוריתם המשופר מציע יתרון ברור על פני האלגוריתם המקורי בכך שהוא מציע דרך דטרמיניסטית לבניית המסר באופן שתמיד יהיה שורש ריבועי עבורו אולם עם אלגוריתם זה אין לחתום על מסר שלו סימן יעקובי formula_104 מאחר שזה מאפשר פירוק המודולוס לגורמיו. בטיחות אלגוריתם זה זהה לגרסה הבסיסית, בכך שניתן להוכיח כי הוא עמיד כפירוק לגורמים. וכמו בגרסה הבסיסית גם אלגוריתם זה סובל מ-Existential forgery כלומר קל למצוא formula_27 כלשהו אשר אחד מהערכים formula_106 מודולו formula_7 שקול ל-formula_108 מודולו formula_109 ואז formula_27 יהיה חתימה תקפה עבור formula_111.
הגרסה המשופרת של אלגוריתם רבין מצריכה חישוב סימן יעקובי מלבד חישוב שורש ריבועי מודולו formula_7 ועל כן יעילה מעט פחות מהאלגוריתם הבסיסי. אולם מאפשרת שימוש במעריך שונה מ-2 בתנאי ש-formula_113 שאז בדומה ל-RSA העלאה בחזקת formula_4 תהיה תמורה ב-formula_10 מה שמאפשר שחזור הערך המקורי בהינתן formula_116.
גרד אלברכט
גרד אלברכט (בגרמנית: Gerd Albrecht; 19 ביולי 1935 - 2 בפברואר 2014) היה מנצח גרמני שכיהן כמנצח ראשי בתזמורות חשובות באירופה, מאז החל בתזמורת טונהאלה בציריך, שווייץ, בשנת 1975.
המחלוקת בתזמורת הפילהרמונית הצ'כית.
אלברכט נבחר בשנת 1991 על ידי נגני התזמורת הפילהרמונית הצ'כית כמנצח הראשי, לתקופת כהונה של שבע שנים החל ב-1994. התזמורת מילאה תפקיד במחאה על השלטון הסובייטי בארצם והתארגנה מחדש כישות עצמאית. בבחירתם באלברכט הביאו להחלפתו של המנצח הצ'כי ייז'י בלוהלאווק, שהקדים את פרישתו ל-1992. כתוצאה מכך, כשהגיעה שעתו של אלברכט לקבל לידיו את התזמורת, כבר הייתה זו מפולגת, במידת מה. אלברכט הוכיח את מיומנותו בשיפור מצבה הכספי של הפילהרמונית הצ'כית ובהעלאת הפרופיל הבינלאומי שלה באמצעות מסעות קונצרטים מחוץ לגבולות צ'כיה. גם הצלחתו המוזיקלית הוכרה ללא עוררין. אף על פי כן, שורה של סכסוכים פוליטיים הביאה לפרישתו המוקדמת.
ב-1994 הוזמנה הפילהרמונית הצ'כית להופיע בותיקן בקונצרט שנועד לחגוג את הפיוס בין הקתולים ליהודים. ואולם, ההזמנה הייתה לנגינה תחת שרביטו של גילברט לוין, שנודע כבר בקשריו הטובים עם הוותיקן בתקופת האפיפיור יוחנן פאולוס השני ובהמשך לכך ב"קונצרט האפיפיור לזכר השואה", שזכה לכיסוי נרחב בטלוויזיה. אלברכט פסל את השתתפות התזמורת, לכאורה בשל עומס רב מדי. אלא שרבים חשדו, שהסיבה העיקרית לסירוב הייתה קנאתו של אלברכט על שלא הוזמן בעצמו לנצח על הקונצרט.
נשיא צ'כיה, ואצלב האוול, התערב בפרשה ואמר לאלברכט, שפעולותיו מזיקות לתזמורת. המצב התדרדר בהתמדה, כשאלברכט הציג עצמו בראיונות לעיתונות כקורבן של גזענות ורגשות אנטי-גרמנים וכמי שנתבע לכפר אישית על כל עוולותיה של גרמניה בעבר. עוד קבל על התקנת ציתות במכשיר הטלפון שלו. האוול השיב מלחמה שערה באמצעי התקשורת בטענות משלו. אלברכט ובלוהלאווק חברו יחדיו לקונצרט חגיגות המאה של התזמורת, כשכל אחד מהם מנצח על מחצית הקונצרט, ב-4 בינואר 1996, אבל האוול בלט בהיעדרו ונגני התזמורת הפגינו למי נתונה אהדתם בהגיע השעה לתשואות. אלברכט התפטר ממשרתו זו כעבור חודש, בטענת חתירה תחת סמכותו המוזיקלית. מאז ניצח ביפן ובדנמרק.
לקריאה נוספת.
Alan Levy. "Storm at Czech Philharmonic", International Herald Tribune, 31 Jan 1996. Retrieved on 2007-05-28.
פורמולה 1 עונת 2000