כל מה שרצית לדעת על חתימה דיגיטלית רבין:
אלגוריתם חתימה דיגיטלית רבין הוא מנגנון חתימה דיגיטלית עם שחזור, המבוסס על הצפנת מפתח פומבי של רבין.
אלגוריתם רבין מבוסס על הפונקציה החד-כיוונית הנובעת מהקושי שבבעיית שורש ריבועי מודולו שלם פריק.
האלגוריתם הומצא על ידי פרופסור מיכאל רבין (האוניברסיטה העברית בירושלים) במהלך ביקורו כפרופסור אורח, במכון הטכנולוגי של מסצ'וסטס בשנת 1979.
אלגוריתם חתימה דיגיטלית של רבין דומה לאלגוריתם חתימה דיגיטלית RSA ובנוי ממודולוס כאשר ו- הם ראשוניים (גדולים), אולם כאן המעריך הפומבי הוא שלם זוגי קטן (בגרסה בסיסית).
המפתח הפרטי של החותם הוא צמד הגורמים , המפתח הפומבי הוא .
החתימה על המסר היא בעצם השורש הריבועי של המסר (לאחר המרתו למספר שלם בדרך מוסכמת) ואילו אימות החתימה הוא הבדיקה שאכן ערך זה הוא שורש ריבועי.
הבדיקה האם שלם כלשהו הוא שורש ריבועי מודולו קלה למדי בעוד שהפעולה ההפוכה קרי, מציאת שורש ריבועי מודולו קשה מאוד, אם הגורמים הראשוניים שלו אינם ידועים.
מרחב החתימה של המסר מוגבל לקבוצה (קבוצת השאריות הריבועיות מודולו ).
כלומר המסר חייב לייצג מספר שלם כזה שקיים עבורו שורש ריבועי מודולו .
הבעיה היא שלא כל מסר עונה על דרישה זו, יכול להיות מסר שעבורו יהיה בלתי אפשרי לחשב שורש ריבועי מודולו .
ניתן להתגבר על בעיה זו על ידי שרשור ערך אקראי קטן כלשהו למסר בתקווה שהתוצאה תהיה מספר שקיים עבורו שורש ריבועי מודולו .
בממוצע מספר הניסיונות הדרושים עד שיימצא ערך כזה הוא 2.
בשל חסרון מהותי זה אלגוריתם רבין הבסיסי המתואר להלן אינו מעשי כל כך.
להלן מתוארת גרסה משופרת של אלגוריתם רבין המבוססת על אלגוריתם וויליאמס (H.
C.
Williams) המבטלת בעיה זו.
בדומה ל-RSA גם אלגוריתם חתימה דיגטלית של רבין מחייב שימוש בפונקציית יתירות בשל קיומה של בעיה מהותית הקרויה Existential forgery, כיוון שכל שלם הוא חתימה תקפה עבור המסר , זאת ללא ידיעת המפתח הפרטי של החותם.
בשל כך תוקף פונטנציאלי עלול לזייף ערך כלשהו ולטעון כי בידו חתימה תקפה עליו.
למרות שלתוקף לא תהיה שליטה מלאה על תוכנו של המסר החתום, עובדה זו מהווה איום בלתי מבוטל.

נלקח מויקיפדיה

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