RSA-הצפנה. תיאור ויישום אלגוריתם RSA

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

היסטוריה של יצירה

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

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

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

כאשר חלה הצפנה במתכונתו הנוכחית?

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

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

חתימה אלקטרונית ואת המפתח הציבורי

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

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

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

מהו האלגוריתם?

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

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

המפתח הציבורי מורכב של מודולוס מעריך הציבור. יחידת מקורה והוא מורכב דמות פרטית, אשר אמור להישמר בסוד.

הצפנה של קבצים וחולשות RSA

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

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

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

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

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

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

אוטומציה

הכלי, שנקרא Yafu, שניתן להשתמש בהם כדי לייעל את התהליך. אוטומציה ב YAFU היא תכונה מתקדמת המשלבת אלגוריתמים פרוקים במתודולוגיה אינטלקטואלית ובעלי כושר ההסתגלות הממזער את הזמן כדי למצוא את הגורמים של מספרי קלט שרירותיים. רוב הטמעות אלגוריתם מרובה הליכי המאפשר שימוש מלא Yafu של מולטי או רבים מעבדים מרובי-ליבות (כולל SNFS, SIQS ו ECM). קודם כל, זה נשלט על ידי כלי שורת פקודה. השעה בילה מחפשים גורם Yafu הצפנה באמצעות מחשב קונבנציונאלי, זה עשוי להיות מופחת שניות 103.1746. הכלי מעבד את בינארי קיבולת של 320 סיביות או יותר. זוהי תוכנה מאוד מורכבת הדורשת כמות מסוימת של כישורים טכניים כדי להתקין ולהגדיר. לפיכך, RSA-הצפנה עשויה להיות פגיע ג

ניסיונות פריצה בתקופה האחרונה

בשנת 2009, Bendzhamin מודים באמצעות מפתח קצת RSA-512 עבדו על פענוח kriptoteksta עבור 73 ימים, באמצעות תוכנה בלבד ידוע (GGNFS) ואת שולחן העבודה הממוצע (Athlon64 ליבה כפולה ב MHz 1900). כפי שמוצג על ידי הניסיון, נדרש מעט פחות 5 GB של דיסק וכ 2.5 ג'יגה של זיכרון עבור התהליך של "ניפוי".

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

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

סיכויים

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

באופן רשמי ב 2003, הועמדה בספק את שלומם של מפתחות 1024 סיביות. נכון לעכשיו, מומלץ להיות באורך מינימלי של 2048 ביטים.