יתירות

Poll without page-refresh

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

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

תוכן עניינים

1 יתירות בהנדסה
2 תורת האינפורמציה
- 2.1 דחיסת מידע
- 2.2 סכום ביקורת
3 יתירות לשונית ויתירות רטורית
4 יתירות בתכנות
5 יתירות בקריפטוגרפיה
- 5.1 יתירות מוספת
6 ראו גם
7 קישורים חיצוניים

יתירות בהנדסה

יתירות בהנדסה הינה כפילות של מרכיבים חיוניים למערכת באופן שבמקרה של כשל באחד מהם תפקוד המערכת לא יושבת כליל אלא יועבר לביצוע מרכיב הגיבוי, בכך משפרים את אמינות ויציבות המערכת. בהקשר זה היתירות היא אמצעי גיבוי. למשל RAID קיצור של Redundant Array of Inexpensive Disks‏ הוא מבנה של כוננים קשיחים המאחסנים נתונים במספר עותקים, באופן המאפשר שחזור מידע שאבד בעת תקלה. יתירות מיושמת גם במצב המכונה אל-כשל (fail-safe), מנגנון הפועל באופן כזה שבקרות אסון או תקלה חמורה, המערכת עוברת אוטומטית לפעול במצב חרום באמצעות מערכת חלופית. אופן פעולה זה קיים במערכות קריטיות רבות, למשל בבתי חולים קיים גנרטור חשמלי שנכנס לפעולה אוטומטית כאשר רשת החשמל הכללית נופלת. דוגמה נוספת היא בלמי חרום במשאית או רכבת שמתחילים לפעול אוטומטית אם הבלמים הפסיקו לפעול כתוצאה מתקלה.

תורת האינפורמציה

את רעיון היתירות בתורת האינפורמציה הגה לראשונה קלוד שאנון אבי תורת האינפורמציה. יתירות בהקשר זה פירושה כמות הסיביות המינימלית הדרושה לשידור מידע פחות כמות הסיביות שמכיל המידע עצמו, במילים אחרות כמות השטח ה"מבוזבז" על מנת לשדר מסר מסוים. כל שפה טבעית מכילה יתירות טבעית המאפיינת אותה, זאת משום שאותיות מסוימות מופיעות לעתים תדירות יותר מאשר אותיות אחרות, למשל בשפה העברית האות יו"ד היא הנפוצה ביותר (11.7 אחוז בקירוב) לעומת האות זי"ן שהיא הנדירה ביותר (רק כ-0.9 אחוז). יתירות טבעית היא חלק בלתי נפרד מהשפה ואמורה לסייע בהבנת השפה לבני אנוש. בעזרת חישוב אנטרופיה, הוכיח שאנון כי בשפה האנגלית, המכילה 26 אותיות, כל אות מסוגלת להכיל תאורטית $\ \mbox{log}_2 26=4.7$ סיביות מידע, אולם בפועל בשל היתירות הטבעית, אותיות השפה האנגלית מעבירות פחות מידע, ליתר דיוק רק 1.5 סיביות לאות. מזה נובע כי יתירות השפה האנגלית היא $\ 4.7-1.5=3.2$ סיביות.

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

דחיסת מידע

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

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

סכום ביקורת

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

יתירות לשונית ויתירות רטורית

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

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

יתירות בתכנות

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

יתירות בקריפטוגרפיה

המושג יתירות בקריפטוגרפיה עלה לראשונה בהקשר של ניתוח תדירויות של צופנים קלאסיים כגון צופן החלפה או צופן ויז'נר. ההצלחה בניתוח הצופנים הקלאסיים נזקפה לא מעט לזכות היתירות הטבעית של השפה, זאת משום שיתירות טקסט המקור זלגה לתוך הטקסט המוצפן ואפשרה למנתח הצופן להבחין בדפוסים ייחודיים בטקסט המוצפן ובעזרת ניתוח סטטיסטי של תדירויות ניתן היה לחשוף חלק נכבד מטקסט המקור ואף את המפתח עצמו. שאנון טבע לראשונה את המונח Unicity distance שהוא מדד הכמות המינימלית של טקסט מוצפן הדרושה למנתח בעל עצמת חישוב בלתי מוגבלת כדי לפרוץ את הצופן או לחלץ את מפתח ההצפנה שבו נעשה שימוש. למשל לחילוץ מפתח ההצפנה בצופן החלפה חד-אלפביתי נדרשות לפחות 28 אותיות. הצופנים הסימטריים המודרניים פועלים על גושי מידע גדולים (כ-64 סיביות לפחות) משום כך אינם חשופים ליתירות הטבעית של שפת הטקסט המיועד להצפנה. לכן ניתוח סטטיסטי מסוג זה אינו ישים כנגדם.

יתירות מוספת

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

דוגמה נפוצה לפונקציית יתירות קריפטוגרפית מופיעה בתקן איזו ISO/IEC 9796 הפונקציה מוגדרת באופן הבא: לאחר שהמסר $\ x$ רופד והורחב לפי התקן, משלבים את $\ t$ הבתים של המסר עם $\ t$ בתים יתירים לסרוגין כך: $\ x_{2i-1}=x_i, x_{2i}=S(x_i)$ . בכך מכפילים את אורך המסר ל- $\ 2t$ בתים. הפונקציה $\ S$ הנקראת Shaddow function מוגדרת עבור קלט $\ u$ בגודל בית אחד כדלהלן:

$\ S(u)=\pi(u_2)\ ||\ \pi(u_1)$ (הסמל || מייצג שרשור, קרי הדבקת ערכים זה לצד זה במקום חיבור אריתמטי).

כאשר $\ u_1$ ו- $\ u_2$ הם שני חצאי הבית הקרויים ניבלים (כל ניבל מיוצג על ידי ספרה הקסדצימלית אחת השווה ל-4 סיביות). הפונקציה $\ \pi$ היא טבלת תמורה סטטית הבאה:

לסיום מחברים לבית האחרון ב-XOR את מספר סיביות הריפוד (מתהליך הריפוד הקודם).

יתירות מאפשרת גם הצפנה עם אימות והבטחת שלמות, על ידי שילוב צופן גושים עם פונצקיית יתירות כדלהלן: השולח מחשב פונקציה $\ h$ פומבית (פונקציית גיבוב למשל) על המסר ומקבל סכום ביקורת $\ T=h(M)$ אותו הוא משרשר למסר לפני ההצפנה $\ C=E_K(M\ ||\ T)$ . כעת בפענוח ניתן לאמת את המסר על ידי בדיקת הטקסט המפוענח $\ M||T$ אם הוא מכיל את היתירות הדרושה על ידי שימוש באותה פונקציה. אם הטקסט אינו מכיל את היתירות הדרושה ניתן להסיק כי אינו אותנטי. אפשר להבחין בשני סוגי פונקציות יתירות קריפטוגרפיות האחת פונקציית יתירות פומבית הידועה גם לתוקף פוטנציאלי, פונקציה זו אינה עושה שימוש במפתח הצפנה והשנייה יתירות סודית כלומר הפועלת עם מפתח הצפנה סודי.

ראו גם

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

Handbook of Applied Cryptography

מקור: http://he.wikipedia.org/wiki/%D7%99%D7%AA%D7%99%D7%A8%D7%95%D7%AA

קטגוריות: מידע | הצפנה

This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.

Giant Panda

Mercedes Car

This site monitored by SitePinger.net